IEEE Transactions on Information Theory

Reed-Muller codes for error detection: the good, the bad, and the ugly

Torleiv Kløve

Published Jan 1, 1996• 12 citations

Abstract

The error detecting capability of Reed-Muller codes is analyzed. If a block code is used for error detection only, then an error is undetectable if it transforms a codeword into another codeword. The probability of undetected error for a binary [n,k] code C used on a binary-symmetric channel with crossover probability p, is given.

DOI: 10.1109/18.532910

Related papers

An Efficient Block Error Probability Estimation of Reed-Muller Codes under Permutation Decoding

Mikhail Kamenev

A method for estimating the block error probability of Reed-Muller codes on a binary erasure channel and a binary symmetric channel under a permutation decoding algorithm is proposed. This method is based on an analysis of the block error probability under a recursive decoding algorithm for a fixed number of input erasures or errors. Simulation results demonstrate that the proposed method allows to effectively predict the block error rate performance of Reed-Muller codes under permutation decoding with a different number of permutations used.

IEEE Information Theory Workshop (ITW)Apr 11, 20210 citations

Linear block codes for error detection (Corresp.)

Tadao Kasami, Torleiv Kløve, Shu Lin

The probability of undetected error of linear block codes for use on a binary symmetric channel is investigated. Upper hounds are derived. Several classes of linear block codes are proved to have good error-detecting capability.

IEEE Transactions on Information TheoryJan 1, 198337 citations

Necessary conditions for good error detection

P.N. Perry

The problem of determining the error detection capabilities of linear codes where the channel is a binary symmetric channel is addressed. Necessary conditions are given on the number of codewords in an (n,k) linear code and its dual for the probability of an undetected error to be upper bounded by 2/sup -(n-k)/.>

IEEE Transactions on Information TheoryMar 1, 199117 citations

Some Necessary Conditions for Codes to Be Good for Error Detection

Irina Naydenova, Torleiv Kløve

Codes for error detection on aq-ary symmetric channel are studied. Whether a code is good or not for error detection (in the technical sense) depends on the structure of the code. For some combinations of the main parameters length, size, and minimum distance, all code are good and for some other combinations all are ugly (stronger than not good). The purpose of this paper is to give bounds on the parameters for codes that are not good for error detection. In particular, it is shown that if the minimum distance is below some bound, which depends on the length and size of the code as well as a lower bound on the number of codewords of minimum distance, then the code is ugly and, hence, not good for error detection.

IEEE Transactions on Information TheoryMar 1, 20100 citations

Error Exponents for Recursive Decoding of Reed–Muller Codes on a Binary-Symmetric Channel

M. V. Burnashev, Ilya I. Dumer

Error exponents are studied for recursive decoding of Reed-Muller (RM) codes and their subcodes used on a binary-symmetric channel. The decoding process is first decomposed into similar steps, with one new information bit derived in each step. Multiple recursive additions and multiplications of the randomly corrupted channel outputs plusmn1 are performed using a specific order of these two operations in each step. Recalculated random outputs are compared in terms of their exponential moments. As a result, tight analytical bounds are obtained for decoding error probability of the two recursive algorithms considered in the paper. For both algorithms, the derived error exponents almost coincide with simulation results. Comparison of these bounds with similar bounds for bounded distance decoding and majority decoding shows that recursive decoding can reduce the output error probability of the latter two algorithms by five or more orders of magnitude even on the short block length of 256. It is also proven that the error probability of recursive decoding can be exponentially reduced by eliminating one or a few information bits from the original RM code

IEEE Transactions on Information TheoryOct 30, 200613 citations

Decoding of Reed-Muller codes with polylogarithmic complexity

Ilya I. Dumer

Code transmission is considered over a binary symmetric (BS) channel whose bit error probability is arbitrarily close to 1/2. New recursive decoding algorithms are designed for Reed-Muller (RM) codes of growing length 2m and fixed order r. The algorithms retrieve all information with a vanishing error probability and polylogarithmic complexity of order mr+1.

Jan 5, 20042 citations