数理解析研究所講究録 1420 巻 2005 年 63-67

63

ターボ符号の構成と復号法
関西学院大学理工学部情報科学科
井坂元彦

1

ターボ符号の特徴と特性

多くのディジタル通信系では, 通信路上での雑音をはじめとする様々な要因によって, 送信された記号が反転するなどの誤りが引き起こされる. その結果とし通信品質の劣化や伝送速度の低下が引き起こされることから, 信頼性向上のために誤り訂正符号が現在までに広く用いられている, 特に畳込み符号やり一ド.て,またそれらを組み合わせた連接符号が実用上の代表例として挙げられ, 移動通信やストレージシステムにおいて重要な役割を果たしてきた.
符号理論における研究対象は長年, 代数的に構成される符号や畳込み符号など符号長が (実質的に) 比較的短く, 構造に富んだ符号が中心となってきた. 一方, 低密度パリティ検査 (LDPC: Low-Density Parity-Check) 符号 [1] やターボ符号 $[2, 3]$などの, ランダム的に構成される符号と確率的反復復号法が近年注目を浴びてきた. これらの符号化および復号法は, シャノンの通信路容量に迫る特性を示してソロモン符号,多くの通信路で従来の符号を大きく上回る耐雑音性能を備えていることかおり,理論応用の両面で目覚しい研究の進展が見られている.
ターボ符号の誤り率特性の特徴は, 図 1 にまとめられる. ここでは, 定義は後述するが, 符号化率 $R=1/2$ , 符号長 $N=4000$ , 及び 20000 のターボ符号 $[2, 3]$ が加法性ガウス雑音通信路で伝送され, 受信側で反復復号を行った結果を示している. 但し, ターボ符号は, いずれの符号長の場合も文献 $[2, 3]$ と同じ符号化器を用に値をいており, 反復復号の反復回数は 18 回としている. この通信路は,の正規分布に従う雑音成分 $N$ に対して, 受信とる送信信号 $X$ と, 平均 0, 分散
信号 $Y$ が $Y=X+N$ として与えられるものである. グラフの横軸は情報ビットあら, 活発な検討がなされ,$\{\pm 1\}$$\sigma^{2}$たりの信号対雑音電力比 $E_{b}/N_{0}(\mathrm{d}\mathrm{B})=10\log_{10}1/(2R\sigma^{2})$ であり, 従ってこの数値が大きいほど雑音電力が低くなっている. 縦軸はビット誤り率 (BER: Bit ErrorRate) を対数表示したものであり, 併せて従来から移動通信などで広く実用化されている 64 状態のトレリスにより最尤復号される畳込み符号のビット誤り率特性ビット誤り率の理論的限界を示すシャノン限界も示している。 図から理解される通り, 十分な符号長をもつターボ符号. LDPC 符号に対して反復復号を施すと,と,ある雑音レベルを境に急激に誤り率が低下し, そのためこの現象が見られるの範囲はウォーターフォール領域と呼ばれる. 一方, さらに通信路の状況$E_{b}/N_{0}$84が良化すると, 誤り率の低下が緩やかになり, このエラーフロア領域では, 反復復号法は最尤復号とほぼ同等の特性を実現しているものと考えられる. よって, このエラーフロア領域の特性が, 符号が本来有している誤り訂正能力を示しており,における振る舞いは反復復一方ウォーターフォール領域及びそれより低い号の性質により引き起こされたものであると解釈できる.
$E_{b}/N_{0}$三の$\mathrm{o}$$\check{\underline{\varpi 0}}$$\mathbb{E}\mathrm{b}/\mathrm{N}0(\mathrm{d}\mathrm{S}\mathrm{l}$図 1: 符号化率 1/2 のターボ符号と畳込み符号のビット誤り率特性

ターボ符号や LDPC 符号に類する符号を設計する上では, 反復復号を適用した場合と, 何らかの意味において 「最適な」 復号を施した場合 (またこのように,は反復復号がそれとほぼ同等の特性を達成している場合) の双方について配慮しておく必要がある. 一般に符号長が長くなるほど, 双方の場合について復号特性が改善されることも図 1 から読み取れるだろう. 結果として, 例えば BER $=10^{-5}$を与えるのに必要なら$1\mathrm{d}\mathrm{B}$を基準としたとき,このターボ符号はシャノン限界か以内に迫っており, 畳込み符号に対して以上の利得を実現している.
$E_{b}/N_{0}$$3\mathrm{d}\mathrm{B}$2

ターボ符号の符号化と復号

2.1

ターボ符号の符号化器

図 2 に示す通り,ターボ符号の符号化器は, 複数の畳込み符号化器がランダムインタリーバを介して並列連接された構造となっている. すなわち, $K$ ビットの情報系列, 及びインタリーバにより交錯された系列の双方に対して畳込み符号化を行う. なお,

このターボ符号では, 1 ビットの入力に対して 3 ビットが出力されるため, 符号化率は $R=K/N=1/3$ となるが, 畳込み符号化器出力の一部を符号85

語に含めない (パンクチャ) ことで, 多様な符号化率に柔軟に対応できる. なお,符号化器が帰還結線をもつことと, インタリーバによる置換を行うことで, 生成される符号が 「ランダム的」 な性質をもつことになる. 図 1 に特性を示した畳込み符号は, 符号化器内に 6 個の遅延素子を有するものであるが, 図 2 のターボ符号の符号化器では, より複雑度の低い符号を連接することで, 訂正能力の高い符号を構成していることに注意されたい.

図 2: ターボ符号の符号化器

なお, 図 1 において, エラーフロアが現れているのは, ターボ符号の最小距離が比較的小さいためである (ただし, インタリーバをランダムに選ばずに, ある工夫を施すことで, エラーフロア領域での特性を大幅に改善することは, 特に符号が長い場合に可能である). ランダムにインタリーバを選ぶ場合, BER は符号長 $N$ に対してほぼ反比例して低下することが知られており [4], これはインタリーバ利得と呼ばれている. 図 1 に示される符号長の異なるターボ符号の特性も,これに即した値となっていることが観察される
一方, 畳込み符号の連接の仕方として, 直列型の符号化法も知られており, 符号化率 1/2 の畳込み符号と符号化率 1 の符号化器を連接した SCCC の例を図 3 に示す. また,SCCC の場合には適切に設計することで BER とワード誤り率の双方に対してインタリーバ利得が得られ, エラーフロア領域における誤り率を低く抑えることができる. 図 1 の数値結果は, 図 3 の符号化器を用いた符号長 4000 の場

ウォーターフォール領域の誤り率はターボ符号に劣る一方で, エラーフロアは示された誤り率の範囲では現れていない.

合のものであり,2.2

ターボ復号

一般に, 与えられた符号に対して最適な BER 特性を実現するには, 受信ベクトルを用いて, 符号語の各シンボルに関する事後確率計算を行えばよい. しかし,

B8interleaver
図 3: 直列連接畳込み符号 (SCCC) の符号化器の例

ターボ符号のようにランダムなインタリーバが用いられる場合に, そのような復号を効率的に実現するアルゴリズムはこれまでに知られていない.
そこで, ターボ符号では, 連接した 2 つの符号化器に対応する復号器を用意し,双方で符号語の各シンボルに対する最大事後確率 (MAP) 復号法を適用する. ここで, 連接されている符号は図 2 に示される通り, 遅延素子数が少ない畳込み符号であるため, 効率的な復号が可能である. ここで得られる外部情報と呼ばれる数値を, 各シンボルの尤度に関する情報として, もう一方の復号器において用いる手順を繰り返すのが, 反復復号法またはターボ復号法と呼ばれる手法である. 図
4 に示されたターボ復号器は, 2 つの軟入力軟出力 (SISO) 復号器から構成されている. SISO 復号器は, 受信信号と, 他方の復号器から得られる各シンボルの事前確率を入力とし, MAP 復号を行った結果得られる各シンボルの外部情報を出力するもので, 通常対数領域で計算が行われる.

図 4: ターボ復号器

ターボ符号では, 符号長が無限である場合の確率計算アルゴリズムを, 符号長が制限されている場合に適用するため, その最適性や収束性は一般に保証されない.
このため図 1 に示される通り, 符号長が小さくなるにつれて, ウォーターフォ–

67
ル領域での誤り率特性に劣化が見られることになる.

参考文献[1] Gallager, R.G., Low-density parity-check codes, MIT Press, 1963, available
from http://web.mit.edu/gallager/www/pages/ldpc.pdf[2] Berrou, C., Glavieux, A., and Thitimajshima, P., Near Shannon limit errorcorrecting coding: Turbo codes, in Proc. of IEEE International Conference
on Communications (ICC93), Geneva, Switzerland, pp.I064-1070, May 1993.
[3] Berrou, C. and Glavieux, A., Near Optimrun error-correcting coding: TurboOct. 1996.
codes, IEEE Rans. on Commun., vo1.44, no.10,$\mathrm{p}\mathrm{p}.1261- 1271_{7}$[4] Benedetto, S. and Montorsi, G., Unveiling Turbo codes: Some results onparallel concatenated coding schemes, IEEE Trans. on Inform. Theory, vo1.42,no.2, pp.409-428, March 1996.