Content deleted Content added
→Description using low-degree polynomials: Being more precise |
No edit summary |
||
Line 28:
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. Note that there are exactly <math display="inline"> k=\sum_{i=0}^r \binom{m}{i}</math> coefficients. With this in mind, an input message consists of <math display="inline"> k </math> values <math display="inline"> x\in\{0,1\}^k </math> which are 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 points <math display="inline"> Z=(Z_1,\ldots,
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 342:
|
|
|Z
|{{math|1=RM(''m,m'')}}<br />({{math|1=2<sup>''m''</sup>}}, {{math|1=2<sup>''m''</sup>}}, 1)
|universe codes
| |||