2 元 BCH 符号 入門: 符号化

本記事で説明する内容:

• 「2 元原始狭義 BCH 符号」の例
• 符号化
• 復号化の概要
• その他、全体の大まかな内容

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

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

0. まとめ

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

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

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

1. 有限体

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

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

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

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

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

例えば、原始多項式を $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. 2 元 BCH 符号

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

このとき符号長 (すなわちデータと誤り訂正符号の両方を合わせた長さ) は $2^4 - 1 = 15$ ビットになります。

3.1. 最小ハミング距離

※本記事では最小ハミング距離自体の説明はしませんが、とりあえず下記のことだけ分かれば大丈夫です。

最小ハミング距離は誤りを訂正したい長さの 2 倍足す 1 以上にします。

例えば、最小ハミング距離を 7 とすると、合計 15 ビット中 $\left\lfloor \dfrac{7 - 1}{2} \right\rfloor = 3$ ビットのデータが誤っても訂正可能です。

(※最小ハミング距離と誤り訂正符号の長さは一致しません。具体的な長さは後述。)

3.2. 最小多項式

まず、最小多項式と呼ばれる多項式を求める必要があります。

最小多項式は

m_i(x) = (x - \alpha^i) (x - \alpha^{2i}) (x - \alpha^{4i}) (x - \alpha^{8i}) \dots

のように計算していき、前に出現した因数と同じ因数が来る前までで終わりとします。

例えば $i = 1$ のとき

\begin{alignat}{3}
&(x - \alpha^1 & &) (x - \alpha^2) (x - \alpha^4) (x - \alpha^8) (x - \alpha^{16} & &) (x - \alpha^{32} & &) \dots \\
= {} &(x - \alpha & &) (x - \alpha^2) (x - \alpha^4) (x - \alpha^8) (x - \alpha & &) (x - \alpha^2 & &) \dots
\end{alignat}

のように計算でき、最小多項式 $m_1(x)$ は

m_1(x) = (x - \alpha) (x - \alpha^2) (x - \alpha^4) (x - \alpha^8)

と求めることができます。ただし、ここでは有限体の性質上 $\alpha^{15} = 1$ です。

同様に計算すると

\begin{alignat}{5}
m_1(x) &= (x - \alpha   & &) (x - \alpha^2    & &) (x - \alpha^4    & &) (x - \alpha^8 & &) \\
m_2(x) &= (x - \alpha^2 & &) (x - \alpha^4    & &) (x - \alpha^8    & &) (x - \alpha   & &) = m_1(x) \\
m_3(x) &= (x - \alpha^3 & &) (x - \alpha^6    & &) (x - \alpha^{12} & &) (x - \alpha^9 & &) \\
m_4(x) &= (x - \alpha^4 & &) (x - \alpha^8    & &) (x - \alpha      & &) (x - \alpha^2 & &) = m_1(x) \\
m_5(x) &= (x - \alpha^5 & &) (x - \alpha^{10} & &) \\
m_6(x) &= (x - \alpha^6    & &) (x - \alpha^{12} & &) (x - \alpha^9 & &) (x - \alpha^3 & &) = m_3(x) \\
m_7(x) &= (x - \alpha^7 & &) (x - \alpha^{14} & &) (x - \alpha^{13} & &) (x - \alpha^{11} & &) \\
&\hspace{0.5em} \vdots \\
m_{14}(x) &= (x - \alpha^{14} & &) (x - \alpha^{13} & &) (x - \alpha^{11} & &) (x - \alpha^7 & &) = m_7(x)
\end{alignat}

のようになります。

ちなみに、ここでは $\alpha^{15} = 1$ より $\alpha^{2^4i} = \alpha^{16i} = \alpha^{15i} \alpha^i = \alpha^i$ となるため、有限体 $GF(2^4)$ 上で計算する場合は最小多項式の因数の個数は最大 4 つになります。

また、例えば $m_1(x) = (x - \alpha) (x - \alpha^2) (x - \alpha^4) (x - \alpha^8)$ の式の形から $m_1(x) = m_2(x) = m_4(x) = m_8(x)$ であることが分かります。

3.3. 生成多項式

3.3.1. 求め方

最小ハミング距離が $d$ 以上の誤り訂正符号を生成したいとき、生成多項式

G_d(x) = \operatorname{LCM} (m_1(x), m_2(x), \dots, m_{d-2}(x), m_{d-1}(x))

を使用します。ただし $\operatorname{LCM}$ 関数は最小公倍数を返します。

符号長が 15 ビットの場合は $2 \leq d \leq 15$ とします。

3.3.2. 例

例えば、$d = 7$ のとき生成多項式は

\begin{align}
G_7(x) &= \operatorname{LCM} (m_1(x), m_2(x), m_3(x), m_4(x), m_5(x), m_6(x)) \\
&= m_1(x) m_3(x) m_5(x) \\
&= (x - \alpha) (x - \alpha^2) (x - \alpha^3) (x - \alpha^4) (x - \alpha^5) (x - \alpha^6) (x - \alpha^8) (x - \alpha^9) (x - \alpha^{10}) (x - \alpha^{12}) \\
&= x^{10} + x^8 + x^5 + x^4 + x^2 + x + 1
\end{align}

になります。

同様に計算すると

\begin{align}
G_3(x) &= x^4 + x + 1 \\
G_5(x) &= x^8 + x^7 + x^6 + x^4 + 1 \\
G_7(x) &= x^{10} + x^8 + x^5 + x^4 + x^2 + x + 1 \\
G_{15}(x) &= x^{14} + x^{13} + x^{12} + \dots + x^2 + x + 1
\end{align}

\begin{align}
G_2(x) &= G_3(x) \\
G_4(x) &= G_5(x) \\
G_6(x) &= G_7(x) \\
G_8(x) = G_9(x) = \dots = G_{14}(x) &= G_{15}(x)
\end{align}

となります。

仮に $d = 8$ とした場合は $G_8(x) = G_{15}(x)$ より最小ハミング距離は 8 でなく 15 になり、$\left\lfloor \dfrac{8 - 1}{2} \right\rfloor = 3$ ビットでなく $\left\lfloor \dfrac{15 - 1}{2} \right\rfloor = 7$ ビット誤っていても訂正可能です。

$(n, k)$	最小ハミング距離	誤り訂正能力	生成多項式	誤り訂正符号の長さ
$(15,11)$	3	1	$G_3(x)$	4
$(15, 7)$	5	2	$G_5(x)$	8
$(15, 5)$	7	3	$G_7(x)$	10
$(15, 1)$	15	7	$G_{15}(x)$	14

3.4. 符号化

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

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

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

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

になります。

最小ハミング距離が $d$ 以上の誤り訂正符号を生成したいとき、情報多項式 $M(x)$ に $x$ の「誤り訂正符号の長さ」乗をかけた式を $G_d(x)$ で割った余り $R(x)$ が誤り訂正符号を表す多項式になります。

例えば、最小ハミング距離が 7 ビットの誤り訂正符号の長さは 10 ビットになり、誤り訂正符号は多項式

\begin{align}
R(x) &= x^{10} M(x) \bmod G_7(x) \\
&= x^{10} M(x) \bmod (x^{10} + x^8 + x^5 + x^4 + x^2 + x + 1) \\
\end{align}

で表されます。

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

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

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

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

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

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

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

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

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

データ符号　　　  00101
　　　　　　　　  001010000000000
生成多項式の係数      10100110111
誤り訂正符号　　       0011011100
符号　　　　　　  001010011011100

3.5. 復号化の概要

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

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

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

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

4. 関連記事

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