第 8 章 たたみ込み符号 65
8.4 Viterbi 復号の特性
78 第8章 たたみ込み符号
8.4.1 何を知りたいのかを決めておこう
Viterbi復号の特性を調べると言っても, いまいち, 何が知りたいのかがハッキリと分からない（抽象的す
ぎる）. そこで, 一体これから何を調べたいのかを, ここでハッキリと理解しておこう. この理解をキッチリ としているかどうかで,これからの理解のスムーズさが大幅に変わってくる.
Def : これから調べること
¶ ³
送信者が全零系列（すなわち,ゼロベクトル）を送信したとき,Viterbi復号によって誤りが発生（すな わち, ゼロベクトルを送ったのに1を含む系列に復号されてしまう）する確率について調べる.
µ ´
8.4.2 イベント誤り
Viterbi復号の特性を考える上で欠かせない概念として,イベント誤り(event error)を定義しよう.
Def : イベント誤り
¶ ³
全零系列を復号した系列（復号系列）が, 全零系列から離れ, 再び合流するまでの誤りを, イベント誤り (event error)と呼ぶ.
µ ´
イベント誤りのイメージは,以下のトレリス線図を見れば掴みやすいだろう.
時点 0 1 2 3 4
(00) (00)
(01)
(10)
(11)
r3r4 r5r6 r7r8
r1r2
00 00 00 00
em1em2
em3em4 em5em6
em7em8
em = [em1,· · · , em8]により作られる1つの経路が, 1つのイベント誤りを表す. 全零系列から離れ, 再
び合流していることがわかるだろう. イベント誤り ek を, 第kのイベント誤りと呼ぶことにする. また,
R= [r1, r2,· · ·, r8]は,受信系列（硬判定復号後の系列）である.
復号により誤りが発生するとは, Rが全零系列ではない系列となってしまう（もともとの送信系列は全零な のだから,復号されたRも, 本来ならば全零にならなければならない）ことを指す. このことから, 復号の誤 りが発生したかどうかを知るためには,以下の判断を行う必要があることがわかる.
受信系列Rは,0(全零系列)と見なすべきか？em（あるイベント誤り）と見なすべきか？
8.4 Viterbi復号の特性 79
そして, Rをどう見なすかを決定するために用いる指標は,Hamming距離である.
Def : Rはどう見なす？
¶ ³
Rを受信系列,emをあるイベント誤り(第mイベント誤り)であるとしたとき,
• dH(R,0)≤dH(R,em) ⇒ Rは0であっただろうと見なす.
• dH(R,0)≥dH(R,em) ⇒ Rはemであっただろうと見なす.
µ ´
¨
§
¥
例¦em = [01110100],0= [00000000],R= [00101001]. このとき,Rは, 0であった可能性と, em であっ た可能性,どちらが高いだろうか？
dH(R),0) =3, dH(R,em) =5.
∴dH(R.0)≤dH(R,em)より,Rは,emであった可能性が高い.
つまるところ, Hamming距離が短いほうが似ているんだから,そっちだった可能性のほうが高いんじゃない の.という至極当然のことを言っているだけなのだが, この条件はこれからずっと有効なので是非ここで理解 しておいてほしい.
8.4.3 イベント誤り確率
あるイベント誤りemを考えたときに,0が誤ってemに復号されてしまう*9確率が一体どの程度になるの かを考えよう. そのためにまず, イベント誤り確率を定義する.
Def : イベント誤り確率Pem
¶ ³
全零系列0が,あるイベント誤りemに復号される確率をemのイベント誤り確率と呼び,Pemと表す.
µ ´
このPemは具体的にどうやって計算すれば求められるのだろうか. その計算式を今から導き出そう.
まず,たたみ込み符号の復号においては2元対称通信路を考えていたため,0を1と復号してしまう確率と,1 を0と復号してしまう確率は一定である. その確率をpbと表すことにしよう.
今,送信系列として全零系列を考えていたので,Rのシンボルがもし1と見なされてしまったら,それは誤り が発生したということになる. 誤りが発生する確率はpbであるので,Rの1つのシンボルが1であると見な される確率はpbである. またそれゆえに, Rのひとつのシンボルが0と見なされる確率は1−pbである.
0 0 0 0 0 0
↑ ↑ ↑ ↑ ↑ 1−pb
R r1 r2 r3 r4 r5
↓ ↓ ↓ ↓ ↓ pb
1 1 1 1 1 1
*9すなわち,何か適当なイベント誤りを1つ作って,全零系列がそれに復号されるということ.
80 第8章 たたみ込み符号
次に,以下の例を考えてみよう.
• wH(em)*10=dm=4とする.
このとき,全零系列が誤ってemに復号されてしまうのはどのような場合だろうか？ちょっと考えてみよう. dm=4のイベント誤りの例として, em= [0111001]を考える. このとき,全零系列が誤ってemと見なされ てしまう(すなわち, dH(R,0)≥dH(R,em)となる)のは,受信系列Rのビットのうち,emの1の部分に対 応する部分のうち, 任意の2ビット以上が1となったときである.
0 0 0 0 0 0 0 0 R 0 1 1 0 0 0 0 em 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 R 0 1 0 1 0 0 0 em 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 R 0 1 0 1 0 0 1 em 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 R 0 1 1 1 0 0 0 em 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 R 0 1 1 1 0 0 1 em 0 1 1 1 0 0 1
これらのすべての場合において,dH(R, 0)≥dH(R,em)となる. よって,Rはemと見なされてしまうとい うことなので,誤りが発生していることになる. このように, 一般に,Rがイベント誤りem と見なされてし まうのは, Rのビットのうちemと対応する場所(ビット数dm)にdm/2個以上の1が発生してしまった場 合である. ただし, dm/2が自然数とならない場合は,桁上げすることとする*11.
Thm : Rがイベント誤りemと見なされる条件
¶ ³
Rのうち,emの1に対応する部分（その部分のビット数はdm）で任意のdd2me個以上の1が発生した ならば,Rはemと見なされる. すなわち,誤りが発生する.
ただし,dxeは,xの桁上げを表す. f(x) =dxeのとき,fを天井関数(ceiling function)と呼ぶ.
µ ´
*10イベント誤りemのHamming重み(すなわち,1の数)のこと.覚えてるかな？
*11たとえば,dm=3ならば,dm=2=1:5となり,整数とならない. この場合は,桁の切り上げを行い,2個以上の1がRに発生 したときに誤った復号が行われると考える.
8.4 Viterbi復号の特性 81
先程のdm =4のイベント誤りの例についてもう一度考えよう. Rのある1ビットが1となる確率はpb, 0 となる確率は1−pbであったので,Rの中のemの1に対応する部分のうち,ある2(=dd2me)ビットが1と なる確率はp2b(1−pb)4−2である. そして,4ビットのうち 2ビットが1となるパターン数はdmC2=4C2
個存在するため,4ビット中の::::::任意の2ビットが1となる（つまり, すべてのパターンの合計）確率は,
dmC2p2b(1−pb)dm−2=4C2p2b(1−pb)4−2 となる. 同様に,3ビットの1が生じる確率は,
dmC3p3b(1−pb)dm−3=4C3p3b(1−pb)4−3 となり, 4ビットの1が生じる確率は,
dmC4p4b(1−pb)dm−4=4C4p4b(1−pb)4−4
として求められる. これで,Rがイベント誤りemと見なされてしまうすべてのパターンを網羅したことにな るので, このすべての確率の和をとればemのイベント誤り確率 Pemが求められるはずである. よって,
Pem= X4 r=2
dmCrprb(1−pb)dm−r.
という結果が得られる. 今までは dm=4の場合のみを考えてきたが,一般の場合にも同様の議論によりイベ ント誤り確率Pemを求めることができる. 以下にその結果を示そう.
Thm : イベント誤り確率
¶ ³
受信系列Rが,イベント誤りemに見なされてしまう確率, すなわちemのイベント誤り確率Pemは, 以下のように求められる. ただし,dm =wH(em)である.
Pem=
dm
X
r=ddm2 e
dmCrprb(1−pb)dm−r.
µ ´
8.4.4 上界
このようにして,上手にイベント誤り確率Pemを求めることができた. が,この式はなかなか複雑であり, 計算をするために結構な手間がかかってしまう. そこで,このPemを,上界を使って::::::::::::::::押さえ込んでやることを 考えよう. その前に,まずは上界とは何かを定義しよう.
Def : 上界(upper bound)
¶ ³
ある関数f(x)が,どんなxに対しても,
f(x)≤M を満たすとき,Mをf(x)の上界(upper bound)と呼ぶ.
f(x)が上界を持つとき,f(x)は上に有界であるという. 上界のうち最小のものを上限と呼ぶ.
µ ´
82 第8章 たたみ込み符号
上界の考え方はちょっとわかりにくいので,詳しく考えておこう. 例えば,以下の関数を考える. f(x) =2.
この関数の上界は, 2以上のすべての実数である. なぜなら,2以上の実数Mをとれば, 必ずf(x)≤Mが満 たされるからだ. このように,上界というものはいくつでも存在する. そして,上界のうち最小のものは 2で あるから,f(x)の上限は2である. このように,上限は唯一だ.
上界のイメージは,以下のような例を使うとわかりやすい. 例えば,今あなたの目の前にとても高いビルがあ るとする. そのビルが一体何mなのかを一目見てハッキリと知ることはできない（すなわち, ビルの高さの 上限を求めることはできない）が,「まあ,100m以下ではあるだろう」と,大雑把な値でビルの高さを評価す ることができる. この「100m」という値は, ビルの高さの上界である. ビルの高さは「1000m以下だ」とも,
「10000m以下だ」とも言えるので,上界はいくつでも考えられる. が,上界のうち最小のもの（すなわち, ビ ルの本当の高さ,上限）はただ1つしか存在しない. このことは,上限が唯一であることと対応する.
8.4.5 Bhattacharyya バウンド
emのイベント誤り確率Pemの上界について考える. このことはすなわち,「まあPemはこの数よりは小 さいですよ」と言えるその「数」を求めることに相当する.
その数を導くには, 高度な確率統計学の知識, そして, 洞察力を必要とするので, ここでは, Pemを上界を 使って不等式で評価した結果のみを示すことにしよう. その時に用いる上界をBhattacharyya*12バウンド (Bhattacharyya bound)と呼ぶ.
Thm : Bhattacharyyaバウンド
¶ ³
Pem≤ 2p
pb(1−pb)
®dm
µ ´
8.4.6 ユニオンバウンド
そして, Bhattacharyyaバウンドを用いて, Viterbi復号によって何か(すなわち, 何でも良い)イベント
誤りが生じてしまう確率の上界を導いてみよう. その確率をPbと置くと,Pbは,イベント誤りe1またはe2
または· · · または em または · · · が生じる確率であるから,
Pb=P(e1te2t · · · temt · · ·) =P Ã1
G
k=1
ek
!
=P(e1) +P(e2) +· · ·+P(em) +· · ·= X1 k=1
P(ek)
ただし,tは, 直和集合（共通部分が存在しない和集合）を表すこととする. このように,結局,すべてのイベ ント誤りが発生する確率の和によってPbが求められるので,Pbは以下のように変形できる.
Pb=【Hamming重みが1であるようなイベント誤り発生確率の和】+· · ·
+【Hamming重みがmであるようなイベント誤り発生確率の和】+· · ·
*12「ばたちゃりや」と読む.
8.4 Viterbi復号の特性 83
さらにこの式についても,次のように変形することができる.
Pb=A1【Hamming重みが1であるようなイベント誤り発生確率】+· · ·
+Am【Hamming重みがmであるようなイベント誤り発生確率】+· · ·
=A1Pe1+A2Pe2+· · ·+AmPem+· · ·= X1 k=1
AkPek
ただし,Ak は, Hamming重みがkであるようなイベント誤りの総数である. このようにして, Pbを変形す
ることができた. あとは,それぞれのPekをBhattacharyyaバウンドを使って評価すると, Pb≤A1
2p
pb(1−pb)
® +A2
2p
pb(1−pb)
®2
+· · ·= X1 k=1
Ak
2p
pb(1−pb)
®k
このように,Rが,何かのイベント誤りに復号されてしまう確率Pbの上界を求めることができた. この上界 をユニオンバウンド(union bound)と呼ぶ.
Thm : ユニオンバウンド
¶ ³
全零系列0を送信したとき, 受信系列Rが何かのイベント誤りに復号されてしまう確率 Pb について, 以下の評価が成り立つ.
Pb≤X1
k=1
Ak
2p
pb(1−pb)
®k
.
µ ´
8.4.7 ユニオンバウンドを実際に求めるには
さて,このようにユニオンバウンドによるPbの評価を求めることができた. しかし, Hamming重みkの イベント誤りの総数Akは一般に求めることが難しいので,ユニオンバウンドを求めるためにも工夫が必要と なる. そこで, ユニオンバウンドをうまく求める方法を, 符号器の状態遷移図を使って考えてみよう. そのた めに,以下のような状態遷移図を考える.
00
01
10
11
状態遷移図におけるイベント誤りは, 例えば太線の矢印で示している経路のように,00からスタートし, 最終 的にまた00に戻る経路により表される. そして,そのような経路は無数に存在する.