Low Weight Subtrellises for Binary Linear Block Codes and Their Applications

Tadao KASAMI  Takuya KOUMOTO  Toru FUJIWARA  Hiroshi YAMAMOTO  Yoshihisa DESAKI  Shu LIN  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E80-A   No.11   pp.2095-2103
Publication Date: 1997/11/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Coding Theory
subtrellis diagram,  low weight,  binary linear code,  recursive decoding algorithm,  subtrellis search,  

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

Subtrellises for low-weight codewords of binary linear block codes have been recently used in a number of trellis-based decoding algorithms to achieve near-optimum or suboptimum error performance with a significant reduction in decoding complexity. An algorithm for purging a full code trellis to obtain a low-weight subtrellis has been proposed by H.T. Moorthy et al. This algorithm is effective for codes of short to medium lengths, however for long codes, it becomes very time consuming. This paper investigates the structure and complexity of low-weight subtrellises for binary linear block codes. A construction method for these subtrellises is presented. The state and branch complexities of low-weight subtrellises for Reed-Muller codes and some extended BCH codes are given. In addition, a recursive algorithm for searching the most likely codeword in low-weight subtrellis-based decoding algorithm is proposed. This recursive algorithm is more efficient than the conventional Viterbi algorithm.