2 元ゴレイ符号 入門: 符号化

本記事で説明する内容:

• 符号化
• 復号化の概要
• その他、全体の大まかな内容

本記事で説明しない内容:

• 復号化の詳細
• その他、厳密な数学的な内容

0. まとめ

2 元ゴレイ符号を用いると、データの誤りを検出したり訂正したりできます。

2 元ゴレイ符号では、有限体またはガロア体と呼ばれる特殊な計算方法を使います。

符号化は、有限体上で割り算しその余りを元のデータに付け加えます。

1. 有限体

有限体に関しては別記事にしました。

参考「有限体の例: GF(2^4) と GF(2^8) - Qiita」

2. 多項式の割り算の余りの計算方法

2 元ゴレイ符号では符号化時に多項式の割り算の余りを計算します。

多項式の割り算自体は通常の計算と同様に筆算等で行えますが、その過程で係数の四則演算は有限体上で行います。

例えば、原始多項式を $x^3 + x + 1$ とする有限体 $GF(2^3)$ 上で計算すると、$x^4 + x^3$ 割る $x^3 + x + 1$ は

\require{enclose}
\begin{align}
\hspace{0.25em} x^\phantom{4} \hspace{0.25em} + \hspace{0.25em} \rlap{1} \phantom{x^3} \hspace{0.25em} \phantom{{} + \hspace{0.25em} x^2 \hspace{0.25em} + \hspace{0.25em} x \hspace{0.25em} + \hspace{0.25em} 1 \hspace{0.25em}} \\
x^3 \hspace{0.25em} + \hspace{0.25em} x \hspace{0.25em} + \hspace{0.25em} 1 \hspace{0.25em} \rlap{\enclose{longdiv}{\phantom{ \hspace{0.25em} x^4 \hspace{0.25em} + \hspace{0.25em} x^3 \hspace{0.25em} }}} \hspace{0.5em} \hspace{0.25em} x^4 \hspace{0.25em} + \hspace{0.25em} x^3 \hspace{0.25em} \phantom{{} + \hspace{0.25em} x^2 \hspace{0.25em} + \hspace{0.25em} x \hspace{0.25em} + \hspace{0.25em} 1 \hspace{0.25em}} \\
\rlap{\underline{\phantom{ \hspace{0.25em} x^4 \hspace{0.25em} + \hspace{0.25em} x^3 \hspace{0.25em} + \hspace{0.25em} x^2 \hspace{0.25em} + \hspace{0.25em} x \hspace{0.25em} }}} \hspace{0.25em} x^4 \hspace{0.25em} \phantom{{} + \hspace{0.25em} x^3} \hspace{0.25em} + \hspace{0.25em} x^2 \hspace{0.25em} + \hspace{0.25em} x \hspace{0.25em} \phantom{{} + \hspace{0.25em} 1 \hspace{0.25em}} \\
\hspace{0.25em} x^3 \hspace{0.25em} + \hspace{0.25em} x^2 \hspace{0.25em} + \hspace{0.25em} x \hspace{0.25em} \phantom{{} + \hspace{0.25em} 1 \hspace{0.25em}} \\
\rlap{\underline{\phantom{ \hspace{0.25em} x^3 \hspace{0.25em} + \hspace{0.25em} x^2 \hspace{0.25em} + \hspace{0.25em} x \hspace{0.25em} + \hspace{0.25em} 1 \hspace{0.25em} }}} \hspace{0.25em} x^3 \hspace{0.25em} \phantom{{} + \hspace{0.25em} x^2} \hspace{0.25em} + \hspace{0.25em} x \hspace{0.25em} + \hspace{0.25em} 1 \hspace{0.25em} \\
\hspace{0.25em} x^2 \hspace{0.25em} \phantom{{} + \hspace{0.25em} x} \hspace{0.25em} + \hspace{0.25em} 1 \hspace{0.25em}
\end{align}

のように計算できます。

この例では商は

Q(x) = x + 1

になり、余りは

\begin{align}
R(x) &= (x^4 + x^3) \bmod (x^3 + x + 1) \\
&= x^2 + 1
\end{align}

となります。

3. (23, 12, 7) 完全 2 元ゴレイ符号

ここでは符号長 (すなわちデータと誤り訂正符号の両方を合わせた長さ) を 23 ビットとします。

(本記事では符号長の条件について詳しく説明しませんが、符号長は素数である必要があります。)

証明が少しややこしいため本記事では詳しく説明しませんが、最小ハミング距離は 7 になり誤り訂正能力は $\left\lfloor \dfrac{7 - 1}{2} \right\rfloor = 3$ になります。

2 元ゴレイ符号の構成方法はいくつかありますが、ここでは主に 2 元平方剰余符号として構成する方法を説明します。

3.1. 有限体上の計算の準備

ここでは、原始多項式を $x^{11} + x^2 + 1$ とする有限体 $GF(2^{11})$ を使用します。

このとき

\begin{alignat}{2}
\alpha^{2^{11}-1} &= \alpha^{2047} & &= 1 \\
2^{11} - 1 &= 2047 & &= 23 \times 89
\end{alignat}

が成り立ちます。

ここで

\beta = \alpha^{89}

とすると

\beta^{23} = \alpha^{2047} = 1

が成り立ち

\begin{alignat}{3}
&β^0    & &= \alpha^0      & &= 00000000001_{(2)} \\
&β^1    & &= \alpha^{89}   & &= 00101000010_{(2)} \\
&β^2    & &= \alpha^{178}  & &= 00010101110_{(2)} \\
&β^3    & &= \alpha^{267}  & &= 10010001100_{(2)} \\
&β^4    & &= \alpha^{356}  & &= 10001111100_{(2)} \\
&β^5    & &= \alpha^{445}  & &= 00111100001_{(2)} \\
&β^6    & &= \alpha^{534}  & &= 01001111101_{(2)} \\
&β^7    & &= \alpha^{623}  & &= 11110010110_{(2)} \\
&β^8    & &= \alpha^{712}  & &= 11101011111_{(2)} \\
&β^9    & &= \alpha^{801}  & &= 10111101110_{(2)} \\
&β^{10} & &= \alpha^{890}  & &= 10010000011_{(2)} \\
&β^{11} & &= \alpha^{979}  & &= 00010100111_{(2)} \\
&β^{12} & &= \alpha^{1068} & &= 11111011011_{(2)} \\
&β^{13} & &= \alpha^{1157} & &= 00110100010_{(2)} \\
&β^{14} & &= \alpha^{1246} & &= 00100011001_{(2)} \\
&β^{15} & &= \alpha^{1335} & &= 10111110101_{(2)} \\
&β^{16} & &= \alpha^{1424} & &= 00101111010_{(2)} \\
&β^{17} & &= \alpha^{1513} & &= 11011000000_{(2)} \\
&β^{18} & &= \alpha^{1602} & &= 11011010011_{(2)} \\
&β^{19} & &= \alpha^{1691} & &= 00100111111_{(2)} \\
&β^{20} & &= \alpha^{1780} & &= 01000101000_{(2)} \\
&β^{21} & &= \alpha^{1869} & &= 11101010100_{(2)} \\
&β^{22} & &= \alpha^{1958} & &= 10000111101_{(2)}
\end{alignat}

という対応を作ることができます。

3.2. 平方剰余

平方剰余は簡単に言うと「2 乗の割り算の余り」です。

$x^2 \bmod p = q$ となる整数 $x$ が存在する整数 $q$ を平方剰余と呼びます。

$p = 23$ とすると

\begin{align}
1^2 \bmod 23 &= 1 \\
2^2 \bmod 23 &= 4 \\
3^2 \bmod 23 &= 9 \\
4^2 \bmod 23 &= 16 \\
5^2 \bmod 23 &= 2 \\
6^2 \bmod 23 &= 13 \\
7^2 \bmod 23 &= 3 \\
8^2 \bmod 23 &= 18 \\
9^2 \bmod 23 &= 12 \\
10^2 \bmod 23 &= 8 \\
11^2 \bmod 23 &= 6
\end{align}

となり、平方剰余は

q \in Q = \{1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18\}

の 11 個が得られます。

$x = 12$ 以降では

\begin{align}
(23 \pm x)^2 \bmod 23 &= (23^2 \pm 2 \cdot 23 x + x^2) \bmod 23 \\
&= x^2 \bmod 23
\end{align}

より同じ平方剰余が出現します (厳密には $23^2 \bmod 23 = 0$ のように 0 も出現します) 。

実際に計算すると

\begin{align}
12^2 \bmod 23 &= 6 \\
13^2 \bmod 23 &= 8 \\
14^2 \bmod 23 &= 12 \\
15^2 \bmod 23 &= 18 \\
16^2 \bmod 23 &= 3 \\
17^2 \bmod 23 &= 13 \\
18^2 \bmod 23 &= 2 \\
19^2 \bmod 23 &= 16 \\
20^2 \bmod 23 &= 9 \\
21^2 \bmod 23 &= 4 \\
22^2 \bmod 23 &= 1 \\
23^2 \bmod 23 &= 0 \\
24^2 \bmod 23 &= 1 \\
25^2 \bmod 23 &= 4 \\
26^2 \bmod 23 &= 9 \\
27^2 \bmod 23 &= 16 \\
28^2 \bmod 23 &= 2 \\
29^2 \bmod 23 &= 13 \\
30^2 \bmod 23 &= 3 \\
31^2 \bmod 23 &= 18 \\
32^2 \bmod 23 &= 12 \\
33^2 \bmod 23 &= 8 \\
34^2 \bmod 23 &= 6 \\
&\hspace{0.5em} \vdots
\end{align}

のようになります。

ちなみに 2 元ゴレイ符号は 2 元 BCH 符号としても構成することができ、2 のべき剰余 (簡単に言うと「べき乗の割り算の余り」) でも

\begin{alignat}{2}
&2^0 & \bmod 23 &= 1 \\
&2^1 & \bmod 23 &= 2 \\
&2^2 & \bmod 23 &= 4 \\
&2^3 & \bmod 23 &= 8 \\
&2^4 & \bmod 23 &= 16 \\
&2^5 & \bmod 23 &= 9 \\
&2^6 & \bmod 23 &= 18 \\
&2^7 & \bmod 23 &= 13 \\
&2^8 & \bmod 23 &= 3 \\
&2^9 & \bmod 23 &= 6 \\
&2^{10} & \bmod 23 &= 12 \\
\end{alignat}

のように同じ値が得られます (ただし同じ値が出現する順番は異なります) 。

参考「2 元 BCH 符号 入門: 符号化 - Qiita」

3.3. 生成多項式

平方剰余符号では生成多項式

G_Q(x) = \prod_{i \in Q} (x - \beta^i)

を使用します。

例えば、$Q = \{1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18\}$ のとき生成多項式は

\begin{align}
G_Q(x) &= \prod_{i \in Q} (x - \beta^i) \\
&= x^{11} + x^9 + x^7 + x^6 + x^5 + x + 1
\end{align}

になります。

ちなみに他の構成法 (2 元 BCH 符号等) では $Q = \{5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22\}$ とすることもでき、このとき生成多項式は

\begin{align}
G_Q(x) &= \prod_{i \in Q} (x - \beta^i) \\
&= x^{11} + x^{10} + x^6 + x^5 + x^4 + x^2 + 1
\end{align}

となります。

3.4. 符号化

3.4.1. 多項式で計算する場合

符号化したいデータを情報多項式 $M(x)$ として扱います。

例えば、2 進数で 000000000111 という 12 ビットのデータ符号があるとき、情報多項式は

\begin{align}
M(x) &= 0 x^{11} + 0 x^{10} + 0 x^9 + 0 x^8 + 0 x^7 + 0 x^6 + 0 x^5 + 0 x^4 + 0 x^3 + 1 x^2 + 1 x + 1 \\
&= x^2 + x + 1
\end{align}

になります。

情報多項式 $M(x)$ に $x$ の「誤り訂正符号の長さ」乗をかけた式を $G_Q(x)$ で割った余り $R(x)$ が誤り訂正符号を表す多項式になります。

ここでは誤り訂正符号の長さは 11 ビットなので、$Q = \{1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18\}$ のとき誤り訂正符号は多項式

\begin{align}
R(x) &= x^{11} M(x) \bmod G_Q(x) \\
&= x^{11} M(x) \bmod (x^{11} + x^9 + x^7 + x^6 + x^5 + x + 1) \\
\end{align}

で表されます。

情報多項式 $M(x)$ を代入すると

\begin{align}
R(x) &= (x^{13} + x^{12} + x^{11}) \bmod (x^{11} + x^9 + x^7 + x^6 + x^5 + x + 1) \\
&= x^{10} + x^9 + x^6 + x^3 + x \\
&= 1 x^{10} + 1 x^9 + 0 x^8 + 0 x^7 + 1 x^6 + 0 x^5 + 0 x^4 + 1 x^3 + 0 x^2 + 1 x + 0
\end{align}

となり、誤り訂正符号は 11001001010 になります。

誤り訂正符号の長さが 11 ビットのとき、2 元ゴレイ符号は情報多項式 $M(x)$ と割り算の余り $R(x)$ を合わせて符号多項式

\begin{align}
C(x) &= x^{11} M(x) + R(x) \\
&= x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^6 + x^3 + x \\
&= 0 x^{22} + 0 x^{21} + 0 x^{20} + 0 x^{19} + 0 x^{18} + 0 x^{17} + 0 x^{16} + 0 x^{15} + 0 x^{14} + 1 x^{13} + 1 x^{12} + 1 x^{11} + 1 x^{10} + 1 x^9 + 0 x^8 + 0 x^7 + 1 x^6 + 0 x^5 + 0 x^4 + 1 x^3 + 0 x^2 + 1 x + 0
\end{align}

で表され、ビット列は 00000000011111001001010 (単に、データ符号 000000000111 と誤り訂正符号 11001001010 を連結したもの) になります。

3.4.2. 多項式の係数のみで計算する場合

理論上は 2 元ゴレイ符号の計算は多項式で行いますが、符号化に関しては多項式の割り算をするだけで $x$ に値を代入しないため、多項式の各係数のみに着目して計算することができます。

2 元ゴレイ符号では情報多項式や生成多項式の係数が 0 か 1 になるため、ある 1 つの多項式の係数をまとめて 1 つの 2 進数の数として扱えます。

データ符号　　　  000000000111
　　　　　　　　  000000000111 00000000000
生成多項式の係数             1 01011100011
誤り訂正符号　　               11001001010
符号　　　　　　  000000000111 11001001010

4. (24, 12, 8) 拡大 2 元ゴレイ符号

本記事では詳しく説明しませんが、2 元ゴレイ符号は線形符号です。

線形符号である 2 元ゴレイ符号に偶数パリティを追加する (符号内の 1 のビットが偶数個になるように 1 桁ビットを追加する) ことで、拡大 2 元ゴレイ符号 (または拡張 2 元ゴレイ符号) を構成することができます。

ここでは (23, 12, 7) 完全 2 元ゴレイ符号を拡大して (24, 12, 8) 拡大 2 元ゴレイ符号を構成します。

拡大線形符号の性質より、(7 は奇数のため) 最小ハミング距離は $7 + 1 = 8$ になり誤り訂正能力は $\left\lfloor \dfrac{8 - 1}{2} \right\rfloor = 3$ になります。

参考「拡大線形符号、短縮符号、削除符号の概要 - Qiita」

4.1. 生成多項式

生成多項式に $x + 1$ をかけることで偶数パリティを追加できます。

例えば、$Q = \{1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18\}$ のとき生成多項式は

\begin{align}
G'_Q(x) &= (x + 1) G_Q(x) \\
&= (x + 1) (x^{11} + x^9 + x^7 + x^6 + x^5 + x + 1) \\
&= x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^5 + x^2 + 1
\end{align}

になります。

4.2. 符号化

拡大線形符号でも同様の方法で符号化できます。

ここでは誤り訂正符号の長さは 12 ビットなので、誤り訂正符号および符号は多項式

\begin{align}
R'(x) &= x^{12} M(x) \bmod G'_Q(x) \\
C'(x) &= x^{12} M(x) + R'(x)
\end{align}

で表されます。

例えば、2 進数で 000000000111 という 12 ビットのデータ符号があるとき、誤り訂正符号は 110010010100、符号は 000000000111110010010100 (単に、データ符号と誤り訂正符号を連結したもの) になります。

データ符号　　　  000000000111
　　　　　　　　  000000000111 000000000000
生成多項式の係数             1 111100100101
誤り訂正符号　　               110010010100
符号　　　　　　  000000000111 110010010100

(23, 12, 7) 完全 2 元ゴレイ符号と (24, 12, 8) 拡大 2 元ゴレイ符号を比較すると、誤り訂正符号に偶数パリティが追加されていることが分かります。

データ符号　　　                 000000000111
(23, 12, 7) 完全 2 元ゴレイ符号  000000000111 11001001010
(24, 12, 8) 拡大 2 元ゴレイ符号  000000000111 110010010100

5. おまけ: (18, 6, 8) 短縮 2 元ゴレイ符号

データ符号の先頭 6 ビットを除去することで、(24, 12, 8) 拡大 2 元ゴレイ符号を短縮して (18, 6, 8) 短縮 2 元ゴレイ符号を構成できます。

参考「拡大線形符号、短縮符号、削除符号の概要 - Qiita」

符号長は異なりますが、生成多項式および符号化の手順は同じです。

誤り訂正符号　　                              110010010100
(24, 12, 8) 拡大 2 元ゴレイ符号  000000000111 110010010100
(18,  6, 8) 短縮 2 元ゴレイ符号        000111 110010010100

6. 2 元ゴレイ符号の復号化の概要

2 元ゴレイ符号の復号法は色々あります。

一般化された方法として、以下の手順で復号することができます:

1. 誤り検出
2. 誤り位置の検出
3. 誤り訂正

ただし、2 元ゴレイ符号でデータのビット長が短い場合、符号としてあり得る値と比較して全探索した方が計算量を減らせる場合があります。

例えば、(18, 6, 8) 短縮 2 元ゴレイ符号ではデータの長さが 6 ビットのため、$2^6 = 64$ つの符号としてあり得る値と比較して、一致するものが見つかれば誤りなし、一致するものが見つからなければ値が異なるビットの個数が最も少ないものに訂正して復号できます。

7. 関連記事

参考「2 元 BCH 符号 入門: 符号化 - Qiita」
参考「リード・ソロモン符号 入門: 符号化と誤り検出 - Qiita」