Chase, Based Decoding Algorithm

The decoding of binary block codes is a very important problem both in coding theory and practical application. So far, many iterative softdecision decoding algorithms have been sufficiently developed, most of these algorithms are devised to find the best (or the most likely) codeword in a series of candidates which are usually generated with simple internal decoders (such as an algebraic decoder)as the output.In general, for an iterative soft-decision decoding algorithm, the internal decoder may failed to generate new codeword candidates at some iterative steps. Hence, the execution of these iterative steps may prolong the decoding delay. Therefore, it is desired to reduce the iterative steps as many as possible and the decoding complexity without degrading the error performance of the algorithm. Usually, at the end of each iterative step, some more suitably devised conditions are tested to control the iterative process. Ruling-out conditions and early termination conditions are two classes of such kind of testing conditions which have been used widely. If a ruling-out condition is satisfied, then, in a few successive iterative steps which are prearranged by the algorithm, the internal decoder can not generate any codeword candidate which may be better than the best codeword candidate obtained so far, and thus these successive iterative steps can be skipped. An early termination condition can be viewed as the strongest version of a ruling-out condition. If a ruling-out condition is satisfied, then there is no improvement on error performance by the following iterative steps, and thus the iterative process is terminated.This thesis discuss one of the iterative softdecision decoding algorithms—Chase-type decoding algorithm whose codeword candidates generate by bounded distance(BD) decoding around the words(called search centers) which are obtained by adding hard-decision sequences to given error patterns which are based on the reliability of received sequences. The original Chase decoding algorithms are Chase-1, Chase-2 and Chase-3, In recent years, these algorithms have been improved and applied, and Chase-2 is applied more widely. The third chapter of this thesis analyze a class of Chase-type decoding algorithm, and devise some effective testing conditions for it such as optimality conditions and ruling-out conditions, and also give some suggestions about how to use these conditions.