For integers and , the binary Reed-Muller code evaluates polynomials of total polynomial degree at most on all points of . Evaluation allows every polynomial to be replaced by a square-free one, using on the field with two elements. Its parameters areThe dimension counts the independent square-free monomials of polynomial degree at most . The minimum Hamming distance follows inductively from the decomposition , with and . A product of coordinate variables attains weight .
For boundary conventions, put when , and when . The displayed parameter formula is asserted for ; in particular is a repetition code.
If have minimum distances , respectively, thenIndeed, , while the words and attain the two candidate bounds.
If is a parity-check matrix of , then a parity-check matrix of isIts equations say that the first half lies in and that the sum of the two halves lies in .
For , the standard binary bilinear form givesIndeed, the product of representing polynomials has polynomial degree at most . Each square-free monomial in that product omits at least one of the variables and therefore takes the value an even number of times on . Summing the product over all evaluation points gives zero in the field with two elements, proving orthogonality. The dimensions of the two Reed-Muller codes add to , by the symmetry , so containment is equality.
At , the Reed-Muller code is the full vector space and its dual code is zero. The same displayed identity holds if denotes the zero code, as in the boundary convention for Reed-Muller codes.
Articles by others on the same topic
Reed–Muller codes are a family of error-correcting codes that are used in digital communication and data storage to detect and correct errors in transmitted or stored data. They are particularly known for their simple decoding algorithms and their good performance in terms of error correction capabilities.