Reed–Muller code: Difference between revisions

Revision as of 17:12, 1 October 2021

Revision as of 16:06, 17 October 2021

Line 19:

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> 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 developeddiscovered 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|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}}</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|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|hdl=10338.dmlcz/143797|hdl-access=free}}</ref>

==Description using low-degree polynomials==