適応信号処理技術.

Presentation on theme: "適応信号処理技術."— Presentation transcript:

1 適応信号処理技術

2 １．信号推定・判定の基礎

3 時系列信号 時系列とは 時系列の処理 不規則に変動する物理過程の観測値を時間の順に並べたもの 予測 推定
時系列における過去の観測値から将来の値を推定すること 推定 雑音に乱された受信信号系列から，その中に含まれる意味のある信号を抽出すること（フィルタリング） 波形の推定 送信データの推定（判定）

4 推定と判定 信号の推定（アナログ／ディジタル通信共通） 信号の判定（ディジタル通信固有） 雑音に埋もれた信号の検出 ひずみを受けた信号の補償
Wienerフィルタ，Kalmanフィルタ 信号の判定（ディジタル通信固有） M源情報源（M個のシンボルで構成される情報源）の判定 ベイズの理論，最尤推定，MAP推定

5 線形自乗推定に基づく信号の推定 推定理論に適用されるシステム方程式が線形 雑音は白色・ガウス雑音 広義定常（平均と相関関数が時刻に無関係）
白色：電力スペクトル密度が一様 時系列データの変化の速度に関する規定 変動幅に関する情報は含まれない ガウス：電圧変動の確率密度関数がガウス分布 時系列データの変動幅に関する規定 時系列データの変化の速度に関する情報は含まれない 広義定常（平均と相関関数が時刻に無関係） 最小二乗規範 推定誤差の分散を最小化

6 最小自乗推定に基づく信号推定 【フィルタリング】 雑音 n(t) 信号 s(t) 受信信号 y(t) 推定値 s(t) ^ 適応 フィルタ
＋ + 推定誤差 e(t) ＋ - 参照信号 （理想的にはs(t)） 【補償】 雑音 n(t) 受信信号 y(t) ひずみ の発生 （伝搬路） 推定値 s(t) ^ 信号 s(t) ひずみ補償器 （フィルタ） ＋ h(t) ^ 推定誤差 e(t) + h(t) ＋ - ひずみの推定 （伝搬路推定） 参照信号 （理想的にはs(t)）

7 ２．ベースバンド信号の取り扱いについて

8 複素信号表示（１） ー送信信号（数式表現）ー
変調された信号：

9 複素信号表示（２） ー送信信号（回路表現）ー
z(t) 実際の送信信号 Re[ ] 複素モデル 回路 zI(t) + p/2 zQ(t)

10 複素信号表示（３） ー復調（回路表現）ー 複素 受信信号 複素モデル 回路 LPF zI(t) p/2 LPF zQ(t)

11 等価低域系表現（信号波形） （フーリエ変換） U(f) A(f) (1/2)U*(-f-fc) (1/2)U(f-fc) f f -fc

12 等価低域系表現（伝送路特性）（１） ？ B(f)=U(f)H(f) A(f) (1/2)B*(-f-fc)
=(1/2)U*(-f-fc)H*(-f-fc) (1/2)B (f-fc) =(1/2)U (f-fc)H (f-fc) f f -fc fc ？ ゼロ

13 等価低域系表現（伝送路特性）（２） H(f) G(f) H*(-f-fc) H(f-fc) f f -fc fc

14 帯域系と等価低域系の関係 【帯域系】 【等価低域系】

15 ３．線形フィルタ理論 （アナログフィルタ）

16 線形フィルタ理論（アナログ表記）(1) ーモデルー
s(t) ^ s(t) + n(t) h(t) 【平均自乗誤差】 最小化

17 線形フィルタ理論（アナログ表記）(2) ー直交原理（自乗平均誤差の最小化）ー
s(t) e(t) =s(t)-ay(t) y(t) a.y(t) 【問題】 y(t)からs(t)を推定する 【手法】 y(t)をa倍してs(t)に近づける（aの最適化） 【判定基準】 |e(t)|2を最小化 |e(t)|2が最小となるのはay(t)とe(t)が直交する場合

18 線形フィルタ理論（アナログ表記）(3) ー最適線形フィルタの算出ー
の最小化 上式ではすべてのy(a) （-∞<a<∞）の値を活用してs(t)を推定 y(t-a)とe(t)が直交化 Wiener-Hopfの方程式

19 線形フィルタ理論（アナログ表記）(4) ー因果律ー
【因果律】 回路の出力は，信号が入力された後でないと発生しない （負のインパルス応答は物理的にありえない） h(t) t0 h(t) 遅延 （t0） + = t t 応答は 有限時間 理論上 （因果律は満足されない） 現実 （因果律は満足される）

20 線形フィルタ理論（アナログ表記）(５) ーWiener-Hopfの方程式の解ー

21 ４．ウィーナフィルタのディジタルフィルタへの展開

22 線形フィルタ理論（ディジタル表記）（１） ーディジタルフィルタの応答ー
時刻 入力 出力 t = 0 x(t) x(0)Dt x(0)Dth(t) t = Dt x(Dt)Dt x(Dt)Dth(t-Dt) t = 2Dt x(2Dt)Dt x(2Dt)Dth(t-2Dt) t . . . x(kDt)Dt t = kDt x(kDt)Dt x(kDt)Dth(t-kDt) t kDt （アナログフィルタ） （ディジタルフィルタ） h((n-k)) Dt→0, kDt→t Dt=T, t = nT, t kDt

23 線形フィルタ理論（ディジタル表記）（２） ーディジタルフィルタの構成ー
・インパルス応答の応答時間を有限とする ・遅延を許容して負のインパルス応答を実現する xn+N-1 xn-(N-1) xn+N xn+1 xn xn-1 xn-N Data Vector T T T T T h-N+1 h-N h-1 h0 h1 hN-1 hN Tap Vector フィルタ遅延が計算可能 フィルタ外の現在 + (フィルタ内の時計） 未来 過去 現在

24 線形フィルタ理論（ディジタル表記）（３） ーディジタルフィルタのベクトル表記ー
Data Vector Tap Vector フィルタ出力 フィルタ hn xn yn

25 線形フィルタ理論（ディジタル表記）（４） ー適応フィルター
h （最適フィルタ？） フィルタ出力 推定誤差 |e|2が最小となるようにhを設定

26 線形フィルタ理論（ディジタル表記）（５） ー最適タップ利得の導出ー
とすると emin Non-negative

27 線形フィルタ理論（ディジタル表記）（６） ー適応フィルタアルゴリズム（最終形態）ー
h （最適フィルタ？） ディジタル型Wiener-Hopfの方程式

28 ５．広帯域伝送における周波数選択性フェージングの影響

29 マルチパス伝搬路

30 遅延波の影響

31 周波数選択性フェージング伝送路モデル ー送信機ー
送信シンボル系列 送信ベースバンド信号 送信フィルタ cT(t) 送信信号

32 周波数選択性フェージング伝送路モデル ー伝搬路ー
送信信号 受信信号 等価低域系における処理により 送信フィルタと伝搬路の合成インパルス応答

33 周波数選択性フェージング伝送路モデル ー受信機ー
受信ベースバンド信号 y1(t) 受信フィルタ cR(t) 受信信号 y(t)

34 周波数選択性フェージング下の伝送路モデル
a(t) y(t) 送信フィルタ cT(t) 伝搬路 cB(t) 受信フィルタ cR(t) 総合インパルス応答に含まれるもの ・送受信フィルタの特性（伝搬路特性の分解能を決定） ・伝搬路そのものの特性 ・検波による位相ひずみ 等化器は全てのひずみを一括して補償する技術

35 ６．判定帰還型等化器

36 判定帰還型等化器 + 等化フィルタ部 FF (Feed Forward)フィルタ FB (Feedback)フィルタ yn+N-1 yn+N
T T T T T h-1 h0 h1 . + タップ利得制御部 誤差 推定部 硬判定器 既知信号an

37 等化メカニズム（１） 伝搬路特性（直接波＞遅延波） 受信信号 Ts h0のタップ h0 yn = yn = an + (1/2)an-1
Ts h0のタップ (h0 = 1) h0 yn = yn = an + (1/2)an-1 Ts Ts h1のタップ (h1 = -(1/2)) 他のタップはゼロ 等化出力

38 等化メカニズム（２） 伝搬路特性（直接波＜遅延波） 受信信号 Ts h-1のタップ (h-1 = 1)
Ts h-1のタップ (h-1 = 1) h-1 yn+1 = yn+1 = (1/2)an+1 + an -Ts h-2のタップ (h-2 = -(1/2)) -2Ts -Ts h-3のタップ (h-3 = (1/4)) -3Ts -2Ts 等化出力

39 等化後の信号レベルが高くなるようにタップ利得を設定すると，パスダイバーシチ効果が得られる
等化メカニズム（３） 直接波が強い→遅延波をキャンセル 遅延波が強い→直接波を抑圧 等化後の信号レベルが高くなるようにタップ利得を設定すると，パスダイバーシチ効果が得られる 最適タップ利得は？ （線形自乗推定）

40 カルマンアルゴリズム タップデータ タップ利得 【初期化】 【出力と推定誤差の計算】 【タップ利得の更新】 nの更新

41 カルマンアルゴリズムとWiner-Hopfの方程式の関係
カルマンアルゴリズムにおける逐次更新式を変形すると，以下の関係が得られる（説明略） D. Godard, “Channel Equalization using a Kalman Algorithm for Fast Data Transmission,” IBM J. Res. Develop., Vol. 18, No. 3, pp , May 1974. l: 忘却係数 Wiener-Hopfの方程式

42 判定帰還型等化器の特徴 任意の変調方式に適用可能 判定値に誤りがあると特性が劣化 伝搬路変動への追随性はλに依存する
演算量が変調多値数にほとんど依存しない 判定値に誤りがあると特性が劣化 FBタップで遅延波が増幅される 伝搬路変動への追随性はλに依存する

43 ７．フレーム化された信号に対するディジタル信号処理

44 連続信号と離散信号の関係 (1) Frequency Time Time Frequency Frequency Time 【アナログ信号】
【時間波形の離散化】 サンプル間隔：Ts Frequency fs = 1/Ts 一番上の図の左に記されているアナログ時間波形のフーリエ変換は，一番上の右の図となり，これらがフーリエ変換対となります。 ・では，時間波形をサンプリングすると，スペクトルのどの部分がどのように変わりますか？ ・では，スペクトルを離散化すると，時間波形はどのように変わりますか？ ・では，図の一番上の時間波形とスペクトルをともに離散化するということは，どのような意味があるのでしょうか？ 【スペクトルの離散化】 Frequency f0 = 1/T0 Time T0

45 連続信号と離散信号の関係 (2) t f 【時間波形とスペクトル両者の離散化】 . . . . . . . . 時間窓 周波数窓
FFTが対象とする時間領域 FFTが対象とする周波数領域 ディジタル信号処理をする上での前提条件 【時間波形】 ・処理対象の波形は時間窓で抽出された波形 ・抽出された波形は時間窓を周期とする周期関数 【スペクトル】 ・処理対象は周波数窓で抽出される波形 ・スペクトルは離散スペクトル ・スペクトル間隔は時間窓の逆数 ・スペクトルは周波数上で繰り返される波形 ・スペクトルの繰り返し周期はサンプル間隔の逆数 この図が，離散時系列と離散スペクトルの関係と，FFT, IFFT処理が意味することを示しています。

46 Cyclic Prefixの意義 －CPがない場合－
1-frame Previous frame FFT window 直接波 a-2 a-1 a0 a1 a2 直接波 an-2 an-1 遅延波1 遅延波1 a-2 a-1 a0 a1 an-3 an-2 遅延波2 遅延波2 a-2 an-1 a0 an-4 an-3 Ts 2Ts この部分に周期性がない 信号がフレーム化されていない場合，1フレームの信号はそのフレームに含まれる，a0からan-1のみで構成されているわけではなく，１つ前のフレームの信号を含まれることになります。 このことは，すなわち，1フレーム信号が周期的に繰り返されていると仮想的にみなすことができなくなり，スペクトルは連続スペクトルとなります。 この場合の等化は，あらたに1タイムスロット（1タイムスロットは1シンボル長）時間が進むごとに，新たに1フレームを定義し，そのフレームに対する最適周波数特性を求めることになります。すなわち、1タイムスロットごとに，Wiener-Hopfの方程式を解き，最適周波数を求めなくてはならないことになります。 このことは，言い換えると，何らかの手法で遅延派が存在しても1フレーム信号が周期関数とみなせることができれば，その信号は離散スペクトルとなるので，離散スペクトルに対して最適係数を求めればよく，さらに，その値は，そのフレームに含まれる全シンボルに対して共通のものとなるので，最適周波数特性の更新は，シンボル周期ではなく，フレーム周期で行えばよいことになります。 では，遅延波が存在しても1フレーム信号を周期信号とみなせるようにするための手段とは何でしょうか？ 1-time slot進むごとにフレーム信号を再定義し，最適フィルタを構成しなければならない

47 Cyclic Prefixの意義 －CPがある場合－
1-frame cyclic prefix FFT window 直接波 直接波 an-2 an-1 a0 a1 a2 an-2 an-1 遅延波1 遅延波1 an-2 an-1 a0 a1 an-3 an-2 遅延波2 遅延波2 an-2 an-1 a0 an-4 an-3 Ts 2Ts この部分は（a0, a1, …, an-1）で構成される そのカギはCyclic Prefixという技術です。 CPを付加すると，フレームの末尾の信号がフレーム先頭にコピーされるので，フレーム先頭に混入する遅延信号は1つ前のフレームの信号ではなく，同一フレーム内の信号となります。それによって，1フレームの信号は，周期関数とみなすことができ，スペクトルは離散スペクトルとなります。 周期関数と見なせる 離散スペクトル（FFT）

48 Cyclic Prefixの意義 －フレーム信号の表現－
1-frame cyclic prefix FFT window h0 h0 an-2 an-1 a0 a1 a2 直接波 an-2 an-1 h1 遅延波1 h1 an-2 an-1 a0 a1 an-3 an-2 h2 遅延波2 h2 an-2 an-1 a0 an-4 an-3 Ts 2Ts では，次に，CPを付加した後の受信信号の数式表現を説明します。 CPを付加した信号は，巡回シフト行列と送信信号との積で与えられます。詳しくは次のスライドで説明します。

49 巡回行列の性質 (1) H ….. h0は，伝搬路のインパルス応答ベクトルです。これは，伝搬路行列Hの一列目です。

50 ディジタル信号処理における周波数は規格化周波数
巡回行列の性質 (2) 周波数0の成分抽出用行ベクトル 【フーリエ変換行列】 周波数(1/N)の成分抽出用行ベクトル 周波数(N-1/N)の成分抽出用行ベクトル ディジタル信号処理における周波数は規格化周波数 基本 周波数に相当 ここは本来のDFTでは1/Nとなるが，このあとDFT行列をユニタリ行列として利用するため，この係数のみ，本来のDFTと異なるものを用いている 次に，フーリエ変換行列（DFT (Discrete Fourier Transform)行列）Fを考えます。 ここで，DFT行列の1行目の成分とh0との内積をとると，h0における直流成分を抽出することになります。 同様に，DFT行列の2行目の成分とh0との内積をとると，h0における規格化周波数（1/N：基本周波数に相当）を抽出することになり，DFT行列のN行目の成分とh0との内積をとると，h0における規格化周波数（(N-1)/N (N-1)倍高調波に相当）を抽出することになります。 次に，Fとh1を定石すると，各周波数成分に対して，直線位相シフト（W0, W1, W2, …, WN-1)を与えたものとなります。このことは，時間軸での遅延が周波数軸での直線位相シフトに相当することに対応しています。

51 巡回行列の性質 (3) ….. 非対角成分は0となることに注意 周波数特性における直線位相を表している
同様に，hを構成する各ベクトルは，遅延時間に相当する位相シフトが与えられます。それをまとめてあらわしたのがFhの式です。 これに対して右からFのエルミート（転置共役行列）を定石すると，一番下の式になります。ここで，FhFHの非対角成分は0になるので、対角行列となります。 非対角成分は0となることに注意

52 巡回行列の性質 (4) まとめ フーリエ変換（DFT） これはhの固有値分解に相当 （INはN行N列の単位行列） Fはユニタリ行列
巡回行列の性質 (4)　　まとめ フーリエ変換（DFT） これはhの固有値分解に相当 以上で説明した巡回行列で構成される伝搬路行列の特徴をまとめるとこのようになります。 特に重要なのは，巡回行列の固有値展開をすると、その固有値は，比例定数を除いて伝搬路の周波数特性となり，固有ベクトルをまとめたものが、DFT行列となっています。 要点は次のスライドです。 （INはN行N列の単位行列） Fはユニタリ行列 巡回シフト行列の固有値はh0の周波数成分 巡回シフト行列の固有ベクトルはFFTベクトル

53 巡回シフト行列は，受信信号がフレーム単位で周期信号であることに対応
巡回シフト行列の意義 巡回シフト行列は，受信信号がフレーム単位で周期信号であることに対応 フレーム信号が仮想的に周期的に繰り返される スペクトルは離散スペクトルとなる 巡回シフト行列の固有値展開 固有値は伝搬路ベクトルの周波数成分 DFT行列は固有ベクトルを並べたもの

54 ガードインターバルの付加と シンボル単位のIFFT処理
【送信処理】 Δf Δf 2Δf OFDM信号 の発生 3Δf 4Δf 5Δf Frequency OFDM信号スペクトル 有効シンボル長 CP OFDMシンボル長 ＣＰ の挿入 Δf ・一部を見れば擬似周期波形 ・全体を見れば干渉のあるランダム波形 先に説明したように，周期波形はすべて離散スペクトルで表すことができます。 OFDMの場合には，各スペクトルのフーリエ係数が ポイントは以下のとおりです。 OFDMを構成する信号にはどのような特徴がありますか？ U(線スペクトル性は，どのようにして確保されていますか？） ガード区間（CP）の付加により，スペクトルはどのように変化しますか？ Frequency CP挿入後のスペクトル

55 OFDM送信機基本構成 符号化 シンボル生成部 デ－タ CP 挿入部 直交 変調 S/P IFFT フレーム化 . . . Time
時間波形 シンボル 時間波形成分 シンボル 時間波形成分 どの段階で，どの時間窓で波形を観測するかがポイントです。 各段階で，波形観測時間長とスペクトルの形状の関係を理解してください。 Frequency Frequency Frequency スペクトル スペクトル スペクトル

56 送信信号処理の数式表現 符号化 シンボル生成部 デ－タ CP 挿入部 直交 変調 S/P IFFT フレーム化
送信されるベースバンドシンボル系列： OFDMでは，uの各成分が各サブキャリアにマッピングされるので，送信信号系列が離散スペクトルそのものを示す OFDMを数式表現したものがこの図です。DFT行列とその逆変換行列はユニタリ行列です。 IFFT後の信号は，サイズNのDFT行列をFNで表す時， で与えられる．

57 受信処理時のCPの効果（確認） 【受信処理】 CP 直接波 遅延波 FFT 1OFDMシンボルの切出し 処理単位 FFT Window
これまでの説明から， ガード区間の削除が，受信信号を線スペクトル化する鍵です。 FFT Window内には，同一のシンボルからの波形のみ存在 ・FFTではWindowサイズの時間波形が繰り返されていると仮定 　- 周期波形とみなされる→線スペクトル化，サブチャネルの直交化 各サブチャネルの中央のチャネル利得のみで特性が決まる

58 OFDM受信機基本構成 デ－タ CP 除去 フレーム 分解 直交 復調 P/S FFT . . . Time フレーム 時間波形 シンボル
時間波形成分 シンボル 時間波形成分 受信機各部のスペクトルが描かれています。 各部で設定されている観測時間長はどのくらいの長さですか？ 上図で，観測時間長とスペクトル形状の関係を理解してください。 Frequency Frequency Frequency スペクトル スペクトル スペクトル

59 シングルキャリア伝送の送信機構成と数式表現
データ 符号化 シンボル生成部 Cyclic prefix 付加 直交 変調 S/P BSG フレーム化 送信されるベースバンドシンボル系列： 送信信号の時系列とスペクトル： 送信される ベースバンド信号 Tx時系列 Txスペクトル シングルキャリア OFDM

60 OFDMにおけるフェージング対策 周波数 選択性 フェージングチャネル Frequency Frequency 送信信号スペクトル
受信信号スペクトル FFT窓の適用 パイロットシンボルを用いた補償方式 CP除去 各サブチャネルの振幅・位相歪補償 （flat fading 対策） OFDM受信処理におけるスペクトルの変化をまとめています。 この図におけるスペクトル変化のポイントが理解できれば，周波数領域等化の重要ポイントは殆どクリアできます。 復号 データ Frequency 受信信号スペクトル Frequency

61 周波数領域等化の構成 送信機 Cyclic prefix 付加 データ 直交 変調 S/P BSG フレーム化 受信機 Cyclic
周波数領域等化を適用する場合の送受信機構成です。 BSGは，符号語系列から送信ベースバンド信号を生成する部分です。 Cyclic prefix 削除 データ 周波数領域等化 直交 復調 復号

62 FFT/IFFT 送信信号 伝搬路 受信信号 FFT/IFFT FFT/IFFT
各セクションにおける時間波形－スペクトルの関係を理解してください。

63 周波数領域等化器の構成 受信信号 周波数領域離散フィルタ {Wk} ウェイト 制御部 （最小自乗規範） 誤差推定部
周波数領域等化器における信号処理系統です。殆どの処理は周波数領域ですが，誤差推定部における考え方は，時間波形の二乗平均誤差最小規範に従うものです。

64 最小自乗規範に基づくウェイと制御アルゴリズム（１）
受信信号： 等化後の波形： 等化後の自乗平均誤差 最小二乗規範にしたがってウェイトの最適値を求めますが，その際，Complex Gradient Algorithmを知っていると便利です。 このスライドは結果のみをまとめて書いてありますが，具体的な導出は後のスライドに出てきます。

65 最小自乗規範に基づくウェイと制御アルゴリズム（２） 等化出力と等化誤差
【等化出力】 【等化誤差】 等化出力と等化誤差を示しています。これは，前のスライドで算出されているウェイトを適用した結果の等化出力と等化誤差です。

66 ８．ビタビ復号

67 畳込み符号化と系列推定 符号化 畳込み符号化によって隣接するビット系列に一定の関係付けをすることにより，ビット系列に一定の拘束を与える ビット系列の拘束により，発生し得ない系列が発生する 発生し得ない系列の存在により，符号語間の距離が拡大される（符号化利得の発生） 系列推定 ビット系列をトレリス図で表される状態遷移系列に置換える 状態遷移系列の拘束を，状態間の状態遷移の有無で表す 最尤系列に基づいて送信された系列を推定する

68 畳込み符号化とトレリス図 an T T cn 00 状態（sn） 1 時系列の概念なし + s0 = 00 状態（sn-1） 11 11
01 s3 = 11 s1 = 01 10 + 10 01 cn 2 00 s2 = 10 an = 0 an = 1 状態遷移図 sn – 1 an sn (cn, cn) s0 = 00 1 00 10 11 s1 = 01 s2 = 10 01 s3 = 11 1 2 状態に合流するパスの入力ビットは同じ値 (n – 1) n 00 s0 s1 s2 s3 11 11 10 時系列 の概念 の導入 00 01 01 2回0が続くと状態0に至る 10 トレリス図

69 ビット系列と状態遷移系列 終端用ビット 送信ビット系列an: 1 1 1 s0 11 11 s1 10 00 01 s2 01 s3
1 1 s0 11 11 s1 10 00 01 s2 01 s3 符号語系列: (cn, cn) 11 10 00 01 01 11 1 2 s2 s1 s0 状態遷移系列： s0 s2 s1 s3

70 最尤系列推定の原理（１） y a0 a1 y1 ML推定 存在し得る系列 {cn} = {c1, c2, …, cN}, の中で

71 最尤系列推定の原理（２） ciに無関係 定数 が最大の系列{cn}を推定 {yn}と{cn}の相関計算に相当
Turbo符号との比較のポイント が最大の系列{cn}を推定

72 最尤系列推定の問題点とビタビアルゴリズム
Nビットの系列を推定する場合，候補となる系列の数は，2N通り 推定するべきビット数が多くなると非現実的な候補系列数となる ビタビアルゴリズムの特徴 生残りパスの選択 生き残らないパスの計算を行わない （１つの状態に至るパスを１つに絞る） パス履歴の更新（ある状態に至る経路は１通りなので，その状態遷移系列と入力ビット系列は１対１に対応 終端処理 送信データ系列の最後の(K – 1)ビットを0とすることで，最終状態を状態0に持っていく

73 ビタビアルゴリズム（事前準備） 終端ビットに対応 受信符号語系列： 11 10 00 01 1.2, 0.6 -0.3, 0.1
-0.8, -0.9 -0.4, 0.6 -0.2, 0.2 0.2, -0.1 s0 s1 s2 s3

74 ビタビアルゴリズム（第1段） 受信符号語系列： 1.2, 0.6 -1, -1 s0 s1 1, 1 s2 s3

75 ビタビアルゴリズム（第2段） 受信符号語 -0.3, 0.1 s0 -1, -1 s1 1, 1 1, -1 s2 -1, 1 s3

76 ビタビアルゴリズム（第3段） ー生残りパスの処理ー
受信符号語 生残りパス -0.8, -0.9 A1 -1, -1 s0 A1: -1.6 A5 0.1 1, 1 A2: A2 A3: s1 1, 1 A3 A6 A4: 1.4 2.1 -1, -1 A4 A5: 1, -1 s2 A6: -2.0 3.1 A7 A7: -1, 1 -1, 1 A8: s3 1, -1 A8 2.2 2.3

77 ビタビアルゴリズム（第4段） 受信符号語 生き残らない -0.4, 0.6 B1 -1, -1 s0 B1: 0.1 2.3 B5 1, 1
2.1 1, 1 B3: s1 B3 B6 3.3 B4: -1, -1 B4 1, -1 B5: s2 B6: 3.1 1.9 B7: B7 -1, 1 -1, 1 B8: s3 2.3 1, -1 B8 4.1

78 ビタビアルゴリズム（第5段） 受信符号語 -0.2, 0.2 C1 -1, -1 s0 C1: 2.3 3.3 1, 1 C2: C2
4.5 C4: C4 1, -1 s2 1.9 -1, 1 s3 4.1 終端ビットなので0のみのパスを考えればよい

79 ビタビアルゴリズム（第6段） 受信符号語 0.2, -0.1 D1: -1, -1 D1: s0 3.3 1, 1 D2: D2: s1
4.5 s2 s3 終端ビットなので0のみのパスを考えればよい

80 ビタビアルゴリズム ー最終判定ー s0 s1 s2 s3 送信ビット 判定結果： s0 s2 s1 s2 s3 s1 s0 1 1 1

81 ビタビアルゴリズムの特徴 各時刻における各状態のメトリックは，ブランチメトリックの累積値 事前情報が活用できない場合の最適推定となっている
各ビットの尤度情報は蓄積されない 系列全体の推定のみを行っている （iterativeではないので各ビットの尤度情報は不要） 事前情報が活用できない場合の最適推定となっている

82 ９．ビタビ等化器

83 ビタビ復号とビタビ等化 ビタビ復号 ビタビ等化 ビタビ復号とビタビ等化の相違点
送信機側で畳み込み符号化（Modulo 2の演算での畳込み）された符号語系列を,最尤復号するアルゴリズム トレリス図における各ブランチの出力は,当該ブランチの遷移に伴って発生する符号語に相当 ビタビ等化 伝搬路が周波数選択性フェージングと見なせる場合,その特性は複素インパルス応答（複素遅延プロファイル）で規程する 符号語系列が複素遅延プロファイルによってアナログ的に畳込み積分されたと見なす トレリス図における各ブランチの出力は、当該ブランチの遷移に伴って発生する受信信号の推定値に相当する ビタビ復号とビタビ等化の相違点 各ブランチの出力 ブランチメトリックの演算 その他は全く同じ

84 ビタビ等化におけるトレリス遷移図（BPSK)
yk 暗黙で（1, 0）→（1, -1）と変換する k – 1 k s0 = 00 (-1, -1) -1.75 入力 状態 s(kT) 0.25 -1.25 T T h0 s1 = 01 (-1, 1) h2 -0.75 h1 1 0.5 0.25 0.75 + s2 = 10 (1, -1) -0.25 yk 1.25 受信信号,受信信号のレプリカとも,送信系列とh(t) の畳込みで計算 s3 = 11 (1, 1) 1.75 状態遷移gk(s’,s)に伴う出力： 状態s’： 状態遷移gk(s’,s)を発生 させる符号語ビット：

85 ブランチメトリックとメトリックの計算 ーまとめー
k k + 1 s0 s1 s2 s3 受信信号 受信信号のレプリカ

86 １０．MAP推定

87 MAP推定の基本 > < > 1 < > 1 <
受信信号yが得られたとき，送信された確率の高いシンボルを送信されたシンボルと判定する推定方式 > < H1 H0 基本ルール： 等価 > < H1 H0 ベイズの定理 1 Turboアルゴリズムで最も重要な意味を持つ項 > < H1 H0 1 ML推定

88 MAP推定における事前確率の意義 復号処理が１回のみの場合 復号処理をiterativeにする場合
事前確率は未知なので，p(a1)/p(a0)=1と仮定せざるを得ない MAPとMLは等価 復号処理をiterativeにする場合 1回目の処理ではp(a1)/p(a0)=1 2回目以降では， 前回の試行によってp(a1)/p(a0)は1ではなくなる MAPに基づくiterative処理が有利 Turboアルゴリズムの根拠

89 MAP推定に基づく復号 ー１つの復号器における処理ー
LLR（Log Likelihood Ratio） H1 > < H0 ：全受信系列{y1, y2, …, yN} akの情報をできるだけ多くの受信シンボルに拡散することが推定効果を高める 全受信系列からakを推定する RSC (Recursive Systematic Coding）の適用 無限に近いインパルス応答を有する符号化 =

90 MAP推定のための符号化器 ーRSC符号化器ー
cn = an 1 bn+2 an T T bn + bn+1 + cn 2 インパルス応答時間を長くする効果

91 an T T an T T FIR型符号化器とRSC型符号化器 【FIR型】 【RSC型】 c2n – 1 cn = an 1 + bn+2
cn = (1+z-1 + z-2)an 1 cn = (1 + z-2)an 2 状態に合流するパスの入力ビットは同じ値 状態に合流するパスの入力ビットは異なる値 (n – 1) n (n – 1) n 00 00 s0 s1 s2 s3 s0 s0 11 11 11 11 10 s1 10 s1 00 00 s2 s2 01 01 01 2回0が続くと状態0に至る 01 2回0が続いても状態0に至らない s3 s3 10 10

92 LLRの式変形（１） について 時刻k-1以前で受信系列がyj<kであり，それによって時刻k-1において状態s’に至る確率
時刻k-1の状態がs’の時，時刻kで状態sに遷移する確率 時刻kの状態がsの時，それ以降の受信系列がyj>kである確率

93 . . . . . . . . . . . . . . . . LLRの変形（２） a, b, gの物理的解釈 s’ s yj<k
1 2 3 k – 1 k k + 1 N – 1 N s0 s’ s1 s2 s s3 yj<k yk yj>k [y1, y2, …, yk – 1] [yk + 1, yk + 2, …, yN ]

94 LLRの変形（３） ー基本式ー ak – 1 (s’), gk(s’, s), bk(s)をどのように求めるか？ 逐次更新型へ

95 LLRの変形（４） ak–1(s’)の計算 周辺確率

96 LLRの変形（５） の具体的計算 g3(0,0) g1(0,0) g2(0,0) a3(0) s0 a1(0) a2(0) a0(0)=1
a1(0)=a0(0)g1(0,0)= g1(0,0) s1 a1(2)=a0(0)g1(0,2)= g1(0,2) g2(2,1) a2(1) a2(0)=a1(0)g2(0,0) s2 a2(1)=a1(2)g2(2,1) a1(2) a3(0)=a2(0)g3(0,0) +a2(1)g3(1,0) s3

97 LLRの計算（６） ーbk(s)の計算ー 周辺確率

98 LLRの計算（７） の具体的計算 終端されていることが条件 gN-2(0,0) gN-1(0,0) gN(0,0) bN(0)=1 s0
bN-1(0)=bN(0)gN(0,0) s1 bN-1(1)=bN(0)gN(1,0) gN-1(2,1) bN-1(1) bN-2(0)=bN-1(0)gN-1(0,0) s2 bN-2(2)=bN-1(1)gN-1(2,1) bN-2(2) bN-3(0)=bN-2(0)gN-2(0,0) +bN-2(2)gN-2(0,2) s3

99 LLRの計算（８） 終端について (N – 2)の状態 終端ビット s0 00 s1 10 s2 11 s3 01

100 １１．Turboアルゴリズム

101 LLRの計算（９） ーg(s’, s)の計算ー 符号語を表す 事前確率 rは受信包絡線レベル MLのブランチメトリックと同じ

102 LLRの計算（１０） ーg(s’, s)の意義ー p(ak)が不明の場合は
p(a1)=p(a0)=1/2なのでp(ak)の乗積は無意味（iterativeで意味を持つ） の意義は？ gk(s’,s) ak-1(s’) bk(s) ブランチにおける遷移確率に加えて， その遷移に至る確率 そこから終端の状態に至る確率 を掛算することで，その遷移が発生する確率を算出 符号の拘束が効いてくる（符号系列が意味を持つ）

103 LLRの計算（１１） p(ak)の取扱い Turbo符号の復号においては，すべてLLRの計算で一貫性を持たせたい（と，多分考えたはず）
p(ak)をL(ak)で表すには？ p(ak)をL(ak)で表す式

104 LLRの計算のまとめ(1) ブランチ情報 ck ak 事前情報 L(ak) 伝搬路特性の測定 Lc 受信信号系列 y l

105 LLRの計算のまとめ(2) ーLLRの分母と分子の計算ー
s0 s1 s2 s3 k – 1 k 状態遷移図 s0 s1 s2 s3 k – 1 k ak = 1による遷移 s0 s1 s2 s3 k – 1 k ak = – 1による遷移

106 ２つの系列のパリティビット間の相関を低くするため
Turbo符号のための符号器構成 ck 1 Component Encoder (1) Multiplexer 2 ck 変調器へ Inter- leaver ‘ ck 1 Component Encoder (2) 2 ck ‘ ２つの系列のパリティビット間の相関を低くするため 送信不要 T +

107 Turbo復号のための準備（１） ーgk(s’, s)の変形ー
組織符号

108 Turbo復号のための準備（２） ーLLRの変形ー
事前情報 チャネル 情報 これがComponent decoderで計算される 外部情報 符号語の1ビット目が情報ビットに等しいことを利用してチャネル情報を抽出

109 Component decoderの構成 + yk 1 yk 2 逐次処理の中で変化がない値（累積してはいけない） y 受信信号系列
- L(ak|y) 外部情報 yk 2 + 　Le(ak) =L(ak|y)-L(ak)-Lcyk 1 - L(ak) （初期値は0） 逐次処理における不要な累積を避けるため Turboアルゴリズムではここが更新される（累積してはいけない） 最終的な復号はこの値を用いる

110 Turbo復号器の構成 yk 1 yk 2 yk 2 yk 1 Le1 (ak) Component Decoder (1)
L1(ak|y) yk 2 Inter- leaver + L1(ak) Inter- leaver Le2 (ak) Component Decoder (2) L2(ak) yk 2 ‘ L2(ak|y) De-inter- leaver + yk 1 ‘

111 外部情報を他の復号器の事前情報として入力することの意義
外部情報はL(ak)と相関があるので， L(ak)の代表値として利用可能である 他の復号器に供給される情報は，当該復号器で生成される外部情報と相関の低い物理量から算出されることが望ましい 符号化利得が高くなる 符号化時のインタリーバによって容易に実現可能

112 Turbo復号におけるiterationの効果
g ( s ' , s ) k (k – 1) k = p ( yk | s = s ' , s = s ) p ( a ) k - 1 k k ak-1(0) bk(0) bk(1) bk(2) ak-1(s’) bk(s) bk(3) L(ak|y) 信頼度が改善する項

113 Component Encoderにおける終端処理
終端の目的：bk(s)の逐次計算の際， bN(0)=1として計算を開始できるようにするため gN-2(0,0) gN-1(0,0) gN(0,0) bN(0)=1 s0 bN-3(0) bN-2(0) bN-1(0) gN-2(0,2) gN(1,0) s1 gN-1(2,1) bN-1(1) s2 bN-2(2) s3 Component Encoderの終端はどうする？

114 Turbo符号化器の終端処理 ck 1 ck 2 ck ‘ 1 ck ‘ 2 終端ビット 符号語（組織符号部） (M bit)
符号語（パリティ部） (M bit) ck 1 Component Encoder (1) データ(M bit) Multiplexer 2 ck 変調器へ Inter- leaver ‘ ck 1 Component Encoder (2) これを送信しないため終端できない 2 ck ‘ データ(M bit) インタリーブ後 パリティ(M bit) 終端なし

115 Turbo復号器の終端処理 【Component Decoder (1)】 N+1 N+2 1 2 N bN+2(0)=1 s0 s1
1 2 N bN+2(0)=1 s0 s1 bN+2(1)=0 s2 bN+2(2)=0 bN+2(3)=0 s3 【Component Decoder (2)】 N 1 2 bN(0)=1 s0 bN(1)=1 s1 s2 bN(2)=1 bN(3)=1 s3 bk(s)の計算 ak(s’)の計算

116 Max-Log-MAPアルゴリズム 近似による誤差（0.35 dB） 近似による誤差（0.35 dB） 指数の計算がなくなる→計算が簡略化される

117 Log-MAP(1) ここを無視したものがMax-Log-MAP |x1-x2| fc(|x1-x2|) 0.20以下 0.65
0.20～0.43 0.55 0.43～0.70 0.45 0.70～1.05 0.35 1.05～1.50 0.25 1.50～2.25 0.15 2.25～3.70 0.05 3.70以上 0.00

118 Log-MAP(2) に， を適用する アルゴリズムは簡略化されるが，劣化はない

119 Punctured符号化Turbo符号 ck 1 ck 2 ck ‘ 1 ck ‘ 2 Component Encoder (1)
Multi- plexer 2 ck 変調器へ Inter- leaver ‘ ck 1 間引き処理部 Component Encoder (2) 2 ck ‘ パリティビットのみを消去する

120 １２．Turbo等化器

121 Turbo等化器の構成 受信信号系列 y LapoEQ(cki|y) Turbo等化器 LexEQ(cki) (MAP推定器） +
事前情報LLR + - LaprEQ(cki) Turbo符号： ・LLRは情報ビットに対してのみ求めればよかった ・符号語の1ビット目は情報ビットなので,それを利用して 　チャネル情報LLRと外部情報LLRが分離できた Turbo等化器： ・情報ビットとパリティビットの両者に対するLLRが必要 ・チャネル情報LLRと外部情報LLRが分離できない ・事前情報LLRのみがa posteriori LLRから減算される

122 トレリス図を用いた周波数選択性フェージングの表記
伝搬路のインパルス応答によるアナログ的畳込み積分 yk (0) 00 ^ h(t) s0 = 00 yk (1) 00 ^ yk (0) 01 ^ 伝搬路の インパルス応答は別途測定する h0 s1 = 01 h1 h2 yk (0) 10 ^ s2 = 10 yk (0) 11 ^ t T 2T s3 = 11 RSC符号化器（r = ½）で符号化されている x2n-1 = cn1=an (情報ビット） {xn} x2n = cn2 （パリティビット） 各ブランチの出力 ^ 入力 ^ 状態（xn-1, xn-2）

123 . . . . . . . . . . . . Turbo等化器のトレリス遷移図 s’ s yj<k yj>k yk
1 2 3 k – 1 k k + 1 N – 1 N s0 s’ s1 s2 s s3 yj<k yk yj>k [y1, y2, …, yk – 1] [yk + 1, yk + 2, …, yN ] ・畳込み符号の場合と同じ ・終端はあり得るがあまり意味はない

124 gk(s’,s)について gk(s’,s)は,(k-1)番目のタイミングにおいて状態s’におり,符号語ビットxkによって状態sに遷移する確率
事前確率 復号器から） Viterbi等化の場合はここが1/2となる 状態s’： 状態遷移gk(s’,s)を発生 させる符号語ビット： 状態遷移gk(s’,s)に伴う出力：

125 LLRの計算（Max-Log-MAP, or Log-MAP)

126 MAP推定によるa posteriori LLRの計算
状態遷移図 xk = 1による遷移 xk = -1による遷移 遷移はすべて符号語ビット単位で発生する

127 １３．Turbo等化器とTurbo復号器の連接

128 Turboアルゴリズムの基本 【基本形】 事後情報 外部情報 事後情報 受信信号 MAP推定器1 MAP推定器2 + + + + - -
事前 情報 外部 情報 【応用形】 - MAP推定器1 + MAP推定器2 + + + - MAP推定器3 + + - 必要に応じてインタリーバ／デインタリーバを挿入 外部情報を他方のMAP推定器の事前情報として利用

129 Turbo等化器とTurbo復号器の 連接処理部の構成
伝搬路 （畳込み 符号化器） データ Component Encoder Inter- leaver Mod. 【送信機】 事前情報LLRに改善があれば収束する LexDEC(xk|z) Inter- leaver LapoDEC(xk|z) + + - LapeEQ(xk) 受信信号系列y - Turbo 等化器 + De-inter- leaver Component Decoder Hard Dec. + LapoEQ(xk|y) LexEQ(xk|y) z 一定のiterationの後 ソースビットを判定 【受信機】

130 Turbo等化器出力とTurbo復号器を連接する場合のgk(s’, s) （１）
ak-1(s’) bk(s) 候補符号語： 復号器入力（事前情報LLR）： ・遷移確率は，状態s’に至った後，状態sに至るための候　 補符号　　　　　が発生する確率 ・候補符号語の発生確率は事前情報LLRから算出可能 【事前情報と符号語の発生確率の関係】

131 Turbo等化器出力とTurbo復号器を連接する場合のgk(s’, s) （２） －状態遷移確率の考え方－
受信信号ykl は，符号語ビットcklを送信した後，雑音によって擾乱を受けて得られた値 遷移確率は結合ガウス分布で与えられる Turbo等化器のLLRをSISOデコーダ入力とする場合 遷移確率は，外部情報LLRで決定される 外部情報LLRを受信信号と見なして通常のTurbo符号と同様の処理を行う 遷移確率は事前情報LLRから逆算する

132 Turbo等化器出力とTurbo復号器を連接する場合のgk(s’, s)（３） －事前LLRが得られている場合の各符号語の発生確率－

133 Turbo等化器出力とTurbo復号器を連接する場合のgk(s’, s) （５） －最終形態－

134 復号部のgk(s’, s)の近似計算（１） 1 -3 -2 -1 1 2 3 軟判定に利用される領域 -1
-3 -2 -1 1 2 3 軟判定に利用される領域 -1 は，信頼性を示しており，受信信号ykに対応する l

135 Turbo等化器出力とTurbo復号器を連接する場合のgk(s’, s)（４） －双曲線関数についてー
1 2 3 -1 -2 -3 x tanh(x)

136 復号部のgk(s’, s)の近似計算（２） 【ターボ符号単独の場合】 【ターボ等化器とMAP復号器を組み合わせる場合】
ターボ等化器出力をデインタリーブしたものを とすると Z= ターボ等化器の外部情報LLRをデインタリーブして,通常のComponent Decoderに入力すればよい

137 Component Decoderが複数ある構成
pc パリティビット（１） LapoDEC1(xk|z) zs （ソースビット） LapeEQ(xk) LexDEC1(xk|z) zp1 Turbo 等化器 Depunc. DeMUX Dec (1) + + pc-1 pt pt-1 + Dec (2) zp2 （パリティビット（２）） LapoDEC2(xk|z) LexDEC2(xk|z) + + 受信信号 LexEQ(xk|y) Punc. MUX LapoEQ(xk|y) Enc. (1) Int (2) MUX pc Hard Dec. 復号データ

138 Turbo等化器とTurbo復号器を連接する場合の注意点
インタリーブの意義 チャネルインタリーブは伝搬路をメモリレスチャネルにするため 符号化器におけるインタリーバは１つの情報ビットの影響が及ぶチャネルビットの範囲を拡大するため Turbo復号器から出力される外部情報LLR ソースビットとパリティビットの両方のLLRを出力する必要がある 送信時にパリティビットがpuncturingされている場合には,LLRにpuncturingとインタリーブを施した後,Turbo等化器の事前情報LLRとして入力する a posteriori LLRの計算法 単なるTurbo符号の場合と,状態遷移パスの加算の方法が異なる

139 A posteriori LLRの計算 ー情報ビットに対するLLRー
k – 1 k 状態遷移図 s0 s1 s2 s3 k – 1 k ak = 1による遷移 s0 s1 s2 s3 k – 1 k ak = – 1による遷移

140 符号語ビットに対する a posteriori LLRの計算法
各符号語ビットに対して分類し,加算する 【1ビット目】 【2ビット目】 (n – 1) n 11 10 (n – 1) n 11 01 (n – 1) n 00 10 (n – 1) n 00 01 このビットは情報ビットなので通常のTurbo復号と同じ パリティビット

141 Turbo等化器におけるA priori LLRの生成について
Component Decoderが複数の場合のa posteriori LLR 情報ビットに関する外部情報LLRは全てのcomponent decoderから得られる パリティビットの関する外部情報LLRは各でコーダから独立に得られる Turbo等化器のa priori LLR 情報ビットに関しては,全てのcomponent decoderからの外部情報LLRを加算する パリティビットに関しては,各component decoderからの外部情報LLRをそれぞれ対応する等化器受信シンボルに対応させる

142 １４．Turbo等化器の 多値変調への適用

143 多値QAMのためのTurbo等化器 伝搬路 （畳込み 符号化器） データ Component Encoder Inter- leaver
Mod. 【送信機】 Gray符号化 1シンボルに複数のビットを含む LexDEC(xk|z) Inter- leaver LapoDEC(xk|z) + + - LapeEQ(xk) 受信信号系列y - Turbo 等化器 + De-inter- leaver Component Decoder Hard Dec. + 各ビットに対するLLRを求める LexEQ(xk|y) z 一定のiterationの後 ソースビットを判定 LapoEQ(xk|y) 【受信機】

144 多値変調の場合の各ブランチにおける 出力候補値の算出
Q s00 s00 s1 = 01 s01 s01 s0 = 11 s02 s02 s0 s03 s03 s1 I s10 s10 s2 s11 s11 s2 = 00 s3 = 10 s12 s12 s3 s13 s13 s20 s20 sij = (si, sj) 入力 状態 s21 s21 s(kT) s22 s22 T T s23 s23 h0 s30 s30 h1 h2 s31 s31 s32 s32 s33 s33 + yk

145 各ビットの a posteriori LLRの計算
x1= 0 x1= 1 Q s00 s00 s00 s00 s01 s01 s01 s01 s1 = 01 s0 = 11 s02 s02 s02 s02 s03 s03 s03 s03 s10 s10 s10 s10 I s11 s11 s11 s11 s2 = 00 s3 = 10 s12 s12 s12 s12 s13 s13 s13 s13 s20 s20 s20 s20 s21 s21 s21 s21 s22 s22 s22 s22 s23 s23 s23 s23 s30 s30 s30 s30 s31 s31 s31 s31 s32 s32 s32 s32 s33 s33 s33 s33

146 Turbo等化の問題点 変調レベルが増すと状態数が多くなり，演算量が急速に増す 対策技術（ソフトキャンセラ技術）
多値数M，遅延波の数をLとすると， 状態数：ML-1 １つの状態から出力されるブランチ数：M 演算量はMLに比例する 対策技術（ソフトキャンセラ技術） I/Q独立の処理 I/Qのクロストークをソフトキャンセラで除去する 時空間処理によるマルチパスキャンセラ SC/MMSE

147 適応等化技術のまとめ 判定帰還型等化器 演算量は遅延波の数の2乗に比例 硬判定誤りによって誤り伝搬が発生 周波数領域等化器
演算量が比較的少ない ビタビ等化器 演算量は (変調多値数)(遅延波の数)に比例 多値変調への適用が困難 性能は判定帰還型等化器より良い Turbo等化器 SISOデコーダとの複合で良好な特性 ソフトキャンセラを用いないと演算量は多い ソフトキャンセラの活用が鍵 硬判定のような誤り伝搬がない 演算量が遅延波の数に対してクリティカルではない

148 カルマンアルゴリズムの補足説明

149 カルマンアルゴリズム（その１） (1) (2) (3) (4) (5) (3)より (6a) (6a)の変形 (6b) (7)
【(5)の右からynを乗積し，変形】 (6b), (7)より (8)

150 カルマンアルゴリズム（その２） (5) (9) (8)を適用 (10) (11a) (11b) (12) (13)

151 カルマンアルゴリズム（その３） (14) と定義すると (15) (16) (15)→(11b) (17) (12)より よって (18)
(17)→(13) (19)

152 カルマンアルゴリズム（その4） (19)→(4) (2)も適用 (16)を適用 (20) (21) (22)