(57)【要約】  プログラマブルプロセッサを使用して、ハードウェアチャネルエンコーダを用いて得られるコードと同一のコードを計算するチャネル符号化方法を提供する。  この方法は、それぞれのメモリアドレスで第１部分系のすべての可能な結果を格納している、第１の事前に計算されたルックアップテーブルにて、入力されたビットの値から決定されるメモリアドレスで、シフトされたビット間の並列ＸＯＲ演算の第１部分系の結果を読み取る第１ステップ（１１２、１２０；２２２）と、少なくとも、プログラマブルプロセッサのＸＯＲ命令を使用することによって読み取られた結果と並列ＸＯＲ演算の第２部分系の結果との間のＸＯＲ演算を実行するステップ（１１６、１２４；２２６）とを含む。
2008527878.tif 000002
【特許請求の範囲】
【請求項１】
プログラマブルプロセッサを使用して、ハードウェアチャネルエンコーダを用いて得られるコードと同一のコードを計算するチャネル符号化方法であって、前記チャネルエンコーダは、
入力されたビット集合を１ビットだけシフトするシフトレジスタと、
前記シフトされたビット間でＸＯＲ演算を実行するＸＯＲゲートと
を備え、前記プログラマブルプロセッサは、ＸＯＲ命令に応じてＸＯＲ演算を実行可能とし、
それぞれのメモリアドレスで第１部分系のすべての可能な結果を格納している第１の事前に計算されたルックアップテーブルにて、前記入力されたビットの値から決定されるメモリアドレスで、シフトされたビット間の並列ＸＯＲ演算の第１部分系の結果を読み取る第１ステップと、
少なくとも、前記プログラマブルプロセッサのＸＯＲ命令を使用することによって前記読み取られた結果と並列ＸＯＲ演算の第２部分系の結果との間のＸＯＲ演算を実行するステップと
を含む方法。
【請求項２】
それぞれのメモリアドレスで前記第２部分系のすべての可能な結果を記録している第２の事前に計算されたルックアップテーブルにて、前記第２部分系の前記結果を前記入力されたビットの値から決定されるアドレスで読み取る第２ステップを含む、請求項１に記載の方法。
【請求項３】
前記第１および第２の読取ステップの際に使用される前記メモリアドレスを、入力された２つの連続するビット集合の値のみから決定し、ハードウェア畳込みエンコーダを用いて得られるコードと同一のコードを計算する、請求項２に記載の方法。
【請求項４】
前記シフトレジスタに格納される前記ビット集合は、残余と呼ばれ、前記読取ステップのうちの１つの読取ステップの際に使用される前記メモリアドレスを、前記残余の現在の値のみから決定し、少なくともフィードバックチェーンを有するハードウェアチャネルエンコーダを用いて得られるコードと同一のコードを計算する、請求項３に記載の方法。
【請求項５】
前記ハードウェアチャネルエンコーダは、ＸＯＲ演算によってお互いにリンクされたＰ個の変数間でＮ個の関係を有するＸＯＲ演算の系に対応し、各関係は、前記コードの１ビットの値を提供するように構成され、各部分系は、前記個数Ｐより厳密に少ない個数の変数を含む、前記系の一部に対応している、前記請求項のいずれか一項に記載の方法。
【請求項６】
前記チャネルエンコーダは、
ビットを出力する少なくとも２つの順方向チェーンと、
各順方向チェーンの出力の多重化動作を実行するマルチプレクサと
を備え、前記ルックアップテーブルの各々に記録されている前記結果を、前記多重化動作にも利用し、ハードウェアチャネルエンコーダを用いて得られるコードと同一のコードを計算する、前記請求項のいずれか一項に記載の方法。
【請求項７】
命令がプログラマブルプロセッサによって実行される時に、前記請求項のいずれか一項に記載のチャネル符号化方法を実行する前記命令を含むメモリ。
【請求項８】
命令がプログラマブルプロセッサによって実行される時に、請求項１から６のいずれか一項に記載のチャネル符号化方法を実行する前記命令を含むマイクロプロセッサプログラム。
【請求項９】
請求項１から６のいずれか一項に記載のチャネル符号化方法を実行するように適合されたチャネルエンコーダであって、
ＸＯＲ命令に応じてＸＯＲ演算を実行するように適合されたプログラマブルプロセッサと、
前記プロセッサに接続されたメモリと
を備え、前記メモリは、前記第１部分系の前記結果を格納している前記第１の事前に計算されたルックアップテーブルを含み、前記プロセッサは、前記第１の事前に計算されたルックアップテーブル内の前記第１部分系の前記結果を読み取り、前記プログラマブルプロセッサの前記ＸＯＲ命令を使用して、前記読み取られた結果とＸＯＲ演算の前記第２部分系の前記結果との間でＸＯＲ演算を実行するように適合されているチャネルエンコーダ。
【請求項１０】
前記メモリは、前記第２部分系の前記結果を格納している前記第２の事前に計算されたルックアップテーブルを含み、前記プロセッサは、前記第２の事前に計算されたルックアップテーブル内で前記第２部分系の前記結果を読み取るように適合されている、請求項９に記載のチャネルエンコーダ。
【請求項１１】
請求項９または１０に記載のチャネルエンコーダを備えているユーザ機器。
【請求項１２】
請求項９または１０に記載のチャネルエンコーダを備えている基地局。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、チャネル符号化に関する。
【背景技術】
【０００２】
ハードウェアチャネルエンコーダは、コードを生成するために次の要素を備えることができる。
入力されたビット集合を１ビットだけシフトするシフトレジスタと、
シフトされたビット間でＸＯＲ演算を実行するＸＯＲゲート。
【０００３】
そのようなハードウェアチャネルエンコーダを用いて得られるコードと同一のコードを計算する、いくつかのチャネル符号化方法が、プログラマブルプロセッサを用いて実施される。これらの方法は、入力されたビット集合から決定されるメモリアドレスで１つの事前に計算されたルックアップテーブル内のコードを読み取る。
【０００４】
このルックアップテーブルのサイズは、２ｎ＋ｋに比例し、ｎは、並列に処理される、入力されたビットの個数であり、ｋは、拘束長としても知られる整数である。
【０００５】
たとえば、ＷＯ  ０３／５２９９７（ＨＵＲＴ  Ｊａｍｅｓ  Ｙ他による）に、そのような方法が開示されている。
【０００６】
このルックアップテーブルのサイズは、重要であり、したがって、この方法は、大きいメモリ空間を必要とし、この大きいメモリ空間は、携帯電話機などのポータブルユーザ機器では必ずしも使用可能ではない。
【特許文献１】ＷＯ  ０３／５２９９７
【発明の開示】
【発明が解決しようとする課題】
【０００７】
したがって、本発明の目的は、プログラマブルプロセッサを用いて実施されるように構成した、より少ないメモリ空間を必要とするチャネル符号化方法を提供することにある。
【課題を解決するための手段】
【０００８】
本発明は、ＸＯＲ命令に応じてＸＯＲ演算を実行できるプログラマブルプロセッサを用いて実施されるように構成したチャネル符号化方法であって、
それぞれのメモリアドレスで第１部分系のすべての可能な結果を格納している第１の事前に計算されたルックアップテーブルにて、入力されたビットの値から決定されるメモリアドレスで、シフトされたビット間の並列ＸＯＲ演算の第１部分系の結果を読み取る第１ステップと、
少なくとも、プログラマブルプロセッサのＸＯＲ命令を使用することによって該読み取られた結果と並列ＸＯＲ演算の第２部分系の結果との間のＸＯＲ演算を実行するステップと
を含む方法を提供する。
【０００９】
上述の方法は、ルックアップテーブルを使用することによるＸＯＲ演算およびＸＯＲ命令を使用することによるＸＯＲ演算の計算を混合する。したがって、一方では、ルックアップテーブルのサイズが、ＸＯＲ命令を使用しない従来のチャネル符号化方法によるものより小さくなる。その一方で、コードを計算するのに使用されるＸＯＲ命令の個数は、ルックアップテーブルを使用しないチャネル符号化方法によるものより少なくなる。その結果、この方法は、わずかなメモリ空間を有するポータブルユーザ機器または基地局で実施するのに好適である。
【００１０】
請求項２の特徴は、プロセッサによって実行される演算の数を減らす。
【００１１】
請求項３の特徴は、プログラマブルプロセッサで畳込み符号化方法を実施するのに必要なメモリ空間を減らす。
【００１２】
請求項４の特徴は、少なくともフィードバックチェーンを有するハードウェアチャネルエンコーダ、たとえばターボエンコーダに対応する符号化方法を実施するのに必要なメモリ空間を減らす。
【００１３】
請求項５の特徴は、プログラマブルプロセッサでチャネル符号化方法を実施するのに必要なメモリ空間を減らす。
【００１４】
請求項６の特徴は、多重化演算を実行する必要がないので、プロセッサによって実行される演算の数を減らす。
【００１５】
本発明は、上述のチャネル符号化方法を実行するメモリおよびプロセッサプログラム、ならびにこの方法を実施するチャネルエンコーダ、ユーザ機器、および基地局にも関する。
【００１６】
本発明の上記および他の態様は、以下の説明、図面、および特許請求の範囲から明白になる。
【発明を実施するための最良の形態】
【００１７】
図１に、ハードウェアターボエンコーダ２を示す。図を単純にするために、本発明を理解するのに必要な詳細だけが、図１に示されている。
【００１８】
エンコーダ２の要素に関するさらなる詳細は、３ＧＰＰ（３ｒｄ  Ｇｅｎｅｒａｔｉｏｎ  Ｐａｒｔｎｅｒｓｈｉｐ  Ｐｒｏｊｅｃｔ）ＵＴＲＡ  ＴＤＤ／ＦＤＤおよび３ＧＰＰ２  ＣＤＭＡ２０００などの３Ｇ無線標準規格で見つけることができる。
【００１９】
すべてのチャネルエンコーダと同様に、ターボエンコーダ２は、入力されたビットストリーム内に冗長性を追加するように構成される。たとえば、エンコーダ２は、入力されたビットストリームのビットｄｉごとに３つのビットＸ［ｉ］、Ｚ［ｉ］、およびＺ’［ｉ］を出力する。インデックスｉは、ビットｄｉがエンコーダ２に入力される瞬間を表す。インデックスｉは、最初のビットｄ０が入力される時に０と等しく、新しいビットが入力されるたびに１つ増分される。通常、ビットｄｉがエンコーダ２に入力される瞬間は、クロック信号の立ち上がりエッジに対応する。
【００２０】
エンコーダ２は、２つの同一の左フィードバックシフトレジスタ４および６と１つのインターリーバ１０とを有する。
【００２１】
シフトレジスタ４は、直列に接続された４つのメモリ要素１４から１７を含む。メモリ要素１４は、新しいビットｄｉを受け取るために入力部２２に接続され、メモリ要素１７は、出力部２４に接続される。出力部２４は、２つのＸＯＲゲート２６および２８の第１入力部に接続される。ＸＯＲゲート２６の第２入力部は、ＸＯＲゲート３０の出力部に接続される。
【００２２】
ＸＯＲゲート２８の第２入力部は、メモリ要素１６の出力部に接続される。
【００２３】
ＸＯＲゲート２６の出力部は、ビットＺ［ｉ］を出力する端子３２に接続される。
【００２４】
ＸＯＲゲート２８の出力部は、ＸＯＲゲート３４の第１入力部に接続される。ＸＯＲゲート３４の第２入力部は、２位置スイッチ３６を介してメモリ要素１４の出力部に接続される。
【００２５】
ＸＯＲゲート３４の出力部は、メモリ要素１５の入力部と、ＸＯＲゲート３０の第２入力部とに接続される。
【００２６】
第１位置で、スイッチ３６は、メモリ要素１４の出力部をＸＯＲゲート３４の第２入力部に接続する。
【００２７】
第２位置で、スイッチ３６は、ＸＯＲゲート２８の出力部をＸＯＲゲート３４の第２入力部に接続する。
【００２８】
スイッチ３６は、入力されたビットストリームの終りを符号化するためにのみ第２位置にシフトされる。この接続は、破線で表されている。
【００２９】
ＸＯＲゲート３４の第２入力部は、ビットＸ［ｉ］を出力する端子４０にも接続される。
【００３０】
各メモリ要素は、１ビットを格納し、各瞬間ｉにこのビットを次のメモリ要素にシフトすることを意図されている。
【００３１】
残余ｒのビットｒ４［ｉ］、ｒ３［ｉ］、ｒ２［ｉ］、およびｒ１［ｉ］の値は、シフトレジスタ４に格納される。
【００３２】
ビットｒ４［ｉ］、ｒ３［ｉ］、ｒ２［ｉ］、およびｒ１［ｉ］の値は、それぞれ、メモリ要素１５、１６、および１７の入力の信号の値ならびにメモリ要素１７の出力の信号の値と等しい。残余値は、入力されたビットｄｉの値ならびに以前のビットｒ４［Ｉ−１］、ｒ３［Ｉ−１］、ｒ２［Ｉ−１］、およびｒ１［Ｉ−１］の値の関数である。
【００３３】
シフトレジスタ６も、直列に接続された４つのメモリ要素５０〜５３を含む。お互いへのメモリ要素５０〜５３の接続は、メモリ要素１４〜１７の接続と同一であり、詳細には説明しない。メモリ要素５０〜５３の間の接続も、それぞれＸＯＲゲート２６、２８、３０、および３４とスイッチ３６とに対応する、４つのＸＯＲゲート５６、５８、６０、および６４と１つのスイッチ６６とを使用する。
【００３４】
シフトレジスタ６は、２つの端子７０および７２に接続される。端子７０は、ビットＺ’［ｉ］を出力するためにＸＯＲゲート５６の出力部に接続される。端子７２は、ビットストリームの符号化の終りにビットＸ’［ｉ］を出力するために、ＸＯＲゲート５８の出力部に接続される。この接続は、破線で表されている。
【００３５】
残余ｒ’のビットｒ’４［ｉ］、ｒ’３［ｉ］、ｒ’２［ｉ］、およびｒ’１［ｉ］の組は、シフトレジスタ６に格納される。
【００３６】
ビットｒ’４［ｉ］、ｒ’３［ｉ］、ｒ’２［ｉ］、およびｒ’１［ｉ］の値は、メモリ要素５１、５２、および５３の入力の信号の値ならびにメモリ要素５３の出力の信号の値と等しい。残余ｒ’の値は、入力されたビットｅｉの値ならびに以前のビットｒ’４［Ｉ−１］、ｒ’３［Ｉ−１］、ｒ’２［Ｉ−１］、およびｒ’１［Ｉ−１］の値の関数である。
【００３７】
メモリ要素５０は、ビットｅｉを受け取る入力部６５を有する。
【００３８】
インターリーバ１０は、入力部２２に接続された入力部と、入力部６５に接続された出力部とを有する。インターリーバ１０は、入力されたビットストリームからのビットｄｉを混合し、ビットｅｉから作られた、混合されたビットストリームを出力する。
【００３９】
図２および３に、エンコーダ２の詳細を示す。図２および３では、図１に既に示された要素が、同一の符号を有する。
【００４０】
図２に、エンコーダ２の順方向チェーンを示す。この順方向チェーンは、ＸＯＲゲート２６および３０を含む。この順方向チェーンの瞬間ｉの出力ビットＺ［ｉ］は、次の関係を用いて計算することができる。
【００４１】
【数１】
2008527878.tif 000003
ここで、記号
【００４２】
【数２】
2008527878.tif 000004
は、ＸＯＲ演算である。
【００４３】
図３に、エンコーダ２のフィードバックチェーンを詳細に示す。図示のフィードバックチェーンは、ＸＯＲゲート２８および３４を含む。このフィードバックチェーンは、次の関係に対応する。
【００４４】
【数３】
2008527878.tif 000005
【００４５】
次の関係をも、エンコーダ２の概略図から導出することができる。
ｒ３［ｉ］＝ｒ４［ｉ−１］
ｒ２［ｉ］＝ｒ３［ｉ−１］                        （３）
ｒ１［ｉ］＝ｒ２［ｉ−１］
【００４６】
並列ＸＯＲ演算の次の系Ｚは、５つの連続する出力ビットＺ［ｉ］からＺ［ｉ＋４］を並列に計算するために、関係（１）から導出される。
【００４７】
【数４】
2008527878.tif 000006
関係（２）および（３）を使用すると、次のように、瞬間ｉの残余ｒのビットだけを使用して系Ｚを記述することが可能である。
【００４８】
【数５】
2008527878.tif 000007
【００４９】
したがって、関係（５）に従って、ビットＺ［ｉ］からＺ［ｉ＋４］を、ビット集合［ｄｉ−１，…，ｄｉ＋３］ならびに瞬間ｉのビットｒ１［ｉ］、ｒ２［ｉ］、およびｒ３［ｉ］の値から計算することができる。
【００５０】
瞬間ｉのビットｒ１［ｉ］、ｒ２［ｉ］、およびｒ３［ｉ］の値から瞬間ｉ＋５のビットｒ１［Ｉ＋５］、ｒ２［Ｉ＋５］、およびｒ３［Ｉ＋５］の値を並列に計算する系ｒ［ｉ＋５］は、関係（２）および（３）から導出することができる。系ｒ［ｉ＋５］は、次の通りである。
【００５１】
【数６】
2008527878.tif 000008
【００５２】
図１の概略図から、ビットＸ［ｉ］からＸ［ｉ＋４］を並列に計算する系Ｘを、次のように記述することができる。
【００５３】
【数７】
2008527878.tif 000009
【００５４】
同様に、ビットＺ’［ｉ］からＺ’［ｉ＋４］を、ビット集合｛ｅｉ−１；…；ｅｉ＋３｝の値ならびにビットｒ’１［ｉ］、ｒ’２［ｉ］、およびｒ’３［ｉ］の値から並列に計算する並列ＸＯＲ演算の系Ｚ’を、図１から導出することができる。系Ｚ’は、次の通りである。
【００５５】
【数８】
2008527878.tif 000010
同様に、ビットｒ’１［ｉ＋５］、ｒ’２［ｉ＋５］、およびｒ’３［ｉ＋５］を並列に計算する並列ＸＯＲ演算の系ｒ’［ｉ＋５］が、図１から導出される。系ｒ’［ｉ＋５］は、次の通りである。
【００５６】
【数９】
2008527878.tif 000011
【００５７】
系Ｚを、ビット集合｛ｄｉ−１；…；ｄｉ＋３｝のすべての可能な値ならびにビット値ｒ１［ｉ］、ｒ２［ｉ］、およびｒ３［ｉ］について事前に計算することができ、その結果を、ルックアップテーブルＺに格納することができる。したがって、ルックアップテーブルＺは、２８×５ビットを含む。同様に、系ｒ［ｉ＋５］の結果、系Ｚ’の結果、および系ｒ’［ｉ＋５］の結果を、入力されたすべての可能なビット集合およびすべての可能な残余値について事前に計算することができる。その結果、系Ｚ、系ｒ［ｉ＋５］、系Ｚ’、および系ｒ’［ｉ＋５］のルックアップテーブルを使用するターボ符号化方法の実施は、２８×５＋２８×３＋２８×５＋２８×３ビットを格納するメモリを必要とする。
【００５８】
系Ｘの結果は、受け取られたビットｄｉから直接に読み取ることができる。
【００５９】
このメモリ空間は、携帯電話機などのユーザ機器にこれらのルックアップテーブルを格納するには大きすぎる。この説明の次の部分では、これらのルックアップテーブルのサイズを減らすことがどのようにして可能であるかを説明する。
【００６０】
ＸＯＲ演算は可換なので、系Ｚを、次のように２つの部分系ＺＰおよびＲｅに分割することができる。
【００６１】
【数１０】
2008527878.tif 000012
ここで、
【００６２】
【数１１】
2008527878.tif 000013
である。
【００６３】
部分系ＺＰの値は、ビット集合｛ｄｉ−１；…；ｄｉ＋３｝の値だけを使用して前もって計算することができ、部分系Ｒｅは、残余ｒ［ｉ］の値だけを使用して計算することができる。したがって、ビット集合｛ｄｉ−１；…；ｄｉ＋３｝のすべての可能な値に関する部分系ＺＰのすべての結果を含むルックアップテーブルＺＰは、２５×５ビットだけを含む。部分系ＺＰの各結果は、ビット集合｛ｄｉ−１；…；ｄｉ＋３｝の値から決定されるそれぞれのメモリアドレスで格納される。
【００６４】
残余ｒ［ｉ］のすべての可能な値に対する部分系Ｒｅの結果を含むルックアップテーブルＲｅは、２３×５ビットだけを格納する。テーブルＲｅでは、部分系Ｒｅの各結果が、ビットｒ１［ｉ］、ｒ２［ｉ］、およびｒ３［ｉ］の値から決定されるそれぞれのメモリアドレスで格納される。
【００６５】
したがって、ルックアップテーブルＺではなく２つのルックアップテーブルＺＰおよびＲｅを使用することによって、ターボ符号化方法を実施するのに必要なメモリ空間が減る。
【００６６】
同様に、系Ｚ’の結果を、次の関係を使用して２つの部分系ＺＰ’およびＲｅ’の結果から計算することができる。
【００６７】
【数１２】
2008527878.tif 000014
ここで、
【００６８】
【数１３】
2008527878.tif 000015
【００６９】
【数１４】
2008527878.tif 000016
である。
【００７０】
ビット集合｛ｅｉ−１；…；ｅｉ＋３｝の値ごとの系ＺＰ’の事前に計算された結果が、ルックアップテーブルＺＰ’に格納され、残余ｒ’［ｉ］のすべての可能な値に関する部分系Ｒｅ’の結果が、ルックアップテーブルＲｅ’に格納される。
【００７１】
ビットＸ［ｉ］からＸ［ｉ＋４］の値は、ビット集合｛ｄｉ−１；…；ｄｉ＋３｝の値から読み取られる。
【００７２】
図４に、プログラマブルマイクロプロセッサ９２およびメモリ９４を有するチャネルエンコーダ９１を含むユーザ機器９０を示す。
【００７３】
ユーザ機器９０は、たとえば、携帯電話機である。
【００７４】
マイクロプロセッサ９２は、ビットｄｉのストリームを受け取る入力部９６と、ターボ符号化されたビットストリームを出力する出力部９８とを有する。
【００７５】
メモリ９４は、ルックアップテーブルＺＰ、Ｒｅ、ｒ［ｉ＋５］、ＺＰ’、およびＲｅ’を格納する。ルックアップテーブルｒ’［ｉ＋５］は、ルックアップテーブルｒ［ｉ＋５］と同一であり、この最後のルックアップテーブルだけが、メモリ９４に格納される。
【００７６】
マイクロプロセッサ９２は、たとえばメモリ９４に格納された、マイクロプロセッサプログラム１００を実行するように適合される。プログラム１００は、図５のターボ符号化方法の実行のための命令を含む。プロセッサ９２は、メモリ９４に格納されたＸＯＲ命令に応じてＸＯＲ演算を実行するように適合される。
【００７７】
プロセッサ９２の動作を、これから図５を参照して説明する。
【００７８】
まず、残余ｒおよびｒ’のすべてが、ヌルである。
【００７９】
ステップ１１０で、プロセッサ９２は、第１ビット集合｛ｄ０；…；ｄ４｝を受け取る。次に、ステップ１１２で、プロセッサ９２は、ビット値Ｘ［１］からＸ［５］と、ビット集合｛ｄ０；…；ｄ４｝の値から決定されるメモリアドレスでルックアップテーブルＺＰ内のビット値ＺＰ［１］からＺＰ［５］とを並列に読み取る。
【００８０】
ステップ１１４で、プロセッサ９２は、ビットｒ３［１］、ｒ２［１］、およびｒ１［１］の値（すべてがヌルである）から決定されるメモリアドレスでルックアップテーブルＲｅ内のビットＲｅ［１］からＲｅ［５］をも並列に読み取る。
【００８１】
その後、ステップ１１６で、プロセッサ９２は、ステップ１１２で読み取られた部分系ＺＰの結果とステップ１１４で読み取られた部分系Ｒｅの結果との間のＸＯＲ演算を実行して、関係（１０）に従ってビットＺ［１］からＺ［５］の値を得る。
【００８２】
ステップ１１２〜１１６と並行に、ステップ１１８で、プロセッサ９２は、受け取ったビットをインターリーブして、インターリーブされたビットストリームｅｉを生成する。
【００８３】
その後、ステップ１２０で、ビットＺＰ’［１］からＺＰ’［５］の値を、ルックアップテーブルＺＰ’にて、ビット集合｛ｅ０；…；ｅ４｝の値から決定されるメモリアドレスで並列に読み取る。
【００８４】
ステップ１２２で、プロセッサ９２は、ビットｒ’３［１］、ｒ’２［１］、およびｒ’１［１］の値（すべてがヌルである）を使用して、ルックアップテーブルＲｅ’内のビットＲｅ’［１］からＲｅ’［４］の値を並列に読み取る。次に、ステップ１２４で、プロセッサ９２は、ステップ１２０で読み取られた結果とステップ１２２で読み取られた結果との間のＸＯＲ演算を実行して、関係（１３）に従ってビットＺ’［１］からＺ’［５］の値を得る。
【００８５】
ビットＸ［１］からＸ［５］、Ｚ［１］からＺ［５］、およびＺ’［１］からＺ’［５］の値がわかったならば、ステップ１３０で、プロセッサ９２は、これらのビット値を組み合わせて、出力部９８を介して出力されるターボ符号化されたビットストリームを生成する。ターボ符号化されたビットストリームは、次の順序Ｘ［ｉ］、Ｚ［ｉ］、Ｚ’［ｉ］、Ｘ［ｉ＋１］、Ｚ［ｉ＋１］、Ｚ’［ｉ＋１］、…などでのビット値を含む。
【００８６】
その後、ステップ１３２で、プロセッサ９２は、ルックアップテーブルｒ［ｉ＋５］内で、ステップ１１４および１２２の次の反復に必要な残余ｒおよびｒ’の値を読み取る。より正確に言うと、動作１３４中に、プロセッサ９２は、ルックアップテーブルｒ［ｉ＋５］にて、ビットｒ３［１］、ｒ２［１］、およびｒ１［１］ならびにビットｄ０からｄ４の値から決定されるメモリアドレスで、ビットｒ１［６］、ｒ２［６］、およびｒ３［６］の値を並列に読み取る。動作１３６で、マイクロプロセッサ９２は、ルックアップテーブルｒ［ｉ＋５］にて、ビットｒ’３［１］、ｒ’２［１］、およびｒ’１［１］の値によって決定されるメモリアドレスで、ステップ１２２の次の反復に必要なビットｒ’１［６］、ｒ’２［６］、およびｒ’３［６］の次の値を並列に読み取る。
【００８７】
その後、マイクロプロセッサ９２は、ステップ１１０に戻って、入力されたビットストリームの次の５つのビットｄｉを受け取る。
【００８８】
その後、ステップ１１２から１３２が、受け取られた新しいビット集合ならびに残余ｒおよびｒ’の計算された新しい値を使用して繰り返される。
【００８９】
図５の方法は、マイクロプロセッサ９２などのプログラマブルマイクロプロセッサで実施される時に、ハードウェアターボエンコーダ２によって生成されるものと同一のターボ符号化されたビットストリームを計算することを可能にする。
【００９０】
図６に、ハードウェアチャネルエンコーダのもう１つの例である、ハードウェア畳込みエンコーダ１５０を示す。より正確に言うと、エンコーダ１５０は、１／２のレートを有する畳込みエンコーダである。１／２のレートは、入力されたビットストリームのビットｄｉごとに、エンコーダ１５０が、符号化されたビットストリームの２ビットを生成することを意味する。
【００９１】
図６には、本発明を理解するのに必要な詳細だけが示されている。そのような畳込みエンコーダに関するさらなる詳細は、前述で引用した３ＧＰＰ  ＵＴＲＡ  ＴＤＤ／ＦＤＤおよび３ＧＰＰ２  ＣＤＭＡ２０００などの３Ｇ無線標準規格で見つけることができる。
【００９２】
エンコーダ１５０は、直列に接続された９つのメモリ要素１５４から１６２を有するシフトレジスタ１５２を含む。要素１５４は、符号化される入力ビットストリームのビットｄｉを受け取る入力部１６６を有する。
【００９３】
エンコーダ１５０は、２つの順方向チェーンを有する。第１の順方向チェーンは、ＸＯＲゲート１７０、１７２、１７４、および１７６を使用して構成され、瞬間ｉにビットＤ１［ｉ］を出力する。
【００９４】
ＸＯＲゲート１７０は、メモリ要素１５４の出力部に接続された１つの入力部と、メモリ要素１５６の出力部に接続された第２の入力部とを有する。ＸＯＲゲート１７０は、ＸＯＲゲート１７２の第１入力部に接続された出力部をも有する。ＸＯＲゲート１７２の第２入力部は、メモリ要素１５６の出力部に接続される。ＸＯＲゲート１７２の出力部は、ＸＯＲゲート１７４の第１入力部に接続される。ＸＯＲゲート１７４の第２入力部は、メモリ要素１５８の出力部に接続される。ＸＯＲゲート１７４の出力部は、ＸＯＲゲート１７６の第１入力部に接続される。ＸＯＲゲート１７６の第２入力部は、メモリ要素１６２の出力部に接続される。ＸＯＲゲート１７６の出力部は、ビットＤ１［ｉ］を出力し、マルチプレクサ１８０の第１入力部に接続される。
【００９５】
第２順方向チェーンは、ＸＯＲゲート１８２、１８４、１８６、１８８、１９０、および１９２を使用して構成される。
【００９６】
ＸＯＲゲート１８２は、メモリ要素１５４および１５５の出力部にそれぞれ接続された２つの入力部を有する。
【００９７】
ＸＯＲゲート１８４は、ＸＯＲゲート１８２の出力部およびメモリ要素１５６の出力部にそれぞれ接続された２つの入力部を有する。
【００９８】
ＸＯＲゲート１８６は、ＸＯＲゲート１８４の出力部およびメモリ要素１５７の出力部にそれぞれ接続された２つの入力部を有する。
【００９９】
ＸＯＲゲート１８８は、ＸＯＲゲート１８６の出力部およびメモリ要素１５９の出力部にそれぞれ接続された２つの入力部を有する。
【０１００】
ＸＯＲゲート１９０は、ＸＯＲゲート１８８の出力部およびメモリ要素１６１の出力部にそれぞれ接続された２つの入力部を有する。
【０１０１】
ＸＯＲゲート１９２は、ＸＯＲゲート１９０の出力部およびメモリ要素１６２の出力部にそれぞれ接続された２つの入力部を有する。ＸＯＲゲート１９２は、ビットＤ２［ｉ］を生成する出力部をも有し、この出力部は、マルチプレクサ１８０の第２入力部に接続される。
【０１０２】
マルチプレクサ１８０は、その入力部で並列に受け取ったビットＤ１［ｉ］およびＤ２［ｉ］をシリアルビットストリームに変換し、２つの順方向チェーンによって生成されたビットＤ１［ｉ］およびＤ２［ｉ］を交番させる。
【０１０３】
符号化された出力ビットストリームの１６個の連続する出力ビットを、次の系Ｄを使用して、並列に計算することができる。
【０１０４】
【数１５】
2008527878.tif 000017
【０１０５】
系Ｄは、符号化された出力ビットストリームの１６個の連続するビットのブロックを、ビット集合｛ｄｉ；…；ｄｉ＋１５｝の値から計算できることを示す。系Ｄが、マルチプレクサ１８０の多重化動作を実行することに留意されたい。ビット集合｛ｄｉ；…；ｄｉ＋１５｝のすべての可能な値について系Ｄの結果を事前に計算し、各結果を、入力されるビット集合｛ｄｉ；…；ｄｉ＋１５｝の値から決定されるメモリアドレスで、ルックアップテーブルＤに記録することも可能である。ルックアップテーブルＤは、２１６×１６ビットを含む。系Ｄを使用して畳込み符号化方法を実施するのに使用されるメモリ空間は、次のように系Ｄを２つの部分系ＤＰ１およびＤＰ２に分割することによって減らすことができる。
【０１０６】
【数１６】
2008527878.tif 000018
ここで、
【０１０７】
【数１７】
2008527878.tif 000019
である。
【０１０８】
部分系ＤＰ１の結果を、ビット集合｛ｄｉ；…；ｄｉ＋７｝の値ごとに事前に計算することができる。部分系ＤＰ１の事前計算の各結果は、ルックアップテーブルＤＰ１に、ビット集合｛ｄｉ；…；ｄ７｝の対応する値から決定されるアドレスで格納される。ルックアップテーブルＤＰ１は、２８×１６ビットだけを含む。
【０１０９】
同様に、部分系ＤＰ２の各結果を、ルックアップテーブルＤＰ２に、ビット集合｛ｄｉ＋８；…；ｄｉ＋１５｝の対応する値から決定されるメモリアドレスで格納することができる。
【０１１０】
したがって、ルックアップテーブルＤではなくルックアップテーブルＤＰ１およびＤＰ２を使用して畳込み符号化方法を実施することによって、この実施に必要なメモリ空間が減る。
【０１１１】
図７に、メモリ２０４に接続されたプログラマブルマイクロプロセッサ２０２を有する畳込みエンコーダ２０１を含むユーザ機器２００を示す。
【０１１２】
たとえば、ユーザ機器２００は、携帯電話機である。
【０１１３】
マイクロプロセッサ２０２は、符号化されるビットストリームを受け取る入力部２０６と、符号化されたビットストリームを出力する出力部２０８とを有する。
【０１１４】
プロセッサ２０２は、メモリ、たとえばメモリ２０４に格納されている命令を実行する。プロセッサ２０２は、ＸＯＲ命令に応じてＸＯＲ演算を実行するように適合もされる。
【０１１５】
メモリ２０４は、プロセッサ２０２によって実行された時に図８の方法を実行する命令を有するマイクロプロセッサプログラム２１０を格納している。メモリ２０４は、ルックアップテーブルＤＰ１およびＤＰ２も格納している。
【０１１６】
マイクロプロセッサ２０２の動作を、これから図８を参照して説明する。
【０１１７】
まず、ステップ２２０で、マイクロプロセッサ２０２は、新しいビット集合｛ｄｉ；…；ｄｉ＋１５｝を受け取る。次に、ステップ２２２で、マイクロプロセッサ２０２は、ルックアップテーブルＤＰ１内で、ビット集合｛ｄｉ；…；ｄｉ＋７｝の値によってのみ決定されるメモリアドレスでビットＤＰ１［ｉ］からＤＰ１［ｉ＋１５］の値を並列に読み取る。
【０１１８】
その後、ステップ２２４で、マイクロプロセッサ２０２は、ルックアップテーブルＤＰ２内で、ビット集合｛ｄｉ＋８；…；ｄｉ＋１５｝の値によってのみ決定されるメモリアドレスでビットＤＰ２［ｉ］からＤＰ２［ｉ＋１５］の値を並列に読み取る。
【０１１９】
その後、ステップ２２６で、マイクロプロセッサ２０２は、部分系ＤＰ１の結果と部分系ＤＰ２の結果との間でＸＯＲ演算を実行して、関係（１７）に従ってビットＤ１［ｉ］からＤ１［ｉ＋７］およびＤ２［ｉ］からＤ２［ｉ＋７］を計算する。
【０１２０】
ステップ２２８で、符号化されたビットを、出力部２０８を介して出力する。
【０１２１】
その後、ステップ２２２〜２２８を、次のビット集合｛ｄｉ＋８；…；ｄｉ＋２３｝について繰り返す。
【０１２２】
多数の追加の実施例が可能である。たとえば、図４の実施例で、ルックアップテーブルＺＰ’を取り消すことができる。実際に、ビットＺ［ｉ］からＺ［ｉ＋４］に関する限り、ルックアップテーブルＺＰとＺＰ’は同一なので、部分系ＺＰ’の結果を、ルックアップテーブルＺＰから読み取ることができる。同様に、ルックアップテーブルＲｅとＲｅ’は同一なので、図４の実施例のルックアップテーブルＲｅ’が、取り消され、ビットＲ’ｅ［ｉ］からＲ’ｅ［ｉ＋４］の値は、ルックアップテーブルＲｅから読み取られる。これによって、ターボ符号化方法を実施するのに必要なメモリ空間が、さらに減る。
【０１２３】
各部分系ｒ［ｉ＋５］またはｒ’［ｉ＋５］を、２つの部分系に分割することができ、第１部分系の値は、ビット集合｛ｄｉ−１；…；ｄｉ＋３｝または｛ｉｅｉ−１；…；ｅｉ＋３｝の値だけに依存し、第２部分系の値は、残余ｒ［ｉ］またはｒ’［ｉ］の値だけに依存するものとできる。
【０１２４】
上述のチャネル符号化方法を実施するのに必要なメモリ空間は、部分系のうちの少なくとも１つを少なくとも２つの部分系に分割することによって、さらに減らすことができる。たとえば、部分系ＤＰ１を、次の関係に従って２つの部分系ＤＰ１１およびＤＰ１２に分割することができる。
【０１２５】
【数１８】
2008527878.tif 000020
ここで、
【０１２６】
【数１９】
2008527878.tif 000021
である。
【０１２７】
記号φは、関係（２０）によるＸＯＲ演算の実行中に、ＤＰ１１とＤＰ１２の対応するビット間でＸＯＲ演算を実行してはならないことを意味する。
【０１２８】
部分系ＤＰ１１およびＤＰ１２を、それぞれビット集合｛ｄｉ；…；ｄｉ＋３｝および｛ｄｉ＋４；…；ｄｉ＋７｝の値ごとに事前に計算することができ、その結果を、ルックアップテーブルＤＰ１１およびＤＰ１２に格納することができる。ルックアップテーブルＤＰ１１およびＤＰ１２は、それぞれ２４×８ビットおよび２４×１６ビットを格納する。したがって、ルックアップテーブルＤＰ１１およびルックアップテーブルＤＰ１２に格納されるビットの総数は、ルックアップテーブルＤＰ１に格納されるビットの個数より少ない。
【０１２９】
部分系ＤＰ１およびルックアップテーブルＤＰ１のこの特定の事例で示されたものは、部分系ＤＰ１１など、上述した部分系のいずれにも適用することができる。上述のチャネルを符号化する方法の１つを実施するのに必要な、より小さいメモリ空間は、各系が一連の部分系に分割された時に達成され、これらの部分系の各々の値は、２ビットの組の値だけに依存する。しかし、この場合では、符号化されたビットストリームを得るために、各部分系の結果の間で大量のＸＯＲ演算を実行する必要がある。実際に、プロセッサによって実行される演算の数は、使用されるルックアップテーブルの個数に比例して増加する。
【０１３０】
ターボ符号化の終りに、スイッチ３６および６６は、それぞれＸＯＲゲート２８および５８の出力部をＸＯＲゲート３４および６４の第２入力部に接続するように切り替えられる。このエンコーダ２の構成を、並列ＸＯＲ演算の系を使用してモデル化し、マイクロプロセッサ９２上で利用することができる。好ましくは、ターボ符号化の終りの実施は、上述した方法を使用してモデル化した系全体に対応するルックアップテーブルより小さい複数のルックアップテーブルを使用して実行される。
【０１３１】
上述した方法は、シフトレジスタおよびＸＯＲゲートを有するハードウェア実施例に対応するすべてのチャネルエンコーダに適用される。上述した方法は、たとえばＷＭＡＮ（無線メトロポリタンエリアネットワーク）または無線通信の他の標準規格など、他の標準規格で使用されるすべてのチャネルエンコーダにも適用される。
【０１３２】
チャネル符号化方法を、５ビットのブロックがこの方法の各反復でプロセッサに入力される特定の事例で説明した。この方法は、入力されるビットブロックの他のサイズ、たとえば、８ビット、１６ビット、または３２ビットを有するブロックに一般化することができる。
【０１３３】
上述のチャネル符号化方法は、すべてのタイプのユーザ機器内ならびに基地局内で実施することができる。
【図面の簡単な説明】
【０１３４】
【図１】ハードウェアターボエンコーダを示す概略図である。
【図２】図１のターボエンコーダの順方向チェーンを示す概略図である。
【図３】図１のターボエンコーダのフィードバックチェーンを示す概略図である。
【図４】チャネル符号化方法を実行するプログラマブルプロセッサを有するユーザ機器を示す概略図である。
【図５】図４のユーザ機器で実施されるチャネル符号化方法を示すフローチャートである。
【図６】ハードウェア畳込みエンコーダを示す概略図である。
【図７】畳込み符号化方法を実行するプログラマブルプロセッサを有するユーザ機器を示す概略図である。
【図８】図７のユーザ機器で実施される畳込み符号化方法を示すフローチャートである。
【図１】
2008527878.tif 000022
【図２】
2008527878.tif 000023
【図３】
2008527878.tif 000024
【図４】
2008527878.tif 000025
【図５】
2008527878.tif 000026
【図６】
2008527878.tif 000027
【図７】
2008527878.tif 000028
【図８】
2008527878.tif 000029
【国際調査報告】
2008527878.tif 000030
2008527878.tif 000031