JPH0783280B2 - 誤り訂正装置 - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、連続モードのディジタル通信における畳込
み符号化／ビタービ復号化を用いた誤り訂正方式に関す
るものである。

〔従来の技術〕

第３図及び第４図は従来の畳込み符号化／ビタービ復号
化を用いた連続モードの誤り訂正方式を示すブロック図
であり、それぞれ送信側，受信側を示す。第３図におい
て、１は送信データ入力端子、３はフレーム同期パター
ンを発生するフレーム同期パターン発生回路、２はこの
フレーム同期パターンよりフレームを作り、これと送信
データとを多重化する速度変換（多重）回路、４は畳込
み符号器、５は畳込み符号器４から出力される符号化デ
ータにより搬送波を変調する変調器、６は変調波出力端
子である。また第４図において、７は受信変調波入力端
子、８は変調波より符号化データを復調する復調器、９
は符号化データより多重化データを復号するビタービ復
号器であり、このビタービ復号器９において、10は枝メ
トリック計算回路、11はACS回路（ACS＝Add Compare Se
lect:加算・比較・選択）、12はパスメモリ回路、13は
最尤状態検出回路、14はトレースバック制御回路であ
る。15はビタービ復号器９により復号された多重化デー
タよりフレーム同期をとるためのフレーム同期回路、16
はフレーム同期回路15からのフレームタイミングに従っ
て元の受信データを速度変換し分離する速度変換（分
離）回路である。

次に動作について説明する。

まず第３図の送信側について説明する。送信データは、
速度変換（多重）回路２においてフレーム同期パターン
発生回路３からのフレーム同期パターンとともに多重化
され、フレームを形成する。さらにこの多重化データ
は、誤り訂正符号化を行うために畳込み符号器４におい
て畳込み符号化され、冗長ビットが付加される。さらに
この符号化データは、伝送路に適合しやすい形態とする
ために変調器５に導びかれ、該符号化データにより搬送
波（キャリア）を変調して変調波出力端子６より出力さ
れる。

次に第４図の受信側について説明する前に、まずビター
ビ復号器について説明する。一般にレート1/n,拘束長Ｋ
の畳込み符号器は第５図の様に表わされる。即ち、時刻
ｉにおいて、Ｋ個のシフトレジスタの左端より送信デー
タuiが入力すると、シフトレジスタはデータを右へ１ビ
ットシフトし、データuiと、レジスタ内の過去のデータ
ui−１〜ui−ｋ＋１とから適当な組合わせのｎ個のモジ
ュロ２の加算を行ない、それらｎ個のデータを伝送路に
符号化データとして出力する。この時、情報ビット１ビ
ットと符号化データｎビットの比1/nをレート（符号化
率）、シフトレジスタの段数Ｋを拘束長と呼んでいる。

説明の簡略化のため、ここではレート1/2,K＝３の場合
について述べる。レート1/2,K＝３の畳込み符号器を第
６図に示す。ある時刻ｉ（ｉは整数）におけるシフトレ
ジスタの記憶内容のうち、左からＫ−１（＝２）までの
内容を状態と称している。第６図の例では、現在の時刻
ｉの状態が01であり、シフトレジスタが１ビットシフト
した次の時刻ｉ＋１の状態は00となる。状態の種類は全
部で2^K-1通り存在する。この例から明らかな様に、時刻
ｉ＋１にて出力される符号化シンボルは、時刻ｉにおけ
る状態01によって決定されており、一番右端のデータに
は関係しない。

ここで状態４つ（00,01,10,11）を例にとり、これら状
態間の遷移を表わすトレリス図を第７図の様に考える。
図において、最初の開始状態は00、即ちレジスタの左か
ら２つの内容が00であり、上の分枝は０のデータ，下の
分枝は１のデータが次の時刻にレジスタに入力した場合
の状態の遷移を表わしている。即ち、時刻０において状
態00であった時、データ０が時刻１において入力する
と、時刻１の状態は00となり、また、もしデータ１が入
力すると、時刻１の状態は10となる。また、この時出力
される符号化シンボルが各分枝の上に書かれており、上
の分枝は00,下の分枝は11がそれぞれ符号化データとし
て出力される。即ち、第７図のトレリス図は、畳込み符
号器がとり得るすべての状態間の遷移を示したものと考
えることができる。

ビタービ復号法は、上記畳込み符号の一復号法であり、
米国のA.J.ビタービ（A.J.Viterbi）が提案したもの
で、その動作の詳細については、例えば論文「G.D.フォ
ーニー・ジュニア“ビタービ アルゴリズム”」（「G.
D.Forney,J_R.;“The Viterbi Algorithm",Proceeceing
of the IEEE,Vol.61,No.3,March 1973,pp.268〜278」）
に記載されている。今、例として第６図のレート1/2,K
＝３の畳込み符号器において情報シンボル00000……が
送信される場合を考える。この時出力される符号化シン
ボルは第８図に示すように、00 00 00 00…である。
今、これら符号化シンボルが伝送路に出力され、雑音に
より２ビット誤って受信されて、同図に示すように10
00 10 00 00…となったとする。この時、受信側では
次の操作を行なって送信された情報シンボルを復号す
る。即ち、受信側では、状態00から始まるトレリス図上
で各状態の尤度（メトリック）を計算する。

ここでメトリックとしては、例えば畳込み符号器のトレ
リス図（第７図）における符号化シンボルと実際に受信
された符号化シンボルとのハミング距離（不一致数）が
用いられる。第９図を用いて説明すると、同図（ａ）に
おいて、まず状態00のメトリックを０とする。第７図の
トレリス図において、時刻０の状態00から時刻１の状態
00へ遷移する場合の符号化シンボルは00,また状態10へ
遷移する場合は11であり、実際にこの時受信されたデー
タは第８図から10であるので、それぞれの分枝のハミン
グ距離（枝メトリックと称する）はそれぞれ１となる。
この値を時刻１における状態00及び状態10のメトリック
として記憶させる（これを状態メトリックと称する）。
時刻１→２の遷移においても全く同様に、第７図のトレ
リス図上の分枝上の符号化シンボルと、実際に受信され
たデータのハミング距離（＝枝メトリック）を計算し、
その状態に遷移してくる前の状態のメトリックと加算し
て、その状態のメトリックとする。この様子を第９図
（ａ）に示す。次に時刻２→３の遷移においては、各分
枝のメトリック計算は同様に行なうが、第７図のトレリ
ス図から明らかな様に、１つの状態に遷移してくる分枝
が時刻３においては２つある。従って、ここでは、ある
状態に遷移してくる２つの分枝について、その遷移して
くる前の状態のメトリック（状態メトリク）と、分枝の
メトリック（枝メトリック）とを加算し、メトリックの
少ない方（即ち尤度の高い方）を残して他は捨て、残っ
た方のメトリックを新しい状態の状態メトリックとす
る。この手順を加算・比較・選択手順（ACS手順＝Add S
elect Compare）と称している。この様子を第９図
（ｂ）に示す。以下、全く同様にして、時刻を進めてい
くと、第９図（ｃ），（ｄ），（ｅ）の様になる。

次に、実際にデータを出力する方法について述べる。上
記の様に、各時刻毎に、各状態毎で加算・比較・選択手
順が繰り返されるが、この各時刻毎の加算，比較，選択
の結果を、各状態毎に、上の分枝を選択した時は0,下の
分枝を選択した時は１という様にして、ある時間分まず
メモリに記憶させる。次にある程度このような記憶がた
まった段階で、もっとも状態メトリックの少ない状態、
即ち尤度の高い状態から、パスを前記記憶された加算，
比較，選択の結果に従ってさかのぼり、ある時刻数さか
のぼった段階で、その時のメモリに記憶されている加
算，比較，選択の結果のデータを復号データとして出力
する。この様な方法をパスのトレースバックと呼んでい
る。これは例えば第９図（ｅ）において、右端の状態00
からトレースバックを始め、９時刻さかのぼった時の状
態00に記憶されているACS手順の結果０を復号データと
して出力することに相当する。第９図（ｅ）において
は、どの状態から始めても、２時刻以内に正しいパス、
即ち送信されたパスに収束することがわかる。なお、さ
かのぼる必要のある時刻数、即ちそれ以上さかのぼって
も符号化利得の改善が得られない時刻数は、（拘束長−
１）の５倍程度であり、これをトランケーションの深さ
と呼んでいる。

次に第４図の受信側の動作について説明する。伝送路を
通って雑音とともに受信された前記変調波は、入力端子
７より入力し、復調器８により元の符号化データに復調
される。この符号化データは伝送路の雑音により誤りを
多く含むので、ビタービ復号器９に導びかれて誤りが訂
正される。ビタービ復号器９においては、前述したよう
に、送信された複合語を受信する毎に受信側で符号化器
のとり得るすべての枝の符号語を発生し、受信した符号
語との相関（前述の不一致数に相当）をとる。この相関
値を枝メトリックと称し、枝メトリック計算回路10にて
この動作を行う。次にこの枝メトリックを、記憶されて
いる各状態の現在のメトリックに加算して新しいメトリ
ックを計算し、前述したACS手順（Add Compare Select:
加算・比較・選択）をACS回路11にて実行する。なお、
上述の様にメトリックは１符号語を受信する毎に増加し
ていくため、メトリックがオーバーフローしない様に、
周期的にメトリックの減算を行う必要があるが、ここで
は特に本質的問題ではないので第４図では削除した。さ
らに、前記ACS手順により得られた各状態の加算・比較
・選択の結果は、各状態毎にパスメモリ回路12に記憶さ
れる。

次にデータの出力は、前述のように、最尤状態検出回路
13により一復号サイクル（データ１ビットを復号する時
間）の間に見つけられた最尤のメトリックを持つ状態よ
り、パスのトランケーションの深さだけ、トレースバッ
ク制御回路14によりパスメモリ回路12のトレースバック
を行い、最後にパスメモリ回路12に記憶されているデー
タ１ビットを復号データとして出力する。即ち、この方
法では、データ１ビットを復号するために、一復号サイ
クルの間にトランケーションの深さに相当する回数だけ
パスメモリにアクセスする必要がある。

パスのトレースバックにより復号された多重化データ
は、フレーム同期回路15においてフレーム同期がとら
れ、このフレーム同期タイミングに従って速度変換（分
離）回路16において元の送信データが分離された後、デ
ータ出力端子17より出力される。

〔発明が解決しようとする問題点〕

従来の連続モードのディジタル通信における畳込み符号
化／ビタービ復号化を用いた誤り訂正方式は以上のよう
に構成されているので、ビタービ復号器において、パス
のトレースバックを一復号サイクルの間に、トランケー
ションの深さ（（拘束長−１）の５倍程度）の全長にわ
たって行なう必要があり、従って伝送路のデータ伝送速
度を上げることが困難であった。

この発明は、上記のような問題点を解消するためになさ
れたもので、一復号サイクルの間にビタービ復号器のパ
スメモリに対して行なうトレースバックの回数を１回と
してビタービ復号器の復号速度を高速化し、その結果伝
送路のデータ伝送路度を飛躍的に上げることのできる畳
込み符号化／ビタービ復号化を用いた誤り訂正方式を得
ることを目的とする。

〔問題点を解決するための手段〕

この発明に係る誤り訂正方式は、 フレーム中のデータ開始時点で畳込み符号器のシフトレ
ジスタをリセットし、またフレーム中のデータの終了時
点では（拘束長−１）個のダミーデータ（符号の末尾）
を付ける様にして１フレーム単位でデータを畳込み符号
化するための制御回路と、該符号化データにフレームの
区切りを示すためのフレームパターンを付加する手段と
を送信装置に設け、 フレームパターンを検出することによりフレーム同期を
とるフレーム同期回路と、実際に受信された符号化デー
タと前記送信装置の畳込み符号化手段のとり得る符号化
データとに基づいて各状態間での枝メトリックを計算す
る回路と、該枝メトリック計算回路の枝メトリック値と
当該状態に遷移する前の状態のメトリック値とを加算し
て当該状態でのメトリック値を算出し，当該状態に遷移
する前の状態が複数ある場合にはさらに各加算結果を比
較し，最小のメトリック値を当該状態でのメトリック値
して選択するACS回路と、該ACS回路の出力である加算，
比較，選択の結果を１フレーム分記憶可能な第1,第２の
パスメモリ回路と、あるフレーム期間において前記２つ
のパスメモリ回路のいずれか一方に前記ACS回路の出力
である加算，比較，選択の結果を１フレーム分記憶させ
るとともに該期間に他方のパスメモリ回路に記憶させて
おいた１フレーム前の加算，比較，選択のデータを全て
の状態においてトレースバックし、次のフレームでは上
記２つのメモリの役割を交代させてデータを復号するた
めのトレースバック制御回路を有するビタービ復号器と
を受信装置に設けたものである。

〔作用〕

この発明においては、ビタービ復号器において、パスメ
モリ回路を２つ設け、一方のパスメモリへACSの結果を
書き込んでいる間に、他方のパスメモリにおいて１フレ
ームの期間に全フレーム長をトレースバックするから、
一復号サイクルの間にパスメモリに対して行なうトレー
スバックの回数は１回となり、復号速度が飛躍的に増大
する。また、最ゆい状態検出回路を省略できるので、ハ
ードウェア規模の大幅な削減が可能となる。

〔実施例〕

以下、この発明の一実施例を図について説明する。第１
図は送信側、第２図は受信側をそれぞれ示し、第１図に
おいて、31はフレーム同期パターン発生回路３から伝達
されるフレームの区切りに従って、フレーム開始時点で
畳込み符号器４のレジスタをリセットし、フレームの終
了時点で（拘束長−１）個の符号の末尾データを付加す
る制御回路である。また第２図において、21,22は１フ
レーム分の加算・比較・選択の結果を各状態につき記憶
する第1,第２のパスメモリ回路、23はこれら２つのパス
メモリ21,22に対し、フレーム単位で加算・比較・選択
結果の記憶とトレースバックの機能を交代させ、データ
を出力するトレースバック制御回路、24はフレーム毎に
１フレーム分の復号データの時間軸上の並びかえを行う
出力バッファ回路である。また、25はビタービ復号器で
ある。

次に動作について説明する。

本実施例では、データを畳込み符号化する際に、データ
をフレーム毎に区切り、フレームの開始時点では畳込み
符号器４のレジスタをリセットし、フレームの終了時点
では（拘束長−１）個の符号の末尾（通常オール０）を
付加している。この制御は送信側の制御回路31で行われ
る。この結果、各データはフレーム毎に完結した形とな
って畳込み符号化され、速度変換（多重）回路２によ
り、フレーム毎にフレームパターンが挿入されてフレー
ムの区切をつけ、変調器５に送られた後変調出力端子６
より伝送路に送出される。フレーム毎の畳込み符号の完
結をトレリス図に示したのが第10図である。但し、図で
は、レート1/2,拘束長３の場合について示している。

次に受信側について説明する。まず第２図の復号器８に
より復調されたベースバンド信号は、フレーム同期回路
15によりフレーム同期がとられてフレーム毎に区切ら
れ、該フレーム毎にビタービ復号器25にて次の処理がな
される。即ち、レート1/2,拘束長３の場合について説明
すると、まずフレームの開始時点においては、ビタービ
復号器のASC回路11において、状態00の状態メトリック
を０とし、その他の状態については状態メトリックを∞
（十分大きな数）とすればよい。これは、第10図のトレ
リス図から明らかな様に、フレームの開始時点では、符
号のトレリス構造が状態00から始まるように送信側の符
号器を構成しているためである。

次に、第２図の第１のパスメモリ回路21及び第２のパス
メモリ回路22の動作を次の様に制御してデータを出力す
る。即ち、あるフレーム期間におけるACS回路11出力の
加算・比較・選択の結果は、第１のパスメモリ回路21に
すべて記憶させる。この間に、第２のパスメモリ回路22
のトレースバックを１フレーム前に記憶した加算・比較
・選択の結果を用いて１フレーム分のデータの全長にわ
たって行うが、この時のトレースバックの開始状態は、
常に符号の末尾に相当する状態である。これは、レート
1/2,拘束長３のトレリス図（第10図）において、１フレ
ームのトレリス構造の終結状態00からトレースバックを
開始することに相当する。即ち、送信側で（拘束長−
１）ビットの符号の末尾をフレームの最後に付加したた
めに、フレームは、常に符号の末尾に相当する最尤状態
で終結することが受信側でわかっており、従って、この
状態からトレースバックを開始することによって、劣化
の少ない復号が可能となる。更に、次のフレーム期間に
おいては、上記第１のパスメモリ回路21と第２のパスメ
モリ回路22の役割を交代し、今度は、第２のパスメモリ
回路22に１フレーム中の加算・比較・選択結果の記憶を
行い、第１のパスメモリ回路21で１フレーム分のトレー
スバックを行なう。この様なフレーム単位のパスメモリ
への書き込みとトレースバックの制御は、フレーム同期
回路10からのフレーム同期パルスを元にトレースバック
制御回路23が行う。

次に、トレースバックにより読み出されたフレーム毎の
データは、出力バッファ回路24に１度蓄えられ、時間軸
上に並びかえ、即ち元の順序への並びかえが行われた
後、受信データ出力端子12より出力される。

このような本実施例では、ビタービ復号器においては、
一復号サイクルの間にトランケーションの深さの回数ト
レースバックするのではなく、１フレームの期間に全フ
レーム長をトレースバックするので、復号データ１ビッ
ト出力するのに要するトレースバックの回数は１回でよ
い。この結果、復号データ速度は大幅に増加でき、伝送
速度の高い誤り訂正方式が実現できる。

さらに本実施例によれば、常に符号の末尾に相当する状
態からトレースバックを開始するので最尤状態を見つけ
る必要がなく、従来ハードウェア規模が大きかった最尤
状態検出回路を省略できる効果もある。

なお、上記実施例では畳込み符号器の直後で速度変換
（多重）回路によりフレーム同期パターンと多重化する
方式を示したが、畳込み符号器の後にインターリーブ回
路を設け、伝送路のバースト誤りに対しても、強力な誤
り訂正ができるようにしてもよい。これは、従来畳込み
符号化／ビタービ復号化は、伝送路のバースト誤りに対
し劣化を受けやすかったので特に有効となる。この場合
には、第２図の受信側で、フレーム同期回路からのフレ
ーム同期パルスに従ってデインターリーブする回路が復
調器の後に設けられる。

〔発明の効果〕

以上のように、この発明によれば、送信側ではフレーム
の開始で畳込み符号器のレジスタをリセットし、終了で
ダミーデータを付加してフレーム毎に畳込み符号化が完
結するようにし、また受信側では、ビタービ復号器にお
いて実際に受信された符号化データと前記送信装置の畳
込み符号化手段のとり得る符号化データとに基づいて全
ての状態の枝メトリックを計算する回路と、該枝メトリ
ック計算回路の枝メトリック値と当該状態に遷移する前
の状態のメトリック値とを加算して当該状態でのメトリ
ック値を算出し，当該状態に遷移する前の状態が複数あ
る場合にはさらに各加算結果を比較し，最小のメトリッ
ク値を当該状態でのメトリック値として選択するACS回
路と、該ACS回路の出力である加算，比較，選択の結果
を１フレーム分記憶可能な２つのパスメモリ回路とを設
け、各フレーム毎に書き込みとトレースバックの役割を
交代させ、１フレーム分のデータを１フレーム期間の間
に１フレームの全長にわたってトレースバックするよう
に構成したので、１フレーム分の全データを復号する間
にメモリに対して行なうトレースバックの回数は１回と
なり、復号速度が飛躍的に増大し、また、最尤状態検出
回路が省略できるため、ハードウェア規模の小さい誤り
訂正方式が得られる効果がある。

【図面の簡単な説明】

第１図はこの発明の一実施例による誤り訂正方式の送信
側を示すブロック図、第２図はその受信側を示すブロッ
ク図、第３図は従来の誤り訂正方式の送信側を示すブロ
ック図、第４図はその受信側を示すブロック図、第５図
はレート1/n,拘束長ｋの畳込み符号器のブロック図、第
６図はレート1/2,K＝３の畳込み符号器のブロック図、
第７図はレート1/2,K＝２の畳込み符号器のトレリス
図、第８図は送信シンボルと受信シンボルの一例を示す
図、第９図はビタービ復号法を説明するためのトレリス
図の一例を示す図、第10図は本発明方式におけるレート
1/2,拘束長３の畳込み符号器の１フレーム分の状態遷移
を表わすトレリス図である。 ２……速度変換（多重）回路、３……フレーム同期パタ
ーン発生回路、４……畳込み符号器、５……変調器、８
……復調器、10……枝メトリック計算回路、11……ACS
回路、15……フレーム同期回路、21,22……パスメモリ
回路、23……トレースバック制御回路、24……出力バッ
ファ回路、25……ビタービ復号器、31……制御回路。 なお図中同一符号は同一又は相当部分を示す。

フロントページの続き (56)参考文献 特開 昭63−78439（ＪＰ，Ａ) 特開 昭62−233933（ＪＰ，Ａ) 米国特許4583078（ＵＳ，Ａ) 国際公開87−6081（ＷＯ，Ａ) ＣＯＭＳＡＴ ＴＥＣＨＮＩＣＡＬ Ｒ ＥＶＩＥＷ ＶＯＬＵＭＥ13 ＮＵＭＢＥ Ｒ２，（1983）「Ｓｅｒｉａｌ ｉｍｐｌ ｅｍｅｎｔａｔｉｏｎ ｏｆ Ｖｉｔｅｒ ｂｉ ｄｅｃｏｄｅｒｓ″Ｐ．315−330； Ａ．ＳＨＥＮＯＹ，Ｐ．ＪＯＨＮＳＯＮ

Claims (2)

【特許請求の範囲】
1. 【請求項１】連続モードのディジタル通信に用いる誤り
   訂正装置であって、 送信データをフレーム毎に区切って畳込み符号化する畳
   込み符号化手段， この畳込み符号化に際し、フレームの開始時点に前記畳
   込み符号化手段のレジスタの初期値を設定し、フレーム
   の終了時点に当該フレームの終了を示すダミーデータを
   挿入する制御手段， 前記畳込み符号化手段から出力されるフレーム毎に畳込
   み符号化されたデータに、フレームパターンを挿入する
   フレームパターン挿入手段， 前記制御手段とフレームパターン挿入手段にフレームタ
   イミングを供給するフレーム発生手段，及び 前記フレームパターン挿入手段の出力により搬送波を変
   調する変調手段からなる送信装置と、 受信変調波より元のベースバンド信号を復調する復調手
   段， この復調手段に接続され、フレーム同期をとるためのフ
   レーム同期手段，及び 実際に受信された符号化データと前記送信装置の畳込み
   符号化手段のとり得る符号化データとに基づいて各状態
   間での枝メトリックを計算する回路と、該枝メトリック
   計算回路の枝メトリック値と当該状態に遷移する前の状
   態のメトリック値とを加算して当該状態でのメトリック
   値を算出し，当該状態に遷移する前の状態が複数ある場
   合にはさらに各加算結果を比較し，最小のメトリック値
   を当該状態でのメトリック値として選択する，加算，比
   較，選択回路（Add Compare Select,以下ACS回路と言
   う）と、該ACS回路の出力である加算，比較，選択の結
   果を１フレーム分記憶可能な第1,第２のパスメモリ回路
   と、あるフレーム期間において前記２つのパスメモリ回
   路のいずれか一方に前記ACS回路の出力である加算，比
   較，選択の結果を１フレーム分記憶させるとともに該期
   間に他方のパスメモリ回路に記憶させておいた１フレー
   ム前の加算，比較，選択のデータを全ての状態において
   トレースバックし、次のフレーム期間ではこれら２つの
   パスメモリ回路の役割を交代させるトレースバック制御
   回路と、このトレースバックにより得られた１フレーム
   毎の復号データの時間順序を並べかえて出力する出力バ
   ッファ回路とを有するビタービ復号器からなる受信装置
   とを備えたことを特徴とする誤り訂正装置。
2. 【請求項２】前記送信装置においては、 前記畳込み符号化手段と前記フレームパターン挿入手段
   の間に、フレーム毎にデータを適当な順序にインターリ
   ーブするインターリーブ手段が設けられ、 前記受信装置においては、 前記復調手段と前記ビタービ復号器の間に、前記フレー
   ム同期手段出力のフレーム同期パルスに従ってフレーム
   毎にデータを元の順序にデインターリーブするデインタ
   ーリーブ手段が設けられていることを特徴とする特許請
   求の範囲第１項記載の誤り訂正装置。