Reed–Muller code

Reed–Muller codes are a family of used in communications. Reed–Muller codes belong to the classes of locally testable codes and locally decodable codes, which is why they are useful in the design of in . They are named after and . Muller discovered the codes, and Reed proposed the majority logic decoding for the first time. Special cases of Reed–Muller codes include the Walsh–Hadamard code and the Reed–Solomon code.

Reed–Muller codes are listed as RM(r, m), where r is the order of the code, 0 ≤ r ≤ m, and m determines the block length N = 2^m. RM codes are related to binary functions on the field GF(2^m) over the elements {0, 1}.

RM(0, m) codes are repetition codes of length N = 2^m, ${R=tfrac{1}{N}}$ and minimum distance $d_min = N$ .

RM(1, m) codes are parity check codes of length N = 2^m, rate $R=tfrac{m+1}{N}$ and minimum distance $d_min = tfrac{N}{2}$ .

RM(m − 1, m) codes are single parity check codes of length N = 2^m, rate $R=tfrac{N-1}{N}$ and minimum distance $d_min = 2$ .

RM(m − 2, m) codes are the family of extended Hamming codes of length N = 2^m with minimum distance $d_min = 4$ .

1 Construction
- 1.1 Building a generator matrix
2 Example 1
3 Example 2
4 Properties
- 4.1 Proof
5 Alternative construction
6 Construction based on low-degree polynomials over a finite field
7 Table of Reed–Muller codes
8 Decoding RM codes
9 Source
10 See Also on BitcoinWiki

Construction

A generator matrix for a Reed–Muller code RM(r,m) of length N = 2^m can be constructed as follows. Let us write the set of all m-dimensional binary vectors as:

X = mathbb{F}_2^m = { x_1, ldots, x_{N} }.

We define in N-dimensional space $mathbb{F}_2^N$ the

mathbb{I}_A in mathbb{F}_2^N

on subsets $A subset X$ by:

left( mathbb{I}_A right)_i = begin{cases} 1 & mbox{ if } x_i in A \ 0 & mbox{ otherwise} \ end{cases}

together with, also in $mathbb{F}_2^N$ , the binary operation

w wedge z = (w_1 cdot z_1, ldots , w_N cdot z_N ),

referred to as the wedge product (this wedge product is not to be confused with the defined in exterior algebra). Here, $w=(w_1,w_2,ldots,w_N)$ and $z=(z_1,z_2,ldots, z_N)$ are points in $mathbb{F}_2^N$ (N-dimensional binary vectors), and the operation $cdot$ is the usual multiplication in the field $mathbb{F}_2$ .

$mathbb{F}_2^m$ is an m-dimensional vector space over the field $mathbb{F}_2$ , so it is possible to write

$(mathbb{F}_2)^m = { (y_m, ldots , y_1) mid y_i in mathbb{F}_2 }$

We define in N-dimensional space $mathbb{F}_2^N$ the following vectors with length $N: v_0 = (1,1,ldots,1)$ and

v_i = mathbb{I}_{ H_i }

where 1 ≤ i ≤ m and the H_i are in $(mathbb{F}_2)^m$ (with dimension m −1):

H_i = { y in ( mathbb{F}_2 ) ^m mid y_i = 0 }

Building a generator matrix

The Reed–Muller RM(r, m) code of order r and length N = 2^m is the code generated by v₀ and the wedge products of up to r of the v_i, 1 ≤ i ≤ m (where by convention a wedge product of fewer than one vector is the identity for the operation). In other words, we can build a generator matrix for the RM(r,m) code, using vectors and their wedge product permutations up to r at a time ${v_0, v_1, ldots, v_n, ldots, (v_{i_1} wedge v_{i_2}), ldots (v_{i_1} wedge v_{i_2} ldots wedge v_{i_r})}$ , as the rows of the generator matrix, where 1 ≤ i_k ≤ m.

Example 1

Let m = 3. Then N = 8, and

X = mathbb{F}_2^3 = { (0,0,0), (0,0,1), ldots, (1,1,1) },

and

begin{align} v_0 & = (1,1,1,1,1,1,1,1) \[2pt] v_1 & = (1,0,1,0,1,0,1,0) \[2pt] v_2 & = (1,1,0,0,1,1,0,0) \[2pt] v_3 & = (1,1,1,1,0,0,0,0). end{align}

The RM(1,3) code is generated by the set

{ v_0, v_1, v_2, v_3 },,

or more explicitly by the rows of the matrix:

begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 end{pmatrix}

Example 2

The RM(2,3) code is generated by the set:

{ v_0, v_1, v_2, v_3, v_1 wedge v_2, v_1 wedge v_3, v_2 wedge v_3 }

or more explicitly by the rows of the matrix:

begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 end{pmatrix}

Properties

The following properties hold:

1 The set of all possible wedge products of up to m of the v_i form a basis for $mathbb{F}_2^N$ .

2 The RM (r, m) code has

sum_{s=0}^r {m choose s}.

3 RM (r, m) = RM (r, m − 1) | RM (r − 1, m − 1) where ‘|’ denotes the of two codes.

4 RM (r, m) has minimum 2^{m − r}.

Proof

There are

sum_{s=0}^m { m choose s } = 2^m = N

such vectors and

mathbb{F}_2^N

have dimension N so it is sufficient to check that the N vectors span; equivalently it is sufficient to check that RM(m, m) =

mathbb{F}_2^N

Let x be a binary vector of length m, an element of X. Let (x)_i denote the i^th element of x. Define

y_i = begin{cases} v_i & text{ if } (x)_i = 0 \ v_0+v_i & text{ if } (x)_i = 1 \ end{cases}

where 1 ≤ i ≤m.

Then

mathbb{I}_{ { x } } = y_1 wedge cdots wedge y_m

Expansion via the distributivity of the wedge product gives

mathbb{I}_{ { x } } in mbox{ RM(m,m)}

. Then since the vectors

{ mathbb{I}_{ { x } } mid x in X }

span

mathbb{F}_2^N

we have RM(m, m) =

mathbb{F}_2^N

By 1, all such wedge products must be linearly independent, so the rank of RM(r, m) must simply be the number of such vectors.

Omitted.

By induction.

The RM(0, m) code is the repetition code of length N =2^m and weight N = 2^m−0 = 2^m−r. By 1 RM(m, m) =

mathbb{F}_2^n

and has weight 1 = 2⁰ = 2^m−r.

The article gives a proof that the weight of the bar product of two codes C₁ , C₂ is given by

min { 2w(C_1), w(C_2) }

If 0 < r < m and if

i) RM(r ,m − 1) has weight 2^m−1−r

ii) RM(r-1,m-1) has weight 2^{m−1−(r−1)} = 2^m−r

then the bar product has weight

min { 2 times 2^{m-1-r}, 2^{m-r} } = 2^{m-r} .

Alternative construction

A Reed–Muller code RM(r,m) exists for any integers $m ge 0$ and $0 le r le m$ . RM(m, m) is defined as the universe ( $2^m,2^m,1$ ) code. RM(−1,m) is defined as the trivial code ( $2^m,0,infty$ ). The remaining RM codes may be constructed from these elementary codes using the length-doubling construction

RM(r,m) = {(mathbf{u},mathbf{u}+mathbf{v})midmathbf{u} in RM(r,m-1),mathbf{v} in RM(r-1,m-1)}.

From this construction, RM(r,m) is a binary (n, k, d) with length n = 2^m, dimension $k(r,m)=k(r,m-1)+k(r-1,m-1)$ and minimum distance $d = 2^{m-r}$ for $r ge 0$ . The to RM(r,m) is RM(m-r-1,m). This shows that repetition and SPC codes are duals, biorthogonal and extended Hamming codes are duals and that codes with k = n/2 are self-dual.

Construction based on low-degree polynomials over a finite field

There is another, simple way to construct Reed–Muller codes based on low-degree polynomials over a finite field. This construction is particularly suited for their application as locally testable codes and locally decodable codes.

Let $mathbb F$ be a finite field and let $m$ and $d$ be positive integers, where $m$ should be thought of as larger than $d$ . We are going to encode messages consisting of ${m+d choose m}$ elements of $mathbb F$ as codewords of length $|mathbb F|^m$ as follows: We interpret the message as an $m$ -variate polynomial $f$ of degree at most $d$ with coefficient from $mathbb F$ . Such a polynomial has ${m+d choose m}$ coefficients. The Reed–Muller encoding of $f$ is the list of the evaluations of $f$ on all $xinmathbb F^m$ ; the codeword at the position indexed by $xinmathbb F^m$ has value $f(x)$ .

Table of Reed–Muller codes

The table below lists the RM(r, m) codes of lengths up to 32 for alphabet of size 2 annotated with standard for The Reed–Muller code is a $[2^m,k,2^{m-r}]_2$ -code, that is, it is a over a , has $2^m$ , (or dimension) $k$ , and $2^{m-r}$ .

						RM(m,m) ( $2^m,2^m,1$ )	universe codes
					RM(5,5) (32,32,1)
				RM(4,4) (16,16,1)		RM(m − 1, m) ( $2^m,2^m-1,2$ )	SPC codes
			RM(3,3) (8,8,1)		RM(4,5) (32,31,2)
		RM(2,2) (4,4,1)		RM(3,4) (16,15,2)		RM(m − 2, m) ( $2^m,2^m-m-1,4$ )	ext. Hamming codes
	RM(1,1) (2,2,1)		RM(2,3) (8,7,2)		RM(3,5) (32,26,4)
RM(0,0) (1,1,1)		RM(1,2) (4,3,2)		RM(2,4) (16,11,4)
	RM(0,1) (2,1,2)		RM(1,3) (8,4,4)		RM(2,5) (32,16,8)
RM(−1,0) (1,0, $infty$ )		RM(0,2) (4,1,4)		RM(1,4) (16,5,8)
	RM(-1,1) (2,0, $infty$ )		RM(0,3) (8,1,8)		RM(1,5) (32,6,16)
		RM(-1,2) (4,0, $infty$ )		RM(0,4) (16,1,16)		RM(1,m) ( $2^m,m+1,2^{m-1}$ )	Punctured hadamard codes
			RM(−1,3) (8,0, $infty$ )		RM(0,5) (32,1,32)
				RM(−1,4) (16,0, $infty$ )		RM(0,m) ( $2^m, 1, 2^m$ )	repetition codes
					RM(−1,5) (32,0, $infty$ )
						RM(-1,m) ( $2^m,0,infty$ )	trivial codes

Decoding RM codes

RM(r, m) codes can be decoded using majority logic decoding. The basic idea of majority logic decoding is to build several checksums for each received code word element. Since each of the different checksums must all have the same value (i.e. the value of the message word element weight), we can use a majority logic decoding to decipher the value of the message word element. Once each order of the polynomial is decoded, the received word is modified accordingly by removing the corresponding codewords weighted by the decoded message contributions, up to the present stage. So for a rth order RM code, we have to decode iteratively r+1, times before we arrive at the final received code-word. Also, the values of the message bits are calculated through this scheme; finally we can calculate the codeword by multiplying the message word (just decoded) with the generator matrix.

One clue if the decoding succeeded, is to have an all-zero modified received word, at the end of (r + 1)-stage decoding through the majority logic decoding. This technique was proposed by Irving S. Reed, and is more general when applied to other finite geometry codes.

Source

http://wikipedia.org/