第 11 回誤り訂正符号

本日の内容

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

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

11-1. レポート課題

ワーク11-1

$GF (2)$ の演算表を作りなさい

ワーク11-2

$GF (2^{2})$ について

整数を4で割った余りは $GF (2^{2})$ にならないことを、演算表を作って、反例を見つけることで示しなさい。
$\{0, 1, a, b\}$ で、体になるように演算表を作り、 $a$ と $b$ の関係を求めなさい。
係数が $GF (2)$ (つまり 0,1 ) の多項式を $x^{2} + x + 1$ で割った余りを考えると、 $GF (2^{2})$ となることを演算表を作って示しなさい。

ワーク11-3

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

(\begin{matrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 \end{matrix})

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

締切、提出方法

12/4 火曜日の夕方までに <sakamoto@c.dendai.ac.jp>宛にグループで一通のレポートを作成し、メールすること。

11-2. 講義

有限体

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

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

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

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

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

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

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

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

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

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

例11-1

$GF (5)$ の演算表

\begin{matrix} + & 0 & 1 & 2 & 3 & 4 \\ 0 & 0 & 1 & 2 & 3 & 4 \\ 1 & 1 & 2 & 3 & 4 & 0 \\ 2 & 2 & 3 & 4 & 0 & 1 \\ 3 & 3 & 4 & 0 & 1 & 2 \\ 4 & 4 & 0 & 1 & 2 & 3 \end{matrix}

\begin{matrix} \cdot & 0 & 1 & 2 & 3 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 \\ 2 & 0 & 2 & 4 & 1 & 3 \\ 3 & 0 & 3 & 1 & 4 & 2 \\ 4 & 0 & 4 & 3 & 2 & 1 \end{matrix}

2,3 は生成元

誤り訂正符号

誤り訂正符号の原理

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

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

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

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

例11-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の誤り訂正能力を考えれば、数ビットの付加により実現できるため、伝送効率を余り落とさずに実現できます。

組織線形ブロック符号

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

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

u = m G = m (\begin{matrix} v_{1} \\ ⋮ \\ v_{k} \end{matrix}) = m_{1} v_{1} + ... + m_{k} v_{k}

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

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

G = (P | I_{k})

P = (\begin{matrix} p_{1, 1} & ... & p_{1, n - k} \\ ⋮ & ⋮ \\ p_{k, 1} & ... & p_{k, n - k} \end{matrix})

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

u H^{T} = m G H^{T} = (\begin{matrix} p_{1, 1} + p_{1, 1} & ... & p_{1, n - k} + p_{1, n - k} \\ ⋮ & ⋮ \\ p_{k, 1} + p_{k, 1} & ... & p_{k, n - k} + p_{k, n - k} \end{matrix}) = u 0 = 0

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

s = r H^{T} = u H^{T} + e H^{T} = e H^{T}

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 11 回 誤り訂正符号