(57)【特許請求の範囲】
【請求項１】
２つのデータの加算を行い、和と上位への桁上げを出力する第１と第２の加算器と、前記第１と第２の加算器の加算によるオーバーフローを検出するオーバーフロー検出回路と、前記第１と第２の加算器が出力する和の大小比較を行う比較器と、前記オーバーフロー検出回路が出力するオーバーフロー検出信号と前記比較器が出力する比較結果をデコードするデコーダ回路と、前記デコーダ回路により制御され前記第１と第２の加算器の和を選択し、選択した加算器の和がオーバーフローデータの場合クリップ処理を行う、選択回路とクリップ処理回路を共通化したクリップ処理付き選択回路を備え、前記デコーダ回路は、前記第１の加算器の和と前記第２の加算器の和のどちらを選択したかを示す選択信号と前記第１の加算器の和を選択する場合と前記第２の加算器の和を選択する場合とクリップ処理を行う場合の３つの状態を制御する制御信号を生成し、前記クリップ処理付き選択回路は、前記制御信号に基づいて、前記第１の加算器の和と前記第２の加算器の和の選択と、各ビットを論理値１にするクリップ処理を一括して行う論理回路で構成されることを特徴とするＡＣＳ演算装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、誤り訂正の一種であるビタビ復号において、パスメトリックの算出を行うためのＡＣＳ演算装置に関する。
【０００２】
【従来の技術】
近年、映像、音声信号をディジタル信号として処理、伝送する方法が主流になっている。これらのディジタル信号処理で重要な技術として、誤り訂正技術がある。誤り訂正として、現在まで、さまざまな方式が提案されており、その一方式として、畳み込み符号を用いたビタビ復号がある。ビタビ復号は最も確からしい値に復号する最尤復号であり、起こりうる符号の中から受信符号に最も近い符号を選択し、情報として復号する。現時点の起こりうる符号と受信符号の差をブランチメトリック、ブランチメトリックの総和をパスメトリックと呼ぶ。パスメトリックを算出し、最小であるものを選択することで、最も近い符号の選択を実現する。パスメトリックの算出は、ＡＣＳ（Ａｄｄ  Ｃｏｍｐａｒｅ  Ｓｅｌｅｃｔ）演算により行われる。
【０００３】
上記した従来のビタビ復号器の一例として、特開平７−２０２７２４号公報のビタビ復号器がある。ＡＣＳ演算を行うＡＣＳユニットは、パスメトリックとブランチメトリックの加算（Ａｄｄ）を２種類のデータについてそれぞれ行い、加算結果を比較（Ｃｏｍｐａｒｅ）し、小さい方を選択（Ｓｅｌｅｃｔ）するＡＣＳ演算装置を基本要素として構成される。また、ＡＣＳ演算装置では、ブランチメトリックの累算を行うため、累算に伴う桁あふれの処理として、２種類のオーバーフロー処理を行う。オーバーフロー処理の一つ目は、ＡＣＳ演算装置自体で行うものであり、加算後に結果の上限を特定の値にするリミッタ処理（本明細書では以降クリップ処理と呼ぶ）である。また、二つ目は、ＡＣＳ演算装置へ与える入力データにより行うものであり、パスメトリックの値が特定の値を越えた場合にブランチメトリックに負の値を与えることによる正規化処理である。
【０００４】
ＡＣＳユニットは、ビタビ復号器の大きな部分を占めており、基本要素となるＡＣＳ演算装置について小規模な装置を提供することが、ビタビ復号器の回路規模縮小につながる。
【０００５】
【発明が解決しようとする課題】
しかしながら上記のようなＡＣＳ演算装置の構成では、オーバーフロー処理として加算後にクリップ処理を行い、続いて、選択を行っており、２つの加算結果に対応した２つのクリップ処理回路と選択回路が必要である。また、加算、選択後にクリップ処理を行えば、選択された１つの加算結果に対応した１つのクリップ処理回路で構成することができるが、オーバーフローデータを含む加算結果を大小比較し、選択後にオーバーフロー検出を行うには、入力データのビット幅に１を加えたビット幅の加算器および比較器が必要である。よって、基本要素であるＡＣＳ演算装置の規模を増大させ、ビタビ復号器の規模を増大させるという問題点を有していた。
【０００６】
そこで、本発明は、オーバーフロー検出信号と比較結果を用いて選択回路を制御すれば、選択回路とクリップ処理回路が共通化できる点に新たに着目して、オーバーフロー検出信号と比較結果をデコードするデコード回路とデコード回路により制御され選択とクリップ処理を一括して行うクリップ処理付き選択回路を備えて得られたものである。また、ＡＣＳ演算装置のパスメトリックは正数データ、ブランチメトリックは２の補数データ、パスメトリックとブランチメトリックの和は正数データである点に新たに着目して、加算器および比較器のビット幅を削減して得られたものである。
【０００７】
従って本発明は上記問題点に鑑み、その目的は、ビタビ復号器の回路規模を縮小させるための小規模なＡＣＳ演算装置を提供することにある。
【０００８】
【課題を解決するための手段】
上記問題点を解決するために本発明のＡＣＳ演算装置は、２つのデータの加算を行い、和と上位への桁上げを出力する第１と第２の加算器と、第１と第２の加算器の加算によるオーバーフローを検出するオーバーフロー検出回路と、第１と第２の加算器が出力する和の大小比較を行う比較器と、オーバーフロー検出回路が出力するオーバーフロー検出信号と比較器が出力する比較結果をデコードするデコーダ回路と、デコーダ回路により制御され第１と第２の加算器の和を選択し、選択した加算器の和がオーバーフローデータの場合クリップ処理を行う、選択回路とクリップ処理回路を共通化したクリップ処理付き選択回路を備え、前記デコーダ回路は、前記第１の加算器の和と前記第２の加算器の和のどちらを選択したかを示す選択信号と前記第１の加算器の和を選択する場合と前記第２の加算器の和を選択する場合とクリップ処理を行う場合の３つの状態を制御する制御信号を生成し、前記クリップ処理付き選択回路は、前記制御信号に基づいて、前記第１の加算器の和と前記第２の加算器の和の選択と、各ビットを論理値１にするクリップ処理を一括して行う論理回路で構成されることを特徴とするものである。
【０００９】
本発明は上記した構成によって、オーバーフロー検出信号と比較結果をデコード回路がデコードし、クリップ処理付き選択回路を制御して、加算結果の選択とクリップ処理を一括して行うことができ、選択回路とクリップ処理回路を共通化することにより、回路規模を縮小させることとなる。
【００１２】
【発明の実施の形態】
以下本発明の一実施の形態のＡＣＳ演算装置について、図面を参照しながら説明する。
【００１３】
図１は本発明の第１の実施の形態におけるＡＣＳ演算装置の構成図である。図に示すＡＣＳ演算装置は、パスメトリックＰＭＡ［４：０］、ＰＭＢ［４：０］、ブランチメトリックＢＭＡ［４：０］、ＢＭＢ［４：０］を入力として、ＡＣＳ演算を行い、パスメトリックＰＭ［４：０］を出力する。
【００１４】
図１において、１０１、１０２はそれぞれパスメトリックとブランチメトリックの加算を行い、加算結果と上位への桁上げを出力する加算器である。加算器１０１はパスメトリックＰＭＡ［４：０］とブランチメトリックＢＭＡ［４：０］を入力として、ＰＭＡ［４：０］＋ＢＭＡ［４：０］を実行後、加算結果ＡＡ［４：０］と上位への桁上げＣＡを出力し、加算器１０２はパスメトリックＰＭＢ［４：０］とブランチメトリックＢＭＢ［４：０］を入力として、ＰＭＢ［４：０］＋ＢＭＢ［４：０］を実行後、加算結果ＡＢ［４：０］と上位への桁上げＣＢを出力する。
【００１５】
１０３は加算結果ＡＡ［４：０］、ＡＢ［４：０］の大小比較を行い比較結果ＣＰを出力する比較器である。１０４は加算器１０１、１０２の加算時のオーバーフローを検出するオーバーフロー検出回路であり、ＰＭＡ［４：０］＋ＢＭＡ［４：０］実行時のオーバーフロー検出信号ＯＡ、ＰＭＢ［４：０］＋ＢＭＢ［４：０］実行時のオーバーフロー検出信号ＯＢを出力する。
【００１６】
１０５はオーバーフロー検出信号ＯＡ、ＯＢ、比較結果ＣＰをデコードして、制御信号ＳＡ、ＳＢ、ＰＳを出力するデコーダ回路である。１０６は制御信号ＳＡ、ＳＢにより制御され、加算結果ＡＡ［４：０］、ＡＢ［４：０］のうち小さい方を選択するが、選択する加算結果がオーバーフローデータの場合、クリップ処理を行うクリップ処理付き選択回路であり、ＡＣＳ演算後のパスメトリックＰＭ［４：０］を出力する。デコーダ回路１０５が出力する制御信号ＰＳはクリップ処理付き選択回路がどちらの加算結果を選択したかを示す信号である。
【００１７】
本明細書では、信号の表記方法として、ｎビットのバスを信号名［ｎ−１：０］と示し、ｎビットのバスのＬＳＢからｉ番目のビットを信号名［ｉ］（０≦ｉ≦ｎ−１）と示す。
【００１８】
以上のように構成されたＡＣＳ演算装置について、以下その動作を説明する。図１のＡＣＳ演算装置では、まず、パスメトリックとブランチメトリックの加算（Ａｄｄ）を２種類のデータについて行うが、加算器１０１でＰＭＡ［４：０］＋ＢＭＡ［４：０］、加算器１０２でＰＭＢ［４：０］＋ＢＭＢ［４：０］を実行する。次に、オーバーフロー検出装置１０４が、加算時のオーバーフローを検出し、また、比較器１０３が加算結果の大小比較（Ｃｏｍｐａｒｅ）を行う。続いて、デコーダ回路１０５が、オーバーフロー検出信号ＯＡ、ＯＢと比較結果ＣＰのデコードを行い、クリップ処理付き選択回路１０６が加算結果のうち小さい方を選択（Ｓｅｌｌｅｃｔ）するが、選択する加算結果がオーバーフローデータの場合、クリップ処理を行い、ＡＣＳ演算後のパスメトリックＰＭ［４：０］を出力する。
【００１９】
クリップ処理付き選択回路１０６はデコーダ回路１０５により制御され加算結果の選択とクリップ処理を一括して行う。図２にデコーダ回路１０５、クリップ処理付き選択回路１０６の動作説明のための真理値表を示す。ＯＡ、ＯＢ、ＣＰはデコーダ回路１０５の入力信号であり、ＳＡ、ＳＢ、ＰＳはデコーダ回路１０５の出力信号であり、ＰＭ［４：０］はクリップ処理付き選択回路１０６が出力するＡＣＳ演算後のパスメトリックである。図に示すように、デコーダ回路１０５は、クリップ処理付き選択回路１０６がＰＭ［４：０］として、ＰＭＡ［４：０］＋ＢＭＡ［４：０］を選択する場合は、ＳＡを論理値１、ＳＢを論理値０とし、ＰＭＢ［４：０］＋ＢＭＢ［４：０］を選択する場合は、ＳＡを論理値０、ＳＢを論理値１とし、また、クリップ処理を行い最大値（ａｌｌ  １）にする場合、ＳＡ、ＳＢを共に論理値０とする。クリップ処理付き選択回路１０６は図１に示すように、２つの論理積と１つの論理和と入出力の論理否定を用いた複合論理ゲートで構成されており、図２に示す制御信号ＳＡ、ＳＢにより加算結果の選択とクリップ処理を一括して行う。
【００２０】
以上のように本実施の形態によれば、オーバーフロー検出信号ＯＡ、ＯＢと比較結果ＣＰをデコードするデコード回路１０５とデコード回路１０５の出力する制御信号により加算結果の選択とクリップ処理を一括して行うクリップ処理付き選択回路１０６を設けたことにより、選択回路とクリップ処理回路を共通化することができ、回路規模を縮小させることとなる。
【００２１】
以下本発明の第２の実施の形態について、図面を参照しながら説明する。
図１は本発明の第２の実施の形態を示すＡＣＳ演算装置の構成図である。構成は第１の実施の形態と同様であり、同一の符号を付して一部その詳細な説明を省略する。第２の実施の形態では、加算器１０１、１０２、オーバーフロー検出回路１０４、比較器１０３の構成について説明する。
【００２２】
図に示すＡＣＳ演算装置は、パスメトリックＰＭＡ［４：０］、ＰＭＢ［４：０］、ブランチメトリックＢＭＡ［４：０］、ＢＭＢ［４：０］を入力として、ＡＣＳ演算を行い、パスメトリックＰＭ［４：０］を出力する。パスメトリックＰＭＡ［４：０］、ＰＭＢ［４：０］、ＰＭ［４：０］は正数データであり、ブランチメトリックＢＭＡ［４：０］、ＢＭＢ［４：０］は２の補数データである。また、パスメトリックとブランチメトリックの和ＡＡ［４：０］、ＡＢ［４：０］は正数データである。ＡＣＳ演算では、オーバーフロー処理として、加算時のオーバーフローを検出して行うクリップ処理に加え、パスメトリックの値が特定の値を越えた場合にブランチメトリックに負の値を与えることによる正規化処理がある。そこで、ブランチメトリックＢＭＡ［４：０］、ＢＭＢ［４：０］は正規化処理を行うために２の補数データとなる。
【００２３】
図３に加算器１０１、１０２で用いる５ビット加算器の構成を示す。図に示す加算器は、５ビットのデータＡ［４：０］、Ｂ［４：０］と下位からの桁上げＣＩＮを入力として、Ａ［４：０］＋Ｂ［４：０］＋ＣＩＮの加算を行い、５ビットの和ＳＵＭ［４：０］と上位への桁上げＣＯＵＴを出力する。図３において、３０１〜３０５は全加算器（１ビット加算器）であり、リップルキャリー加算器を構成する。図に示す加算器のＡ［４：０］、Ｂ［４：０］、ＣＩＮ、ＣＯＵＴを、加算器１０１ではそれぞれＰＭＡ［４：０］、ＢＭＡ［４：０］、論理値０、ＣＡとし、加算器１０２ではそれぞれＰＭＢ［４：０］、ＢＭＢ［４：０］、論理値０、ＣＢとして用いる。
【００２４】
図１にオーバーフロー検出回路１０４の構成を示す。オーバーフロー検出回路１０４は、ブランチメトリックの最上位ビットＢＭＡ［４］、ＢＭＢ［４］と上位への桁上げ出力ＣＡ、ＣＢより、加算器１０１、１０２の加算時のオーバーフローを検出する。ＢＭＡ［４］、ＢＭＢ［４］はそれぞれのブランチメトリックＢＭＡ［４：０］、ＢＭＢ［４：０］の符号ビットである。図４、図５にオーバーフロー検出回路１０４の動作説明のための真理値表を示す。図４において、ＯＡは加算器１０１のオーバーフロー検出信号であり、図５において、ＯＢは加算器１０２のオーバーフロー検出信号である。ブランチメトリックが負（符号ビットが論理値１）の場合には、オーバーフローは起こり得ない。そこで、オーバーフロー検出回路では、ブランチメトリックが正（符号ビットが論理値０）であり、それぞれの加算器の上位への桁上げが論理値１の時にオーバーフローを検出する。
【００２５】
図６に比較器１０３の構成を示す。図に示す比較器は、加算結果ＡＢ［４：０］とＡＡ［４：０］の減算を行い、減算結果の符号ビットにより大小判定を行う比較器であり、比較結果ＣＰにＡＢ［４：０］がＡＡ［４：０］より小さい場合、論理値０、そうでない場合、論理値１を出力する。図６において、２０１は図３に示したものと同様の加算器であり、２０２はＡＡ［４：０］の全ビットを論理反転させる論理否定ゲートである。加算器２０１では、図３に示す加算器のＡ［４：０］、Ｂ［４：０］、ＣＩＮ、ＣＯＵＴを、それぞれＡＡ［４：０］の論理反転、ＡＢ［４：０］、論理値１、ＣＰとして用いる。
【００２６】
通常、２つの５ビットデータの加算結果は、オーバーフローデータを含んで表現する場合、６ビットデータとなり、大小比較を行うには６ビット加算器が必要となる。しかしながら、加算器１０１、１０２のパスメトリックとブランチメトリックの和である加算結果ＡＡ［４：０］、ＡＢ［４：０］は正数データであり、また、加算器１０１、１０２の加算時のオーバーフローを検出した場合、比較結果に関わらず、デコーダ回路１０５、クリップ処理付き選択回路１０６がクリップ処理を行うため、５ビット加算器で構成することができる。
【００２７】
以上のように、ＡＣＳ演算装置のパスメトリックは正数データ、ブランチメトリックは２の補数データである点を考慮し、オーバーフロー検出回路１０４がブランチメトリックの符号ビットと加算による上位への桁上げよりオーバーフローを検出し、また、パスメトリックとブランチメトリックの和は正数データである点を考慮して比較器１０３が加算結果の大小比較を行うことにより、加算器および比較器のビット幅を入力データのビット幅に等しいビット幅にすることができ、回路規模を縮小させることとなる。
【００２８】
なお、本発明の第１および第２の実施の形態において、加算器１０１と加算器１０２の加算によるオーバーフローが検出されず、かつ、加算結果が等しい場合、クリップ処理付き選択回路１０６は加算器１０１の加算結果を選択するが、加算器１０２の加算結果を選択してもよい。
【００２９】
また、本発明の第２の実施の形態において、加算器１０１、１０２および比較器１０３の加算器２０１で用いる５ビット加算器としてリップルキャリー加算器を用いたが、ＣＬＡ（Ｃａｒｒｙ  Ｌｏｏｋ  Ａｈｅａｄ）加算器等の高速な加算器を用いてもよい。
【００３０】
【発明の効果】
以上のように本発明はオーバーフロー検出信号と大小比較による比較結果をデコードするデコード回路とデコード回路の出力する制御信号により加算結果の選択とクリップ処理を一括して行うクリップ処理付き選択回路を設けることにより、選択回路とクリップ処理回路を共通化することができ、回路規模を縮小することができる。
【００３２】
ＡＣＳ演算装置はビタビ復号器の大きな部分を占めるＡＣＳユニットの基本要素であり、上記回路規模縮小により、小規模なビタビ復号器を提供することができる。
【図面の簡単な説明】
【図１】本発明の第１、第２の実施の形態におけるＡＣＳ演算装置の構成図
【図２】第１の実施の形態におけるデコーダ回路、クリップ処理付き選択回路の動作説明のための真理値表を示した図
【図３】本発明の第２の実施の形態における５ビット加算器の構成図
【図４】本発明の第２の実施の形態におけるオーバーフロー検出回路の動作説明のための真理値表を示した図
【図５】本発明の第２の実施の形態におけるオーバーフロー検出回路の動作説明のための真理値表を示した図
【図６】本発明の第２の実施の形態における比較器の構成図
【符号の説明】
１０１，１０２，２０１  加算器
１０３  比較器
１０４  オーバーフロー検出回路
１０５  デコーダ回路
１０６  クリップ処理付き選択回路
２０２  論理否定ゲート
３０１〜３０５  全加算器（１ビット加算器）
【図１】
0003546581.tif 000002
【図２】
0003546581.tif 000003
【図３】
0003546581.tif 000004
【図４】
0003546581.tif 000005
【図５】
0003546581.tif 000006
【図６】
0003546581.tif 000007