通信符号理論 14

1 通信符号理論 第14回 伊藤彰則

2 ターボ符号 • 概要 • 複数の符号化器（典型的には２つの畳み込み符号）を組み合わせる • 片方はインターリーバを経由させる • 1つだけインターリーバを使うことは本質ではない • ２つの系列が異なる誤りパターンであれば良い 1010 𝒎 1010 ConvCoder 11100010 𝒙1 11100110 𝒚1 ConvCoder 11010111 𝒙𝟐 10010111 𝒚𝟐 Interleaver 1100

3 ターボ符号 • さまざまなバリエーションがある • 本質的にはブロック符号であってもよいが、畳み込み符号を使うこと が多い • 再帰的畳み込み符号がよく使われる • Punctured畳み込み符号による符号化率の制御 • ターボ復号 • トレリスを使って２つ （以上）の符号をそれぞれ復号する • 片方のシンボルMAP復号の結果を事前確率としてもう片方を復号 →繰り返す

4 再帰型／非再帰型畳み込み符号 • メモリの内容を入力に戻すのが「再帰型」 • ディジタル信号処理でいう「IIRフィルタ」に相当する • 非再帰型の例 … , 𝑚3 , 𝑚2 , 𝑚1 𝑚𝑖 𝑚𝑖−1 𝑚𝑖−2 + + (2) 𝑥𝑖 (1) 𝑥𝑖

5 再帰型／非再帰型畳み込み符号 • メモリの内容を入力に戻すのが「再帰型」 • ディジタル信号処理でいう「IIRフィルタ」に相当する • 再帰型の例 (1) 𝑥𝑖 = 𝑚𝑖 … , 𝑚3 , 𝑚2 , 𝑚1 𝑚𝑖 + 𝑠𝑖 𝑠𝑖−1 𝑠𝑖−2 𝑠𝑖 = 𝑚𝑖 + 𝑠𝑖−1 + 𝑠𝑖−2 (1) この例では𝑥𝑖 がメッセージそのものに なっているので、組織符号化である + (2) 𝑥𝑖 = 𝑠𝑖 + 𝑠𝑖−2

6 再帰型畳み込み符号 0, 1, 0, 1 0 + + 0

7 再帰型畳み込み符号 1 0, 1, 0 1 0 + + 0

8 再帰型畳み込み符号 1 0, 1, 0 1 + 1 0 + 0

9 再帰型畳み込み符号 1 0, 1, 0 1 + 1 0 + 0 1

10 再帰型畳み込み符号 1 0, 1, 0 1 + + 0 1

11 再帰型畳み込み符号 0,1 0, 1 0 1 + + 0 1

12 再帰型畳み込み符号 0,1 0, 1 0 + 1 1 + 0 1,1

13 再帰型畳み込み符号 1,0,1 0 1 1 + + 1 1,1

14 再帰型畳み込み符号 1,0,1 0 1 + 1 1 + 1 0,1,1

15 再帰型畳み込み符号 + + 𝒎𝒊 𝒔𝒊 𝒔𝒊−𝟏 𝒔𝒊−𝟐 𝒙𝒊 (𝟏) 𝒙𝒊 (𝟐) 1 1 0 0 1 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 1 1 1 0

16 先ほどの例のトレリス 𝑠𝑖−1 𝑠𝑖−2 00 00 00 00 00 11 11 11 11 11 11 11 11 10 11 01 11 00 11 00 11 00 11 01 01 01 01 01 01 01 01 10 10 𝑚𝑖 = 0 10 𝑚𝑖 = 1 10 00

17 Punctured畳み込み符号 • 符号化率を上げるため、畳み込み符号を一定のパターンで省く •例 • 先ほどの（再帰型）畳み込み符号で 10101101 10101101 + 1101100111110110 11011110 +

18 Punctured畳み込み符号 • 符号化率を上げるため、畳み込み符号を一定のパターンで省く •例 • 先ほどの（再帰型）畳み込み符号で 10101101 10101101 + 1101100111110110 11011110 +

19 先ほどの例のトレリス 00 00 0 00 0 11 1 11 1 11 1 11 1 10 11 01 00 01 0 01 11 1 0 10 11 00 1 01 01 1 𝑚𝑖 = 0 0 10 𝑚𝑖 = 1 0 0 1 0

20 ターボ符号の符号化 • （典型的には）（再帰型）畳み込み符号化器を複数使う • 途中にインターリーバを挟んで系列をシャッフルする • Punctured符号を使って符号化率を上げることもある 1010 𝒎 1010 1010 𝒙𝟎 1010 ConvCoder 𝒙1 1101 Interleaver 1100 ConvCoder 𝒙𝟐 1001 111010100011

21 ターボ符号の符号化 • （典型的には）（再帰型）畳み込み符号化器を複数使う • 途中にインターリーバを挟んで系列をシャッフルする • Punctured符号を使って符号化率を上げることもある 1010 𝒎 1010 1010 𝒙𝟎 1010 ConvCoder 𝒙1 1101 Interleaver 1100 ConvCoder 𝒙𝟐 1001 11001001

22 ターボ符号の復号 • メッセージそのものに対応する部分と畳み込み符号部分が受信 される 1010 𝒎 1010 1010 𝒙0 1010 𝒚0 ConvCoder 𝒙1 1101 𝒚1 ConvCoder 𝒙2 1001 𝒚2 Interleaver 1100

23 ターボ符号の復号 • メッセージそのものに対応する部分と畳み込み符号部分が受信 される • シンボルMAP復号により、各ビットの対数尤度比𝑳 = (𝐿1 , … , 𝐿𝑛 )を計算 1010 𝒎 1010 1010 𝒙0 1010 𝒚0 ConvCoder 𝒙1 1101 𝒚1 ConvCoder 𝒙2 1001 𝒚2 Interleaver 1100 Decoder 𝑳

24 ターボ符号の復号 • メッセージそのものに対応する部分と畳み込み符号部分が受信 される • 𝒚0 , 𝑳をインターリーブ • 𝑳を「事前情報」（外部値）として利用 Interleaver 𝒚0 𝒚1 𝒚2 Decoder 𝑳 Interleaver Decoder 𝑳’

25 ターボ符号の復号 • メッセージそのものに対応する部分と畳み込み符号部分が受信 される • 𝑳′を逆インターリーブ、外部値として利用 Interleaver 𝒚0 𝒚1 𝒚2 Decoder 𝑳 Interleaver Decoder 𝑳’ DeInterleaver Decoder 𝑳

26 ターボ符号の復号 • シンボルMAP復号を考える σ𝒙,𝑥 =0 𝑃𝑌|𝑋 (𝒚|𝒙)𝑃𝑋 (𝒙) • 𝐿𝑖 = log σ = log 𝑖 𝒙,𝑥𝑖 =1 𝑃𝑌|𝑋 (𝒚|𝒙)𝑃𝑋 (𝒙) σ𝒙,𝑥 =0 𝑃𝑌|𝑋 (𝒚|𝒙) ς𝑘 𝑃𝑋 (𝑥𝑘 ) = log σ 𝑖 𝒙,𝑥𝑖 =1 𝑃𝑌|𝑋 (𝒚|𝒙) ς𝑘 𝑃𝑋 (𝑥𝑘 ) 𝑃𝑋 (𝑥𝑖 =0) σ𝒙,𝑥 =0 𝑃𝑌|𝑋 (𝒚|𝒙) ς𝑘≠𝑖 𝑃𝑋 (𝑥𝑘 ) 𝑖 𝑃𝑋 (𝑥𝑖 = 1) σ𝒙,𝑥 =0 𝑃𝑌|𝑋 (𝒚|𝒙) ς𝑘≠𝑖 𝑃𝑋 (𝑥𝑘 ) 𝑖 = log σ𝒙,𝑥 =0 𝑃𝑌|𝑋 (𝒚|𝒙) ς𝑘≠𝑖 𝑃𝑋 (𝑥𝑘 ) 𝑖 𝑃 (𝑥 = 0) 𝑋 𝑖 + log 𝑃 (𝑥 ) 𝑃 (𝑥 = 1) σ𝒙,𝑥 =1 𝑃𝑌|𝑋 (𝒚|𝒙) ς𝑘≠𝑖 𝑋 𝑖 𝑘 𝑋 𝑖

27 事前確率 • 𝑥𝑘 の事前確率に相当する項 log 𝑃𝑋 (𝑥𝑘 =0) 𝑃𝑋 (𝑥𝑘 =1) • 何の情報もなければ𝑃𝑋 0 = 𝑃𝑋 1 = 0.5なのでlog 𝑃𝑋 (𝑥𝑘 =0) 𝑃𝑋 (𝑥𝑘 =1) =0 • ターボ復号では受信語が（最低）2つあるので、片方のシンボ ルMAP復号による対数尤度比𝐿𝑘 をもう片方の事前確率として使 う (1) (1) (2) (2) • 復号器1による対数尤度比 𝑳(1) = 𝐿1 , … , 𝐿𝑛 • 復号器2による対数尤度比 𝑳(2) = 𝐿1 , … , 𝐿𝑛

28 復号の式 • 𝑃𝑋 𝑥𝑘 = 0 = • 𝑃𝑋 𝑥𝑘 = 1 = (𝑑′ ) exp 𝐿𝑘 (𝑑′ ) 1+exp 𝐿𝑘 1 𝑑′ 1+exp 𝐿𝑘 (𝑑′ ) (𝑑) • 𝐿𝑖 = log = log σ𝒙,𝑥 =0 𝑃𝑌|𝑋 (𝒚𝑑 |𝒙𝑑 ) ς𝑘≠𝑖 𝑃𝑋 𝑥𝑘 𝑖 + log (𝑑′ ) σ𝒙,𝑥 =0 𝑃𝑌|𝑋 (𝒚𝑑 |𝒙𝑑 ) ς𝑘≠𝑖 𝑃𝑋 𝑥𝑘 𝑖 (𝑑′ ) σ𝒙,𝑥 =0 𝑃𝑌|𝑋 (𝒚𝑑 |𝒙𝑑 ) ς𝑘≠𝑖 𝑃𝑋 𝑥𝑘 (𝑑 ′ ) 𝑖 𝑖 (𝑑′ ) σ𝒙,𝑥 =0 𝑃𝑌|𝑋 (𝒚𝑑 |𝒙𝑑 ) ς𝑘≠𝑖 𝑃𝑋 𝑥𝑘 𝑖 +𝐿 (𝑑′ ) 𝑃𝑋 𝑥𝑖 =0 (𝑑′ ) 𝑃𝑋 𝑥𝑖 =1

29 ターボ符号の性能 井坂、「畳み込み符号とターボ符号」、映像情報メディア学会誌 70(4) 576-581, 2016.

30 演習 次の畳み込み符号で次の入力を符号化せよ。 • 畳み込み符号の定義 • 入力 𝑚1 , 𝑚2 , … 1 2 1 (2) • 出力 𝑥1 , 𝑥1 , 𝑥2 , 𝑥2 , … (1) • 𝑥𝑖 = 𝑚𝑖 • 𝑠𝑖 = 𝑚𝑖 + 𝑠𝑖−2 + 𝑠𝑖−3 (2) • 𝑥𝑖 = 𝑠𝑖 + 𝑠𝑖−1 + 𝑠𝑖−3 • 入力系列 10101100 (ちなみにこの符号は 3GPP LTE （3.9G携帯電話）のターボ符号に使われている畳み込み符号である） 参考 https://www.intel.co.jp/content/dam/www/programmable/us/en/pdfs/literature/an/an505.pdf

• https://www.intel.co.jp/content/dam/www/programmable/us/en/pdfs/literature/an/an505.pdf