(57)【特許請求の範囲】
【請求項１】
後退帰納の次状態を生成するための方法であって：
後退帰納プロセスの現状態を決定する段階であって、前記現状態は、複数のビットによって定義される、段階；
仮設化情報ビットを受信する段階；および
次状態後退帰納プロセスのための次状態を決定するために、前記複数のビットおよび前記仮設化情報ビットを線形に合成する段階であって、前記線形に合成する段階は、現状態後退帰納レジスタ内の全ビットを前記仮設化情報ビットと線形に合成し、次状態後退帰納レジスタの最上位ビット（ＭＳＢ）を生成する段階；
前記現状態後退帰納レジスタ内のビットをシフトし、前記次状態後退帰納レジスタの残余のビットを求める段階；
によって構成されることを特徴とする方法。
【請求項２】
前記後退帰納プロセスが、現状態後退帰納レジスタ内の全ビットを線形に合成して、次状態後退帰納レジスタの最上位ビット（MSB）を生成する段階を含むことを特徴とする請求項１記載の方法。
【請求項３】
前記現状態後退帰納レジスタ内の全バイナリ・デジットを線形に合成する段階がモジューロ２によって前記バイナリ・デジットのすべてを線形に合成する段階を含むことを特徴とする請求項２記載の方法。
【請求項４】
前記後退帰納プロセスを実行する前記段階が、前記現状態後退帰納レジスタ内のビットをシフトして、前記次状態後退帰納レジスタの残りのビットを求める段階をさらに含むことを特徴とする請求項２記載の方法。
【請求項５】
次後退帰納状態に関して第１論理レベルにある前記仮説化情報ビットに基づき前記仮説化情報ビットに関する推移量を決定する段階；
次後退帰納状態にある前記次状態に関して前記第１レベルにある前記仮説化情報ビットに基づき前記仮説化情報ビットの後退状態量を決定する段階；
前記推移量と前記後退状態量とを格納する段階；
第２論理レベルにある前記仮説化情報ビットに基づき推移量を決定し、かつ後退状態量を決定する段階を反復する段階；
前記推移量，前進状態量および後退状態量を合成する段階；および
前記第１論理レベルがエンコード済み情報ビットの実際の論理レベルである尤度値を更新する段階；
を含むことを特徴とする請求項４記載の方法。
【請求項６】
現状態後退帰納レジスタ；
前記現状態後退帰納レジスタから次状態後退帰納レジスタの最下位ビットとして複数の最上位ビットを受信するために動作状態に結合される前記次状態帰納レジスタ；および
前記現状態後退帰納レジスタの段に動作状態に結合され、仮説化情報ビットを受信するために動作状態に結合される入力と、現状態後退帰納レジスタ内の全ビットと前記仮設化情報ビットとの線形合成に基づいて、前記次状態後退帰納レジスタの最上位ビットを出力するために動作状態に結合される出力とを有する加算器；
によって構成されることを特徴とする後退帰納の次状態生成装置。
【請求項７】
前記加算器がモジューロ２加算器であることを特徴とする請求項６記載の装置。
【請求項８】
前記加算器が、前記現状態後退帰納レジスタから前記複数の最上ビットの各々に関連する多項式関数係数を受信することを特徴とする請求項６記載の装置。
【請求項９】
前記現状態後退帰納レジスタと前記次状態後退帰納レジスタとがその内容を書き換えられた同一のレジスタであることを特徴とする請求項６記載の装置。
【発明の詳細な説明】
【０００１】
【発明の分野】
本発明は、一般に畳込デコーダに関し、さらに詳しくは、ソフト・デシジョン出力デコーダなどの前進後退帰納を伴う畳込デコーダおよび方法に関する。
【０００２】
【発明の背景】
帰納最大値(MAP: maximum a posteriori)デコーダなどのソフト・デシジョン出力デコーダは、畳込符号と共に用いて、ワイヤレス通信リンク上に通信される音声，映像，データまたはその他の情報などの被送信情報を表す記号を解読することが知られる。前進後退帰納を伴う畳込デコーダは周知のものであり、ときに、ターボ・コードで用いられる構成帰納畳込符号を解読するために利用される。このようなデコーダは、MAPアルゴリズムの１つの経路から得られるソフト・デシジョン情報をMAPアルゴリズムの次の経路への入力として用いて、被解読記号から判断して被送信情報データの最良の推定値を求める帰納解読を実行する。当技術で周知の如く、MAPアルゴリズムにおいては、前進帰納により時刻ｔにおける状態と時刻ｔを通じて受信されるデータの同時確率（joint probability）を評価する。後退帰納は、時刻の状態が与えられると、時刻ｔからフレーム終点までに受信されるデータの確率を計算する。このため、後退帰納デコーダに関するこの確率の計算は、フレームの終点から始まるのが普通である。MAPデコーダは、たとえば１９７４年３月発行のL.R. Bahel他著「Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate」（IEEE Transactions on Information Theory）と題される論文に解説される。このMAPデコーダの用途の１つを、本明細書に参考文献として含まれる１９９３年５月発行のC.Berrou他著「Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes」（Proceedings of ICC '93, スイス，ジュネーブpp.1064-1070）に見ることができる。
【０００３】
たとえば、符号分割多重接続（CDMA：code division multiple access）ワイヤレス通信システムなどにおける場合のターボ・コードの解読に関して、帰納畳込符号化される情報ビットの解読には、現在の状態と仮説情報ビットなどの入力ビットが与えられ、トレリス内の次の状態を判断することが求められる。MAPアルゴリズムなどの解読アルゴリズムには、前進方向だけでなく後退方向にもトレリスを更新するものがあるので、現在の状態（ｎにおける）と入力ビットが与えられた、コーダ（エンコーダ）の次の状態（前進帰納については時刻n+1の状態で、後退帰納については時刻n-1の状態）を判断することが必要になる。この演算は、通常、トレリス内の各状態に関して実行されるので、効率的にこのプロセスを実行することが重要である。
【０００４】
次式で定義されるＭ要素シフト・レジスタの現在の状態σn
【０００５】
【数１】
0004844949.tif 000002
【０００６】
と、入力ビットunが与えられると、前進帰納の次の状態は：
【０００７】
【数２】
0004844949.tif 000003
【０００８】
を与えるようにシフト・レジスタをクロックすることで容易に計算することができる。ただし、帰還ビットfnは帰還多項式grに指定されるシフト・レジスタ要素のモジューロ２加算に定義される。
より難しい問題は、σnとunが与えられて、後退帰納の次状態であるσn-1を見つけることである。ただし：
【０００９】
【数３】
0004844949.tif 000004
【００１０】
解決策の１つとして、各状態の次状態と入力ビットを与えるルックアップ・テーブルを利用する方法がある。このためには、Mビット・ルックアップ・テーブルにより予め計算される2M+1が必要である。しかし、このようなルックアップ・テーブルは、乏しいメモリを利用して、ルックアップ・テーブルを作成するために複雑性が増すことになる。
【００１１】
したがって、このようなルックアップ・テーブルを用いることを避けることのできる、より効率的な帰納畳込デコーダが必要である。
【００１２】
【好適な実施例の説明】
帰納畳込記号を解読する方法および装置は、帰納畳込的に生成される記号に関して前進帰納プロセスを実行し、この記号に関して後退帰納を実行する。このとき、後退帰納プロセスに関する次状態が後退帰納プロセスの現状態を定義する複数のビットと仮説化される情報ビットの両方を線形に合成することに基づいて決まる。ある実施例では、後退帰納プロセスは、現状態後退帰納シフト・レジスタ内のすべてのバイナリ・ビットを線形に合成して、次状態後退帰納シフト・レジスタの最上位ビット（MSB：most significant bit）を生成する。次状態後退帰納シフト・レジスタの現在の残りのビットを求めるために、現状態後退帰納シフト・レジスタ内のビットがシフトされる。シフトされたビットは、次状態後退帰納シフト・レジスタ内で最下位ビットとして働く。従って、適切な線形合成とビット・シフトの手法を用いて、次状態後退帰納シフト・レジスタの内容を判断する。この演算は、マイクロプロセッサ，デジタル信号プロセッサ，ソフトウェア，ハードウェア，これらを任意に適切に組み合わせたもの、あるいは他の適切な任意のメカニズムにより実行することができる。
【００１３】
図１は、MAPデコーダ１００などの帰納畳込解読装置を示す。この装置は、エンコードされた情報ビットを表す帰納畳込的に生成される記号１０２を受信し、被推定バイナリ情報ビット１０４のシーケンスを出力する。MAPデコーダ１００は、当技術で周知の適切なスケーラ１０６を備えることがある。スケーラ１０６は、記号の受信されエンコードされたシーケンスを測定し、所望の場合は、尤度比を記録する。これらは、記号１０８の記録尤度比として示される。MAPデコーダ１００は、前進および後退帰納解読プロセス１１４，１１６を備え、これらはたとえば構成DSPや他の任意の適切なメカニズムにより実行される。MAPデコーダ１００は、後退帰納プロセス１１４に関する状態移行判断を行う後退状態判断装置２００を備える。バイナリ・スライサ１０５が、情報ビット１０３の記録尤度比を被推定バイナリ情報ビットに変換する。スライサ１０５の被推定バイナリ情報ビット１０４のシーケンスは、順次、ボコーダまたは他の任意の適切な装置またはプロセスに通信される。
【００１４】
MAPデコーダ１００は、帰納畳込的に生成される記号１０２に関して従来の前進帰納を実行する。これは、当技術では周知の適切な前進帰納プロセス１１６に関する前進状態判断プロセスを用いて実行することができる。前進状態決定プロセス１１０および前進帰納プロセス１１６は、適切なDSPまたは他の装置上で実行することができる。また、MAPデコーダ１００は、後退帰納デコーダの次状態が後退帰納プロセスの現状態を定義する複数のビットと仮説化情報ビットunの両方を線形に合成することにより決まる後退帰納プロセスを実行する。
【００１５】
図２および図３を参照して、帰納畳込解読の方法を説明する。図３については、前進機能プロセスが当技術で周知の如く終了していることを前提とする。ブロック３００に示すように、プロセスは、後退帰納プロセスの現状態を表すビットまたは値を求める段階と、現状態後退帰納レジスタ２０２の格納要素に現状態を格納する段階とを含む。ブロック３０２に示すように、プロセスは、仮説化情報ビット２１２，unを論理０に設定する段階を含む。ブロック３０４に示すように、本方法は、現状態後退帰納レジスタ２０２内の全ビットを線形に合成して、次状態後退帰納レジスタ２０４の最上位ビット２１０を生成する段階を含む。ブロック３０６に示すように、本方法は、現状態後退帰納レジスタ２０２の内容を１ビットだけ左にシフトさせて、次状態後退帰納レジスタ２０４の残りの下位ビット２０８ａ〜２０８ｎを求める段階を含む。
【００１６】
次状態後退帰納レジスタ２０４の内容を求めると、現状態から次状態への推移量が決定される（たとえば計算される）。これは、たとえば、本明細書に参考文献として含まれる１９７４年３月IEEE Transactions on Information Theory 発行、L.R. Bahl他著「Optimum Decoding of Linear codes for Minimizing Symgol Error Rate」と題される論文に述べられるように実行される。たとえば、仮説化情報ビットの推移量は、次の後退帰納状態に関する第１論理レベルにある仮説化情報ビットに基づく。
【００１７】
ブロック３１０に示すように、本方法は、論理「０」などの第１論理レベルにある仮説化情報ビット２１２に基づいて仮説化情報ビットの後退状態量を決定する段階も含む。これは、たとえば、１９７４年３月IEEE Transactions on Information Theory 発行、L.R. Bahl他著「Optimum Decoding of Linear codes for Minimizing Symgol Error Rate」と題される論文に述べられるように実行される。
【００１８】
ブロック３１２に示すように、本方法は後退状態量をメモリに格納する段階を含む。ブロック３１４に示すように、解読プロセスは推移量，前進状態量および後退状態量を当技術で周知の方法により加算し、「０」が仮説化情報ビット２１２unの実際の値である尤度値を適切に更新する段階を含む。このように、推移量，前進状態量および後退状態量は当技術で周知の方法で適切に合成される。ブロック３１６に示すように、プロセスは論理「１」状態など第２状態に設定される仮説化情報ビット２１２unについて反復される。ブロック３１８に示すように、ブロック３０４ないし３１６の段階は、すべてのトレリス状態に関して繰り返され、情報ビットの状態の尤度を決定する。従って、プロセスは、第１論理値（たとえば論理「０」）が当初エンコードされた情報ビットに関連する実際の論理レベルである尤度値を更新する段階を含む。
【００１９】
図２は、後退状態決定装置２００の一例を示す。これは、MAPデコーダ１００の一部である場合もある。後退状態決定装置２００は、適切にプログラミングされたDSP，マイクロプロセッサ，離散論理または他の任意の適切な装置またはソフトウェア上に実行される後退帰納プロセス１１４において用いられる。この例では、後退状態決定装置２００は、現状態後退帰納レジスタ２０２，次状態後退帰納レジスタ２０４および加算器２０６を具備する。加算器２０６はモジューロ２加算器である。これらの要素が、任意の適切な方法で機能し実行されることは言うまでもない。たとえば、現状態後退帰納レジスタ２０２と次状態後退帰納レジスタ２０４とは、その内容が適切に書き換えられた同一のレジスタでもよい。後退帰納デコーダの次状態は、現状態後退帰納レジスタ２０２の内容を線形に合成して決定される。次状態後退帰納レジスタ２０４は、最下位ビット（LSB）２０８ａ〜２０８ｎと同様、現状態後退帰納レジスタ２０２から複数の最上位ビット２０７ａ〜２０７ｎを受信するよう、動作状態で結合される。そのため、次状態後退帰納レジスタ２０４の最下位ビットは、現状態後退帰納レジスタ２０２の最上位ビットから求められる。最上位ビット２１０レジスタ要素として示される次状態後退帰納レジスタ２０４の次状態の最上位ビットを得るために、加算器２０６は現状態後退帰納レジスタ２０２のレジスタ要素を仮説化情報ビット２１２unと線形に合成して、次状態後退帰納レジスタ２０４の最上位ビット（MSB）２１０を導く。また、図示される如く、生成元多項式関数係数２１４ａ〜２１４ｎは、当技術で周知の要領で用いられて、結合性を示す。
【００２０】
後退状態決定装置２００は、ハードウェア，ソフトウェア，シフト・レジスタおよび加算器を用いて構築するものとして図示されるが、任意の適切なハードウェア，ソフトウェアまたはそれらの組み合わせを用いることができることは言うまでもない。
【００２１】
図示される如く、加算器２０６は現状態後退帰納レジスタ２０２から最上位ビット２０７ａ〜２０７ｎの各々と関連する多項式関数係数２１４ａ〜２１４ｎを受信する。従って、後退状態決定装置２００は、以下の公式に従い、最上位ビット２１０を生成する：
【００２２】
【数４】
0004844949.tif 000005
【００２３】
図４および図５を参照して、３要素デコーダの例を用いて、本発明の動作を説明する。この例では、情報ビットは、畳込帰納コーダを用いてエンコードされる。このコーダは、たとえば、長さＭ＝３（Ｍはレジスタ内の格納要素数）を有するTIA/EIA IS-2000Aに記述される種類のものである。さらに、帰還多項式は係数（ｇ0f，ｇ1f，ｇ2f）＝（０，１，１）を有する。後退状態決定装置４００は、現状態後退帰納レジスタ４０２とモジューロ加算器４０４とを用いて、後退帰納プロセスの現状態から後退帰納プロセスの次状態を導き、次状態レジスタ４０６に移植する。たとえば、現状態（σ0n，σ1n，σ2n）＝（１，０，１）の次状態（σ0n-1，σ1n-1，σ2n-1）は、入力un＝０に関して（０，１，０）であり、入力un＝１に関して（０，１，１）である。この例の状態移行４０８の完全な集合を図５に示す。従って、後退帰納の現状態の要素の適切な合成を用いて、ルックアップ・テーブル・メモリを必要とせずに後退帰納の次状態に関する内容を直接的に得ることができる。
【００２４】
種々の側面における本発明の他の変形および修正の実行例が、当業者に明白であろうことと、本発明は開示される特定の実施例に制約されないことは言うまでもない。従って、本明細書に開示され請求される基本的な基礎原理の精神および範囲に入る任意のすべての修正，変形または等価物は本発明に包含されるものである。
【図面の簡単な説明】
【図１】  本発明のある実施例によるデコーダの一例を示すブロック図である。
【図２】  本発明のある実施例による後退状態決定装置を示すブロック図である。
【図３】  図２に示す後退状態決定装置の動作の一例を示す流れ図である。
【図４】  本発明のある実施例による後退状態決定装置の一例を示すブロック図である。
【図５】  本発明のある実施例によるデコーダに供給される後退状態決定装置の潜在的状態を示すトレリス図である。
【図１】
0004844949.tif 000006
【図２】
0004844949.tif 000007
【図３】
0004844949.tif 000008
【図４】
0004844949.tif 000009
【図５】
0004844949.tif 000010