Average Complexity Evaluation of an MLD Algorithm Using the Trellis Structure for a Linear Block Code

Hidehisa NAGANO, Toru FUJIWARA, Tadao KASAMI

Summary :

This letter is concerned with the evaluation of the average computational complexity of the maximum likelihood decoding of a linear block code using its trellis diagram. Each section of the L-section minimal trellis diagram for a linear block code consists of parallel components which are structurally identical subgraphs without cross connection between them. A parallel component is also known to be decomposed into subgraphs, and a decoding algorithm by using the structure of the subgraphs of parallel components was proposed, and an upper bound on the worst case computational complexity was derived. In this letter, the average computational complexity of the decoding algorithm is evaluated by computer simulation. We evaluated the average numbers of additions and comparisons performed in the decoding algorithm for example codes, (64,45) extended and permuted binary primitive BCH code, the third order Reed-Muller (64,42) code and its (64,40) subcode. It is shown that the average numbers are much smaller than those for the worst case, and hence the decoding algorithm is efficient when the number of sections, L, is small, say 4 or 8, for the example codes. Especially, for the (64,45) extended binary primitive BCH code with L4, the average numbers of additions and comparisons in the decoding algorithm for finding the survivor's metric of each state after finding the smallest metric among parallel branches are about 1/50 and 17/100 of those in the conventional exhaustive search, respectively. The number of additions and comparisons by the conventional search for all the example codes is smallest when L is 4. As a result, the decoding algorithm with L4 gives the smallest number of operations among those decoding methods considered here.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E78-A No.9 pp.1209-1214
• Publication Date: 1995/09/25
• Type of Manuscript: Special Section LETTER (Special Section on Information Theory and Its Applications)

Authors

Hidehisa NAGANO
Toru FUJIWARA
Tadao KASAMI

Keyword

maximum likelihood decoding,  linear block code,  BCH code,  Reed-Muller code,  L-section minimal trellis diagram