Content deleted Content added
No edit summary Tag: Reverted |
m →External links: HTTP to HTTPS for SourceForge |
||
| (6 intermediate revisions by 5 users not shown) | |||
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
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 26:
=== Encoder ===
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–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 [[multilinear polynomial]]s with ''m'' variables and [[total degree]] at most ''r''. Every multilinear 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.
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–Muller code is a [[linear code]].
Line 116:
* <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
Line 141:
** 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
** 1100 1100 0011 01<u>11</u>. Sum is
One error detected, coefficient is 0, no change to current code.
* <math display="inline"> \mu=X_3 </math>
Line 157:
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+
=== Generalization to larger alphabets via low-degree polynomials ===
Line 342:
|
|
|Z
|{{math|1=RM(''m,m'')}}<br />({{math|1=2<sup>''m''</sup>}}, {{math|1=2<sup>''m''</sup>}}, 1)
|universe codes
Line 474:
==External links==
* [http://ocw.mit.edu MIT OpenCourseWare], 6.451 Principles of Digital Communication II, Lecture Notes section 6.4
* [
* [
*{{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 |issn=0019-9958|doi-access= }}
| |||