有限体の勉強 〜リード・ソロモン符号のシミュレーション〜

　有限体の勉強を始めてちょっとわかった気になってきましたが、ここで有限体の応用の一つである「誤り訂正符号」、その中でも誤り訂正能力が高い方式である「リード・ソロモン符号」について、その原理をシミュレートしてみたいと思います。

　誤り訂正能力がどのくらい高いのかというと、
「送りたいシンボルに2t個の冗長なシンボルを追加するだけで、t個までならどのシンボルにどんな誤りが生じても正しく復元することができる」
というくらい高いのです。QRコードがある程度まで汚損しても正しく読み取れるのはこの符号方式を使っているからであり、他にもCDや衛星通信など様々な場面で使われています。

　このリード・ソロモン符号については、Wikipediaの記事にその原理が記述されていたり、他にも書籍を含めてたくさんの解説がありますが、数式を眺めてもなかなか理解できるものではありません。そこで実際に手を動かして、符号化と復号の推移を見てみることにします。

　リード・ソロモン符号は有限体を係数とする多項式を本格的に使います。まずはその有限体を定めますが、8ビットで表現できる $F_{2^8} (= F_{256})$ を使うことが多いようなので、本記事でも $F_{256}$ を使います。

　例によって $F_{256}$ の乗法群 $F_{256}^\times$ の原始元を見つけることから始めなければいけませんが、そこからするのはもうしんどいのでWikipediaから答えを頂きます。次の多項式
\[ X^8+X^4+X^3+X^2+1 \]
は $F_2$ 上で既約で、その根$\alpha$が $F_{256}^\times$ の原始元を与えます。これさえわかれば、スプレッドシートを使って $F_{256}$ の全ての元について $\alpha$ のべき表現と $(\alpha^7, \alpha^6, \cdots , \alpha, 1)$ を基底とするベクトル表現との対応づけをすることができます。スプレッドシート上は単純な縦長の表になりますが、全体を見やすくするためベクトル表現を$16$進で表してここに掲載します。

$F_{256}$ の変換表（ベクトル表現16進 → べき表現）

	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0x	*	0	1	25	2	50	26	198	3	223	51	238	27	104	199	75
1x	4	100	224	14	52	141	239	129	28	193	105	248	200	8	76	113
2x	5	138	101	47	225	36	15	33	53	147	142	218	240	18	130	69
3x	29	181	194	125	106	39	249	185	201	154	9	120	77	228	114	166
4x	6	191	139	98	102	221	48	253	226	152	37	179	16	145	34	136
5x	54	208	148	206	143	150	219	189	241	210	19	92	131	56	70	64
6x	30	66	182	163	195	72	126	110	107	58	40	84	250	133	186	61
7x	202	94	155	159	10	21	121	43	78	212	229	172	115	243	167	87
8x	7	112	192	247	140	128	99	13	103	74	222	237	49	197	254	24
9x	227	165	153	119	38	184	180	124	17	68	146	217	35	32	137	46
Ax	55	63	209	91	149	188	207	205	144	135	151	178	220	252	190	97
Bx	242	86	211	171	20	42	93	158	132	60	57	83	71	109	65	162
Cx	31	45	67	216	183	123	164	118	196	23	73	236	127	12	111	246
Dx	108	161	59	82	41	157	85	170	251	96	134	177	187	204	62	90
Ex	203	89	95	176	156	169	160	81	11	245	22	235	122	117	44	215
Fx	79	174	213	233	230	231	173	232	116	214	244	234	168	80	88	175

$F_{256}$ の変換表（べき表現 → ベクトル表現16進）

	0	1	2	3	4	5	6	7	8	9
0x	01	02	04	08	10	20	40	80	1D	3A
1x	74	E8	CD	87	13	26	4C	98	2D	5A
2x	B4	75	EA	C9	8F	03	06	0C	18	30
3x	60	C0	9D	27	4E	9C	25	4A	94	35
4x	6A	D4	B5	77	EE	C1	9F	23	46	8C
5x	05	0A	14	28	50	A0	5D	BA	69	D2
6x	B9	6F	DE	A1	5F	BE	61	C2	99	2F
7x	5E	BC	65	CA	89	0F	1E	3C	78	F0
8x	FD	E7	D3	BB	6B	D6	B1	7F	FE	E1
9x	DF	A3	5B	B6	71	E2	D9	AF	43	86
10x	11	22	44	88	0D	1A	34	68	D0	BD
11x	67	CE	81	1F	3E	7C	F8	ED	C7	93
12x	3B	76	EC	C5	97	33	66	CC	85	17
13x	2E	5C	B8	6D	DA	A9	4F	9E	21	42
14x	84	15	2A	54	A8	4D	9A	29	52	A4
15x	55	AA	49	92	39	72	E4	D5	B7	73
16x	E6	D1	BF	63	C6	91	3F	7E	FC	E5
17x	D7	B3	7B	F6	F1	FF	E3	DB	AB	4B
18x	96	31	62	C4	95	37	6E	DC	A5	57
19x	AE	41	82	19	32	64	C8	8D	07	0E
20x	1C	38	70	E0	DD	A7	53	A6	51	A2
21x	59	B2	79	F2	F9	EF	C3	9B	2B	56
22x	AC	45	8A	09	12	24	48	90	3D	7A
23x	F4	F5	F7	F3	FB	EB	CB	8B	0B	16
24x	2C	58	B0	7D	FA	E9	CF	83	1B	36
25x	6C	D8	AD	47	8E

　本記事では $F_{256}$ の元はべき表現で扱うことを基本とするので、乗法演算は指数を足し合わせて$\mod 255$ をとることで行えます。加法演算はちょっと手間ですが、変換表を用いてベクトル表現にしてから各ビット毎にXORを取って、再び変換表を用いてべき表現にすれば求まります。実際にはこれらの計算は全部スプレッドシート上で関数を駆使して行いました。

　では、実際に文字列 "Hello!" をリード・ソロモン符号で符号化し、通信路上で生じた誤りが受信側で復元できることを見てみましょう。以下ではWikipediaの記事の方法に従ってシミュレートします。

　リード・ソロモン符号では、符号を $F_{256}$ の元を係数とする多項式で表します。"Hello!" の6文字をASCIIコード16進で表すと、

48, 65, 6C, 6C, 6F, 21

となりますが、これを $F_{256}$ の元のベクトル表現とみなしてべき表現に変換すると、
\[ \alpha^{226}, \ \alpha^{72}, \ \alpha^{250}, \ \alpha^{250}, \ \alpha^{61}, \ \alpha^{138} \]
となり、これを表す情報多項式 $I(X)$ は、
\[ I(X) = \alpha^{226}X^5 + \alpha^{72}X^4 + \alpha^{250}X^3 + \alpha^{250}X^2 + \alpha^{61}X + \alpha^{138} \]
という$5$次多項式になります。
　これに誤り検出と訂正のための冗長化符号を追加します。ここでは最大 $t = 2$ 個のシンボルの誤りが訂正できるようにします。このため、生成多項式 $G(X)$ は
\[ G(X) = (X-\alpha^0)(X-\alpha^1)(X-\alpha^2)(X-\alpha^3) = X^4+\alpha^{75}X^3+\alpha^{249}X^2+\alpha^{78}X+\alpha^6 \]
によって定めればよく、これを使うと冗長多項式 $P(X)$ は
\[ P(X) = I(X) \times X^4 \mod G(X) = \alpha^{189}X^3 + \alpha^{19}X^2 + \alpha^{42}X + \alpha^{177} \]
となって、実際に送信する符号多項式 $C(X)$ は
\begin{eqnarray*}
C(X) &=& I(X) \times X^4 + P(X) \\
&=& \alpha^{226}X^9 + \alpha^{72}X^8 + \alpha^{250}X^7 + \alpha^{250}X^6 + \alpha^{61}X^5 + \alpha^{138}X^4 + \alpha^{189}X^3 + \alpha^{19}X^2 + \alpha^{42}X + \alpha^{177}
\end{eqnarray*}
となります。この上位$6$つの項の係数が送りたい文字列 "Hello!" を表しています。

　さて、この送信符号に通信路上で誤りが混入し、受信側では
\[ Y(X) = \alpha^{226}X^9 + \alpha^{72}X^8 + \alpha^{250}X^7 + \alpha^{250}X^6 + \alpha^{138}X^5 + \alpha^{138}X^4 + \alpha^{189}X^3 + \alpha^{43}X^2 + \alpha^{42}X + \alpha^{177} \]
となったとしましょう。つまり受信側では $X^5$ の係数が $\alpha^{61}$ から $\alpha^{138}$ に化け、さらに冗長化で追加した部分も $X^2$ の係数が $\alpha^{19}$ から $\alpha^{43}$ に化けて伝わったと想定します。これでは情報部分が文字列 "Hell!!" を表すことになり、そのまま受け止めるとコミュニケーション上大変な問題が生じてしまいます。
　そこで、この受信符号から誤りを見つけ出し、訂正する必要があります。これもWikipediaの記事に従って実際に行ってみます。

　まず、シンドロームと呼ばれる $t \times 2 = 4$ 個の $F_{256}$ の値を次によって計算します。
\begin{eqnarray*}
S_1 &=& Y(\alpha^0) &=& \alpha^{163} \\
S_2 &=& Y(\alpha^1) &=& \alpha^{112} \\
S_3 &=& Y(\alpha^2) &=& \alpha^{2} \\
S_4 &=& Y(\alpha^3) &=& \alpha^{25}
\end{eqnarray*}
$C(X)$ が $G(X)$ で整除されるので、もし誤りがなければこれらは全て$0$になるはずのものですが、誤りが生じているためどれも$0$以外の値となっています。

　次にこれらの値を使って誤り数 $k$ を求めます。次の行列式を計算します。
\begin{equation*}
\begin{vmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{vmatrix}
= S_2^2 - S_1S_3 = \alpha^{247}
\end{equation*}
これは$0$ではないので、$k = 2$ すなわち誤りのあるシンボル数は$2$個です（$3$個以上の誤りは想定しないものとします）。

　続いて、誤りがどの位置にあるのかを特定します。$k=2$ なので、誤り位置多項式 $\sigma(X)$ は次の形の$2$次多項式になります。
\[ \sigma(X) = \sigma_2X^2 +\sigma_1X+1 \]
ここで係数 $\sigma_1, \sigma_2$ は、
\begin{equation*}
\begin{bmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
=
\begin{bmatrix}
S_3 \\
S_4 \\
\end{bmatrix}
\end{equation*}
をみたすので、これを解くと $\sigma_1 = \alpha^{225}, \ \sigma_2 = \alpha^{7}$ が得られ、
\[ \sigma(X) = \alpha^{7}X^2 +\alpha^{225}X+1 \]
となります。
　この $\sigma(X)$ に $\alpha^0, \alpha^{-1}, \cdots , \alpha^{-9}$ を次々に代入すると、$\sigma(\alpha^{-2})$ と $\sigma(\alpha^{-5})$ だけが$0$となり、他は$0$ではないので、$Y(X)$ の $X^2$ と $X^5$ の係数が誤りを含んでいると特定されました。

　最後に誤りの値を計算します。誤り多項式 $E(X) = Y(X) - C(X)$ は
\[ E(X) = e_1X^5 + e_2X^2 \]
の形になることがわかりましたので、これに $\alpha^0, \alpha^1$ を代入することにより、
\begin{eqnarray*}
e_1 &+& e_2 &=& S_1 &=& \alpha^{163} \\
e_1\alpha^5 &+& e_2\alpha^2 &=& S_2 &=& \alpha^{112}
\end{eqnarray*}
これを解くと $e_1 = \alpha^{34}, \ e_2 = \alpha^{18}$ が得られるので、
\begin{eqnarray*}
C(X) &=& Y(X) + E(X) \\
&=& \alpha^{226}X^9 + \alpha^{72}X^8 + \alpha^{250}X^7 + \alpha^{250}X^6 &+& \alpha^{138}X^5 + \alpha^{138}X^4 + \alpha^{189}X^3 &+& \alpha^{43}X^2 + \alpha^{42}X + \alpha^{177} \\
&& &+& \alpha^{34}X^5 &+& \alpha^{18}X^2\\
&=& \alpha^{226}X^9 + \alpha^{72}X^8 + \alpha^{250}X^7 + \alpha^{250}X^6 &+& \alpha^{61}X^5 + \alpha^{138}X^4 + \alpha^{189}X^3 &+& \alpha^{19}X^2 + \alpha^{42}X + \alpha^{177}
\end{eqnarray*}
となって、無事に送信符号と同じもの、情報部分の文字列 "Hello!" が復元されました。

　このシミュレーションを行ったスプレッドシートをそのままここにアップロードしておきます。ダウンロードしてExcelなどで開き、2箇所の黄色のセルに$0$から$254$までのどのような数字を入れても、復号した緑のセルは元の青いセルの値が正しく表示されることが確認できると思います。

　有限体の四則演算が自由自在にできることを利用した巧妙な符号化方式であることが実感できました。考えた人（リードさんとソロモンさん）は天才ですね。

（続く）（前記事）

コメント 2

仕事でFPGAにリードソロモンの復号を実装する必要が生じて、ここにたどり着きました。
有限体とか全く知らなかったのですが、このページとスプレッドシートのおかげで何とか実装できそうです。
具体的に書かれていたおかげで、有限体と原始元の意味も少し理解できました。
ありがとうございました。
by 通りすがり (2022-02-27 10:51) 

　通りすがりさん、コメントの承認が大変遅くなって申し訳ありませんでした。
　僕は数学的興味からリード・ソロモン法を調べたのですが、現実に実装される立場の人は、原理の勉強もさることながら実装時の問題もたくさんあるとのことで、大変だと思います。
　少しでも僕の稚拙なブログが役に立てば嬉しいです。
by ロイロット博士 (2022-05-01 10:37)