The Optimal Sectionalized Trellises for the Generalized Version of Viterbi Algorithm of Linear Block Codes and Its Application to Reed-Muller Codes

Yuansheng TANG  Toru FUJIWARA  Tadao KASAMI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E83-A   No.11   pp.2329-2340
Publication Date: 2000/11/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Coding Theory
linear block code,  sectionalization,  minimal sectionalized trellis,  generalized Viterbi algorithm,  computational complexity,  

Full Text: PDF(508.3KB)>>
Buy this Article

An algorithm for finding the optimal sectionalization for sectionalized trellises with respect to distinct optimality criterions was presented by Lafourcade and Vardy. In this paper, for linear block codes, we give a direct method for finding the optimal sectionalization when the optimality criterion is chosen as the total number |E| of the edges, the expansion index |E|-|V|+1, or the quantity 2|E|-|V|+1, only using the dimensions of the past and future sub-codes. A more concrete method for determining the optimal sectionalization is given for the Reed-Muller codes with the natural lexicographic coordinate ordering.