通信符号理論 02

通信符号理論 第２回 伊藤彰則 1

2 0と1だけからなる計算の体系 • 誤り訂正符号の理論では、0と1の系列（ベクトル）を 扱う • 例：系列 01001 は、5次元のベクトル (0,1,0,0,1) • 0と1の計算で理論を構築したい • 加減乗除が可能 • ベクトル空間の演算が可能（ベクトルと行列の演算）

3 代数的構造（代数系） • 集合と、その元に対する演算を組にしたもの • 同じ構造を持てば、対象が違うものであっても同じ計算ができ る •例 • 整数と加算（＋）は「群」 • 有理数と乗算（×）は０を除いて「群」 • 有理数と加算と乗算は「体」 • 複素数と加算と乗算は「体」

4 演算が１つの代数系 • 群(Group)とは、集合𝐺と二項演算∘について、 • 𝑎 ∈ 𝐺, 𝑏 ∈ 𝐺ならば 𝑎 ∘ 𝑏 ∈ 𝐺 （演算について閉じている） • 𝑎 ∘ 𝑏 ∘ 𝑐 = 𝑎 ∘ 𝑏 ∘ 𝑐 （結合則） • 𝑒 ∈ 𝐺が存在し、任意の𝑎 ∈ 𝐺について𝑎 ∘ 𝑒 = 𝑒 ∘ 𝑎 = 𝑎 （単位元） • 任意の𝑎 ∈ 𝐺について𝑏 ∈ 𝐺が存在し、𝑎 ∘ 𝑏 = 𝑏 ∘ 𝑎 = 𝑒 （逆元） • 交換則が成り立つ場合は「可換群」または「アーベル群」 • 𝑎∘𝑏 =𝑏∘𝑎

5 演算が１つの代数系 • マグマ (Magma)：集合と、閉じた二項演算の組 • 半群 (Semigroup)：演算が結合則を満たすマグマ • モノイド (Monoid)：単位元を持つ半群 • 群 (Group)：逆元を持つモノイド • 可換群 (Commutative group)：演算が交換則を満たす群

6 例 • 可換群：整数全体の集合と加算＋ • 群：正則行列全体の集合と行列積 • 単位元は単位行列、逆元は逆行列、可換でない • モノイド：文字列全体の集合と文字列連結 • 単位元は空文字列 “” • 結合則 (“ab”+”cd”)+”ef” = “ab”+(“cd”+”ef”) • 逆元はない • 半群：正の整数の集合と加算＋ • 単位元はなく、結合則を満たす

7 演算が2つの代数系 • 環 (Ring) • 集合と2つの演算（＋、×）を持つ • ＋に対して可換群 • ×に対してモノイド（逆元がなくてもよい） • 整数の四則演算など • 体 (Field) • 環である • ×が0以外の元に対して可換群（逆元を持つ） 減算は加算の逆演算、除算は乗算の逆演算として定義される

8 2元有限体 GF(2) • 有限体：有限集合に対する体 • 「整数全体」や「実数全体」は有限集合では ない • 集合の大きさ＝位数 • 位数p (pは素数)の有限体を GF(p) または Fp と表す • 加算・乗算は整数の加算・乗算結果を p で割った余りで定義する (mod p) • {0,1}からなる体：2元有限体 GF(2) + 0 1 0 0 1 1 1 0 × 0 1 0 0 0 1 0 1

9 有限体とガロア • エヴァリスト・ガロア (1811-1832) • フランスの数学者・革命家 • 群論などの業績が有名だが、生前は評価され ず • 政治活動に没頭し投獄される • 女性をめぐる決闘がもとで病死 • GFは Galois Field の略

10 GF(2)の特徴 • 加減乗除が可能 • GF(2)の行列とベクトル • 𝑧 = 𝑥 − 𝑦は、𝑧 + 𝑦 = 𝑥の解と して求まる • 1 + 1 = 0 より 0 − 1 = 1 • GF(2)の減算は加算と同じ 0 1 1 1 • 除算は = 0, = 1のみ • 数の総和は「パリティ」 • 足した数に1が偶数個含まれて いれば0、奇数個含まれていれ ば1 • 加減乗除が可能なので、整数や 実数と全く同じ扱い • スカラー倍は 「そのまま（×1）」か 「0にする（×0）」 • ベクトルの内積、行列積なども 全く同じ

11 ベクトルの一次独立性 （通常の定義） ベクトル𝒙, 𝒚が一次独立であるとは、スカラ𝑎, 𝑏に対して、 𝑎𝒙 + 𝑏𝒚 = 0 ⇔ 𝑎 = 𝑏 = 0 GF(2)でも基本的に同じ • スカラは0または1しかない ベクトル𝒙, 𝒚が一次独立であるとは、𝒙 ≠ 𝒚, 𝒙 ≠ 𝟎, 𝒚 ≠ 𝟎 • 「複数のベクトルが一次独立」＝ どのベクトルも0でなく、かつ、どのベクトルも 他のベクトルの和で表せない

12 2元線形符号 • 一次独立なn次元ベクトル 𝒗1 , … 𝒗𝑘 があるとき、 2元線形符号 𝐶 = {σ𝑘𝑖=1 𝑎𝑖 𝒗𝑖 , 𝑎𝑖 ∈ 𝐺𝐹 2 } • 符号長𝑛、符号語数2𝑘 、符号化率 𝑘Τ𝑛 •例 • 基底ベクトル 00111, 11100 • 符号𝐶 = {00000, 00111, 11100, 11011}

13 2元線形符号の性質 • 符号には必ず零ベクトルが含まれる • 𝒙 ∈ 𝐶, 𝒚 ∈ 𝐶のとき、𝒙 + 𝒚 ∈ 𝐶 • メッセージが 𝒎 = 𝑚1 , … , 𝑚𝑘 のとき、対応する符号は σ𝑘𝑖=1 𝑚𝑖 𝒗𝑖 • すべてのメッセージに対応する符号を記憶しておく必要はなく、 基底ベクトル𝒗1 , … , 𝒗𝑘 だけ記憶すればよい • 特定のメッセージに対応する符号は計算で求めることができる

14 符号化の行列演算による表現：生成行列 • メッセージベクトル 𝒎 = (𝑚1 , … , 𝑚𝑘 ) 𝒗1 • 生成行列 𝐺 = ⋮ 𝑘 × 𝑛行列 𝒗𝑘 • 符号 𝒙 = 𝒎𝐺 生成行列Gは線形符号を定義する

15 検査行列による線形符号の定義 • 𝑚 × 𝑛行列 𝐻 の各行が一次独立であるとする ⇒𝐶 = 𝒄 𝐻𝒄𝑇 = 0} は線形符号 •例 • 𝐻= 1 0 1 1 0 1 𝒙 𝐻𝒙𝑻 𝒙 𝐻𝒙𝑻 𝒙 𝐻𝒙𝑻 𝒙 𝐻𝒙𝑻 000 00 100 10 000 0 100 1 001 01 101 11 001 1 101 0 010 11 110 01 010 1 110 0 011 10 111 00 011 0 111 1 𝐻 = (1 1 1) 𝐶 = {000,111} 𝐶 = {000,011, 101, 110}

16 シンドローム 検査行列 𝐻 の線形符号において、受信語 𝒚 に対して 𝑇 𝒔 = 𝐻𝒚 をシンドロームと呼ぶ • 符号語のシンドロームは0ベクトル • シンドロームが0でない場合、誤りが含まれていることがわか る • 受信語と符号語一覧を逐一比較する必要がなく、行列演算1回ですむ

17 シンドロームと誤差ベクトル • 受信語は符号語のどこかの（0ビット以上の）ビットが反転し ている • 反転しているビットが1、それ以外が0のベクトル 𝒆 ：誤差ベクトル • 受信語を𝒚、元の符号語を 𝒙 とすれば、𝒚 = 𝒙 + 𝒆 • 𝑎 + 1は𝑎を反転することと同じ 𝑇 𝑇 𝑇 • 𝒔 = 𝐻𝒚 = 𝐻 𝒙 + 𝒆 = 𝐻𝒙 + 𝐻𝒆𝑇 = 𝐻𝒆𝑇 • シンドロームは元の符号の情報を含まず、誤りの情報だけを含 んでいる

18 最小距離と最小重み • 最小距離 𝑑 = min 𝑑ℎ (𝒂, 𝒃) , 𝒂, 𝒃 ∈ 𝐶 𝒂≠𝒃 • ハミング距離の性質 𝑑ℎ 𝒂, 𝒃 = 𝑑ℎ (𝒂 + 𝒙, 𝒃 + 𝒙) • したがって (*) • 𝑑 = 𝑑ℎ 𝒂, 𝒃 = 𝑑ℎ 𝒂 + 𝒃, 𝒃 + 𝒃 = 𝑑ℎ 𝒂 + 𝒃, 0 = 𝑤ℎ (𝒂 + 𝒃) • 線形符号の場合、最小距離dは、0を除くすべての符号語の中で最小の ハミング重み（符号語に含まれる1の個数が最も少ない符号語での1の 個数）に等しい ⇒あらゆる符号語２つの組み合わせを調べなくても、すべての符号語 を見ただけで最小距離がわかる • 例 𝐶 = 000,011,101,110 最小距離２

19 (*) 𝑑ℎ 𝒂, 𝒃 = 𝑑ℎ (𝒂 + 𝒙, 𝒃 + 𝒙)の証明 • ハミング距離の性質 • 長さ𝑛1 のベクトル𝒂1 , 𝒃1 と長さ𝑛2 のベクトル𝒂2 , 𝒃2 について 𝑑ℎ 𝒂1 , 𝒂2 , 𝒃1 , 𝒃2 = 𝑑ℎ 𝒂1 , 𝒃1 + 𝑑ℎ (𝒂2 , 𝒃2 ) • 𝒙の長さ𝑛に関する数学的帰納法 • 𝑛 = 1のとき • 𝒂 = 0, 𝒃 = 0 → 𝑑ℎ 0, 0 = 𝑑ℎ 0 + 0, 0 + 0 = 𝑑ℎ 0 + 1,0 + 1 = 0 • 𝒂 = 0, 𝒃 = 1 → 𝑑ℎ 0, 1 = 𝑑ℎ 0 + 0, 1 + 0 = 𝑑ℎ 0 + 1,1 + 1 = 1 • 𝒂 = 1, 𝒃 = 1 → 𝑑ℎ 1, 1 = 𝑑ℎ 1 + 0, 1 + 0 = 𝑑ℎ 1 + 1,1 + 1 = 0

20 (*)の証明 • 𝑛 = 𝑘のとき成立を仮定。 • 長さ𝑘 + 1のベクトル𝒂𝑘+1 = 𝒂𝑘 , 𝑎𝑘+1 , 𝒃𝑘+1 = 𝒃𝑘 , 𝑏𝑘+1 , 𝒙𝑘+1 = (𝒙𝑘 , 𝑥𝑘+1 ) と表現 • 𝑑ℎ 𝒂𝑘+1 + 𝒙𝑘+1 , 𝒃𝑘+1 + 𝒙𝑘+1 = 𝑑ℎ 𝒂𝑘 + 𝒙𝑘 , 𝒃𝑘 + 𝒙𝑘 + 𝑑ℎ 𝑎𝑘+1 + 𝑥𝑘+1 , 𝑏𝑘+1 + 𝑥𝑘+1 = 𝑑ℎ 𝒂𝑘 , 𝒃𝑘 + 𝑑ℎ 𝑎𝑘+1 , 𝑏𝑘+1 = 𝑑ℎ (𝒂𝑘+1 , 𝒃𝑘+1 )

21 線形符号の性質と最小距離 • 線形符号の符号長n、メッセージ長 k、最小距離 d を使い、 線形符号の性質を (n, k, d) と書く • これを見ればどのような長さでどのような性質の符号なのかわかる • 最小距離と誤り訂正能力 • 最小距離1の場合、訂正能力がない • どこかのビットが反転すると別な符号語になる • 最小距離2の場合、1ビット誤りが検出できる • 1ビット反転すると符号語ではなくなるので誤りは検出できるが、元の符号語は 一意に特定できない • 最小距離3の場合、1ビット誤りが訂正できる • 最小距離𝑑の場合、 𝑑−1 2 ビットまでの誤りが訂正できる

22 最小距離と訂正能力 距離3 • 𝐶 = 000,111 • 最小距離3、符号化率 1/3 • 𝑑ℎ 𝒄, 𝒚 = 𝑑0 ≤ 𝑑−1 2 のとき 000 距離2 001 010 100 距離1 距離1 011 101 110 距離2 111 𝒄′ ∈ 𝐶, 𝒄′ ≠ 𝒄について 𝑑ℎ 𝒄, 𝒄′ ≥ 𝑑 三角不等式より𝑑 ≤ 𝑑ℎ 𝒄, 𝒄′ ≤ 𝑑ℎ 𝒄, 𝒚 + 𝑑ℎ 𝒚, 𝒄′ 𝑑−1 したがって 𝑑 ≤ 𝑑0 + 𝑑ℎ 𝒚, 𝒄′ ≤ + 𝑑ℎ (𝒚, 𝒄′ ) 2 𝑑−1 𝑑− ≤ 𝑑ℎ (𝒚, 𝒄′) 2 距離3

23 最小距離と訂正能力 𝑑−1 𝑑− ≤ 𝑑ℎ (𝒚, 𝒄′) 2 𝑑−1 𝑑−1 𝑑+1 𝑑−1 𝑑−1 𝑑− ≥𝑑− = > ≥ 2 2 2 2 2 したがって 𝑑−1 𝑑−1 𝑑ℎ 𝒚, 𝒄 ≤ <𝑑− ≤ 𝑑ℎ (𝒚, 𝒄′ ) 2 2 以上より𝒚との距離が最小となる符号語は一意に定まる。

24 演習 1. 次の生成行列で表される符号の符号語をすべて列挙せよ。 また、符号長、メッセージ長、最小距離はいくらか。 1 0 0 1 1 0 𝐺= 0 1 0 0 1 1 0 0 1 1 1 1 2. 受信語が𝒚 = (1,1,0,0,1,0) であるとき、誤りを1ビット含んで いると仮定すると、元の符号語とメッセージは何か。