(57)【特許請求の範囲】
【請求項１】
誤り訂正符号によって符号化された受信系列を復号するビタビ復号器において、
複数のブランチメトリックを記憶した記憶部と、
受信系列が入力された場合に、前記記憶部に記憶されたブランチメトリックを用いて各状態に対する生き残りパス選択処理を行う制御部とを備え、
前記記憶部は、受信系列のパターンに応じて用意され、各状態に応じたブランチメトリックを保持した複数のテーブルを記憶し、
各テーブルは、各状態に入り込む２つのブランチのブランチメトリックがトレリスを構成するブランチの順で前記制御部によって読み出されるように、１つ前の状態に対応するアドレスの次のアドレスに各ブランチメトリックを保持することを特徴とするビタビ復号器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、誤り訂正符号の復号法に係る分野において、誤り訂正符号によって符号化された受信系列をプロセッサによる演算処理で復号するビタビ復号器に関する。
【０００２】
【従来の技術】
通信分野や情報処理分野では、通信の信頼性や情報処理の信頼性を向上させる必要性があることから、“誤り訂正符号”が使用されており、その結果、高性能な誤り訂正符号の復号法が必要とされている。最も効果的な誤り訂正符号の復号法の１つには、誤り訂正符号化された受信系列を最尤復号するビタビ復号法があり、誤り訂正能力が特に優れているので、広く用いられている。
【０００３】
以下に、ビタビ復号法の例を示す。図２１は、ビタビ復号法において利用されるトレリスの例を示す図である。ビタビ復号法では、図２１に示すトレリスを用いて最尤復号が行われる。
【０００４】
図２１において、各状態Ｓｋ(ｋ＝０,１,２,・・・)に入り込む２つのブランチ(枝)は、ブランチ出力値と呼ばれる値を夫々持っている。また、図中の各状態Ｓｋの下に記載してある数値はパスメトリックと呼ばれ、状態Ｓｋに至るブランチメトリックの最小和である。
【０００５】
例えば、現在の時刻がＴ１であるとき、はじめに、状態Ｓ０において、状態Ｓ０に入り込む２つのブランチ(ブランチ０,ブランチ１)と受信系列と間のブランチメトリック(ハミング距離)が夫々計算される。
【０００６】
各ブランチ０,１のブランチメトリック(ブランチ０＝１,ブランチ１＝１)が求められると、ブランチ０が１つ前の時刻Ｔ０につながっている状態Ｓ０のパスメトリックが呼び出され、ブランチ０のブランチメトリックと足し合わせた値Ｐ１が求められる。即ち、
Ｐ１＝ブランチ0のブランチメトリック(=1)＋状態Ｓ０のパスメトリック(=2)＝３
が求められる。同様に、ブランチ１が１時刻前のＴ０につながっている状態Ｓ２のパスメトリックとブランチ１のブランチメトリックを足し合わせた値Ｐ２が求められる。即ち、
Ｐ２＝ブランチ0のブランチメトリック(=1)＋状態Ｓ２のパスメトリック(=101)＝１０２
が求められる。
【０００７】
次に、Ｐ１とＰ２との大きさが比較され、小さい方(Ｐ１＝３)が時刻Ｔ１の状態Ｓ０のパスメトリックとして記憶される。また、図２１では、選択されたブランチ０が１時刻前の状態Ｓ０から遷移するために、情報ビット“０”が入力されているので、この値が記憶される。図２１に示すトレリスでは、太線が上記手法によって選択されたパスを示している。
【０００８】
以上の処理を全ての状態Ｓｋ(ｋ＝０,１,２,・・・)と全ての時刻とについて行った後に、例えば、送信側と受信側との事前のネゴシエーションによって、トレリスが最終的に時刻Ｔ２の状態Ｓ３で終了することが解っている場合には、トレリスを時刻Ｔ２の状態Ｓ３から時刻Ｔ０に向かって太線の生き残りパスを辿り(「バックトレース」と称する)、太線の実線だったら“０”を、太線の破線だったら“１”を出力すれば、復号した符号系列を入力時と逆向きに出力することができる。
【０００９】
このようにして、ビタビ復号法では、送信側で送信したと考えられることが最も確からしい符号系列を推定し、伝送路での誤りを除去する。
【００１０】
【発明が解決しようとする課題】
上述したビタビ復号法を実現するビタビ復号器は、既に提案されている。近年では、ビタビ復号器をハードウェアのみで構成するのではなく、ソフトウェア(ファームウェア)及びプロセッサにて構成する傾向にある。ビタビ復号器をソフトウェアを用いて実現する場合、処理速度がハードウェアよりも低下することは避けられないので、演算量(処理量)を少なくする必要がある。特に、ビタビ復号法を含む最尤復号法は、演算量が比較的多いので、可能な限り演算量が削減されることが望まれる。
【００１１】
本願出願人は、ビタビ復号法をプロセッサによる演算処理にて実現するビタビ復号器を既に提案している(特開平７−３０４３８号公報参照：以下、「先行例」と称する)。先行例では、ブランチメトリックの計算のために、受信系列に対応するブランチメトリックをテーブルとして保持し、受信系列が入力されると、その受信系列からブランチメトリックのテーブルへアクセスするためのアドレスが算出され、そのアドレスに対応するブランチメトリックがテーブルから読み出されることで、ブランチメトリックの算出に要する演算量が削減される。
【００１２】
しかしながら、先行例は、ランダムアクセスによってテーブルからブランチメトリックを読み出す構成であるため、ブランチメトリックを読み出す度にアドレスを生成するための演算を要し、ブランチメトリックの算出に時間を要する問題があった。
【００１３】
また、テーブルに予め保持されるブランチメトリックが膨大な量となっていたため、テーブルを記憶するメモリの記憶容量を大きくせざるを得ないという問題もあった。
【００１４】
本発明は、上記問題に鑑みなされたものであり、ブランチメトリックの計算に要する時間を短縮することができるとともに、ブランチメトリックの計算に用いるテーブルに必要なメモリ量を削減することができるビタビ復号器を提供することを課題とする。
【００１５】
【課題を解決するための手段】
本発明は、上述した課題を解決するために以下の構成を採用する。すなわち、請求項１の発明は、誤り訂正符号によって符号化された受信系列を復号するビタビ復号器において、複数のブランチメトリックを記憶した記憶部と、受信系列が入力された場合に、前記記憶部に記憶されたブランチメトリックを用いて各状態に対する生き残りパス選択処理を行う制御部とを備え、前記記憶部は、受信系列のパターンに応じて用意され、各状態に応じたブランチメトリックを保持した複数のテーブルを記憶し、各テーブルは、各状態に入り込む２つのブランチのブランチメトリックがトレリスを構成するブランチの順で前記制御部によって読み出されるようにブランチメトリックを保持することを特徴とする。
【００１６】
請求項２の発明は、誤り訂正符号によって符号化された受信系列を復号するビタビ復号器において、複数のブランチメトリックを記憶した記憶部と、受信系列が入力された場合に、前記記憶部に記憶されたブランチメトリックを用いて各状態に対する生き残りパス選択処理を行う制御部とを備え、前記記憶部は、受信系列のパターンに応じて用意され、各状態に応じたブランチメトリックを保持した複数のテーブルを記憶し、各テーブルは、或る状態に入り込む２つのブランチのブランチメトリックが一方のブランチメトリックから他方のブランチメトリックを求めることが可能である場合には、何れか一方のブランチメトリックのみを保持し、前記制御部は、受信系列に応じたテーブルから或る状態に入り込む２つのブランチの何れか一方のブランチメトリックのみを読み出した場合には、この一方のブランチメトリックから他方のブランチメトリックを求めることを特徴とする。
【００１７】
例えば、各テーブルは、或る状態に入り込む２つのブランチの出力値が相互に各ビットを反転させた符号となっている場合には、何れか一方のブランチのブランチメトリックのみを保持する。
【００１８】
請求項３の発明は、誤り訂正符号によって符号化された受信系列を復号するビタビ復号器において、複数のブランチメトリックを記憶した記憶部と、受信系列が入力された場合に、前記記憶部に記憶されたブランチメトリックを用いて各状態に入り込む２つのブランチに対応するパスメトリックを計算することによって各状態に対する生き残りパス選択処理を行う制御部とを備え、前記記憶部は、受信系列のパターンに応じて用意され、各状態に応じたブランチメトリックを保持した複数のテーブルを記憶し、各テーブルは、状態に応じたブランチメトリックとして、０対称となるように変換された或る状態に入り込む２つのブランチのブランチメトリックの何れか一方のみを保持し、前記制御部は、受信系列に応じたテーブルから０対称の２つのブランチのブランチメトリックの何れか一方のみを読み出した場合には、この一方のブランチメトリックを用いて各状態に入り込む２つのブランチに対応するパスメトリックを計算することを特徴とする。
【００１９】
請求項４の発明は、誤り訂正符号によって符号化された受信系列を復号するビタビ復号器において、複数のブランチメトリックを記憶した記憶部と、受信系列が入力された場合に、前記記憶部に記憶されたブランチメトリックを用いて各状態に入り込む２つのブランチに対応するパスメトリックを計算することによって各状態に対する生き残りパス選択処理を行う制御部とを備え、前記記憶部は、受信系列のパターンに応じて用意され、各状態に応じたブランチメトリックを保持した複数のテーブルを記憶し、各テーブルは、各状態に応じたブランチメトリックとして、或る状態に入り込む２つのブランチのブランチメトリックであって一方のブランチメトリックから他方のブランチメトリックを求めることが可能なブランチメトリックの何れか一方を保持し、さらに隣り合う状態同士が同じブランチメトリックを持つものをグループ化して保持し、前記制御部は受信系列に応じたテーブルからグループ化されたブランチメトリックを読み出し、読み出したブランチメトリックに応じた各状態に係るパスメトリックを夫々計算することを特徴とする。
【００２０】
請求項５の発明は、誤り訂正符号によって符号化された受信系列を復号するビタビ復号器において、複数のブランチメトリックを記憶した記憶部と、受信系列が入力された場合に、前記記憶部に記憶されたブランチメトリックを用いて各状態に入り込む２つのブランチに対応するパスメトリックを計算することによって各状態に対する生き残りパス選択処理を行う制御部とを備え、前記記憶部は、受信系列のパターンに応じて用意され、各状態に応じたブランチメトリックを保持した複数のテーブルを記憶し、各テーブルは、各状態に応じたブランチメトリックとして、或る状態に入り込む２つのブランチのブランチメトリックであって一方のブランチメトリックから他方のブランチメトリックを求めることが可能なブランチメトリックの何れか一方を保持し、さらに隣り合う状態同士が正負反対のブランチメトリックを持つものをグループ化して保持し、前記制御部は受信系列に応じたテーブルからグループ化されたブランチメトリックを読み出し、読み出したブランチメトリックに応じた各状態に係るパスメトリックを夫々計算する
ことを特徴とする。
【００２１】
請求項６の発明は、誤り訂正符号によって符号化された受信系列を復号するビタビ復号器において、複数のブランチメトリックを記憶した記憶部と、受信系列が入力された場合に、前記記憶部に記憶されたブランチメトリックを用いて各状態に入り込む２つのブランチに対応するパスメトリックを計算することによって各状態に対する生き残りパス選択処理を行う制御部とを備え、前記記憶部は、受信系列のパターンに応じて用意され、各状態に応じたブランチメトリックを保持した複数のテーブルを記憶し、各テーブルは、各状態に応じたブランチメトリックとして、或る状態に入り込む２つのブランチのブランチメトリックであって一方のブランチメトリックから他方のブランチメトリックを求めることが可能なブランチメトリックの何れか一方を保持し、さらに、隣り合う状態同士のブランチメトリックが同じでなく且つ正負反対でもない場合に、状態同士が隣合わないがブランチメトリックが同じであるものをグループ化して保持し、前記制御部は受信系列に応じたテーブルからグループ化されたブランチメトリックを読み出し、読み出したブランチメトリックに応じた各状態に係るパスメトリックを夫々計算することを特徴とする。
【００２２】
請求項７の発明は、誤り訂正符号によって符号化された受信系列を復号するビタビ復号器において、複数のブランチメトリックを記憶した記憶部と、受信系列が入力された場合に、前記記憶部に記憶されたブランチメトリックを用いて各状態に対する生き残りパス選択処理を行う制御部とを備え、前記記憶部は、特定の受信系列とこの特定の受信系列のパターンを反転した受信系列とに共通なテーブルを記憶し、前記制御部は、前記特定の受信系列又はこの受信系列を反転した受信系列が入力された場合に、前記テーブルに記憶されたブランチメトリックを読み出して各状態に対する生き残りパス選択処理を行うことを特徴とする。
【００２３】
請求項８の発明は、誤り訂正符号によって符号化された受信系列を復号するビタビ復号器において、複数のブランチメトリックを記憶した記憶部と、受信系列が入力された場合に、前記記憶部に記憶されたブランチメトリックを用いて各状態に入り込む２つのブランチに対応するパスメトリックを計算することによって各状態に対する生き残りパス選択処理を行う制御部とを備え、前記制御部は、受信系列の送信側とのネゴシエーションによって決定された、受信系列の復号に適用されるトレリスが前記制御部に入力された受信系列に応じて各状態に係るブランチメトリックを前記記憶部からシーケンシャルアクセスによって読み出すことができないものである場合に、当該トレリスの構造を制御部がブランチメトリックをシーケンシャルアクセスによって読み出すことが可能な状態に変換し、構造が変換されたトレリスに応じた各状態のブランチメトリックを保持したテーブルを作成することを特徴とする。
【００２４】
【発明の実施の形態】
以下、図面を参照して本発明の実施形態を詳細に説明する。
〔実施形態１〕
〈ビタビ復号器の構成〉
図１は、本発明の実施形態によるビタビ復号器の構成図である。このビタビ復号器は、自身に入力された受信系列をビタビ復号法に用いて復号し、図示せぬ送信側から送信されたと考えられる最も確からしい情報系列を推定し、出力することによって、送信側と受信側との間における伝送路での符号誤りを除去するものである。
【００２５】
図１において、ビタビ復号器は、ワーク領域１１と、ＡＣＳ(Add Compare Select：加算・比較・選択)回路１２(制御部に相当)と、ブランチメトリックメモリ１３(記憶部に相当)と、パスメトリックメモリ１４と、パスメモリ１５とからなる。
【００２６】
ここに、ワーク領域１１は、ビタビ復号器の作業領域として利用される。このワーク領域１１には、復号対象となる受信系列が入力される。本実施形態における受信系列は、誤り訂正符号によって符号化された時刻ｔに対応する２ビット符号(“００”,“０１”,“１０”,“１１”の何れか)である。
【００２７】
ＡＣＳ回路１２は、ワーク領域１１に入力された受信系列を用いて、生き残りパス選択処理(図３参照)を行う。
ブランチメトリックメモリ１３には、ＡＣＳ回路１２によるブランチメトリックの計算に際して用いられるブランチメトリックテーブル１６が、予め保持されている。
【００２８】
図２は、図１に示したブランチメトリックメモリ１３に保持されたブランチメトリックテーブル１６の例を示す説明図である。図２において、ブランチメトリックテーブル１６は、ワーク領域１１に入力される受信系列のパターンに応じて用意されたテーブル１６ａ〜１６ｄからなる。
【００２９】
各テーブル１６ａ〜１６ｄは、各状態Ｓｋ(ｋ＝０,１,２,３・・・)に入り込む２つのブランチに対応するブランチメトリックを格納しており、各ブランチメトリックは、状態Ｓ０，状態Ｓ１，状態Ｓ２，状態Ｓ３の順でシーケンシャルに並べて保持されている。即ち、各状態Ｓ１〜Ｓ３に対する各ブランチメトリックは、１つ前の状態に対応するアドレスの次のアドレスに格納されている。なお、各ブランチメトリックの値は、例として、図２１に示したトレリスに応じて設定されている。
【００３０】
パスメトリックメモリ１４は、現在の状態に入り込む２つのブランチが接続されている過去(１時刻前)の各状態におけるパスメトリックを保持している。
なお、図１に示したビタビ復号器は、実際には、ＤＳＰ(Data Signal Processor)，半導体メモリ等の記憶装置，及びビタビ復号法を実行するためのソフトウェア等の組み合わせにより実現される。
【００３１】
〈ビタビ復号器による処理〉
図３は、実施形態１におけるビタビ復号器による処理を示すフローチャートである。図３中に示された文字は、図４に示す定義を持つ。なお、図３において、破線で囲んだステップは、ＡＣＳ回路１２による生き残りパス選択処理を示す。
【００３２】
図３に示す処理は、受信系列がワーク領域１１に入力されることによって開始される。ワーク領域１１には、時刻ｔに対応する受信系列が次々と入力される。受信系列がワーク領域１１に入力されると、最初に入力された受信系列が特定され、ワーク領域１１に保持されている時刻ｔがｔ＝Ｔ０に設定され(Ｓ０１)、ワーク領域１１に保持されている状態Ｓｋがｋ＝０に設定される(Ｓ０２)。
【００３３】
次に、ＡＣＳ回路１２が、特定された受信系列についての状態Ｓtkに対して、各ブランチｂt2k，ｂt2k+1(現在の状態Ｓtkに入り込む２つのブランチ)に対応するブランチメトリックをブランチメトリック１３から夫々読み出し、ワーク領域１１に保持されている各代数ｂ１，ｂ２に代入する(Ｓ０３)。
【００３４】
即ち、ＡＣＳ回路１２は、特定された受信系列に対応するテーブルを、図２に示すテーブル１６ａ〜１６ｄの中から選択し、選択したテーブルにおける現在の状態Ｓtkに応じた位置に図示せぬリードポインタを合わせる。
【００３５】
例えば、処理がスタートしてから最初のＳ０３の処理では、状態Ｓｋは、ｋ＝０，即ち状態Ｓ０である。このとき、ｔ＝Ｔ０のときの受信系列が例えば“００”である場合には、ＡＣＳ回路１２は、テーブル１６ａの状態Ｓ０に対応する各ブランチのブランチメトリックの読み出し位置(最初の(先頭の)アドレス)にリードポインタを合わせ、各ブランチメトリック(ブランチ０＝０，ブランチ１＝２)を読み出し、これらをワーク領域１１に保持されている各代数ｂ１,ｂ２に代入する。
【００３６】
次に、ＡＣＳ回路１２は、各ブランチｂt2k，ｂt2k+1のブランチ出力値を用いて、各ブランチｂt2k，ｂt2k+1が接続されている各過去の状態(１時刻前の状態)におけるパスメトリックをパスメトリックメモリ１４から読み出し、ワーク領域１１に保持されている各代数ｐ１，ｐ２に夫々代入する(Ｓ０４)。
【００３７】
次に、ＡＣＳ回路１２は、ワーク領域１１に保持されている各代数ｂ１,ｂ２,ｐ１,ｐ２を用いて、Ｐ１＝ｂ１＋ｐ１，Ｐ２＝ｂ２＋ｐ２を計算し、計算結果をワーク領域１１に格納する(Ｓ０５)。
【００３８】
次に、ＡＣＳ回路１２は、ワーク領域１１に保持されているＰ１,Ｐ２のうち小さい方を、状態Ｓtkのパスメトリックとしてパスメトリックメモリ１４に格納する(Ｓ０６)。
【００３９】
次に、ＡＣＳ回路１２は、Ｐ１,Ｐ２のうち小さい方に対応するブランチをパスメモリ１５に格納する(Ｓ０７)。このようにして、ＡＣＳ回路１２によって選択された生き残りパスがパスメモリ１５に記憶される。
【００４０】
次に、現在の状態を示すｋの値が所定の状態数(状態数＝３)以上か否か(ｋ≧状態数)が判定され(Ｓ０８)、そうである場合(Ｓ０８；Ｙ)には、ｋに１が加算され(Ｓ０９)、処理がＳ０３に戻され、次の状態に対するＳ０３〜Ｓ０７の処理(パスメトリックの計算)が行われる。
【００４１】
このとき、Ｓ０３において、ＡＣＳ回路１２は、前回のＳ０３にてアクセスされたアドレスの次のアドレスにリードポインタを移動させる。例えば、前回のＳ０３にて、リードポインタが状態Ｓ０に合わせられている場合には、次のアドレスである状態Ｓ１にリードポインタが合わせられ、状態Ｓ１における各ブランチメトリックが読み出される。
【００４２】
このように、或る受信系列に対する２巡目以降のＳ０３の処理では、ＡＣＳ回路１２がリードポインタの位置を次のアドレスに移動させる(１インクリメントする)ことによって、当該受信系列に対応する各ブランチメトリックが、テーブル１６ａ〜１６ｄの何れかから、状態Ｓ１，状態Ｓ２，状態Ｓ３の順でシーケンシャルに読み出される。このように、或る受信系列に対する２巡目以降のＳ０３の処理では、アドレス生成処理を要しないので、各状態Ｓtkに対する各ブランチメトリックの計算に要する時間が短縮される。
【００４３】
一方、Ｓ０８において、ｋの値が状態数未満と判定された場合(Ｓ０８；Ｎ)には、時刻ｔが時刻Ｔを上回るか否かが判定され(Ｓ１０)、時刻ｔが時刻Ｔを上回る場合(Ｓ１０；Ｙ)には、ワーク領域１１に入力された受信系列の全てに対する処理が終了したものとして、図３に示す処理が終了する。
【００４４】
これに対し、Ｓ１０において、時刻ｔがＴ以下の場合(Ｓ１０；Ｎ)には、時刻ｔが現在の時刻ｔに１を加算した値に設定される。例えば、現在の時刻ｔがｔ＝Ｔ０である場合には、時刻ｔがｔ＝Ｔ１に設定される。その後、処理がＳ０２に戻り、次の受信系列に対し、Ｓ０２〜Ｓ１１の処理が行われる。
【００４５】
以上のようにして、全ての受信系列に対する図３の処理が終了した場合には、パスメモリ１５が、各受信系列に対応する生き残りパスの情報を保持した状態となる。その後、従来と同様に、パスメモリ１５に保持された生き残りパスの情報を用いてバックトレース処理が行われ、これによって、送信側から送信されたと推定される符号系列がパスメモリ１５から出力される。
【００４６】
〈実施形態１の作用〉
実施形態１によるビタビ復号器によると、ブランチメトリックの計算に使用されるブランチメトリックテーブル１６が、受信系列のパターンに応じて用意されたテーブル１６ａ〜１６ｄからなり、各テーブル１６ａ〜１６ｄには、各状態Ｓｋに応じたブランチメトリックがシーケンシャルに保持されている。
【００４７】
このため、ＡＣＳ回路１２は、或る時刻ｔにおいて、或る状態Ｓtkの次の状態Ｓtk+1に対応する各ブランチメトリックを求める場合に、リードポインタの位置を１インクリメントすること(シーケンシャルアクセス)によって、該当する各ブランチメトリックを得ることができる。
【００４８】
従って、従来のビタビ復号器(先行例)のように、ランダムアクセスによってテーブルからブランチメトリックを読み出す場合に比べて、ブランチメトリックの計算に要する時間が短縮される。
【００４９】
ブランチメトリックの計算は量が多いので、１回のブランチメトリックの計算(１回のＳ０３の処理)に要する時間が短ければ短い程、受信系列の復号に要する時間を短縮することができる。従って、実施形態１のビタビ復号器によれば、従来のビタビ復号器(先行例)に比べて、受信系列の復号速度の向上を図ることができる。
【００５０】
また、先行例に比べて、ブランチメトリックテーブル１６に保持されるブランチメトリックの量を減らすことができるので、ブランチメトリックテーブル１６を保持するブランチメトリックメモリ１３の記憶容量を、先行例に比べて小さくすることができる。
【００５１】
〔実施形態２〕
次に、本発明の実施形態２によるビタビ復号器について説明する。但し、実施形態２は、実施形態１と共通点を有するので、実施形態１との相違点についてのみ説明する。
【００５２】
トレリスを構成する各状態Ｓｋ(ｋ＝０,１,２,・・・)に入り込む２つのブランチのブランチ出力値は、通常、誤り訂正能力を最大にするために、その間のブランチメトリック(ハミング距離)が最大になるように設定されている。例えば、図２１に示すトレリスでは、ブランチ０のブランチ出力値が“００”であるのに対し、ブランチ１のブランチ出力値が“１１”であるように、一方のブランチ出力値のビットは、他方のブランチ出力値のビットを反転させたものとなっている。
【００５３】
このことから、受信系列の如何に拘わらず、ブランチｂt2kに対するブランチｂt2k+1のブランチメトリックは、ブランチ出力値が２ビットであることを考慮し、
ブランチ１のブランチメトリック＝２−ブランチ０のブランチメトリック
により求めることができる。上記式を一般的にすれば、
ブランチｂt2k+1のブランチメトリック＝Const(定数:C)−ブランチｂt2kのブランチメトリック
(k=0,1,2,・・・)
で求めることができる。この性質を利用すれば、ブランチメトリックテーブルには、ある状態Ｓｋ(ｋ＝０,１,２,・・)に入り込む２つのブランチのどちらか一方のブランチメトリックを記憶しておくだけで済むこととなる。
【００５４】
図５は、上述した手法によって得られる実施形態２におけるブランチメトリックテーブル２６の例を示す説明図である。図５において、ブランチメトリックテーブル２６は、受信系列(２ビット符号)のパターンに応じて用意されたテーブル２６ａ〜２６ｄからなる。各テーブル２６ａ〜２６ｄは、各状態Ｓｋにおける一方のブランチのブランチメトリックのみを保持している。
【００５５】
この例では、各テーブル２６ａ〜２６ｄは、各状態Ｓtkにおけるブランチの番号が若い方(ブランチｂt2k)に対応するブランチメトリックのみを保持している。例えば、テーブル２６ａには、状態Ｓ０に対応する各ブランチのブランチメトリックとして、ブランチ０のブランチメトリックのみが保持されている。
【００５６】
また、各テーブル２６ａ〜２６ｄは、実施形態１(各テーブル１６ａ〜１６ｄ)と同様に、各状態Ｓｋに対応するブランチメトリックをシーケンシャルに(状態Ｓ０，状態Ｓ１，状態Ｓ２，状態Ｓ３の順で)保持している。
【００５７】
実施形態２によるビタビ復号器は、実施形態１と同様の構成を有する(図１参照)。但し、ブランチメトリックメモリ１３が、ブランチメトリックテーブル１６(図２参照)の代わりに、図５に示したブランチメトリックテーブル２６を保持している。
【００５８】
図６は、実施形態２におけるビタビ復号器による処理を示すフローチャートである。図６に示すように、実施形態２におけるビタビ復号器は、Ｓ２０３の処理を除き、実施形態１とほぼ同様の処理を行う(図３参照)。このため、Ｓ２０３の処理についてのみ説明し、その他のステップの説明は省略する。
【００５９】
Ｓ２０３において、ＡＣＳ回路１２は、状態Ｓtkに対して、ブランチメトリックメモリ１３からブランチｂt2kのブランチメトリックを読み出し、代数ｂ１に代入し、ブランチｂt2k+1(ｂ２)に関しては、ｂt2k+1(ｂ２)＝Ｃ(定数)−ｂ１を計算する。
【００６０】
即ち、ＡＣＳ回路１２は、処理対象に該当する受信系列に対応するテーブルを図５に示すテーブル２６ａ〜２６ｄの中から選択し、選択したテーブルから、現在の状態Ｓtkに応じたブランチに対応するブランチメトリックを読み出す。
【００６１】
このとき、ＡＣＳ回路１２は、テーブル２６ａ〜２６ｄの何れかから、ブランチの番号の若い方(ｂt2k)のブランチメトリックを読み出し、ワーク領域１１に保持されている代数ｂ１に代入する。そして、代数ｂ１を用いてｂ２＝Ｃ−ｂ１を計算することで、状態Ｓtkに入り込むもう一つのブランチｂt2k+1に対応するブランチメトリックを算出し、代数ｂ２とする。
【００６２】
その後、再びＳ２０３の処理にて、ブランチメトリックテーブル２６からブランチメトリックが読み出される場合には、ＡＣＳ回路１２は、実施形態１と同様に、リードポインタの位置を１インクリメントし、次の状態に入り込むブランチに対応するブランチメトリックを読み出す。このように、ブランチメトリックテーブル２６に対するアクセスがシーケンシャルに行われるので、実施形態１と同様に、ブランチメトリックの計算に要する時間を短縮することができる。
【００６３】
実施形態２のビタビ復号器は、実施形態１とほぼ同様の効果を奏する。さらに、実施形態２のビタビ復号器によれば、実施形態１に比べて、ブランチメトリックテーブルに保持されるブランチメトリックの量を１／２に削減することができる。このため、ブランチメトリックメモリ１３の記憶容量を実施形態１に比べて小さくすることができる。
【００６４】
〔実施形態３〕
次に、本発明の実施形態３によるビタビ復号器について説明する。但し、実施形態３は、実施形態１,２と共通点を有するので、実施形態１,２との相違点についてのみ説明する。
【００６５】
実施形態２では、各ブランチのブランチメトリックの計算には、ブランチｂt2k+1のブランチメトリックは、(Ｃ(定数)−(ブランチｂt2kのブランチメトリック))の式を用いて求められた。上記式において、定数Ｃはパンクチャレートによって異なる。このため、例えば、ある１つの状態Ｓ０のパスメトリックの決定には以下の計算を要する。
(１)状態Ｓ０のパスメトリックの候補＝ブランチ０のブランチメトリック＋ブランチ０の一時刻前のパスメトリック
(２)Ｃ＝定数Const(パンクチャレートに依存)
(３)ブランチ１のメトリック＝Ｃ−ブランチ０のメトリック
(４)状態Ｓ０のパスメトリックの候補＝ブランチ１のブランチメトリック＋ブランチ１の一時刻前のパスメトリック
(５)状態Ｓ０のパスメトリック＝ｍｉｎ[(１),(２)]
ここで、ブランチメトリックメモリ中に受信系列とブランチ出力値との間のブランチメトリックをそのまま記憶するのではなく、以下の変換式を用いることで、ブランチメトリックを別のブランチメトリックに変換でき、ブランチメトリックの計算量を削減することができる。
ｘ：ブランチＮ(Ｎは偶数)のブランチメトリック
ｙ：ブランチＮ＋１のブランチメトリック
ａ＝(ｘ−ｙ)×Ｃ(Ｃ＝定数) ・・・〔変換式〕
ブランチＮの変換後のブランチメトリックｘ’は
ｘ’＝  ａ(ｘ＞ｙ)
ｘ’＝−ａ(ｘ＜ｙ)
ｘ’＝０  (ｘ＝ｙ)
また、ブランチＮ＋１のメトリックは、
ｙ’＝−ｘ’
例えば、今、図５に示したブランチメトリックテーブル２６を例として挙げれば、受信系列“００”に対応するテーブル２６ａにおいて、ブランチ０のブランチメトリック＝０，ブランチ１のブランチメトリック＝２である。これらについて上記した〔変換式〕を用いれば、ブランチ０のブランチメトリック＝−１，ブランチ１のブランチメトリック＝１となり、各ブランチメトリックの値を０対称とすることができる。
【００６６】
図７は、上記手法によって得られた実施形態３におけるブランチメトリックテーブル３６の例を示す説明図である。図７に示すように、ブランチメトリックテーブル３６をなす各テーブル３６ａ〜３６ｄは、図５に示したテーブル２６ａ〜２６ｂに保持されていたブランチメトリックを上記〔変換式〕によって変換した場合におけるブランチメトリックを保持している。
【００６７】
また、各テーブル３６ａ〜３６ｄは、各テーブル２６ａ〜２６ｄと同様に、各状態Ｓtkに対応するブランチメトリックをシーケンシャルに(状態Ｓ０，状態Ｓ１，状態Ｓ２，状態Ｓ３の順で)保持している。
【００６８】
実施形態３におけるビタビ復号器は、実施形態１と同様の構成を有する(図１参照)。但し、ブランチメトリックメモリ１３が、ブランチメトリックテーブル１６(図２参照)の代わりに、図７に示したブランチメトリックテーブル３６を保持している。
【００６９】
図８は、実施形態３におけるビタビ復号器による処理を示すフローチャートである。図８に示すように、実施形態３のビタビ復号器は、Ｓ３０３,Ｓ３０５の処理を除き、実施形態１とほぼ同様の処理を行う(図３参照)。このため、Ｓ３０３,Ｓ３０５の処理についてのみ説明し、その他のステップの説明は省略する。
【００７０】
Ｓ３０３において、ＡＣＳ回路１２は、状態Ｓtkに対して、ブランチメトリックメモリ１３からブランチｂt2kのブランチメトリックを読み出し、代数ｂ１に代入する。
【００７１】
その後、ＡＣＳ回路１２は、Ｓ３０５において、Ｓ３０４にて得たｐ１,ｐ２を用いて、Ｐ１＝ｂ１＋ｐ１，Ｐ２＝−ｂ１＋ｐ２を計算する。即ち、ブランチｂt2k+1(ｂ２)のブランチメトリックに関しては、予めｂ１とｂ２が０対称となるように設定されているので、ｂ２の代わりに−ｂ１を用いてＰ２を求めることができる。
【００７２】
実施形態３におけるビタビ復号器は、実施形態１と同様に、ブランチメトリックテーブル３６に対してシーケンシャルアクセスすることができることで、先行例よりもＡＣＳ回路１２の処理速度を速めることができ、実施形態２と同様に、実施形態１に比べてブランチメトリックメモリ１３の記憶容量を減らすことができる。
【００７３】
さらに、実施形態３によれば、上述したように、図８に示した処理において、ＡＣＳ回路１２は、全ての受信系列に対する全ての状態の生き残りパス選択処理，例えば受信系列“００”に対する状態Ｓ０の生き残りパス選択処理を、
▲１▼状態０のパスメトリックの候補＝ブランチ０のブランチメトリック(＝−１)＋ブランチ０の一時刻前のパスメトリック(Ｓ３０５参照)
▲２▼状態０のパスメトリックの候補＝ブランチ１のメトリック(＝１)＋ブランチ１の一時刻前のパスメトリック(Ｓ３０５参照)
▲３▼状態０のパスメトリック＝ｍｉｎ[▲１▼,▲２▼](Ｓ３０６,Ｓ３０７参照)
の計算のみで行うことができる。
【００７４】
このように、実施形態３によれば、ｂ２の計算が不要となるので、実施形態１,２に比べてＡＣＳ回路１２による生き残りパス選択処理を短縮することができる。特に、ブランチメトリックの計算はビタビ復号器の中で最も繰り返し計算されるところであるので、実施形態３によるビタビ復号器は、大幅な演算量の削減を可能とし、受信系列の復号処理を短縮することができる。
【００７５】
〔実施形態４〕
次に、本発明の実施形態４によるビタビ復号器について説明する。但し、実施形態４は、実施形態１,３と共通点を有するので、実施形態１,３との相違点についてのみ説明する。
【００７６】
図７に示した各テーブル３６ａ〜３６ｄには、必ず同じブランチメトリックを持つブランチが保持されている。このことに鑑み、これらをグループ化したときに、グループ化されたブランチがシーケンシャルに並ぶものについては、グループ化を行なっても、ＡＣＳ回路１２によるシーケンシャルアクセスでブランチメトリックを読み出すことができる。これによって、メモリの共有化を図ることができる。
【００７７】
図９は、上記手法によって得られた実施形態４におけるブランチメトリックテーブル４６の例を示す説明図である。図９に示すように、ブランチメトリックテーブル４６をなす各テーブル４６ａ〜４６ｄは、図７に示したテーブル３６ａ〜３６ｄに保持されていたブランチメトリックを上記手法によってグループ化したものである。
【００７８】
例えば、テーブル４６ａの最初のアドレスには、同じブランチメトリック(＝−１)をもつブランチ０,１,２,３が状態Ｓ０及び状態Ｓ１に対応づけて保持されており、最初のアドレスの次のアドレスには、同じブランチメトリック(＝０)を持つブランチ４,５,６,７が状態Ｓ２及び状態Ｓ３に対応づけて保持されている。
【００７９】
実施形態４におけるビタビ復号器は、実施形態１と同様の構成を有する(図１参照)。但し、ブランチメトリックメモリ１３が、ブランチメトリックテーブル１６(図２参照)の代わりに、図９に示したブランチメトリックテーブル４６を保持している。
【００８０】
図１０は、実施形態４におけるビタビ復号器による処理を示すフローチャートである。図１０に示すように、実施形態３のビタビ復号器は、Ｓ４０２,Ｓ４１２〜Ｓ４１４の処理を除き、実施形態３とほぼ同様の処理を行う(図８参照)。このため、Ｓ４０２,Ｓ４１２〜４１４の処理について説明し、その他の処理の説明は省略する。
【００８１】
Ｓ４０２では、状態を示すｋの値がｋ＝０に設定されるとともに、ワーク領域１１に保持されているフラグｉがｉ＝０に設定される。その後、Ｓ４０３〜４０９の処理を経てＳ４１２に処理が進むと、Ｓ４１２では、フラグｉがｉ＝０か否かが判定される。このとき、フラグｉが０である場合(Ｓ４１２；Ｙ)には、処理がＳ４１３に進み、フラグｉが０でない場合(Ｓ４１２；Ｎ)には、処理がＳ４１４へ進む。
【００８２】
Ｓ４１３では、ＡＣＳ回路１２が、ｉ＝(ｉ＋１)ｍｏｄ２の処理を行い、フラグｉがｉ＝１に設定される。その後、処理がＳ４０４へ戻る。このように、Ｓ４１３からＳ４０４へ処理が進むとき、ＡＣＳ回路１２は、前回のＳ４０３にて読み出したブランチメトリックの値ｂ１を用いてＳ４０４の処理を行う。これによって、状態遷移に伴ってブランチメトリックテーブル３６からブランチメトリックを読み出す処理(Ｓ４０３の処理)が省略される。
【００８３】
これに対し、Ｓ４１３に処理が進んだ場合には、ＡＣＳ回路１２にてｉ＝０でないと判定された場合には、ＡＣＳ回路１２が、ｉ＝(ｉ＋１)ｍｏｄ２の処理を行い、フラグｉがｉ＝０に設定される。その後、処理がＳ４０３へ戻り、ブランチメトリックに対するシーケンシャルアクセスが行われる。
【００８４】
このように、Ｓ４１２において、フラグｉがｉ＝０のときには、ブランチメトリックテーブル４６に対するアクセスが省略され、ｉ＝１のときには、ブランチメトリックテーブル４６に対してシーケンシャルアクセスがなされる。
【００８５】
図１０に示す処理では、状態Ｓ１又は状態Ｓ３のとき、処理がＳ４１２からＳ４１３を経てＳ４０４へ進み、状態Ｓ２のとき、処理がＳ４１２からＳ４１４を経てＳ４０３へ進むようになっている。これによって、或る時刻ｔにおける状態Ｓ０〜Ｓ３に対する生き残りパス選択処理において、ブランチメトリックテーブル４６に対するアクセスは２回であり、２回目のアクセスは、１回目にアクセスしたアドレスの次のアドレスに対して行うことで足りる。
【００８６】
実施形態４におけるビタビ復号器によれば、実施形態１,３の効果に加え、さらに、ブランチメトリックメモリ１３に対するアクセス回数を減らすことができるので、実施形態１,３よりもＡＣＳ回路１２の処理速度を高め、復号処理の速度の向上を図ることが可能となる。
【００８７】
〔実施形態５〕
次に、本発明の実施形態５によるビタビ復号器について説明する。但し、実施形態５は、実施形態１,４と共通点を有するので、実施形態１,４との相違点についてのみ説明する。
【００８８】
ビタビ復号器が適用されるトレリスが、例えば、図１１に示すトレリスである場合、各実施形態１,２,３のブランチメトリックテーブル１６,２６,３６は、それぞれ、図１２(ａ),(ｂ),(ｃ)に示すようになる。
【００８９】
図１２(ａ),(ｂ),(ｃ)において、例えば、図１２(ｃ)に示すテーブル３６ａにおける各ブランチ４,５,６,７は、ブランチメトリック値が同じ０であるので、一つにまとめてグループ化することが可能である。これに対し、テーブル３６ａにおけるブランチ０,１,２,３は、ブランチ０,１の値とブランチ２,３の値が０対称(正負が反対)なのでまとめることができない。
【００９０】
これに対し、テーブル３６ａのブランチ０,１,２,３をブランチ０,１の値で代表させて―つにまとめ、図１２(ｃ)に示したブランチメトリックテーブル３６を、図１３に示すブランチメトリックテーブル５６のように構成すれば、ＡＣＳ回路１２で以下のように計算を行うことで、シーケンシャルに各ブランチのブランチメトリックを得ることができる。
ブランチ0のメトリック ＝ブランチメトリックメモリのブランチ0,1,2,3の値
ブランチ1のメトリック ＝−１×ブランチメトリックメモリのブランチ0,1,2,3の値
ブランチ2のメトリック ＝ブランチメトリックメモリのブランチ0,1,2,3の値
ブランチ3のメトリック ＝−１×ブランチメトリックメモリのブランチ0,1,2,3の値
ブランチ4のメトリック ＝ブランチメトリックメモリのブランチ4,5,6,7の値
ブランチ5のメトリック ＝−１×ブランチメトリックメモリのブランチ4,5,6,7の値
ブランチ6のメトリック ＝ブランチメトリックメモリのブランチ4,5,6,7の値
ブランチ7のメトリック ＝−１×ブランチメトリックメモリのブランチ4,5,6,7の値
図１３は、上記手法によって得られた実施形態５におけるブランチメトリックテーブル５６の例を示す説明図である。図１３に示すように、ブランチメトリックテーブル５６をなす各テーブル５６ａ〜５６ｄは、図１２(ｃ)に示したテーブル３６ａ〜３６ｄに保持されていたブランチメトリックを上記手法によってグループ化したものである。
【００９１】
例えば、テーブル５６ａの最初のアドレスには、ブランチ０,１のブランチメトリック(＝−１)で代表してグループ化された状態Ｓ０及び状態Ｓ１におけるブランチ０,１,２,３のブランチメトリックが格納されており、最初のアドレスの次のアドレスには、同一のブランチメトリック(＝０)を持つブランチ４,５,６,７でまとめられた状態Ｓ２及び状態Ｓ３のブランチメトリックが格納されている。
【００９２】
実施形態５におけるビタビ復号器は、実施形態１と同様の構成を有する(図１参照)。但し、ブランチメトリックメモリ１３が、ブランチメトリックテーブル１６(図２参照)の代わりに、図１３に示したブランチメトリックテーブル５６を保持している。
【００９３】
図１４は、実施形態５におけるビタビ復号器による処理を示すフローチャートである。図１４に示すように、実施形態５のビタビ復号器は、Ｓ５１５の処理を除き、実施形態４とほぼ同様の処理を行う(図１０参照)。このため、Ｓ５１５のの処理についてのみ説明し、他の処理の説明は省略する。
【００９４】
Ｓ５１５の処理は、状態を示すｋの値がｋ＝１又はｋ＝３である場合に、Ｓ５１３の処理後に行われる。Ｓ５１５では、ＡＣＳ回路１２は、前回のＳ５０３の処理にて得られた代数ｂ１の値をｂ１＝−ｂ１に設定し、処理をＳ５０４へ戻す。
【００９５】
実施形態５におけるビタビ復号器によれば、実施形態４とほぼ同様の効果を得ることができる。
【００９６】
〔実施形態６〕
次に、本発明の実施形態６によるビタビ復号器について説明する。但し、実施形態５は、実施形態１,５と共通点を有するので、実施形態１,５との相違点についてのみ説明する。
【００９７】
ビタビ復号器が復号する符号(受信系列)によっては、トレリスが、図１５に示すようなものとなる場合がある。図１５に示すトレリスについて、上述した実施形態１〜３における手法を用いてブランチメトリックテーブルを作成すると、図１６に示すようになる。
【００９８】
ここで、図１６に示すブランチメトリックテーブルでは、隣り合う状態同士のブランチメトリックの値(例えば、受信系列“００”に対応するテーブルにおける状態Ｓ０のブランチメトリック＝１と状態Ｓ１のブランチメトリック＝０)が、図７に示したブランチメトリックテーブル３６のように、同じ値を持たない(例えば、図７のテーブル３６ａの状態Ｓ０のブランチメトリックと状態Ｓ１のブランチメトリックとは共に−１である)。
【００９９】
また、図１６に示すブランチメトリックテーブルでは、図９に示すブランチメトリックテーブル４６のように、隣合う状態同士のブランチメトリックが正負反対の値(０対称の(絶対値が等しい)値)を有していない。
【０１００】
このような場合において、図１６に示すように、ブランチ０,１(状態Ｓ０)のブランチメトリック値とブランチ４,５(状態Ｓ２)のブランチメトリック値とが同じである場合には、これらを１つのグループとしてまとめ、同様に、ブランチメトリック値が同じであるブランチ２,３(状態Ｓ１)とブランチ６,７(状態Ｓ３)とを１つのグループとしてまとめて保持すれば、ブランチメトリックテーブルを小さくすることができる。
【０１０１】
図１７は、上記手法によって得られる実施形態６におけるブランチメトリックテーブル６６の例を示す説明図である。図１７において、ブランチメトリックテーブル６６をなす各テーブル６６ａ〜６６ｄの最初のアドレスには、状態Ｓ０及び状態Ｓ２に対応するブランチ０,１,４,５からなるグループのブランチメトリックが保持されており、最初のアドレスの次のアドレスには、状態Ｓ１及び状態Ｓ３に対応するブランチ２,３,６,７からなるグループのブランチメトリックが保持されている。
【０１０２】
実施形態６によるビタビ復号器は、実施形態１と同様の構成を有する(図１参照)。但し、ブランチメトリックメモリ１３が、ブランチメトリックテーブル１６(図２参照)の代わりに、図５に示したブランチメトリックテーブル６６を保持している。
【０１０３】
実施形態６によるビタビ復号器は、上記した構成を有するため、ＡＣＳ回路１２が、各テーブル６６ａ〜６６ｄに保持されたブランチメトリックを、トレリスのブランチの番号順に読み出すことができない。
【０１０４】
但し、実施形態４にて説明した１回のブランチメトリックテーブルに対するアクセスで同時に複数のブランチメトリックを取得可能な性質を利用し、ＡＣＳ回路１２が、一回のアクセスでブランチメトリックを取得可能な複数のブランチに対する処理を同時を行う構成とすることで、ワーク領域１１の増加は免れないが、各テーブル６６ａ〜６６ｄに対するシーケンシャルアクセスを可能にすることができる。即ち、ＡＣＳ回路１２が、
(１)ブランチ０,１,４,５のブランチメトリック読み出し
(２)パスメトリック計算
(３)状態Ｓ０のブランチ選択
(４)状態Ｓ２のブランチ選択
というように計算を行なえば、ＡＣＳ回路１２は、シーケンシャルにブランチメトリックテーブル６６をアクセスすることが可能である。ただし、実施形態６によるビタビ復号器は、パスメモリに対するアクセスをシーケンシャルに行なうことができない。
【０１０５】
図１８及び図１９は、実施形態６におけるビタビ復号器による処理を示すフローチャートである。図１８において、最初に、受信系列がワーク領域１１に入力されると、時刻ｔがｔ＝Ｔ０に設定され(Ｓ６０１)、状態を示すｋがｋ＝０に設定される(Ｓ６０２)。
【０１０６】
次に、ＡＣＳ回路１２が、状態Ｓtk(状態Ｓ０,Ｓ２)に対して、受信系列に対応するテーブル６６ａ〜６６ｄの何れか(図１７参照)から、ブランチｂt2k (ブランチ０,４)のブランチメトリックを読み出し、ワーク領域１１に保持されている代数ｂ１に代入する(Ｓ６０３)。
【０１０７】
次に、ＡＣＳ回路１２が、ブランチｂt2k(ブランチ０,４)が接続されている過去の状態Ｓt-1b(ｂ＝ｂt2k)のパスメトリックを、ブランチｂt2kのブランチ出力値を用いて、パスメトリックメモリ１４から読み出し、ワーク領域１１に保持されている各代数ｐ０,ｐ１,ｐ４,ｐ５に夫々代入する。
【０１０８】
次に、ＡＣＳ回路１２は、Ｓ６０５の処理を飛ばしてＳ６０６に進み、ワーク領域１１に保持されている各代数ｂ１,ｐ０,ｐ１,ｐ４,ｐ５を用いて以下の計算を行い、各計算結果をワーク領域１１に格納する(Ｓ６０６)。
Ｐ０＝ｐ０＋ｂ１；Ｐ１＝ｐ１−ｂ１
Ｐ４＝ｐ４＋ｂ１；Ｐ５＝ｐ５−ｂ１
次に、ＡＣＳ回路１２は、図１９に示すように、Ｐ０とＰ１との小さい方，及びＰ４とＰ５の小さい方を各状態Ｓtk(状態Ｓ０及び状態Ｓ２)のパスメトリックとしてパスメトリックメモリ１４に記憶する(Ｓ６０７)。
【０１０９】
次に、ＡＣＳ回路１２は、Ｐ０とＰ１との小さい方，及びＰ４とＰ５の小さい方のブランチをパスメモリ１５に記憶する(Ｓ６０８)。
次に、状態を示すｋが所定の状態数(状態数＝８)以上か否かが判定され(Ｓ６０９)、ｋが状態数未満である場合(Ｓ６０９；Ｎ)には、ｋの値が(ｋ＝ｋ＋８)に設定され(Ｓ６１０)、処理がＳ６０３へ戻る。
【０１１０】
処理がＳ６０３へ戻ると、ＡＣＳ回路１２が、図示せぬリードポインタの位置(リードアドレス)を１インクリメントすることによって、前回のＳ６０３にてアクセスされたアドレスの次のアドレスから、状態Ｓtk+1(状態Ｓ１,Ｓ４)に対するブランチｂt2k+1(ブランチ３,７)のブランチメトリックを読み出し、ワーク領域１１に保持されている代数ｂ２に代入する。
【０１１１】
次に、ＡＣＳ回路１２は、Ｓ６０４の処理を飛ばしてＳ６０５に進み、ブランチｂt2k+1(ブランチ３,７)が接続されている過去の状態Ｓt-1b(ｂ＝ｂt2k+1)のパスメトリックを、ブランチｂt2k+1のブランチ出力値を用いて、パスメトリックメモリ１４から読み出し、ワーク領域１１に保持されている各代数ｐ２,ｐ３,ｐ６,ｐ７に夫々代入する。
【０１１２】
次に、ＡＣＳ回路１２は、ワーク領域１１に保持されている各代数ｂ２,ｐ２,ｐ３,ｐ６,ｐ７を用いて以下の計算を行い、各計算結果をワーク領域１１に格納する(Ｓ６０６)。
Ｐ２＝ｐ２＋ｂ２；Ｐ３＝ｐ３−ｂ２
Ｐ６＝ｐ６＋ｂ２；Ｐ７＝ｐ５−ｂ２
次に、ＡＣＳ回路１２は、図１９に示すように、Ｐ２とＰ３との小さい方，及びＰ６とＰ７の小さい方を各状態Ｓtk(状態Ｓ１及び状態Ｓ３)のパスメトリックとしてパスメトリックメモリ１４に記憶する(Ｓ６０７)。
【０１１３】
次に、ＡＣＳ回路１２は、Ｐ０とＰ１との小さい方，及びＰ４とＰ５の小さい方のブランチをパスメモリ１５に記憶する(Ｓ６０８)。
次に、状態を示すｋが所定の状態数(状態数＝８)以上か否かが判定され(Ｓ６０９)、ｋが状態数以上であると判定されると(Ｓ６０９；Ｙ)、Ｓ６１１に処理が進む。Ｓ６１１以降の処理は、実施形態１における処理(Ｓ１１０,Ｓ１１１)とほぼ同様であり、その後、最終的にバックトレースによって受信系列を復号した符号系列がパスメモリ１５から出力されることも実施形態１と同じである。
【０１１４】
実施形態６におけるビタビ復号器によれば、ブランチメトリックをブランチの順で読み出すことはできないが、複数の状態に対するブランチメトリックを一度に読み出して同時に処理する。これによって、ブランチメトリックテーブル６６に対するアクセス回数を減らすことができ、且つブランチメトリックテーブル６６に対してシーケンシャルにアクセスすることができる。従って、先行例に比べてＡＣＳ回路１２の処理速度(復号速度)を向上させることができる。
【０１１５】
〔実施形態７〕
次に、本発明の実施形態７によるビタビ復号器について説明する。但し、実施形態７は、実施形態１,６と共通点を有するので、実施形態１,６との相違点についてのみ説明する。
【０１１６】
実施形態１〜６では、受信系列のパターンによってブランチメトリックテーブルのアクセスアドレスが生成され、このアクセスアドレスを先頭としてシーケンシャルにアクセスすることで各ブランチのブランチメトリックを読み出すことができる。
【０１１７】
ところで、受信系列をなす２ビット符号を反転した受信系列のブランチメトリックテーブルは、２ビット符号が反転される前の受信系列のブランチメトリックの値から簡単な演算で知ることができる。このため、どちらか一方の受信系列に対応するブランチメトリックを持てば良い。
【０１１８】
例えば、図２１に示したトレリスの場合、ブランチメトリックがハミング距離である場合には、受信系列“００”のブランチ０のブランチメトリックは２−０＝０であるのに対し、受信系列“１１”のブランチ０のブランチメトリックは０である(図２参照)。
【０１１９】
また、ブランチメトリックが実施形態３にて説明した〔変換式〕によって変換されたものである場合には、受信系列“００”のブランチ０のブランチメトリックが−１であるのに対し、受信系列“１１”のブランチ０のブランチメトリックは１となる。この性質を利用して、ブランチメトリックテーブルのメモリ量を図２０に示すように削減することが可能となる。
【０１２０】
図２０は、上記した手法によって得られる実施形態７におけるブランチメトリックテーブル７６の例を示す説明図である。図２０に示すブランチメトリックテーブル７６は、図９に示したブランチメトリックテーブル４６を変形したものであり、受信系列“００”及び“１１”に対応するテーブル７６ａと、受信系列“０１”及び“１０”に対応するテーブル７６ｂとからなる。
【０１２１】
各テーブル７６ａ,７６ｂは、最初のアドレスに状態Ｓ０及び状態Ｓ１に対応するブランチ０〜３に応じたブランチメトリックが保持され、最初のアドレスの次のアドレスに状態Ｓ２及び状態Ｓ３に対応するブランチ４〜７に応じたブランチメトリックが格納されている。
【０１２２】
実施形態７におけるビタビ復号器は、実施形態１と同様の構成を有する(図１参照)。但し、ブランチメトリックメモリ１３が、ブランチメトリックテーブル１６(図２参照)の代わりに、図１９に示したブランチメトリックテーブル７６を保持している。
【０１２３】
実施形態７におけるビタビ復号器は、実施形態４にて説明した処理ルーチン(図１０参照)と同じルーチンに従って受信系列を復号するので、処理(動作)の説明は省略する。但し、実施形態７では、実施形態４におけるブランチメトリックテーブル４６(図９参照)の代わりに、図１９に示すブランチメトリックテーブル７６が用いられる。
【０１２４】
実施形態７におけるビタビ復号器によれば、実施形態１〜６に比べて、ブランチメトリックメモリ１３の記憶容量をさらに削減することができる。このように、実施形態１〜７によるブランチメトリックメモリ１３の記憶容量の削減によって、ビタビ復号器のコストダウンを図ることが可能となる。
【０１２５】
〔実施形態８〕
次に、本発明の実施形態８によるビタビ復号器について説明する。但し、実施形態８は、実施形態１,６と共通点を有するので、実施形態１,６との相違点についてのみ説明する。
【０１２６】
ビタビ復号器が復号処理に用いるトレリスが図１５に示したトレリスである場合、ブランチメトリックテーブルは、図１７に示したものとなる。この場合には、ビタビ復号器は、図１８及び図１９に示した処理を行う必要がある。この処理では、ＡＣＳ回路１２は、ブランチメトリックをブランチの順番でシーケンシャルに読み出すことができない。このことに鑑み、実施形態８におけるビタビ復号器は、以下の処理を行う。
【０１２７】
実施形態８におけるビタビ復号器は、図１に示す構成を持つ。受信系列の復号処理に使用されるトレリスは、受信系列の種類によって異なり、受信側と送信側とのネゴシエーションによって決定される。ビタビ復号器のＡＣＳ回路１２は、受信系列の復号処理の前に、受信側と送信側とのネゴシエーションによって決定された、復号処理に使用されるトレリスを知ることができる。
【０１２８】
このとき、ＡＣＳ回路１２は、ネゴシエーションによって、受信する受信系列が図１５に示すトレリスを用いて復号するものであることを知った場合には、図２１に示すように、各状態の順番を変更することで、トレリスの構造を変換する。
【０１２９】
その後、ＡＣＳ回路１２は、変換後のトレリスに応じたブランチメトリックテーブルを作成する。即ち、ＡＣＳ回路１２は、図２１に示した変換後のトレリスに従って、図９に示したものと同じ内容のブランチメトリックテーブルを作成する。その後、ＡＣＳ回路１２は、作成したブランチメトリックテーブルを、ワーク領域１１又はブランチメトリックメモリ１３に保持させる。
【０１３０】
その後、ビタビ復号器は、入力される受信系列に対して、図１０と同じ処理を行うことで、ブランチメトリックテーブルをブランチの順番でシーケンシャルに読み出すことが可能となる。
【０１３１】
〔その他〕
本発明によるビタビ復号器は、パンクチャーレート毎にブランチメトリックテーブルを持てば、パンクチャーが施された誤り訂正符号(例えばＲＣＰＣ符号)に対して適用することができる。この場合、上述した実施形態１〜８に対して何ら変更を加える必要はない。
【０１３２】
なお、本発明によるビタビ復号器は、例えば、携帯電話やＣＤ−ＲＯＭリーダ等の送受信間で受信した符号の誤り訂正を行う情報処理分野や通信分野において広く実施可能である。
【０１３３】
【発明の効果】
本発明によるビタビ復号器によれば、ブランチメトリックテーブルをシーケンシャルにアクセス可能な構造としたので、ブランチメトリックテーブルからブランチメトリックを読み出す時間を短縮でき、ブランチメトリックの計算に要する時間を短縮することができる。
【０１３４】
また、本発明によるビタビ復号器によれば、ブランチメトリックテーブルがブランチメトリックをグループ化してまとめて保持するので、ブランチメトリックテーブルに対するアクセス数を減らすことができ、パスメトリックの演算量を減らすことができ、且つブランチメトリックメモリの記憶容量を削減することができる。
【０１３５】
また、本発明によるビタビ復号器によれば、或る状態に入り込む各ブランチのブランチメトリックの値を０対称としたことで、繰り返し計算の行われるパスメトリックの演算量を削減することができ、且つブランチメトリックメモリの記憶容量を削減することが可能である。
【０１３６】
以上のように、本発明によるビタビ復号器によれば、生き残りパス選択処理に係る演算量を減少させることができるので、受信系列の復号処理による時間を短縮できるとともに、ブランチメトリックメモリの記憶容量を減少させることができる。
【図面の簡単な説明】
【図１】本発明の実施形態によるビタビ復号器の構成図
【図２】図１に示したブランチメトリックメモリに保持されたブランチメトリックテーブルの例を示す説明図
【図３】実施形態１のビタビ復号器による処理を示すフローチャート
【図４】図３に示したフローチャートにおける文字の定義を示す図
【図５】実施形態２のブランチメトリックテーブルの例を示す説明図
【図６】実施形態２のビタビ復号器による処理を示すフローチャート
【図７】実施形態３のブランチメトリックテーブルの例を示す説明図
【図８】実施形態３のビタビ復号器による処理を示すフローチャート
【図９】実施形態４のブランチメトリックテーブルの例を示す説明図
【図１０】実施形態４のビタビ復号器による処理を示すフローチャート
【図１１】実施形態５にて適用されるトレリスを示す図
【図１２】図１１に示したトレリスに対応するブランチメトリックテーブルの説明図
【図１３】実施形態５のブランチメトリックテーブルの例を示す説明図
【図１４】実施形態５のビタビ復号器による処理を示すフローチャート
【図１５】実施形態６にて適用されるトレリスを示す図
【図１６】図１５に示したトレリスに対応するブランチメトリックテーブルの説明図
【図１７】実施形態６のブランチメトリックテーブルの例を示す説明図
【図１８】実施形態６のビタビ復号器による処理を示すフローチャート
【図１９】実施形態６のビタビ復号器による処理を示すフローチャート
【図２０】実施形態７のブランチメトリックテーブルの例を示す説明図
【図２１】実施形態８の説明図
【図２２】ビタビ復号器に適用されるトレリスの例を示す図
【符号の説明】
１１    ワーク領域
１２    ＡＣＳ回路(制御部)
１３    ブランチメトリックメモリ(記憶部)
１４    パスメトリックメモリ
１５    パスメモリ
１６    ブランチメトリックテーブル
１６ａ〜１６ｄ    テーブル
２６    ブランチメトリックテーブル
２６ａ〜２６ｄ    テーブル
３６    ブランチメトリックテーブル
３６ａ〜３６ｄ    テーブル
４６    ブランチメトリックテーブル
４６ａ〜４６ｄ    テーブル
５６    ブランチメトリックテーブル
５６ａ〜５６ｄ    テーブル
６６    ブランチメトリックテーブル
６６ａ〜６６ｄ    テーブル
７６    ブランチメトリックテーブル
７６ａ，７６ｂ    テーブル
【図１】
0004213286.tif 000002
【図２】
0004213286.tif 000003
【図３】
0004213286.tif 000004
【図４】
0004213286.tif 000005
【図５】
0004213286.tif 000006
【図６】
0004213286.tif 000007
【図７】
0004213286.tif 000008
【図８】
0004213286.tif 000009
【図９】
0004213286.tif 000010
【図１０】
0004213286.tif 000011
【図１１】
0004213286.tif 000012
【図１２】
0004213286.tif 000013
【図１３】
0004213286.tif 000014
【図１４】
0004213286.tif 000015
【図１５】
0004213286.tif 000016
【図１６】
0004213286.tif 000017
【図１７】
0004213286.tif 000018
【図１８】
0004213286.tif 000019
【図１９】
0004213286.tif 000020
【図２０】
0004213286.tif 000021
【図２１】
0004213286.tif 000022
【図２２】
0004213286.tif 000023