リード・マラー符号

リード・マラー符号について

リード・マラー符号（Reed–Muller code）は、誤り訂正のために利用される線型符号の一種で、Irving S. ReedとD. E. Mullerによって発見されました。この符号は、情報の正確性を保つために通信分野で重要な役割を果たしています。

符号の定義

リード・マラー符号は、R(r, m)という形で表され、ここでrは符号の次数、mは符号語の長さnに関連しています。具体的には、nは2^mでうなるため、mの値によって符号語の長さが決まります。この符号は、バイナリ関数が定義される有限体GF(2^m)と関連しています。符号の中で、R(0, m)は反復符号、R(1, m)はアダマール符号、R(m - 1, m)はパリティチェック符号です。そのため、リード・マラー符号には直交性という特性があり、これはブール関数空間としても扱われることができます。

構成方法

リード・マラー符号は、長さn = 2^mのベクトル空間を使用して構成されます。まず、次のようにm次元の二項体を設定します:
\[
eta _{2}^{m} = \{x_1, x_2, \ldots, x_n\}
\]
次に、部分集合Aに対する指示ベクトルI_Aを定義し、Aに含まれる要素に1を、含まれない要素に0を割り当てます:
\[
(I_A)_j = \begin{cases} 1 & (x_j \in A) \\ 0 & (x_j
otin A) \end{cases}
\]

この指示ベクトルを用い、次に「楔積（wedge product）」を用いて二項ベクトルの演算も行います。これにより、リード・マラー符号はより柔軟に構成され、特定の条件を満たす符号ベクトルを生成することが可能となります。

具体例

例えば、m = 3の場合には、符号語の長さnは8となり、以下のような構成が可能です：
\[
F_2^3 = \{(0,0,0), (0,0,1), \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)
\]

ここで、符号R(1, 3)は、これらのベクトルから生成される符号集合となります。

特性と応用

リード・マラー符号の重要な特性の一つは、m番目までのv_iが生成する全ての楔積が、F_2^nの基底を形成することです。この特性により、符号は高い誤り訂正能力を持ち、多くの通信システムで実用化されています。また、リード・マラー符号はランクや最小距離など、数学的にも興味深い性質を持っています。

これらの特性を活かすことで、リード・マラー符号は、多様な通信技術における誤り訂正効率を向上させるために利用されています。

もう一度検索