(57)【要約】【課題】ビタビ復号化の高速化を実現できるビタビ復号装置を提供する。【解決手段】４次元ブランチメトリック演算部４は、畳み込み符号のデータから、ブランチメトリックを算出する。パスメトリック保持レジスタ７は、処理過程の１時点前の各ステートへ至るパスのパスメトリックのうち最小のパスメトリックを保持する。加算部５は、パスメトリック保持レジスタ７に保持されたパスメトリックに、４次元ブランチメトリック演算部４によって算出されたブランチメトリックを加算して現時点のパスメトリックを得る。ステートの遷移の回数が２のｍ乗以下であり、各ブランチのブランチメトリックの値をｎビットで表現した場合に、演算部５とパスメトリック保持レジスタ７のビット幅はｍ＋ｎ以上である。この構成により、正規化処理を行わなくともオーバーフローが発生しない。そのため、正規化処理を省略することができ、ビタビ復号化の高速化を実現することができる。【選択図】図１
2007312267.tif 000002
【特許請求の範囲】
【請求項１】
畳み込み符号のデータからブランチメトリックを算出する演算部と、
処理過程の１時点前の各ステートのパスメトリックを保持するパスメトリック保持レジスタと、
前記パスメトリック保持レジスタに保持された処理過程の１時点前の各ステートのパスメトリックに、前記演算部によって算出されたブランチメトリックを加算して現時点のパスメトリックを得る加算部と、
を備え、
ステートの遷移の回数が２のｍ乗以下であり、各ブランチのブランチメトリックの値をｎビットで表現した場合に、前記演算部と前記パスメトリック保持レジスタのビット幅はｍ＋ｎ以上であることを特徴とするビタビ復号装置。
【請求項２】
請求項１記載のビタビ復号装置において、前記加算部が得た現時点のパスメトリックを保持し、前記パスメトリック保持レジスタに入力する、ビット幅がｍ＋ｎ以上の加算結果保持レジスタを備えたことを特徴とするビタビ復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、受信した畳み込み符号に対してビタビ復号を行うビタビ復号装置に関するものである。
【背景技術】
【０００２】
ＡＤＳＬ（Ａｓｙｍｍｅｔｒｉｃ  Ｄｉｇｉｔａｌ  Ｓｕｂｓｃｒｉｂｅｒ  Ｌｉｎｅ）、ＰＬＣ（Ｐｏｗｅｒ  Ｌｉｎｅ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ）等のＯＦＤＭ(Ｏｒｔｈｏｇｏｎａｌ  Ｆｒｅｑｕｅｎｃｙ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘｉｎｇ)変調を用いる通信では、誤り訂正符合に畳み込み符号が使用され、復号にはビタビ復号を用いる。受信した畳み込み符号の複素数データに対してビタビ復号を行うビタビ復号装置は、ある周波数の複素数のデータから複数のブランチメトリックを算出する。ビタビ復号装置は、処理過程の１時点前の各ステートのパスメトリックを保持するレジスタと、レジスタに保持された処理過程の１時点前のパスメトリックに算出したブランチメトリックを加算して新しいパスメトリックを得る加算部とを備える。次の周波数のデータが入力されそのデータからブランチメトリックが算出されると、得られたパスメトリックは処理過程の１時点前のパスメトリックとしてレジスタに保持され、同様の処理が繰り返される。
【０００３】
このように、パスメトリックを得るために繰り返し加算を行うことによって、パスメトリックの値が非常に大きくなる。演算部やレジスタからパスメトリックがオーバーフローしてしまい正しい結果が得られなくなるのを防止するために、従来のビタビ復号装置は、パスメトリックの演算を行ったところで、必要に応じて全てのパスメトリックから一定の値又は最小値を減算する正規化と呼ばれる処理を行っていた。
【０００４】
図３は、従来のビタビ復号におけるメトリック正規化装置の構成を示すブロック図である（特許文献１参照）。比較手段１０９〜１１６は、ディジタルデータ信号１０１〜１０８を入力とし、入力をしきい値と比較し、入力がしきい値以下であれば０を、しきい値より大きければ１を出力する。論理和手段１１７は、比較手段１０９〜１１６の出力を入力とし、入力がすべて０であれば０を出力する。減算手段１１８〜１２５は、それぞれディジタルデータ信号１０１〜１０８及び論理和手段１１７の出力を入力とし、後者が０であれば前者を出力し、後者が１であれば前者から所定値を減算し、出力する。この構成によって、いずれかのメトリックがしきい値を越えたときに全てのメトリックから定数を減算することによりメトリックの正規化を行う。
【特許文献１】特開平６−１６４４２２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記の従来の構成では、正規化処理を行うのに時間が非常にかかり、復号処理の高速化の障害となるという課題があった。
【０００６】
本発明は、このような課題を解決するものであり、処理の高速化を実現できるビタビ復号装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明は上記目的を達成するために、畳み込み符号のデータからブランチメトリックを算出する演算部と、処理過程の１時点前の各ステートのパスメトリックを保持するパスメトリック保持レジスタと、前記パスメトリック保持レジスタに保持された処理過程の１時点前の各ステートのパスメトリックに、前記演算部によって算出されたブランチメトリックを加算して現時点のパスメトリックを得る加算部と、を備え、ステートの遷移の回数が２のｍ乗以下であり、各ブランチのブランチメトリックの値をｎビットで表現した場合に、前記演算部と前記パスメトリック保持レジスタのビット幅はｍ＋ｎ以上であることを特徴とする。この構成により、正規化処理を行わなくともオーバーフローが発生しない。そのため、正規化処理を省略することができ、ビタビ復号化の高速化を実現することができる。
【発明の効果】
【０００８】
本発明のビタビ復号装置によれば、演算器及びレジスタが十分なビット幅を有するため、パスメトリックの正規化処理を行わずともオーバーフローが発生することがない。そのため、パスメトリックの正規化処理を省略することができ、ビタビ復号化の処理の高速化を実現することができる。
【発明を実施するための最良の形態】
【０００９】
本発明のビタビ復号装置は、畳み込み符号のデータからブランチメトリックを算出する演算部と、処理過程の１時点前の各ステートのパスメトリックを保持するパスメトリック保持レジスタと、前記パスメトリック保持レジスタに保持された処理過程の１時点前の各ステートのパスメトリックに、前記演算部によって算出されたブランチメトリックを加算して現時点のパスメトリックを得る加算部と、を備え、ステートの遷移の回数が２のｍ乗以下であり、各ブランチのブランチメトリックの値をｎビットで表現した場合に、前記演算部と前記パスメトリック保持レジスタのビット幅はｍ＋ｎ以上であることを特徴とする。この構成により、正規化処理を行わなくともオーバーフローが発生しない。そのため、正規化処理を省略することができ、ビタビ復号化の高速化を実現することができる。
【００１０】
また、本発明のビタビ復号装置は、前記加算部が得た現時点のパスメトリックを保持し、前記パスメトリック保持レジスタに入力する、ビット幅がｍ＋ｎ以上の加算結果保持レジスタを備えたことを特徴とする。これによって、加算部が得たパスメトリックをパスメトリック保持レジスタへ間接的に入力することができる。
【００１１】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００１２】
図１は本発明の実施の形態に係るビタビ復号装置の構成を示すブロック図である。
【００１３】
このビタビ復号装置は、ＡＤＳＬにおける畳み込み符号のビタビ復号装置に関するものである。ＡＤＳＬでは、変調方式にＯＦＤＭが用いられるため、ＦＦＴ（Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）と周波数領域での等化処理とが行われ、それらの処理によって得られた各周波数の複素数データが連続して本ビタビ復号装置に入力される。
【００１４】
図１において、１はデマッパ、２は上位ビットメモリ、３は２次元ブランチメトリック演算部、４は４次元ブランチメトリック演算部、５は加算部、６は加算結果保持レジスタ、７はパスメトリック保持レジスタ、８は最小値探索部、９はステートメモリ、１０はトレースバック処理部、１１は出力制御部である。
【００１５】
前記各周波数の複素数データはまずデマッパ１に入力され、デマッパ１は入力された複素数データをビット列に分解する。デマッパ１は上位ビットメモリ２と２次元ブランチメトリック演算部３とに接続されている。ＡＤＳＬにおいては、複素数データのうち下位２ビットのみが畳み込み符号化されているため、デマッパ１は、下位２ビット以外を上位ビットとして上位ビットメモリ２に入力し、上位ビットメモリ２は入力された上位ビットを保存する。上位ビットメモリ２は出力制御部１１に接続され、上位ビットメモリ２は上位ビットを出力制御部１１に入力する。また、デマッパ１は、下位２ビットを２次元ブランチメトリック演算部３へ入力する。
【００１６】
２次元ブランチメトリック演算部３は、デマッパ１から入力された下位２ビットの２次元ブランチメトリックの計算を行う。図２は、２次元ブランチメトリックの概念を示す複素数平面図であり、ある周波数の複素数データを図示する。ここでは、座標（１，１）、（１，３）、（３，１）、（３，３）の４つの点が本来の受信点とし、各点がビタビ復号のアルゴリズムにおけるステート００、０１、１０、１１のいずれかに相当する。受信データは本来これらの受信点のうちのいずれかで表されるが、伝送路の歪やノイズ等の影響で、実際の受信点は本来の受信点からずれてしまう。図２では、２４が実際の受信点とする。２次元ブランチメトリック演算部３は、実際の受信点２４と本来の受信点各々との距離（図２上では矢印で示す）を２次元ブランチメトリックとして算出する。２次元ブランチメトリック演算部３は、４次元ブランチメトリック演算部４に接続され、算出した２次元ブランチメトリックを４次元ブランチメトリック演算部４に入力する。そして、次の周波数の複素数データに対しても同様に、２次元ブランチメトリックを算出し４次元ブランチメトリック演算部４に入力する。４次元ブランチメトリック演算部４は、入力された隣り合う２つの周波数の２次元ブランチメトリックを加算し、得られたものを４次元ブランチメトリックとする。４次元ブランチメトリック演算部４は、加算部５に接続され、得られた各４次元ブランチメトリックを加算部５に入力する。
【００１７】
４次元ブランチメトリックをたどることで得られるパスに沿った４次元ブランチメトリックの和をパスメトリックといい、初期状態から現時点の各ステートに至るパスのパスメトリックが該ステートのパスメトリックである。全てのステートのパスメトリックの初期値は０であり、１時点ごとに各ステートに至るパスの新しいブランチメトリックが該ステートのパスメトリックに加算される。加算部５はパスメトリック保持レジスタ７にも接続され、パスメトリック保持レジスタ７は処理過程の１時点前の各ステートへ至る複数のパスのパスメトリックのうち最小のパスメトリックを保持しており、加算部５に入力する。
【００１８】
加算部５は、パスメトリック保持レジスタ７から入力された処理過程の１時点前の各ステートの最小のパスメトリックに、４次元ブランチメトリック演算部４から入力された４次元ブランチメトリックを加算することによって、現時点での各パスのパスメトリックを算出する。加算部５はさらに加算結果保持レジスタ６に接続され、算出した各パスのパスメトリックを加算結果保持レジスタ６に入力し、加算結果保持レジスタ６は最新のパスメトリックを保持する。加算結果保持レジスタ６は、パスメトリック保持レジスタ７に接続され、最新のブランチメトリックが算出されたら、保持しているパスメトリックを１状態前のパスメトリックとしてパスメトリック保持レジスタ７に入力する。
【００１９】
パスメトリック保持レジスタ７は、最小値探索部８にも接続され、最小値探索部８は、パスメトリックとブランチメトリックの加算の結果に関して最も小さな値を探索する。パスメトリック保持レジスタ７は、さらにステートメモリ９に接続され、ステートメモリ９は、各ステートへの複数のパスのうちパスメトリックが最小となるパスを生き残りパスとして記憶する。具体的には、該生き残りパスがどのステートからどのステートへ遷移したか、該生き残りパスに沿ったブランチメトリックは何であるかを記憶する。
【００２０】
以上の処理が周波数毎に繰り返され、各ステートへの生き残りパスの情報がステートメモリ９に記憶される。ステートメモリ９にはトレースバック処理部１０が接続され、トレースバック処理部１０は所定数（例えば、１６）の遷移がなされたら、ステートメモリ９の内容をうしろから振り返ることによって復号を行う。まず、トレースバック処理部１０は現時点のパスメトリックのうち最小のパスメトリックを有するステートを検索し、そのステートへ至る生き残りパスをさかのぼる。つまり、トレースバック処理部１０は、ステートメモリ９から生き残りパスの情報を取り出し、最終的に所定数の遷移前のステートにたどりついたら、そこに保持されているブランチメトリックに基づく値を下位２ビットの復号データとする。
【００２１】
新しいパス情報がステートメモリ９に記憶されたら、トレースバック処理部１０は次に１時点ずらして同様の処理を行う。トレースバック処理部１０は、出力制御部１１に接続され、下位２ビットの復号データを出力制御部１１に入力する。出力制御部１１は、上位ビットメモリ２から入力された上位ビットと、トレースバック処理部１０から入力された復号下位２ビットとを組み合わせて、複素数データの復号データを得て出力する。
【００２２】
本発明では、加算部５が処理過程の１時点前のパスメトリックに新しいブランチメトリックを加算し最新のパスメトリックを算出したのちに、該最新のパスメトリックの正規化処理を行わない。加算部５による加算は、全周波数帯にわたって行われるため、パスメトリックの値はどんどん大きくなり、加算部５、加算結果レジスタ６、パスメトリック保持レジスタ７が十分なビット幅がなければ、オーバーフローが生じて正確な値が得られなくなることになる。
【００２３】
本発明のビタビ復号装置では、符号の状態遷移の回数が２のｍ乗以下で終端する畳み込み符号の復号化処理において、ブランチメトリックの値をｎビットで表現した場合に、最低限ｍ＋ｎビット幅の演算のできる加算部５、加算結果レジスタ６、パスメトリック保持レジスタ７を備える。これにより、ブランチメトリックの値とパスメトリックの値との加算を符号が終端するまで繰り返してもオーバーフローが生ずることなく演算することができる。そのため、正規化処理を省略することができ、ビタビ復号化の処理を高速化することができる。
【００２４】
例えば、ＡＤＳＬでは、周波数帯は、Ｇ．９９２．１勧告に従った場合には２５６（２の８乗）本以下となる。２本の周波数帯で１個の４次元のブランチメトリックの値となるため、ブランチメトリックとパスメトリックの加算は、最高１２８回行われる事となる。また、２次元ブランチメトリックの値を８ビットの値とすると、その最大値は１６進数表現でＦＦ（１０進数で２５５）となる。４次元ブランチメトリックでは、２次元ブランチメトリックを２個加算するため、その最大値は、２次元ブランチメトリックの最大値の２倍の、１６進数で１ＦＥ（１０進数で５１０）となる。パスメトリックは、４次元ブランチメトリックの値が１２８回加算されるため、その最大値は、４次元ブランチメトリックの最大値の１２８倍の、１６進数でＦＦ００（１０進数で６５２８０＝５１０×１２８）となる。これは、２の１６乗（１０進数で６５５３６）未満であるため、加算部５、加算結果保持レジスタ６及びパスメトリック保持レジスタ７は最低限１６ビット幅を備えていればオーバーフローが生じることはない。この場合、ｍもｎも８であり、最低限のビット幅はｍ＋ｎの１６である。
【００２５】
本実施の形態では、ビタビ復号装置をＡＤＳＬに適用したが、ＡＤＳＬに限定されるものではなく、ＰＬＣ等のＯＦＤＭ変調を用いる通信ならどれにでも適用できる。
【産業上の利用可能性】
【００２６】
本発明にかかるビタビ復号装置は、ＡＤＳＬやＰＬＣ等のＯＦＤＭ変調を用いる通信において、畳み込み符号を高速で復号するのに利用できる。
【図面の簡単な説明】
【００２７】
【図１】本発明の実施の形態に係るビタビ復号装置の構成を示すブロック図
【図２】２次元ブランチメトリックの算出方法を示す概念図
【図３】従来のビタビ復号装置の正規化装置の構成を示す回路図
【符号の説明】
【００２８】
１    デマッパ
２    上位ビットメモリ
３    ２次元ブランチメトリック演算部
４    ４次元ブランチメトリック演算部
５    加算部
６    加算結果保持レジスタ
７    パスメトリック保持レジスタ
８    最小値探索部
９    ステートメモリ
１０    トレースバック処理部
１１    出力制御部
２４    受信点
１０１〜１０８    入力ディジタルデータ信号
１０９〜１１６    比較手段
１１７〜１２５    論理和手段
【図１】
2007312267.tif 000003
【図２】
2007312267.tif 000004
【図３】
2007312267.tif 000005