第０５章 「誤り訂正の効果その1： 誤り訂正符号化を用いる伝送系 代数的復号法を用いるときの誤り率」 誤り訂正符号化を用いる伝送系 代数的復号法による訂正能力 代数的復号法による復号後のビット誤 り率 2014/12/3 安達：コミュニケーション符号理論 1 2014/12/3 安達：コミュニケーション符号理論 伝送システム 情報伝送速度と帯域幅 送信側 符号化率 情報源から出た2値情報系列を符号化 ディジタル変調波に変換して伝送 kビットの情報をnビットの符号語に符号化するときの符号化率 R=k/n (<1) 受信側 帯域幅 ディジタル変調波を復調して2値系列に変換 送信された情報ビット系列に復号 情報伝送速度を同じにするなら，帯域幅は1/R (>1)倍に拡大さ Tb れる． X ( x0 x1 xk 1 ) W ( w0 w1 wn k 1wn k wn 1 ) (c0c1 cn k 1 x0 x1 xk 1 ) R ( r r r 0 1 n k 1rn k rn 1 ) ˆ X ( xˆ0 xˆ1 xˆk 1 ) 通信路 ディジタル 符号器 変調器 情報源 X 2014/12/3 W 通信路 2 ディジタル 通信路 復号器 復調器 R 符号化前 情報ビット ハミング 情報 (7,4)符号 ビット 検査 ビット 帯域幅を同じにするなら，情報伝送速度はR (<1)倍に低下する． 時間 Tb 受け取り 手 符号化前 情報ビット ハミング (7,4)符号 情報ビット ˆ X 安達：コミュニケーション符号理論 時間 3 2014/12/3 検査 ビット 安達：コミュニケーション符号理論 4 最小ハミング距離 1つの符号語Wのハミング重みはその符号語の0でない 要素の数として定義される． 2つの符号語WiとWjとの間のハミング距離は，WiWjの ハミング重みで与えられるが， WiとWjとが線形符号の符 号語なら，これらの符号語は符号空間を構成するから， WiWjもまた，符号語になる． つまり，2つの符号語間のハミング距離は，第3の符号語 のハミング重みに等しい． 従って，線形符号の最小距離は，その線形符号の全て の要素が0の符号語を除く符号語の最小のハミング重み に等しい． 代数的復号法による 訂正能力 2014/12/3 安達：コミュニケーション符号理論 5 2014/12/3 安達：コミュニケーション符号理論 誤り検出 6 誤り訂正 符号語間の最小ハミング距離をdminとする． dmin1個の誤りによって1つの符号語が他の符号語に変 わることがないから，誤りがあったと検出できる． 各符号語を中心として半径t1の球をつくると， d min 2t1 1 であれば球は重複しない．すなわちt1以下の誤りを訂正 できる． t1の最大値はこの符号の誤り訂正能力といわれ， t (d min 1) / 2 dmin-1 である． dmin t1 dmin=2t+1 今井，情報理論，昭晃堂，1984年 2014/12/3 安達：コミュニケーション符号理論 7 2014/12/3 安達：コミュニケーション符号理論 8 ハミング(n,k)符号語 ハミング(7,4)符号 符号語長はn=7ビットであるので全部で2n=128種類の系 列がある．このうち符号語となり得るのは，情報がk=4ビッ ト長であるから2k=16個． 最小ハミング距離はdmin=3であるから，1ビット訂正ができ る． 符号長n，検査ビット長m=nk m個の検査ビットで表せる系列の個数は，全零を除いて 2m1個である（つまり，検査行列の列の数は2m1個であ る．すべての列が違わなければならないからである）． これがnビット符号語に単一誤りが発生する場合の数nに ハミング(7,4)符号の検査ビット 等しくなければならない． 1 0 0 1 0 1 1 従って H 0 1 0 1 1 1 0 符号語長： n=2m1 情報ビット数： k=n-m=2m1m 単一誤り訂正： t=1 W XG ここで 1 0 G 1 1 0 0 1 0 1 1 1 受信した検査 情 報 (k=4 ビ ッ ト ) ビ ッ ト を 表 す から検査ビットの 生成 (m=3ビット) シンドローム s0 S s1 HR T HET s 2 2014/12/3 安達：コミュニケーション符号理論 9 2014/12/3 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 検査ビット 岩垂：符号理論入門， 情報ビット(k=4ビット) (m=3ビット) 昭晃堂，1992年 を表す の生成 10 安達：コミュニケーション符号理論 シンドローム ハミング(7,4)符号 2014/12/3 c0 c1 c2 x0 x1 x2 x3 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 シンドローム 1 0 0 1 0 1 1 s0 T T S s1 HR HE , H 0 1 0 1 1 1 0 0 0 1 0 1 1 1 s 2 受 信 し た 検 情報(4ビット)か 査ビットを表 ら 検 査 ビ ッ ト の す(3ビット) 生成 X ( x0 x1 xk 1 ) W ( w0 w1 wn k 1wn k wn 1 ) (c0 c1 cn k 1 x0 x1 xk 1 ) R (r0 r1 rn k 1rn k rn 1 ) 7個の全ての単一誤りベクトルEに対するシンドロームS は互いに異なるから，単一誤りの位置が判別できて訂正 可能となる． 安達：コミュニケーション符号理論 11 2014/12/3 安達：コミュニケーション符号理論 12 1個のビット誤り 第1ビットに誤りがあったとき 単一誤りベクトルEとシンドロームS 誤りビットの位置に 対応した列ベクトル E 0 1 1 0 0 1 0 1 1 0 0 S HR T 0 1 0 1 1 1 0 0 1 0 0 1 0 1 1 1 0 0 0 0 2014/12/3 安達：コミュニケーション符号理論 e0 1 0 0 0 0 0 0 0 13 e1 0 1 0 0 0 0 0 0 e2 0 0 1 0 0 0 0 0 e3 0 0 0 1 0 0 0 0 S e4 0 0 0 0 1 0 0 0 e5 0 0 0 0 0 1 0 0 e6 0 0 0 0 0 0 1 0 s0 1 0 0 1 0 1 1 0 s1 0 1 0 1 1 1 0 0 s2 0 0 1 0 1 1 1 0 2014/12/3 安達：コミュニケーション符号理論 14 2個以上のビット誤り 1 0 0 1 0 1 1 H h 0 h1h 2 h 3 h 4 h 5 h 6 0 1 0 1 1 1 0 0 0 1 0 1 1 1 であり 2ビット誤りがあるときの復号結果 2ビット誤りの位置に 対応した列ベクトル 0 1 1 0 0 1 0 1 1 0 1 S HR T 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 1 0 0 0 0 シンドローム Sから推定した誤りベク トルEは E (1000000) 第0ビット位置に1ビッ ト誤りがあったと誤判 定 S HR t HE t H( e0 e1e 2 e3 e 4 e5 e6 ) t であることから 6 S i i i 0 となる． 1ビット誤りでei （それ以外は 1 0）であるときにはS h iとなるから もし， であるが，実際の誤り ベクトル Eは 2ビット誤りでei e j 1(i j ) 誤りベクトルを正しく推定できる．しかし， E (e0 e1e2 e3e4 e5e6 ) (0101000) であるときには であったので，次のよ うに3ビット誤りを引き起こ してしまう． ˆ E E (1101000) E 2014/12/3 e h 安達：コミュニケーション符号理論 S h i h j ある．例えば，e1 e3 1とすると 15 2014/12/3 安達：コミュニケーション符号理論 16 0 1 1 S h1 h3 1 1 0 h0に等しい 0 0 0 代数的復号法による復号後 のビット誤り率 であるので，E (1000000)になる．したがって，次のように 3ビット誤りを引き起こしてしまう． ˆ E E (0101000) (1000000) (1101000) E 注）ハミング(7,4)符号の最小ハミング距離はd min 3 2014/12/3 安達：コミュニケーション符号理論 17 2014/12/3 安達：コミュニケーション符号理論 22 2PSKを用いるときの復号後ビット誤 り率 2元対称通信路 通信路への入力は0, 1の記号 誤り生起確率がpで，通信路への入力記号に無関係 符号化後のビットエネルギー ・情報ビット長をTbとする． ・ (n, k )ブロック符号化後のビット長Tcは 1-p “1” p p “0” 1-p 4 Tc RTb Tb 7 ここで，R k / nは符号化率． “1” ・ 符号化ビットのエネルギーは Ec PTc R PTb REb “0” ここで，Pは送信電力で，Ebは情報ビットあたりのエネルギー． Tb 符号化前 Eb=PTb 符号化後 Ec Tc 2014/12/3 安達：コミュニケーション符号理論 23 2014/12/3 検査 ビット Ec=REb，R=k/n 時間 安達：コミュニケーション符号理論 24 ハミング(7,4)符号 復号後ビット誤り率の近似解 3ビット以上誤る確率は2ビット誤りの確率より充分小さいので，2ビッ ト誤りだけを考慮すれば充分である．このような復号誤りの発生確率 は 7 Pe p 2 1 p 5 21 p 2 2 ハミング(7,4)符号の符号化率と帯域幅 符号化率はR=4/7であるから 情報伝送速度を同じにするなら，帯域幅は7/4倍に広がる 帯域幅を同じにするなら，情報伝送速度は4/7倍に低下する つまり，単純な3ビット繰り返し符号化に比べて効率がよい． 2ビット誤りが発生したとき，ハミング距離が3ビットの異なる符号語へ 誤訂正してしまう． 誤訂正が発生したとき，7ビット中の3ビットが誤ることになる．どの3 ビットが誤るかはランダムである．したがって，あるビットに着目する と，誤訂正が発生したという条件下で，そのビットが誤る確率は3/7で ある． 以上より，復号後のビット誤りの確率（ビット誤り率）は次式で与えら れる 復号誤りが発生する確率 最小ハミング距離はdmin=3であるので単一誤り訂正（t=1）であり， 7ビット符号語の中に2ビット以上のビット誤りが発生すると他の 符号語に誤って復号してしまう． 復号誤りの発生確率は 7 7 Pe p 2 1 p 5 p 3 1 p 4 p 7 3 2 2014/12/3 pb 安達：コミュニケーション符号理論 2 PSK変調を考える．ビット 誤り率は（第2章参照） スペクトル密度比， erfc y は次式で表せる誤差補 関数． Tc=RTb 4 Eb 1 E 1 erfc R b erfc 7 N0 2 2 N 0 ディジタル 復調器 R 通信路 復号器 ˆ X 4 Eb 9 pb erfc 7 N 0 4 受け取り 手 復号後ビット誤り率 4 Eb 9 pb 9 p erfc 7 N 0 4 (7,4)Haming 10-4 2 10-6 10-8 10-10 10-12 2 2 2014/12/3 10-2 Coded Uncoded 符号化ありのとき のビット誤り率 1 1 exp t 2 dt erfc y 2 y の関係があるから（ Rは符号化率）， Eb 1 pb erfc N 2 0 符号化 ビットc 27 安達：コミュニケーション符号理論 符号化しないとき のビット誤り率 情報ビットx 符号化前 Ec 1 p erfc N0 符号化後 2 ここでEc / N 0は符号化ビットあたり のエネルギー対雑音電 力 p 2014/12/3 Tb 復号前ビット誤り率 E E c R b , N0 N0 26 3 3 Pe 21 p 2 9 p 2 7 7 10-14 4 安達：コミュニケーション符号理論 28 2014/12/3 6 8 10 Eb/N0 (dB) 12 安達：コミュニケーション符号理論 14 29 復号後ビット誤り率の厳密解 ハミング(7,4)符号の重 み分布 ハ ミ ン グ (7,4) 符 号 の 誤 り 訂 正 能 力 は t=1 で あ る ． 符 号 0=(0000000)を送信する． W=0=(0000000)が送信 されたものとしている． 7 ①誤りビット数がi ( t 1)個のときの誤りベクトルの個数は で i ある． 7 ② 個の誤りベクトルのうちの第j番目の誤りベクトルE jについて i 7 検査行列Hを用いてシンドロームS jを求める．ただし, j 0 ~ 1. i ③シンドロームS jを用いて復号し，復号によって得られた符号語の 符号重みd j (i )を求める． 2014/12/3 安達：コミュニケーション符号理論 33 (7,4)ハミング符号 c0 c1 c2 x0 x1 x2 x3 0 0 0 0 0 0 0 重み 0 1 0 1 1 1 0 0 1 1 1 0 1 0 1 1 0 0 0 0 0 0 3 3 4 1 1 1 0 0 1 0 4 0 1 0 1 0 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0 0 4 3 4 1 0 1 0 0 0 1 3 0 1 1 1 0 0 1 3 1 1 0 0 1 0 1 4 0 0 0 1 1 0 1 3 0 1 0 0 0 1 1 3 1 0 0 1 0 1 1 4 0 0 1 0 1 1 1 4 1 1 1 1 1 1 1 7 2014/12/3 安達：コミュニケーション符号理論 34 厳密解と近似解 7 個の誤りベクトルについて，符号の重みを求める以上の計算を行って， ④ i 符号重みの和 ハミング(7,4)符号の復号後ビット誤り率の厳密解は次式 のようになる（(7,4)ハミング符号の重み分布の表を参照）． 7 i 1 d (i ) pb 9 p 2 (1 p )5 19 p 3 (1 p ) 4 16 p 4 (1 p )3 d j (i ) 12 p 5 (1 p ) 2 7 p 6 (1 p ) p 7 j 0 を求める． ここで ⑤i個のビット誤りのあるときの復号後のビット誤り率は次式で 与えられる． 1 pb (i ) d (i ) p i (1 p ) n i 7 Ec 1 1 erfc R Eb 1 erfc 4 Eb erfc N0 2 7 N0 2 N 0 2 ●ところで，近似式は 以上の①から⑤をi t 1からnまで繰り返せば，求めたい復号後 pb 9 p 2 (1 p )5 のビット誤り率が得られる． であったから，厳密式の第1項と同じである． 7 1 i 1 pb pb (i ) d j (i ) p i (1 p ) n i 7 i t 1 i t 1 j 0 ● p 1のとき，厳密式の第2～6項は無視できるほど小さいから， n 2014/12/3 p n かなり精度の良い近似式であることが分かる． 安達：コミュニケーション符号理論 36 2014/12/3 安達：コミュニケーション符号理論 37 BCH符号 厳密解と近似解の比較 10 符号の訂正能力 最小ハミング距離がd min であるとき， t (d min 1) / 2個 0 のビット誤りまで訂正 できる． 10 -2 10 -4 10 -6 10 -8 10 -10 10 -12 1ビット以上(t>1)の訂正能力を持つブロック符号がBCH 符号である． 無符号化 厳密解 近似解 0 2014/12/3 2 4 6 8 Eb /N0 (dB) 10 12 14 安達：コミュニケーション符号理論 38 2014/12/3 安達：コミュニケーション符号理論 39 BCH符号の 復号後ビット誤り率の厳密解 符号長n，検査ビット長（n-k)，訂正可能なビット数t 一般性を失うことなく，全ての要素が0の符号語 W=0=(0000000)を送信したものとする． 復号前のビット誤り個数がi個(i≧t+1)となる誤りベクトル の個数は(ni)であり，各誤りベクトルの発生確率はpi(1-p)n-i である． (ni)個中の第j番目の誤りベクトルで復号される符号語の 符号重みdj(i)を求める（パリティ検査行列を用いてどの符 号語に誤訂正されるかを求め，dj(i)を求める）． 復号語のビット誤り率は次式のように求められる． n 1 i 1 pb d j (i ) p i (1 p ) n i n i t 1 j 0 n 2014/12/3 ハミング符号 安達：コミュニケーション符号理論 40 2014/12/3 安達：コミュニケーション符号理論 41 復号後ビット誤り率の近似解 復号誤りの発生確率 復号後のビット誤り率 ●符号語にt 1個以上のビット誤りが生じると他の符号語に誤訂正さ ●受信した符号語にt 1個以上のビット誤りがあると，正しい れてしまう． 符号語からのハミング距離が 2t 1の他の符号語に誤訂正 ●復号前のビット誤り率をpで表わすと，復号誤り確率Peは される． n i p (1 p) n i Pe (i ) Pe i t 1 i t 1 i ● p 1であるのでt 2個以上のビット誤りが生ずる確率は ●nビット中にi t 1個の誤りが発生する確率は n n n t 1 p (1 p ) n (t 1) Pe Pe (t 1) t 1 ●このとき，復号後の誤りビット数はnビット中に2t 1個である t 1個のビット誤りの確率より充分小さい．つまり， Pe (t 1) Pe (t 2) Pe (n)． ●したがって， から，復号後のビット誤り率pbは次式のようになる． n t 1 p (1 p) n (t 1) Pe Pe (t 1) t 1 2014/12/3 pb 安達：コミュニケーション符号理論 42 2t 1 2t 1 n t 1 p (1 p ) n (t 1) Pe (t 1) n n t 1 2014/12/3 安達：コミュニケーション符号理論 43 BCH(63,k,t)符号の 復号後ビット誤り率 (n,k,t)=(63,57,1),(63,51,2),(63,45,3),(63,39,4),(63,36,5), (63,30,6),(63,24,7) ブロック長n,情報ビット長k,訂正能力tを持つ(n,k,t)ブロック 符号の復号後のビット誤り率は次式で与えられる． pb 2t 1 n t 1 p (1 p ) n ( t 1) n t 1 2t 1 63 62(63 t ) p t 1 (1 p ) 62 t 63 (t 1)t (t 1) 2 1 ここで Ec 1 1 erfc R Eb 1 erfc k Eb p erfc 2 N0 2 N0 2 n N0 である． なお，符号化なしの ときのビット誤り率は次式になる． Eb 1 pb erfc 2 N0 ここで，erfc y は誤差補関数である． 1 1 exp t 2 dt erfc y 2 y 2t 1 n t 1 p (1 p ) n (t 1) n t 1 pb 復号後ビット誤り率はpt+1に比例する．訂正能力tを大きく できれば復号後のビット誤り率をより小さくできる． 2014/12/3 安達：コミュニケーション符号理論 44 2014/12/3 安達：コミュニケーション符号理論 46 符号化利得 定義 10 -2 10 -4 10 -6 10 -8 10 -10 10 -12 ●所要誤り率（例えば10 6 ）を確保するために必要なEb / N 0を 比較する． t=0 ●符号化しないときの値と符号化したときの値の比 ( E / N 0 ) uncoded G b ( Eb / N 0 ) coded t=1 t=2 t=4 t=5 t=6 t=7 5 6 7 8 9 Eb /N0 (dB) を符号化利得と言う． t=3 10 2014/12/3 11 12 安達：コミュニケーション符号理論 47 検査ビット数を増やすと誤り訂正能力が増加するので， 符号化利得が向上する．しかし，符号化ビットあたりのエ ネルギーが減少するので復号前のビット誤り率が増加し てしまう． このため，検査ビット数を増加し過ぎると，訂正能力を超 えるビット誤りが発生する確率が増えてくる．t=3程度が 安達：コミュニケーション符号理論 2014/12/3 目安となろう． 48 ビット誤り率10-6における符号化利得 10 -2 10 -4 10 -6 10 3.5 2.5 -10 10 -12 10-6 t=1 2 t=2 -8 10 3 t=0 t=4 t=5 t=6 t=7 1.5 t=3 1 0.5 2014/12/3 5 6 7 8 9 Eb /N0 (dB) 10 11 12 安達：コミュニケーション符号理論 0 49 2014/12/3 0 1 2 3 t 4 5 6 7 安達：コミュニケーション符号理論 50 第０６章「誤り検出・訂正の原理」 その２：畳み込み符号とビタビアルゴリズム」 畳み込み符号 符号化 t=1 なし t=2 t=3 t=4 t=5 t=6 t=7 符号化 0 利 得 (dB) 1.72 2.53 2.92 3.04 3.32 3.08 2.62 帯域拡 1 大率 R-1=n/k 1.11 1.24 1.40 1.62 1.75 2.1 2.63 2014/12/3 安達：コミュニケーション符号理論 符号器 樹枝状表現 格子状表現（トレリス） 最尤復号 ハミング距離に基づくビタビ復号 51 2014/12/3 安達：コミュニケーション符号理論 52
© Copyright 2025 ExpyDoc
