JPS61121622A - ビタビ復号用正規化回路 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 誤り訂正用たたみ込み符号の復号に使用されるビタビ復
号器に於ける演算回路のオーバフローを防止する為のビ
タビ復号用正規化回路に関するものである。

〔従来の技術〕

とタビ（Ｖ　１ｔａｂｉ）復号器は、たたみ込み符号の
最尤復号法（ｍａｘｉｍｕｍ　１ｉｋｅｌｉｈｏｏｄ　
ｄｅｃｏｄｉｎｇ）に使用されるものであり、回線品質
を保証する為の訂正能力の高い復号器として、衛星通信
方式等に於いて多く使用されている。このビタビ復号器
は、既知の複数個の符号系列のうち、受信符号系列に最
も符号距離が近いパスを最尤パスとして選択し、そのパ
スに対応する復号データを得る復号器であり、又たたみ
込み符号（ｃｏｎｖｏｌｕｔｉｏｎａｌ　ｃｏｄｅｓ）
は、成るシンボルを入力した時の出力が、その時点から
何シンボルか前までの入力全体の影響を受けて生成され
る符号であって、成るシンボル自体を含めて何グループ
の出力に影響を与えるかを拘束長と称するものである。

この拘束長が長（なる程、誤り訂正能力が向上する反面
、復号器の規模が指数関数的に増大することになる。

第４図はたたみ込み符号の符号器の一例のブロック図で
あり、３１は入力端子、３２は３段のシフトレジスタ、
３３．３４は法２の加算器、３５は切換スイッチ、３６
は出力端子である。入力端子３１に情報系列の１ビツト
が加えられると、それ以前に入力されてシフトレジスタ
３２に加えられた情報系列の２ビツトが、加算器３３．
３４の出力に影響を与えることになり、１人カシンボル
は３グループの出力に影響を与える構成となる。

従って、拘束長には３となる。又シフトレジスタ３２の
各段が初期状態で総て“０”であるとし、入力端子３１
に“１０６１”の情報系列が加えられた場合、出力端子
３６から出力される符号系列は“１１１０１１１１″と
なる。

又符号系列の符号化率Ｒは、入力情報系列のビット数を
ｂ、変換された符号系列のビット数をｎとした時、ｂ　
／　ｎで表され、前述の符号器による符号化率Ｒは、Ｒ
＝１／２となる。この符号化率Ｒを大きくする程、情報
転送レートを高くすることができるが、誤り訂正能力は
低下することにな′　る。

第５図は第４図の符号器の内部状態遷移説明図であり、
シフトレジスタ３２の第１段に情報系列のビットが入力
された時に、第２段、第３段には以前に入力されたビッ
トが残存しており、その２ビツトにより、“００′、“
１０″、“Ｏ１″。

“１１”の何れかの内部状態となる。それらの内部状態
に於いて“Ｏ”の入力ビットにより点線矢印方向に遷移
し、“ｌ”の入力ビットにより実線矢印方向に遷移する
。例えば、“ＯＯ”の内部状態に於いて“０”が入力さ
れると、符号系列としては（０，０）で示すように“Ｏ
Ｏ”が出力され、内部状態は“００”のままとなる。又
“１”が入力された場合は、符号系列としては（１，１
）で示すように“１１”が出力され、内部状態は実線矢
印方向の“１０゛に遷移する。又内部状態が“１１″の
場合に、“１”が入力されると、（１，０）で示すよう
に、“１０”が符号系列として出力され、内部状態は変
化しない。又“Ｏ”が入力されると、（０，１）で示す
ように、“０１″が符号系列として出力され、内部状態
は実線矢印方向の“０１”に遷移する。

例えば、内部状態が“ＯＯ”のａに於いて、前述のよう
に情報系列の“１００１”が入力された場合、最初の“
１”により符号系列の“１１”が出力され、内部状態は
“１０”のｂに遷移する。

次の“Ｏ”により符号系列の“１０”が出力されて内部
状態はｂから“０１”のＣに遷移する。次のＯ”により
符号系列の“１１”が出力され内部状態はＣから“００
”のｄに遷移する。最後の“ｌ”により、符号系列の“
１１”が出力され内部状態はｄから“１０”のｅに遷移
する。従って、符号系列は１１１０１１１１″となる。

なお、情報系列が“Ｏ”の連続の場合は、内部状態は、
ａ、ｆ、ｇ、ｄのように“００”で、符号系列は“００
”の連続となる。

第６図は従来のビタビ復号器のブロック図であり、４１
３〜４１ｎは演算回路（ＡＣ３）であって、加算器（人
ｄｄｅｒ）　４２．　４３　（ＡＤＤ）　、比較器（Ｃ
ｏｍｐａｒａｔｏｒ）　４４　（ＣＭ　Ｐ　）及びセレ
クタ（Ｓｅｌｅｃｔｏｒ）　４５　（Ｓ　Ｅ　Ｌ）を含
むものであるから、ＡＣ５回路と称されるものである。

これらの演算回路４１３〜４１ｎは、前述の符号器の内
部状態に対応して設けられるものであり、拘束長Ｋに対
応して、２に一１個の演算回路を必要とするものである
。第４図に示す構成の符号器に対応した復号器とするに
は、Ｋ＝３であるから、４個の演算回路が必要となる。

又４６は正規化用加算器（ＡＤＤ）　、４７はメトリッ
クメモリ　（ＭＥＭ）　、４８はパスメモリにパス選択
情報を転送する為の信号線、４９はパスメトリック値を
パスメモリ　（図示せず）及び他の演算回路へ転送する
為の出力線、５０は各演算回路４１ａ〜４１ｎのセレク
タ４５の出力のメトリック値を加えて最小メトリック値
を選択する最小メトリック選択回路（ＭＩＮ　　５ＥＬ
）　、５１は補数化回路（ＣＰ　Ｌ）である。

前述の内部状態の遷移径路をパスと称し、このパスと受
信符号系列との符号距離をパスメトリック（ｐａｔｈ　
ｍｅｔｒｉｃ）と称するものである。他の演算回路から
のパスメトリック値と、分配器（図示せず）からのブラ
ンチメトリック値とが加算器４２．４３に加えられ、そ
の加算結果が比較器４４により比較され、小さい値の方
をセレクタ４５から出力するように比較器４４の比較出
力信号によりセレクタ４５を制御し、又その比較出力信
号をパス選択情報として信号線４８を介してパスメモリ
（図示せず）へ転送して記憶させる。

セレクタ４５の出力のパスメトリック値は、正規化用加
算器４６に加えられ、修正値（補数）と加算されて正規
化され、メトリックメモリ４７に加えられる。このメト
リックメモリ４７から出力線４９を介してパスメトリッ
ク値が出力される。

又セレクタ４５で選択出力されたパスメトリック値は、
他の演算回路からのパスメトリック値と共に最小メトリ
ック選択回路５０に加えられ、最小値のパスメトリック
値が選択され、そのパスメトリック値は補数化回路５１
により補数に変換されて正規化用加算器４６に修正値と
して加えられる。従って、最小パスメトリック値を出力
した演算回路に於いては、零のパスメトリ・ツク値が出
力されることになる。

受信符号系列に誤りがない場合は、最尤パスのパスメト
リック値はＯとなるものである。例えば、受信符号系列
が“１１１０１１１１”の場合、第５図を参照すると、
内部状Ｂａから内部状６ｂ、ｆに遷移することが可能で
あり、受信符号系列の”１１’については、内部状ｇｂ
へ遷移するパスのパスメトリック値は「０」、内部状Ｈ
ｒへ遷移するパスのパスメトリック値は「２」となる。

次の受信符号系列の“ＩＯ”については、内部状Ｌｉｂ
から内部状Ｂｃへ遷移するパスのパスメトリック値は「
０」であるが、内部状態「から内部状態ｇへ遷移するパ
スのパスメトリック値は「１」となる。又次の受信符号
系列の“１１”については、内部状り、Ｃから内部状ｆ
ｉｄに遷移するパスのパスメトリック値はｒＯＪである
が、内部状ｔｆ１Ｍｇから内部状ｌｄに遷移するパスの
パスメトリック値は「２」となる。

この場合、同一の内部状Ｊｌｉｄとなるものであるが、
パスによってメトリック値が相違し、加算されたパスメ
トリック値は、ａ、ｂ、ｃ、ｄのパスについてはｒｏｂ
、ａ、ｒ、ｇ、ｄのパスについては「５」となる。従っ
て、パスメトリック値の最小のパスが受信符号系列に最
も近いパスであるから、パスｄ　−４（−＊　ｌ）　−
ｅ　ａを辿って内部状Ｍａに戻った時、内部状態ａに於
ける復号出力は、内部状態すに遷移させる“１″となる
。

次の受信符号系列の’１１″については、内部状Ｂａか
ら内部状態ｅに遷移するパスのパスメトリック値がｒＯ
Ｊとなる。又他のパスのパスメトリック値も演算されて
、パスメトリック値の大小比較が行われ、パスメトリッ
ク値の最小のパスを辿って、例えば、内部状態すに於け
る復号出力として、内部状態Ｃに遷移させる“Ｏ”が出
力されることになる。

受信符号系列の誤りが生じると、最尤パスのパスメトリ
ック値は「０」ではな（なり、それによって、それ以後
の復号過程に於ける総てのパスのパスメトリック値が増
加することになる。その為に演算回路がオーバフローし
て、正しい判定が不可能となる場合が発生する。このよ
うなオーバフローを防止する為に、総ての演算回路のパ
スメトリック値から適当な値を減算して正規化する構成
が採用されているものであり、パスメトリック値の最小
値を零とするように、他のパスメトリック値を正規化す
るものであって、前述の正規化用加算器４６により、補
数化回路５１からの修正値を加算して正規化するもので
ある。

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

前述のビタビ復号器に於いては、前段のパスメトリック
及びブランチメトリックが人力されてから、パスメトリ
ック出力が得られるまでを、１シンボル内に処理しなけ
ればならないものであり、（加算−比較−選択）の処理
に加えて、正規化の為の（最小メトリック選択−補数化
−正規化用加算）の処理も１シンボル内で行わなければ
ならないので、スループットが大幅に低下する欠点があ
った。

本発明は前述の従来の欠点を改善することを目的とする
ものである。

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

本発明のビタビ復号用正規化回路は、ビタビ復号器の分
配器のブランチメトリ・７り計算部の出力から修正値を
減算して各演算回路（ＡＣ５回路）へ分配する加算器を
設けたものである。

〔作用〕

ブランチメトリック値について修正値を減算して正規化
することにより、パスメトリック値を求めるフィードバ
ックループ外で正規化処理を行うごとになり、スルーブ
ツト低下を防止できるものである。

〔実施例〕

以下図面を参照して本発明の実施例について詳細に説明
する。

第１図は本発明の実施例のブロック図であり、■は分配
器（ＤＩＳ）、２〜５は演算回路（ＡＣ３）、６はパス
メモリ　（ＰＭ）　、７はセレクタ（ＳＥＬ）　、８は
最小メトリック選択回路（ＭＩＮＳＥＬ）　、９は補数
化回路（ＣＰＬ）である。最小メトリック選択回路８に
より各演算回路２〜５に於けるパスメトリック値の最小
値を選択して補数化回路９に加えて、その最小値を補数
とし、分配器ｌに加えるもので、分配器１に於いてブラ
ンチメトリック値にその最小値の補数を加算して、正規
化を行うものである。

又演算回路２〜５は、第５図に示す内部状態の遷移に対
応した接続構成を有する場合を示し、例えば、演算回路
２は内部状態“Ｏｏ”に対応し、この演算回路２の出力
のパスメトリンク値と、内部状態“０１”に対応する演
算回路４の出力のパスメトリック値と、分配器１からの
ブランチメトリック値とが入力されるものである。又各
演算回路２〜５からのパスメトリック値が最小メトリッ
ク選択回路８に加えられる。又パスメモリ６及びセレク
タ７に、各演算回路２〜５からのパスメトリック値及び
パス選択情報が加えられて、セレクタ７によりパスメト
リック値の最小のパスが選択されて、復号されることに
なる。

第２図は本発明の一実施例の要部ブロック図であり、第
１図に於ける分配器１の部分を示すものである。同図に
於いて、１１はブランチメトリック計算部（ＢＭＡ）　
、１２〜１５は加算器（ＡＤＤ）であり、加算器１２〜
１５の出力のブランチメトリック値は、（２）〜（５）
で示すように、″演算回路２〜５　（第１図参照）に加
えられる。

又最小メトリンク選択回路８には、各演算回路２〜５　
（第１図参照）からのパスメトリック値が加えられ、最
小値が選択されて補数化回路９により補数に変換され、
修正値として分配器１の各加算器１２〜１５に加えられ
、ブランチメトリック計算部１１から出力されるブラン
チメトリック値に加算されて正規化が行われる。

演算回路２〜５に於いては、他の演算回路からのパスメ
トリック値がそれぞれ入力されてパスメトリック値の演
算が行われるものであるが、正規化は分配器１に於いて
行われる。即ち、演算回路２〜５に於いては、〔前段の
パスメトリック値＋（ブランチメトリック値−修正値）
〕の処理が行われ、０内は分配器１で処理されるもので
あるから、修正値を減算する処理が演算回路２〜５に含
まれないことになり、従って、正規化処理によるスルー
プットの低下を防止できることになる。

なお、正規化を行う為の加算器１２〜１５は、減算器と
することも可能であり、その場合は、補数化回路９は省
略されることになる。又修正値は、最小パスメトリック
値と同一の値となるから、パスメトリック値が負数とな
ることはなく、符号ビットを追加する必要はないもので
ある。

第３図は本発明の他の実施例の要部ブロック図であり、
第１図及び第２図と同一符号は同一部分を示し、１６〜
１９はＤ型のフリップフロップ（ＤＦＦ）である。ブラ
ンチメトリック計算部１１の出力をフリップフロップ１
６〜１９に加えて、図示を省略したクロック信号により
ラッチし、それらのフリップフロン１１６〜１７の出力
を加算器１２〜１５に加えて、補数化した修正値との加
算を行って、正規化を行うものである。

とタビ復号器に於いては、ブランチメトリック値と前段
のパスメトリ・ツク値とが演算回路に入力されて、ｌシ
ンボル内にパスメトリック値が出力される構成となるこ
とが必要であり、前述のように、分配器１に於ける遅延
は、バスメトリンク値の演算処理に影響を与えないから
、フリップフロン１１６〜１９を設けて、内部クロック
（図示せず）に同期化させ、加算器１２〜１５により正
規化させても、この正規化処理によるスループットの低
下は生じないことになる。

〔発明の効果〕

以上説明したように、本発明は、ビタビ復号器の分配器
１のブランチメトリック計算部１１の出力から修正値を
減算して各演算回路２〜５へ分配する加算器１２〜１５
を設けたものであり、分配器ｌに設けた加算器１２〜１
５により正規化を行うことにより、演算回路１２〜１５
に於けるオーバフローを防止し、且つスループットの低
下を防止することができるものである。

【図面の簡単な説明】

第１図は本発明の実施例のブロック図、第２図及び第３
図は本発明のそれぞれ異なる実施例の要部ブロック図、
第４図は符号器の概略ブロック図、第５図は内部状態の
遷移説明図、第６図は従来のビタビ復号器の要部ブロッ
ク図である。 ■は分配器（ＤＩＳ）、２〜５は演算回路（ＡＣ３）　
、６はパスメモリ　（ＰＭ）　、７はセレクタ（ＳＥＬ
）　、８は最小メトリック選択回路（ＭＩＮＳＥＬ）、
９は補数化回路（ＣＰＬ）　、１１はブランチメトリッ
ク計算部（ＢＭＡ）　、１２〜１５は加算器（ＡＤＤ）
　、１６〜１９はＤ型フリ・ノブフロップ（ＤＦＦ）で
ある。

Claims (1)

【特許請求の範囲】
1. 誤り訂正用たたみ込み符号の復号を行うビタビ復号器に
   於いて、分配器のブランチメトリック計算部の出力から
   修正値を減算して各演算回路へ分配する加算器を設けた
   ことを特徴とするビタビ復号用正規化回路。