Reed–Muller code: Difference between revisions

Revision as of 17:03, 5 September 2023

Revision as of 23:52, 6 September 2023

Line 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.|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 (coincidence not by design) [[Polar code (coding theory)|polar codes]]<ref>{{Cite journal|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|doi=10.1109/TIT.2009.2021379|year=2009|last1=Arikan|first1=Erdal|hdl=11693/11695|arxiv=0807.3917|s2cid=889822 }}</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.