On viewing block codes as finite automata

✍ Scribed by Priti Shankar; Amitava Dasgupta; Kaustubh Deshmukh; B.Sundar Rajan

• Book ID: 104325384
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 320 KB
• Volume: 290
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00083-x

✦ Synopsis

Block codes are viewed from a formal language theoretic perspective. It is shown that properties of trellises for subclasses of block codes called rectangular codes follow naturally from the Myhill Nerode theorem. A technique termed subtrellis overlaying is introduced with the object of reducing decoder complexity. Necessary and su cient conditions for trellis overlaying are derived from the representation of the block code as a group, partitioned into a subgroup and its cosets. The conditions turn out to be simple constraints on coset leaders. It is seen that overlayed trellises are tail-biting trellises for which decoding is generally more e cient than that for conventional trellises. Finally, a decoding algorithm for tail-biting trellises is described, and the results of some simulations are presented.