<4D F736F F F696E74202D2091E6824F82568FCD8CEB82E892F990B382CC8CF889CA82BB82CC82515F B834E838A B9797A3959C8D F A282E982C682AB82CC8CEB82E897A62E >

Transcription

1 第 7 章 誤り訂正の効果その : ユークリッド距離復号法を用いるときの誤り率 ユークリッド距離に基づく最尤復号ブロック符号のユークリッド距離に基づく最尤復号畳み込み符号のユークリッド距離に基づく最尤復号 安達 : コミュニケーション符号理論 ユークリッド距離に基づく最尤復号 送信情報系列 Xx x x x x x 5.. を符号化して得られた符号系列 5.. を送信する. 伝送路途中の雑音のため誤りが発生するので, 受信系列は送信された符号系列とは異なることがある. 受信系列.. から送信符号系列 を推定し, これより送信情報系列 Xを推定する. 受信系列 と符号系列 との間の近さの目安としてハミング距離を用いるときハミング距離に基づく最尤復号法 maxmum lkelhood deodg, ユークリッド距離 Eulda dstae を用いるときユークリッド距離に基づく最尤復号法になる. 安達 : コミュニケーション符号理論 PSK 伝送時の受信信号表現 送信信号は伝送路を通って受信されるが両側電力 スペクトル密度 が加わる. t P os πf t ここで, PSKのとき, 整合フィルタ t osπf t / の零平均白色ガウス性雑音 t t, t < ± であることに注意. dt 信号の電力スペクトル密度 -f 白色雑音 白色雑音の電力スペクトル密度 / 安達 : コミュニケーション符号理論 f 整合フィルタ出力 tosπf t dt P sπf P os πf P σ [ ] E E { osπ f t } π f であり, その分散 σ は次式で与えられる. E tosπf t dt [ t τ ] dt osπf tosπf τ dtdτ t τosπf tosπf τ dtdτ tosπf t dt tosπf t dt 第 項は信号成分, 第 項 は 平均のガウス分布する雑音成分 安達 : コミュニケーション符号理論

2 ところで, t は電力スペクトル密度が / の白色雑音であるから, 雑音の自己相関関数 t τ は t τ / δ t τ 従って, σ t os ftos f dtd δ τ π π τ τ os ft dt π sπf os π f πf 以上より, 整合フィルタ出力 平均値 分散 σ P のガウス分布する. / であることから, 結局, MP判定は P は P l[ ] p σ を最大とする を探索することに帰着することが分かる. MP判定では, 事前確率 p が必要である. { osπ f t } 整合フィルタ出力 は平均値 Pで, 分散が σ / のガウス分布するから P p exp πσ σ p p を最大とするはp p の対数も最大にする. そこで P l[ p ] l πσ σ P P l l[ p ] πσ σ dt 安達 : コミュニケーション符号理論 5 安達 : コミュニケーション符号理論 7 最大事後確率判定 Maxmum a posteo poalty deso:mp 判定 受信信号が であるときに事後確率 p 送信されたと判定するのがMP判定である. PSKのときは ± である. ayesの定理を用いて変形すると次式を得る. 分母の確率 p になるから, MP判定は を最大とする を探索することと等価である. ここでp は 事前確率 a po poalty と言われる. もし, p が全ての で等しければ PSKのとき ± が等確率 で発生するなら, MP判定は条件付確率 p を探索することと等価である. p p p p p p を最大とする が p p は送信情報 には無関係 を最大とする 安達 : コミュニケーション符号理論 6 最尤系列推定 Maxmum lkelhood sequee estmato: MLSE を用いる復号 と - の出現確率が等しい, つまり p p -.5 とみなして, 受信信号系列,,, - の条件付確率 p を最大とする符号化系列,,, - を推定する. これは MLSE と呼ばれる. 推定した より送信情報系列を求める. MLSE の手順 受信信号 は, 等価低域表現を用いて次式のように表わせる. P ここで, Pは信号電力, は 平均で分散 σ のガウス雑音である. が送信されたときの条件付確率 p は次式で表される. P p exp πσ σ 安達 : コミュニケーション符号理論 8

3 安達 : コミュニケーション符号理論 9 最小とする系列を探索することに等しい. をする. これは, ユークリッド距離の乗和を探索を最大とする系列 最尤復号では, 条件付確率の条件付確率は 雑音が独立であるとき, 受信系列 σ πσ σ πσ exp exp P p P P p しかし, 符号化率が で符号系列長が ビットのとき, 可能性ある符号系列の個数は 個である. 全ての可能性ある符号系列とのユークリッド距離を計算し, 比較し, 選択することにより, それが最大の系列を探索しなければならない. 演算量が膨大になる安達 : コミュニケーション符号理論 を最大とする系列を探索することと等価である. はには無関係. したがって, 項目は系列 第およびであるからのとき ところで, ± MLSE } { PSK L P P P P P 安達 : コミュニケーション符号理論 ブロック符号のユークリッド距離に基づく最尤復号ブロック,k 符号の代数的復号について第 6 章で述べたが, ユークリッド距離に基づく最尤復号も可能である. 以下では, そのときのビット誤り率の近似解について述べる. 安達 : コミュニケーション符号理論

4 ユークリッド距離に基づく復号安達 : コミュニケーション符号理論 ことと等価である. を最小とする系列を探索するであるから, 最尤復号は つまり, する系列を探索することに等しい. を最小と これは, ユークリッド距離の乗和を探索する. を最大とする系列 最尤復号では, 条件付確率 exp exp P P P P P P p p σ πσ σ πσ 安達 : コミュニケーション符号理論,,,,,, m ag,,,,, j P P ± このような復号は次式のように表せる. ことに注意. であるは受信電力を表す. また, であり, ここで, を比較し, 最小の符号語を送信符号語と見なして復号する. の乗ユークリッド距離 受信側では, 全ての符号語とする. 受信ベクトルを 安達 : コミュニケーション符号理論 5 復号誤りが起きる条件, < < > < < 場合に復号誤りが生じる. が次式を満たす以外のいずれかの符号語 つまり, となる符号語が存在するとき復号誤りが生じる. となるときは正しく復号され, このことから, 上式を書き換えると, のときである. 正しく復号されるのはが送信されたとする. 符号語安達 : コミュニケーション符号理論 6 ± ± ± ε ε }, { PSK,,,, d d d d d 複号同順 ここで, したがってはハミング距離である. ここで, ビット符号語であり, 実数なので, を要素とするはと伝送を考える. 以下では, これよりは雑音ベクトルを表す. である. ここで, ところで,

5 復号後ビット誤り率 復号誤りが生ずるのは d ε ± となる個数はビット中にd のガウス確率変数である. ここで, は白色雑音の片側電力スペクトル 密度, は符号化系列のビット長. e e ε は等価雑音. 個ある. は平均値 で分散が / のガウス確率変数であるから, は平均値 で分散がd < となるときである. ここで 必要なE しかし, 符号語の数は 符号化利得 誤り率が十分小さいとき つまりP さくできる. つまり, 符号化利得はG k / d ハミング7, 符号の符号化利得 : 7, k, d e < である., ef / を, 符号化することによって k / d / 安達 : コミュニケーション符号理論 7 x の寄与は無視してよいから, 同じ誤り率を得るために の係数 倍だけ小 個あるから, 符号語長が長くなる につれ 乗ユークリッド距離の計算と比較が膨大になる. であるから, G / 7.d となって, 代数的復号を用いるときより大きな符号化利得が得られる. k m m m ハミング距離最小の符号語へ誤る確率が最も高い. そこで, 最小ハミング距離をdm m{ d } とする. ハミング距離最小の符号語へ誤って復号されたときの誤りビットの個数はビット中にdm個である. 復号誤りが発生したという条件下でのビット誤り率はdm / になる. 以上から, 復号後ビット誤り率 P は次式で近似できる. d m dm dm P p ef ef dm dm / d m E dm k E ef dm ef dm 無符号化のビット誤り率 E p ef ハミング 7, 符号の場合 ハミング7, 符号 7, k, dm 符号化時のビット誤り率 E ef 最尤復号 7 P 9 E ef 代数的復号 lgea eodg 7 無符号化時のビット誤り率 E p ef 安達 : コミュニケーション符号理論 8 安達 : コミュニケーション符号理論 9 安達 : コミュニケーション符号理論

6 veage E Uoded 無符号化 Maxmum Lkelhood eodg 最尤系列推定 lgea eodg 代数的復号法ハミング 7, 符号 畳み込み符号のユークリッド距離に基づく最尤復号 -6 符号化利得 veage eeved E / d 安達 : コミュニケーション符号理論 安達 : コミュニケーション符号理論 畳み込み符号器 情報 ビット x が入力されると ビット が出力される ビット入力で ビットが出力されるので, 符号化率は / 入力 x 出力 x x - x - 入力 x x - x - 並直変換 出力 状態遷移 入力ビットとシフトレジスタの内部状態 ビット を用いて, 符号器出力を表現できる S レジスタの状態 第 桁 第 桁 x x x - x - x が入力されると x x - x - 出力 x x x x x 安達 : コミュニケーション符号理論 S x x x x - 安達 : コミュニケーション符号理論

7 格子状 トレリス 表現 畳み込み符号は符号器に用いたシフトレジスタの内部状態の遷移を用いて表現できる. これを格子状表現 トレリス と言う. 初期状態 5 6 状態 : 状態 : 状態 : 状態 : 入力ヒ ット x 安達 : コミュニケーション符号理論 5 ハミング距離に基づくビタビ復号 復習 符号系列のトレリス表現を用いて, 受信途中でハミング距離の小さい候補系列を選択し残して行くことにより, 効率的に復号するのがビタビアルゴリズムである. 状態遷移と出力符号, ビタビ復号は次のような動作 から成り立っているブランチメトリックの計算パスメトリックの計算パスメトリックの比較生き残りパスの選択,, 入力ヒ ット x 安達 : コミュニケーション符号理論 6 初期状態 S - から出発して時点 ~- における各状態 S {,,,} に合流する つのパスのハミング距離を比較し, ハミング距離の小さいパスを残す. 各状態で以下の計算を行う. 各状態 S {,,,} に入る枝 ブランチ が つあるブランチメトリックの計算 : 受信した ビット符号と各状態 {,,,} に入る つの枝 ブランチ のハミング距離を計算パスメトリック 状態 S に至るパスのハミング距離 の計算 : 状態 S - におけるパスメトリック ブランチメトリックを計算状態 S に到達する つのブランチのパスメトリックの比較パスメトリックの小さい方のブランチとそのパスメトリックを残す最後に, 状態 S - {,,,} のパスメトリックを比較し, 最小のパスを遡り, 復号系列を出力する 安達 : コミュニケーション符号理論 7 7 ビット情報を送信するものと考える畳み込み符号化 情報系列 x : 符号系列, : 初期状態 5 6,, 安達 : コミュニケーション符号理論 8

8 ビタビアルゴリズムの実行 受信系列が次のような場合についてビタビ復号を実行してみる. 誤りベクトル E および受信ベクトル は 元ベクトルである. 誤りベクトル Ee e e e e e 5 e 6 e 7 e 8 e 9 e e e e 受信ベクトル E 各状態 {,,,} に入る枝 ブランチ が つあるブランチメトリック 受信した ビット符号と各状態 {,,,} に入る つの枝 ブランチ のハミング距離 状態遷移 S S S Sのブランチメトリック : d, S S パスメトリック 状態 S に至るパスのハミング距離 状態 S - におけるパスメトリック ブランチメトリック L S L S S S 状態 S に到達する つのブランチのパスメトリックの比較 パスメトリックの小さい方のブランチとそのパスメトリックを残す 安達 : コミュニケーション符号理論 9 安達 : コミュニケーション符号理論 ブランチメトリックとパスメトリックの計算 全ての受信系列を受信し終えてからブランチメトリック, パスメトリックの計算をするのではなく, ビットを受信するごとにブランチメトリック計算, パスメトリックの計算, パスメトリック比較, パス選択を行う ,, 送信系列 受信系列 安達 : コミュニケーション符号理論 時点 より各状態へ つのパスが入り込む時点 でのメトリック計算とパス選択各状態に入るパス 個存在 のパスメトリックを比較し, 少ないほうを生き残りパスとして残す各状態に入る生き残りパスが 個ある 受信系列 -,, 安達 : コミュニケーション符号理論

9 時点 各状態に入るパス 個存在 のパスメトリックを比較し, 少ないほうを生き残りパスとして残す各状態に入る生き残りパスが 個ある 受信系列 - 時点 各状態に入るパス 個存在 のパスメトリックを比較し, 少ないほうを生き残りパスとして残す各状態に入る生き残りパスが 個ある 受信系列 -,, 5 安達 : コミュニケーション符号理論,, 5 安達 : コミュニケーション符号理論 時点 5 各状態に入るパス 個存在 のパスメトリックを比較し, 少ないほうを生き残りパスとして残す各状態に入る生き残りパスが 個ある 受信系列 - 5,, 5 5 安達 : コミュニケーション符号理論 5 時点 6 最尤パスを選択最小パスメトリックを持つ状態は S 6 であり,S 5 からパスが延びている 受信系列 - 5,, 安達 : コミュニケーション符号理論 6

10 復号 状態 S 6 に至るパスを遡ると符号器では次の状態遷移であったことが分かる. これより送信情報は であったことが分かる 送信系列 受信系列 - 5 6,, 安達 : コミュニケーション符号理論 7 ユークリッド距離に基づくビタビ復号 最尤復号は L を最大とする { 時点 におけるユークリッド距離に基づく距離関数 メトリック を とすると L つまり, 上式のメトリックを用いて逐次計算によりパスメトリックを最大とする符号系列を探索することができる. これが, 少ない演算量で最尤復号を実現するビタビアルゴリズムである. ところで, は連続値をとるから, このビタビ復号は軟判定 ビタビ復号と呼ばれる. L L ± } の探索と等価であることが分かった. 安達 : コミュニケーション符号理論 ビタビ復号の動作 一方, 次のように受信信号 を /判定して > のとき のとき を得て, ハミング距離最小の系列を探索するビタビ復号は, 硬判定ビタビ復号と呼ばれる. 符号系列のトレリス表現を用いて, 受信途中で距離の小さい候補系列を選択し残して行くことにより, 効率的に復号する. 時点 における各状態 S に合流するつのブランチのパスメトリックを比較し, パスメトリックの大きいブランチを残す. 各状態で以下の計算を行う. 状態 S に至るブランチのブランチメトリックの計算 状態 S に至るブランチのパスメトリックの計算 時点 -における状態のパスメトリック ブランチメトリック 状態 S に到達するパスメトリックの比較 パスメトリックの大きい方のブランチを残す 安達 : コミュニケーション符号理論 安達 : コミュニケーション符号理論

11 状態 : 状態 : 状態 : 状態 : 7 ビット情報を送信するものと考える畳み込み符号化 情報系列 : 符号化系列 : 初期状態 5 6 -,-,,- -, 安達 : コミュニケーション符号理論 受信系列 , -., -.,., -.9,.9, -.,., -.7, -.,.,.,.7, -.9 注 硬判定では,,,,,,,,,,,,, ビタビ復号各状態,,, に入る枝 ブランチ が つある受信した ビット符号と各状態,,, に入る つの枝 ブランチ のブランチメトリックを計算 下記の計算では, - として計算する 状態遷移 S S のブランチメトリック S S 状態 S に至るパスのパスメトリックの計算 状態 S - におけるパスメトリック ブランチメトリック L S L S S S 状態 S に到達する つのブランチのパスメトリックの比較パスメトリックの大きい方のブランチとそのパスメトリックを残す 安達 : コミュニケーション符号理論 状態 : 状態 : 状態 : 状態 : ブランチメトリックとパスメトリックの計算結果 初期状態 5 6.9, -., -.,., -.9,.9, -.,., -.7, -.,.,.,.7, 全ての受信系列を受信し終えてからブランチメトリック, パスメトリックの計算をするのではなく,ビットを受信するごとにメトリック計算, パスメトリック比較, パス選択を行う以下では, このようなビタビ復号の動作を示す 安達 : コミュニケーション符号理論 5 状態 : 状態 : 状態 : 状態 : 時点 より各状態へ つのパスが入り込む時点 でのメトリック計算とパス選択各状態に入るパス 個存在 のパスメトリックを比較し, 大きいほうを生き残りパスとして残す各状態に入る生き残りパスが 個ある 初期状態 安達 : コミュニケーション符号理論 6

12 時点 各状態に入るパス 個存在 のパスメトリックを比較し, 大きいほうを生き残りパスとして残す各状態に入る生き残りパスが 個ある 時点 各状態に入るパス 個存在 のパスメトリックを比較し, 大きいほうを生き残りパスとして残す各状態に入る生き残りパスが 個ある 初期状態 状態 : 初期状態 状態 : 状態 : 状態 : 状態 : 状態 : 状態 : 状態 : 安達 : コミュニケーション符号理論 7 安達 : コミュニケーション符号理論 8 時点 5 各状態に入るパス 個存在 のパスメトリックを比較し, 大きいほうを生き残りパスとして残す各状態に入る生き残りパスが 個ある 受信系列の最後の時点で最尤パスを選択時点 6 最大パスメトリックの状態を選択 :S 7 状態 S 7 から出発して過去に遡ることにより最尤受信系列を得る 初期状態 状態 : 状態 : 初期状態 状態 : 状態 : 状態 : 状態 : 状態 : 状態 : 安達 : コミュニケーション符号理論 9 安達 : コミュニケーション符号理論 5

13 時点 7 でメトリック最小の状態は S 7. に至るパスは S 6 から延びている. 状態 S 7 に至るパスを次々と遡ると符号器では次の状態遷移であったことが分かる. これより送信情報は であったことが分かる 畳み込み符号の復号後誤り率 下図のような符号器を用いるときの硬判定 ハミング距離 ビタビ復号と軟判定 ユークリッド距離 ビタビ復号の復号後ビット誤り率の解析は難しい. 近似解析について述べる. 計算機シミュレーションによるビット誤り率特性と比較する. 初期状態 5 6 状態 : 状態 : 状態 : 入力 x 並直変換 出力 状態 : 安達 : コミュニケーション符号理論 5 安達 : コミュニケーション符号理論 5 復号後ビット誤り率の近似式 線形符号では誤りの生じた系列は同じ符号に含まれるので, 全ての要素がの符号語が送信されたものと考えて復号誤りを考察してよい. 符号語 に最も近い符号語は, 時点 で状態 から離れ, 状態, 状態 を経て, 時点 でに合流する符号語である. その符号語は, である. ハミング距離は5である. 状態 : 状態 : 状態 : - 安達 : コミュニケーション符号理論 5 ハミング距離は5であるので, 送信された6ビット系列 に 個以上の誤りが生じたとき, 復号誤りが発生する. このときのパスメトリック最小の状態遷移は であり, そのときの符号系列は である. 状態遷移 または符号系列 を与える情報ビット系列は であるから,ビット誤りを引き起こす. 安達 : コミュニケーション符号理論 55

14 復号後ビット誤り率の近似解 "" "" に誤る確率を確率 P"" "" で表わす. どの時点においても, 状態 から離れパス を選択 送信符号系列が"" であると誤判定 してしまう可能性がある. パス が選択されると, 復号出力にビット誤りが生ずる. それ以外のパスに誤ってしまう確率は充分小さい. 以上より, 復号後ビット誤り率 P は次式のように近似できる. P P"" "" 誤りパスの例 me ll tasmsso 復号後の情報ビット系列 t eo t eo 安達 : コミュニケーション符号理論 56 安達 : コミュニケーション符号理論 57 ハミング距離を用いる硬判定ビタビアルゴリズム 受信系列の6ビット中にビット以上の誤りが発生する確率は, ビット判定誤り率をpとすると 6 6 k p p k k であるから 6 6 k 6k P o"" "" p p p, p << のとき k k 以上より, 復号後ビット誤り率 Pは次式のように近似できる. P p, ここで,PSKを用いるとき E p ef ここで, E E. 6k p << のとき 情報ビット系列 #- # 符号化系列 E #- # - # # 一方, 符号化なしのときの判定誤り率 P ef まとめ P ef E P ef E E 符号化なし 5 ef E 符号化あり E 安達 : コミュニケーション符号理論 58 安達 : コミュニケーション符号理論 59

15 硬判定ビタビ復号 符号化利得 E E exp ef を用いると, ビット誤り率は次式のように近似できる. E exp 符号化なし P E exp E exp 符号化あり これまで考えてきた拘束長 ビット, 符号化率 / の畳み込みの 符号化利得 符号化なしとありで同じビット誤り率を得るために必要な E / の比 は次のようになる. G デシベル表示では.76d veage E Uoded heoy ad eso Vte heoy Uoded Smulato ad eso Vte Smulato 5 5 veage eeved E / [d] 安達 : コミュニケーション符号理論 6 安達 : コミュニケーション符号理論 6 ユークリッド距離を用いる軟判定ビタビアルゴリズム 符号長 の符号系列 ˆ パスメトリックL L ˆ ただし, < L ˆ ˆ L ˆ < { ˆ ± ; ~ } ここで, 第 項が信号成分, Pは受信電力, 第 項 w が雑音成分は平均 ˆ を最大とする系列 { } を探索する. 送信系列がであるとき, 次式を満たす系列 ˆ が存在すれば L Δ L ˆ P で分散 / のガウス雑音である. ユークリッド距離に基づく最尤復号法ではL 上式は次式のように変形できる. は次式で与えられている. 送信系列以外の系列が送信されたものと誤判定してしまうことになる. の 安達 : コミュニケーション符号理論 6 Δは次式のように表せる. Δ ± である. m ˆ ˆ ˆ ところで, ˆ と が一致していれば ˆ 距離をd X Pdm W 平均 で分散 dm 以上より, Δ < となる確率は Po P ˆ ˆ [ ] Δ Pdm Δ < exp π d m / ˆ またはであること, は平均 で分散 X W, そうでなければ とする へ誤る場合が殆どである. ここで, 送信符号系列 に最もハミング距離が近い系列 最小ハミング / のガウス変数 d m dδ / / のガウス変数であるから 安達 : コミュニケーション符号理論 6

16 Po Po [ ] Δ Pd m Δ < exp ここで, E ただし, E π d y exp dy Pd π d m / m d m / E P exp t dy ef d π m dm P は 符号ビット当たりの信号エネルギーを表す. E であるから m [ ] Δ < ef d m / E d m dδ / 情報ビット系列 # # #k- 符号化系列 E E # # #- 軟判定ビタビ復号 時間 安達 : コミュニケーション符号理論 6 送信符号系列を とする. それに最も近い符号系列は ˆ であるから, dm 5である. / であるから E Po"" "" ef d m 5 E ef この系列が選択されるとビットの情報誤りが発生するから復号後ビット誤り率 P は次式のように近似できる. 5 E P ef 一方, 符号化なしのときは E P ef 安達 : コミュニケーション符号理論 65 軟判定と硬判定ビタビ復号の比較 veage E Uoded heoy Soft eso Vte heoy Uoded Smulato Soft eso Vte Smulato veage E Uoded heoy ad eso Vte ad Soft eso Vte Uoded ad eso Vte Smulato Soft eso Vte Smulato veage eeved E / [d] veage eeved E / [d] 安達 : コミュニケーション符号理論 66 安達 : コミュニケーション符号理論 67

17 所要誤り率 例えば を符号化利得と言う. 符号化利得 G を確保するために必要なE 比較する. 符号化しないときの値と符号化したときの値の比 E / G E / uoded oded 拘束長 ビット, 生成多項式 7,5 の畳み込み符号を軟判定 ビタビ復号したときに得られる符号化利得はG.5 デシベル表示では.98d になる. 硬判定ビタビ復号より大きな符号化利得が得られる. 8 / を むすび ユークリッド距離を用いる最尤系列推定に基づく復号は, ハミング距離を用いる最尤系列推定に基づく復号より強力な誤り訂正能力をもつ. ビタビ復号は最尤系列推定に基づく復号の誤り訂正能力を落とさずに演算量を大幅に削減できる. 最近のほとんどのディジタル伝送システムに畳み込み符号化, ユークリッド距離に基づくビタビ復号が用いられている. 入力 x 並直変換 出力 安達 : コミュニケーション符号理論 68 安達 : コミュニケーション符号理論 69