An Investigation on Sectionalized Block Codes and Their Dual

Block codes have large and time-varying trellis diagram. Viterbi and Maximum-A-Posteriori (MAP) decoders are very complex. This thesis shows how to utilize sectionalized trellis diagrams in these two decoding schemes to minimize computational complexity and memory storage requirements. For high rate {k > n - k) component codes, decoding using the sectionalized trellis of the dual code is most advantageous. For Viterbi algorithm, most of Hamming codes can save around 50% in real operations compared to decoding based on the original bit-level trellis and the memory storage is also reduced based on the code length and the boundary location of sectionalized trellises. The longer the code length, the more the pre-computations required. For example, extended Hamming (32, 26) needs 528 x 1457 operations for first step calculation, 32 x 192 operations for second step calculation and 16896 for decoding complexity calculation and requires three 32 x 32 matrices to store them. Optimum sectionalization can be obtained from optimal permutation. For Hamming, Reed-Muller and Golay codes, optimal permutation thus optimal sectionalization is achieved with natural binary ordering permutation. Vardy algorithm requires a large number of pre-determined calculations and memory spaces. This technique is not suitable for long block codes. A more practical algorithm-straightforward algorithm, which trades complexity for implementation simplicity is proposed in this thesis. For dual codes, excluding the complicated pre-determined calculations Vardy algorithm offers 50% reduction in trellis complexity, whereas the proposed straightforward algorithm reduces the complexity by 30%. The straightforward algorithm does not require any pre-determined calculations. Performance of unsectionalized MAP, sectionalized MAP and MAX-Log-MAP algorithms are simulated and results show that they perform considerably equal. Based on simulation results and theoretical analysis, it is shown that MAX-Log-MAP algorithm is independent of sectionalization