Map decoding of linear block codes, iterative decoding of Reed-Solomon codes and interactive concatenated turbo coding systems

This dissertation is intended to investigate soft-decision decoding algorithms for block codes and concatenated coding systems to achieve high performance with reduced decoding complexity. Research consists of three major parts.; The first part presents modified MAP, Log-MAP and Max-Log-MAP algorithms for decoding linear block codes based on their sectionalized trellises. Using the structural properties of properly sectionalized trellises, the decoding complexity and delay of the MAP algorithms can be significantly reduced. Computation-wise optimum sectionalizations of a trellis for MAP algorithms are investigated. Also presented in this dissertation are bi-directional and parallel MAP decodings.; Part two of the dissertation presents an interactive concatenated turbo coding system in which an RS outer code is concatenated with a binary turbo inner code to achieve both good bit-error and frame-error performances. The outer code decoder and the inner turbo code decoder interact with each other. The inner turbo decoder provides reliability information for soft-decision decoding of the outer code. The outer code helps the inner turbo decoding to terminate its iterative process with a new stopping criterion which provides a significant reduction in the number of decoding iterations and hence reduces decoding delay.; The final part of the dissertation first presents a method for expanding a Reed-Solomon code over GF GF2m into a binary image code. Then, turbo decoding of a RS code through binary decomposition is presented. In order to reduce the decoding complexity, the binary image of entire RS code is first decomposed into a set of correlated binary component codes, each binary component code has much less trellis complexity than the entire code. Then, a concatenation system is formed, in which the binary component codes are used as the inner codes. The outer code is the RS code itself. The inner decoding of this concatenated code is turbo decoding and the outer decoding is algebraic or reliability-based soft-decision decoding. Due to the binary decomposition, the decoding complexity of the proposed algorithm is reduced drastically compared with other existing soft-decision decoding algorithms for RS codes, especially for those codes with long code lengths.