Low weight subtrellises for binary linear block codes and their applications

Tadao Kasami, Takuya Koumoto, Toru Fujiwara, Hiroshi Yamamoto, Yoshihisa Desaki, Shu Lin

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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 subtrellisbased decoding algorithm is proposed. This recursive algorithm is more efficient than the conventional Viterbi algorithm.

Original languageEnglish
Pages (from-to)2095-2102
Number of pages8
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number11
Publication statusPublished - Jan 1 1997
Externally publishedYes


  • Binary linear code
  • Low weight
  • Recursive decoding algorithm
  • Subtrellis diagram
  • Subtrellis search

ASJC Scopus subject areas

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Low weight subtrellises for binary linear block codes and their applications'. Together they form a unique fingerprint.

Cite this