次回予告 6/2 June 2 lecture 30min 講義30分 test 60min 試験60分 you can bring books & PC 本，ＰＣ等の持込み可 use of a calculator recommended 電卓の使用を推奨 この後は... 前回の復習 練習問題の解答 今日の内容 0 前回の復習：線形符号と生成行列 線形符号：情報記号の線形式で検査記号を定義 符号語 ＝ 𝑥1 , 𝑥2 , … , 𝑥𝑘 , 𝑝1 , 𝑝2 , … , 𝑝𝑚 𝑝𝑖 = 𝑎𝑖,1 𝑥1 + 𝑎𝑖,2 𝑥2 + ⋯ +𝑎𝑖,𝑘 𝑥𝑘 (𝑎𝑖,𝑗 = 0 or 1) 生成行列：符号化のための便利な道具 𝑥1 , … 𝑥𝑘 , 𝑝1 , … , 𝑝𝑚 1 ⋯ 0 𝑎1,1 符号語 ⋮ = 𝑥1 , … , 𝑥𝑘 ⋮ ⋱ ⋮ 0 ⋯ 1 𝑎1,𝑘 符号化したいデータ 𝑘 × 𝑘単位行列 生成行列 ⋯ 𝑎𝑚,1 ⋱ ⋮ ⋯ 𝑎𝑚,𝑘 検査記号定義式の 係数行列の転置 1 練習問題 情報記号(𝑥1 , 𝑥2 , 𝑥3 )に対し， 𝑝1 = 𝑥1 +𝑥2 +𝑥3 𝑝2 = 𝑥1 +𝑥2 𝑝3 = 𝑥1 +𝑥3 とし，(𝑥1 , 𝑥2 , 𝑥3 , 𝑝1 , 𝑝2 , 𝑝3 )を符号語と定義する． この符号の生成行列を求めよ この符号の符号語をすべて列挙せよ p.31 のような符号化器を示せ 2 練習問題の解答例 𝑝1 = 𝑥1 +𝑥2 +𝑥3 𝑝2 = 𝑥1 +𝑥2 𝑝3 = 𝑥1 +𝑥3 係数行列 転置 生成行列 𝐺 111 110 101 111 110 101 100111 010110 001101 符号語を列挙： 𝑥1 , 𝑥2 , 𝑥3 = 0,0,0 , … , (1,1,1)を𝐺に掛けると， 000000, 001101, 010110, 011011, 100111, 101010, 110001, 111100. 𝑥1 𝑥2 𝑥3 𝑥1 𝑥2 𝑥3 𝑝1 𝑝2 𝑝3 3 本日の講義内容 線形符号 定義と基本的な性質 線形符号の符号化 線形符号の復号 ハミング符号 線形符号の性能評価 前回 今回 4 線形符号の復号 アプリケーション 送信者 受信者 情報源符号化 符号化 復号 情報保護 暗号化 復号 通信路符号化 符号化 復号 符号語 𝒖 ∈ 𝐶を送信 通信路 𝒗を受信 【誤り検出】 𝒗 ∈ 𝐶か否かを判定する 【誤り訂正】 𝒗に一番近い符号語 𝒖′ ∈ 𝐶を求める 5 「復号」と生成行列 復号...「どのように符号化されたか」が重要 水平垂直パリティ検査符号：(𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑝1 , 𝑝2 , 𝑝3 , 𝑝4 , 𝑝5 ) 𝑥1 𝑝1 = 𝑥1 +𝑥2 𝑝2 = 𝑥3 +𝑥4 𝑝3 = 𝑥1 +𝑥3 𝑝4 = 𝑥2 +𝑥4 𝑝5 = 𝑥1 +𝑥2 +𝑥3 +𝑥4 𝑥2 𝑝1 𝑥3 𝑥4 𝑝2 𝑝3 𝑝4 𝑝5 𝐺= 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 6 符号語であるための条件（１） 符号化の計算： 1 0 (𝑥1 , … 𝑥4 , 𝑝1 , … , 𝑝5 ) = (𝑥1 , … , 𝑥4 ) 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 受信系列 𝒗 = (𝑣1 , … , 𝑣9 )が符号語... 𝑣1 , … , 𝑣9 ∈ 𝐶 𝑣5 = 𝑣1 +𝑣2 𝑣6 = 𝑣3+𝑣4 𝑣7 = 𝑣1 +𝑣3 𝑣2 +𝑣4 必要十分条件 𝑣8 = 𝑣9 = 𝑣1 +𝑣2+𝑣3 +𝑣4 7 符号語であるための条件（２） 各左辺を右辺に移項すると．．． 𝑣5 = 𝑣1 +𝑣2 𝑣6 = 𝑣3+𝑣4 𝑣7 = 𝑣1 +𝑣3 𝑣8 = 𝑣2 +𝑣4 𝑣9 = 𝑣1 +𝑣2+𝑣3 +𝑣4 −𝑣5 =0 −𝑣6 𝑣3+𝑣4 =0 −𝑣7 𝑣1 +𝑣3 =0 −𝑣8 =0 𝑣2 +𝑣4 −𝑣9 = 0 𝑣1 +𝑣2+𝑣3 +𝑣4 𝑣1 +𝑣2 ２進演算：𝑥 − 𝑦 = 𝑥 + 𝑦 𝑣1 , … , 𝑣9 ∈ 𝐶 +𝑣5 =0 +𝑣6 𝑣3+𝑣4 =0 +𝑣7 𝑣1 +𝑣3 =0 +𝑣8 =0 𝑣2 +𝑣4 +𝑣9 = 0 𝑣1 +𝑣2+𝑣3 +𝑣4 𝑣1 +𝑣2 パリティ検査方程式 8 符号語であるための条件（３） +𝑣5 =0 +𝑣6 𝑣3+𝑣4 =0 +𝑣7 𝑣1 +𝑣3 =0 +𝑣8 =0 𝑣2 +𝑣4 +𝑣9 = 0 𝑣1 +𝑣2+𝑣3 +𝑣4 𝑣1 +𝑣2 𝑣1 , … , 𝑣9 ∈ 𝐶 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 𝑣1 ⋮ = 𝑣9 0 0 0 0 0 9 検査行列 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 𝑣1 ⋮ = 𝑣9 0 0 0 0 0 検査行列 𝐻 系列 𝒗 が符号語か否かを検査したいときは... 検査行列 𝐻 の右から，𝒗 の転置ベクトルを乗ずる 𝐻𝒗T = 𝟎 ... 𝒗 ∈ 𝐶 【誤り検出】 T 𝐻𝒗 ≠ 𝟎 ... 𝒗 ∉ 𝐶 10 検査行列を用いた誤り検出 水平垂直パリティ検査符号 • 110101101 は符号語か？ yes 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 1 1 0 1T 0 0 0 0 1 • 011011010 は符号語か？ no 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0T 1 0 0 0 1 11 生成行列と検査行列 検査記号の定義式 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 a2,1x1 + a2,2x2 + ... + a2,kxk + p2 : am,1x1 + am,2x2 + ... + am,kxk 生成行列 0 0 a1,1 a2,1 am,1 1 0 a1,2 a2,2 am,2 0 1 a1,k a2,k am,k + pm = 0 検査行列 n－k行 k行 1 0 0 =0 =0 単位行列 係数を転置した行列 a1,1 a2,1 a m,1 a1,2 a1,k a 2, 2 a 2, k am, 2 am, k 係数行列 1 0 0 0 1 0 0 0 1 単位行列 12 生成行列と検査行列（実例） 水平垂直パリティ検査符号： 𝑛 = 9, 𝑘 = 4, 𝑚 = 𝑛 − 𝑘 = 5 𝑥1 𝑥2 𝑝1 𝑝1 = 𝑥1 +𝑥2 𝑝2 = 𝑥3 +𝑥4 𝑝3 = 𝑥1 +𝑥3 𝑝4 = 𝑥2 +𝑥4 𝑝5 = 𝑥1 +𝑥2 +𝑥3 +𝑥4 𝑥3 𝑥4 𝑝2 𝑝3 𝑝4 𝑝5 生成行列 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 検査行列 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 13 シンドローム 検査行列 𝐻, 系列 𝒗 に対し， 𝐻𝒗T = 𝟎 ならば 𝒗 ∈ 𝐶 𝐻𝒗T ≠ 𝟎 ならば 𝒗 ∉ 𝐶 𝐻𝒗T を，系列 𝒗 のシンドロームと呼ぶ 𝒗 のシンドロームが 0 ならば 𝒗 ∈ 𝐶 𝒗 のシンドロームが 0 でなければ 𝒗 ∉ 𝐶 シンドロームには，誤りに関する情報が含まれている ⇒ シンドロームを使って，誤りを訂正することが可能 14 加法的通信路とシンドローム 2元対称通信路（BSC）に符号語 𝒖 を送信 誤りベクトル 𝒆 が発生し，符号語に対して加法的に作用 受信系列は 𝒗 = 𝒖 + 𝒆 誤りがない場合（𝒆＝0）， 雑音源 受信系列 𝒗 のシンドロームは0 符号語 𝒖 𝒆 受信系列 𝒗 = 𝒖 + 𝒆 誤りがある場合（𝒆 ≠ 0）， 𝒗 のシンドロームは 0 以外 受信系列 𝒗 のシンドロームは 𝐻𝒗T = 𝐻(𝒖 + 𝒆)T = 𝐻𝒖T + 𝐻𝒆T = 𝐻𝒆T シンドロームは送信符号語に依存せず，誤りのみに依存する シンドロームを見れば，どんな誤りが発生したかわかる 15 誤りパターンとシンドローム 𝐻= 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 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ビット目が誤り 16 シンドロームを利用した誤り訂正 誤りパターンとシンドロームの対応がわかっていれば， 受信系列のシンドロームから誤りパターンを推測可能． 誤りパターンを受信系列から引く（足す）ことで， 送信符号語を特定可能 （誤りの影響を打消す）． 受信系列 𝒗 = 𝒖 + 𝒆 シンドローム計算 𝒔 = 𝐻𝒗T 誤りパターン 𝒆 復号結果 𝒖 【誤り訂正】 シンドローム 𝒔 誤り / シンドローム対応表 ..... ..... ..... ..... ..... ..... 17 １ビット誤りパターンとシンドローム 検査行列 𝐻の第 𝑖 列目の列ベクトルを𝒉𝑖 と書く： 𝐻 = (𝒉𝟏 𝒉𝟐 ⋯ 𝒉𝒏 ) 𝑖 誤りベクトルが 𝒆 = (0, … , 0,1,0, … , 0) のときのシンドロームは ⋮ 0 T 𝐻𝑒 = 𝒉𝟏 𝒉𝟐 ⋯ 𝒉𝒏 1 = 𝒉𝒊 0 ⋮ ^ 第 𝑖 ビット目だけに誤りが発生 ⇔ シンドロームは，検査行列の第 𝑖 列ベクトルと等しい （わざわざ対応表を作らなくてもOK） 18 シンドロームを使った誤り訂正 水平垂直パリティ検査符号 符号語 000000000, 100010101, 検査行列 1 1 0 0 1 0 0 0 0 𝐻= 0 1 0 1 0 0 1 1 1 1 0 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 000101011, 100111110, 001001101, 101011000, 001100110, 101110011, 010010011, 110000110, 010111000, 110101101, 011011110, 111001011, 011110101, 111100000. • 受信系列が 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 19 ここまでのまとめ：復号と検査行列 検査行列：シンドローム計算のための道具 シンドロームが0なら誤りなし 0以外なら，そのシンドロームから誤り位置を特定可能 線形符号では，符号化も，復号も，行列演算で実現可能 20 検査行列と符号の能力 第 𝑖 ビット目に誤りが発生 ⇔ シンドローム＝検査行列の第 𝑖列ベクトル 検査行列が同一の列ベクトルを複数含んでいると... ⇒ 複数の１ビット誤りに対し，同一シンドロームが得られる ⇒ シンドロームからは，誤り位置の特定ができない 偶パリティ符号 𝑝 = 𝑥1 + 𝑥2 𝐻 = (1 1 1) 情報記号 (x1, x2, x3) に対し， 11010 p1 = x 1 + x 2 𝐻= 01101 p2 = x2 + x3 誤 り 訂 正 能 力 な し 21 誤り訂正符号の設計方針 符号語中の１ビット誤りを訂正可能な符号を構成したい 「列ベクトルが全て異なる検査行列」を持つ符号を作れば良い 良い例： H= 101100 110010 011001 H= 1010011 0100111 1101001 悪い例： H= 110100 101010 010001 H= 1010011 1100111 1101001 𝐶 = 𝒗 𝐻𝒗T = 𝟎} H= 101001 010011 110100 010101 （簡単のため，検査行列の 右部分行列は単位行列とする） 22 符号の構成例 係数行列 H= 101 100 101 110 010 110 転置 011 001 左部分 011 p1 = x 1 + x3 p2 = x 1 + x 2 p3 = x2 + x3 G= 100 110 010 011 001 101 000000, 001101, 010011, 011110, 100110, 101011, 110101, 111000. 符号語 23 検査行列の大きさと符号の効率 検査行列が 𝑚 行 𝑛 列 ⇒ 構成される符号は，符号長 𝑛, 情報記号数 𝑘 = 𝑛 − 𝑚, 検査記号数 𝑚. 符号長 9, 情報記号数 4. 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 𝑚=5 水平垂直パリティ検査符号 1 0 1 0 1 𝑛=9 検査行列が縦に長いと，符号語の中の検査記号数が多くなる ⇒ 符号語の中の情報記号数が少なくなる ⇒ 符号の効率は悪い 24 ハミング符号 効率の良い１ビット誤り訂正可能な符号 ⇒ できるだけ「横長」な検査行列を作れば良い Richard Hamming ハミング符号 （Hamming Code） 1915-1998 1) 検査記号数 𝑚 を決定 2) 長さ 𝑚 の非零ベクトルを全て列挙 3) 列挙したベクトルを，検査行列の列ベクトルに （右部分行列が単位行列になるようにする） 1 1 1 1 0 1 0 0 0 𝑚 = 3 の場合， H 1 1 0 1 0 1 0 , G 0 1 0 1 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0 1 1 符号長（列数） 7, 検査記号数（行数） 3, 情報記号数 7 – 3 = 4 25 ハミング符号のパラメータ ハミング符号： 検査行列は，𝑚個の行ベクトルを持つ 検査行列は，2𝑚 – 1個の列ベクトルを持つ 符号長 検査記号数 情報記号数 2𝑚 𝑛= −1 𝑚 𝑘 = 𝑛 − 𝑚 = 2𝑚 − 1 − 𝑚 𝑚 2 3 4 5 6 7 𝑛 3 7 15 31 63 127 𝑘 1 4 11 26 57 120 26 ハミング符号の性能 ビット誤り率 𝑝 の BSC上で，4ビット情報を送受信 情報が正しく伝わる確率を評価 符号化を行わない... 1 − 𝑝 4 𝑛 = 7, 𝑘 = 4のハミング符号を使用 ... 1 − 𝑝 7 + 7 1 − 𝑝 6𝑝 1 0.8 ハミング符号 0.6 0.4 符号化なし 0.2 𝑝 0 0 0.1 0.2 0.3 0.4 0.5 27 どうして，誤りを訂正できるのか？ 検査行列とは異なる視点から，誤り訂正のメカニズムを考える 「符号語 𝒖 を送信したところ，誤りが発生し，系列 𝒗 を受信した」 符号語 𝒖 𝒗 が符号語でないならば，誤りを検出できる 𝒗に一番近い符号語が 𝒖 ならば，誤りを訂正できる 受信系列 𝒗 他の符号語 𝒖′ 符号語と符号語のあいだの「距離」が重要 ... できるだけ離れていることが望ましい 28 ハミング距離 𝒂 = (𝑎1, 𝑎2, … , 𝑎𝑛), 𝒃 = (𝑏1, 𝑏2, … , 𝑏𝑛) ...同じ長さの系列 𝒂 と 𝒃のハミング距離 𝑑𝐻 (𝒂, 𝒃) ： 系列中で異なる記号の個数 dH(0100,1101) = 2 dH(000, 011) = 2 dH(010, 110) = 1 dH(000, 111) = 3 dH(011, 011) = 0 符号語 𝒖 = 01011 受信系列 𝒗 = 01001 1ビットの誤り発生 ⇒ 送信符号語と受信系列の ハミング距離は 1 29 最小ハミング距離 符号 C の最小ハミング距離 𝑑min = min 𝒂,𝒃∈𝐶,𝒂≠𝒃 𝑑𝐻 (𝒂, 𝒃) 定理：ハミング符号の最小ハミング距離は3である（証明略） どの符号語の間も，3以上離れている 「𝒖 ∈ 𝑪から１ビットだけ誤って得られる系列」と， 「𝒗 ∈ 𝑪から１ビットだけ誤って得られる系列」を区別可能 符号語 𝒗 符号語 𝒖 誤り 誤り ⇒ だから，1ビット誤りを訂正できる 30 一般的な線形符号 ハミング符号は，線形符号の作り方の1つに過ぎない 「最小ハミング距離 > 3」の符号も存在 最小ハミング距離が 𝑑min ⇒𝑡max = 𝑑min −1 2 ビットまでの誤りを訂正可能 dmin=7, tmax=3 tmax tmax 詳しくは III 期の「符号理論」で 31 まとめ 線形符号... 取扱いに優れた通信路符号化方式 生成行列による符号化 検査行列による誤り検出・訂正 ハミング符号 最小ハミング距離は 3 1ビット誤り訂正可能な線形符号 32 練習問題 𝑛 = 15, 𝑘 = 11のハミング符号の検査行列，生成行列を作れ 上記の符号に対し，p.27 のように，性能を評価せよ 6/2 June 2 lecture 30min 講義30分 test 60min 試験60分 you can bring books & PC 本，ＰＣ等の持込み可 use of a calculator recommended 電卓の使用を推奨 33
© Copyright 2024 ExpyDoc
