Reed–Muller code: Difference between revisions

Revision as of 22:10, 7 August 2019

Revision as of 13:30, 6 December 2019

Line 13:

}}

'''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.|date=1992|pages=1–17|publisher=Springer-Verlag|language=en|doi=10.1007/bfb0036046|isbn=978-3540558514|title=Advanced Methods for Satellite and Deep Space Communications|volume=182|series=Lecture Notes in Control and Information Sciences|chapter=Deep-space communications and coding: A marriage made in heaven|citeseerx=10.1.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 journal|url=https://ieeexplore.ieee.org/abstract/document/5075875/|title=Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels - IEEE Journals & Magazine|journal=IEEE Transactions on Information Theory|volume=55|issue=7|pages=3051–3073|language=en-US|access-date=2018-08-31|doi=10.1109/TIT.2009.2021379|year=2009|last1=Arikan|first1=Erdal|hdl=11693/11695|arxiv=0807.3917}}</ref> for error correction in the 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.

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 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}}</ref>.

==Description using low-degree polynomials==