リード・ミュラー符号
無線通信で使用される誤り訂正符号
リード・ミュラー符号 RM(r,m)
名前の由来アーヴィング・S・リードとデイビッド・E・ミュラー
分類
タイプ線形ブロックコード
ブロック長 2 メートル {\displaystyle 2^{m}}
メッセージの長さ け ＝ ∑ 私 ＝ 0 r （ メートル 私 ） {\displaystyle k=\sum _{i=0}^{r}{\binom {m}{i}}}
レート け / 2 メートル {\displaystyle k/2^{m}}
距離 2 メートル − r {\displaystyle 2^{mr}}
アルファベットのサイズ 2 {\displaystyle 2}
表記 [ 2 メートル 、 け 、 2 メートル − r ] 2 {\displaystyle [2^{m},k,2^{mr}]_{2}} -コード

リード・ミュラー符号は、無線通信アプリケーション、特に深宇宙通信において用いられる誤り訂正符号である。 [1]さらに、提案されている5G規格[2]では、制御チャネルの誤り訂正に密接に関連する極性符号[3]が用いられている。リード・ミュラー符号は、その優れた理論的および数学的特性から、理論計算機科学においても広く研究されてきた。例えば、対称的な無記憶通信路において、漸近的にシャノン容量を達成することが示されている。[4] [5] [6] [7]

リード・マラー符号は、リード・ソロモン符号とウォルシュ・アダマール符号を一般化したものです。リード・マラー符号は、局所的に検証可能、局所的に復号可能、リスト的に復号可能な線形ブロック符号です。これらの特性により、確率的に検証可能な証明の設計において特に有用です。

従来のリード・ミュラー符号はバイナリ符号であり、メッセージとコードワードはバイナリ文字列です。rとmが0 ≤ r ≤ mの整数である場合、パラメータrとmを持つリード・ミュラー符号 は RM( r ,  m )と表記されます。kビット からなるメッセージ（ただし r , m ）を符号化する場合、 RM( r ,  m ) 符号は 2 mビットからなるコードワードを生成します。 け ＝ ∑ 私 ＝ 0 r （ メートル 私 ） {\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}

リード・ミュラー符号は、1954年にこの符号を発見したデイビッド・E・ミュラー氏[8]と、最初の効率的な復号アルゴリズムを提案したアーヴィング・S・リード氏[9]にちなんで名付けられました。

低次多項式を用いた記述

リード・ミュラー符号は、いくつかの異なる（しかし最終的には等価な）方法で記述することができる。低次多項式に基づく記述は非常に簡潔であり、局所的に検査可能な符号や局所的に復号可能な符号としての応用に特に適している。[10]

エンコーダ

ブロック符号は、メッセージを符号語 にマッピングする1 つ以上の符号化関数を持つことができます。リード・ミュラー符号RM( r , m )は、メッセージ長とブロック長を持ちます。この符号の符号化を定義する 1 つの方法は、m個の変数を持ち、総次数が最大rである多重線形多項式の評価に基づきます。2 つの要素を持つ有限体上のすべての多重線形多項式は、次のように記述できます。 は多項式の変数であり、値は多項式の係数です。係数はちょうど 個あることに注意してください。これを念頭に置いて、入力メッセージはこれらの係数として使用される値で構成されます。このようにして、各メッセージはm個の変数を持つ一意の多項式を生成します。符号語 を構築するために、エンコーダはすべての点で多項式を評価します。ここで、多項式は 2 を法として乗算と加算が行われます。つまり、符号化関数は次のように定義されます。 C : { 0 、 1 } け → { 0 、 1 } n {\textstyle C:\{0,1\}^{k}\to \{0,1\}^{n}} × ∈ { 0 、 1 } け {\textstyle x\in \{0,1\}^{k}} C （ × ） ∈ { 0 、 1 } n {\textstyle C(x)\in \{0,1\}^{n}} け ＝ ∑ 私 ＝ 0 r （ メートル 私 ） {\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}} n ＝ 2 メートル {\displaystyle \textstyle n=2^{m}} p c ( Z 1 , … , Z m ) = ∑ S ⊆ { 1 , … , m } | S | ≤ r c S ⋅ ∏ i ∈ S Z i . {\displaystyle p_{c}(Z_{1},\dots ,Z_{m})=\sum _{\underset {|S|\leq r}{S\subseteq \{1,\dots ,m\}}}c_{S}\cdot \prod _{i\in S}Z_{i}\,.} Z 1 , … , Z m {\textstyle Z_{1},\dots ,Z_{m}} c S ∈ { 0 , 1 } {\textstyle c_{S}\in \{0,1\}} k = ∑ i = 0 r ( m i ) {\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}} k {\textstyle k} x ∈ { 0 , 1 } k {\textstyle x\in \{0,1\}^{k}} x {\textstyle x} p x {\textstyle p_{x}} C ( x ) {\textstyle C(x)} p x {\textstyle p_{x}} Z = ( Z 1 , … , Z m ) ∈ { 0 , 1 } m {\textstyle Z=(Z_{1},\ldots ,Z_{m})\in \{0,1\}^{m}} ( p x ( Z ) mod 2 ) ∈ { 0 , 1 } {\textstyle (p_{x}(Z){\bmod {2}})\in \{0,1\}} C ( x ) = ( p x ( Z ) mod 2 ) Z ∈ { 0 , 1 } m . {\displaystyle C(x)=\left(p_{x}(Z){\bmod {2}}\right)_{Z\in \{0,1\}^{m}}\,.}

符号語が一意に再構成するのに十分であるという事実は、ラグランジュ補間から導かれる。ラグランジュ補間とは、十分な数の評価点が与えられた場合、多項式の係数は一意に決定されるというものである。すべてのメッセージに対しておよびが成立するため、関数 は線形写像となる。したがって、リード・ミュラー符号は線形符号である。 C ( x ) {\displaystyle C(x)} x {\displaystyle x} C ( 0 ) = 0 {\displaystyle C(0)=0} C ( x + y ) = C ( x ) + C ( y ) mod 2 {\displaystyle C(x+y)=C(x)+C(y){\bmod {2}}} x , y ∈ { 0 , 1 } k {\displaystyle x,y\in \{0,1\}^{k}} C {\displaystyle C}

例

コードRM( 2,4 )の場合、パラメータは次のとおり です。

r = 2 m = 4 k = ( 4 2 ) + ( 4 1 ) + ( 4 0 ) = 6 + 4 + 1 = 11 n = 2 m = 16 {\textstyle {\begin{aligned}r&=2\\m&=4\\k&=\textstyle {\binom {4}{2}}+{\binom {4}{1}}+{\binom {4}{0}}=6+4+1=11\\n&=2^{m}=16\\\end{aligned}}}

を先ほど定義した符号化関数とする。長さ11の文字列 x = 1 1010 010101 を符号化するために、符号化器はまず4変数の多項式を構築する。次に、この多項式を16個の評価点すべてで評価する（0101は以下を意味する： C : { 0 , 1 } 11 → { 0 , 1 } 16 {\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}} p x {\textstyle p_{x}} p x ( Z 1 , Z 2 , Z 3 , Z 4 ) = 1 + ( 1 ⋅ Z 1 + 0 ⋅ Z 2 + 1 ⋅ Z 3 + 0 ⋅ Z 4 ) + ( 0 ⋅ Z 1 Z 2 + 1 ⋅ Z 1 Z 3 + 0 ⋅ Z 1 Z 4 + 1 ⋅ Z 2 Z 3 + 0 ⋅ Z 2 Z 4 + 1 ⋅ Z 3 Z 4 ) = 1 + Z 1 + Z 3 + Z 1 Z 3 + Z 2 Z 3 + Z 3 Z 4 {\displaystyle {\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{aligned}}} Z 1 = 0 , Z 2 = 1 , Z 3 = 0 , Z 4 = 1 ) {\displaystyle Z_{1}=0,Z_{2}=1,Z_{3}=0,Z_{4}=1)} p x ( 0000 ) = 1 , p x ( 0001 ) = 1 , p x ( 0010 ) = 0 , p x ( 0011 ) = 1 , {\displaystyle p_{x}(0000)=1,\;p_{x}(0001)=1,\;p_{x}(0010)=0,\;p_{x}(0011)=1,\;}

p x ( 0100 ) = 1 , p x ( 0101 ) = 1 , p x ( 0110 ) = 1 , p x ( 0111 ) = 0 , {\displaystyle p_{x}(0100)=1,\;p_{x}(0101)=1,\;p_{x}(0110)=1,\;p_{x}(0111)=0,\;}

p x ( 1000 ) = 0 , p x ( 1001 ) = 0 , p x ( 1010 ) = 0 , p x ( 1011 ) = 1 , {\displaystyle p_{x}(1000)=0,\;p_{x}(1001)=0,\;p_{x}(1010)=0,\;p_{x}(1011)=1,\;}

p x ( 1100 ) = 0 , p x ( 1101 ) = 0 , p x ( 1110 ) = 1 , p x ( 1111 ) = 0 . {\displaystyle p_{x}(1100)=0,\;p_{x}(1101)=0,\;p_{x}(1110)=1,\;p_{x}(1111)=0\,.} その結果、C(1 1010 010101) = 1101 1110 0001 0010が成立します。

デコーダ

既に述べたように、ラグランジュ補間はコードワードからメッセージを効率的に取得するために使用できます。ただし、デコーダはコードワードの一部が破損している場合でも、つまり受信ワードがどのコードワードとも異なる場合でも動作する必要があります。このような場合、ローカルデコード手順が役立ちます。

リードのアルゴリズムは、以下の特性に基づいています。まず、コードワード、つまり、最大次数の未知の多項式から得られる評価点の列から始めます。この列には、最大で任意の数のエラーが含まれる場合があります。 p x {\textstyle p_{x}} F 2 [ X 1 , X 2 , . . . , X m ] {\textstyle {\mathbb {F} }_{2}[X_{1},X_{2},...,X_{m}]} r {\textstyle r} 2 m − r − 1 − 1 {\textstyle 2^{m-r-1}-1}

における最高次数の単項式を考え、その多項式の評価点（変数の値が0または1で、かつ他の変数の値が0である点）をすべて合計すると、 における係数の値（0または1）が得られます（そのような点があります）。これは、 の単項式における下側の約数が和の中で偶数回出現し、かつ一度しか出現しないという事実によるものです。 μ {\textstyle \mu } d {\textstyle d} p x {\textstyle p_{x}} μ {\textstyle \mu } μ {\textstyle \mu } p x {\textstyle p_{x}} 2 d {\textstyle 2^{d}} μ {\textstyle \mu } μ {\textstyle \mu }

エラーの可能性を考慮すると、他の変数の値は任意の値に固定できることにも留意してください。つまり、0以外の変数について合計を1回だけ行うのではなく、他の変数の各固定値について合計を複数回行うということです。エラーがない場合、これらの合計はすべて、検索対象の係数の値と等しくなるはずです。このアルゴリズムは、答えの過半数を検索対象の値として採用します。少数派が最大エラー数よりも大きい場合、入力コードにエラーが多すぎると判断され、デコード処理は失敗します。 μ {\textstyle \mu } 2 m − d {\textstyle 2^{m-d}}

係数が計算され、それが 1 の場合、コードを更新して入力コードから単項式を削除し、次数の逆順で次の単項式に進みます。 μ {\textstyle \mu }

例

前の例を考えて、コードから始めましょう。コード内のエラーは最大1つしか修正できません。入力コードが1101 1110 0001 0110（エラーが1つある前のコード）だとします。 r = 2 , m = 4 {\textstyle r=2,m=4}

多項式の次数は最大 であることがわかっているので、まず次数 2 の単項式を検索します。 p x {\textstyle p_{x}} r = 2 {\textstyle r=2}

  • μ = X 3 X 4 {\textstyle \mu =X_{3}X_{4}}
    • まず、 の評価ポイントを探します。コードでは、これは1101 1110 0001 0110 です。最初の合計は 1（1 の奇数）です。 X 1 = 0 , X 2 = 0 , X 3 ∈ { 0 , 1 } , X 4 ∈ { 0 , 1 } {\textstyle X_{1}=0,X_{2}=0,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}
    • で評価点を探します。コードでは、これは1101 1110 0001 0110です。2番目の合計は1です。 X 1 = 0 , X 2 = 1 , X 3 ∈ { 0 , 1 } , X 4 ∈ { 0 , 1 } {\textstyle X_{1}=0,X_{2}=1,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}
    • で評価点を探します。コードでは、これは1101 1110 0001 0110です。3番目の合計は1です。 X 1 = 1 , X 2 = 0 , X 3 ∈ { 0 , 1 } , X 4 ∈ { 0 , 1 } {\textstyle X_{1}=1,X_{2}=0,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}
    • で評価点を探します。コードでは、これは 1101 1110 0001 0110です。3番目の合計は0（1の偶数）です。 X 1 = 1 , X 2 = 1 , X 3 ∈ { 0 , 1 } , X 4 ∈ { 0 , 1 } {\textstyle X_{1}=1,X_{2}=1,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}

4 つの合計は一致しません (したがって、エラーがあることがわかります) が、少数意見は最大許容エラー数 (1) よりも大きくないため、多数派を採用し、係数は1 になります。 μ {\textstyle \mu }

続行する前にコードから削除します: コード: 1101 1110 0001 0110、評価は 0001000100010001、新しいコードは 1100 1111 0000 0111 です μ {\textstyle \mu } μ {\textstyle \mu }

  • μ = X 2 X 4 {\textstyle \mu =X_{2}X_{4}}
    • 11 00 11 11 0000 0111。合計は0です
    • 11 00 11 11 0000 0111。合計は0です
    • 1100 1111 00 00 01 11. 合計は1です
    • 1100 1111 00 00 01 11。合計は0です

1 つのエラーが検出されました。係数は 0 で、現在のコードには変更はありません。

  • μ = X 1 X 4 {\textstyle \mu =X_{1}X_{4}}
    • 11 00 1111 00 00 0111。合計は0です
    • 11 00 1111 00 00 0111。合計は0です
    • 1100 11 11 0000 01 11。合計は1です
    • 1100 11 11 0000 01 11。合計は0です

1 つのエラーが検出されました。係数は 0 で、現在のコードには変更はありません。

  • μ = X 2 X 3 {\textstyle \mu =X_{2}X_{3}}
    • 1 1 0 0 1 1 1 1 0000 0111。合計は1
    • 1 1 0 0 1 1 1 1 0000 0111。合計は1
    • 1100 1111 0 0 0 0 0 1 1 1. 合計は1です
    • 1100 1111 0 0 0 0 0 1 1 1。合計は0です

1 つのエラーが検出されました。係数は 1、評価は0000 0011 0000 0011、現在のコードは 1100 1100 0000 0100 です。 μ {\textstyle \mu }

  • μ = X 1 X 3 {\textstyle \mu =X_{1}X_{3}}
    • 1 1 0 0 1100 0 0 0 0 0100。合計は1
    • 1 1 0 0 1100 0 0 0 0 0100。合計は1です
    • 1100 1 1 0 0 0000 0 1 0 0。合計は1です
    • 1100 1 1 0 0 0000 0 1 0 0。合計は0です

1 つのエラーが検出されました。係数は 1、評価は0000 0000 0011 0011、現在のコードは 1100 1100 0011 0111 です。 μ {\textstyle \mu }

  • μ = X 1 X 2 {\textstyle \mu =X_{1}X_{2}}
    • 1 100 1 100 0 011 0 111。合計は0です
    • 1 1 00 1 1 00 0 0 11 0 1 11。合計は1です
    • 11 0 0 11 0 0 00 1 1 01 1 1。合計は0です
    • 110 0 110 0 001 1 011 1。合計は0です

エラーが1つ検出されました。係数は0です。現在のコードに変更はありません。これで多項式の2次係数がすべて判明したので、1次単項式から始めることができます。次数が進むにつれて、和の数は2倍になり、それぞれの和は半分ずつ小さくなることに注意してください。

  • μ = X 4 {\textstyle \mu =X_{4}}
    • 11 00 1100 0011 0111。合計は0です
    • 11 00 1100 0011 0111。合計は0です
    • 1100 11 00 0011 0111。合計は0です
    • 1100 11 00 0011 0111。合計は0です
    • 1100 1100 00 11 0111。合計は0です
    • 1100 1100 00 11 0111。合計は0です
    • 1100 1100 0011 01 11。合計は1です
    • 1100 1100 0011 01 11。合計は0です

1 つのエラーが検出されました。係数は 0 で、現在のコードには変更はありません。

  • μ = X 3 {\textstyle \mu =X_{3}}
    • 1 1 0 0 1100 0011 0111。合計は1
    • 1 1 0 0 1100 0011 0111。合計は1
    • 1100 1 1 0 0 0011 0111。合計は1です
    • 1100 1 1 0 0 0011 0111。合計は1です
    • 1100 1100 0 0 1 1 0111。合計は1です
    • 1100 1100 0 0 1 1 0111。合計は1です
    • 1100 1100 0011 0 1 1 1. 合計は1
    • 1100 1100 0011 0 1 1 1。合計は0です

1 つのエラーが検出されました。係数は 1、評価は0011 0011 0011 0011、現在のコードは 1111 1111 0000 0100 です。 μ {\textstyle \mu }

すると、 には 0 、 には 1 が見つかり、現在のコードは 1111 1111 1111 1011 になります。 μ = X 2 {\textstyle \mu =X_{2}} μ = X 1 {\textstyle \mu =X_{1}}

次数0の場合、1ビットの和が16個あります。少数派は依然としてサイズ1であり、対応する初期ワード1 1010 010101が 見つかりました。 p x = 1 + X 1 + X 3 + X 1 X 3 + X 2 X 3 + X 3 X 4 {\textstyle p_{x}=1+X_{1}+X_{3}+X_{1}X_{3}+X_{2}X_{3}+X_{3}X_{4}}

低次多項式によるより大きなアルファベットへの一般化

サイズ の有限体上の低次多項式を使用すると、リード・ミュラー符号の定義をサイズ のアルファベットに拡張できます。 およびを正の整数とし、 はより大きいと考えます。幅 のメッセージをエンコードするには、メッセージは再び、全次数が最大でから係数が与えられた-変数多項式として解釈されます。このような多項式には実際に係数があります。 のリード・ミュラー符号化は全体にわたるのすべての評価のリストです。したがって、ブロック長は です。 F {\displaystyle \mathbb {F} } q {\displaystyle q} q {\displaystyle q} m {\displaystyle m} d {\displaystyle d} m {\displaystyle m} d {\displaystyle d} x ∈ F k {\textstyle x\in \mathbb {F} ^{k}} k = ( m + d m ) {\displaystyle k=\textstyle {\binom {m+d}{m}}} m {\displaystyle m} p x {\displaystyle p_{x}} d {\displaystyle d} F {\displaystyle \mathbb {F} } ( m + d m ) {\displaystyle \textstyle {\binom {m+d}{m}}} x {\displaystyle x} p x ( a ) {\displaystyle p_{x}(a)} a ∈ F m {\displaystyle a\in \mathbb {F} ^{m}} n = q m {\displaystyle n=q^{m}}

生成行列を用いた説明

長さN = 2 mのリード・ミュラー符号RM( r , m )の生成行列は以下のように構成できる。すべてのm次元2値ベクトル の集合を次のように書く。

X = F 2 m = { x 1 , … , x N } . {\displaystyle X=\mathbb {F} _{2}^{m}=\{x_{1},\ldots ,x_{N}\}.}

N次元空間において、指示ベクトルを定義する。 F 2 N {\displaystyle \mathbb {F} _{2}^{N}}

I A ∈ F 2 N {\displaystyle \mathbb {I} _{A}\in \mathbb {F} _{2}^{N}}

サブセットごとに: A ⊂ X {\displaystyle A\subset X}

( I A ) i = { 1  if  x i ∈ A 0  otherwise {\displaystyle \left(\mathbb {I} _{A}\right)_{i}={\begin{cases}1&{\mbox{ if }}x_{i}\in A\\0&{\mbox{ otherwise}}\\\end{cases}}}

とともに、また、二項演算 F 2 N {\displaystyle \mathbb {F} _{2}^{N}}

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

ウェッジ積と呼ばれる（外積代数で定義されるウェッジ積と混同しないように注意）。ここで、およびは（N次元2値ベクトル）内の点であり、演算は体における通常の乗算​​である。 w = ( w 1 , w 2 , … , w N ) {\displaystyle w=(w_{1},w_{2},\ldots ,w_{N})} z = ( z 1 , z 2 , … , z N ) {\displaystyle z=(z_{1},z_{2},\ldots ,z_{N})} F 2 N {\displaystyle \mathbb {F} _{2}^{N}} ⋅ {\displaystyle \cdot } F 2 {\displaystyle \mathbb {F} _{2}}

F 2 m {\displaystyle \mathbb {F} _{2}^{m}} は体上のm次元ベクトル空間なので、 F 2 {\displaystyle \mathbb {F} _{2}}

( F 2 ) m = { ( y m , … , y 1 ) ∣ y i ∈ F 2 } . {\displaystyle (\mathbb {F} _{2})^{m}=\{(y_{m},\ldots ,y_{1})\mid y_{i}\in \mathbb {F} _{2}\}.}

N次元空間において、長さと F 2 N {\displaystyle \mathbb {F} _{2}^{N}} N : v 0 = ( 1 , 1 , … , 1 ) {\displaystyle N:v_{0}=(1,1,\ldots ,1)}

v i = I H i , {\displaystyle v_{i}=\mathbb {I} _{H_{i}},}

ここで 1 ≤ i ≤ mであり、H i は（次元m − 1） の超平面である。 ( F 2 ) m {\displaystyle (\mathbb {F} _{2})^{m}}

H i = { y ∈ ( F 2 ) m ∣ y i = 0 } . {\displaystyle H_{i}=\{y\in (\mathbb {F} _{2})^{m}\mid y_{i}=0\}.}

ジェネレータマトリックス

r次、長さN  = 2 mのリード・ミュラーRM( r , m )符号は、 v 0と、 v i , 1 ≤ i ≤ mのrまでのウェッジ積によって生成される符号です （慣例により、1つ未満のベクトルのウェッジ積は演算の恒等式です）。言い換えれば、生成行列の行として、一度にrまでのベクトルとそのウェッジ積の順列を用いて、 RM( r , m )符号の生成行列を構築することができます（1 ≤ i k ≤ m ）。 v 0 , v 1 , … , v n , … , ( v i 1 ∧ v i 2 ) , … ( v i 1 ∧ v i 2 … ∧ v i r ) {\displaystyle {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

m = 3とするとN = 8となり、

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

そして

v 0 = ( 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ) v 1 = ( 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 ) v 2 = ( 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 ) v 3 = ( 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 ) . {\displaystyle {\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{aligned}}}

RM(1,3)コードは、次の集合によって生成される。

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

あるいは、より明確には行列の行で表すと次のようになります。

( 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 ) {\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\end{pmatrix}}}

例2

RM(2,3)コードは次のセットによって生成されます。

{ v 0 , v 1 , v 2 , v 3 , v 1 ∧ v 2 , v 1 ∧ v 3 , v 2 ∧ v 3 } {\displaystyle \{v_{0},v_{1},v_{2},v_{3},v_{1}\wedge v_{2},v_{1}\wedge v_{3},v_{2}\wedge v_{3}\}}

あるいは、より明確には行列の行で表すと次のようになります。

( 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 ) {\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}}}

プロパティ

次の特性が当てはまります:

  1. v iのmまでのすべての可能なウェッジ積の集合は の基底を形成します。 F 2 N {\displaystyle \mathbb {F} _{2}^{N}}
  2. RM ( r , m ) コードのランクは
    ∑ s = 0 r ( m s ) . {\displaystyle \sum _{s=0}^{r}{m \choose s}.}
  3. RM ( r , m ) = RM ( r , m − 1) | RM ( r − 1, m − 1)ここで '|' は2 つのコードのバー積を表します。
  4. RM( r , m )の最小ハミング重みは2m − rである。

証拠

  1. がある
    ∑ s = 0 m ( m s ) = 2 m = N {\displaystyle \sum _{s=0}^{m}{m \choose s}=2^{m}=N}

    このようなベクトルと は次元Nを持つので、 Nベクトルが張ることを確認すれば十分です。同様に、 を確認すれば十分です。 F 2 N {\displaystyle \mathbb {F} _{2}^{N}} R M ( m , m ) = F 2 N {\displaystyle \mathrm {RM} (m,m)=\mathbb {F} _{2}^{N}}

    x を長さmの2進ベクトル（ Xの要素）とする。 ( x ) i をxのi番目の要素とする。定義

    y i = { v i  if  ( x ) i = 0 v 0 + v i  if  ( x ) i = 1 {\displaystyle y_{i}={\begin{cases}v_{i}&{\text{ if }}(x)_{i}=0\\v_{0}+v_{i}&{\text{ if }}(x)_{i}=1\\\end{cases}}}

    ここで 1 ≤ i ≤ mです。

    それから I { x } = y 1 ∧ ⋯ ∧ y m {\displaystyle \mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}}

    ウェッジ積の分配法則による展開は となる。そしてベクトルは張るのでとなる。 I { x } ∈ R M ( m , m ) {\displaystyle \mathbb {I} _{\{x\}}\in \mathrm {RM} (m,m)} { I { x } ∣ x ∈ X } {\displaystyle \{\mathbb {I} _{\{x\}}\mid x\in X\}} F 2 N {\displaystyle \mathbb {F} _{2}^{N}} R M ( m , n ) = F 2 N {\displaystyle \mathrm {RM} (m,n)=\mathbb {F} _{2}^{N}}
  2. 1により、このようなウェッジ積はすべて線形独立でなければならないため、RM( r, m )の階数は単にこのようなベクトルの数でなければなりません。
  3. 省略。
  4. 誘導により。
    RM (0,  m )符号は、長さN  =2 m、重みN = 2 m −0 = 2 m − rの繰り返し符号です。1で、 重みは1 = 2 0 = 2 m − rです。 R M ( m , n ) = F 2 n {\displaystyle \mathrm {RM} (m,n)=\mathbb {F} _{2}^{n}}
    バー積（符号理論） の記事では、2つの符号C 1、C 2のバー積の重みが次のように与えられる ことが証明されている。
    min { 2 w ( C 1 ) , w ( C 2 ) } {\displaystyle \min\{2w(C_{1}),w(C_{2})\}}
    0 < r < mかつ
    1. RM( r , m  − 1)の重みは2 m −1− rである。
    2. RM( r  − 1, m  − 1)の重みは2 m − 1−( r −1) = 2 m − rである。
    バー製品の重量は
    min { 2 × 2 m − 1 − r , 2 m − r } = 2 m − r . {\displaystyle \min\{2\times 2^{m-1-r},2^{m-r}\}=2^{m-r}.}

RMコードのデコード

RM( r , m ) コードは、多数決論理復号法を使用して復号化できます。多数決論理復号法の基本的な考え方は、受信したコードワード要素ごとに複数のチェックサムを作成することです。異なるチェックサムはそれぞれすべて同じ値 (つまり、メッセージワード要素の重みの値) を持つ必要があるため、多数決論理復号法を使用してメッセージワード要素の値を復号化できます。多項式の各次数が復号化されると、受信ワードは、現在の段階までの復号化メッセージの寄与によって重み付けされた対応するコードワードを削除することにより、それに応じて変更されます。したがって、r次の RM コードの場合、最終的な受信コードワードに到達するまでに、 r+1 回繰り返し復号化する必要があります。また、メッセージビットの値もこの方式を使用して計算され、最終的に (復号化された) メッセージワードを生成行列に乗算することでコードワードを計算できます。

復号が成功したかどうかの手がかりの一つは、多数決論理復号による( r + 1)段復号の最後に、受信語がすべてゼロになるかどうかである 。この手法はアーヴィング・S・リードによって提案され、他の有限幾何学符号にも適用できるほど汎用性が高い。

再帰構造を用いた記述

任意の整数とに対してリード・ミュラー符号RM( r,m )が存在する。RM ( m , m )はユニバース( )符号として定義される。RM(−1,m)は自明符号( )として定義される。残りのRM符号は、長さ倍増構成を用いてこれらの基本符号から構成することができる。 m ≥ 0 {\displaystyle m\geq 0} 0 ≤ r ≤ m {\displaystyle 0\leq r\leq m} 2 m , 2 m , 1 {\displaystyle 2^{m},2^{m},1} 2 m , 0 , ∞ {\displaystyle 2^{m},0,\infty }

R M ( r , m ) = { ( u , u + v ) ∣ u ∈ R M ( r , m − 1 ) , v ∈ R M ( r − 1 , m − 1 ) } . {\displaystyle \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)\}.}

この構成から、RM( r,m ) は長さn  = 2 m、次元、最小距離の2値線形ブロック符号( n , k , d ) であることがわかる。RM ( r,m ) の双対符号は RM( m - r -1, m ) である。これは、繰り返し符号とSPC符号が双対符号であり、双直交符号と拡張ハミング符号が双対符号であり、k  =  n /2の符号が自己双対符号であることを示す。 k ( r , m ) = k ( r , m − 1 ) + k ( r − 1 , m − 1 ) {\displaystyle k(r,m)=k(r,m-1)+k(r-1,m-1)} d = 2 m − r {\displaystyle d=2^{m-r}} r ≥ 0 {\displaystyle r\geq 0}

リード・ミュラー符号の特殊なケース

m≤5のすべてのRM(r,m)コードの表

アルファベットサイズが2であるすべてのRM( r ,  m )符号が、ブロック符号の 標準的な[n,k,d]符号化理論表記法で注釈付けされてここに表示されます。RM ( r ,  m )符号は-符号、つまり2進アルファベット上の線形符号であり、ブロック長は、メッセージ長（または次元）はk、最小距離はです。 0 ≤ m ≤ 5 {\displaystyle 0\leq m\leq 5} [ 2 m , k , 2 m − r ] 2 {\displaystyle \textstyle [2^{m},k,2^{m-r}]_{2}} 2 m {\displaystyle \textstyle 2^{m}} 2 m − r {\displaystyle \textstyle 2^{m-r}}

0 1 2 3 4 5 メートル
Z RM( m ,m )
( 2m , 2m , 1 ) 		宇宙コード
RM(5,5)
(32,32,1)
RM(4,4)
(16,16,1) 		RM( m  − 1,  m )
(2 m , 2 m −1, 2) 		SPCコード
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) 		拡張ハミング符号
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( r , m =2 r +1)
(2 2 r +1 , 2 2 r , 2 r +1 ) 		自己双対コード
RM(−1,0)
(1,0, ) ∞ {\displaystyle \infty } 		RM(0,2)
(4,1,4) 		RM(1,4)
(16,5,8)
RM(−1,1)
(2,0, ) ∞ {\displaystyle \infty } 		RM(0,3)
(8,1,8) 		RM(1,5)
(32,6,16)
RM(−1,2)
(4,0, ) ∞ {\displaystyle \infty } 		RM(0,4)
(16,1,16) 		RM(1, m )
(2 m , m +1, 2 m −1 ) 		パンクチャード・アダマール符号
RM(−1,3)
(8,0, ) ∞ {\displaystyle \infty } 		RM(0,5)
(32,1,32)
RM(−1,4)
(16,0, ) ∞ {\displaystyle \infty } 		RM(0, m )
(2 m , 1, 2 m ) 		繰り返しコード
RM(−1,5)
(32,0, ) ∞ {\displaystyle \infty }
RM(−1, m )
(2 m , 0, ∞) 		単純なコード

r≤1またはr≥m-1の場合のRM(r,m)コードの特性

  • RM(0,  m )コードは長さN  = 2 m、レート、最小距離の繰り返しコードです。 R = 1 N {\displaystyle {R={\tfrac {1}{N}}}} d min = N {\displaystyle d_{\min }=N}
  • RM(1,  m )コードは長さN  = 2 m、レート、最小距離のパリティチェックコードです。 R = m + 1 N {\displaystyle R={\tfrac {m+1}{N}}} d min = N 2 {\displaystyle d_{\min }={\tfrac {N}{2}}}
  • RM( m  −1,  m )コードは長さN  = 2m 、レート、最小距離の単一パリティチェックコードです。 R = N − 1 N {\displaystyle R={\tfrac {N-1}{N}}} d min = 2 {\displaystyle d_{\min }=2}
  • RM( m  −2,  m )符号は長さN  =2m 、最小距離の拡張ハミング符号の族である。[11] d min = 4 {\displaystyle d_{\min }=4}

参考文献

  1. ^ Massey, James L. (1992)、「深宇宙通信と符号化：天国のような結婚」、衛星および深宇宙通信の高度な方法、制御および情報科学の講義ノート、第182巻、Springer-Verlag、pp.  1-17、CiteSeerX  10.1.1.36.4265、doi :10.1007/bfb0036046、ISBN 978-3540558514pdf
  2. ^ 「3GPP RAN1会議#87最終報告書」。3GPP 。 2017年8月31日閲覧。
  3. ^ Arikan, Erdal (2009). 「チャネル分極：対称バイナリ入力メモリレスチャネルにおける容量達成符号の構築法 - IEEE Journals & Magazine」. IEEE Transactions on Information Theory . 55 (7): 3051– 3073. arXiv : 0807.3917 . doi :10.1109/TIT.2009.2021379. hdl :11693/11695. S2CID  889822.
  4. ^ Abbe, Emmanuel; Shpilka, Amir; Wigderson, Avi (2015-06-14).ランダム消去と誤りに対するリード・ミュラー符号. ACM. pp.  297– 306. doi :10.1145/2746539.2746575. ISBN 978-1-4503-3536-2. 2025年11月12日閲覧。
  5. ^ Kudekar, Shrinivas; Kumar, Santhosh; Mondelli, Marco; Pfister, Henry D.; Sasoglu, Eren; Urbanke, Ridiger L. (2017). 「リード・ミュラー符号は消失訂正チャネルで容量を実現する」. IEEE Transactions on Information Theory . 63 (7): 4298– 4316. doi :10.1109/TIT.2017.2673829. ISSN  0018-9448 . 2025年11月12日閲覧。
  6. ^ Reeves, Galen; Pfister, Henry D. (2024). 「BMSチャネルにおけるリード・ミュラー符号は、容量以下のすべてのレートでビット誤り確率ゼロを実現する」IEEE Transactions on Information Theory . 70 (2): 920– 949. doi : 10.1109/TIT.2023.3286452 . ISSN  0018-9448 . 2025年11月12日閲覧。
  7. ^ Abbe, Emmanuel; Sandon, Colin (2023-11-06). リード・ミュラー符号が対称通信路上でシャノン容量を達成することの証明. IEEE. pp.  177– 193. doi :10.1109/FOCS57990.2023.00020. ISBN 979-8-3503-1894-4. 2025年11月12日閲覧。
  8. ^ Muller, David E. (1954). 「ブール代数のスイッチング回路設計とエラー検出への応用」. Transactions of the IRE Professional Group on Electronic Computers . EC-3 (3): 6– 12. doi :10.1109/irepgelc.1954.6499441. ISSN  2168-1740.
  9. ^ Reed, Irving S. (1954). 「多重誤り訂正符号のクラスとその復号法」. IRE情報理論専門グループ論文集. 4 (4): 38– 49. doi :10.1109/tit.1954.1057465. hdl : 10338.dmlcz/143797 . ISSN  2168-2690.
  10. ^ Prahladh Harsha 他「近似アルゴリズムの限界: PCP とユニーク ゲーム (DIMACS チュートリアル講義ノート)」、セクション 5.2.1。
  11. ^ トレリスとターボ符号化、C. シュレーゲル & L. ペレス、Wiley Interscience、2004 年、p149。

さらに読む

  • MIT OpenCourseWare、6.451 デジタルコミュニケーションの原則 II、講義ノートセクション6.4
  • RMコードのGPL Matlab実装
  • ソース GPL Matlab 実装 RM コード
  • ワイス, E. (1962年9月). 「一般化リード・ミュラー符号」.情報制御. 5 (3): 213– 222. doi :10.1016/s0019-9958(62)90555-7. ISSN  0019-9958.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Reed–Muller_code&oldid=1332023738"