無線通信における畳み込み符号化について

信号をどこかに伝える場合を考えると、伝えるべき本来の信号をそのまま送る様な事はあまりせずに、何らかのアルゴリズムにより少し歪めたり変形したりして送る事が多く見られます。これから述べる畳み込み符号もこのような信号変形のアルゴリズムの一つです。

通常、信号の通信は伝達すべき情報や送信波形があるシステムに入力されて、そのシステムの出力として送るべき情報を得る事ができます。このような、情報や信号に何らかの変化を与えるシステムの事を信号変換系と言います。ディジタルフィルタの様な処理系も一つの信号変換系と呼ぶ事も出来るでしょう。

図1:信号変換系

信号変換の目的は情報を別の形式に変換して、通信経路及び受信時に発生する符号誤り(つまり伝送時のエラー)を極力減らす事に目的がありますが、一般的にそのような信号変換系は、入力をx_n 出力をy_nとすると式:1の一般式で表わす事が出来ます。

$\displaystyle y_n$ $\textstyle = h_0x_n + h_1x_{n-1} + \cdots + h_0x_n + \cdots +h_{-1}x_{n+1} + h_{-2}x_{n+2} + \cdots$
$\textstyle = \sum_{k=-\infty}^\infty h_kx_{n-k}$	(1)

式:1で表される複数の数列から一つの数列を求める演算を畳み込み[convolutional]と呼びます。

図2:畳み込み演算

なぜ畳み込み符号化を行うのか

通常、伝送路では遅延波やドップラーシフトよる信号の歪み,酸素分子や雨などによる減衰,そして雷や太陽風による白色雑音等の誤りを起こさせる原因が数々とあります。

先程も述べたように、信号変換の目的は情報を別の形式に変換して、通信経路及び受信時に発生する符号誤りを極力減らす事に目的があります。

通信路の為の符号変換は、ある規則にしたがった方法で余分に情報を挿入する事により、送るべき情報(情報源符号)に冗長性を加えます。そして、受信機側は通信路によって引き起こされる誤りを検出し、それを訂正する事が可能になります。

このような伝送路の誤りを減らす事が出来るような符号化方式は、ブロック符号と畳み込み符号の２種類に分別する事ができます。

図3:伝送路の誤り

畳み込み符号化とは

畳み込み符号化の出力は、２進数のシフトレジスタの配列により生じ、その出力された情報は前後の符号の記憶を持ます。

図4を例に取った場合、入力には0または1が順次入力されD¹に入る事になり、各bitに関連づけられた排他的論理和の計算の結果が、出力端子g0,g1に出力されます。これらの出力が畳み込み符号化されたbitになります。

図4:畳み込み符号器の例

図4の場合、1bitの入力に対し出力は2bit発生することになりますが、入力と出力の比率を 符号化率 Rと呼び、この場合はR=1/2と表します。

また、1bitの入力情報が影響を受ける範囲の事を拘束長:K[Constraintlength] と呼び、拘束長はK=3となります。

そしてbitを入力する事により変化するD¹やD²の取りうる値を内部状態と言い、拘束長がKの時2^(k-1)状態がある事を表します。
内部状態数は、畳み込み符号化された情報をもとの情報に復元する逆畳み込み[Deconvolution]を行う時に重要です。

例えば、送信側では送った情報を、受信側で計算しやすい様に送るべき情報系列の一番最後に''ゼロ''をk-1個付加します。これにより畳み込みを行った時の内部状態は必ず0となるので受信側は最初と最後は内部状態は0となる事を前提に予測する事が出来ます。

0か1かが入力された時の出力bitと内部の状態はオートマンという表現により表す事が出来ます、図5では拘束長2符号化率1/2の時にbitを入力した場合に、取り得る内部状態と出力されるbitをオートマン表現したものです。

図5:オートマン表現による畳み込み符号器の状態

これらの事柄を式で表すと、D¹やD²は遅延演算子[Shift Register]と考えられるから、式：2のように表す事ができます。

では実際に、図4の様な回路に情報系列 X を入力する場合を考えて見ましょう。

X=01001(3)

最初は内部状態をstate 00(D¹とD²が共に0の状態)にして開始します。また、式:3の様な有限長の情報を符号化する場合、誤り訂正能力を向上させる為や計算を簡単にする為、K-1個の"0"[TerminateBit]を挿入したりもします。

これにより符号化の始めはstate 00となり符号化終了時にもstate 00になります。式:3に終端bitを加えたもの式:4がです。

$\displaystyle \hat{X}=01001 \quad 00$ (4)

そして、Xhatを式:(2)に従い畳み込み符号化すると、符号化系列Yが得られます。

$\displaystyle Y= 00 \quad 11 \quad 01 \quad 11 \quad 11 \quad 01 \quad 11$ (5)

先程は、内部状態を表すオートマン表現を紹介しましたが、この表現であると時系列的な変化を見るのには適していません。時系列データの場合に、現在の内部状態と出力を表す方法としてトレリス線図があります。図6は符号化率1/2,拘束長=3の時に取り得るパスを表したものです。

図6:トレリス線図

そして、図7は式:4を畳み込み符号化した場合に遷移する状態を表したものです。

図7:Xhatを畳み込んだ時の状態の遷移図

畳み込み符号化とは

受信機の復調器はどのような2進ディジット情報が伝送路を伝って受信されているかを推定しながら受信します。この時復調器は、1が受信されたにもかかわらず0が受信されたと判定をしたり、その逆を判定したりします。と言う事は復調結果の情報には誤ったディジットが含まれたままで復号器に伝って来る場合があります。復号器の目的は復調出力の誤りを含んだディジットを受け入れ、情報源系列に一番近い情報の複製を再生することです。

これらのエラーを含んだ信号を復号する方法は幾つか存在しますが、最尤復号法 が広く一般的に使用されています。最尤復号法とは受信側が受けた、エラーが含まれている可能性がある受信系列を

$\begin{eqnarray*}\hat{Y} = \hat{y}_1 \hat{y}_2 \hat{y}_3 \cdots \hat{y}_m \cdots\end{eqnarray*}$

とした場合、送信側から畳み込み符号化され伝送路に送信された情報、いわゆる伝送系列

$\begin{eqnarray*}Y = y_1 y_2 y_3 \cdots y_m \cdots\end{eqnarray*}$

に最も近い情報系列を推定する復号化です。

最尤復号法アルゴリズムとしてはViterbi氏にによって考案されたビタビアルゴリズムが有名であり、短い拘束長の符号に適応されるビタビアルゴリズムは宇宙通信やデジタル無線電話等に応用されています。

ハミング距離

ビタビアルゴリズムを理解するにあたっては、ハミング距離の概念を知る事が重要です。ハミング距離を本などで見ると次のように定義されてます。

長さがm個ある２つの系列

$Y=y_0y_1 \cdots y_{m-1}$	(但し $y_i,\hat{y_i} \in {0,1}$ )
と
$\hat{Y}=\hat{y_0}\hat{y_1} \cdots \hat{y}_{m-1}$

の時ハミング距離 $d_H(Y,\hat{Y})$ は食い違っているbitの個数で表され、次のように定義できる。

$\displaystyle d_H(Y,\hat{Y})= \sum_{i=0}^{m-1} Y \oplus \hat{Y}$

(6)

これはどういう事かと言うと、例えば Y=10101010 と言う系列がある時、それぞれのハミング距離は下記のようになります。

$\hat{Y}=10101010$ とのハミング距離は $d_H(Y,\hat{Y})= 0$
$\hat{Y}=01010101$ とのハミング距離は $d_H(Y,\hat{Y})= 8$
$\hat{Y}=11110000$ とのハミング距離は $d_H(Y,\hat{Y})= 4$

この事から分かるように、ハミング距離は同一ディジット位置の差異の個数であり、ハミング距離が小さい事と２系列の符号がより近い事は同意である事が理解出来るでしょう。

受信した情報の誤り率が高く、全ての誤りを訂正出来なかったり、符号自信が誤り訂正能力を待っていなかった場合、復号は符号語との比較により達成され、この時受信した情報を考えられるだけの符号語と比較し最近接整合のもが送信された情報であると予測します。そして予測時の近接の測度にハミング距離はしばしば用いられたりします。

しかし、ハミング距離による表現は語の長さ(bit長)が大きく、多くの符号語と比較しなければならない様な場合、この手法はあまり魅力的ではありません。

Viterbi復号

Viterbi復号は最尤復号化の一種であり、送信側で畳み込み符号化を行った時に通過したリトレス線図上の経路に最も近いパスを選ぶ事です。もちろん受信側では畳み込み時に通過した真のパスは知らないので、畳み込み符号化時に取り得る、全てのパスの中から最も近いパスを選ぶ事になります。

ここで、最も近い経路を選択する時の基準となるのがハミング距離であり、Viterbi復号ではトレリス線図のTi時点でのそれぞれのハミング距離を求めます(これを枝メトリック[Branch Metric]と呼びます)。そして、ハミング距離の総和(これをパスメトリック[Path Metric]と呼びます)が最小となる解を求める事により最も近いパスを検索して行く事になります。

では実際に、Viterbi復号の手順を説明して行きましょう。復号化するデータは、「畳み込み符合化とは」の項で、式:2に畳み込み符号化を行った、

$\begin{eqnarray*}Y= 00 \quad 11 \quad 01 \quad 11 \quad 11 \quad 01 \quad 11\end{eqnarray*}$

を使います。ただし、このデータは伝送路を通り誤りを含んで

$\begin{eqnarray*}\hat{y}= 00 \quad 1{\bf0} \quad 01 \quad 11 \quad {\bf0}1 \quad 01\quad 11\end{eqnarray*}$

となったと仮定します。

まず初期状態(state 00)の時''00''が受信されますここから延びるパスは「''00''を出力するパス」と「''11''を出力するパス」の２通りが存在し、これらのパスメトリック(以下pm)とブランチメトリック(以下bm)は

「受信データ00」と「00を出力するパス」のハミング距離は0であるからbm=0,pm=0となります。
「受信データ00」と「11を出力するパス」のハミング距離は2であるからbm=2,pm=2となります。

これは、図8の様に表す事が出来ます。

図8:初期状態時のメトリック

次に時刻1Tで''10''が受信されます、時刻1Tでは内部状態がstate 00とstate01が存在し、それぞれ''00'',``11'',``10'',``01''を出力するパスがあります。

「受信データ10」と「00を出力するパス」のハミング距離は1であるからbm=1,pm=1となります。
「受信データ10」と「11を出力するパス」のハミング距離は1であるからbm=1,pm=1となります。
「受信データ10」と「01を出力するパス」のハミング距離は2であるからbm=2,pm=4となります。
「受信データ10」と「10を出力するパス」のハミング距離は0であるからbm=0,pm=2となります。

図9:1T時の状態

次に時刻2Tで''10''が受信されます、時刻2Tでは全ての内部状態が存在し、それぞれ''00'',``11'',``10'',``01''を出力するパスがあります。ここでも前回と同様にメトリックを計算して行きますが、今までの状態の遷移とは異なることが起きます。

図10を見るとわかるように、state 00に入るパスは2つあります。この場合、ここからの経路は2つとも同一であるはずであるから、2つのパスのパスメトリックスを比較してハミング距離の小さい方を選択します。この選択されたパスの事を残存経路[Survivor Path]と呼びます。この場合は、state00=3,state10=4であるので、ハミング距離が小さいstate00が生き残る事になります。

図10:2Tで発生する生き残りパス

これを最後まで行うと図11の様なパスを通る事になります。図中で点線で表したモノは生き残れなかったパスであり、細い実線は生き残ったが最適なパスではないものを表します。

図11:Viterbi復号化による残存経路の状態

ここで最後のパスメトリックスに注目すると、state00の値が最小である事がわかります。つまり7Tの時点でstate00に来る経路が最も確からしいと言う事です。

では、最後の時点で同じ値が存在した場合、どのように最適なパスをどのように選べば良いのでしょう？これは、畳み込み符号化を行う所で、符号化を行う前にK-1個の''0''を挿入しました。これは畳み込み符号が終了した時点での内部状態をstate00にする為であり、受信側では畳み込みの終了時にはstateが''00''になる事を「知っている」のでstateが''00''になるパスを選択すればいい事になります。

では、時点7Tに来る経路を逆にたどって見ましょう。viterbi復号の結果選択されたパスの復号bitは

$\displaystyle OutBit=0100100$

(7)

と正しく復元されたbitが出力されるはずです。

終りに

ここまで説明して、畳み込み符号化復号化理解できたでしょうか？一見複雑怪奇に見えるViterbi復号ですが、Viterbi復号は異なるbitの個数を数え、その数の一番少ないパスを選択していくだけの簡単なアルゴリズムである事が解ると思います。

通常の通信でのViterbi復号は、より正確に復号を行う為、受信bitだけで行うのではなく、Soft bitが付加されたかたちの軟判定復号という手法が存在します。Soft bitはMLSE等により付加され、遅延波(ゴースト,エコー等)を除去する役割を担います。

誤り訂正率が非常に高いViterbi復号ですが、データの長さが大きくなると、残存経路を蓄積する為に必要なのメモリーが大きくなるとか、演算量が増えて処理が間に合わなくなる等の欠点があります。しかし無線通信ではViterbi復号は非常に一般的になっており、DSP化やゲートアレー化がなされているようです。

無線通信における畳み込み符号化について

Introductions

なぜ畳み込み符号化を行うのか

畳み込み符号化とは

畳み込み符号化とは

ハミング距離

Viterbi復号

終りに

参考リンク