(57)【要約】    【課題】      複数種類の拘束長及び任意の推定伝送路の係数の数に対応でき、かつ、小さな回路規模の専用ハードウエアにより構成できるようにすること。    【解決手段】  前時刻の状態から現時刻の状態に至る全てのパスのブランチメトリックを演算し、ブランチメトリック１０１ａとパスメトリック１０３ａとにより各状態へ至るパスの中から最も確からしいパスを選択し、パスセレクト信号１０２ａとパスメトリック１０２ｂとを出力する。パスメトリック記憶装置１０３は、次時刻でのＡＣＳ演算を行なう際にＡＣＳ演算装置１０２に対して入力するパスメトリック１０３ａを出力する。パスセレクト信号一時記憶装置１０４は、パスセレクト信号１０２ａをｎステート分だけ記憶し、ｍステート分（ｍ＜＝ｎ）のパスセレクト信号１０４ａを出力し、ビタビ復号を行なうシステムの符号化拘束長又は想定される推定伝送路の係数の数に応じて入力ビット位置を変更する。  【選択図】      図１
2005045727.tif 000002
【特許請求の範囲】
【請求項１】
入力符号に基づいて前時刻の状態から現時刻の状態に至るすべてのパスのブランチメトリックを算出するブランチメトリック演算手段と、
前記ブランチメトリック演算手段により算出された前記ブランチメトリックと与えられたパスメトリックとにより現時刻の各状態へ至るパスの中から選択した最も確実性の高いパスによって決定されるパスセレクト信号と現時刻の状態に至るまでに要したパスメトリックとを出力するＡＣＳ演算手段と、
前記ＡＣＳ演算手段より出力された前記パスメトリックを記憶するパスメトリック記憶手段と、
前記ＡＣＳ演算手段から出力された前記パスセレクト信号をｎステート分だけ記憶するパスセレクト信号一時記憶手段と、
前記パスセレクト信号一時記憶手段に格納された前記パスセレクト信号を順に一連のトレースバック長分だけ記憶するパスセレクト信号記憶手段と、
前記パスセレクト信号記憶手段に記憶された前記パスセレクト信号に基づいて復号データを生成するトレースバック処理手段と、
を具備することを特徴とするビタビ復号器。
【請求項２】
前記パスセレクト信号一時記憶手段はｎビットのパスセレクト信号用シフトレジスタを有し、前記パスセレクト信号用シフトレジスタが所定のビット位置より前記パスセレクト信号を入力することを特徴とする請求項１記載のビタビ復号器。
【請求項３】
前記トレースバック処理手段は、前記パスセレクト信号記憶手段から読み出されたパスセレクト信号をシフトするバレルシフタと、前記バレルシフタより所定のビット位置にシフトされた１ビットを入力とする復号データ用シフトレジスタと、を有し、前記復号データ用シフトレジスタの入力ビット位置より入力符号の情報に応じた所定のビット位置までのビットの内容を変換して前記バレルシフタでの前記パスセレクト信号のシフト数を生成することを特徴とする請求項１又は請求項２記載のビタビ復号器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、畳み込み符号や受信信号の等化処理を行う最尤復号法に用いられるビタビ復号器に関する。
【背景技術】
【０００２】
この種のビタビ復号器は、誤り訂正能力が高いことから、伝送経路誤りが生じやすい衛星通信及び移動体通信等の伝送方式における復号装置及び受信装置などの情報通信システムに用いられている。
【０００３】
ビタビ復号は、受信データ系列と期待データ系列との差分（ブランチメトリック）を求める処理と、加算、比較及び選択という単純な処理（ＡＣＳ）の繰り返し処理と、最終的にデータを復号するトレースバック処理と、で復号を実現するものである。このビタビ復号では、入力ビット１ビットに対応する符号化データを得るごとに、その時刻での各状態のパスの信号間距離を計算して、生き残りパスを求めている。
【０００４】
例えば、符号化方式を畳み込み符号とする場合のビタビ復号の処理は、以下のように行われる。
【０００５】
畳み込み符号は、入力ビットと、それに先行する一定数のビットとの排他的論理和により生成され、入力ビット１ビットに対応して複数の符号化データが生成される。この符号化データに影響を与える入力ビット（情報ビット）数のことを拘束長Ｋといい、その数は排他的論理和に用いられるシフトレジスタの段数に等しい。
【０００６】
この符号化データは、入力ビットと先行する（Ｋ−１）個の入力ビットの状態とで定まる。この状態は、新たな入力ビットが入力されることによって新たな状態に遷移するが、遷移可能な状態は、新たな入力ビットが「０」であるか「１」であるかによって決定される。この状態数は、（Ｋ−１）個のビットのそれぞれが「０」又は「１」を取り得るから（２Ｋ−１）個となる。
【０００７】
ビタビ復号では、受信した符号化データ系列を観測し、取り得るすべての状態遷移の中から最も確からしい状態を推定する。そのため、このビタビ復号では、入力ビット１ビットに対応する符号化データを得るごとに、その時刻での各状態へのパスの信号間距離（メトリック）を計算し、同一状態に達するパスのうち、メトリックの小さいほうを生き残りパスとして残す。
【０００８】
図７に、拘束長Ｋの畳み込み符号器において、時刻ｔにおける状態Ｓ［２ｊ］及びＳ［２ｊ＋１］に対し、１つ前の時刻ｔ−１の状態Ｓ［ｊ］とＳ［ｊ＋ｍ／２］とからの状態遷移を表す２本のパスがそれぞれ延びている様子を示す（ここで、ｊは正整数）。
【０００９】
図７において、パスメトリックＡ１は、状態Ｓ［２ｊ］に遷移される際に出力される期待データ系列と受信データ系列との信号間距離（ブランチメトリックＢ１）と、１つ前の時刻の状態Ｓ［ｊ］までのパスメトリックＰＭ［ｊ］との和である。
【００１０】
同様に、パスメトリックＡ２は、状態Ｓ［２ｊ］に遷移される際に出力される期待データ系列と受信データ系列との信号間距離（ブランチメトリックＢ２）と、１つ前の時刻の状態Ｓ［ｊ＋ｍ／２］までのパスメトリックＰＭ［ｊ＋ｍ／２］との和である。
【００１１】
こうして求めた、状態Ｓ［２ｊ］に入力するパスメリックＡ１、Ａ２を比較し、小さいほうのパスを生き残りパスとして選択する。そして、選択したパスのパスメトリックを現時刻ｔでの状態Ｓ［２ｊ］に至るまでのパスメトリックとして、パスメトリックを更新する。
【００１２】
さらに、パスメリックＡ１又はＡ２の、どちらのパスが選択されたかという履歴を、パスセレクト信号ＰＳ［ｉ］（ｉ＝０〜２Ｋ−１−１）として残しておく。このとき選択されたパスの１つ前の状態番号が、選択されなかった他方のパスの１つ状態番号よりも小さければ、ＰＳ［ｉ］＝０とし、大きければＰＳ［ｉ］＝１とする。
【００１３】
これらの処理を、状態数×トレースバック長だけの回数行なう。そして、状態数×トレースバック長だけのパスセレクト信号と最終時刻での状態数だけのパスメトリックとを得る。その後、これらの情報よりトレースバックを行なって、符号化データを復号していく。
【００１４】
次に、トレースバック処理について図８を用いて簡単に説明する。図８は、拘束長を「３」、トレースバック長を「７」としたときの、前記状態数×トレースバック長だけの処理が終了した時点での各状態遷移の履歴を表したトレリス線図である。但し、各状態間の線上の数値は、それぞれの状態遷移におけるパスセレクト信号を表し、実線で示されたパスが生き残りパスであるとする。このトレースバック処理では、まず、最終時刻における各状態でのパスメトリックを参照して、パスメトリックが最小となる状態を選択する。但し、符号化データの入力データ列に、テールビットとして既知のデータ列が付加されている場合は、このテールビットにより示される状態を一意的に選択する（本例では、Ｓ［００］が選択されているものとしている）。次に、選択された状態の最終時刻でのパスセレクト信号より１つ前の時刻での状態へ遡る。そして、このときのパスセレクト信号を復号データとして出力する。以下同様に、単位時刻ごとに、パスセレクト信号を基に、状態（図８に太い実線で示されたパス）を遡りながら、トレースバック長だけの復号データを出力する。これにより、符号化データ列を復号することができる（本例では、１→０→１→１→０→０→０）。
【００１５】
ところで、このビタビ復号器においては、拘束長を大きくする程、その誤り訂正能力が大きくなるが、拘束長を大きくすることにより処理量が増大する。そこで、従来の情報通信システムでは、高い誤り訂正能力を必要とする情報源を送信する場合には拘束長の大きな符号化方式を用い、ある程度の誤りが許容されるような情報源を送信する場合には拘束長の短い符号化方式を用いるなどしている。しかしながら、このような方式では、１つの情報通信システムにおいて、複数種類の拘束長により符号化された信号を復号する必要がある。
【００１６】
一方、受信信号の等化処理を行なう場合には、伝送路の状況に応じて推定伝送路の係数の数を任意に変化させることで、より精度の高い等化処理を行なうことができる。しかし、このような精度の高い等化処理を行なうには、ビタビ復号器として、任意の推定伝送路の係数の数に対応することができる汎用性の高いものが求められる。
【００１７】
特に、ビタビ復号法が用いられている移動体通信分野においては、電源に電池を使用して通信端末装置の携帯性を向上させているため、その低消費電力化が必須の条件となっている。
【００１８】
このため、従来のビタビ復号器では、ブランチメトリックやパスメトリックの計算といった符号化の拘束長等によらない決まりきった処理は、専用ハード化を行なって低消費電力化を図っていた。また、パスセレクト信号からの復号や最尤判定といった拘束長により処理フローが変わるような処理は、ソフトウエアによってなされていた（例えば、特許文献１参照）。
【特許文献１】特開平１１-７４８００号公報
【発明の開示】
【発明が解決しようとする課題】
【００１９】
ところで、移動体通信分野においては、通信端末装置の連続通話時間の拡大や、携帯性を高めるための電池容量の削減などが求められている。このような低消費電力の通信端末装置を実現するためには、任意の拘束長及び任意の係数の数に対応するビタビ復号器を消費電力の少ない小さな回路規模の専用ハードウエアで構成することが望ましい。
【００２０】
しかしながら、従来のビタビ復号器においては、前述したように、ソフトウエアにより複雑な処理が行われていたため、その消費電力が大きく前記要求に応えることが難しいという問題がある。
【００２１】
本発明は、かかる点に鑑みてなされたものであり、複数種類の拘束長及び任意の推定伝送路の係数の数に対応でき、かつ、小さな回路規模の専用ハードウエアにより構成することができる汎用性の高い低消費電力のビタビ復号器を提供することを目的とする。
【課題を解決するための手段】
【００２２】
請求項１記載のビタビ復号器は、入力符号に基づいて前時刻の状態から現時刻の状態に至るすべてのパスのブランチメトリックを算出するブランチメトリック演算手段と、前記ブランチメトリック演算手段により算出された前記ブランチメトリックと与えられたパスメトリックとにより現時刻の各状態へ至るパスの中から選択した最も確実性の高いパスによって決定されるパスセレクト信号と現時刻の状態に至るまでに要したパスメトリックとを出力するＡＣＳ演算手段と、前記ＡＣＳ演算手段より出力された前記パスメトリックを記憶するパスメトリック記憶手段と、前記ＡＣＳ演算手段から出力された前記パスセレクト信号をｎステート分だけ記憶するパスセレクト信号一時記憶手段と、前記パスセレクト信号一時記憶手段に格納された前記パスセレクト信号を順に一連のトレースバック長分だけ記憶するパスセレクト信号記憶手段と、前記パスセレクト信号記憶手段に記憶された前記パスセレクト信号に基づいて復号データを生成するトレースバック処理手段と、を具備する構成を採る。
【００２３】
この構成によれば、ビタビ復号器を小さな回路規模の専用ハードウエアで構成することができ、従来のＤＳＰにて行なっていた場合に比べ低消費電力化を実現することができる。
【００２４】
請求項２に記載のビタビ復号器は、請求項１記載の発明において、前記パスセレクト信号一時記憶手段はｎビットのパスセレクト信号用シフトレジスタを有し、前記パスセレクト信号用シフトレジスタが所定のビット位置より前記パスセレクト信号を入力する構成を採る。
【００２５】
この構成によれば、請求項１記載の発明の効果に加えて、符号化において使用されている拘束長、もしくは等化処理において考えられている推定伝送路の係数の数に応じて、前記パスセレクト信号を任意のビット位置より前記パスセレクト信号用シフトレジスタに書き込むことができる。これにより、前記拘束長、もしくは前記推定伝送路の係数の数によらず、一定の形式（例えば、下位ビット詰め形式）で前記パスセレクト信号を前記パスセレクト信号記憶手段に格納できる。従って、この構成においては、前記拘束長、もしくは前記推定伝送路の係数の数に応じた特別な処理が不要となり、ソフトウエアによる余分な処理が不要となる。
【００２６】
請求項３記載のビタビ復号器は、請求項１又は請求項２記載の発明において、前記トレースバック処理手段は、前記パスセレクト信号記憶手段から読み出されたパスセレクト信号をシフトするバレルシフタと、前記バレルシフタより所定のビット位置にシフトされた１ビットを入力とする復号データ用シフトレジスタと、を有し、前記復号データ用シフトレジスタの入力ビット位置より入力符号の情報に応じた所定のビット位置までのビットの内容を変換して前記バレルシフタでの前記パスセレクト信号のシフト数を生成する構成を採る。
【００２７】
この構成によれば、請求項１又は請求項２記載の発明の効果に加えて、前記パスセレクト記憶手段から読み出されたパスセレクト信号のうち、前記入力符号の情報（符号化において使用されている拘束長、もしくは等化処理において想定されている推定伝送路の係数の数）に応じて、任意のビット位置のパスセレクト信号を取り出すことができる。そして、この取り出されたパスセレクト信号を復号データ用シフトレジスタにシフトインすることができる。これにより、任意の拘束長あるいは推定伝送路の係数の、任意の数に対応したトレースバック回路を専用ハードウエアで実現することができる。
【発明の効果】
【００２８】
以上説明したように、本発明によれば、複数種類の拘束長及び任意の推定伝送路の係数の数に対応でき、かつ、小さな回路規模の専用ハードウエアにより汎用性の高い低消費電力のビタビ復号器を構成することができる。
【発明を実施するための最良の形態】
【００２９】
本発明の骨子は、選択されたパスによって決定されるパスセレクト信号をｎスエート分だけ一時記憶し、この一時記憶したパスセレクト信号を順に一連のトレースバック長分だけ記憶したパスセレクト信号に基づいて復号データを生成することである。
【００３０】
以下、本発明の一実施の形態に係るビタビ復号器について、図面を参照して詳細に説明する。
【００３１】
（実施の形態１）
図１に、本発明の一実施の形態に係るビタビ復号器１００の構成を示す。このビタビ復号器１００は、図１に示すように、ブランチメトリック演算装置１０１、ＡＣＳ演算装置１０２、パスメトリック記憶装置１０３、パスセレクト信号一時記憶装置１０４、パスセレクト信号記憶装置１０５及びトレースバック処理装置１０６を備えている。
【００３２】
図１において、ブランチメトリック演算装置１０１は、入力される符号化データについて、前時刻の状態から現時刻の状態に至るすべてのパスについてのブランチメトリックを演算して出力する。このブランチメトリック演算装置１０１により算出されたブランチメトリック１０１ａは、ＡＣＳ演算装置１０２に出力される。
【００３３】
ＡＣＳ演算装置１０２は、ブランチメトリック演算装置１０１より出力されたブランチメトリック１０１ａと、パスメトリック記憶装置１０３から与えられたパスメトリック１０３ａとにより、各状態へ至るパスの中から最も確からしいパスを選択する。そして、このＡＣＳ演算装置１０２は、選択したパスがどの状態からのパスであるかを示すパスセレクト信号１０２ａと、現時刻における各状態に至までに要したパスメトリック１０２ｂとを出力する。
【００３４】
パスメトリック記憶装置１０３は、ＡＣＳ演算装置１０２より出力されるパスメトリック１０２ｂを状態数分だけ記憶するメモリ領域を備えており、次時刻でのＡＣＳ演算を行なう際にＡＣＳ演算装置１０２に対して入力するパスメトリック１０３ａを出力する。
【００３５】
パスセレクト信号一時記憶装置１０４は、ＡＣＳ演算装置１０２により生成されたパスセレクト信号１０２ａを、ｎステート分だけ記憶する。そして、このパスセレクト信号一時記憶装置１０４は、所用のステート分だけのパスセレクト信号が格納された後、ｍステート分（ｍ＜＝ｎ）のパスセレクト信号１０４ａを出力する。このパスセレクト信号一時記憶装置１０４は、図２に示すように、所定のビット位置より入力することを可能としたセレクタ（不図示）を備えたシフトレジスタで構成されている。このパスセレクト信号一時記憶装置１０４としてのシフトレジスタは、ビタビ復号を行なうシステムの符号化拘束長又は想定される推定伝送路の係数の数に応じて入力ビット位置を変更する。
【００３６】
図２に示すパスセレクト信号一時記憶装置１０４は、８ステート分のパスセレクト信号を記憶するシフトレジスタである。このパスセレクト信号一時記憶装置１０４は、入力ビット位置は左側のレジスタより１番目、５番目、７番目、８番目のそれぞれのビット位置からパスセレクト信号を入力できる構成となっている。例えば、拘束長が「４」の生成多項式で符号化されたシンボルをビタビ復号器により復号する場合、１シンボル当たり「８」だけのステート数がある。そして、これらのステートを、それぞれＳ[０]、Ｓ[１]、…、Ｓ[７]とし、パスセレクト信号一時記憶装置１０４の左側から１番目のレジスタよりＡＣＳ演算装置より生成された順（Ｓ[０]、Ｓ[１]、…、Ｓ[７]）にパスセレクト信号を入力する。これにより、１シンボル分のパスセレクト信号が、パスセレクト信号一時記憶装置１０４のレジスタに、Ｓ[０]、Ｓ[１]、…、Ｓ[７]のパスセレクト信号が、右側のレジスタより順にそれぞれ格納される。
【００３７】
また、このビタビ復号器１００にて拘束長３の生成多項式で符号化されたシンボルを復号する場合は、１シンボル当たり４だけのステート数がある。そして、これらのステートを、それぞれＳ[０]、Ｓ[１]、Ｓ[２]、Ｓ[３]とし、パスセレクト信号一時記憶装置１０４の左側から５番目のレジスタよりＡＣＳ演算装置より生成された順（Ｓ[０]、Ｓ[１]、Ｓ[２]、Ｓ[３]）にパスセレクト信号を入力する。これにより、１シンボル分のパスセレクト信号が、パスセレクト信号一時記憶装置１０４のレジスタに、Ｓ[０]、Ｓ[１]、Ｓ[２]、Ｓ[３]のパスセレクト信号が、右側のレジスタより順に格納される。
【００３８】
また、ＡＣＳ演算を並列に行なった場合は、同時に２つ以上のパスセレクト信号が生成される。そこで、この場合には、パスセレクト信号一時記憶装置１０４の複数ある入力ポートに同時に入力する。これにより、パスセレクト信号を記憶するために余分な処理サイクルが不要となり、一連のレジスタに所定のステートの順でパスセレクト信号を格納することができる。例えば、拘束長が「４」の生成多項式で符号化されたシンボルを、前半のステートと後半のステートとのＡＣＳ演算を２並列で復号するとする。つまり、Ｓ[０]とＳ[４]、Ｓ[１]とＳ[５]、Ｓ[２]とＳ[６]、Ｓ[３]とＳ[７]がそれぞれ同時に結果を出力するとする。この場合は、パスセレクト信号一時記憶装置１０４の左側から１番目と５番目のレジスタから同時に入力することで、４サイクルでパスセレクト信号一時記憶装置１０４のレジスタに、Ｓ[０]、Ｓ[１]、…、Ｓ[７]のパスセレクト信号が、右側のレジスタより順に格納される。同様に、拘束長が３の生成多項式で符号化されたシンボルを、前半のステートと後半のステートとのＡＣＳ演算を２並列で復号するとする。つまり、Ｓ[０]とＳ[２]、Ｓ[１]とＳ[３]がそれぞれ同時に結果を出力するとする。この場合は、パスセレクト信号一時記憶装置１０４の左側から５番目と７番目のレジスタから同時に入力することで、２サイクルで、パスセレクト信号一時記憶装置１０４のレジスタに、Ｓ[０]、Ｓ[１]、Ｓ[２]、Ｓ[３]のパスセレクト信号が、右側のレジスタより順に格納される。
【００３９】
以上のように、パスセレクト一時記憶装置１０４は、所定のビット位置より入力可能なシフトレジスタで構成されることにより、この種のシステムにおいて使用されている符号化の拘束長によらず、一定のビット位置に一定のステートにおけるパスセレクト信号を格納することができる。
【００４０】
パスセレクト信号記憶装置１０５には、パスセレクト信号一時記憶装置１０４から取り出したｎステート分のパスセレクト信号１０４ａが、一括もしくは複数回に分けて入力される。パスセレクト信号記憶装置１０５は、これらを１ワード単位として、トレースバック長分だけのパスセレクト信号を記憶する。そして、パスセレクト信号記憶装置１０５は、トレースバック処理装置１０６に、制御回路（不図示）より指定されたアドレスのパスセレクト信号１０５ａを１ワード単位で出力する。
【００４１】
トレースバック処理装置１０６は、図３に示すように、パスセレクト信号記憶装置１０５より読み出された１ワード単位分のパスセレクト信号１０５ａを、シフトするためのバレルシフタ（ＢＳＨＴ）３０１を備えている。また、トレースバック処理装置１０６は、バレルシフタ３０１より所定のビット位置へシフトとされたビットを入力とする復号データ用シフトレジスタ３０２を備えている。さらに、この復号データ用シフトレジスタ３０２の入力ビット位置より入力符号の情報に応じた所定のビット位置までのビットの内容をデコードするデコーダ３０３を備えている。
【００４２】
トレースバック処理は、ある１つの受信シンボルにおける全ステートのパスセレクト信号のうち、ある１つのステートのパスセレクト信号を選択することで復号を行なっている。このため、このトレースバック処理においては、符号化を行なった際の拘束長や、等化処理を行なう際の想定している推定伝送路の係数の数によって、ステートの数が異なってくる。
【００４３】
そこで、このトレースバック処理装置１０６では、全ステートのパスセレクト信号のうち、ある１つのステートのパスセレクト信号を選択するためのバレルシフタ３０１の制御信号３０１ａを、デコーダ３０３で生成するようにしている。つまり、トレースバック処理装置１０６は、デコーダ３０３により、入力符号の情報に応じて復号データ用シフトレジスタ３０２の入力ビット位置より所定のビット位置までのビットの内容をデコードするように構成されている。これにより、拘束長や推定伝送路の係数の数が変化した場合においても、ソフトウエアによる余分な処理を必要とすることなく、トレースバック処理による復号が可能となった。
【００４４】
次に、前述のビタビ復号器１００の動作について、図４及び図５に示すフローチャートを用いて説明する。但し、以下の説明では、受信シンボルが、畳み込み符号によって符号化されているものとする。
【００４５】
図４に示すように、ビタビ復号器１００は、まず、ＳＴ４０１において、時刻ｔでの符号化データを受信する。
【００４６】
ビタビ復号器１００が受信した符号化データは、ブランチメトリック演算装置１０１に入力される。そして、ステップＳＴ４０２において、状態番号Ｎでの受信期待値と受信した符号化データ系列のハミング距離あるいはユークリッド距離を求めることにより、時刻ｔにおける状態番号Ｎでのブランチメトリック１０１ａを計算する。
【００４７】
ここで、状態番号Ｎにおける受信期待値は、例えば、受信した符号化データが、図６に示すような畳み込み符号器６００によって符号化されたものである場合、その状態番号Ｎは畳み込み符号器のシフトレジスタ６０１に保持されている値によって決定されるものである。そして、その符号化出力系列６０２は、畳み込み符号器６００のシフトレジスタ６０１に保持されている値と、畳み込み符号器６００への符号化入力６０３を排他的論理和ゲート６０４ａ〜６０４ｃによって演算された値として求められたものである。このブランチメトリックの算出においては、受信期待値の生成を複数の状態に対して同時に行なうことで、ブランチメトリックを複数の状態番号もしくは畳み込み符号器６００への符号化入力６０３の値が異なった場合に対して同時に算出することも可能である。
【００４８】
次いで、ステップＳＴ４０３においては、図７に示したようなバタフライ演算を行ない、ＡＣＳ演算を実行する。つまり、ステップＳＴ４０３では、時刻（ｔ−１）から時刻ｔに遷移する際の、時刻ｔおける状態番号Ｎに遷移しうる時刻（ｔ−１）での２つの状態でのパスメトリックと、ステップＳＴ４０２において求められた時刻ｔでの状態番号ＮでのブランチメトリックよりＡＣＳ演算を行い、パスメトリックとパスセレクト信号を出力する。このようにステップＳＴ４０３では、生き残りパスを選択し、どちらのパスが選択されたかを示すパスセレクト信号１０２ａと、時刻ｔでの状態番号Ｎでのパスメトリック１０２ｂとを出力する。このパスセレクト信号とパスメトリックとの算出においては、ＡＣＳ演算装置を複数個備えることで２つ以上の状態番号に対して同時に算出することが可能である。
【００４９】
次いで、ステップＳＴ４０４においては、ステップＳＴ４０３において算出されたパスメトリック１０２ｂを、時刻ｔにおける状態番号Ｎでのパスメトリックとして、パスメトリック記憶装置１０３に記憶しておく。
【００５０】
次に、ステップＳＴ４０５においては、ステップＳＴ４０３において算出されたパスセレクト信号をパスセレクト信号一時記憶装置１０４のシフトレジスタに格納する。このとき、符号化を行なった際の拘束長に応じて、パスセレクト信号一時記憶装置１０４へ入力するビット位置を変更する。これにより、システムにおいて使用されている符号化の拘束長によらず、一定のビット位置に一定のステートにおけるパスセレクト信号が格納することができる。但し、ステップＳＴ４０４とステップＳＴ４０５とについては順不同である。
【００５１】
次いで、ステップＳＴ４０６においては、時刻ｔでの全状態について終了と判断されるまで、ステップＳＴ４０２からＳＴ４０５までの処理が繰り返される。
【００５２】
次いで、ステップＳＴ４０７においては、トレースバック長のデータ受信終了ｔ＝ｔと判断されるまで、ステップＳＴ４０２からＳＴ４０６までの処理が繰り返される。
【００５３】
次いで、図５に示すように、ステップＳＴ４０８からＳＴ４１０においては、トレースバック開始状態番号が一意的に決められているかどうかを判断し、各状態のパスメトリックを参照してトレースバック開始状態番号を決定する。ここで、符号化データにテールビット等の既知のビットが存在する場合は、これらのビットによりトレースバック開始状態番号が決められるのでステップＳＴ４１０に進み、トレースバック開始状態番号を決定する。符号化データにテールビット等の既知のビットが存在しない場合はステップＳＴ４０９に進み、パスメトリック記憶装置１０３に記憶されている各状態におけるパスメトリックを参照し、トレースバック開始状態番号を決定する。
【００５４】
次いで、ステップＳＴ４１１においては、パスセレクト信号記憶装置１０５に記憶されている時刻ｔのパスセレクト信号を読み出し、トレース開始位置に応じてその内容をバレルシフタによりシフトさせる。つまり、受信した最終時刻のシンボルにおけるパスセレクト信号をパスセレクト信号記憶装置１０５から読み出して、この内容をトレースバック開始位置に応じてバレルシフタによりシフトさせ、所定のビット位置のビットを得る。
【００５５】
次いで、ステップＳＴ４１２においては、ステップＳＴ４１１において得られたバレルシフタの出力（シフト結果）を、復号データ用シフトレジスタに代入する。
【００５６】
次いで、ステップＳＴ４１３及びＳＴ４１４においては、先ほど読み出したパスセレクト信号が生成されたときから１時刻前のパスセレクト信号を、パスセレクト信号記憶装置１０５から読み出す。そして、このパスセレクト信号を、復号データ用シフトレジスタのうち符号化の拘束長に応じたビット位置までの内容に従って、バレルシフタによりシフトさせる。これによって、複数種類の拘束長に対応したビタビ復号におけるトレースバック処理が、ハードウエアによって実現される。
【００５７】
次いで、ステップＳＴ４１５において、ｔ＝０であると判断されるまで、ＳＴ４１２からＳＴ４１４の動作が繰り返される。そして、受信したすべてのシンボル、もしくはトレースバック長だけのシンボルのトレースバック処理が終了することで、ビタビ復号が終了する。
【００５８】
このように、本発明の一実施の形態に係るビタビ復号器１００によれば、拘束長や推定伝送路の係数の数が変化した場合においても、ソフトウエアによる余分な処理を必要とすることなく、トレースバック処理による復号をすることができる。
【産業上の利用可能性】
【００５９】
本発明に係るビタビ復号器は、複数種類の拘束長及び任意の推定伝送路の係数の数に対応でき、かつ、小さな回路規模の専用ハードウエアにより汎用性が高く低消費電力に構成することができるので、畳み込み符号や受信信号の等化処理を行う最尤復号法に用いられるビタビ復号器等として有用である。
【図面の簡単な説明】
【００６０】
【図１】本発明の一実施の形態に係るビタビ符号器の構成を示すブロック図
【図２】本発明の一実施の形態に係るビタビ復号器におけるパスセレクト信号一時記憶装置の構成を示すブロック図
【図３】本発明の一実施の形態に係るビタビ復号器におけるトレースバック処理装置の構成を示すブロック図
【図４】本発明の一実施の形態に係るビタビ復号器におけるビタビ復号の動作を説明するための一部のフローチャート
【図５】本発明の一実施の形態に係るビタビ復号器におけるビタビ復号の動作を説明するための他の部のフローチャート
【図６】畳み込み符号方式による符号化回路の一例を示す回路図
【図７】ビタビ復号器における符号の状態遷移のパスを示す状態遷移図
【図８】ビタビ復号器における符号の状態遷移の一例を示すトレリス線図
【符号の説明】
【００６１】
１００  本発明のビタビ復号器本体
１０１  ブランチメトリック演算装置
１０１ａ  現時刻でのブランチメトリック
１０２  ＡＣＳ演算装置
１０２ａ  現時刻でのパスセレクト信号
１０２ｂ  現時刻でのパスメトリック
１０３  パスメトリック記憶装置
１０３ａ  前時刻でのパスメトリック
１０４  パスセレクト信号一時記憶装置
１０４ａ  ｎステート分のパスセレクト信号
１０５  パスセレクト信号記憶装置
１０５ａ  パスセレクト信号記憶装置より読み出されたパスセレクト信号
１０６  トレースバック処理装置
１０６ａ  トレースバック処理により復号されたデータ
３０１  バレルシフタ
３０２  復号データ用シフトレジスタ
３０３  デコーダ
６００  畳み込み符号器
６０１  シフトレジスタ
【図１】
2005045727.tif 000003
【図２】
2005045727.tif 000004
【図３】
2005045727.tif 000005
【図４】
2005045727.tif 000006
【図５】
2005045727.tif 000007
【図６】
2005045727.tif 000008
【図７】
2005045727.tif 000009
【図８】
2005045727.tif 000010