次回予告 5/31： 講義30分 試験60分 本，ＰＣ等の持込み可 電卓の使用を推奨 May 31: lecture 30min test 60min you can bring books & PC use of a calculator recommended この後は... 前回の復習 練習問題の解答 今日の内容

前回の復習：線形符号と生成行列 線形符号：情報記号の線形式で検査記号を定義 符号語 ＝ 𝑥 1 , 𝑥 2 ,…, 𝑥 𝑘 , 𝑝 1 , 𝑝 2 ,…, 𝑝 𝑚 𝑝 𝑖 = 𝑎 𝑖,1 𝑥 1 + 𝑎 𝑖,2 𝑥 2 +⋯ +𝑎 𝑖,𝑘 𝑥 𝑘 ( 𝑎 𝑖,𝑗 =0 or 1) 生成行列：符号化のための便利な道具 生成行列 𝑥 1 ,… 𝑥 𝑘 , 𝑝 1 ,…, 𝑝 𝑚 = 𝑥 1 ,…, 𝑥 𝑘 1 ⋯ 0 𝑎 1,1 ⋯ 𝑎 𝑚,1 ⋮ ⋱ ⋮ ⋮ ⋱ ⋮ 0 ⋯ 1 𝑎 1,𝑘 ⋯ 𝑎 𝑚,𝑘 符号語 符号化したいデータ 𝑘×𝑘単位行列 検査記号定義式の 係数行列の転置

練習問題 情報記号( 𝑥 1 , 𝑥 2 , 𝑥 3 )に対し， とし，( 𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑝 1 , 𝑝 2 , 𝑝 3 )を符号語と定義する． この符号の生成行列を求めよ この符号の符号語をすべて列挙せよ p.32 のような符号化器を示せ 𝑝 1 = 𝑥 1 +𝑥 2 +𝑥 3 𝑝 2 = 𝑥 1 +𝑥 2 𝑝 3 = 𝑥 1 +𝑥 3

練習問題の解答例 符号語を列挙： 𝑥 1 , 𝑥 2 , 𝑥 3 = 0,0,0 ,…,(1,1,1)を𝐺に掛けると， 111 110 𝑝 1 = 𝑥 1 +𝑥 2 +𝑥 3 𝑝 2 = 𝑝 3 = 符号語を列挙： 𝑥 1 , 𝑥 2 , 𝑥 3 = 0,0,0 ,…,(1,1,1)を𝐺に掛けると， 111 110 101 係数行列 転置 100111 010110 001101 生成行列 𝐺 000000, 001101, 010110, 011011, 100111, 101010, 110001, 111100. 𝑥1 𝑥2 𝑥3 𝑝1 𝑝2 𝑝3

本日の講義内容 線形符号 定義と基本的な性質 線形符号の符号化 線形符号の復号 ハミング符号 線形符号の性能評価 線形符号 前回 今回

線形符号の復号 符号語 𝒖∈𝐶を送信 𝒗を受信 【誤り検出】 𝒗∈𝐶か否かを判定する 【誤り訂正】 𝒗に一番近い符号語 𝒖 ′ ∈𝐶を求める 通信路 アプリケーション 送信者 受信者 情報源符号化 符号化 復号 情報保護 暗号化 通信路符号化 符号語 𝒖∈𝐶を送信 𝒗を受信 【誤り検出】 𝒗∈𝐶か否かを判定する 【誤り訂正】 𝒗に一番近い符号語 𝒖 ′ ∈𝐶を求める

「復号」と生成行列 𝑥 1 𝑥 3 𝑥 2 𝑝 1 𝑥 4 𝑝 3 𝑝 2 𝑝 4 𝑝 5 復号...「どのように符号化されたか」が重要 水平垂直パリティ検査符号：( 𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 ,𝑝 1 , 𝑝 2 , 𝑝 3 , 𝑝 4 , 𝑝 5 ) 𝑥 1 𝑥 3 𝑥 2 𝑝 1 𝑥 4 𝑝 3 𝑝 2 𝑝 4 𝑝 5 𝑝 1 = 𝑥 1 +𝑥 2 𝑝 2 = 𝑥 3 +𝑥 4 𝑝 3 = +𝑥 3 𝑝 4 = 𝑥 2 𝑝 5 = 𝐺= 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1

符号語であるための条件（１） 符号化の計算： 受信系列 𝒗=( 𝑣 1 ,…, 𝑣 9 )が符号語... 𝑣 1 ,…, 𝑣 9 ∈𝐶 ( 𝑥 1 ,… 𝑥 4 , 𝑝 1 ,…, 𝑝 5 )=( 𝑥 1 ,…, 𝑥 4 ) 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 受信系列 𝒗=( 𝑣 1 ,…, 𝑣 9 )が符号語... 𝑣 1 ,…, 𝑣 9 ∈𝐶 𝑣 5 𝑣 1 +𝑣 2 𝑣 6 𝑣 3 +𝑣 4 𝑣 7 +𝑣 3 𝑣 8 𝑣 2 𝑣 9 = 必要十分条件

符号語であるための条件（２） 各左辺を右辺に移項すると．．． ２進演算：𝑥−𝑦=𝑥+𝑦 𝑣 1 ,…, 𝑣 9 ∈𝐶 パリティ検査方程式 𝑣 5 𝑣 1 +𝑣 2 −𝑣 5 − 𝑣 6 −𝑣 7 −𝑣 8 −𝑣 9 = 𝑣 1 +𝑣 2 𝑣 3 +𝑣 4 +𝑣 3 𝑣 2 = 𝑣 6 = 𝑣 3 +𝑣 4 𝑣 7 = 𝑣 1 +𝑣 3 𝑣 8 = 𝑣 2 +𝑣 4 𝑣 9 = 𝑣 1 +𝑣 2 +𝑣 3 +𝑣 4 ２進演算：𝑥−𝑦=𝑥+𝑦 𝑣 1 ,…, 𝑣 9 ∈𝐶 𝑣 1 +𝑣 2 +𝑣 5 = 𝑣 3 +𝑣 4 + 𝑣 6 = 𝑣 1 +𝑣 3 +𝑣 7 = 𝑣 2 +𝑣 4 +𝑣 8 = 𝑣 1 +𝑣 2 +𝑣 3 +𝑣 4 +𝑣 9 = パリティ検査方程式

符号語であるための条件（３） 𝑣 1 ,…, 𝑣 9 ∈𝐶 +𝑣 5 + 𝑣 6 +𝑣 7 +𝑣 8 +𝑣 9 = 𝑣 1 +𝑣 2 𝑣 3 𝑣 1 +𝑣 2 𝑣 3 +𝑣 4 +𝑣 3 𝑣 2 𝑣 1 ,…, 𝑣 9 ∈𝐶 1 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 1 𝑣 1 ⋮ ⋮ ⋮ ⋮ ⋮ 𝑣 9 = 0 0 0 0 0

検査行列 検査行列 𝐻 系列 𝒗 が符号語か否かを検査したいときは... 検査行列 𝐻 の右から，𝒗 の転置ベクトルを乗ずる 1 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 1 𝑣 1 ⋮ ⋮ ⋮ ⋮ ⋮ 𝑣 9 = 0 0 0 0 0 検査行列 𝐻 系列 𝒗 が符号語か否かを検査したいときは... 検査行列 𝐻 の右から，𝒗 の転置ベクトルを乗ずる 𝐻 𝒗 T =𝟎 ... 𝒗∈𝐶 𝐻 𝒗 T ≠𝟎 ... 𝒗∉𝐶 【誤り検出】

検査行列を用いた誤り検出 水平垂直パリティ検査符号 110101101 は符号語か？ yes 011011010 は符号語か？ no 1 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 1 = 0 0 0 0 0 1 1 0 1 0 1 1 0 1 yes 011011010 は符号語か？ 1 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 1 = 0 0 1 0 0 0 1 1 0 1 1 0 1 0 no

生成行列と検査行列 検査記号の定義式 生成行列 検査行列 k 行 n － k 行 単位行列 係数を転置した行列 係数行列 単位行列 p1 = a1,1x1 + a1,2x2 + ... + a1,kxk p2 = a2,1x1 + a2,2x2 + ... + a2,kxk : pm = am,1x1 + am,2x2 + ... + am,kxk a1,1x1 + a1,2x2 + ... + a1,kxk + p1 = 0 a2,1x1 + a2,2x2 + ... + a2,kxk + p2 = 0 : am,1x1 + am,2x2 + ... + am,kxk + pm = 0 生成行列 検査行列 k 行 n － k 行 単位行列 係数を転置した行列 係数行列 単位行列

生成行列と検査行列（実例） 𝑥 1 𝑥 3 𝑥 2 𝑝 1 𝑥 4 𝑝 3 𝑝 2 𝑝 4 𝑝 5 水平垂直パリティ検査符号： 𝑛=9, 𝑘=4, 𝑚=𝑛−𝑘=5 𝑥 1 𝑥 3 𝑥 2 𝑝 1 𝑥 4 𝑝 3 𝑝 2 𝑝 4 𝑝 5 𝑝 1 = 𝑥 1 +𝑥 2 𝑝 2 = 𝑥 3 +𝑥 4 𝑝 3 = +𝑥 3 𝑝 4 = 𝑥 2 𝑝 5 = 生成行列 検査行列

シンドローム 検査行列 𝐻, 系列 𝒗 に対し， 𝐻𝒗T=𝟎 ならば 𝒗∈𝐶 𝐻𝒗T≠𝟎 ならば 𝒗∉𝐶 𝒗 のシンドロームが 0 ならば 𝒗∈𝐶 𝒗 のシンドロームが 0 でなければ 𝒗∉𝐶 シンドロームには，誤りに関する情報が含まれている ⇒ シンドロームを使って，誤りを訂正することが可能

加法的通信路とシンドローム 2元対称通信路（BSC）に符号語 𝒖 を送信 誤りベクトル 𝒆 が発生し，符号語に対して加法的に作用 受信系列は 𝒗=𝒖+𝒆 誤りがない場合（𝒆＝0）， 受信系列 𝒗 のシンドロームは0 誤りがある場合（𝒆≠0）， 𝒗 のシンドロームは 0 以外 雑音源 𝒆 符号語 𝒖 受信系列 𝒗 = 𝒖 + 𝒆 受信系列 𝒗 のシンドロームは 𝐻𝒗T=𝐻(𝒖+𝒆)T=𝐻𝒖T + 𝐻𝒆T = 𝐻𝒆T シンドロームは送信符号語に依存せず，誤りのみに依存する シンドロームを見れば，どんな誤りが発生したかわかる

誤りパターンとシンドローム 000000000 を送信して 000100000 を受信した... 𝐻= 1 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 1 000000000 を送信して 000100000 を受信した... 𝐻 0 0 0 1 0 0 0 0 0 T=(0 1 0 1 1)T. 110000110 を送信して 110100110 を受信した... 𝐻 1 1 0 1 0 0 1 1 0 T=(0 1 0 1 1)T. 送信符号語に依存していない ⇒　シンドロームが (0 1 0 1 1) ならば，受信語の4ビット目が誤り

シンドロームを利用した誤り訂正 誤りパターンとシンドロームの対応がわかっていれば， 受信系列のシンドロームから誤りパターンを推測可能． 誤りパターンを受信系列から引く（足す）ことで， 送信符号語を特定可能 （誤りの影響を打消す）． 【誤り訂正】 受信系列 シンドローム シンドローム計算 𝒗 = 𝒖 + 𝒆 𝒔 𝒔 = 𝐻𝒗T 誤り / シンドローム対応表 誤りパターン ..... ..... 𝒆 ..... ..... ..... ..... 復号結果 𝒖

１ビット誤りパターンとシンドローム 検査行列 𝐻の第 𝑖 列目の列ベクトルを𝒉𝑖と書く： 𝐻=( 𝒉 𝟏 𝒉 𝟐 ⋯ 𝒉 𝒏 ) 𝑖 ^ 𝐻=( 𝒉 𝟏 𝒉 𝟐 ⋯ 𝒉 𝒏 ) 𝑖 ^ 誤りベクトルが 𝒆=(0,…,0,1,0,…,0) のときのシンドロームは 𝐻 𝑒 T = 𝒉 𝟏 𝒉 𝟐 ⋯ 𝒉 𝒏 ⋮ 0 1 0 ⋮ = 𝒉 𝒊 第 𝑖 ビット目だけに誤りが発生 ⇔　シンドロームは，検査行列の第 𝑖 列ベクトルと等しい 　　（わざわざ対応表を作らなくてもOK）

シンドロームを使った誤り訂正 水平垂直パリティ検査符号 符号語 検査行列 000000000, 000101011, 001001101, 001100110, 010010011, 010111000, 011011110, 011110101, 100010101, 100111110, 101011000, 101110011, 110000110, 110101101, 111001011, 111100000. 検査行列 𝐻= 1 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 1 受信系列が 101001000 のとき， ⇒　シンドロームは H(1 0 1 0 0 1 0 0 0)T = (1 0 0 0 0)T ⇒　H の５列目と等しい ⇒　５ビット目が誤り，送信符号語は 101011000 受信系列が 101100110 のとき， ⇒　シンドロームは H(1 0 1 1 0 0 1 1 0)T = (1 0 1 0 1)T ⇒　H の１列目と等しい ⇒　１ビット目が誤り，送信符号語は 001100110

ここまでのまとめ：復号と検査行列 検査行列：シンドローム計算のための道具 シンドロームが0なら誤りなし 0以外なら，そのシンドロームから誤り位置を特定可能 線形符号では，符号化も，復号も，行列演算で実現可能

検査行列と符号の能力 第 𝑖 ビット目に誤りが発生 ⇔ シンドローム＝検査行列の第 𝑖列ベクトル ⇔　シンドローム＝検査行列の第 𝑖列ベクトル 検査行列が同一の列ベクトルを複数含んでいると... ⇒　複数の１ビット誤りに対し，同一シンドロームが得られる ⇒　シンドロームからは，誤り位置の特定ができない 誤り訂正能力なし 偶パリティ符号 𝑝= 𝑥 1 + 𝑥 2 𝐻=(1 1 1) 情報記号 (x1, x2, x3) に対し， p1 = x1 + x2 p2 = x2 + x3 𝐻= 1 1 0 1 0 0 1 1 0 1

誤り訂正符号の設計方針 符号語中の１ビット誤りを訂正可能な符号を構成したい 「列ベクトルが全て異なる検査行列」を持つ符号を作れば良い 良い例： 101100 110010 011001 H= 1010011 0100111 1101001 H= 101001 010011 110100 010101 H= 悪い例： 110100 101010 010001 H= 1010011 1100111 1101001 H= （簡単のため，検査行列の 右部分行列は単位行列とする） 𝐶= 𝒗 𝐻𝒗T=𝟎}

符号の構成例 係数行列 H= G= 101 100 110 010 011 001 101 110 011 100 110 010 011 001 101 左部分 転置 p1 = x1 + x3 p2 = x1 + x2 p3 = x2 + x3 000000, 001101, 010011, 011110, 100110, 101011, 110101, 111000. 符号語

検査行列の大きさと符号の効率 検査行列が 𝑚 行 𝑛 列 ⇒ 構成される符号は，符号長 𝑛, 情報記号数 𝑘=𝑛−𝑚, 検査記号数 𝑚. ⇒　構成される符号は，符号長 𝑛, 情報記号数 𝑘=𝑛−𝑚, 検査記号数 𝑚. 水平垂直パリティ検査符号 𝑛=9 𝑚=5 符号長 9, 情報記号数 4. 1 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 1 検査行列が縦に長いと，符号語の中の検査記号数が多くなる ⇒　符号語の中の情報記号数が少なくなる ⇒　符号の効率は悪い

ハミング符号 効率の良い１ビット誤り訂正可能な符号 ⇒ できるだけ「横長」な検査行列を作れば良い ハミング符号 （Hamming Code） ⇒　できるだけ「横長」な検査行列を作れば良い Richard Hamming 1915-1998 1)　検査記号数 𝑚 を決定 2)　長さ 𝑚 の非零ベクトルを全て列挙 3) 列挙したベクトルを，検査行列の列ベクトルに （右部分行列が単位行列になるようにする） ハミング符号 （Hamming Code） 𝑚 = 3 の場合， 符号長（列数） 7, 検査記号数（行数） 3, 情報記号数 7 – 3 = 4

ハミング符号のパラメータ ハミング符号： 検査行列は，𝑚個の行ベクトルを持つ 検査行列は，2𝑚 – 1個の列ベクトルを持つ 3 4 5 6 7 𝑛 15 31 63 127 𝑘 1 11 26 57 120 符号長 𝑛=2𝑚−1 検査記号数 𝑚 情報記号数 𝑘=𝑛−𝑚=2𝑚−1−𝑚

ハミング符号の性能 ビット誤り率 𝑝 の BSC上で，4ビット情報を送受信 情報が正しく伝わる確率を評価 符号化を行わない... 1−𝑝 4 符号化を行わない... 1−𝑝 4 𝑛=7, 𝑘=4のハミング符号を使用 ... 1−𝑝 7 +7 1−𝑝 6 𝑝 ハミング符号 符号化なし 𝑝

どうして，誤りを訂正できるのか？ 検査行列とは異なる視点から，誤り訂正のメカニズムを考える 「符号語 𝒖 を送信したところ，誤りが発生し，系列 𝒗 を受信した」 符号語 𝒖 𝒗 が符号語でないならば，誤りを検出できる 𝒗に一番近い符号語が 𝒖 ならば，誤りを訂正できる 受信系列 𝒗 符号語と符号語のあいだの「距離」が重要 ... できるだけ離れていることが望ましい 他の符号語 𝒖′

ハミング距離 dH(0100,1101) = 2 𝒂=(𝑎1, 𝑎2,…, 𝑎𝑛), 𝒃=(𝑏1, 𝑏2,…, 𝑏𝑛) ...同じ長さの系列 𝒂 と 𝒃のハミング距離 𝑑𝐻(𝒂, 𝒃) ： 系列中で異なる記号の個数 dH(0100,1101) = 2 dH(000, 011) = 2 dH(000, 111) = 3 dH(010, 110) = 1 dH(011, 011) = 0 符号語 𝒖=01011 受信系列 𝒗=01001 1ビットの誤り発生 ⇒ 送信符号語と受信系列の ハミング距離は 1

最小ハミング距離 符号 C の最小ハミング距離 𝑑 min = min 𝒂,𝒃∈𝐶,𝒂≠𝒃 𝑑 𝐻 (𝒂,𝒃) 定理：ハミング符号の最小ハミング距離は3である（証明略） どの符号語の間も，3以上離れている 「𝒖∈𝑪から１ビットだけ誤って得られる系列」と， 「𝒗∈𝑪から１ビットだけ誤って得られる系列」を区別可能 誤り 符号語 𝒖 符号語 𝒗 ⇒ だから，1ビット誤りを訂正できる

一般的な線形符号 ハミング符号は，線形符号の作り方の1つに過ぎない 「最小ハミング距離 > 3」の符号も存在 最小ハミング距離が 𝑑 min ⇒ 𝑡 max = 𝑑 min −1 2 ビットまでの誤りを訂正可能 dmin=7, tmax=3 tmax tmax 詳しくは III 期の「符号理論」で

まとめ 線形符号... 取扱いに優れた通信路符号化方式 生成行列による符号化 検査行列による誤り検出・訂正 ハミング符号 最小ハミング距離は 3 1ビット誤り訂正可能な線形符号

練習問題 𝑛=15, 𝑘=11のハミング符号の検査行列，生成行列を作れ 上記の符号に対し，p.27 のように，性能を評価せよ 5/31： 講義30分 試験60分 本，ＰＣ等の持込み可 電卓の使用を推奨 May 31: lecture 30min test 60min you can bring books & PC use of a calculator recommended