Reed–Muller code: Difference between revisions

Revision as of 14:46, 31 August 2018

Latest revision as of 03:04, 11 August 2025

(48 intermediate revisions by 27 users not shown)

Line 1:

{{Short description|Error-correcting codes used in wireless communication}}

{{confusing|date=March 2011}}

{{infobox code

| name = Reed-Muller code RM(r,m)

Line 15 ⟶ 14:

}}

'''Reed–Muller codes''' are [[error-correcting code]]s that are used in wireless communications applications, particularly in deep-space communication.<ref>{{Citation|last=Massey|first=James L.|titledate=Deep1992|pages=1–17|publisher=Springer-space communications and coding: A marriage made in heavenVerlag|datelanguage=1992en|urldoi=https://link.springer.com/chapter/10.1007/BFb0036046bfb0036046|workisbn=978-3540558514|title=Advanced Methods for Satellite and Deep Space Communications|pagesvolume=1–17182|publisherseries=Springer-VerlagLecture Notes in Control and Information Sciences|languagechapter=enDeep-space communications and coding: A marriage made in heaven|doiciteseerx=10.1007/bfb0036046|isbn=3540558519|access-date=2018-08-311.1.36.4265}}[[https://www.isiweb.ee.ethz.ch/archive/massey_pub/pdf/BI321.pdf pdf]]</ref>. Moreover, the proposed [[5G|5G standard]]<ref>{{cite web|url=http://www.3gpp.org/ftp/tsg_ran/WG1_RL1/TSGR1_87/Report/Final_Minutes_report_RAN1%2387_v100.zip|title=3GPP RAN1 meeting #87 final report|publisher=3GPP|accessdate=31 August 2017}}</ref> relies on the closely related [[Polar code (coding theory)|polar codes]]<ref>{{Cite web|url=https://ieeexplore.ieee.org/abstract/document/5075875/journal|title=Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels - IEEE Journals & Magazine|websitejournal=ieeexplore.ieee.orgIEEE Transactions on Information Theory|volume=55|issue=7|pages=3051–3073|language=en-US|access-datedoi=2018-08-3110.1109/TIT.2009.2021379|year=2009|last1=Arikan|first1=Erdal|hdl=11693/11695|arxiv=0807.3917|s2cid=889822 }}</ref> for itserror channelcorrection codingin needsthe control channel. Due to their favorable theoretical and mathematical properties, Reed–Muller codes have also been extensively studied in [[theoretical computer science]].

Reed–Muller codes generalize the [[Reed–Solomon error correction|Reed–Solomon codes]] and the [[Hadamard code|Walsh–Hadamard code]]. Reed–Muller codes are [[Linear code|linear block codes]] that are [[locally testable code|locally testable]], [[locally decodable code|locally decodable]], and [[List decoding|list decodable]]. These properties make them particularly useful in the design of [[probabilistically checkable proof]]s.

Traditional Reed–Muller codes are binary codes, which means that messages and codewords are binary strings. When ''r'' and ''m'' are integers with 0 ≤ ''r'' ≤ ''m'', the Reed–Muller code with parameters ''r'' and ''m'' is denoted as RM(''r'',&nbsp;''m''). When asked to encode a message consisting of ''k'' bits, where <math>\textstyle k=\sum_{i=0}^r \binom{m}{i}</math>to produce a holds, the RM(''r'',&nbsp;''m'') code produces a codeword consisting of 2^''m'' bits.

Reed–Muller codes are named after [[David E. Muller]], who discovered the codes in 1954,<ref>{{Cite journal|last=Muller|first=David E.|date=1954|title=Application of Boolean algebra to switching circuit design and to error detection|url=https://ieeexplore.ieee.org/document/6499441/?reload=true|journal=Transactions of the I.R.E. Professional Group on Electronic Computers|language=en-US|volume=EC-3|issue=3|pages=6–12|doi=10.1109/irepgelc.1954.6499441|issn=2168-1740|via=}}</ref>, and [[Irving S. Reed]], who proposed the first efficient decoding algorithm.<ref>{{Cite journal|last=Reed|first=Irving S.|date=1954|title=A class of multiple-error-correcting codes and the decoding scheme|url=https://ieeexplore.ieee.org/document/1057465/?reload=true|journal=Transactions of the IRE Professional Group on Information Theory|language=en-US|volume=4|issue=4|pages=38–49|doi=10.1109/tit.1954.1057465|issn=2168-2690|viahdl=10338.dmlcz/143797|hdl-access=free}}</ref>.

==Description using low-degree polynomials==

==Construction==

Reed–Muller codes can be described in several different (but ultimately equivalent) ways. The description that is based on low-degree polynomials is quite elegant and particularly suited for their application as [[locally testable code]]s and [[locally decodable code]]s.<ref>Prahladh Harsha et al., [[arxiv:1002.3864|Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)]], Section 5.2.1.</ref>

=== Encoder using multivariate polynomials ===

A [[block code]] can have one or more encoding functions <math display="inline"> C:\{0,1\}^k\to\{0,1\}^{n} </math> that map messages <math display="inline"> x\in\{0,1\}^k </math> to codewords <math display="inline"> C(x)\in\{0,1\}^{n} </math>. The Reed&ndash;Muller code {{nowrap|RM(''r'', ''m'')}} has [[Block code#The message length k|message length]] <math>\textstyle k=\sum_{i=0}^r \binom{m}{i}</math> and [[Block code#The block length n|block length]] <math>\textstyle n=2^m</math>. One way to define an encoding for this code is based on the evaluation of polynomials[[multilinear polynomial]]s with ''m'' variables and [[total degree]] at most ''r''. Every suchmultilinear polynomial over the [[finite field]] with two elements can be written as follows:

<math display="block">p_c(Z_1,\dots,Z_m) = \sum_{\underset{|S|\le r}{S\subseteq\{1,\dots,m\}}} c_S\cdot \prod_{i\in S} Z_i\,.</math>

The <math display="inline"> Z_1,\dots,Z_m </math> are the variables of the polynomial, and the values <math display="inline"> c_S\in\{0,1\} </math> are the coefficients of the polynomial. SinceNote that there are exactly <math display="inline"> k=\sum_{i=0}^r \binom{m}{i}</math> coefficients. With this in mind, thean input message consists of <math display="inline"> k </math> values <math display="inline"> x\in\{0,1\}^k </math> canwhich beare used as these coefficients. In this way, each message <math display="inline"> x </math> gives rise to a unique polynomial <math display="inline"> p_x </math> in ''m'' variables. To construct the codeword <math display="inline"> C(x) </math>, the encoder evaluates the polynomial <math display="inline"> p_x </math> at all evaluation points <math display="inline"> aZ=(Z_1,\ldots,Z_m)\in\{0,1\}^m </math>, where it interprets the sumpolynomial asis additiontaken modulowith twomultiplication inand orderaddition tomod obtain a bit2 <math display="inline">(p_x(aZ)\bmod 2) \in \{0,1\}</math>. That is, the encoding function is defined via<math display="block">C(x) = \left(p_x(aZ)\bmod 2\right)_{aZ\in\{0,1\}^m}\,.</math>

The fact that the codeword <math>C(x)</math> suffices to uniquely reconstruct <math>x</math> follows from [[Lagrange polynomial|Lagrange interpolation]], which states that the coefficients of a polynomial are uniquely determined when sufficiently many evaluation points are given. Since <math>C(0)=0</math> and <math>C(x+y)=C(x)+C(y) \bmod 2</math> holds for all messages <math>x,y\in\{0,1\}^k</math>, the function <math>C</math> is a [[linear map]]. Thus the Reed&ndash;Muller code is a [[linear code]].

==== Example ====

=== Construction using a generator matrix ===

AFor generator matrix for a Reed&ndash;Mullerthe code {{nowrap|RM(''r2'', ''m4'')}}, ofthe lengthparameters {{nowrap|1=''N'' = 2^''m''}} can be constructedare as follows. Let us write the set of all ''m''-dimensional binary vectors as:

<math display="inline"> \begin{align}

r&=2\\

m&=4\\

k&=\textstyle\binom{4}{2}+\binom{4}{1}+\binom{4}{0}= 6+4+1=11\\

n&=2^m=16\\

\end{align} </math>

Let <math display="inline"> C:\{0,1\}^{11}\to\{0,1\}^{16} </math> be the encoding function just defined. To encode the string x = 1 1010 010101 of length 11, the encoder first constructs the polynomial <math display="inline"> p_x </math> in 4 variables:<math display="block">\begin{align}

p_x(Z_1,Z_2,Z_3,Z_4)

&= 1

+ (1\cdot Z_1 + 0\cdot Z_2 + 1\cdot Z_3 + 0\cdot Z_4)

+ (0\cdot Z_1 Z_2 + 1\cdot Z_1Z_3 + 0\cdot Z_1Z_4 + 1\cdot Z_2Z_3 + 0\cdot Z_2Z_4+ 1\cdot Z_3Z_4)\\

&=1+Z_1+Z_3+Z_1Z_3+Z_2Z_3+Z_3Z_4

\end{align}</math>Then it evaluates this polynomial at all 16 evaluation points (0101 means <math>Z_1=0, Z_2=1, Z_3=0, Z_4=1)</math>:

<math display="block">

p_x(0000)= 1,\;

p_x(0001)= 1,\;

p_x(0010)= 0,\;

p_x(0011)= 1,\;</math>

<math display="block">

p_x(0100)= 1,\;

p_x(0101)= 1,\;

p_x(0110)= 1,\;

p_x(0111)= 0,\;</math>

<math display="block">

p_x(1000)= 0,\;

p_x(1001)= 0,\;

p_x(1010)= 0,\;

p_x(1011)= 1,\;</math>

<math display="block">

p_x(1100)= 0,\;

p_x(1101)= 0,\;

p_x(1110)= 1,\;

p_x(1111)= 0\,.</math>As a result, C(1 1010 010101) = 1101 1110 0001 0010 holds.

=== Decoder ===

As was already mentioned, Lagrange interpolation can be used to efficiently retrieve the message from a codeword. However, a decoder needs to work even if the codeword has been corrupted in a few positions, that is, when the received word is different from any codeword. In this case, a local decoding procedure can help.

The algorithm from Reed is based on the following property:

you start from the code word, that is a sequence of evaluation points from an unknown polynomial <math display="inline"> p_x </math> of <math display="inline"> {\mathbb F}_2[X_1,X_2,...,X_m] </math> of degree at most <math display="inline"> r </math> that you want to find. The sequence may contains any number of errors up to <math display="inline"> 2^{m-r-1}-1 </math> included.

If you consider a monomial <math display="inline"> \mu </math> of the highest degree <math display="inline"> d </math> in <math display="inline"> p_x </math> and sum all the evaluation points of the polynomial where all variables in <math display="inline"> \mu </math> have the values 0 or 1, and all the other variables have value 0, you get the value of the coefficient (0 or 1) of <math display="inline"> \mu </math> in <math display="inline"> p_x </math> (There are <math display="inline"> 2^d </math> such points). This is due to the fact that all lower monomial divisors of <math display="inline"> \mu </math> appears an even number of time in the sum, and only <math display="inline"> \mu </math> appears once.

To take into account the possibility of errors, you can also remark that you can fix the value of other variables to any value. So instead of doing the sum only once for other variables not in <math display="inline"> \mu </math> with 0 value, you do it <math display="inline"> 2^{m-d} </math> times for each fixed valuations of the other variables. If there is no error, all those sums should be equals to the value of the coefficient searched.

The algorithm consists here to take the majority of the answers as the value searched. If the minority is larger than the maximum number of errors possible, the decoding step fails knowing there are too many errors in the input code.

Once a coefficient is computed, if it's 1, update the code to remove the monomial <math display="inline"> \mu </math> from the input code and continue to next monomial, in reverse order of their degree.

==== Example ====

Let's consider the previous example and start from the code. With <math display="inline"> r=2, m=4 </math> we can fix at most 1 error in the code.

Consider the input code as 1101 1110 0001 0110 (this is the previous code with one error).

We know the degree of the polynomial <math display="inline"> p_x </math> is at most <math display="inline"> r=2 </math>, we start by searching for monomial of degree 2.

* <math display="inline"> \mu=X_3X_4 </math>

** we start by looking for evaluation points with <math display="inline"> X_1=0, X_2=0, X_3\in\{0,1\}, X_4\in\{0,1\}</math>. In the code this is: <u>1101</u> 1110 0001 0110. The first sum is 1 (odd number of 1).

** we look for evaluation points with <math display="inline"> X_1=0, X_2=1, X_3\in\{0,1\}, X_4\in\{0,1\}</math>. In the code this is: 1101 <u>1110 </u>0001 0110. The second sum is 1.

** we look for evaluation points with <math display="inline"> X_1=1, X_2=0, X_3\in\{0,1\}, X_4\in\{0,1\}</math>. In the code this is: 1101 1110 <u>0001</u> 0110. The third sum is 1.

** we look for evaluation points with <math display="inline"> X_1=1, X_2=1, X_3\in\{0,1\}, X_4\in\{0,1\}</math>. In the code this is: 1101 1110 0001 <u>0110</u>. The third sum is 0 (even number of 1).

The four sums don't agree (so we know there is an error), but the minority report is not larger than the maximum number of error allowed (1), so we take the majority and the coefficient of <math display="inline"> \mu </math> is 1.

We remove <math display="inline"> \mu </math> from the code before continue : code : 1101 1110 0001 0110, valuation of <math display="inline"> \mu </math> is 0001000100010001, the new code is 1100 1111 0000 0111

* <math display="inline"> \mu=X_2X_4 </math>

** <u>11</u>00 <u>11</u>11 0000 0111. Sum is 0

** 11<u>00</u> 11<u>11</u> 0000 0111. Sum is 0

** 1100 1111 <u>00</u>00 <u>01</u>11. Sum is 1

** 1100 1111 00<u>00</u> 01<u>11</u>. Sum is 0

One error detected, coefficient is 0, no change to current code.

* <math display="inline"> \mu=X_1X_4 </math>

** <u>11</u>00 1111 <u>00</u>00 0111. Sum is 0

** 11<u>00</u> 1111 00<u>00</u> 0111. Sum is 0

** 1100 <u>11</u>11 0000 <u>01</u>11. Sum is 1

** 1100 11<u>11</u> 0000 01<u>11</u>. Sum is 0

One error detected, coefficient is 0, no change to current code.

* <math display="inline"> \mu=X_2X_3 </math>

** <u>1</u>1<u>0</u>0 <u>1</u>1<u>1</u>1 0000 0111. Sum is 1

** 1<u>1</u>0<u>0</u> 1<u>1</u>1<u>1</u> 0000 0111. Sum is 1

** 1100 1111 <u>0</u>0<u>0</u>0 <u>0</u>1<u>1</u>1. Sum is 1

** 1100 1111 0<u>0</u>0<u>0</u> 0<u>1</u>1<u>1</u>. Sum is 0

One error detected, coefficient is 1, valuation of <math display="inline"> \mu </math> is 0000 0011 0000 0011, current code is now 1100 1100 0000 0100.

* <math display="inline"> \mu=X_1X_3 </math>

** <u>1</u>1<u>0</u>0 1100 <u>0</u>0<u>0</u>0 0100. Sum is 1

** 1<u>1</u>0<u>0</u> 1100 0<u>0</u>0<u>0</u> 0100. Sum is 1

** 1100 <u>1</u>1<u>0</u>0 0000 <u>0</u>1<u>0</u>0. Sum is 1

** 1100 1<u>1</u>0<u>0</u> 0000 0<u>1</u>0<u>0</u>. Sum is 0

One error detected, coefficient is 1, valuation of <math display="inline"> \mu </math> is 0000 0000 0011 0011, current code is now 1100 1100 0011 0111.

* <math display="inline"> \mu=X_1X_2</math>

** <u>1</u>100 <u>1</u>100 <u>0</u>011 <u>0</u>111. Sum is 0

** 1<u>1</u>00 1<u>1</u>00 0<u>0</u>11 0<u>1</u>11. Sum is 1

** 11<u>0</u>0 11<u>0</u>0 00<u>1</u>1 01<u>1</u>1. Sum is 0

** 110<u>0</u> 110<u>0</u> 001<u>1</u> 011<u>1</u>. Sum is 0

One error detected, coefficient is 0, no change to current code.

We know now all coefficient of degree 2 for the polynomial, we can start mononials of degree 1. Notice that for each next degree, there are twice as much sums, and each sums is half smaller.

* <math display="inline"> \mu=X_4 </math>

** <u>11</u>00 1100 0011 0111. Sum is 0

** 11<u>00</u> 1100 0011 0111. Sum is 0

** 1100 <u>11</u>00 0011 0111. Sum is 0

** 1100 11<u>00</u> 0011 0111. Sum is 0

** 1100 1100 <u>00</u>11 0111. Sum is 0

** 1100 1100 00<u>11</u> 0111. Sum is 0

** 1100 1100 0011 <u>01</u>11. Sum is 1

** 1100 1100 0011 01<u>11</u>. Sum is 0

One error detected, coefficient is 0, no change to current code.

* <math display="inline"> \mu=X_3 </math>

** <u>1</u>1<u>0</u>0 1100 0011 0111. Sum is 1

** 1<u>1</u>0<u>0</u> 1100 0011 0111. Sum is 1

** 1100 <u>1</u>1<u>0</u>0 0011 0111. Sum is 1

** 1100 1<u>1</u>0<u>0</u> 0011 0111. Sum is 1

** 1100 1100 <u>0</u>0<u>1</u>1 0111. Sum is 1

** 1100 1100 0<u>0</u>1<u>1</u> 0111. Sum is 1

** 1100 1100 0011 <u>0</u>1<u>1</u>1. Sum is 1

** 1100 1100 0011 0<u>1</u>1<u>1</u>. Sum is 0

One error detected, coefficient is 1, valuation of <math display="inline"> \mu </math> is 0011 0011 0011 0011, current code is now 1111 1111 0000 0100.

Then we'll find 0 for <math display="inline"> \mu=X_2 </math>, 1 for <math display="inline"> \mu=X_1 </math> and the current code become 1111 1111 1111 1011.

For the degree 0, we have 16 sums of only 1 bit. The minority is still of size 1, and we found <math display="inline"> p_x=1+X_1+X_3+X_1X_3+X_2X_3+X_3X_4</math> and the corresponding initial word 1 1010 010101

=== Generalization to larger alphabets via low-degree polynomials ===

Using low-degree polynomials over a finite field <math>\mathbb F</math> of size <math>q</math>, it is possible to extend the definition of Reed&ndash;Muller codes to alphabets of size <math>q</math>. Let <math>m</math> and <math>d</math> be positive integers, where <math>m</math> should be thought of as larger than <math>d</math>. To encode a message <math display="inline">x\in\mathbb F^k</math> of width <math>k=\textstyle\binom{m+d}{m}</math>, the message is again interpreted as an <math>m</math>-variate polynomial <math>p_x</math> of total degree at most <math>d</math> and with coefficient from <math>\mathbb F</math>. Such a polynomial indeed has <math>\textstyle\binom{m+d}{m}</math> coefficients. The Reed–Muller encoding of <math>x</math> is the list of all evaluations of <math>p_x(a)</math> over all <math>a\in\mathbb F^m</math>. Thus the block length is <math>n=q^m</math>.

== Description using a generator matrix ==

{{Confusing section|date=March 2011|reason=this section uses dense notation that is not explained well for most readers}}

A [[generator matrix]] for a Reed&ndash;Muller code {{nowrap|RM(''r'', ''m'')}} of length {{nowrap|1=''N'' = 2^''m''}} can be constructed as follows. Let us write the set of all ''m''-dimensional binary vectors as:

:<math> X = \mathbb{F}_2^m = \{ x_1, \ldots, x_{N} \}. </math>

Line 63 ⟶ 195:

:<math>H_i = \{ y \in ( \mathbb{F}_2 ) ^m \mid y_i = 0 \} .</math>

====Building aThe generator matrix= ===

The '''Reed&ndash;Muller {{nowrap|RM(''r'', ''m'')}} code''' of order ''r'' and length ''N''&nbsp;=&nbsp;2^''m'' is the code generated by ''v''₀ and the wedge products of up to ''r'' of the ''v''_''i'', {{nowrap|1 ≤ ''i'' ≤ ''m''}} (where by convention a wedge product of fewer than one vector is the identity for the operation). In other words, we can build a generator matrix for the {{nowrap|RM(''r'', ''m'')}} code, using vectors and their wedge product permutations up to ''r'' at a time <math>{v_0, v_1, \ldots, v_n, \ldots, (v_{i_1} \wedge v_{i_2}), \ldots (v_{i_1} \wedge v_{i_2} \ldots \wedge v_{i_r})}</math>, as the rows of the generator matrix, where {{nowrap|1 ≤ ''i''_''k'' ≤ ''m''}}.

=== Example 1 ===

Let ''m'' = 3. Then ''N'' = 8, and

:<math> X = \mathbb{F}_2^3 = \{ (0,0,0), (0,0,1), (0,1,0) \ldots, (1,1,1) \}, </math>

and

Line 98 ⟶ 230:

</math>

=== Example 2 ===

The RM(2,3) code is generated by the set:

Line 117 ⟶ 249:

</math>

===Properties===

The following properties hold:

Line 126 ⟶ 258:

# {{math|1=RM&thinsp;(''r'', ''m'')}} has minimum [[Hamming weight]] 2^{''m'' &minus; ''r''}.

====Proof====

{{Ordered list

|

Line 167 ⟶ 299:

::<math>\min \{ 2 \times 2^{m-1-r}, 2^{m-r} \} = 2^{m-r} .</math>

}}

===Further Properties of Specific Reed-Muller Codes===

* {{math|1=RM(0,&nbsp;''m'')}} codes are repetition codes of length {{math|1=''N''&nbsp;=&nbsp;2^''m''}}, [[code rate|rate]] <math>{R=\tfrac{1}{N}}</math> and minimum distance <math>d_\min = N</math>.

=== Decoding RM codes ===

* {{math|1=RM(1,&nbsp;''m'')}} codes are parity check codes of length {{math|1=''N''&nbsp;=&nbsp;2^''m''}}, rate <math>R=\tfrac{m+1}{N}</math> and minimum distance <math>d_\min = \tfrac{N}{2}</math>.

RM(''r'', ''m'') codes can be decoded using [[majority logic decoding]]. The basic idea of majority logic decoding is

to build several checksums for each received code word element. Since each of the different checksums must all

have the same value (i.e. the value of the message word element weight), we can use a majority logic decoding to decipher

the value of the message word element. Once each order of the polynomial is decoded, the received word is modified

accordingly by removing the corresponding codewords weighted by the decoded message contributions, up to the present stage.

So for a ''r''th order RM code, we have to decode iteratively r+1, times before we arrive at the final

received code-word. Also, the values of the message bits are calculated through this scheme; finally we can calculate

the codeword by multiplying the message word (just decoded) with the generator matrix.

One clue if the decoding succeeded, is to have an all-zero modified received word, at the end of (''r''&nbsp;+&nbsp;1)-stage decoding

* {{math|1=RM(''m''&nbsp;&minus;&nbsp;1,&nbsp;''m'')}} codes are single parity check codes of length {{math|1=''N''&nbsp;=&nbsp;2^''m''}}, rate <math>R=\tfrac{N-1}{N}</math> and minimum distance <math>d_\min = 2</math>.

through the majority logic decoding. This technique was proposed by Irving S. Reed, and is more general when applied

to other finite geometry codes.

==Description using a recursive construction==

* {{math|1=RM(''m''&nbsp;&minus;&nbsp;2,&nbsp;''m'')}} codes are the family of extended Hamming codes of length {{math|1=''N''&nbsp;=&nbsp;2^''m''}} with minimum distance <math>d_\min = 4</math>.<ref>Trellis and Turbo Coding, C. Schlegel & L. Perez, Wiley Interscience, 2004, p149.</ref>

==Alternative construction==

A Reed–Muller code RM(''r,m'') exists for any integers <math>m \ge 0</math> and <math>0 \le r \le m</math>. RM(''m'', ''m'') is defined as the universe (<math>2^m,2^m,1</math>) code. RM(&minus;1,m) is defined as the trivial code (<math>2^m,0,\infty</math>). The remaining RM codes may be constructed from these elementary codes using the length-doubling construction

: <math>\mathrm{RM}(r,m) = \{(\mathbf{u},\mathbf{u}+\mathbf{v})\mid\mathbf{u} \in \mathrm{RM}(r,m-1),\mathbf{v} \in \mathrm{RM}(r-1,m-1)\}.</math>

From this construction, RM(''r,m'') is a binary [[linear block code]] (''n'', ''k'', ''d'') with length {{math|1=''n''&nbsp;=&nbsp;2^''m''}}, dimension <math>k(r,m)=k(r,m-1)+k(r-1,m-1)</math> and minimum distance <math>d = 2^{m-r}</math> for <math>r \ge 0</math>. The [[dual code]] to RM(''r,m'') is RM(''m''-''r''-1,''m''). This shows that repetition and SPC codes are duals, biorthogonal and extended Hamming codes are duals and that codes with {{math|1=''k''&nbsp;=&nbsp;''n''/2}} are self-dual.

==Special cases of Reed&ndash;Muller codes==

==Construction based on low-degree polynomials over a finite field==

=== Table of all RM(r,m) codes for m≤5 ===

There is another, simple way to construct Reed–Muller codes based on low-degree polynomials over a finite field. This construction is particularly suited for their application as [[locally testable code]]s and [[locally decodable code]]s.<ref>Prahladh Harsha et al., [https://arxiv.org/abs/1002.3864 Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)], Section 5.2.1.</ref>

All {{math|1=RM(''r'',&nbsp;''m'')}} codes with <math>0\le m\le 5</math> and alphabet size 2 are displayed here, annotated with the standard [n,k,d] [[Block code#Popular notation|coding theory notation]] for [[block code]]s. The code {{math|1=RM(''r'',&nbsp;''m'')}} is a <math>\textstyle [2^m,k,2^{m-r}]_2</math>-code, that is, it is a [[linear code]] over a [[binary set|binary alphabet]], has [[Block code#The block length n|block length]] <math>\textstyle 2^m</math>, [[Block code#The message length k|message length]] (or dimension) {{mvar|k}}, and [[Block code#The distance d|minimum distance]] <math>\textstyle 2^{m-r}</math>.

Let <math>\mathbb F</math> be a finite field and let <math>m</math> and <math>d</math> be positive integers, where <math>m</math> should be thought of as larger than <math>d</math>. We are going to encode messages consisting of <math>\textstyle\binom{m+d}{m}</math> elements of <math>\mathbb F</math> as codewords of length <math>|\mathbb F|^m</math> as follows: We interpret the message as an <math>m</math>-variate polynomial <math>f</math> of degree at most <math>d</math> with coefficient from <math>\mathbb F</math>. Such a polynomial has <math>\textstyle\binom{m+d}{m}</math> coefficients. The Reed–Muller encoding of <math>f</math> is the list of the evaluations of <math>f</math> on all <math>x\in\mathbb F^m</math>; the codeword at the position indexed by <math>x\in\mathbb F^m</math> has value <math>f(x)</math>.

==Table of Reed&ndash;Muller codes==

The table below lists the {{math|1=RM(''r'',&nbsp;''m'')}} codes of lengths up to 32 for alphabet of size 2 annotated with standard [[Block code#Popular notation|coding theory notation]] for [[block code]]s

The Reed&ndash;Muller code is a <math>\textstyle [2^m,k,2^{m-r}]_2</math>-code, that is, it is a [[linear code]] over a [[binary set|binary alphabet]], has [[Block code#The block length n|block length]] <math>\textstyle 2^m</math>, [[Block code#The message length k|message length]] (or dimension) {{mvar|k}}, and [[Block code#The distance d|minimum distance]] <math>\textstyle 2^{m-r}</math>.

{|

|-0

|1

|2

|3

|4

|5

|m

|

|-

|

|

Line 202 ⟶ 342:

|

|

|Z

|{{math|1=RM(''m,m'')}}<br />(<math>2^m,2^m,1</math>)

|{{math|1=RM(''m,m'')}}<br />({{math|1=2^''m''}}, {{math|1=2^''m''}}, 1)

|universe codes

|-

Line 211 ⟶ 352:

|

|RM(5,5)<br />(32,32,1)

|

|

|-

|

Line 218 ⟶ 361:

|RM(4,4)<br />(16,16,1)

|

|{{math|1=RM(''m''&nbsp;&minus;&nbsp;1,&nbsp;''m'')}}<br />{{math|1=(2<mathsup>2^''m''</sup>, 2^<sup>''m-1,2''</mathsup>&minus;1, 2)}}

|[[parity bit|SPC]] codes

|-

Line 234 ⟶ 377:

|RM(3,4)<br />(16,15,2)

|

|{{math|1=RM(''m''&nbsp;&minus;&nbsp;2, ''m'')}}<br />{{math|1=(2<mathsup>2^''m''</sup>, 2^^''m-''&minus;''m-''&minus;1, 4</math>)}}

|ext.extended [[Hamming code]]s

|-

|

Line 256 ⟶ 399:

|

|RM(2,5)<br />(32,16,8)

|{{math|1=RM(''r'', ''m''=2''r''+1)}}<br />{{math|1=(2^2''r''+1, 2^2''r'', 2^''r''+1)}}

|

|[[self-dual code]]s

|-

Line 266 ⟶ 409:

|-

|

|RM(-1−1,1)<br />(2,0,<math>\infty</math>)

|

|RM(0,3)<br />(8,1,8)

Line 274 ⟶ 417:

|

|

|RM(-1−1,2)<br />(4,0,<math>\infty</math>)

|

|RM(0,4)<br />(16,1,16)

|

|{{math|1=RM(1,''m'')}}<br />{{math|1=(2<mathsup>2^''m''</sup>, ''m''+1, 2^{<sup>''m-''&minus;1}</mathsup>)}}

|Puncturedpunctured [[hadamardHadamard code]]s

|-

|

Line 294 ⟶ 437:

|RM(&minus;1,4)<br />(16,0,<math>\infty</math>)

|

|{{math|1=RM(0,''m'')}}<br />{{math|1=(2<mathsup>2^''m''</sup>, 1, 2^<sup>''m''</mathsup>)}}

|[[repetition code]]s

|-

Line 310 ⟶ 453:

|

|

|{{math|1=RM(-&minus;1,''m'')}}<br />{{math|1=(2<mathsup>2^''m,0,\infty''</mathsup>, 0, &infin;)}}

|trivial codes

|}

=== DecodingProperties of RM(r,m) codes for r≤1 or r≥m-1 ===

RM(''r'', ''m'') codes can be decoded using [[majority logic decoding]]. The basic idea of majority logic decoding is

to build several checksums for each received code word element. Since each of the different checksums must all

have the same value (i.e. the value of the message word element weight), we can use a majority logic decoding to decipher

the value of the message word element. Once each order of the polynomial is decoded, the received word is modified

accordingly by removing the corresponding codewords weighted by the decoded message contributions, up to the present stage.

So for a ''r''th order RM code, we have to decode iteratively r+1, times before we arrive at the final

received code-word. Also, the values of the message bits are calculated through this scheme; finally we can calculate

the codeword by multiplying the message word (just decoded) with the generator matrix.

One clue if the decoding succeeded, is to have an all-zero modified received word, at the end of (''r''&nbsp;+&nbsp;1)-stage decoding

through the majority logic decoding. This technique was proposed by Irving S. Reed, and is more general when applied

to other finite geometry codes.

*{{math|1=RM(0,&nbsp;''m'')}} codes are [[repetition code]]s of length {{math|1=''N''&nbsp;=&nbsp;2^''m''}}, [[code rate|rate]] <math>{R=\tfrac{1}{N}}</math> and minimum distance <math>d_\min = N</math>.

== See also ==

*{{math|1=RM(1,&nbsp;''m'')}} codes are [[Low-density parity-check code|parity check codes]] of length {{math|1=''N''&nbsp;=&nbsp;2^''m''}}, rate <math>R=\tfrac{m+1}{N}</math> and minimum distance <math>d_\min = \tfrac{N}{2}</math>.

*[[Reed–Muller expansion]]

*{{math|1=RM(''m''&nbsp;&minus;&nbsp;1,&nbsp;''m'')}} codes are [[Low-density parity-check code|single parity check codes]] of length {{math|1=''N''&nbsp;=&nbsp;2^''m''}}, rate <math>R=\tfrac{N-1}{N}</math> and minimum distance <math>d_\min = 2</math>.

*{{math|1=RM(''m''&nbsp;&minus;&nbsp;2,&nbsp;''m'')}} codes are the family of [[Hamming code|extended Hamming codes]] of length {{math|1=''N''&nbsp;=&nbsp;2^''m''}} with minimum distance <math>d_\min = 4</math>.<ref>Trellis and Turbo Coding, C. Schlegel & L. Perez, Wiley Interscience, 2004, p149.</ref>

== References ==

Line 336 ⟶ 469:

== Further reading ==

* {{cite book | author=Shu Lin |author2=Daniel Costello | title=Error Control Coding | edition=2 | year=2005 | publisher=Pearson | isbn=978-0-13-017973-69 }} Chapter 4.

* {{cite book | author=J.H. van Lint | title=Introduction to Coding Theory | edition=2 | publisher=[[Springer-Verlag]] | series=[[Graduate Texts in Mathematics|GTM]] | volume=86 | year=1992 | isbn=978-3-540-54894-72 | url-access=registration | url=https://archive.org/details/introductiontoco0000lint }} Chapter 4.5.

==External links==

* [http://ocw.mit.edu MIT OpenCourseWare], 6.451 Principles of Digital Communication II, Lecture Notes section 6.4

* [httphttps://octave.sourceforge.net/communications/function/reedmullergen.html GPL Matlab-implementation of RM-codes ]

* [httphttps://octave.svn.sourceforge.net/viewvc/octave/trunk/octave-forge/main/comm/inst/reedmullergen.m?revision=9852&view=markup Source GPL Matlab-implementation of RM-codes]

*{{cite journal |last1=Weiss |first1=E. |title=Generalized Reed-Muller codes |journal=Information and Control |date=September 1962 |volume=5 |issue=3 |pages=213–222 |doi=10.1016/s0019-9958(62)90555-7 |urlissn=https://doi.org/10.1016/S00190019-9958(62)90555|doi-7access= |issn=0019-9958}}

{{CCSDS}}