(57)【特許請求の範囲】
【請求項１】
ビタビ復号に係る任意の二つのブランチ間の差分ブランチメトリック（以下、「ＤＢＭ」と称する。）を入力し、当該入力したＤＢＭを任意の二つのステート間の差分パスメトリック（以下、「ＤＰＭ」と称する。）に加算し、当該加算後のＤＰＭどうしを比較して最尤パスを選択するＡＣＳ回路であって、
前記ＤＰＭのうち、基準となるステートに係るパスメトリックと他のステートに係るパスメトリックとの間のＤＰＭである基本ＤＰＭを保持し、当該基本ＤＰＭに基づいて最尤パスを選択する
ことを特徴とするＡＣＳ回路。
【請求項２】
請求項１に記載のＡＣＳ回路において、
前記基本ＤＰＭを保持する基本ＤＰＭ保持部と、
前記基本ＤＰＭを算出する基本ＤＰＭ演算部と、
前記基本ＤＰＭ演算部による基本ＤＰＭの算出に必要なＤＰＭであって基本ＤＰＭ以外のＤＰＭである参照ＤＰＭを算出する参照ＤＰＭ演算部と、
前記ＤＢＭのうち、前記基本ＤＰＭ演算部による基本ＤＰＭの算出に必要なＤＢＭである基本ＤＢＭを算出する基本ＤＢＭ演算部と、
前記基本ＤＰＭ保持部に保持された基本ＤＰＭ、前記参照ＤＰＭ演算部によって算出された参照ＤＰＭ及び前記基本ＤＢＭ演算部によって算出された基本ＤＢＭに基づいて、ビタビ復号に係る最尤パスを選択するパス選択部とを備え、
前記基本ＤＰＭ演算部は、前記基本ＤＰＭ保持部に保持された基本ＤＰＭ、前記参照ＤＰＭ演算部によって算出された参照ＤＰＭ、前記基本ＤＢＭ演算部によって算出された基本ＤＢＭ及び前記パス選択部による最尤パスの選択結果に基づいて、新たな基本ＤＰＭを算出する
ことを特徴とするＡＣＳ回路。
【請求項３】
請求項２に記載のＡＣＳ回路において、
前記基本ＤＢＭ演算部による基本ＤＢＭの算出及び前記参照ＤＰＭ演算部による参照ＤＰＭの算出は、並列処理される
ことを特徴とするＡＣＳ回路。
【請求項４】
請求項２に記載のＡＣＳ回路において、
前記参照ＤＰＭ演算部は、前記基本ＤＰＭ保持部に保持された基本ＤＰＭのうちのいずれかから他を減算して参照ＤＰＭを算出する
ことを特徴とするＡＣＳ回路。
【請求項５】
請求項２に記載のＡＣＳ回路において、
前記基本ＤＰＭ演算部は、前記パス選択部による最尤パスの選択結果に基づいて、前記基本ＤＰＭ保持部に保持された基本ＤＰＭ、前記参照ＤＰＭ演算部によって算出された参照ＤＰＭ及び前記基本ＤＢＭ演算部によって算出された基本ＤＢＭの中から前記新たな基本ＤＰＭの算出の元となる基本ＤＰＭ及び基本ＤＢＭを選択し、当該選択した基本ＤＰＭ及び基本ＤＢＭを加算して前記新たな基本ＤＰＭを算出する
ことを特徴とするＡＣＳ回路。
【請求項６】
請求項２に記載のＡＣＳ回路において、
前記基本ＤＰＭ演算部は、前記基本ＤＰＭ保持部に保持された基本ＤＰＭ及び前記参照ＤＰＭ演算部によって算出された参照ＤＰＭと、前記基本ＤＢＭ演算部によって算出された基本ＤＢＭとをそれぞれ加算して、前記新たな基本ＤＰＭの候補を算出し、前記パス選択部による最尤パスの選択結果に基づいて、当該候補の中から前記新たな基本ＤＰＭを選択する
ことを特徴とするＡＣＳ回路。
【請求項７】
請求項２に記載のＡＣＳ回路において、
前記パス選択部は、ビタビ復号における各ステートへの遷移に係るブランチに互いに異なるパス選択番号を割り当て、最尤パスの選択結果として、当該パス選択番号を示すパス選択信号を出力する
ことを特徴とするＡＣＳ回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビタビ復号に係るパスメトリックの加算及び比較、及びパス選択を行うＡＣＳ回路に関し、特に、メトリック差分に基づいてパス選択を行うＡＣＳ回路に関する。
【背景技術】
【０００２】
ビタビ復号は、ある特定の畳み込み演算によって符号化されたデータ系列を受信し、当該畳み込み演算の規則に基づいて、もっとも適当と思われるデータ系列を予測し、復号する技術である。畳み込み演算の規則は状態遷移図として記述することができる。さらに、この状態遷移図に時間概念を加味すると、トレリス線図を記述することができる。
【０００３】
図９は、ギガビットイーサネット（イーサネット：登録商標）で一般的に用いられる畳み込み符号化器の構成を示す。当該畳み込み符号化器は、入力した値を１クロック遅延させて出力する遅延素子１０１、１０２及び１０３と、加算器１０４及び１０５とを備えた、２ビット入力８ステートの畳み込み符号化器である。加算器１０４は、遅延素子１０１の出力と入力上位ビットとを加算する。遅延素子１０２は、加算器１０４の加算結果を入力する。加算器１０５は、遅延素子１０２の出力と入力下位ビットとを加算する。遅延素子１０３は、加算器１０５の加算結果を入力する。そして、遅延素子１０１は、遅延素子１０３の出力を入力する。これにより、遅延素子１０１〜１０３は、３ビットのステート、すなわち、８ステートを表す。
【０００４】
図１０は、上記畳み込み符号化器に係るトレリス線図である。当該トレリス線図は、ステートＳ０，Ｓ１，Ｓ２，Ｓ３，Ｓ４，Ｓ５，Ｓ６及びＳ７に関して、時刻（ｋ−１）から時刻ｋへの遷移と、時刻ｋから時刻（ｋ＋１）の遷移とを示している。各ステート間を結ぶ線はブランチと呼ばれる。各ブランチは、あるステートとそのステートの遷移先のステートとを接続している。
【０００５】
ビタビ復号では、各ステートからの遷移の尤度、すなわち、確からしさを評価するために、各ブランチについて評価関数を用いて「ブランチメトリック」を計算する。通常、ブランチメトリックの計算は、理想値と実際に受信した値との二乗誤差で求められる。一方、復号を開始して以来、各ステートに関して、そのステートに至るブランチのうちのもっとも確からしいブランチのブランチメトリックを累積加算した値が記憶されている。これを「パスメトリック」という。ビタビ復号では、時刻（ｋ−１）におけるパスメトリックと時刻ｋでのブランチメトリックとを加算した結果が最小となるブランチをもっとも確からしいブランチであると判断する。すなわち、ＡＣＳ回路とは、もっとも確からしいブランチを決定するために、時刻（ｋ−１）におけるパスメトリックと時刻ｋでのブランチメトリックとの加算を行い、その結果を比較し、もっとも確からしいブランチを選択するＡｄｄ−Ｃｏｍｐａｒｅ−Ｓｅｌｅｃｔ回路のことである。
【０００６】
各時刻で得られたもっとも確からしいブランチを連結したパスを「生き残りパス」と呼ぶ。トレリス線図中、各ステートはそれぞれの生き残りパスを持っているが、復号処理が進むにつれてすべてのステートが持つ生き残りパスは一つに収束する。このようにして得られた一つの生き残りパスがビタビ復号による最終的な復号結果となる。
【０００７】
従来のＡＣＳ回路は、ブランチメトリックの算出に二乗計算を用いる。このため、回路が複雑化し、また、パスメトリックがブランチメトリックの累積であるためオーバーフローが発生するという問題があった。このうち、パスメトリックのオーバーフローを解消する対策として、パスメトリックの値を随時監視し、オーバーフローが発生しそうになった時点で各ステートのパスメトリック値から同じ値を減算するという手法が知られている。しかし、この手法では、通常のＡＣＳ回路の処理の後に、さらにオーバーフローの判定及び減算処理が必要となるため、処理速度が低下するという問題がある。そこで、ブランチメトリックどうしの差である差分ブランチメトリック（以下、「ＤＢＭ」と称する。）を用いて、ブランチメトリックの計算に係る二乗の項を消去して演算を容易化するとともに、パスメトリックどうしの差である差分パスメトリック（以下、「ＤＰＭ」と称する。）を用いて、パスメトリックの計算に係るオーバーフローを回避するという手法が考案されている（例えば、特許文献１参照）。
【０００８】
しかし、上記のようなメトリック差分に基づいてパス選択を行うＡＣＳ回路では、比較的多くのＤＰＭを保持しなければならないため、比較的大規模な保持回路が必要となる。例えば、８ステートのトレリス線図の場合、パスメトリックは８個であるのに対してＤＰＭは２８個（＝8Ｃ2）である。そこで、保持回路の大規模化を抑制するために、保持するＤＰＭの個数を制限するというＡＣＳ回路が考案されている（例えば、非特許文献１参照）。しかし、当該ＡＣＳ回路は、ＤＰＭの算出にＤＢＭの他に通常のブランチメトリックを用いるため、二乗計算が必要になるという問題がある。
【特許文献１】特許第３２５８１７４号明細書
【非特許文献１】Akira Yamamoto, et al, “A 500MHz 50mW Viterbi Detector for DVD Systems using Simplified ACS and New Path Memory Architecture”, 2002 Symposium On VLSI Circuits Digest of Technical Papers, pp.256-259
【発明の開示】
【発明が解決しようとする課題】
【０００９】
上述したように、メトリック差分に基づいてパス選択を行う従来のＡＣＳ回路については回路規模の増大が問題となる。ここで、２入力８ステートの畳み込み符号化器によって生成されたデータ系列を復号するＡＣＳ回路について、ＤＰＭを用いる場合と用いない場合とで回路規模を比較してみる。前者は、８個のパスメトリックを保持するための保持回路、及び各パスメトリックと各ブランチメトリックとの加算を行う３２個の加算器を必要とする。加算器の個数は、８個の各ステートに１時刻前の４個のステートからの４本のブランチが接続されることに基づいている。さらに、前者は、これ以外にオーバーフロー対策用の回路を必要とする。これに対し、後者は、２８個のＤＰＭを保持するための保持回路、及び各ＤＰＭと各ＤＢＭとの加算を行う４００個の加算器を必要とする。加算器の個数は、２８個の各ＤＰＭに１６個のＤＢＭが関連することに基づいている。なお、入力するＤＰＭが“０”となる加算器の数（合計４８個）は除いている。
【００１０】
このように、メトリック差分に基づいてパス選択を行う従来のＡＣＳ回路については、処理速度は比較的速いが、回路規模が極端に大きくなってしまうという欠点がある。回路規模の増大は、消費電力増さらには製造コスト増の要因となるため好ましくない。
【００１１】
上記問題に鑑み、本発明は、ビタビ復号に用いられるＡＣＳ回路について、回路規模の増大を極力抑制しつつ、ビタビ復号に係るパスメトリックのオーバーフロー対策を講じることを課題とする。
【課題を解決するための手段】
【００１２】
上記課題を解決するために本発明が講じた手段は、ビタビ復号に係る任意の二つのブランチ間の差分ブランチメトリック（ＤＢＭ）を入力し、当該入力したＤＢＭを任意の二つのステート間の差分パスメトリック（ＤＰＭ）に加算し、当該加算後のＤＰＭどうしを比較して最尤パスを選択するＡＣＳ回路であって、前記ＤＰＭのうち、基準となるステートに係るパスメトリックと他のステートに係るパスメトリックとの間のＤＰＭである基本ＤＰＭを保持し、当該基本ＤＰＭに基づいて最尤パスを選択するものとする。
【００１３】
これによると、すべてのＤＰＭではなくその一部である基本ＤＰＭを保持すればよくなるため、ＤＰＭを保持するための回路の規模は比較的小さくて済む。また、当該ＡＣＳ回路は、メトリック差分に基づいて最尤パスを選択するため、処理速度を低下させることなくパスメトリックのオーバーフローが解消される。
【００１４】
具体的には、上記のＡＣＳ回路は、前記基本ＤＰＭを保持する基本ＤＰＭ保持部と、前記基本ＤＰＭを算出する基本ＤＰＭ演算部と、前記基本ＤＰＭ演算部による基本ＤＰＭの算出に必要なＤＰＭであって基本ＤＰＭ以外のＤＰＭである参照ＤＰＭを算出する参照ＤＰＭ演算部と、前記ＤＢＭのうち、前記基本ＤＰＭ演算部による基本ＤＰＭの算出に必要なＤＢＭである基本ＤＢＭを算出する基本ＤＢＭ演算部と、前記基本ＤＰＭ保持部に保持された基本ＤＰＭ、前記参照ＤＰＭ演算部によって算出された参照ＤＰＭ及び前記基本ＤＢＭ演算部によって算出された基本ＤＢＭに基づいて、ビタビ復号に係る最尤パスを選択するパス選択部とを備えている。そして、前記基本ＤＰＭ演算部は、前記基本ＤＰＭ保持部に保持された基本ＤＰＭ、前記参照ＤＰＭ演算部によって算出された参照ＤＰＭ、前記基本ＤＢＭ演算部によって算出された基本ＤＢＭ及び前記パス選択部による最尤パスの選択結果に基づいて、新たな基本ＤＰＭを算出するものとする。
【００１５】
これによると、ＤＢＭは、基本ＤＰＭの算出に必要なＤＢＭである基本ＤＢＭのみを算出すればよくなる。また、ＤＰＭは、基本ＤＰＭ以外に、基本ＤＰＭの算出に必要なＤＰＭである参照ＤＰＭのみを算出すればよくなる。
【００１６】
好ましくは、前記基本ＤＢＭ演算部による基本ＤＢＭの算出及び前記参照ＤＰＭ演算部による参照ＤＰＭの算出は、並列処理されるものとする。
【００１７】
また、好ましくは、前記参照ＤＰＭ演算部は、前記基本ＤＰＭ保持部に保持された基本ＤＰＭのうちのいずれかから他を減算して参照ＤＰＭを算出するものとする。
【００１８】
そして、具体的には、前記基本ＤＰＭ演算部は、前記パス選択部による最尤パスの選択結果に基づいて、前記基本ＤＰＭ保持部に保持された基本ＤＰＭ、前記参照ＤＰＭ演算部によって算出された参照ＤＰＭ及び前記基本ＤＢＭ演算部によって算出された基本ＤＢＭの中から前記新たな基本ＤＰＭの算出の元となる基本ＤＰＭ及び基本ＤＢＭを選択し、当該選択した基本ＤＰＭ及び基本ＤＢＭを加算して前記新たな基本ＤＰＭを算出するものとする。
【００１９】
また、具体的には、前記基本ＤＰＭ演算部は、前記基本ＤＰＭ保持部に保持された基本ＤＰＭ及び前記参照ＤＰＭ演算部によって算出された参照ＤＰＭと、前記基本ＤＢＭ演算部によって算出された基本ＤＢＭとをそれぞれ加算して、前記新たな基本ＤＰＭの候補を算出し、前記パス選択部による最尤パスの選択結果に基づいて、当該候補の中から前記新たな基本ＤＰＭを選択するものとする。
【００２０】
また、具体的には、前記パス選択部は、ビタビ復号における各ステートへの遷移に係るブランチに互いに異なるパス選択番号を割り当て、最尤パスの選択結果として、当該パス選択番号を示すパス選択信号を出力するものとする。
【発明の効果】
【００２１】
以上のように本発明によると、メトリック差分に基づいてパス選択を行うＡＣＳ回路において、ＤＰＭを保持する回路の規模が小さくなる。また、必要最小限のＤＢＭ（基本ＤＢＭ）及びＤＰＭ（基本ＤＰＭ及び参照ＤＰＭ）のみを算出すればよいため、ＡＣＳ回路において備えるべき加算器などの演算器の個数が比較的少なくて済む。したがって、ＡＣＳ回路全体としての回路規模が小さくなり、消費電力が低減するとともに、製造コストもまた低減する。
【発明を実施するための最良の形態】
【００２２】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。なお、便宜上、図１０のトレリス線図を前提としたビタビ復号を想定して説明する。なお、本発明は、当該トレリス線図を前提としたビタビ復号に限定されるものではない。
【００２３】
まず、以後の説明で使用する表記の説明を行う。ブランチメトリックはｂｉｊと表記し、これはステートＳｉからステートＳｊに遷移するブランチを意味する。例えば、ｂ０２はステートＳ０からステートＳ２に遷移するブランチである。また、ＤＢＭは差分ブランチメトリック全般を意味する。ＤＰＭｉｊはステートＳｊに係るパスメトリックとステートＳｉに係るパスメトリックとの間のＤＰＭを示す。例えば、ステートＳ０に係るパスメトリックをＰＭ０、ステートＳ２に係るパスメトリックをＰＭ２とした場合、
ＤＰＭ０２＝ＰＭ２−ＰＭ０
となる。また、単にＤＰＭと記述した場合は差分パスメトリック全般を意味する。
【００２４】
図１は、本発明の最良の実施形態に係るＡＣＳ回路の構成を示す。本実施形態に係るＡＣＳ回路は、基準となるステートに係るパスメトリックと他のステートに係るパスメトリックとの間の差分パスメトリックである基本ＤＰＭを保持する基本ＤＰＭ保持部１１と、基本ＤＰＭを算出する基本ＤＰＭ演算部１２と、基本ＤＰＭの算出に必要なＤＰＭである参照ＤＰＭを算出する参照ＤＰＭ演算部１３と、基本ＤＰＭの算出に必要なＤＢＭである基本ＤＢＭを算出する基本ＤＢＭ演算部１４と、ビタビ復号に係る最尤パスを選択するパス選択部１５とを備えている。
【００２５】
基本ＤＰＭ保持部１１は、基本ＤＰＭとして、ＤＰＭ０１，ＤＰＭ０２，ＤＰＭ０３，ＤＰＭ０４，ＤＰＭ０５，ＤＰＭ０６及びＤＰＭ０７を保持する。すなわち、基本ＤＰＭ保持部１１は、ステートＳ０を基準のステートとしたときの、当該基準ステートと他のステートとの間のＤＰＭを基本ＤＰＭとして保持する。
【００２６】
基本ＤＰＭ演算部１２は、基本ＤＰＭを新たに算出し、基本ＤＰＭ保持部１１に出力する。図２は、基本ＤＰＭ演算部１２の内部構成を示す。基本ＤＰＭ演算部１２は、基本ＤＢＭ演算部１４によって算出された基本ＤＢＭ、基本ＤＰＭ保持部１１に保持された基本ＤＰＭ及び参照ＤＰＭ演算部によって算出された参照ＤＰＭに基づいて、基本ＤＰＭの一つであるＤＰＭ０１を算出するＤＰＭ０１演算部１２１、ＤＰＭ０２を算出するＤＰＭ０２演算部１２２、ＤＰＭ０３を算出するＤＰＭ０３演算部１２３、ＤＰＭ０４を算出するＤＰＭ０４演算部１２４、ＤＰＭ０５を算出するＤＰＭ０５演算部１２５、ＤＰＭ０６を算出するＤＰＭ０６演算部１２６及びＤＰＭ０７を算出するＤＰＭ０７演算部１２７を備えている。これら演算部の構成については後ほど詳細に説明する。
【００２７】
参照ＤＰＭ演算部１３は、基本ＤＰＭ保持部１１に保持された基本ＤＰＭから参照ＤＰＭを算出する。図３は、参照ＤＰＭ演算部１３の内部構成を示す。参照ＤＰＭ演算部１３は、参照ＤＰＭの一つであるＤＰＭ１２を算出するＤＰＭ１２演算部３０１、ＤＰＭ１４を算出するＤＰＭ１４演算部３０２、ＤＰＭ１６を算出するＤＰＭ１６演算部３０３、ＤＰＭ２３を算出するＤＰＭ２３演算部３０４、ＤＰＭ２４を算出するＤＰＭ２４演算部３０５、ＤＰＭ２５を算出するＤＰＭ２５演算部３０６、ＤＰＭ２６を算出するＤＰＭ２６演算部３０７、ＤＰＭ２７を算出するＤＰＭ２７演算部３０８、ＤＰＭ３４を算出するＤＰＭ３４演算部３０９、ＤＰＭ３６を算出するＤＰＭ３６演算部３１０、ＤＰＭ４５を算出するＤＰＭ４５演算部３１１、ＤＰＭ４６を算出するＤＰＭ４６演算部３１２、ＤＰＭ４７を算出するＤＰＭ４７演算部３１３、ＤＰＭ５６を算出するＤＰＭ５６演算部３１４及びＤＰＭ６７を算出するＤＰＭ６７演算部３１５を備えている。ここで、参照ＤＰＭは、基本ＤＰＭどうしの差分として得られる。すなわち、参照ＤＰＭであるＤＰＭｉｊは、
ＤＰＭｉｊ＝ＤＰＭ０ｊ−ＤＰＭ０ｉ
として表される。すなわち、参照ＤＰＭは、特に複雑な計算を行うことなく算出することができる。なお、基本ＤＰＭの算出に必要な参照ＤＰＭについては後ほど詳細に説明する。
【００２８】
基本ＤＢＭ演算部１４は、畳み込み符号化されたデータ系列を受信し、特定の組み合わせのブランチメトリックどうしの差分を出力する。一般に、ブランチメトリックは入力データと理想値との間の二乗誤差である。すなわち、Ｄを入力データ、Ｙｉｊを理想値とすると、ブランチメトリックは、
ｂｉｊ＝（Ｄ−Ｙｉｊ）2
となる。これに対し、ＤＢＭは、
ＤＢＭ＝ｂｉｊ−ｂｋｌ＝（Ｄ−Ｙｉｊ）2−（Ｄ−Ｙｋｌ）2＝（Ｙｋｌ−Ｙｉｊ）（−Ｙｋｌ−Ｙｉｊ＋２・Ｄ）
となる。すなわち、ＤＢＭを用いることによって、ブランチメトリックの計算式に現れる二乗の項が消去される。ここで、Ｙｋｌ及びＹｉｊは定数であるため、Ｃ０及びＣ１を固定値として、
ＤＢＭ＝Ｃ０＋Ｃ１・Ｄ
となる。このように、基本ＤＢＭ演算部１４は、入力データに対して乗算及び加算をそれぞれ１回行って基本ＤＢＭを算出するため、比較的簡単な回路構成で実現される。なお、基本ＤＰＭの算出に必要な基本ＤＢＭについては後ほど詳細に説明する。
【００２９】
パス選択部１５は、基本ＤＢＭ、基本ＤＰＭ及び参照ＤＰＭを入力し、各ステートについてもっとも確からしいブランチがいずれであるかを示すパス選択信号を出力する。図４は、パス選択部１５の内部構成を示す。パス選択部１５は、パス選択信号出力部として、ステートＳ０に対応するパス選択信号ＳＰＮ０を出力するＳＰＮ０出力部１５０、ステートＳ１に対応するパス選択信号ＳＰＮ１を出力するＳＰＮ１出力部１５１、ステートＳ２に対応するパス選択信号ＳＰＮ２を出力するＳＰＮ２出力部１５２、ステートＳ３に対応するパス選択信号ＳＰＮ３を出力するＳＰＮ３出力部１５３、ステートＳ４に対応するパス選択信号ＳＰＮ４を出力するＳＰＮ４出力部１５４、ステートＳ５に対応するパス選択信号ＳＰＮ５を出力するＳＰＮ５出力部１５５、ステートＳ６に対応するパス選択信号ＳＰＮ６を出力するＳＰＮ６出力部１５６及びステートＳ７に対応するパス選択信号ＳＰＮ７を出力するＳＰＮ７出力部１５７を備えている。図１０のトレリス線図では、８個の各ステートに１時刻前の４個のステートからの計４本のブランチが接続されている。パス選択部１５は、各ステートについて、当該ステートに接続された４本のブランチの中からもっとも確からしいものを選択し、当該選択したブランチを示すパス選択信号を出力する。以下、パス選択信号出力部の例として、ＳＰＮ０出力部１５０について説明する。なお、これ以外のパス選択信号出力部についてもＳＰＮ０出力部１５０と同様に構成される。
【００３０】
図５は、ＳＰＮ０出力部１５０の内部構成を示す。ＳＰＮ０出力部１５０は、ステートＳ０への遷移に係る４本のブランチに、遷移元のステート番号の昇順に２ビットのパス選択番号を割り当て、このパス選択番号をステートＳ０に対応するパス選択信号ＳＰＮ０として出力する。具体的には、パス選択番号は、選択ブランチがｂ００のとき“０”、選択ブランチがｂ２０のとき“１”、選択ブランチがｂ４０のとき“２”、そして、選択ブランチがｂ６０のとき“３”である。
【００３１】
加算器５１は、基本ＤＰＭであるＤＰＭ０２と基本ＤＢＭである（ｂ２０−ｂ００）とを加算する。すなわち、加算器５１は、パス選択番号が“１”のブランチが選択された場合のパスメトリックから、パス選択番号が“０”のブランチが選択された場合のパスメトリックを引いた結果を出力する。符号判定器５２は、加算器５１の加算結果を入力し、当該結果が負の場合は“１”、それ以外の場合は“０”となる信号ｓｉｇ１を出力する。同様に、加算器５３は、パス選択番号が“３”のブランチが選択された場合のパスメトリックから、パス選択番号が“２”のブランチが選択された場合のパスメトリックを引いた結果を出力する。符号判定器５４は、加算器５３の加算結果を入力し、当該結果が負の場合は“１”、それ以外の場合は“０”となる信号ｓｉｇ２を出力する。
【００３２】
セレクタ５５は、信号ｓｉｇ１及びｓｉｇ２のいずれもが“０”の場合、パス選択番号が“２”のブランチのブランチメトリックからパス選択番号が“０”のブランチのブランチメトリックを引いた結果を出力し、信号ｓｉｇ１が“０”かつ信号ｓｉｇ２が“１”の場合、パス選択番号が“３”のブランチのブランチメトリックからパス選択番号が“０”のブランチのブランチメトリックを引いた結果を出力し、信号ｓｉｇ１が“１”かつ信号ｓｉｇ２が“０”の場合、パス選択番号が“３”のブランチのブランチメトリックからパス選択番号が“１”のブランチのブランチメトリックを引いた結果を出力し、そして、信号ｓｉｇ１及びｓｉｇ２のいずれもが“１”の場合、パス選択番号が“３”のブランチのブランチメトリックからパス選択番号が“１”のブランチのブランチメトリックを引いた結果を出力する。
【００３３】
セレクタ５６は、信号ｓｉｇ１及びｓｉｇ２のいずれもが“０”の場合、パス選択番号が“２”のブランチの始点であるステートＳ４のパスメトリックからパス選択番号が“０”のブランチの始点であるステートＳ０のパスメトリックを引いたＤＰＭ（基本ＤＰＭ０４）を出力し、信号ｓｉｇ１が“０”かつ信号ｓｉｇ２が“１”の場合、パス選択番号が“３”のブランチの始点であるステートＳ６のパスメトリックからパス選択番号が“０”のブランチの始点であるステートＳ０のパスメトリックを引いたＤＰＭ（基本ＤＰＭ０６）を出力し、信号ｓｉｇ１が“１”かつ信号ｓｉｇ２が“０”の場合、パス選択番号が“２”のブランチの始点であるステートＳ４のパスメトリックからパス選択番号が“１”のブランチの始点であるステートＳ２のパスメトリックを引いたＤＰＭ（参照ＤＰＭ２４）を出力し、信号ｓｉｇ１及びｓｉｇ２のいずれもが“１”の場合、パス選択番号が“３”のブランチの始点であるステートＳ６のパスメトリックからパス選択番号が“１”のブランチの始点であるステートＳ２のパスメトリックを引いたＤＰＭ（参照ＤＰＭ２６）を出力する。
【００３４】
加算器５７は、セレクタ５５からの出力とセレクタ５６からの出力を加算する。符号判定器５８は、加算器５７の加算結果を入力し、当該結果が負の場合は“１”、それ以外の場合は“０”となる信号ｓｉｇ３を出力する。セレクタ５９は、信号ｓｉｇ３が“０”の場合、信号ｓｉｇ１を出力し、信号ｓｉｇ３が“１”の場合、信号ｓｉｇ２を出力する。そして、セレクタ５９からの出力がパス選択信号ＳＰＮ０の下位ビット（ＳＰＮ０［０］）となり、信号ｓｉｇ３が上位ビット（ＳＰＮ０［１］）となる。
【００３５】
なお、本実施形態では、各ステートに接続されたブランチに、遷移元のステート番号の昇順にパス選択番号を割り当てているが、パス選択信号は必ずしも当該規則に従って生成しなくてもよい。
【００３６】
次に、基本ＤＰＭ演算部１２における、各基本ＤＰＭを算出するＤＰＭ０ｍ（ｍは１から７までの整数）演算部の例として、ＤＰＭ０１演算部１２１について説明する。なお、これ以外のＤＰＭ０ｍ演算部についてもＤＰＭ０１演算部と同様に構成される。
【００３７】
まず、ＤＰＭ０１演算部１２１の具体的な構成を説明する前に、ＤＰＭ０１の生成について説明する。図６は、時刻ｋにおける各種基本ＤＰＭの生成規則を示す。このうち、図６（ａ）は、時刻ｋにおけるＤＰＭ０１の生成規則を示す。時刻ｋにおけるＤＰＭ０１であるＤＰＭ０１（ｋ）は、パス選択信号ＳＰＮ０及びＳＰＮ１によって選択されるＤＢＭ及びＤＰＭ（ｋ−１）の和として算出される。例えば、パス選択信号ＳＰＮ０及びＳＰＮ１が、それぞれ、“０”及び“１”の場合、
ＤＰＭ０１（ｋ）＝（ｂ２１−ｂ００）＋ＤＰＭ０２（ｋ−１）
となる。なお、ＤＰＭ（ｋ−１）は、時刻ｋの１時刻前である時刻（ｋ−１）におけるＤＰＭを表す。ＤＰＭ０１以外の基本ＤＰＭであるＤＰＭ０２、ＤＰＭ０３、ＤＰＭ０４、ＤＰＭ０５、ＤＰＭ０６及びＤＰＭ０７は、それぞれ、図６（ｂ）、（ｃ）、（ｄ）、（ｅ）、（ｆ）及び（ｇ）に示した規則に従って生成される。
【００３８】
すでに述べたように、本実施形態に係るＡＣＳ回路が保持するＤＰＭは７個の基本ＤＰＭのみである。しかし、図６に示した生成規則によると、基本ＤＰＭの算出に、基本ＤＰＭ以外のＤＰＭが必要となる。そして、基本ＤＰＭ以外のＤＰＭを算出するのが、参照ＤＰＭ演算部１３である。参照ＤＰＭは、基本ＤＰＭどうしの差分として容易に算出されることはすでに述べたとおりである。しかも、基本ＤＰＭの算出に必要となる参照ＤＰＭは、当該基本ＤＰＭ算出の１時刻前のものでよい。すなわち、新たな基本ＤＰＭの算出には、基本ＤＢＭ演算部１４によって算出された基本ＤＢＭと、基本ＤＰＭ保持部１１に保持された１時刻前の基本ＤＰＭと、参照ＤＰＭ演算部１３によって１時刻前の基本ＤＰＭどうしの差分として得られる参照ＤＰＭとを用いればよい。
【００３９】
参照ＤＰＭとして、基本ＤＰＭ以外のすべてのＤＰＭを算出する必要はない。図１０のトレリス線図の場合、全部で２８個あるＤＰＭのうち基本ＤＰＭが７個であり、残りの２１個のＤＰＭが参照ＤＰＭとなり得る。このうち、実際に必要な参照ＤＰＭは、図３に示した１５個である。したがって、残り６個のＤＰＭについては、算出する必要がない。また、ＤＢＭは、基本ＤＰＭの算出に必要なものだけ、すなわち、基本ＤＢＭのみを算出すればよい。
【００４０】
次に、ＤＰＭ０１演算部１２１の具体的な構成について説明する。図７は、ＤＰＭ０１演算部１２１の内部構成を示す。当該ＤＰＭ０１演算部１２１は、図６に示した生成規則に従って、ＤＰＭ０１の候補となり得る値をすべて算出しておき、パス選択信号ＳＰＮ０及びＳＰＮ１に基づいて当該算出結果からいずれか一つを選択し、出力する。図８は、図７とは異なる構成のＤＰＭ０１演算部１２１の内部構成を示す。当該ＤＰＭ０１演算部１２１は、パス選択信号ＳＰＮ０及びＳＰＮ１に基づいてＤＰＭ０１の算出に必要なＤＢＭ及びＤＰＭを選択し、当該選択したＤＢＭとＤＰＭとを加算し、出力する。
【００４１】
以上、本実施形態によると、基本ＤＰＭのみを保持すればよいため、保持回路の規模は従来よりも小さくなる。さらに、ＤＰＭについては、基本ＤＰＭ及び参照ＤＰＭのみを算出すればよいため、ＤＰＭ算出に必要な加算器の個数は従来よりも少なくなる。具体的には、図１０のトレリス線図の場合、従来のＡＣＳ回路では、２８個のＤＰＭを保持する必要があるのに対して、本実施形態に係るＡＣＳ回路では、７個のＤＰＭ（基本ＤＰＭ）を保持するだけでよい。また、従来のＡＣＳ回路では、ＤＰＭの算出に４００個の加算器が必要となるが、本実施形態に係るＡＣＳ回路で必要となる加算器（減算器を含む）の個数は、基本ＤＰＭの算出用の１００個の加算器と参照ＤＰＭの算出用の１５個の減算器とを合わせた１１５個である。さらに、図８に示したＤＰＭ０ｍ演算部を採用することによって、加算器の個数は２５個にまで低減する。
【００４２】
なお、従来のＡＣＳ回路と比較して、本実施形態に係るＡＣＳ回路は、基本ＤＰＭを算出してから参照ＤＰＭを算出するため、参照ＤＰＭを算出する分だけ処理時間が長くなると想像されるかもしれない。しかし、時刻ｋにおける基本ＤＰＭ（ｋ）及び参照ＤＰＭ（ｋ）が実際に必要となるのは、時刻（ｋ＋１）における新たな基本ＤＰＭの算出のときであるから、時刻（ｋ＋１）における基本ＤＢＭの算出と同時に時刻ｋにおける参照ＤＰＭを演算すればよい。すなわち、基本ＤＢＭ演算部１４と参照ＤＰＭ演算部１３とを並列に動作させればよい。このようにすることで、参照ＤＰＭ算出に伴って処理時間が増加することがない。
【００４３】
また、上記説明ではステートＳ０を基準のステートとして説明したが、これ以外のステートを基準としてもよいことは言うまでもない。
【産業上の利用可能性】
【００４４】
以上のように、本発明に係るＡＣＳ回路は、比較的小さな回路規模及び比較的高速な処理速度で、ビタビ復号に係るパスメトリックのオーバーフロー対策を講じることができ、通信、光ディスク、磁気ディスクのリードチャネルシステムにおける誤り訂正技術に適用するものとして有用である。
【図面の簡単な説明】
【００４５】
【図１】本発明の最良の実施形態に係るＡＣＳ回路の構成図である。
【図２】基本ＤＰＭ演算部の内部構成図である。
【図３】参照ＤＰＭ演算部の内部構成図である。
【図４】パス選択部の内部構成図である。
【図５】パス選択部におけるＳＰＮ０出力部の内部構成図である。
【図６】基本ＤＰＭの生成規則を示した表である。
【図７】基本ＤＰＭ演算部におけるＤＰＭ０１演算部の内部構成図である。
【図８】基本ＤＰＭ演算部におけるＤＰＭ０１演算部の内部構成図である。
【図９】ギガビットイーサネット（イーサネット：登録商標）で一般的に用いられる畳み込み符号化器の構成図である。
【図１０】図９の畳み込み符号化器に係るトレリス線図である。
【符号の説明】
【００４６】
１１  基本ＤＰＭ保持部
１２  基本ＤＰＭ演算部
１３  参照ＤＰＭ演算部
１４  基本ＤＢＭ演算部
１５  パス選択部
【図１】
0004217261.tif 000002
【図２】
0004217261.tif 000003
【図３】
0004217261.tif 000004
【図４】
0004217261.tif 000005
【図５】
0004217261.tif 000006
【図６】
0004217261.tif 000007
【図７】
0004217261.tif 000008
【図８】
0004217261.tif 000009
【図９】
0004217261.tif 000010
【図１０】
0004217261.tif 000011