JPH0361377B2

JPH0361377B2 -

Info

Publication number: JPH0361377B2
Application number: JP29762386A
Authority: JP
Inventors: Masaru Moriwake; Atsushi Yamashita
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1986-12-16
Filing date: 1986-12-16
Publication date: 1991-09-19
Also published as: JPS63151227A

Description

【発明の詳細な説明】〔目次〕概要産業上の利用分野従来の技術（第９図〜第１２図）発明が解決しようとする問題点問題点が解決するための手段（第１図）作用（第２図）実施例実施例装置の構成（第３図、第４図）パストレースの説明（第２図、第５図〜第７図）パストレースの再開方式の説明（第８図）発明の効果〔概要〕ノード番号とそのノード番号に対応するパスメ
モリの内容とを用いて当該ノード番号で生き残り
として選択された側のノード番号を求めることを
繰り返して最尤パスをトレースし、最後に到達し
たノード番号の２進数の最上位桁を復号出力とす
るパストレース方式のビタビ復号器。

〔産業上の利用分野〕

本発明はパストレース方式のビタビ復号器に関
する。

ビタビ復号器は、畳み込み符号の最尤復号法に
使用されるものであり、既知の複数個の符号系列
のうち、受信符号系列に最も符号距離が近いパス
を最尤パスとして選択し、この選択されたパスに
対応して復号データを得るものであり、誤り訂正
能力が高いことから衛星通信などの復号器として
使用されている。

〔従来の技術〕

ビタビ復号器は、分配器とACS回路とパスメ
モリとを主要素として構成される。第９図は、拘
束長Ｋ＝３のビタビ復号器の一例を示す。図中、
１は分配器、２はACS部、３はパスメモリであ
る。この分配器１には直交変調の復号信号Ｉ，Ｑ
が受信符号として入力されており、分配器１はこ
の受信符号から各ノード毎のブランチメトリツク
を計算し、そのブランチメトリツクをACS部２
に与える。

ACS部２は、符号化器で生成される符号を第
１０図に示すような格子状表現した場合のノード
にそれぞれ対応するACS回路２（０）〜２（３）
からなり、各ACS２（０）〜２（３）はそれぞ
れ加算器と比較器とセレクタとからなる。各
ACS回路２（０）〜２（３）には分配器１から
のブランチメトリツク値の他に、第１０図の格子
状表現のノードが選択し得る２つのパスに相当す
る他のACS回路からのパスメトリツク値がそれ
ぞれ入力されている。ACS回路２（０）〜２
（３）は、入力されたブランチメトリツク値に１
シンボル前のパスメトリツク値を加算して２つの
パスに対応する新たなパスメトリツク値を計算
し、これらのパスメトリツク値を比較器で比較し
てパスメトリツク値の小さい方を生き残りパスと
して選択し、その選択したパスを示すパス選択信
号と選択したパスメトリツク値とを出力する。

パスメモリ３はACS部２からのパス選択信号
が加えられて、生き残りパスの経歴が記憶される
ものであり、パスメトリツク値が最小となる経歴
のパスメモリの内容が復号出力となる。このパス
メモリ３はセレクタとフリツプフロツプとからな
るパスメモリセルを多段に接続した構成、あるい
はRAMを用いた構成が可能である。

第１１図は従来例の拘束長Ｋ＝３の場合のパス
メモリのブロツク図を示す。同図において、２
（０）〜２（３）はACS回路であり、ACS回路２
（０）〜２（３）、MS１１〜MS４３はパスメモ
リセルである。図中にはパスメモリが３段のみ示
してあるが、通常は拘束長の５、６倍程度の段数
が用いられる。またパスメモリセルMSij（ｉ、ｊ
＝１、２、３…）は下方に拡大して示すように、
それぞれセレクタ４４とフリツプフロツプ４５と
から構成される。セレクタ４４はACS回路から
のパス選択信号によつて選択動作し、その選択出
力をフリツプフロツプ４５のデータ端Ｄに与え
る。フリツプフロツプ４５の出力端Ｑからの出力
信号は次段の２個のパスメモリセルに供給され
る。

初段のパスメモリセルMS１１，MS２１，MS
３１，MS４１には“０”、“１”、“０”、“１”が
それぞれ初段入力として印加され、パス選択信号
に対応して順次に内部状態を遷移させるようにシ
フトされることになる。すなわち、復号サイクル
毎にACS回路２（０）〜２（３）で生き残りパ
スと判定した側のパスメモリセルの内容をパス選
択信号を用いて他側のパスメモリセルに転送す
る。

第１２図はランダムアクセスメモリ（RAM）
を用いてパスメモリを構成した場合の従来例を示
すブロツク図である。図において、５１は初段入
力設定部、５２，５３はRAM、ADはアドレス
入力端、DIはデータ入力端、DOはデータ出力
端、５４は多数決回路等からなる出力処理部であ
る。

このパスメモリは２個のメモリを用いて多重化
したものであり、例えば前述のパスメモリの或る
パスメモリセルに相当する或るノード番号Ｉにお
いてメモリ５２のアドレスに「Ｉ／２」と、2^K-1
＋「Ｉ／２」とのうちの生き残りとして選択され
た方のノード番号を設定し、またメモリ５３のア
ドレスにＩを設定して、メモリ５２のデータ出力
端DOからメモリ５３のデータ入力端DIにデータ
（パス情報）を転送する。これを全ノードについ
て行い、出力処理部５４から復号出力を導出す
る。次の復号サイクルではメモリ５３のデータ出
力端DOからメモリ５２のデータ入力端DIにデー
タ（パス情報）を転送する。なお、前述の「Ｉ／
２」は、Ｉ／２を越えない最大の整数を示すガウ
ス記号である。

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

パスメモリを第１１図に示すような、セレクタ
４４とフリツプフロツプ４５とからなるパスメモ
リセルで構成した場合、RAMのように高集積化
することが困難である。また第１２図に示すよう
にRAMで構成しあ場合、パスメモリを高集積化
することが可能となるが、多重化してRAMを使
用しているためRAMに対するアクセス回数が増
大し、復号処理速度を向上させることが困難であ
る。例えば拘束長Ｋ＝７の復号器の場合、１復号
サイクルあたりメモリ５２，５３を64回アクセス
する必要がある。多重度を低くしてアクセス回路
を減少させることも可能であるが、その場合、メ
モリの個数が増加する。

したがつて、本発明の目的は、高集積化が容易
なRAMを使用しつつ復号処理速度の向上が可能
なパストレース方式を用いたビタビ復号器を提供
することにある。

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

第１図は本発明に係るビタビ復号器の原理ブロ
ツク図である。

本発明に係るビタビ復号器は、受信符号から各
ノード対応にブランチメトリツク値をそれぞれ計
算する分配器１、各ノード対応に設けられた複数
のACS回路２（０）〜２（ｎ）からなるACS部
２であつて、各ACS回路２（０）〜２（ｎ）は、
分配器１からのブランチメトリツク値に基づいて
選択し得る２つのパスについてのパスメトリツク
値を演算し、その演算結果を比較して２つのパス
から生き残りパスを選択し、生き残りパス選択を
示すパス選択信号PS（０）〜PS（ｎ）を出力する
もの、パス選択信号PS（０）〜PS（ｎ）を各ノー
ド対応に所定段数にわたり記憶するパスメモリ
３、任意のノードのノード番号Ｎ（０）〜Ｎ（ｎ）
と該ノード番号に対応するパスメモリ３のパス選
択信号PS（０）〜PS（ｎ）とに基づいて前段で生
き残りとして選択されたノードのノード番号を演
算することを所定段数にわたり繰り返すパストレ
ース制御部４、パストレース制御部４でトレース
されたノード番号を所定段数にわたり記憶するト
レースメモリ５を具備する。復号出力としてはト
レースメモリ５の所定段目のノード番号の２進撰
の最上位桁が用いられる。

ACS部２は、拘束長Ｋの場合、2^K-1個の回路か
らなり、例えばＫ＝４のときはACS部２は８個
のACS回路２（０）〜２（７）からなり、各
ACS回路２（０）〜２（７）は８個のノードに
それぞれ対応している。８個のノードには０から
７までのノード番号がそれぞれ付されている。各
ACS回路２（０）〜２（７）からはパス選択信
号PS（０）〜PS（７）がパストレース制御部４に
与えられる。

またACS回路２（０）〜２（７）で計算され
たパスメトリツク値PM（０）〜PM(7)のうちから
最小のパスメトリツク値を検出する最小パスメト
リツク検出回路を備えることも可能であり、その
場合、検出された最小パスメトリツク値に対応す
るノードのノード番号がパストレース制御部４に
送られる。

〔作用〕

本発明のビタビ復号器によるパストレース動作
を第２図を参照して以下に説明する。

第２図はパストレース動作説明図であり、図中
には、各ノードのノード番号０〜７（並びにその
２進数表示）、そのノード番号におけるパスメト
リツク値、そのノード番号に対応するパスメモリ
内のパス選択信号がそれぞれ描かれている。パス
メモリの段数は拘束長（この場合はＫ＝４）の５
〜６倍程度が望ましいが、説明を簡単にするため
第２図には８段のみが示されている。

まず、ACS回路２（０）〜２（７）は通常の
ビタビ復号器のものと同様に動作してパスメトリ
ツク演算、演算結果の比較により生き残りパス選
択を行い、パス選択信号PS（０）〜PS（７）
（“０”または“１”）を出力する。このパス選択
信号PS（０）〜PS（７）はパスメモリに書き込ま
れる。この場合、このパス選択信号は生き残りと
して選択された側のノード番号（２進数表示）の
最上位ビツト（MSB）に相当する。

パストレース制御部４はまずトレースを開始す
るノードを選択してトレースを開始する。トレー
ス開始ノードとしては任意のノードを選択するこ
とが可能であるが、望ましくはパスメトリツク値
最小のノードが選択される。第２図においては、
パスメトリツク値82、78、76、64、62のうちの最
小となる62のノード（ノード番号７）がトレース
開始ノードとして選定される。

いまトレース開始ノードのノード番号をN₀、
（N₀＝０〜2^K-1−１、Ｋは拘束長、符号化率Ｒ＝
１／２）とし、このノード番号N₀に対応するパスメ
モリの内容をPS₀とする。ここで添字はトレース
の段数に対応しており、第２図ではメモリ長が８
段なので０〜７の値をとり得る。このトレース開
始の時点で、ノード：N₀に対応するACS回路は
ノード：N₁ N₁＝2^K-2×PS₀＋「N₀／２」ここで「Ｎ／２」はＮ／２を越えない最大の整
数からの遷移を生き残りパスとして選択したことを
意味しており、よつて次はノード：N₁に対応す
るパスメモリの内容（パス選択信号）：PS₁を読
み出す。この操作を繰り返し、パスメモリの全長
にわたつてトレースして最後に到達したノードの
ノード番号から復号出力を得る。その場合、最後
のノード番号を２進数表記し、そのMSBを復号
出力する。

これを第２図の説明図を用いて一層詳細に説明
すると、ステツプ０ではパスメトリツク値最小の
ノード番号N₀＝７を選定して、それに対応する
パスメモリの内容である最新のパス選択信号PS₀
の“１”が読み出され、それらに基づいて前述の
式の演算、すなわち、４×１＋３＝７、が行わ
れ、ノード番号N₁＝７が求められる。

従つて、次のステツプ１では、このノード番号
N₁＝７と、それに対応するパスメモリの内容：
PS₁の“１”とに基づきノード番号N₂＝７を求
め、さらに続くステツプ２ではノード番号N₂＝
７とパスメモリの内容：PS₂＝０とに基づきノー
ド番号N₃＝３を演算する。以下、同様にしてス
テツプ７でノード番号N₈＝４を算出する。この
ノード番号N₈がトレース最後の場合、ノード番
号４の２進数表記は“100”であるから、その
MSBの“１”が復号出力となる。そして、ステ
ツプ０〜７におけるノード番号が各ステツプ毎に
トレースメモリ５に書き込まれる。

このように、例えばノード番号N₁は、ノード
番号N₀とそのパスメモリの内容：PS₀とにより与
えられる。これはノード番号を２進数表記した場
合、ノード：N₀を下位に１桁シフトし、ノー
ド：N₀のパスメモリの内容：PS₀を最上位とする
ことで、ノード：N₁が導かれる。すなわち、第
２図において最後に到達したノードのノード番号
４（すなわち“100”）は、トレースしたパス選択
信号の最後の３ビツトにより導かれる。よつて一
番最後のパス選択信号がノード番号のMSBとな
り、これが復号出力となる。

復号出力としては、ビタビ復号法のアルゴリズ
ムに従えば、本来、最後に到達したノードのノー
ド番号のLSB（最下位ビツト）が用いられる。し
かしこの場合の復号出力は最後から３番目に読み
出したパス選択信号そのものであり、残り２回
（拘束長）をＫとすればＫ−２回）のトレースは
復号出力に何等影響を与えない。よつて復号出力
として本発明のようにMSBを用いると、同じ復
号出力を得るのに、LSBを用いた場合よりメモ
リアクセスの回数が少ないため高速動作が可能と
なる。換言すれば、MSBを復号出力に用いると、
LSBの場合と同じ回数だけメモリをアクセスし
てパスメモリ全部をトレースした場合、パスメモ
リ長が長く見えるため、すなわちパスメモリの実
効長が実際のパスメモリ長より長くなるため、パ
ス打切りによる誤り率の増加が減少する。

〔実施例〕

以下、本発明の実施例を図面を参照して説明す
る。

前述したパストレースの方法では、パストレー
スのためのノード番号の演算を一つの復号サイク
ルで最後に到達するノードまで行つた場合、パス
メモリに対するアクセス回数が多くなり、復号処
理速度を低下させる。以下に説明する実施例で
は、この問題点を解決するため、ある復号サイク
ルにおける最尤パスとその前の復号サイクルにお
ける最尤パスとは殆ど同一の形となる確率が高
く、現サイクルと前サイクルでノード番号が一致
した後は以降のパスは同一となることに着目し、
演算されたノード番号が前復号サイクルのノード
番号と最初に一致した時点でトレースを打ち切
り、最後までトレースを行わないでパスメモリに
対するアクセス回数を少なくし、それにより復号
処理速度を向上させている。

実施例装置の構成第３図は本発明の実施例のブロツク図であり、
１１は分配器、１２はACS回路、１３は最小パ
スメトリツク検出回路、１４はタイミング発生回
路、１５は、パストレース制御部、１６はパスメ
モリ、１７はトレースメモリ、１８はトレースス
テート制御回路、１９はマルチプレクサ
（MPX）、２０はノード番号計算部、２１は比較
部、２２はポインタ制御部、２３はトレースアド
レスカウンタ、２４，２６はアドレス制御部、２
５，２７はデータ制御部である。タイミング発生
回路１４は、高速クロツク信号とデータクロツク
信号とにより、各部に供給するクロツク信号及び
タイミング信号を出力するものである。又分配器
１１は、受信符号ａからブランチメトリツクを計
算し、このブランチメトリツクｂをACS回路１
２に加えるものである。

ACS回路１２は、受信符号ａの拘束長Ｋに対
応した数の加算器、比較器及びセレクタから構成
され、タイミング発生回路１４からのタイミング
信号ｃに従つて動作し、ブランチメトリツクｂと
１シンボル前のパスメトリツクと加算器で加算
し、その加算出力の新たなパスメトリツクを比較
器で比較し、小さい方のパスメトリツクをセレク
タから出力し、そのパストリツクｅを最小パスメ
トリツク検出回路１３に加え、又比較器に於ける
比較結果を示すパスセレクト信号ｄをマルチプレ
クサ１９及びノード番号計算部２０に加える。ト
レースステート制御回路１８は、タイミング発生
回路１４からのタイミング信号により動作し、比
較部２１からの一致検出信号ｉによつてトレース
ステートの切替えを行う。

又ポインタ制御部２２は、復号サイクル毎にパ
スメモリ１６とトレースメモリ１７との先頭アド
レスを示すポインタを１段シフトさせるものであ
り、それによつてトレースアドレスカウンタ２３
からトレース時のアドレス信号が出力される。ア
ドレス制御部２４からパスメモリ１６に対して書
込イネーブル信号や読出イネーブル信号等の制御
信号ｊとアドレス信号ｋとが加えられ、パスメモ
リ１６からの読出データｌはデータ制御部２５に
転送され、又データ制御部２５を介して書込デー
タｌがパスメモリ１６に加えられる。又アドレス
制御部２６からトレースメモリ１７に、書込イネ
ーブル信号や読出イネーブル信号等の制御信号ｍ
とアドレス信号ｎとが加えられ、データ制御部２
７とトレースメモリ１７との間でデータ（ノード
番号）ｏが転送される。読出されたノード番号ｈ
はデータ制御部２７を介して比較部２１に加えら
れ、ノード番号計算部２０で計算されたノード番
号ｇと比較され、比較一致信号ｉはトレースステ
ート制御回路１８に加えられる。

受信符号ａが入力され、パスメモリ１６にパス
セレクト信号を書込む処理については従来例と同
様である。このパスメモリ１６及びトレースメモ
リ１７は通常のランダムアクセスメモリにより構
成されており、第４図に示すように、ポインタに
よつてパスメモリ１６及びトレースメモリ１７の
先頭アドレスが指定される。

このポインタは、ポインタ制御部２２によつて
制御され、復号サイクル毎にポインタ進行方向に
１段シフトされる。パスメモリ１６及びトレース
メモリ１７のポインタによつて指示された先頭ア
ドレスに、パスセレクト信号及び開始ノード番号
が加えられる。トレース方向は、ポインタ進行方
向と反対方向であり、ポインタによつて指示され
た先頭アドレスから開始され、トレースアドレス
カウンタからのアドレス信号に従つて、前の復号
サイクルに於けるパスセレクト信号及びノード番
号が読出される。パスメモリ１６及びトレースメ
モリ１７の物理アドレスは、トレース論理アドレ
スとポインタによる先頭アドレスとの、パスメモ
リ長を法とする和となる。その為、パスメモリ長
は2ⁿ段にすることが望ましい。

パストレースの説明前述の第２図を用いて実施例装置のパストレー
ス動作を以下に説明する。

前述のように第２図に於いては、パスメトリツ
ク値が82、78、64、62のうちの最小となる62のノ
ード番号７が、トレース開始ノードとして選定さ
れている。

トレース開始ノード番号N₀₀、このノード番号
N₀₀に対応するパスメモリ１６の内容をSP₀₀とす
ると、この時点でノード番号N₀₀に対応するACS
回路１２は、ノード番号N₀₁を N₀₁＝2^K-1×PS₀₀＋N₀₀／「２」 ……(1) からの遷移を生き残りパスとして選択したことを
意味することになり、次はこのノード番号N₀₁に
対応するパスメモリ１６の内容のパスセレクト信
号PS₀₁を読出す。このような操作を繰り返す。
なお、「N₀₀／２」は、N₀₀／２を超えない最大の
整数を意味する。

第２図に於いて、ステツプ１は、パスメトリツ
ク最小のノード番号N₀₀＝７と、それに対応する
パスメモリ１６の内容として、最新のパスセレク
ト信号SP₀₀の“１”とがノード番号計算部２０
に読込まれて、(1)式に従つた演算が行われ、４×
１＋３＝７となるから、ノード番号N₀₁＝７が算
出される。

次のステツプ２は、このノード番号N₀₁＝７に
対応するパスメモリ１６の内容のパスセレクト信
号SP₀₁の“１”が読出されて、ノード番号N₀₂＝
７が算出される。次のステツプ３は、ノード番号
N₀₂に対応するパスメモリ１６の内容のパスセレ
クト信号SP₀₂の“０”が読出されて、ノード番
号N₀₃＝３が算出される。以下同様にして、ステ
ツプ８で、ノード番号N₀₈＝４が算出される。こ
のノード番号N₀₈＝４がトレース最後の場合に、
４＝“100”であるから、そのMSB（最上位ビツ
ト）の“１”が復号出力となる。そして、ステツ
プ１〜８に於けるノード番号が、各ステツプ毎に
トレースメモリ１７に書込まれる。

前述のように、一般に、ビタビ復号器に於いて
は、或る復号サイクルで得られる最尤パスは、そ
の前の復号サイクルに於ける最尤パスとほぼ同一
である確率が高い。換言すると、前回の復号サイ
クルに於ける最尤パスを１段シフトし、それに１
回分の遷移を追加したものと同一となる確率が高
い。

第５図はパストレース説明図であり、第２図の
復号サイクルの次の復号サイクルに於けるパスト
レースを示すものである。パスメモリの内容は、
先頭に最新のパスセレクト信号が加えられること
により、第２図に示す内容を１段シフトしたもの
となる。又この復号サイクルに於けるパスメトリ
ツク値が、19、18、14、５、０のうちの最小の０
のノード番号１からトレースが開始される。第２
図と同様にノード番号を求めると、ステツプ１〜
８に於いて、N₀₀＝０、N₀₁＝４、N₀₂＝６、N₀₃
＝７、N₀₄＝３、N₀₅＝１、N₀₆＝０、N₀₇＝０、
N₀₈＝０となる。そして、最後のノード番号N₀₈
＝０であるから、そのMSBの“０”を復号出力
とする。

各ノード番号をトレースメモリ１７に書込むも
のであるが、前回の復号サイクルに於けるトレー
スメモリを１段シフトした内容と比較すると、３
回目でノード番号７が一致することになり、それ
以降のノード番号は総て同一となる。即ち、前回
の復号サイクルに於けるノード番号と、今回の復
号サイクルに於けるノード番号とが一致した時
に、それ以降のトレースを打ち切り、前回の復号
サイクルに於ける最後のノード番号から１段前の
ノード番号を、今回の復号サイクルに於けるトレ
ースの最後のノード番号として復号出力を得るこ
とができる。

このようなトレース過程に於いて、ノード番号
計算部２０で算出したノード番号ｇと、トレース
メモリ１７から読出した前回の復号サイクルに於
けるノード番号ｈとを比較器２１で比較し、不一
致の場合は、算出したノード番号ｇをトレースメ
モリ１７に書込み、ノード番号ｇ，ｈが一致した
時は、信号ｉがトレースステート制御回路１８に
加えられて、トレースが打ち切られ、次の制御状
態に移行する。

平均トレース回数は、実験によれば、回線誤り
率が極端に悪くならない限り、２回以下となる。

第６図はパストレースの動作タイムチヤートを
示し、復号サイクル当りトレース回数を２回とし
た場合であり、従つて、復号サイクルは、Ｉ／Ｏ
ステートと、トレースステート１と、トレースス
テート２とに分けられている。又拘束長Ｋ＝７と
した時に、ACS回路からのパスセレクト信号は
64ビツトとなり、16ビツトずつ４回に分けてパス
メモリに書込む場合を示す。従つて、パスメモリ
は、８ビツト／ワードのランダムアクセスメモリ
が２個必要となる。

ACS回路からパスセレクト信号PS₀₀と、トレ
ース開始ノード番号N₀₀とが出力され、パスセレ
クト信号PS₀₀は、前述のように、16ビツトずつ
矢印で示すように４回に分けて書込まれ、後半の
２回はＩ／Ｏステートに於いて書込まれる。又こ
のＩ／Ｏステートに於いてトレースメモリから復
号出力（トレース最後のノード番号MSB）が読
出され、次にトレース開始ノード番号N₀₀がトレ
ースメモリに書込まれる。又トレース開始ノード
番号N₀₀とパスセレクト信号PS₀₀とにより、前述
の(1)式に基づいてノード番号N₀₁が計算される。

第３図を参照すると、ACS回路１２からパス
セレクト信号ｄが出力され、最小パスメトリツク
検出回路１３からトレース開始ノード番号ｆが出
力され、ノード番号計算部２０に於いて(1)式に基
づいたノード番号ｇが算出される。又パスセレク
ト信号ｄはマルチプレクサ１９からデータ制御部
２５を介してパスメモリ１６に書込データｌとし
て加えられる。この時、ポインタ制御部２２によ
るポインタによつてパスメモリ１６とトレースメ
モリ１７との先頭アドレスが指定されているの
で、そのアドレスに、64ビツトのパスセレクト信
号は、16ビツトずつ４回に分けて書込まれる。又
トレース開始ノード番号ｆは、ノード番号計算器
２０からデータ制御部２７を介してトレースメモ
リ１７に加えられる。

ノード番号N₀₁が算出されると、それに対応す
るパスセレクト信号PS₀₁がトレースステート１
に於いてパスメモリから読出され、又トレースメ
モリから前回のトレース結果のノード番号N₀₁′が
読出される。この場合、トレースステート制御回
路１８によつて制御されるトレースアドレスカウ
ンタ２３からのアドレス信号が、アドレス制御部
２４，２６をそれぞれ介して、パスメモリ１６と
トレースメモリ１７とに加えられ、パスセレクト
信号とノード番号とが読出される。

そして、先に算出されたノード番号N₀₁と読出
されたパスセレクト信号PS₀₁とによりノード番
号N₀₂が計算され、又その間に、ノード番号N₀₁，
N₀₁′の比較が行われる。これは、比較部２１に於
いて、ノード番号計算部２０で算出したノード番
号ｇと、トレースメモリ１７から読出したノード
番号ｈとを比較するもので、比較一致の場合は、
信号ｉがトレースステート制御回路１８に加えら
れるので、次の制御状態に移行される。そして、
次の復号サイクルは、トレース開始ノード番号
N₁₀から行われる。

比較不一致の場合は、更にトレースが継続され
る。即ち、算出されたノード番号N₀₂に対応する
パスセレクト信号PS₀₂が、トレースステート２
に於いてパスメモリから読出されて、ノード番号
N₀₃が計算され、又トレースメモリから読出され
た前回のトレース結果のノード番号N₀₂′と算出さ
れたノード番号N₀₂とが比較される。比較一致の
場合に、次のトレース開始ノード番号N₁₀から行
われ、前述の動作が繰り返される。

第６図は１復号サイクルでトレース終了となる
場合を示すものであるが、トレース終了とならな
い場合を第７図に示す。トレース開始ノード番号
N₀₀から順次ノード番号N₀₁，N₀₂，N₀₃が算出さ
れ、トレースステート２に於いてノード番号の比
較が行われた時に、ノード番号N₀₂とノード番号
N₀₂′とが不一致であると、次の復号サイクルで継
続してトレースを行うことになる。その場合、次
の復号サイクルのＩ／Ｏステートではトレースが
禁止され、復号出力の読出しとトレース開始ノー
ド番号N₁₀の書込み、及びパスセレクト信号PS₁₀
の後半の書込みが行われる。そして、次のトレー
スステート１に於いてノード番号N₀₃に対応する
パスセレクト信号PS₀₃が読出され、又前回のノ
ード番号N₀₃′が読出され、次のトレースステート
２に於いてノード番号N₀₃，N₀₃′の比較が行われ
る。

パストレースの再開方式このように、１復号サイクルでトレースが終了
しない場合に、トレースが終了した復号サイクル
に於いて、次のトレースを開始する為の再開方式
として３種類が考えられる。第８図はａ〜ｃはそ
れぞれのパストレース再開説明図であり、復号サ
イクル０、１、２、…に於けるトレースの開始ノ
ード番号をN₀₀，N₁₀，N₂₀，…とすると、再開方
式１は、ａに示すように、先のトレース（１復号
サイクルで終了しなかつたトレース）が開始され
た復号サイクルの次の復号サイクルで選択された
トレース開始ノードから再開するもので、復号サ
イクル０に於けるトレース開始ノード番号N₀₀か
らトレースを行つて、復号サイクル２に於いて終
了したとすると、次は復号サイクル１に於いて選
択されたトレース開始ノード番号N₁₀から開始
し、この場合のトレースが１復号サイクルで終了
した時は、次の復号サイクル２に於いて選択され
たトレース開始ノード番号N₂₀から開始する。

又再開方式２は、ｂに示すように、先のトレー
スが終了した復号サイクル（或いはその次の復号
サイクル）に於けるトレース開始ノードから再開
するものであり、前述の場合と同様に、復号サイ
クル０に於ける選択されたトレース開始ノード番
号N₀₀からトレースを行い、復号サイクル０〜２
の３復号サイクルで終了した場合、復号サイクル
１、２に於いて選択されたトレース開始ノード番
号N₁₀，N₂₀を、Ｉ／Ｏステートに於いてトレー
スメモリへ書込み、次の復号サイクル３に於いて
選択されたトレース開始ノード番号N₃₀からトレ
ースを開始するものである。

又再開方式３は、先のトレースが終了した復号
サイクル（或いはその次の復号サイクル）に於け
るトレース開始ノードから再開する。但し、先の
トレースが終了していない復号サイクルでは、
Ｉ／Ｏステートに於けるトレースメモリへの書込
みを、トレース開始ノード番号ではなくダミー番
号を書込むものである。前述の場合と同様に、ト
レース開始ノード番号N₀₀から開始したトレース
が、復号サイクル０〜２の３復号サイクルで終了
した時に、復号サイクル１、２に於いて選択され
たトレース開始ノード番号N₁₀，N₂₀の代わりに、
実在しないノード番号を示すダミー番号を、Ｉ／
Ｏステートに於いてトレースメモリに書込み、次
の復号サイクル３に於いて選択されたトレース開
始ノード番号N₃₀からトレースを開始するもので
ある。このトレースも１復号サイクルで終了しな
い場合は、次の復号サイクル４に於いて選択され
たトレース開始ノード番号N₄₀の代わりに、ダミ
ー番号をトレースメモリに書込み、トレース終了
の復号サイクル或いはその次の復号サイクルに於
いて選択されたトレース開始ノードからトレース
を開始することになる。

前述の再開方式１は、トレース開始ノード番号
及びパスセレクト信号の記憶等の為に、構成が多
少複雑となる。又Es／No（信号対雑音比）が劣
化している時は、パスメモリの実効長が短くなる
為、BER（ビツト誤り率）が或る程度劣化する。

又再開方式２は、構成が最も簡単となる。しか
し、再開方式１のようにパストレースを完全に行
うものではないので、Es／Noが悪い時には、
BERの劣化が比較的大きくなる。

又再開方式３は、再開方式２に比較して構成が
多少複雑となり、トレース回数も増加する。しか
し、BERは再開方式２に比較して改善される。

〔発明の効果〕

本発明によれば、高集積化しやすいRAMを使
用しつつ、復号処理速度を向上させることができ
る。

【図面の簡単な説明】

第１図は本発明の原理ブロツク図、第２図はパ
ストレース説明図、第３図は本発明の実施例のブ
ロツク図、第４図はアドレス制御説明図、第５図
はパストレース説明図、第６図及び第７図はパス
トレースの動作タイムチヤート、第８図ａ〜ｃは
パストレース再開説明図、第９図は従来のビタビ
復号器、第１０図は格子状表現説明図、第１１図
及び第１２図は従来例のパスメモリである。１は分配器、２はACS回路、３はパスメモリ、
４はパストレース制御部、５はトレースメモリ、
１１は分配器、１２はACS回路、１３は最小パ
スメトリツク検出回路、１４はタイミング発生回
路、１５はパストレース制御部、１６はパスメモ
リ、１７はトレースメモリ、１８はトレースステ
ート制御回路、１９はマルチプレクサ、２０はノ
ード番号計算部、２１は比較部、２２はポインタ
制御部、２３はトレースアドレスカウンタであ
る。

Claims

【特許請求の範囲】１受信符号から各ノード対応にブランチメトリ
ツク値をそれぞれ計算する分配器１、各ノード対応に設けられた複数のACS回路２
であつて、各個は、該分配器からのブランチメト
リツク値に基づいて選択し得る２つのパスについ
てのパスメトリツク値を演算し、その演算結果を
比較して該２つのパスから生き残りパスを選択
し、該生き残りパス選択を示すパス選択信号を出
力するもの、該パス選択信号を各ノード対応に所定段数にわ
たり記憶するパスメモリ３、任意のノードのノード番号と該ノード番号に対
応するパスメモリのパス選択信号とに基づいて前
段で生き残りとして選択されたノードのノード番
号を演算することを所定段数にわたり繰り返すパ
ストレース制御部４、該パストレース制御部でトレースされたノード
番号を所定段数にわたり記憶するトレースメモリ
５、を具備し、該トレースメモリの所定段目のノ
ード番号の２進数の最上位桁を復号出力とするよ
うに構成されたビタビ復号器。