第 5 回 誤り訂正符号

本日の内容

• 5-1. レポート課題
• 5-2. 講義

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

5-1. レポート課題

ワーク5-1

$\mathrm{GF}\left(2\right)$ の演算表を作りなさい

ワーク5-2

$\mathrm{GF}\left(2^2\right)$ について

1. 整数を4で割った余りは $\mathrm{GF}\left(2^2\right)$ にならないことを、演算表を作って、反例を見つけることで示しなさい。
2. 係数が $\mathrm{GF}\left(2\right)$ (つまり 0,1 ) の多項式を $x^2+x+1$ で割った余りを考えると、 $\mathrm{GF}\left(2^2\right)$ となることを演算表を作って示しなさい。 (このような多項式のことを体の原始多項式と言います）
3. $\mathrm{GF}\left(2^2\right)$ の 0 でも 1 でもない元 $x$ は、 $x,x^2,x^3$ で、 $\mathrm{GF}\left(2^2\right)$ の 0 で無い要素を網羅できることを確かめなさい。 (このような元を体の原始元と言います)

ワーク5-3

次の (7,4)符号の生成行列を考えます。

1. パリティチェック行列を求めなさい
2. 送信符号7bit に関して、それぞれ1bit誤ったときのシンドロームを求 めなさい
3. 学籍番号の下3桁をそれぞれ4桁の2進数にして、3つのメッセージベクトル を作りなさい。 そして、それぞれに生成行列をかけ、送信符号7✕3=21bit を求めなさい。
4. それぞれの送信符号を1ビット改変したものを作り、隣同士で交換しなさい
5. 受け取った誤りを含んだ送信符号の誤りを訂正し、情報を取り出しなさい。

締切、提出方法

来週の火曜日の夕方までに <[email protected]>宛に グループで一通のレポートを作成し、 メールすること。

5-2. 講義

整数の余り

通信では、全ての符号が有限の長さです。従って、有限の長さの符号の性質 を知る必要があります。

まず、「下何桁」に相当する、数の余りについて考えることにします。 特定の数を定めます（法と言います）。 計算を行った後、また、その法による余りを求めることにします。

例えば、100×200=20000となりますが、それぞれの3で割った余りを考える と、100は1, 200 は2, 20000 は2となります。 そのため、1×2=2 と同じ結果になります。 実際に、演算に関して、余りだけを考える場合、最初から余りだけを考えれば 済みます。 つまり、余りを考える場合、どんな大きな数でも、余りが等しければ同じ性 質を持ちます。

余りが等しいという関係は、次の関係を持ちます。

1. x と x は余りが等しい（反射律）
2. x と y の余りが等しければ、 y と x の余りも等しい（対称律）
3. x と y の余りが等しく、 y と z の余りが等しければ、 x と z の余 りが等しい（推移律）

数学ではこの反射律、対称律、推移律を満たす関係を同値関係 と言い、 ≡の記号を使います。 特に、余りが等しいということを示すのに、法を n とすると次の式を用い ます。

例えば、 $2^{103}$ を5で割った余りはいくつになるでしょうか？ これは次のようにして解きます。

素数を法とした余り

さて、ここで、法を素数pに限定します。 $p$ の倍数でない2つの数の積は $p$ の倍数にはなりません。 さらに、数 $x$ に対して、 $xy\equiv 1\left(modp\right)$ となる$y$が必ず存在します（証明はユークリッドの 互除法を使うなど）。 例えば、法 5 に関する掛け算の演算表を示します。

これにより、5 で割った余りの中で、足し算、掛け算に対して、逆元が存在 することがわかりました。

素数を法とした余りでは、足し算、掛け算に逆元があります。 足し算、掛け算についてこのような性質がある集合を体と言い、特に有限集 合の体を ガロア体と言います。 素数$p$を法とした余りの集合を $\mathrm{GF}\left(p\right)$ で表します。

素数冪の有限体

4や25で割った余りについては体になりません。 しかし、体の元を係数とする多項式の間で、ある多項式を法とした余りを考 えると体になります。

$\mathrm{GF}\left(p^r\right)$ は、$r-1$次の多項式の集合で、 $r$次の最高次の係数が1の既約多項式を法とした余り を考えます。

例えば、 $\mathrm{GF}\left(3^2\right)$ を考えると、集合は $\left\{0,1,2,x,x+1,x+2,2x,2x+1,2x+2\right\}$ です。 既約多項式は2次式になるのですが、 ここでは $x^2+x+2$ と与えておきます。 すると演算表はつぎのようになります。

特に、ディジタル通信などでは、二進数を使うので $\mathrm{GF}\left(2^r\right)$ が使われます。

体の性質

体の性質には様々あります。 その一つとして、体には原始元というものがあります。

体$F$から0を取り除いたものを $F^{*}$ で表します。 この時、要素 $\alpha \in F^{*}$ により、 $\left\{\alpha ,{\alpha }^2,{\alpha }^3,...\right\}=F^{*}$ となるものが存在し、それを原始元と呼びます。 明らかに 1 は $\mathrm{GF}\left(2\right)$ 以外では原始元になりません。 体の要素のうちの一部のみが原始元になります。

例えば、 $\mathrm{GF}\left(5\right)$ では、2,3 が原始元になります。

同様に、 $\mathrm{GF}\left(3^2\right)$ では、 $x,x+1,2x,2x+2$ が原始元になります。

また、体の係数の多項式は一意に素因数分解できることが保証されます。

有限体

コンピュータのデータ表現は有限です。 そのため、数学的な処理もすべて有限の操作に限られます。 有限長のデータに関して、様々な操作が、通常の整数や実数などを使った数 学的な性質と同じ性質を持つと便利です。

足し算や掛け算の持つ性質が有限集合で成り立つと、数学の性質を有限集合 に適用できます。 集合$G$と演算子 $\circ$ が整数の足し算のような性質を持つには、 次のような性質が必要になります。

1. どんな要素 $x,y\in G$ であっても演算可能で、 演算結果は集合に含まれる $x\circ y\in G$ 。
2. 演算結果を変えない単位元（0のようなもの) $e\circ x=x$ がある。
3. 単位元に戻せる元(逆元)がある $x\circ y=e$ がある。

このような性質を含み、さらに足し算や掛け算の性質を持つために必要な条 件などが研究され、群、環、体などの概念が生まれました。

集合$G$と演算子 $\circ$ が群であるとは、次の条件を満たすことです。

1. すべての演算結果が閉じている。 つまり、 $x,y\in G$ ならば、 $x\circ y\in G$ が成り立つ。
2. 結合法則 $\left(x\circ y\right)\circ z=x\circ \left(y\circ z\right)$ が成立
3. 単位元 $e$ が存在する。 つまり、 $x\circ e=x$
4. 逆元が存在する。 つまりすべての $x\in G$ に対して、次を満たす$y\in G$ が必ず存在する: $x\circ y=e$

集合$F$と2つの演算子 ＋, ・が 体であるとは、次の条件が成り立つことです：

1. F が ＋ に対して群になり、単位元が 0となる
2. Fから0を取り除いた集合について・が群になり、単位元が1となる
3. 分配法則 $\left(x+y\right)z=xz+yz$ が成り立つ

例えば、整数は足し算について群になっています。 さらに、有理数、実数、複素数は足し算、掛け算について群になっていて、 さらに体にもなっています。 そして、これらの持つ重要な性質（方程式が解ける）などは既に学んだとお りです。

コンピュータや通信では、無限長のデータは扱いません。 そのため、符号やデータ表現は有限の集合に含まれます。 有限の集合が群や体になると、有理数や実数などで成り立っていた様々な定 理やアルゴリズムが流用できます。

演算に交換法則 $x\circ y=y\circ x$ が成り立つ群を 可換群あるいはアーベル群 と呼びます。

単純な有限アーベル群としては、 整数の余りがあります。 有限アーベル群には基本定理があり、「素数のべき乗の群の直和になる」、 つまり、要素数に対して構造が一意に定まることが知られています。

さらに、有限体はガロア体とも呼ばれますが、要素数は素数の べきに限られ、構造も一意に定まります。 素数$p$で割った余りは有限体 $\mathrm{GF}\left(p\right)$ になります。 また、論理演算も有限体 $\mathrm{GF}\left(2\right)$ になります。

なお、有限体には生成元と呼ばれる要素が（いくつか）存在し ます。 これは、ある生成元$g$に対してその有限体が $\left\{0,1,g,g^2,...,g^k\right\}$ で要素をすべて表すことができます。

例5-1

$\mathrm{GF}\left(5\right)$ の演算表

2,3 は生成元

また、体の元を係数に持つ多項式は一意に因数分解ができます。 例えば、GF(2)の元として、0,1 のみの係数を持つ多項式は一意に因数分解 ができます。

一方、体で無い係数による多項式は因数分解が一意にならない場合がありま す。 例えば、 4 で割った余りという集合は体にならないが、これを係数として 許す多項式は因数分解が一意になりません。

誤り訂正符号の原理

送信したいデータを符号化する際に、 送受される符号の何ビットかが改変されても、受信側でそれを訂正して本来送 受されるデータに復元できるような符号方式を誤り訂正符号と呼びます。

最も単純な例として、送信データについて同じビットを3回ずつ送る符号方 式があります。つまり 0 を送りたいときは 000、1を送りたいときは 111 を送るというものです。 この時、3回中1回だけビットが誤っても、多数決を取れば、必ず正しいデー タが多いので、正しいデータを受け取ることが出来ます。 しかし、これだと、送信ビット数が元のデータの3倍になり、効率はよくありません。

さて、そこで、まず誤りを訂正できる符号の性質を考えます。 送受される符号において、１ビットの変更で別のデータに対応する符号になっ てしまう場合は、誤り訂正ができません。 従って、冗長なビットを付加して、1ビット程度の変更で相互に符号語になら ないようにする必要があります。 ２つのビット列について、ハミング距離とは異なるビット数を 言います。 これは一般の距離の定義である、次の条件を満たします。

1. xとxの距離は0である
2. xとyの距離と yとxの距離は等しい
3. xとyの距離とyとzの距離の和はxとzの距離以上になる

このハミング距離を用いると、誤り訂正符号は次のように定義できます。 誤り訂正符号では、すべての符号語はある一定のハミング距離を持ち、符号語 が一定のビット数の誤りがある場合、最もハミング距離の近い符号に訂正さ れます。

例5-2

1bitの情報(0か1)を送る誤り訂正符号として、0 の時は 00000, 1 の時は 11111 を符号語として送ることとします。 すると、この符号語同士のハミング距離は 5 となり、 2bit までの誤りを 訂正できます。 実際、 00001, 01010, 11000 はすべて 00000に訂正され、情報として0 が取 り出されます。 一方、00111, 10101, 11001 はすべて 11111 に訂正され、情報として 1 が取 り出されます。

1bit の誤り訂正能力を持つ誤り訂正符号は、すべての符号語のハミング距 離が 3 以上であれば良いことになります。 データが1bitなら、符号語長は3bit以上となり、伝送効率が1/3となります が、ある程度長いデータに対して、1bitの誤り訂正能力を考えれば、数ビッ トの付加により実現できるため、伝送効率を余り落とさずに実現できます。

組織線形ブロック符号

誤り訂正符号の構成法には行列を使う方法と有限体を使う方法がありますが、 今回は行列を使う方法を説明します。

送りたい情報を表すビット列を $\mathit{m}=\left(m_1,...,m_k\right)\in {\left\{0,1\right\}}^k$ で表します。 $\mathrm{GF}\left(2\right)$ 上の演算による行列演算を考えます。 $n$次元の $k$個の生成ベクトル ${\mathit{v}}_1,...,{\mathit{v}}_k$ に対して、符号語 $\mathit{u}$ は 生成行列$G$ により次のように表されます。

これを $\left(n,k\right)$符号 と呼び ます。

ここで、$G$が単位行列 $I_k$ を含むとし、残りをパリティ行列 $P$ と呼ぶ行列に分 解する。

ここで、パリティチェック行列 $H=\left(I_{n-k}|P^T\right)$ を定義すると次の性質を持つ。

ここで通信路にノイズ $\mathit{e}$ が乗って受信した符号 $\mathit{r}=\mathit{u}+\mathit{e}$ について、パリティチェック行列をかけると次のように、エラーに関する積（ シンドローム）だ け得られる。

リードソロモン符号

リードソロモン符号は有限体の多項式の性質を利用した誤り訂 正符号です。 $\mathrm{GF}\left(2^r\right)$ の元をシンボルと呼ぶことにします。 送りたい情報が $K$シンボル ($=rK$ ビット) で、送信時に訂正したいシンボル数を $t$ 個とした時、 $N=K+2t$ とした時、 $2^r>N$ が満たせれば符号を作ることが出来ます。

符号を作るには、 まず、 送りたい情報を $\mathrm{GF}\left(2^r\right)$ の係数を持つ $K-1$ 次の多項式で表したものを情報多項式 $I\left(x\right)$ とする。係数の列は $K$ 桁で、各 $r$ ビットで表せるので、全体 で $rK$ ビットになる。

$\mathrm{GF}\left(2^r\right)$ の原始元 $\alpha$ に対して、 ある適当な数 $b$ について 生成多項式 $G\left(x\right)$ を ${\alpha }^b,{\alpha }^{b-1},...,{\alpha }^{b+2t-1}$ までの $2t$ 個の元の根を持つ多項式とします。 つまり生成多項式は以下の式とします。

この時、送信する符号を表す多項式は次のようになります。

但し、 $P\left(x\right)$ は $C\left(x\right)$ が $G\left(x\right)$ で割り切れるように求めた補正項です。 具体的には $I\left(x\right)x^{2t}$ を $G\left(x\right)$ で割った余りになります。 （なお、係数は $\mathrm{GF}\left(2^r\right)$ の元なので、 $-P\left(x\right)$ と $+P\left(x\right)$ は同じになります。 ですので、 $+P\left(x\right)$ で書かれている文献が多い)

復号、誤り訂正などは、 $C\left(x\right)$ が誤りなしで送られた場合、 ${\alpha }^b,{\alpha }^{b+1},...,{\alpha }^{b+2t-1}$ の全てが解となる。 つまり以下が成り立ちます。

従って、この性質を用いて復号アルゴリズムが作られています。 詳細は省略します。