(57)【要約】本発明は、予め決められた数のクロック・サイクルのうちにデータを計算する能力を有する少なくとも１つの計算装置（３１）によって計算された第１のデータ・セットに基づいて第２のデータ・セットを計算するための回路に関する。この計算装置は入力（３１１）および出力（３１２）を有する。この回路は、第１のデータ・セットのデータ数およびデータの計算に必要な予め決められたサイクル数に応じたクロック・サイクル数において、第１のデータ・セットのデータを計算装置の出力から入力へルーティングするための移送手段（３２）を含む。データは、前記移送手段の中を１クロック・サイクルごとに前進する。
2006500850.tif 000002
【特許請求の範囲】
【請求項１】
予め決められた数のクロック・サイクルのうちにデータを計算する能力を有し、入力および出力を有する少なくとも１つの計算装置によって計算された第１のデータ・セットに基づいて第２のデータ・セットを計算するための回路であって、前記第１のデータ・セットのデータ数およびデータの計算に必要な前記予め決められたサイクル数に応じたクロック・サイクル数にて、前記第１のデータ・セットのデータを前記計算装置の前記出力から前記入力へルーティングするための移送手段を含み、前記移送手段を介してデータが１クロック・サイクルごとに前進することを特徴とする回路。
【請求項２】
前記移送手段が、前記計算装置の前記出力から前記入力へデータを移送するために必要なサイクル数を調整するための調整手段を含むことを特徴とする、請求項１に記載の回路。
【請求項３】
前記移送手段が、１クロック・サイクルごとに新しいデータを記憶する能力を有する、クロックによって活性化する少なくとも１つのレジスタを含むことを特徴とする、請求項１または２に記載の回路。
【請求項４】
インタリーバの列内置換要素を計算するためのシステムであって、請求項１に記載の回路を含むシステム。
【請求項５】
請求項４に記載のシステムを含む復号回路。
【請求項６】
請求項５に記載の復号回路を含む電子装置。
【請求項７】
信号を送信する能力を有する少なくとも１つの送信機と、伝送路と、前記信号を受信する能力を有する受信機と、請求項５に記載の復号回路とを含む通信ネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、予め決められた数のクロック・サイクルのうちにデータを計算する能力を有し、入力および出力を有する少なくとも１つの計算装置によって計算された第１のデータ・セットに基づいて第２のデータ・セットを計算するための回路に関する。
【０００２】
本発明はさらに、インタリーバの列内置換要素を計算するためのシステム、このようなシステムを含む復号回路、このような復号回路を含む電子装置および通信ネットワークに関する。
【０００３】
本発明は、例えば衛星通信システム、第３世代携帯電話などのＵＭＴＳ規格（UMTS=Universal Mobile Telecommunication System）を実装したシステムに応用することができる。
【背景技術】
【０００４】
ある種のデータ処理システムは、別のデータ・セットに基づいてデータ・セットを計算する必要があるデータの再帰計算を実行する。例えばデータｂｊ［ｉ］の計算を実行することができる。ただしｉおよびｊは添字、ｉは０からｎまで、ｊは０からｍまでの間を変化し、ｍおよびｎはゼロでない整数である。これは特にベキ行列（power matrix）の計算の場合に当てはまる。
【０００５】
図１に、このような処理システムによって計算されるデータの一例を示す。この例では整数ｍの値が９、整数ｎの値が４である。５つのデータ・セットｂ０［０］からｂ９［０］、ｂ０［１］からｂ９［１］、ｂ０［２］からｂ９［２］、ｂ０［３］からｂ９［３］、およびｂ０［４］からｂ９［４］が計算される。処理システムはデータｂ０［０］からｂ９［０］をそれぞれ計算し、次いでｂ０［１］からｂ９［１］を計算し、以下同様に順次計算する。データ・セットは１つ前のデータ・セットに左右される。例えばｂ０［１］は関数ｆによるｂ０［０］の関数である。
【０００６】
ｂ０［１］＝ｆ（ｂ０［０］）
同様にｂ１［１］＝ｆ（ｂ１［０］）、ｂ２［１］＝ｆ（ｂ２［０］）、．．．である。一般化すると以下のようになる。
【０００７】
ｂｊ［ｉ＋１］＝ｆ（ｂｊ［ｉ］）
図２に、このような計算を実行することができる回路を示す。このような回路はメモリ２１、制御装置２２および計算装置２３を含む。以下の例では、第１のデータ・セットｂ０［１］〜ｂ９［１］に基づく第２のデータ・セットｂ０［２］〜ｂ９［２］の計算を説明する。この例では、計算装置２３によって１つのデータを計算するのに１クロック・サイクルを要する。第１のデータ・セットｂ０［１］〜ｂ９［１］のデータはメモリ２１に記憶されている。１クロック・サイクルの間にデータｂ０［１］が計算装置２３に送られ、次いで計算装置２３がデータｂ０［２］を計算する。このデータは次いでメモリ２１に記憶される。次のクロック・サイクルではデータｂ１［１］が計算装置２３に送られ、次いで計算装置２３がデータｂ１［２］を計算する。このデータは次いでメモリ２１に記憶される。同様にしてこの回路はデータｂ２［２］〜ｂ９［２］の計算を続ける。
【０００８】
制御装置２２は、第２のデータ・セットのデータを計算するための計算装置２３への第１のデータ・セットのデータの送信を制御する。これを実行するため、制御装置２２は、第１のデータ・セットの前記データが記憶されているメモリ２１のアドレスを生成する。メモリ２１はＲＡＭメモリ（RAM=Random Access Memory）である。制御装置２２からアドレスを受け取るとメモリ２１は、そのアドレスに記憶されているデータを計算装置２３に送る。
【０００９】
したがってこのような回路はランダム・アクセス・メモリおよび制御装置を必要とする。このようなメモリおよび制御装置はかなりの面積のシリコン表面を覆い、かなりの量の電流を消費する。このことは特に携帯電話などの携帯型電子装置の場合に障害になる。実際、携帯型電子装置において使用可能なシリコン表面は限られている。さらに、このような装置はバッテリから給電されるので、前記バッテリの頻繁な再充電を回避するために、電流消費が少ないことは重要である。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明の目的は、第１のデータ・セットに基づいて第２のデータ・セットを計算するための回路であって、小さなシリコン表面を占有し、電流消費の少ない回路を提案することにある。
【課題を解決するための手段】
【００１１】
冒頭の段落で定義した本発明に基づく回路は、第１のデータ・セットのデータ数およびデータの計算に必要な予め決められたサイクル数に応じたクロック・サイクルの数にて、第１のデータ・セットのデータを計算装置の出力から入力へルーティングするための移送手段を含み、前記移送手段の中をデータが１クロック・サイクルごとに前進することを特徴とする。
【００１２】
計算装置によって第１のデータ・セットのデータが計算され、数クロック・サイクル後に、第２のデータ・セットのデータを計算するためにこのデータがこの計算装置によって使用されるとき、第１のデータ・セットのデータは、前記クロックだけによって制御される移送手段によって計算装置の入力にルーティングされる。移送手段は、第１のデータ・セットのデータが計算装置によって使用される瞬間にこのデータが前記計算装置の入力に到着するような手段である。したがってこの回路は、ランダム・アクセス・メモリも、制御装置も持つ必要がなく、これによってこのような回路の電流消費およびこのような回路によって覆われるシリコン表面を小さくすることができる。
【００１３】
有利には、この移送手段は、前記計算装置の出力から入力へデータをルーティングするために必要なサイクル数を調整するための調整手段を含む。このような回路は大きな柔軟性を有する。実際、この回路によって処理されるデータ・セットは変更可能なデータ数を有することができる。計算装置の出力から入力へデータをルーティングするために必要なサイクル数はとりわけデータ・セットのデータ数によって決まる。この調整手段のおかげで、計算装置の出力から入力へデータをルーティングするために必要なサイクル数を、処理するデータ・セットのデータ数の関数として調整することができる。したがって、このような回路を使用して、さまざまな数のデータを有するデータ・セットを処理することができる。
【００１４】
好ましい一実施形態では、この移送手段は少なくとも一つのクロックで活性化されるレジスタを有し、このレジスタは、１クロック・サイクルごとに新しいデータを記憶する能力を有する活性化。この実施形態によれば移送手段は１つのデータを記憶する能力を有するレジスタだけを含む。このようなレジスタはシリコン表面をほとんど覆わず、小さい電流消費を有する。このような回路はさらに設計が簡単であり、このようなレジスタの数は、計算装置の出力から入力へデータをルーティングするために必要なサイクル数に一致する。
【００１５】
本発明のこれらの態様および他の態様は、以下に記載する非限定的な例としての実施形態から明らかであり、これらの実施形態を参照すれば解明されるであろう。
【発明を実施するための最良の形態】
【００１６】
図３に本発明に基づく回路の一例を示す。このような回路は、入力３１１、出力３１２および移送手段（transport means）３２を有する計算装置３１を含む。この例では移送手段が９つのレジスタ３２１から３２９を含む。計算装置３１はさらに、係数などの追加データ３４を受け取ることができる。
【００１７】
以下に説明する例では、図３の回路によって第２のデータ・セットを第１のデータ・セットに基づいて計算する方法を示す。この例は、図１の第２のデータ・セットｂ０［２］〜ｂ９［２］および第１のデータ・セットｂ０［１］〜ｂ９［１］に適用される。
【００１８】
第１のデータ・セットのデータは予め、図１のデータ・セットｂ０［０］〜ｂ９［０］に対応する初期データに基づいて計算されている。これらのデータは追加データ３４の形態で計算装置３１に送られる。第１のクロック・サイクルの間にデータｂ０［０］が計算装置３１に送られる。次いで計算装置３１によってデータｂ０［１］が計算され、レジスタ３２１に記憶される。データｂ０［１］は、図１には示されていない記憶装置に並列に記憶することができることに留意されたい。第２のクロック・サイクルの間にデータｂ１［０］が計算装置３１に送られる。次いでデータｂ１［１］は計算装置３１によって計算され、レジスタ３２２に送られたデータｂ０［１］の代わりにレジスタ３２１に記憶される。実際、レジスタ３２１〜３２９はクロックによって活性化活性化される。すなわち１クロック・サイクルごとにレジスタの中に存在するデータはそのレジスタを出ていく。
【００１９】
同様の操作がデータｂ２［１］〜ｂ９［１］に対して実施される。１０番目のクロック・サイクルの間に、レジスタ３２９に記憶されていたデータｂ１［０］が計算装置３１の入力３１１に送られ、計算装置３１によってデータｂ９［１］が計算され、レジスタ３２１に送られる。
【００２０】
１１番目のクロック・サイクルの間に、第２のデータ・セットのデータｂ０［２］が、計算装置３１によってデータｂ０［１］に基づいて計算される。このデータｂ０［２］は次いでレジスタ３２１に記憶される。この１１番目のクロック・サイクルの間に、レジスタ３２９に記憶されていたデータｂ１［１］が計算装置３１の入力３１１に送られる。１２番目のクロック・サイクルの間に、計算装置３１によってデータｂ１［２］が計算され、レジスタ３２１に記憶される。同様の操作がデータｂ２［２］からｂ９［２］に対して実施される。
【００２１】
この例では、計算装置３１によってデータを計算するのに１クロック・サイクルを要すると仮定している。このような計算はさまざまなクロック・サイクルを要することができる。例えば、このような計算が３クロック・サイクルを要とすると仮定する。
【００２２】
第１のクロック・サイクルの間にデータｂ０［０］が計算装置３１に送られる。第２のクロック・サイクルの間にデータｂ１［０］が計算装置３１に送られる。第３のクロック・サイクルの間にデータｂ２［０］が計算装置３１に送られる。このデータ計算は３クロック・サイクルを要するので、この第３のクロック・サイクルの間にデータｂ０［１］が計算される。このデータは次いでレジスタ３２１に記憶される。１０番目のクロック・サイクルの間にデータｂ９［０］が計算装置３１に送られる。このときデータｂ０［１］はレジスタ３２７に位置し、第２のデータ・セットのデータｂ０［２］の計算を開始するために計算装置３１に送られる。したがって、移送手段３２は７つのレジスタ３２１から３２７だけを必要とする。
【００２３】
結果的に、計算装置３１の出力から入力にデータをルーティングするために必要なクロック・サイクル数は、データ・セットのデータ数と１つのデータの計算に必要なクロック・サイクル数の両方によって決まる。一般に、データ・セットがｋ個のデータを含み、１つのデータの計算に必要なクロック・サイクル数が１の場合、計算装置３１の出力から入力に１つのデータをルーティングするために必要なクロック・サイクル数は（ｋ−１）になる。図３の例においてこのことは、クロックによって活性化される（ｋ−ｌ）個のレジスタが移送手段には必要であることを意味している。
【００２４】
前の例ではとりわけ、計算がパイプライン処理される、すなわち１クロック・サイクルごとに１つのデータが計算装置３１に送られると仮定した。本発明に基づく回路がさまざまな計算装置を含むときには特に、１クロック・サイクルごとに１つのデータを計算装置３１に送らないことも可能である。このような場合も、計算装置の出力から入力に１つのデータをルーティングするために必要なクロック・サイクル数は、図５に関してさらに詳細に論じるように、データ・セットのデータ数、および１つのデータの計算に必要なクロック・サイクル数によって決まる。
【００２５】
図４に、本発明の有利な実施形態に基づく回路を示す。このような回路は、図３に関して述べた要素に加えて、計算装置３１の出力から入力にデータをルーティングするために必要なサイクル数を調整するためのマルチプレクサ３５の形態の調整手段を含む。マルチプレクサ３５は、図４には示されていない制御回路によって制御され、レジスタ３２３またはレジスタ３２７、あるいはレジスタ３２９に記憶されているデータを計算装置３１の入力３１１に送ることができる。したがって、計算装置３１の出力から入力にデータを運ぶために必要なサイクル数を調整することができる。実際、レジスタ３２３に記憶されているデータを計算装置３１の入力に送ることを選択した場合、計算装置３１の出力から入力にデータをルーティングするために必要なサイクル数は３になる。レジスタ３２７に記憶されているデータを計算装置３１の入力に送ることを選択した場合には、計算装置３１の出力から入力にデータをルーティングするために必要なサイクル数は７になる。
【００２６】
したがって、このような回路を使用して、さまざまな数のデータを有するデータ・セットを処理することができる。計算がパイプライン処理され、計算装置３１によって１つのデータを計算するのに１クロック・サイクルを要すると仮定すると、例えば４つのデータを含むデータ・セットを処理するためには、レジスタ３２３に記憶されているデータを計算装置３１の入力３１１に送ることを選択する。８つのデータを含むデータ・セットを処理するためには、レジスタ３２７に記憶されているデータを選択する。１０個のデータを含むデータ・セットを処理するためには、レジスタ３２９に記憶されているデータを選択する。
【００２７】
それぞれのレジスタ３２１〜３２９からデータを選択できるように調整手段を設計できることは明白である。したがって、計算装置３１によってデータを計算するのに１クロック・サイクルを要する場合、２個から１０個の間のデータを含むデータ・セットを処理することができる。
【００２８】
図５に、乗算−累算計算用の本発明に基づく回路を示す。このような回路は４つの計算装置４１〜４４を含む。これらの計算装置は加算器である。各計算装置４１〜４４にはそれぞれ乗算器４１０〜４４０が結合されている。さらに各計算装置にはそれぞれ３つのレジスタ４１１〜４１３、４２１〜４２３、４３１〜４３３および４４１〜４４３が結合されている。
【００２９】
図５の回路は、乗算−累算の４つの結果ＭＡＣ１〜ＭＡＣ４を、１６個のデータｄ１〜ｄ１６および１６個の係数ｃ１〜ｃ１６に基づいて計算するためのものである。
【００３０】
ＭＡＣ１＝ｃ１×ｄ１＋ｃ５×ｄ５＋ｃ９×ｄ９＋ｃ１３×ｄ１３
ＭＡＣ２＝ｃ２×ｄ２＋ｃ６×ｄ６＋ｃ１０×ｄ１０＋ｃ１４×ｄ１４
ＭＡＣ３＝ｃ３×ｄ３＋ｃ７×ｄ７＋ｃ１１×ｄ１１＋ｃ１５×ｄ１５
ＭＡＣ４＝ｃ４×ｄ４＋ｃ８×ｄ８＋ｃ１２×ｄ１２＋ｃ１６×ｄ１６
このような回路は例えば、ＭＰ３フォーマットで送信されたデータの復号フィルタで使用される。このデータは、それぞれのバンドがいくつかのサブ・バンドに分割されたデータ・バンドの形態で送信される。図５の回路はクロックによって制御される。１クロック・サイクルごとに１つのデータが回路に到着し、乗算器４１０〜４４０の１つに送られる。データｄ１は乗算器４１０に送られ、データｄ２は乗算器４２０に、データｄ３は乗算器４３０に、データｄ４は乗算器４４０に、データｄ５は乗算器４１０に送られ、その後のデータも順次、１つの乗算器に送られる。
【００３１】
第１のクロック・サイクルの間に、係数ｃ１が乗算器４１０に送られ、データｃ１×ｄ１が計算され、次いでこれに計算装置４１によってゼロが加算される。データｃ１×ｄ１は次いでレジスタ４１１に送られる。第２のクロック・サイクルの間に、係数ｃ２が乗算器４２０に送られ、データｃ２×ｄ２が計算され、次いでこれに計算装置４２によってゼロが加算される。データｃ２×ｄ２は次いでレジスタ４２１に送られる。同様の操作が実施されて値ｃ３×ｄ３およびｃ４×ｄ４が計算され、これらはそれぞれレジスタ４３１および４４１に送られる。データｃ１×ｄ１、ｃ２×ｄ２、ｃ３×ｄ３およびｃ４×ｄ４が第１のデータ・セットを構成する。
【００３２】
第５のクロック・サイクルの間に、係数ｃ５が乗算器４１０に送られ、データｃ５×ｄ５が計算され、次いでこれに計算装置４１によってデータｃ１×ｄ１が加算される。実際、第２、第３および第４のクロック・サイクルの間にレジスタ４１１、４１２、４１３と進んだデータｃ１×ｄ１は、第４のクロック・サイクルの間に計算装置４１に送られる。計算装置４１によって計算されたデータｃ１×ｄ１＋ｃ５×ｄ５は次いでレジスタ４１１に送られる。同様の操作が第６、第７および第８のクロック・サイクルの間に実施されて、データｃ２×ｄ２＋ｃ６×ｄ６、ｃ３×ｄ３＋ｃ７×ｄ７およびｃ４×ｄ４＋ｃ８×ｄ８が計算される。データｃ１×ｄ１＋ｃ５×ｄ５、データｃ２×ｄ２＋ｃ６×ｄ６、ｃ３×ｄ３＋ｃ７×ｄ７およびｃ４×ｄ４＋ｃ８×ｄ８が、第１のデータ・セットに基づいて計算された第２のデータ・セットを構成する。
【００３３】
図６に、本発明に基づく回路を含む通信ネットワークを示す。このようなネットワークは、符号化装置ＥＮＣ、伝送路ＣＨＡＮおよび復号回路ＤＥＣを含む。符号化装置ＥＮＣのレベルで、送信されるデータ・ベクトルＳ１は、第１のシステマティック再帰コーダ（systematic recursive coder）６１によって符号化されて第１のパリティ・ベクトルＰ１を生み出す。これと並行して、データ・ベクトルＳ１のデータは第１のインタリーバ（interleaver）６２によってインタリーブされ、その結果得られたベクトルが、第２のシステマティック再帰コーダ６３によって符号化されて第２のパリティ・ベクトルＰ２を生み出す。
【００３４】
ベクトルのデータのインタリービングは、別のベクトルを得るためにそのベクトルの成分を予め決められた順序に置換することからなる。以下では、説明を単純にするため、ベクトルのデータのインタリービングまたはベクトルのインタリービングを特に区別せずに用いる。
【００３５】
続いて、データ・ベクトルＳ１、第１のパリティ・ベクトルＰ１および第２のパリティ・ベクトルＰ２が、伝送路ＣＨＡＮを介して受信機（図６には示されていない）に送られる。これは送信機（図６には示されていない）によって実行される。データ・ベクトルＳ１、第１のパリティ・ベクトルＰ１および第２のパリティ・ベクトルＰ２は次いで、復号回路ＤＥＣに送られる。
【００３６】
復号回路ＤＥＣは、第１の符号器６４、第２の符号器６６、第２のインタリーバ６５、第３のインタリーバ６７およびデインタリーバ（de-interleaver）６８を含む。図１の例では符号器６４および６６がソフト・インプット・ソフト・アウトプット符号器（ＳＩＳＯ）である。
【００３７】
この復号回路ＤＥＣは反復的に動作する。一反復の間に、第１の符号器６４は、受け取ったデータ・ベクトルＳ１、受け取った第１のパリティ・ベクトルＰ１、および第２の符号器６６から来るエキストリンシック・データ・ベクトルに基づいて第１のエキストリンシック出力データ・ベクトルを計算する。第２の符号器６６から来るエキストリンシック・データ・ベクトルがまだない場合には、このベクトルは予め決められたベクトル、例えば単位ベクトルに置き換えられる。これは復号の最初の反復の間に起こり得る。
【００３８】
第１のエキストリンシック出力データ・ベクトルは第２のインタリーバ６５によってインタリーブされ、その結果得られたベクトルが第２の符号器６６に送られる。第２の符号器６６は次いで、第２のパリティ・ベクトルＰ２、データ・ベクトルＳ１を入力に持つ第３のインタリーバ６７から来るベクトルＳ２、および第２のインタリーバ６５から来るベクトルに基づいて、第２のエキストリンシック出力データ・ベクトルを計算する。第２のエキストリンシック出力データ・ベクトルは次いでデインタリーバ６８によってデインタリーブされ、その結果得られたベクトルは第１の符号器６４に送られる。次いで新しい反復を実行することができる。
【００３９】
このような復号回路は、第３世代携帯電話などの電子装置で使用することができる。
【００４０】
データのインタリービングには、図７に関して説明する列内置換要素（intracolumn permutation element）の計算が必要である。このような列内置換要素の計算は、図８に関して説明するように、本発明に基づく回路を含むシステムによって実行される。
【００４１】
図７に、図６の通信ネットワークのインタリーバによって実施されるインタリービング行列の計算およびインタリーブされたブロックを示す。以下に説明する例は、「3GGP TS 25.212 V3.9.0(2002-03)」規格に基づくインタリーバに適用される。
【００４２】
このようなインタリーバの目的は、Ｋ個のビットを含むデータ・ベクトルに含まれるデータの位置を置換することである。Ｋは４０から５１１４までの整数である。インタリーバは、Ｒ個の行およびＣ個の列を含むインタリービング行列によって定義されるインタリービング方式によって、データ・ベクトルを、インタリーブされたデータ・ベクトルに変換する。
【００４３】
図７の例は、インタリービング行列を定義する方法、およびデータ・ベクトルのビットをインタリーブする方法を示している。この例では、２５個のビットを含むデータ・ベクトルＢをインタリーブし、インタリーブされたデータ・ベクトルＢ’を得る。この例の目的は、インタリーブされたデータ・ベクトルＢ’を得る方法を単純に示すことにあることに留意されたい。より具体的には、この例は、データ・ベクトルの長さＫが４０および５１１４である「3GGP TS 25.212 V3.9.0(2002-03)」規格とは一致しない。
【００４４】
この例では、データ・ベクトルＢのそれぞれビットは０から２４までの識別子によって識別される。これらの識別子は第１の行列Ｍ１に横方向に書き込まれている。次いで、列内置換方式に従って行列Ｍ１の列内置換を実施し、行列Ｍ２を得る。次いで、列間置換（intercolumn permutation）方式に従って行列Ｍ２の列間置換を実施し、行列Ｍ３を得る。この行列Ｍ３がインタリービング行列である。
【００４５】
次いで、インタリービング行列の識別子の縦読みによって、インタリーブされたデータ・ベクトルＢ’のビットの識別子を得る。この例では、データ・ベクトルＢでは最初の位置にある識別子＜＜０＞＞によって識別されるビットが、インタリーブされたデータ・ベクトルＢ’では２４番目の位置にある。データ・ベクトルＢの識別子＜＜５＞＞によって識別されるビットは、インタリーブされたデータ・ベクトルＢ’では２番目の位置にある（以下同様）。
【００４６】
インタリービング方式はＫの値ごとに定義される。そのために、列内置換方式および列間置換方式が定義される。前述の規格は表１に定義された４つの列間置換方式を指定している。例えば、番号１によって識別される列間置換方式は、＜＜０＞＞で示される行列Ｍ２の最初の行を、＜＜１９＞＞で示される行列Ｍ２の２０番目の行に置き換え、第２の行を１０番目の行に置き換える（以下同様）。
【表１】
2006500850.tif 000003
表１：列間置換方式
【００４７】
インタリービング行列の行数および列間置換方式は、表２に記載されたデータ・ベクトルの長さＫによって決まる。この表はメモリに記憶されており、長さＫが分かれば、インタリーバは、インタリービング行列の行数Ｒおよび使用する列間置換方式を決定する。したがって所与の長さＫを有するデータ・ベクトルのインタリーブでは、インタリーバは、インタリービング行列の行数も列間置換方式も計算する必要がない。これらのパラメータは予め定まっているからである。
【００４８】
反対に、可能なそれぞれの列数Ｃごとに列内置換方式を記憶しておくことはできない。実際、列数Ｃは、２から２５６までの整数値をとることができる。したがって、可能なそれぞれの列数Ｃごとに列内置換方式を記憶することにすると非常に大きなメモリ容量が必要となる。したがって列内置換方式は、新しい長さＫを有するデータ・ベクトルをインタリーブするたびに計算される。
【表２】
2006500850.tif 000004
表２：Ｋに対する列間置換方式およびＲ
【００４９】
所与の長さＫに対する列内置換方式を計算するためには以下に説明するパラメータを決定する。
【００５０】
まず第一に素数ｐを決定する。この数ｐは、（ｐ−１）−Ｋ／Ｒ≧０となる最も小さい素数である。
【００５１】
次いで列数Ｃを決定する。この数Ｃは、Ｋ≦Ｒ×Ｃとなる、整数の集合｛（ｐ−１），ｐ，（ｐ＋１）｝のうちの最も小さい整数である。
【００５２】
次いで素数ｐの関数として原始根ｖを、表３に記載されているように決定する。
【表３】
2006500850.tif 000005
表３：素数ｐに対する原始根ｖ
【００５３】
続いて、最小素数の数列ｑを計算する。この数列はＲ個の値からなり、以下のように構築される。
【００５４】
−ｑ［０］＝１
−ｊ＞０に対して、ｑ［ｊ］は、
・ｑ［ｊ］と（ｐ−１）の最大公約数が１
・ｑ［ｊ］＞６
・ｑ［ｊ］＞ｑ［ｊ−１］
となる最も小さい素数
次いで、最小素数の置換された数列ｒを、列間置換方式Ｔを利用することによって計算する：ｒ［Ｔ［ｊ］］＝ｑ［ｊ］。
【００５５】
次いで基本数列ｓを計算する。この数列はｐ−１個の値からなり、以下のように構築される。
【００５６】
−ｓ［０］＝１
−ｓ［ｉ］＝（ｖ×ｓ［ｉ−１］）ｍｏｄ  ｐ。ただし「ｍｏｄ  ｐ」は、モジュロｐ（ｍｏｄｕｌｏ−ｐ）乗算を実施することを指示している。
【００５７】
最後に、それぞれの列ｊについて列内置換方式を計算する。所与の列ｊに対して、Ｃ＝ｐに対して与えられる以下に説明する計算モードに従ってＣ個の列内置換要素Ｕｊを計算する。
【００５８】
−Ｕｊ［ｉ］＝ｓ［（ｉ×ｒ［ｊ］）ｍｏｄ（ｐ−１）］，ｉ＝０，１，．．．，ｐ−２
−Ｕｊ［ｐ−１］＝０
式Ｕｊ［ｉ］＝ｓ［（ｉ×ｒ［ｊ］）ｍｏｄ（ｐ−１）］が、
Ｕｊ［ｉ＋１］＝（ｖ’［ｊ］×Ｕｊ［ｉ］）ｍｏｄ  ｐ
に等しいことは証明することができる。ただしｖ’［ｊ］はｖに等しい新しい原始根である。実際、
−式ｓ［ｉ］＝（ｖ×ｓ［ｉ−１］）ｍｏｄ  ｐは式
ｓ［ｉ］＝（ｖｉ×ｓ［０］）ｍｏｄ  ｐ＝ｖｉｍｏｄ  ｐ
に等しい。
【００５９】
−したがって、式Ｕｊ［ｉ］＝ｓ［（ｉ×ｒ［ｊ］）ｍｏｄ（ｐ−１）］は式Ｕｊ［ｉ］＝ｖ（ｉ×ｒ［ｊ］）ｍｏｄ（ｐ−１）ｍｏｄ  ｐに等しい。
【００６０】
−ａ＝ｖおよびｉ×ｒ［ｊ］＝ｂとした場合、
−ａｂｍｏｄ  ｐ＝［ａｎ（ｐ−１）］［ａｂｍｏｄ（ｐ−１）］ｍｏｄ  ｐ。ただしｎはｂ＝ｎ（ｐ−１）＋ｂｍｏｄ（ｐ−１）となるような値である。
【００６１】
−したがってａｂｍｏｄ  ｐ＝［ａｎ（ｐ−１）ｍｏｄ  ｐ］［ａｂｍｏｄ（ｐ−１）］ｍｏｄ  ｐ
＝［（ａ（ｐ−１））ｎｍｏｄ  ｐ］［ａｂｍｏｄ（ｐ−１）］ｍｏｄ  ｐ
＝［ａ（ｐ−１）ｍｏｄ  ｐ］ｎ［ａｂｍｏｄ（ｐ−１）］ｍｏｄ  ｐ
−ｐが素数、ａとｐの最大公約数が１の場合、ａ（ｐ−１）ｍｏｄ  ｐ＝１。この例ではａ＝ｖであり、ｖは決してｐにならない。このことは、ａとｐの最大公約数が１であることを意味する。したがって、
［ａ（ｐ−１）ｍｏｄ  ｐ］ｎ＝１。したがってａｂｍｏｄ  ｐ＝ａｂｍｏｄ（ｐ−１）ｍｏｄ  ｐ
−この式でａをｖに置き換え、ｂをｉ×ｒ［ｊ］に置き換えた場合、下式が得られる。
【００６２】
ｖｉ×ｒ［ｊ］ｍｏｄ  ｐ＝ｖ（ｉ×ｒ［ｊ］）ｍｏｄ（ｐ−１）ｍｏｄ  ｐ＝Ｕｊ［ｉ］
−この式は式Ｕｊ［ｉ］＝（ｖ’［ｊ］）ｉｍｏｄ  ｐに等しい。ただしｖ’［ｉ］＝ｖｒ［ｊ］である。
【００６３】
−この式を再帰的に適用することによって、下式が得られる。
【００６４】
Ｕｊ［ｉ＋１］＝（ｖ’［ｊ］×Ｕｊ［ｉ］）ｍｏｄ  ｐ
図８に、上述の列内置換要素を計算するための本発明に基づく回路を含むシステムを示す。
【００６５】
このようなシステムは、計算装置８００および移送手段８０１を含む。この計算装置は、１５個のレジスタＲ１〜Ｒ１５、７つのモジュロｐシフト要素ＳＭＰ１〜ＳＭＰ７、８つのマルチプレクサＭＵＸ１〜ＭＵＸ８、および７つのモジュロｐ加算器ＡＭＰ２〜ＡＭＰ８を含む。移送手段８０１は１２個のレジスタＲ１６〜Ｒ２７を含む。このシステムはさらにマルチプレクサＭＵＸ９の形態の調整手段を含む。
【００６６】
計算装置８００は、ｐよりも小さい２つのデータｘとｙの間のモジュロｐ乗算を実行することができる。ｘおよびｙが、最下位ビットから最上位ビットまで８ビットの２進言語で書かれていると仮定する。
【００６７】
ｘ＝ｘ（０）ｘ（１）ｘ（２）ｘ（３）ｘ（４）ｘ（５）ｘ（６）ｘ（７）
ｙ＝ｙ（０）ｙ（１）ｙ（２）ｙ（３）ｙ（４）ｙ（５）ｙ（６）ｙ（７）
ステージ８１の間に、データｘはモジュロｐシフト要素ＳＭＰ１に送られる。ビットｙ（０）の値が１の場合、値ｘはマルチプレクサＭＵＸ１によってレジスタＲ８にコピーされる。ビットｙ（０）の値が０の場合、レジスタＲ８には値０がコピーされる。
【００６８】
モジュロｐシフト要素はデータｘを左にシフトし、得られたデータをｐと比較する。得られたこのデータは以下のように書かれる。
【００６９】
ｘ（１）ｘ（２）ｘ（３）ｘ（４）ｘ（５）ｘ（６）ｘ（７）０
得られたこのデータがｐよりも大きい場合、この得られたデータを用いたモジュロｐ演算が実施され、この演算の結果がレジスタＲ１に書き込まれる。得られたデータがｐよりも小さい場合、レジスタＲ１にはこのデータがコピーされる。
【００７０】
ステージ８２の間に、レジスタＲ１に記憶されているデータが、モジュロｐシフト要素ＳＭＰ２およびマルチプレクサＭＵＸ２に送られる。それぞれのステップは、レジスタを活性化するために１クロック・サイクルを要する。第２のビットｙ（１）の値が１の場合、レジスタＲ１に記憶されているデータはモジュロｐ加算器ＡＭＰ２に送られる。第２のビットｙ（１）の値が０の場合、モジュロｐ加算器ＡＭＰ２には値０が送られる。モジュロｐ加算器ＡＭＰ２にはレジスタＲ８に記憶されていたデータも送られる。モジュロｐ加算器ＡＭＰ２は、その２つの入力値のモジュロｐ加算を実行し、結果をレジスタＲ９に送る。
【００７１】
ステージ８３から８８の間に同様の演算が実施され、モジュロｐ加算器ＡＭＰ８の出力にｘとｙのモジュロｐ乗算の結果が得られる。
【００７２】
図８の回路による列内置換要素の計算を以下で説明する。
【００７３】
新しい原始根ｖ’［ｊ］および列内置換要素は、インタリービング行列の行数Ｒが１０または２０の場合には８ビット、Ｒが５の場合には５ビットで書かれる。
【００７４】
新しい原始根ｖ’［ｊ］および列内置換要素が８ビットで書かれていると仮定する。この場合、新しい原始根と列内置換要素の間のモジュロｐ乗算には８クロック・サイクルを要する。
【００７５】
列内置換要素Ｕ０［１］を計算するために、列内置換要素Ｕ０［０］が、ステージ８１の間に、モジュロｐシフト要素ＳＭＰ１およびマルチプレクサＭＵＸ１に送られる。第１のクロック・サイクルの後、第２のクロック・サイクルの間にステージ８２が実施される。ｖ’［０］とＵ０「０」の間のモジュロｐ乗算の第２のステージが実施されている間にｖ’［１］とＵ１［０］の間の第１のモジュロｐ乗算ステージを実施するため、この第２のクロック・サイクルの間に、列内置換要素Ｕ１［０］がモジュロｐシフト要素ＳＭＰ１およびマルチプレクサＭＵＸ１に送られる。
【００７６】
図８に、８番目のクロック・サイクルの間に実施される計算を示す。ｖ’［０］とＵ０［０］の間のモジュロｐ乗算の第８のステージが実施され、その中で、新しい原始根ｖ’［０］の８番目のビットｖ’［０］（７）の値が１であるかどうかをマルチプレクサＭＵＸ８が確認する。ｖ’［１］とＵ１［０］の間のモジュロｐ乗算の第７のステージは実施され、その中で、新しい原始根ｖ’［１］の７番目のビットｖ’［１］（６）の値が１であるかどうかをマルチプレクサＭＵＸ７が確認し、以下同様の操作を順次実施する。ｖ’［７］とＵ７［０］の間のモジュロｐ乗算の最初のステージは実施され、その中で、新しい原始根ｖ’［７］の最初のビットｖ’［７］（０）の値が１であるかどうかをマルチプレクサＭＵＸ１が確認する。
【００７７】
８番目のクロック・サイクルの終わりに、列内置換要素Ｕ０［１］が計算され、レジスタＲ１５に記憶される。インタリービング行列の行数が２０であると仮定する。列ごとに２０個の列内置換要素が計算される。したがって列内置換要素Ｕ０［１］〜Ｕ１９［１］が計算され、次いでＵ０［１］に基づいて要素Ｕ０［２］が計算され、Ｕ１［１］に基づいて要素Ｕ１［２］が計算され、以下同様に順次計算される。したがって計算装置８００によって計算されたそれぞれの列内置換要素は、計算されてから１２クロック後にこの計算装置８００によって再び使用される。１２個のレジスタＲ１６〜Ｒ２７を含む移送手段８０１は、１２クロック・サイクルのうちに１つのデータを計算装置８００の出力から入力へ移動させることができる。
【００７８】
インタリービング行列の行数が１０であると仮定する。それぞれの列ｊに対して１０個の列内置換要素が計算される。したがって計算装置８００によって計算されたそれぞれの列内置換要素は、計算されてから２クロック後にこの計算装置８００によって再び使用される。マルチプレクサＭＵＸ９のおかげで、レジスタＲ１７の出力のデータを選択して、２クロック・サイクルのうちにこのデータを計算装置８００の出力から入力へ移送することができる。
【００７９】
動詞「含む」およびその活用形は幅広く解釈しなければならない。すなわちこれらの表現は、前記動詞の後に挙げた要素以外の要素が存在することを排除するものでも、また複数と明示せずに前記動詞の後にすでに挙げた要素が複数存在することを排除するものでもないと解釈しなければならない。
【図面の簡単な説明】
【００８０】
【図１】計算前のデータの一例を示す図である。
【図２】図１のデータを計算するための従来技術の回路を示すブロック図である。
【図３】本発明に従う回路を示すブロック図である。
【図４】本発明の有利な実施形態に従う回路を示すブロック図である。
【図５】乗算累算計算用の本発明に従う回路を示す図である。
【図６】本発明に従う回路を含む通信ネットワークを示す図である。
【図７】インタリービング行列の計算およびインタリーブされたブロックを示す図である。
【図８】インタリーバの列内置換要素を計算するための本発明に従う回路を示す図である。
【図１】
2006500850.tif 000006
【図２】
2006500850.tif 000007
【図３】
2006500850.tif 000008
【図４】
2006500850.tif 000009
【図５】
2006500850.tif 000010
【図６】
2006500850.tif 000011
【図７】
2006500850.tif 000012
【図８】
2006500850.tif 000013
【国際調査報告】
2006500850.tif 000014
2006500850.tif 000015