A note on the computation of the bit error rate for binary block codes

Vladimir B. Balakirsky

Michele Elia

Gérard Cohen, Philippe Godlewski

Bin Zhang

This paper shows that bit-level reliability can be converted into block-level reliability for binary codes over BMS channels through Forney's concatenation scheme. The construction concatenates an inner code of rate R-o(1) and vanishing bit-error probability εwith an outer code of rate 1-o(1) equipped with a bounded-distance decoder. We show that, when the outer correction radius exceeds εand a suitable large-deviation condition holds, the concatenated code has rate R-o(1) and vanishing block-error probability. Hence, a family with vanishing bit-error probability for rates below capacity can be converted into a capacity-achieving concatenated-code family. We further show that, when binary BCH codes are used as outer codes, inner codes with bit-error probability ε=o(1/\log\log n) can be converted into a capacity-achieving concatenated family.

Bruce L. Montgomery

This dissertation investigates the complexity of minimum-distance decoding (MDD) algorithms for general binary linear block codes, and also investigates the use of such codes in constructing error correcting/detecting codes that are effective against both random and unidirectional errors. A new MDD algorithm is proposed, and its complexity is analyzed and compared to that of other such algorithms. The question of whether all good codes satisfy certain properties required for efficient implementation of the algorithm is also considered. The performance of decoding algorithms, with the information bit error rate as the criterion instead of the block error rate, is also studied. New decoding rules which can yield lower information bit error rates than the MDD rule are proposed and evaluated. A new class of binary codes is developed which corrects random errors and detects all unidirectional errors. These codes are obtained by appending a suffix to each codeword of a linear block code. To evaluate the efficiency of the new codes, a thorough comparison with the best previously obtained codes is made.

Saif E. A. Alnawayseh, Pavel Loskot

The ordered statistics-based list decoding techniques for linear binary block codes of small to medium block length are investigated. The construction of a list of the test error patterns is considered. The original ordered-statistics decoding (OSD) is generalized by assuming segmentation of the most reliable independent positions (MRIPs) of the received bits. The segmentation is shown to overcome several drawbacks of the original OSD. The complexity of the ordered statistics-based decoding is further reduced by assuming a partial ordering of the received bits in order to avoid the complex Gauss elimination. The probability of the test error patterns in the decoding list is derived. The bit error rate performance and the decoding complexity trade-off of the proposed decoding algorithms is studied by computer simulations. Numerical examples show that, in some cases, the proposed decoding schemes are superior to the original OSD in terms of both the bit error rate performance as well as the decoding complexity.