리드-뮬러 코드

리드-뮬러 코드 RM(r,m)
리드-뮬러 코드 RM(r,m)
이름을 따서 명명됨	어빙 S. 리드 앤 데이비드 E. 뮬러
분류
유형	선형블록코드
블록 길이
메시지 길이
등급
거리
알파벳 크기
표기법	- }}-code
	v; t;

리드-뮬러 코드는 무선 통신 애플리케이션, 특히 심우주 통신에 사용되는 오류 수정 코드다.^[1] 더욱이, 제안된 5G^[2] 표준은 제어 채널의 오류 보정을 위해 밀접하게 관련된 극성^[3] 코드에 의존한다. 리드-뮬러 코드는 그들의 유리한 이론적, 수학적 특성 때문에 이론 컴퓨터 과학에서도 광범위하게 연구되어 왔다.

리드-뮬러 코드는 리드-솔로몬 코드와 월시-하다마드 코드를 일반화한다. Reed-Muller 코드는 로컬 테스트가 가능하고 로컬에서 해독 가능하며 목록 해독이 가능한 선형 블록 코드다. 이러한 특성은 확률적으로 확인할 수 있는 증빙의 설계에 특히 유용하게 만든다.

전통적인 리드-뮬러 코드는 이진 코드인데, 이는 메시지와 코드워드가 이진 문자열이라는 것을 의미한다. r과 m이 0 ≤ r ≤ m의 정수인 경우, 매개변수 r과 m을 가진 리드-뮬러 코드는 RM(r, m)으로 표시된다. k $\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}$ 구성된 메시지를 인코딩하도록 요청하면 여기서 k $\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}$ = $\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}$ i $\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}$ = $\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}$ r $\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}$ ( m $\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}$ ) ${\$ 이 $\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}$ (가) 코드 워드를 2비트로^m 생성한다.

리드-뮬러 코드는 데이비드 E의 이름을 따서 명명되었다. 1954년에 암호를 발견한 뮬러와 ^[4]어빙 S. 최초의 효율적인 디코딩 알고리즘을 제안한 리드.^[5]

저차 다항식을 사용한 설명

리드-뮬러 코드는 여러 가지 다른 방법(그러나 궁극적으로 동등한 방법)으로 설명할 수 있다. 낮은 수준의 다항식들에 기초한 설명은 매우 우아하며 특히 지역적으로 시험 가능한 코드와 지역적으로 해독 가능한 코드로서 그들의 적용에 적합하다.^[6]

인코더

A block code can have one or more encoding functions ${\textstyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$ that map messages ${\textstyle x\in \{0,1\}^{k}}$ to codewords ${\textstyle C(x)\in \{0,1\}^{n}}$ . The Reed–Muller code RM(r, m) has message length $\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}$ and block length $\textstyle n=2^{m}$ . One way to define an encoding for this code is based on the evaluation of multilinear polynomials with m variables and 총 도 r. 두 개의 원소를 가진 유한한 장 위에 모든 다항식은 다음과 같이 쓸 수 있다.

p_{c}(Z_{1},\dots ,Z_{m})=\sum_{\des{S\s.r}{1,\dots,m\}}c_}cdot \prod _{i\in S},{i},}\},}\}}\sum_.

{\textstyle Z_{1},\dots ,Z_{m}}

{\textstyle Z_{1},\dots ,Z_{m}}

,

{\textstyle Z_{1},\dots ,Z_{m}}

… ,

{\textstyle Z_{1},\dots ,Z_{m}}

{\textstyle Z_{1},\dots ,Z_{m}}

{\

는 다항식의 변수고

{\textstyle Z_{1},\dots ,Z_{m}}

,

{\textstyle c_{S}\in \{0,1\}}

{\textstyle c_{S}\in \{0,1\}}

{

{\textstyle c_{S}\in \{0,1\}}

{\textstyle c_{S}\in \{0,1\}}

{\textstyle c_{S}\in \{0,1\}}

{\textstyle c_{S}\in{0,1\}

는 다항식의 계수다

{\textstyle c_{S}\in \{0,1\}}

. 정확히

{\textstyle k}

{\textstyle k}

계수가

{\textstyle k}

있기 때문에 메시지 x

{\textstyle x\in \{0,1\}^{k}}

{

{\textstyle x\in \{0,1\}^{k}}

{\textstyle x\in \{0,1\}^{k}}

{\

x

\in \{0,1\}^{k}}

는 이러한 계수로 사용할 수 있는

{\textstyle k}

{\textstyle k}

값으로

{\textstyle k}

구성된다

{\textstyle x\in \{0,1\}^{k}}

. 이렇게 각 메시지

{\textstyle x}

{\textstyle

x}은

(

는) m 변수에 고유한

{\textstyle p_{x}}

다항식 p

{\textstyle p_{x}}

{\

를 발생시킨다

{\textstyle x}

. To construct the codeword

{\textstyle C(x)}

, the encoder evaluates

{\textstyle p_{x}}

at all evaluation points

{\textstyle a\in \{0,1\}^{m}}

, where it interprets the sum as addition modulo two in order to obtain a bit

{\textstyle (p_{x}(a){\bm

od {2})\in \{0,1\}.

즉, 인코딩 함수는 다음을 통해 정의된다.

C(x)=\left(p_{x})(a){\bmod{2}}\오른쪽)_{a\in \{0,1\}^{m}}\,

코드워드 $C(x)$ ( $C(x)$ ) $C(x)$ 이(가) $x$ $x$ 을(를) 고유하게 재구성하기에 $C(x)$ 충분하다는 사실은 다항식의 계수가 충분히 많은 평가 지점이 주어졌을 때 고유하게 결정된다는 라그랑주 보간에서 비롯된다 $x$ . Since $C(0)=0$ and $C(x+y)=C(x)+C(y){\bmod {2}}$ holds for all messages $x,y\in \{0,1\}^{k}$ , the function $C$ is a linear map. 따라서 리드-뮬러 코드는 선형 코드다.

예

코드 RM(2, 4)의 경우 매개변수는 다음과 같다.

${\textstyle {\m&=2\m&=4\k&=\textstyle {\binom{4}{1}:{4}{1}:{0}}{0}}=6+4+1=11\n&=2^{m}=16\\end{liged}}}}}}}}}$

${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ : ${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ { ${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ ${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ ${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ ${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ → ${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ { 0 ${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ ${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ ${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ ${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ ${\$ \{ $0,1\}^{$ 16 $}}}$ 을(를) 방금 정의한 인코딩 함수가 되게 한다 ${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ . 문자열 x = 1 1010 010101의 길이 11을 인코딩하려면 인코더는 먼저 4개의 ${\textstyle p_{x}}$ 에 ${\textstyle p_{x}}$ p x {\ $textstyle$ p_ ${\textstyle p_{x}}$ { $x}$ 를 생성한다.

{\begin{aligned}p_{x}(Z_{1},Z_{2},Z_{3},Z_{4})&=1+(1\cdot Z_{1}+0\cdot Z_{2}+1\cdot Z_{3}+0\cdot Z_{4})+(0\cdot Z_{1}Z_{2}+1\cdot Z_{1}Z_{3}+0\cdot Z_{1}Z_{4}+1\cdot Z_{2}Z_{3}+0\cdot Z_{2}Z_{4}+1\cdot Z_{3}Z_{4})\\&=1+Z_{1}+Z_{3}+Z_{1}}Z_{3}+Z_{2}}Z_{3}+Z_{3}}}Z_{4}\end{aigned}}

그런 다음 16개의 모든 평가 지점에서 이 다항식을 평가한다.

p_{x}(0000)=1,\;p_{x}(0001)=1,\;p_{x}(0010)=1,\;p_{x}(0011)=1,\;p_{x}(0100)=1,\;p_{x}(0101)=0,\;p_{x}(0110)=1,\;p_{x}(0111)=0,\;p_{x}(1000)=0,\;p_{x}(1001)=1,\;p_{x}(1010)=0,\;p_{x}(1011)=1,\;p_{x}(1100)=0,\;p_{x}(1101)=0,\;p_{x}(1110)=0,\;p_{x}(1111)=0\,.

그 결과 C(1 1010 010101) = 1111 1010 0101 0000이 유지된다.

디코더

이미 언급했듯이, 라그랑주 보간법은 코드 워드에서 메시지를 효율적으로 검색하는 데 사용될 수 있다. 그러나암호문이몇 가지 위치, 즉 수신된 단어가 어떤 암호어와 다를 때라도 해독기가 작동해야 한다. 이 경우 국부적인 디코딩 절차가 도움이 될 수 있다.

낮은 수준의 다항식을 통한 큰 알파벳에 대한 일반화

크기 $q$ {\ $displaystyle$ q $}$ 의 $\mathbb F$ 유한 $\mathbb {F}$ F {\ $displaystyle \mathb$ { $F}$ 에 저급 다항식을 사용하면 크기 $q$ {\displaysty $q$ }의 알파벳까지 $Reed-Muller$ 코드의 정의를 확장할 수 있다 $q$ $m$ 서 $m$ ${\displaystystylem$ $m}$ 과 $m$ $d}$ 을 양의 정수로 한다 $d$ . $le$ $m}$ 은(는) d ${\displaystyle$ $d$ $}$ 보다 큰 것으로 간주해야 $m$ 한다 $d$ 메시지 ${\textstyle x\in \mathbb {F} ^{k}}$ ${\textstyle x\in \mathbb {F} ^{k}}$ ${\textstyle x\in \mathbb {F} ^{k}}$ k ${\$ x $\in \mathb {F}^{k}}}$ 의 ${\textstyle x\in \mathbb {F} ^{k}}$ 너비 $k=\textstyle {\binom {m+d}{m}}$ = ( $k=\textstyle {\binom {m+d}{m}}$ + d $k=\textstyle {\binom {m+d}{m}}$ ) ${\$ k $=\binom {m+d}{$ m}{ $m$ }}}을 인코딩하려면 $k=\textstyle {\binom {m+d}{m}}$ 메시지는 다시 최대 $d$ $d$ 에서 전체 $d$ 도수의 $p_{x}$ $m$ ${\displaystyle$ $p_{x}$ x ${\$ 로 해석되며 $\mathbb {F}$ ${\$ \ $mattb$ ${F}}}$ 의 계수가 있다 $\mathbb {F}$ 이러한 다항식은 실제로 $\textstyle {\binom {m+d}{m}}$ ( $\textstyle {\binom {m+d}{m}}$ + $) {\binom$ {\ $d$ )가 있다. $}{m}}}$ 개의 $\textstyle {\binom {m+d}{m}}$ 계수. $x$ $x$ 의 Reed-Muller 인코딩은 $a\in \mathbb {F} ^{m}$ $a\in \mathbb {F} ^{m}$ $a\in \mathbb {F} ^{m}$ $a\in \mathbb {F} ^{m}$ ${\$ 에 대한 $p_{x}(a)$ $p_{x}(a)$ $p_{x}(a)$ ( $p_{x}(a)$ ) ${\displaystyle p_{x}(a)$ 의 모든 평가 목록이다 $x$ $a\in \mathbb {F} ^{m}$ 따라서 블록 길이는 $n=q^{m}$ = $n=q^{m}$ m ${\$ 이다 $n=q^{m}$

제너레이터 매트릭스를 사용한 설명

길이 N = 2의^m 리드-뮬러 코드 RM(r, m)에 대한 제너레이터 매트릭스는 다음과 같이 구성할 수 있다. 모든 m-차원 이항 벡터 세트를 다음과 같이 쓰자.

X=\mathb {F} _{2}^{m}=\{x_{1},\ldots ,x_{N}\}

N차원 공간 $\mathbb {F} _{2}^{N}$ $\mathbb {F} _{2}^{N}$ ${\$ { $F} _{2}^{N}$ 에서 지시 $\mathbb {F} _{2}^{N}$ 벡터를 정의함

\mathb {I} _{A}\in \mathb {F} _{2}^{N}}

하위 $A\subset X$ 에서 다음 기준 $A\subset X$ { $A\subset X$ X {\ $displaystyle$ A\ $subset$ X $}:$

\left(\mathb {I} _{A}\오른쪽)_{i}={\begin{case}1&{\mbox{{}}\in A\0&{\mbox{다른 경우}\case}}}}}

함께, $\mathbb {F} _{2}^{N}$ F $\mathbb {F} _{2}^{N}$ ${\$ 에서 $\mathbb {F} _{2}^{N}$ 이진 연산

w\wedge z=(w_{1}\cdot z_{1},\ldots, w_{N}\cdot z_{N}),

쐐기 제품(외부 대수학에서 정의한 쐐기 제품과 혼동하지 않음). 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 ${\displaystyle \cdot$ $}}$ 은 $\cdot$ (는) $\mathbb {F} _{2}$ 2 $\mathbb {F} _{2}$ {\ $displaystyle \mathb {F} _{2$ } 필드의 일반적인 곱셈이다 $\mathbb {F} _{2}$

$\mathbb {F} _{2}^{m}$ $\mathbb {F} _{2}^{m}$ ${\$ 는 필드 $\mathbb {F} _{2}$ $\mathbb {F} _{2}$ ${\$ }}에 걸친 m차원 벡터 공간이기 때문에 $\mathbb {F} _{2}^{m}$ 쓰기가 가능하다 $\mathbb {F} _{2}$

${\displaystyle(\mathb {F} _{2})^{m}=\{{{{m},\ldots,y_{1}}\mid y_{i}\in \mathb {F}_{2}\}.}$

N-차원 공간 $\mathbb {F} _{2}^{N}$ $\mathbb {F} _{2}^{N}$ ${\$ 에서 $N:v_{0}=(1,1,\ldots ,1)$ N $N:v_{0}=(1,1,\ldots ,1)$ : $N:v_{0}=(1,1,\ldots ,1)$ $N:v_{0}=(1,1,\ldots ,1)$ = $N:v_{0}=(1,1,\ldots ,1)$ ( $N:v_{0}=(1,1,\ldots ,1)$ , $N:v_{0}=(1,1,\ldots ,1)$ , 1, $N:v_{0}=(1,1,\ldots ,1)$ … $N:v_{0}=(1,1,\ldots ,1)$ , $N:v_{0}=(1,1,\ldots ,1)$ ) ${\displaysty N:v_{0}=(1,1,\ldots ,$ 1)와 $N:v_{0}=(1,1,\ldots ,1)$ 길이 N-displaysty N:v_{N $}$ 를 정의한다.

v_{i}=\mathb {I} _{H_{i}},

여기서 1 ≤ i ≤ m과 H는_i $(\mathbb {F} _{2})^{m}$ ( $(\mathbb {F} _{2})^{m}$ 2) $(\mathbb {F} _{2})^{m}$ ${\$ m}}}( $(\mathbb {F} _{2})^{m}$ 차원 m - 1)의 하이퍼플레인이 된다.

H_{i}=\{y\in (\mathb {F} _{2})^{m}\mid y_{i}=0\}}

제너레이터 매트릭스

리드-뮬러 RM(r, m) 순서 r 및 길이 N = 2는^m v에₀ 의해 생성된 코드로서, v의_i 최대 r인 1 i i m m의 쐐기 제품이다(관습에 의해 1 벡터 이하의 쐐기 제품이 작동에 대한 ID가 된다). 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 ${\displaystyle {v_{0},v_{1},\ldots ,v_{n},\ldots ,(v_{i_{1}}\wedge v_{i_{$ ${{}})\ldots(v_{i_{1}}\remit v_{2}}\ldots \rem}}}}}}}$ 생성기 매트릭스의 행으로 ${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}})}$ 여기서 1 i_k i m m $.$

예 1

m = 3으로 하자. 그 다음 N = 8

X=\mathb {F} _{2}^{3}=\{(0,0,0,0), (0,0)\ldots ,(1,1,1)\}

그리고

{\begin{aligned}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{정렬}}

RM(1,3) 코드는 세트에 의해 생성된다.

\{v_{0},v_{1},v_{2},v_{3}\},\,

행렬의 행에 의해 더 명확하게 표시:

{\pmatrix}1&1&1&1&1&1&1&1&1&1&1&0&0&0&0&#1&0&0&#1&0&#1&1&0&#1&#1&0&#0&end{pmatrix}}}}}}}}}}}

예 2

RM(2,3) 코드는 다음 세트에 의해 생성된다.

{\displaystyle \{v_{0},v_{1},v_{2},v_{1},v_{1},v_{1},v_{1},v_{1},v_{2},v_{3}\message v_{3}\}}}}}}}.

행렬의 행에 의해 더 명확하게 표시:

{\displaystyle{\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}}}

특성.

다음 속성이 유지됨:

v의_i 최대 m까지 가능한 모든 쐐기 제품 세트는 $\mathbb {F} _{2}^{N}$ $\mathbb {F} _{2}^{N}$ $\mathbb {F} _{2}^{N}$ {\ $displaystyle \mathb {F} _{2}^{N}$ 의 기초를 형성한다 $\mathbb {F} _{2}^{N}$
RM(r, m) 코드의 순위는
$\sum _{s=0}^{r}{m \선택 s}.$
$RM(r,$ $m)$ = $RM(r,$ $m$ - 1 $) RM(r$ - 1 $, m$ - 1 $)$ 여기서 '는 두 개의 코드의 바 제품을 의미한다.
$RM(r,$ $m)$ 은 최소 해밍 중량 2를^{m − r} 가진다.

증명

있다
$\sum _{s=0}^{m}{m \선택 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 $\mathrm {RM} (m,m)=\mathbb {F} _{2}^{N}$ .
x를 길이 m의 이진 벡터, X의 원소가 되게 하라. (x)_i x의 i 요소를^th 나타냄. 정의

$y_{i}={\case}v_{i}&#{\text{{}}}}}}}{}(x)_{0}+v_{i}&#{}{}{}}}{}}}}{}}}}}}{}}}}}}}}}}:케이스{case{d}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

여기서 1 ≤ i ≤m.
그러면 $\mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}$ { $\mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}$ $\mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}$ = $\mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}$ $\mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}$ ∧ $\mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}$ $\mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}$ $\mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}$ m ${\$
Expansion via the distributivity of the wedge product gives $\mathbb {I} _{\{x\}}\in \mathrm {RM} (m,m)$ . Then since the vectors $\{\mathbb {I} _{\{x\}}\mid x\in X\}$ span $\mathbb {F} _{2}^{N}$ we have $\mathrm {RM} (m,n)=\mathbb {F} _{2}^{N}$ $\mathrm {RM} (m,n)=\mathbb {F} _{2}^{N}$ $\mathrm {RM} (m,n)=\mathbb {F} _{2}^{N}$ , $\mathrm {RM} (m,n)=\mathbb {F} _{2}^{N}$ ) $\mathrm {RM} (m,n)=\mathbb {F} _{2}^{N}$ = $\mathrm {RM} (m,n)=\mathbb {F} _{2}^{N}$ 2 $\mathrm {RM} (m,n)=\mathbb {F} _{2}^{N}$ ${\$
1에 의해, 그러한 모든 쐐기 제품은 선형적으로 독립적이어야 하므로, RM(r, m)의 순위는 단순히 그러한 벡터의 수여야 한다.
생략.
유도하여.
$RM(0,$ $m)$ 코드는 길이 $N =2$ 와^m 무게 N = 2 = 2의^m−0^m−r 반복 코드로, By 1 R $\mathrm {RM} (m,n)=\mathbb {F} _{2}^{n}$ , $\mathrm {RM} (m,n)=\mathbb {F} _{2}^{n}$ ) $\mathrm {RM} (m,n)=\mathbb {F} _{2}^{n}$ = F $\mathrm {RM} (m,n)=\mathbb {F} _{2}^{n}$ ${\$ 의 $\mathrm {RM} (m,n)=\mathbb {F} _{2}^{n}$ 가중치가 1 = 2이다⁰^m−r.
기사 바 제품(코딩 이론)은 2개의 코드₁ C , C의₂ 바 제품의 무게가 다음과 같이 주어진다는 증거를 제시한다.
$\min\{2w(C_{1}),w(C_{2})\}$
만약 0 < r < m이 되면, 그리고 만일 0 < r > m이 되면
1. $RM(r, m$ - 1)은 중량 $2$ 를^m−1−r 가진다.
2. $RM(r -$ 1, $m$ - 1)의 $중량은 m -1-(r -1) 2 m - r$ = 2
그러면 바 제품은 무게가 있다.
$\min\{2\put 2^{m-1-r},2^{m-r}\}=2^{m-r}.$

RM 코드 디코딩 중

RM(r, m) 코드는 다수 논리 디코딩을 사용하여 디코딩할 수 있다. 다수 논리 디코딩의 기본 아이디어는 각 수신된 코드 워드 요소에 대해 여러 개의 체크섬을 구축하는 것이다. 각각의 체크섬은 모두 동일한 값(즉, 메시지 워드 요소 무게의 값)을 가져야 하기 때문에, 우리는 메시지 워드 요소의 값을 해독하기 위해 다수의 로직을 디코딩할 수 있다. 다항식의 각 순서가 디코딩되면 디코딩된 메시지 기여도에 의해 가중된 해당 코드 워드를 현재 단계까지 제거하여 수신된 단어를 수정한다. 그래서 RM코드는 최종 수신된 코드 워드에 도착하기 전에 반복적으로 r+1을 해독해야 한다. 또한 메시지 비트의 값은 이 방법을 통해 계산된다. 마지막으로 메시지 워드(디코딩만)에 제너레이터 매트릭스를 곱하여 코드 워드를 계산할 수 있다.

디코딩이 성공했다면 한 가지 단서는 (r + 1)단계 디코딩의 끝에서 다수 논리 디코딩을 통해 수신된 단어를 0으로 수정하는 것이다. 이 기술은 어빙 S에 의해 제안되었다. 리드, 그리고 다른 유한 형상 코드에 적용할 때 더 일반적이다.

재귀적 구조를 사용한 설명

A Reed–Muller code RM(r,m) exists for any integers $m\geq 0$ and $0\leq r\leq m$ . RM(m, m) is defined as the universe ( $2^{m},2^{m},1$ ) code. RM(-1,m)은 사소한 코드( $2^{m},0,\infty$ $2^{m},0,\infty$ $2^{m},0,\infty$ ${\displaystyle 2^{m,0,\inful })$ 로 정의된다. 나머지 RM 코드는 길이 더빙 공법을 사용하여 이 기본 코드로 작성할 수 있다.

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

From this construction, RM(r,m) is a binary linear block code (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\geq 0$ . RM(r,m)에 대한 이중 코드는 RM(m-r-1,m)이다. 이는 반복과 SPC 코드가 듀얼이고, 바이오르토곤과 확장 해밍 코드가 듀얼이며, $k$ = $n /2$ 가 있는 코드가 자체 이중임을 보여준다.