Half-ChaseAlgorithm ofNon-softDecision Decoding Based on Majority

Chun-Fong Kuo, Hsin-Kun Lai, Erl‐Huei Lu

Published Jan 1, 2007• 0 citations

Abstract

Anon-soft decision decoding algorithm forbinary linear block codes transmitted overAWGN channel ispresented. Unlike soft decision decoding algorithms, theproposed algorithm doesnotcomputing weighted Hammingdistances. Basedonthe majority ofcodewordcandidates fromtheharddecision decodingoutput,the proposedalgorithmimproves error-correcting performance byldBofcoding gaincompared tothatofharddecision decoding algorithms. Also, aschematic block diagram forfinding thecodewordofmajority isdeveloped. Furthermore, a comparison ofhardware complexity ismade between thecomputation ofweighted Hammingdistances and thefinding ofmajority codeword.

Related papers

Half-Chase Algorithm of Non-soft Decision Decoding Based on Majority

Chun-Fong Kuo, Hsin-Kun Lai, Erl‐Huei Lu

A non-soft decision decoding algorithm for binary linear block codes transmitted over AWGN channel is presented. Unlike soft decision decoding algorithms, the proposed algorithm does not computing weighted Hamming distances. Based on the majority of code word candidates from the hard decision decoding output, the proposed algorithm improves error-correcting performance by 1 dB of coding gain compared to that of hard decision decoding algorithms. Also, a schematic block diagram for finding the codeword of majority is developed. Furthermore, a comparison of hardware complexity is made between the computation of weighted Hamming distances and the finding of majority code word.

International Conference on Advanced Communication TechnologyFeb 1, 20070 citations

Majority Voting Procedure Allowing Soft Decision Decoding of Linear Block Codes on Binary Channels

Saïd Nouh, Achraf El Khatabi, Mostafa Belkasmi

In this paper we present an efficient algorithm to decode linear block codes on binary channels. The main idea consists in using a vote procedure in order to elaborate artificial reliabilities of the binary received word and to present the obtained real vector r as inputs of a SIHO decoder (Soft In/Hard Out). The goal of the latter is to try to find the closest codeword to r in terms of the Euclidean distance. A comparison of the proposed algorithm over the AWGN channel with the Majority logic decoder, Berlekamp-Massey, Bit Flipping, Hartman-Rudolf algorithms and others show that it is more efficient in terms of performance. The complexity of the proposed decoder depends on the weight of the error to decode, on the code structure and also on the used SIHO decoder.

International Journal of Communications Network and System SciencesJan 1, 201211 citations

Study on Iterative Soft-Decision Decoding Algorithms for Binary Linear Block Codes

卓也甲本

For iterative soft-decision decoding algorithms for binary linear block codes, error performance and computational complexity are very important factors.In this thesis, suÆcient conditions of the optimality of decoded codeword and a suÆcient condition which is used for ruling-out some useless iterations of bounded distance decoding which reduces the computational complexity of iterative soft-decision decoding algorithms are shown.New iterative soft-decision decoding algorithms which uses the suÆcient conditions of the optimality of decoded codeword to achievegood error performance with small computational complexity are also shown.First, the suÆcient conditions are derived based on: (1) partial knowledge of the distance pro le of the code, and (2) previously generated candidate codewords.When the numberof previously generated candidate codewords is greater than 1, the conditions presented here are less stringent than those derived by Taipale and Pursley [4] and Kaneko et.al.[5].The condition based on three previously generated candidate codewords is the rst such s u Æ c i e n t condition that has ever been derived.It is shown by computer simulation that these suÆcient condions reduce the computational complexity of iterative decoding algorithms without degradation of error performance.Second, a suÆcient condition to rule-out some useless test error patterns is derived.In an iterative decoding algorithm, such as Chase Type-II decoding algorithm[2] and its improved versions, candidate codewords for a received vector are generated

Mar 24, 19991 citation

Soft-decision majority decoding of Reed-Muller codes

Ilya I. Dumer, R.E. Krichevskiy

We present a new soft-decision majority decoding algorithm for Reed-Muller codes RM(r,m). First, the reliabilities of 2/sup m/ transmitted symbols are recalculated into the reliabilities of 2/sup m-r/ parity checks that represent each information bit. In turn, information bits are obtained by the weighted majority that gives more weight to more reliable parity checks. It is proven that for long low-rate codes RM(r,m), our soft-decision algorithm outperforms its conventional hard-decision counterpart by 10 log/sub 10/(/spl pi//2)/spl ap/2 dB at any given output error probability. For fixed code rate R and m/spl rarr//spl infin/, our algorithm increases almost 2/sup r/2/ times the correcting capability of soft-decision bounded distance decoding.

IEEE Transactions on Information TheoryJan 1, 200031 citations

Semi-soft Decision Decoding Based on Correspondence between Error Patterns and the Relative Test Patterns

Hsin-Kun Lai, Erl‐Huei Lu

A semi-soft decision decoding algorithm based on the correspondence between error patterns and the relative test patterns for binary linear block codes over AWGN channel is presented. The proposed algorithm improves coding gain by 0.8 dB without computing weighted Hamming distances.

International Conference on Innovative Computing, Information and ControlSep 1, 20070 citations

Design of optimization techniques for soft-decision decoding of linear block codes

Ching-Cheng Shih

This dissertation deals with maximum-likelihood soft-decision decoding as well as suboptimal soft-decision decoding of linear block codes. We present three new decoding algorithms: $MA\sp*D,\ H\sp*,$ and Directed Search. The first algorithm, $MA\sp*D,$ is an instance of Algorithm $A\sp*$ that conducts heuristic search through a code tree of the transmitted code when the decoding problem is transformed into a problem of graph-search through a code tree. $MA\sp*D$ takes into consideration more properties of the code and is considerably more efficient than the original $A\sp*$ decoding algorithm presented by Han, Hartmann, and Chen in 1993. The second algorithm, $H\sp*,$ is a new decoding algorithm that determines the value of every component of a minimum-cost codeword by estimating the cost of the minimum-cost codeword, which has a fixed value at one of the k most reliable, linearly independent bit positions. The suboptimal version of this algorithm is combined with other decoding algorithms to reduce the search space during the decoding process. The third algorithm, Directed Search, is designed to enhance the performance of soft-decision decoding by searching in continuous space. This approach explores the search space between a given vector and the received vector and finds the codeword closest to the received vector in the space explored. We also present a novel and efficient hybrid decoding algorithm for (n, k) linear block codes. It hybridizes $MA\sp*D,\ H\sp*,$ and Directed Search algorithms, utilizing their strengths to make the decoding more efficient. Simulation results for this hybrid algorithm are presented for the (104,52) binary-extended quadratic residue code and for the (128,64), the (256, 131), and the (256, 139) binary-extended BCH codes. This hybrid algorithm can efficiently decode the (104,52) binary extended quadratic residue code and the (128,64) code for any signal-to-noise ratio and has near-optimal to optimal performance. Previously, no practical decoder could decode these two codes with such a performance for all signal-to-noise ratio ranges.

Jan 1, 19960 citations