Discussion On The Related Problems Of Chase Type Decoding Algorithm

In1972, a class of iterative soft decision decoding method is proposed by Chase, this method is able to get close to performance of the maximum likelihood decoding and is suitable for many kinds of block codes, this method is now known as Chase-like decoding algorithm. Candidate codewords of Chase-like decoding algorithm are got by using the threshold distance decoding around some search center, and the search center is got when a hard decision vector is added to some wrong pattern according to the reliability measure of vector. In this paper, we will discuss this kind of iterative soft decision decoding algorithm-Chase-like decoding algorithm. There are three different solutions of the original Chase decoding algorithm, they are called Chase-1algorithm, Chase-2algorithm and Chase-3algorithm. Chase-3algorithm’s complexity is smaller than Chase-1algorithm’s and Chase-2algorithm’s complexity, but the performance is even worse. When the distance is very big, Chase-3algorithm’s prominent advantage is that the number of test sequences will be in linear increasing, rather like being in exponential growth for Chase-1algorithm and Chase-2algorithm. In recent years, these algorithms are improved and applied, Chase-2algorithm is used more widely in practice. For binary linear block code decoding with Hamming distance d in additive white gaussian noise channel, if square error correction radius is equal to the Hamming distance d, we think this decoding algorithm is achieved BD decoding algorithm. BD decoding algorithm is asymptotically optimal. We let Δ(d) or η(d) note the minimum number of input vector.In this paper, we explore the structure of the Chase-3-like algorithm and its minimum sequence, conditions of Chase-3-like algorithm achieving BD decoding algorithm, upper bounds of the minimum number of input vector. To improve Chase-3-like algorithm’s upper bound of the minimum number of input vector, we constructed a new type of Chase-like algorithm, respectively explored the structure of smallest sequence of this new type Chase-like algorithm, conditions of this new type decoding algorithm achieving BD decoding algorithm, upper and lower bounds of the minimum number of input vector. When the distance d tends to infinity, the present best study about the upper bound isη(d)≤(λ＋o(1))d1/2. In this paper, we proved a best result:Δ(d)≤(ψ＋o(1))d1/2.