(57)【要約】【課題】従来のビタビ復号装置の回路規模を変更させることなく、正しく復号できないパスの種類を減らすことによりビット誤り率を改善する。【解決手段】畳み込み符号の各遷移状態でのパスの選択情報を記憶して、その記憶された情報を打ち切り長分だけトレースバックすることでビタビ復号を行う場合に、あるステートに合流する２本のパスの尤度が等しい状態が連続する場合のパス選択を、ランダムに毎トレース毎に切り換えながら行うようにした。【選択図】　　　図１
2004140454.tif 000002
【特許請求の範囲】
【請求項１】
畳み込み符号の各遷移状態でのパスの選択情報を記憶して、その記憶された情報を打ち切り長分だけトレースバックすることでビタビ復号を行うビタビ復号方法において、
前記トレースバックを行うためにステートメトリックを計算する際に、あるステートに合流する２本のパスの尤度が等しい状態が連続する場合のパス選択を、ランダムに毎トレース毎に切り換えながら行うことを特徴とする
ビタビ復号方法。
【請求項２】
請求項１記載のビタビ復号方法において、
前記ランダムに毎トレース毎に切り換えながら行うパス選択として、擬似ランダム系列としてのＭ系列を利用したパス選択を行うことを特徴とする
ビタビ復号方法。
【請求項３】
請求項２記載のビタビ復号方法において、
前記Ｍ系列の周期を、トレースの打ち切り長よりも長く設定することを特徴とする
ビタビ復号方法。
【請求項４】
受信した畳み込み符号の各遷移状態での尤度を計算する計算手段と、
該計算手段で計算された尤度に基づいて、最適なパスを選択するパス選択手段と、
該パス選択手段で選択されたパスの選択情報を記憶するパスメモリと、
前記パスメモリの記憶情報を、打ち切り長分だけトレースバックさせる制御を行い、トレースバックを行う際のパス選択として、あるステートに合流する２本のパスの尤度が等しい状態が連続する場合のパス選択を、ランダムに毎トレース毎に切り換える制御手段とを備える
ビタビ復号装置。
【請求項５】
請求項４記載のビタビ復号装置において、
前記制御手段は、あるステートに合流する２本のパスの尤度が等しい状態の場合のパス選択として、擬似ランダム系列としてのＭ系列を利用したパス選択を行うことを特徴とする
ビタビ復号装置。
【請求項６】
請求項５記載のビタビ復号装置において、
前記制御手段で使用するＭ系列の周期を、トレースの打ち切り長よりも長く設定することを特徴とする
ビタビ復号装置。
【請求項７】
畳み込み符号の各遷移状態でのパスの選択情報を記憶して、その記憶された情報を打ち切り長分だけトレースバックすることでビタビ復号を行う処理を実行するプログラムにおいて、
前記トレースバックを行うためにステートメトリックを計算する際に、あるステートに合流する２本のパスの尤度が等しい状態が連続する場合のパス選択を、ランダムに毎トレース毎に切り換えながら行うことを特徴とする
プログラム。
【請求項８】
請求項７記載のプログラムにおいて、
前記トレースバックを行うためにステートメトリックを計算する際に、あるステートに合流する２本のパスの尤度が等しい状態の場合のパス選択として、擬似ランダム系列としてのＭ系列を利用したパス選択を行うことを特徴とする
プログラム。
【請求項９】
請求項８記載のプログラムにおいて、
前記Ｍ系列の周期を、トレースの打ち切り長よりも長く設定することを特徴とする
プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、畳み込み符号の最尤復号に使用されるビタビ復号方法及びビタビ復号装置と、並びにこの復号処理を実行するプログラムに関する。
【０００２】
【従来の技術】
畳み込み符号を復号する方式の一つとして、ビタビ復号方式が知られている。このビタビ復号方式は、畳み込み符号に対する最尤復号方式であり、送信側のエンコーダで生成され得る符号系列の中から、受信された符号系列に最も近い系列（これを最尤パスという）を選ぶことで誤り訂正を行う。
【０００３】
図６は、ビタビ復号方式を用いた従来のビタビ復号装置の一例を示すブロック図である。この図６に示すビタビ復号装置は、受信データＳ６００の各シンボル毎にシンボルメトリックを計算するシンボルメトリック計算回路６００と、そのシンボル単位でのメトリック信号Ｓ６０１から、ブランチ毎のメトリックを計算するブランチメトリック計算回路６０１と、ブランチメトリック信号Ｓ６０２と記憶されたステートメトリックとを比較して加算する演算回路（以下ＡＣＳ回路と称する）６０２と、そのＡＣＳ回路６０２での比較及び加算で得られたステートメトリックを正規化する正規化回路６０３と、正規化回路６０３の出力を記憶するステートメトリック記憶回路６０４と、ＡＣＳ回路６０２から出力されるパス選択情報を記憶するパスメモリ回路６０５とを備えている。
【０００４】
ＡＣＳ回路６０２では、ブランチメトリック計算回路６０１から供給されるブランチメトリックと、ステートメトリック記憶回路６０４に記憶されたステートメトリックとに基づいて、あるステートに合流する２本のそれぞれのパスに対し、ブランチメトリックとステートメトリックを加算して比較し、この比較結果に基づいて尤度の高いものを選択して、新ステートメトリックとする。その選択内容を、パス選択情報Ｓ６０６として出力し、最小のステートメトリックをステートの番号を最尤ステート信号Ｓ６０７として出力し、新たに得られたステートメトリックを新ステートメトリック出力Ｓ６０３として出力する。パスメモリ回路６０５は、ＡＣＳ回路６０２が出力するパス選択情報Ｓ６０６を記憶し、同時にＡＣＳ回路６０２が出力する最尤ステート信号Ｓ６０７に基づいて、最尤パスに対応する情報の内、打ち切り長と呼ばれる一定の長さ以前の情報を復号データＳ６０８として出力する。
【０００５】
ここでパスの選択方法について、拘束長Ｋ＝４の場合を例として説明する。図９の遷移ダイアグラム（以下トレリスと略す）に示す通り、各タイムスロット毎にすべてのステートには合流する２本のパスが存在する。そこで、あるステートに合流する２本のそれぞれのパスに対し、受信信号とパスとのハミング距離（ブランチメトリック）と、それまでのブランチメトリックの累積和（ステートメトリック）とを加算して比較を行い、この比較結果に基づいて尤度の高いものが選択される。
【０００６】
図６の正規化回路６０３は、ＡＣＳ回路６０２から出力される新ステートメトリック信号Ｓ６０３に対し、その値が予め設定されている範囲内の値になるように制御し、その範囲内に正規化された正規化ステートメトリック信号Ｓ６０４として出力する。
【０００７】
正規化方法として、新ステートメトリック計算後に毎タイムスロット、全ステートメトリックの中から最小のステートメトリックを減算する方法や固定値を減算する方法がある。ビタビ復号装置を高速に動作させたい場合には、固定値を減算する方法の実装として、各ステートメトリックの最上位ビットの値が“１”になった場合にその最上位ビットを“０”に反転する方法が装置化が容易でありしばしば用いられる。
【０００８】
ステートメトリック記憶回路６０４は正規化回路６０３から供給される正規化ステートメトリック信号Ｓ６０４を記憶し、これをステートメトリック信号Ｓ６０５として出力してＡＣＳ回路６０２に戻す。
【０００９】
パスメモリ回路６０５はＡＣＳ回路６０２から出力されるパス選択情報Ｓ６０６を記憶し、同時にＡＣＳ回路６０２から出力される最尤ステート信号Ｓ６０７に基づいて、最尤パス対応する情報のうち、打ち切り長と呼ばれる一定の長さ以前の情報を復号データＳ６０８として出力する。パスメモリ回路６０５は、これらの処理の制御手段（図示せず）を必要とする。
【００１０】
ここでパスメモリ回路の実装に当たっては、レジスタ列を用いてパス選択内容を遷移させる方法と、ＲＡＭ等を用いてパス選択内容を記憶させ、それをトレースして復号する方法の２種類がある。以下この２つの方法の説明を行う。
【００１１】
従来のビタビ復号装置においては、パスメモリ回路はレジスタ列を用いてパス選択内容を遷移させる方法が一般的であった。以下、この方法をレジスタ遷移法と呼ぶ。
【００１２】
レジスタ遷移法においては、セレクタとレジスタからなるメモリセルをトレリス上に配置し、ＡＣＳ回路から出力されるパス選択情報に基づいてレジスタの内容を遷移させる。メモリセルの構造を図１０に、拘束長Ｋ＝４の場合のメモリセルの配置を図１１に示す。図１０に示したように、それぞれのメモリセル１０００は、２つの入力を選択するセレクタ１００１と、そのセレクタ１００１で選択されたデータを記憶するレジスタ１００２とで構成してあり、そのレジスタ１００２に記憶されたデータを、次段のメモリセルに送る。
【００１３】
図１１に示したように、各メモリセル１１００，１１０１，‥‥を配置する際には、図９に示したトレリスに従った配置としてある。即ち、各タイムスロットに相当する位置に、ステート数だけ（ここでは８個）だけメモリセルが配置してあり、各メモリセルの出力は図９に示したトレリスに従った順序で、次のタイムスロットに相当する位置の２つのメモリセルに送られる。図１１では、４つのタイムスロット位置までのメモリセル１１００〜１１０７，１１１０〜１１１７，１１２０〜１１２７，１１３０〜１１３７を示してある。こうすることによって、各メモリセルのレジスタ内には各ステートからの生き残りパスに対応する情報が保存されることになる。実際にはメモリセルは打ち切り長分の段数が配置され、最終段の出力のうち最尤ステートの出力を選ぶことによって最尤パスに対応する情報を選択し、復号データを出力する。
【００１４】
レジスタ遷移法は高速動作が可能であるというメリットがある反面、打ち切り長が長くなると回路規模が膨大になるというデメリットがある。特に最近では打ち切り長が１００を越えるような用途も出てきたために、その回路規模の大きさは深刻な問題となっている。
【００１５】
この問題に鑑みて、近年では、ＲＡＭ等を用いてパス選択情報を記憶し、その情報をトレースすることで復号する方法が盛んに研究されている。以下、この方法をトレースバック法と呼ぶ。
【００１６】
トレースバック法におけるトレースの動作を拘束長Ｋ＝４の場合を例として説明する。図１２においてステート００１からトレースする場合を考える。ステート００１への遷移の可能性のあるステートはステート０００とステート１００である。ここでパスメモリには、ステート０００側のパスを選んであったときには０、ステート１００側のパスを選んであったときには１（すなわち前ステートの最上位ビット）が記憶してある。また、どちらから遷移する場合も入力は１であり、これはステート００１の最下位ビットで表現されている。
【００１７】
以上より、トレースの動作は以下のように行えばよい。即ち、図１３に示すように、現在トレースを行っているステートの最下位ビットを復号ビットとし、次にトレースするステートの番号は現トレースステートの最上位ビットから下位２ビット目までに、パスメモリ内のビットを新たに上位ビットとして付け加えることで生成する。この動作によって最小ステートメトリックをとるステートから、選択されたパスを順次遡ることができる。
【００１８】
一方、打ち切り長の十分長いトレースバック法においては、ステートメトリックのビット幅に制限がなくその値がクリップされないと仮定できる理想的なビタビ復号装置であれば、トレースバックの開始ステートを任意に設定しても最尤復号が保証されることがＧ．Ｄ．Ｆｏｒｎｅｙの論文（　“Ｔｈｅ　Ｖｉｔｅｒｂｉ　Ａｌｇｏｒｉｔｈｍ　”，Ｐｒｏｃｅｅｄｉｎｇ　ｏｆ　ｔｈｅ　ＩＥＥＥ，Ｖｏｌ．６１，Ｎｏ３，Ｍａｒ．１９７３　）に記載されており、通常はオール０ステート（ステート０００）からトレースバックを開始する。
【００１９】
【発明が解決しようとする課題】
しかし、ビタビ復号装置の実装を考える場合、当然のことながら、ステートメトリックのビット幅には制限が存在する。このとき、例えば各ステートメトリックの最上位ビットが１となった場合にその最上位ビットを反転する方法による正規化を行うと、正規化が行われないままステートメトリックがクリップされた値を保持し続けるステートが発生し、最尤復号できないパターンが存在するという問題がある。
【００２０】
以下、その例を図面を参照しながら説明する。図１４は、拘束長Ｋ＝４の畳み込み符号化器の例を示した図であり、図１５は、その拘束長Ｋ＝４の畳み込み符号の状態遷移図である。図１４に示すように、拘束長Ｋ＝４の畳み込み符号化器は、３段に接続されたレジスタ１４０１，１４０２，１４０３と、各レジスタ１４０１〜１４０３の入出力を図１４に示すように加算する加算器１４１１〜１４１７で構成されて、３ビットのデータｃ０，ｃ１，ｃ２を得、この３ビットのデータを畳み込み符号とするものである。
【００２１】
このような畳み込み符号をビタビ復号する場合に、ここでは、ステートメトリックのビット幅を６ビットとし、ブランチメトリックのビット幅を５ビットと設定する。正規化は各ステートメトリックの最上位ビットが１になった場合にその最上位ビットを反転して行うものとする。また、ＡＣＳ回路内でステートメトリックはオーバーフローを起こさないように“３１”（５ビットで表現される最大値）の値でクリッピングが行われているものとする。また、符号語の１シンボル当たりのシンボルメトリックは、符号語と受信語が一致していれば０、不一致ならば１５と計算するものとする。
【００２２】
図１６は、同値のステートメトリックが合流した際のパス選択についての説明図である。ステート０００からトレースバックを開始し、ある時刻においてステート０１１に到達した状態を例に考える。
【００２３】
ステート０１１への遷移の可能性のあるステートはステート００１とステート１０１である。１時刻前のステート００１のステートメトリックが６３、ステート１０１のステートメトリックが４６であったとし、それぞれのステート０１１への遷移パスのブランチメトリックが１５と３０とであったとする。このとき、ステート０１１におけるステートメトリックはステート００１からの遷移によるメトリック、ステート１０１からの遷移によるメトリックがともにクリッピングされて６３となり、ＡＣＳ回路内の比較部ではこれらを比較することになる。従来の構成では、常時オール０ステート（ステート０００）寄りのステート００１が選択される。
【００２４】
このような同値のステートメトリックの合流が存在する場合の実際のトレリスを図１７に示す。
【００２５】
いま正しいパスが１０１０１０…とデータが続くパスであるとして、打ち切り長は十分に長いとすると、この１０１０１０…の状態が連続するパスを受信し続けた場合、トレリスのステートメトリックはある定常状態にあると考えてよい。これをオール０ステート（ステート０００）からトレースバックを開始して復号を行うと、図１７に示すようなトレースバックを行い、本来復号されるべき最尤パスを復号できないことがある。
【００２６】
これは、ステート０００とステート１００からステート０００に合流する２本のパスによって計算されるステートメトリックがともに６３という値にクリップされて同値のステートメトリックとしてステート０００で合流しているため、パスの選択が正常に行われないことに起因している。
【００２７】
ここで、従来のビタビ復号装置におけるＡＣＳ回路の内部構成を詳細に見てみる。図７は従来のビタビ復号装置におけるＡＣＳ回路の構成例を示したものである。
【００２８】
図６に示したＡＣＳ回路６０２は、各ステートに対応したＡＣＳ回路７０１〜７０８によって構成され、以下のように構成されて処理を行う。ステート０００に対応するＡＣＳ回路７０１は、ステート０００から遷移するパスとステート１００から遷移するパスがあり、ステート０００のステートメトリックＳ７０１とステート０００から遷移したときのパスのブランチメトリックＳ７０３とを、加算器７１１で加算してＳ７０５を計算し、ステート１００のステートメトリックＳ７０２とステート１００から遷移したときのパスのブランチメトリックＳ７０４とを、加算器７１２で加算してＳ７０６を計算する。これをクリッピング回路７１３によってステートメトリックのビット幅で決まる最大値でそれぞれクリッピングを行った後、比較回路７１４で尤度の高い（メトリックの小さい）方を判断して、その判断されたパスの信号をセレクタ７１５で選択させ、新ステートメトリックＳ７１０とパス選択情報Ｓ７１１とを出力する。同様に、ステート００１に対応するＡＣＳ回路７０２，‥‥、ステート１１１に対応するＡＣＳ回路７０８も、各ステートに合流する２本のパスのメトリックを比較し、新ステートメトリックとパス選択情報とを出力する。
【００２９】
図８はこのＡＣＳ回路の動作を示したフローチャートである。このフローチャートに従って順に説明すると、現ステートメトリックにブランチメトリックを加算し（ステップＳ８０１）、その加算された値が、ステートメトリックのビット幅で決まる最大値を超えていた場合に、その最大値にクリッピングさせる処理を、クリッピング回路７１３で行う（ステップＳ８０２）。その後、比較回路７１４で、次の時刻で合流するステートのメトリックの大小を比較し（ステップＳ８０３）、次時刻で合流するステートのメトリックが等しい値であるか否か判断する（ステップＳ８０４）。ここで、合流するステートのメトリックが等しい値である場合には、オール０ステートに近い方のステートのメトリックを選択する（ステップＳ８０６）。また、合流するステートのメトリックが等しい値でない場合には、尤度の高い方のメトリックを選択する（ステップＳ８０５）。
【００３０】
このような従来の処理においては、同値のステートメトリックが、あるステートで合流した場合には一般的に常に上側つまりオール０ステート（ステート０００）側のパスが選択されるように実装が行われる。これは各ステートに対応するＡＣＳ回路内の全ての比較回路において、ＡとＢの大小比較を「Ａ＞Ｂ」のように等号を付けずに構成することに対応している。
【００３１】
図１７の例を振り返ってみると、ＡＣＳ回路内において、ステート０００からステート０００につながるパスによって計算されるステートメトリックが６３＋１５＝７８となりクリップされて６３となる。一方、ステート１００からステート０００につながるパスによって計算されるステートメトリックが６３＋３０＝９３あるいは６２＋３０＝９２となりこちらもクリップされて６３となる。ＡＣＳ回路は、この合流する２つのメトリックを比較し尤度の高い方を選択して次のタイムスロットにおけるステート０００でのステートメトリックとするわけであるが、同値である６３同士の比較により、図中の上側のパス、すなわちステート０００からのパスを選択することになる。このため、打ち切り長を十分長くしても、トレースバックをオール０ステート（ステート０００）から開始してしまうと最尤復号ができないことになる。
【００３２】
上述したようなパス選択を行う場合、データが１０１０１０‥‥と続くパス以外にも、例えばオール１のデータが続くパス等、正常に復号できない例が存在する。
【００３３】
以上述べたように、ステートメトリック計算時に、あるステートに合流する２本のパスの尤度が等しい場合のパス選択をオール０ステート側に行う従来のビタビ復号装置においては、データが１０１０１０‥‥と続くパスのように、正しく復号できないパスが存在するという問題があった。
【００３４】
本発明はかかる点に鑑みてなされたものであり、従来のビタビ復号装置の回路規模を変更させることなく、正しく復号できないパスの種類を減らすことによりビット誤り率を改善することを目的とする。
【００３５】
【課題を解決するための手段】
本発明は、畳み込み符号の各遷移状態でのパスの選択情報を記憶して、その記憶された情報を打ち切り長分だけトレースバックすることでビタビ復号を行う場合に、あるステートに合流する２本のパスの尤度が等しい状態が連続する場合のパス選択を、ランダムに毎トレース毎に切り換えながら行うようにしたものである。
【００３６】
このようにしたことで、あるステートに合流する２本のパスの尤度が等しい状態が連続する場合のパス選択処理が変更されるため、正しいステートが選ばれる可能性が高くなり、正しく復号できる可能性が高くなる。
【００３７】
【発明の実施の形態】
以下、図１〜図３を参照して本発明の一実施の形態について説明する。
【００３８】
本例においては、従来例で説明した畳み込み符号をビタビ復号する際に、ビタビ復号装置内でトレースバックによりビタビ復号する構成としてある。ビタビ復号するデータは、例えば何らかの伝送路を介して受信したデータであるとする。即ち、ビタビ復号装置の基本的な構成については、従来例として図６に示したビタビ復号装置を使用する。そして本例においては、図６に示したビタビ復号装置の内の、計算されたブランチメトリックと記憶されたステートメトリックとを比較して加算する演算回路であるＡＣＳ回路６０２でのパス選択の制御を行う制御手段での処理を、従来とは異なるようにしたものである。この例では、トレースバックを行う際には、そのトレースバックを開始させるステートは、後述する復号トレリスに示される最も上側のステート０００に設定してある。
【００３９】
図１は本例のＡＣＳ回路の構成を示した図である。この例では、従来例として説明した畳み込み符号と同様に、拘束長Ｋ＝４つまり状態数（ステート数）＝８の符号に対するビタビ復号装置に適用したものであり、ステート数に対応した数のＡＣＳ回路が用意されている。即ち、ステート０００に対応したＡＣＳ回路１０１、ステート００１に対応したＡＣＳ回路１０２、‥‥ステート１１１に対応したＡＣＳ回路１０８の８個のＡＣＳ回路が用意されている。また、ここではステートメトリックのビット幅を６ビット，ブランチメトリックのビット幅を５ビットとする。
【００４０】
以下、本例のＡＣＳ回路について説明すると、本例のＡＣＳ回路は、同値のステートメトリックが、あるステートで合流した場合に、オール１ステート（ステート１１１）寄りのパス選択を行うＡＣＳ回路である。なお、ここではトレースバックを開始するステートを、オール０ステートとしてある。
【００４１】
図１に示したステート０００に対応するＡＣＳ回路１０１は、ステート０００から遷移するとステート１００から遷移するパスがあり、ステート０００のステートメトリックＳ１０１とステート０００から遷移したときのパスのブランチメトリックＳ１０３とを加算器１１１で加算して、加算信号Ｓ１０５を計算する。また、ステート１００のステートメトリックＳ１０２とステート１００から遷移したときパスのブランチメトリックＳ１０４とを加算器１１２で加算して、加算信号Ｓ１０６を計算する。
【００４２】
計算された信号Ｓ１０５，Ｓ１０６は、クリッピング回路１１３に供給し、ステートメトリックのビット幅で決まる最大値でそれぞれクリッピングを行い、クリッピングされた信号Ｓ１０７，Ｓ１０８を得る。ここでは、ステートメトリックのビット幅を６ビットとしてあるので、加算値が６３を超える場合に６３にクリッピングされる。
【００４３】
クリッピング回路１１３で処理された信号Ｓ１０７，Ｓ１０８は、比較回路１１４で尤度の高い（メトリックの小さい）方を判断して、いずれか一方のパスの尤度の方が高い場合には、その尤度の高い方のパスを選択してセレクタ１１６の一方の入力に供給する。また、一致検出回路１１５で、２つの信号Ｓ１０７，Ｓ１０８の尤度が等しいか否か判断し、尤度が等しい場合には、そのことをセレクタ１１６に指示する。
【００４４】
また、本例のビタビ復号装置は、図１に示すように、ＡＣＳ回路１０１〜１０８とは別にＭ系列発生器１１８を備えて、このＭ系列発生器１１８で、擬似ランダム系列であるＭ系列（Ｍａｘｉｍｕｍ　Ｌｅｎｇｔｈ　Ｃｏｄｅ　）符号を発生させる構成としてある。Ｍ系列発生器１１８が出力するＭ系列の値は、各ステートに対応したＡＣＳ回路１０２〜１０８に並列に入力される。なお、ここでのＭ系列符号の１周期は、ビタビ復号装置でトレースバックする際の、トレースの打ち切り長よりも長く設定してある。
【００４５】
ＡＣＳ回路１０１では、Ｍ系列発生器１１８が出力するＭ系列符号を、セレクタ１１６の他方の入力に供給する。そしてセレクタ１１６では、一致検出回路１１５で一致が検出されない状況の場合には、比較回路１１４で選択されたパスを示す信号を出力させ、一致検出回路１１５で一致が検出された状況の場合には、Ｍ系列発生器１１８から供給されるＭ系列符号を、パスを示す信号の代わりに出力させるようにしてある。
【００４６】
セレクタ１１６の出力は、パス選択情報Ｓ１１１としてＡＣＳ回路１０１から外部に出力されると共に、クリッピング回路１１３で処理された信号Ｓ１０７，Ｓ１０８を選択するセレクタ１１７に、制御信号として供給される。セレクタ１１７では、セレクタ１１６の出力により示されるパスの信号が選択され、その選択された信号が、新ステートメトリックＳ１１０として出力される。ここで、もし一致検出回路１１５で一致が検出されて、セレクタ１１６でＭ系列符号が選択された場合には、そのときのＭ系列の値が０であれば、図中の上側つまりオール０ステート（ステート０００）側のパスが選択され、Ｍ系列の値が１であれば、図中の下側つまりオール１ステート（ステート１１１）側のパスが選択されることになる。
【００４７】
同様に、ステート００１に対応するＡＣＳ回路１０２、‥‥、ステート１１１に対応するＡＣＳ回路１０８も、各ステートに合流する２本のパスのメトリックを比較し、２つのメトリックに違いがある場合には、尤度の高いパスを選択して新ステートメトリックを得る処理を行い、尤度が等しい場合には、Ｍ系列発生器１１８から供給されるＭ系列の値に基づいて選択されたパスの信号を新ステートメトリックとする処理を行う。
【００４８】
このようなＡＣＳ回路での処理動作を図２のフローチャートに示す。このフローチャートに従って順に説明すると、現ステートメトリックにブランチメトリックを加算し（ステップＳＴ２０１）、その加算された値が、ステートメトリックのビット幅で決まる最大値を超えていた場合に、その最大値にクリッピングさせる処理を、クリッピング回路１１３で行う（ステップＳＴ２０２）。その後、比較回路１１４で、次の時刻で合流するステートのメトリックの大小を比較し（ステップＳＴ２０３）、次時刻で合流するステートのメトリックが等しい値であるか否か判断する（ステップＳＴ２０４）。ここで、合流するステートのメトリックが等しい値である場合には、Ｍ系列の値に応じたメトリックを選択する（ステップＳＴ２０６）。また、合流するステートのメトリックが等しい値でない場合には、尤度の高い方（即ちの値の小さい方）のメトリックを選択する（ステップＳＴ２０５）。
【００４９】
ここで、Ｍ系列について説明する。Ｍ系列とは最長（符号）系列のことであり、ある段数のレジスタの出力の排他的論理和をフィードバックさせることで発生できる（符号）系列の中で最長の周期Ｌを持つもののことを言う。レジスタの段数をｎとした場合、Ｍ系列の周期ＬはＬ＝２ｎ　−１となる。Ｍ系列はシミュレーション等で擬似乱数としてよく用いられる。
【００５０】
図３はレジスタ段数ｎ＝８，周期Ｌ＝２５５のＭ系列を発生するＭ系列発生器の例を示したものである。図３に示すように、Ｍ系列発生器は多数（ｎ段）直列に接続されたレジスタと、そのレジスタの特定位置の信号を加算して排他的論理和を得る加算器とで構成されて、排他的論理和を初段のレジスタに戻す構成としてある。Ｍ系列を発生させるための、排他的論理和の挿入位置は原始多項式によって決定される。図３の例では、１＋Ｘ２　＋Ｘ３　＋Ｘ４　＋Ｘ８　という原始多項式に基づいて排他的論理和の挿入位置を決定している。これにより、レジスタの初期値を１１００１０００とした場合、１１００１０００００１０１１１０‥‥という系列が生成される。レジスタの初期値に関しては、オール０の系列以外であれば任意でよい。
【００５１】
図４は上述した図３に示したＭ系列によって得られたパス選択情報の系列が、トレースバック開始時刻以前の数タイムスロットにおいて、‥‥０１００１１０１１であった場合に決まるパス選択の例を示したものである。上述したＭ系列１１００１０００００１０１１１０‥‥は系列の前方から逐次ＡＣＳ回路において利用されるため、Ｍ系列が、トレースの打ち切り長の終端つまりトレースバック開始時刻とそれ以前の数タイムスロットにおいて‥‥０１００１１０１１という系列であったと仮定すれば、この系列の最後尾のビットがトレースバック開始時刻のパス選択情報に対応することになる。同値のステートメトリックの合流が起こったステートに対しては、この情報に基づいてトレースバックを行うことになる。
【００５２】
このようにＭ系列の擬似ランダムな特性を利用してパス選択の方向の偏りを軽減させることで、最尤復号できないパターン数を低減する効果を得ることが、本例のビタビ復号装置の特徴である。本例のビタビ復号装置は、従来のビタビ復号装置に対し、ｎ段のレジスタと排他的論理和で構成されるＭ系列発生器とステート数分のセレクタおよびステートメトリックの一致検出回路とを付加するのみであるため、回路規模の変更に要するコストは非常に小さいことが分かる。
【００５３】
このような処理を行った場合の復号トレリスの例を、図５に示す。この例では、従来例として説明した例の復号トレリス（図１７）と同じ条件の符号を受信した例としてあり、正しいパスが１０１０１０‥‥のパスであるとして、打ち切り長は十分に長いとすると、１０１０１０‥‥のパスを受信し続けた場合トレリスのステートメトリックはある定常状態にあると考えてよい。尤度の設定条件についても、図１７の例と同じであり、具体的には符号語の１シンボル当たりのシンボルメトリックは、符号語と受信語が一致していれば０、不一致ならば１５と計算し、メトリックは６３でクリッピングされるものとする。トレースバックを開始させるステートは図中の最も上側であるステート０００に設定してある。また、各受信時刻でのＭ系列の値を、図５の最も下側に示してある。
【００５４】
図５の例では、ステート０００からトレースバックを開始させる例であるが、このステート０００からのトレースバックで選択されるパスを、太い線で示してある。また、図５の受信例での正しいパスの遷移についても、太い線で示してある（トレースバック開始時の正しいステートはステート１０１）。
【００５５】
図５の例でステート０００からトレースバックを開始させた場合、そのステート０００に合流する２つのパスの尤度であるステートメトリックが６３で等しくなるが、そのときのＭ系列の値が１であるので、下側のパスが選択されるのでステート１００が選択される。次の段では、ステート１００に合流する２つのパスのステートメトリックが６３で等しくなり、そのときのＭ系列の値が１であるので、下側のパスが選択されるのでステート１１０が選択される。
【００５６】
次の段では、ステート１１０に合流する２つのパスの内、一方のステート０１１のパスのステートメトリックが６２で、ブランチメトリックが１５で、他方のステート１１１のパスのステートメトリックが６３で、ブランチメトリックが３０であるので、結局両方のパスの加算値は６３にクリッピングされた値となり、そのときのＭ系列の値に基づいたパスが選択される。このときのＭ系列の値は０であるので、上側のパスが選択されることになり、ステート０１１が選択される。
【００５７】
さらに次の段では、ステート０１１に合流する２つのパスの内、一方のステート００１のパスのステートメトリックが６３で、他方のステート１０１のパスのステートメトリックが３１で、ブランチメトリックが０であるので、ステート１０１のパスのメトリックの方が小さい（即ち尤度が高い）ことがＡＣＳ回路内で検出されて、ステート１０１のパスが選択されることになる。このステート１０１が選択されることで、受信データに基づいた正しいパスのステートと重なり、以後は、受信エラーがない限り、本来復号されるべきパスをトレースバックするようになる。従って、１０１０１０‥‥のパスにトレースバックがなされ、正しく復号できることが分かる。
【００５８】
このように本例のビタビ復号装置によると、従来のビタビ復号装置に比べて、回路規模の変更コストの増加を僅かに抑えつつ、正しく復号できないパスの種類を減らすことができる。
【００５９】
なお、以上説明した例は、拘束長Ｋ＝４、ステートメトリックのビット幅＝６ビット、ブランチメトリックのビット幅＝５ビットの場合を例としたが、これらはこの値に限らず、任意の値とすることがきる。正規化方法に関しても、各ステートメトリックの最上位ビットが全て１になった場合にその最上位ビットを反転するステートメトリック正規化方法にのみ限定されるものではなく、他の正規化方法を利用した場合の適用も考えられる。
【００６０】
また、ＡＣＳ回路内のクリッピングと比較の順序を入れ替えて行った場合に、本発明の処理を適用してもよい。一方、Ｍ系列に関して言えば、Ｍ系列のレジスタ段数ｎ＝８つまり周期Ｌ＝２ｎ　−１＝２５５、レジスタの初期値１１００１０００の場合を例としたが、これらはこの値に限らず任意の値とすることができる。ただし、Ｍ系列の周期Ｌはトレースの打ち切り長よりも長く設定する方が、本発明による効果をより期待できる。
【００６１】
また、本発明は、ランダム系列符号としてＭ系列符号を使用したが、Ｍ系列に限定されるものではなく、ランダム性を持つ系列であれば任意の系列を利用することが可能である。
【００６２】
【発明の効果】
以上述べたように、本発明によれば、ステートメトリック計算時に、あるステートに合流する２本のパスの尤度が等しい場合のパス選択をランダムに毎トレース時に切り換えることで行い、従来のビタビ復号装置に比べて回路規模の変更コストを極力小さく抑えつつ、正しく復号できないパスの種類を減らすことができるため、復号後のビット誤り率を改善することができるという効果が得られる。よって、本発明によって、復号後のビット誤り率が改善することができるようになる。
【図面の簡単な説明】
【図１】本発明の一実施の形態によるビタビ復号装置のＡＣＳ回路の例を示すブロック図である。
【図２】図１例の構成でのＡＣＳ回路の動作を示すフローチャートである。
【図３】Ｍ系列発生器の構成例を示したブロック図である。
【図４】図３のＭ系列発生器の構成で生成されるＭ系列で決まるパス選択の例を示すブロック図である。
【図５】本発明の一実施の形態でトレースバックを行った場合の復号トレリスを示す説明図である。
【図６】従来のビタビ復号装置の構成例を示すブロック図である。
【図７】従来のＡＣＳ回路の構成例を示すブロック図である。
【図８】従来のＡＣＳ回路の動作例を示すフローチャートである。
【図９】拘束長Ｋ＝４の畳み込み符号の場合の遷移ダイアグラムである。
【図１０】レジスタ遷移法におけるメモリセルの構成例を示したブロック図である。
【図１１】レジスタ遷移法におけるメモリセルの配置例を示した構成図である。
【図１２】トレースバック法におけるトレースの原理を示した説明図である。
【図１３】トレースバック法におけるトレース方法を示した説明図である。
【図１４】拘束長Ｋ＝４の畳み込み符号化器の例を示したブロック図である。
【図１５】拘束長Ｋ＝４の畳み込み符号の状態遷移図である。
【図１６】同値のステートメトリックが合流した際のパス選択を示す説明図である。
【図１７】従来の復号トレリスの例を示す説明図である。
【符号の説明】
１０１〜１０８…ＡＣＳ回路（比較及び加算回路）、１１１，１１２…加算器、１１３…クリッピング回路、１１４…比較回路、１１５…一致検出回路、１１６，１１７…セレクタ、６００…シンボルメトリック計算回路、６０１…ブランチメトリック計算回路、６０２…ＡＣＳ回路、６０３…正規化回路、６０４…ステートメトリック記憶回路、６０５…パスメモリ回路、７０１〜７０８…ＡＣＳ回路（比較及び加算回路）、７１１，７１２…加算器、７１３…クリッピング回路、７１４…比較回路、７１５…セレクタ、１０００…メモリセル、１００１…セレクタ、１００２…レジスタ、１１００〜１１０７，１１１０〜１１１７，１１２０〜１１２７，１１３０〜１１３７…メモリセル
【図１】
2004140454.tif 000003
【図２】
2004140454.tif 000004
【図３】
2004140454.tif 000005
【図４】
2004140454.tif 000006
【図５】
2004140454.tif 000007
【図６】
2004140454.tif 000008
【図７】
2004140454.tif 000009
【図８】
2004140454.tif 000010
【図９】
2004140454.tif 000011
【図１０】
2004140454.tif 000012
【図１１】
2004140454.tif 000013
【図１２】
2004140454.tif 000014
【図１３】
2004140454.tif 000015
【図１４】
2004140454.tif 000016
【図１５】
2004140454.tif 000017
【図１６】
2004140454.tif 000018
【図１７】
2004140454.tif 000019