Research On The Selection Method Of Chase - Type Decoding Algorithm Search Center

In this thesis,we mainly deal with soft-decision decoding algotihms for binary linear block codes over the additive white Gaussian noise(AWGN)channel with binary phase-shift keying(BPSK)signaling.Although a maximum-likelihood (ML)decoding algorithm minimizes the probability of decoding error,the computational complexity of ML decoding remains very high for long codes. Hence,suboptimum soft-decision decoding algorithms,which provide an efficient tradeoff between the error performance and the decoding complexity,are highly attractive for both coding theorists and practicing communication engineers.Reliability-order-based decoding algorithms(ROBDAs),which are widely used in practical communication systems,are sub-optimum soft-decision decoding algorithms.Any ROBDA is asymptotically optimal if it achieves bounded-distance (BD)decoding.Any Chase-like decoding algorithm is a ROBDA which outputs the best(most likely)codeword in a list of candidates generated by a conventional algebraic binary decoder around some given search centers.Chase-like decoding algorithms are generaltzations of the iterative soft-decision decoding algorithms proposed by Chase in[1].The original Chase decoding algorithms achieve BD decoding with(d/2 N),2[d/2] and[d/2]+1search centers,respectively,where N and d denote the length and minimum Hamming distance of the code, respectiVely.In Chase-3 decoding algorithm,the non-zero components of the search centers are confined in the most unreliable positions.Since the decoding complexity of a Chase-life decoding algorithm is by and large proportional to the number of search centers, it is of interest to design Chase-like BD decoding algorithms with as least number of search centers as possible. Let Δ(d) denote the smallest size of the search center set of Chase-like BD decoding algorithms. In 2003, Δ(d)≤[(d+2)/4] and Δ(d)≤[d/6]+1 were proved in [2] and [3], respectively. When the minimal Hamming distance d approaches to infinity, the asymptotical upper boundsΔ(d)≤O(d2/3), Δ(d)≤O(d⊥/2+ε)), Δ(d)≤O(√dlnd) were shown in [4], [5], [6], respectively. In [7], it was further proved that　Δ(d)≤ Ψ+o(1))d1/2,Ψ≈2.414.In this thesis, we showed that Chase-3-like decoding algorithms can achieve BD decoding with less search centers when adding some search centers of other type. If we add 5 search centers of other type to a Chase-3-like decoding algorithm, it can achieve BD decoding within (μ+o(1))d1/2 search centers, where μ≈2.173. Furthermore, if we add more search centers to the Chase-3-like decoding algorithms, the constant μ can be replaced by μ’, where μ’≈2.10.