プルーンインタリーバおよびプルーンデインタリーバの効率的なアドレス生成

专利摘要:
プルーンインタリーバおよびプルーンデインタリーバのアドレスを効率的に生成する技法を説明する。一態様では、線形アドレスに対応する無効なマッピングの総数を決定することによって、線形アドレスを、プルーンインタリーバのインタリーブされたアドレスにマッピングすることができる。中間アドレスを入手するために、線形アドレスと無効なマッピングの総数との合計をとることができる。次に、プルーンインタリーバのインタリーブされたアドレスを、中間アドレスの非プルーンインタリーバ関数に基づいて決定することができる。プルーンインタリーバは、プルーンビット逆転インタリーバ、ビット逆転関数および線形合同シーケンス関数からなるプルーンターボインタリーバ、またはある他のタイプのインタリーバとすることができる。無効なマッピングの総数を、反復的に決定することができ、各反復を、異なるタイプのプルーンインタリーバについて異なる形で実行することができる。
公开号:JP2011508530A
申请号:JP2010539758
申请日:2008-12-17
公开日:2011-03-10
发明作者:マンサワー、モハマッド
申请人:クゥアルコム・インコーポレイテッドＱｕａｌｃｏｍｍ Ｉｎｃｏｒｐｏｒａｔｅｄ；
IPC主号:H03M13-27

专利说明:

[0001] 米国特許法第１１９条の下での優先権の主張
本願は、本発明の譲受人に譲渡され、特に参照によって本明細書に組み込まれている、２００７年１２月２１日に出願した米国仮出願第６１／０１６０４５号、名称「ＰＡＲＡＬＬＥＬ ＰＲＵＮＥＤ ＩＮＴＥＲＬＥＡＶＥＲ ＭＥＴＨＯＤＡＮＤＡＰＰＡＲＡＴＵＳ」の優先権を主張するものである。]
[0002] 本開示は、全般的にはデータ処理に関し、より具体的にはインタリーバおよびデインタリーバに関する。]
背景技術

[0003] インタリーバは、入力データを受け取り、入力データをシャッフルしすなわち並べ変え、シャッフルされたデータを出力データとして供給する機能ブロックである。インタリーバは、性能に対する雑音および干渉の影響を減らすために、ほとんどの無線通信システムで使用される。たとえば、チャネルインタリービングは、一般に、雑音および干渉に起因する誤りのバーストに対して保護するのに利用される。送信機では、チャネルインタリーバは、チャネル符号器からのコードビットをシャッフルし、その結果、連続するコードビットが、インタリーブされたビット内で分離されるようにする。インタリーブされたビットのシーケンスが、誤りのバースト内で用いられる時には、これらのインタリーブされたビットは、受信器のチャネルデインタリーバによる相補的再シャッフリングの後に、分離される。したがって、インタリービングは、誤りのバーストに含まれる連続するビットの間の時間的相関を壊し、これが、性能を改善する場合がある。]
[0004] インタリービングを、特定の線形アドレスのデータ値（たとえば、コードビット）を受け取ることと、線形アドレスに基づいてインタリーブされたアドレスを決定すること（determining）と、インタリーブされたアドレスにデータ値を格納することとによって実行することができる。線形アドレスからインタリーブされたアドレスへのマッピングは、ルックアップテーブルに基づくものとすることができる。複数のパケットサイズをサポートすることができ、ルックアップテーブルを、サポートされるパケットサイズごとに生成することができる。多数の異なるパケットサイズについて線形アドレスをインタリーブされたアドレスにマッピングする多数のルックアップテーブルを格納するために、大量のメモリが必要になる可能性がある。したがって、インタリーブされたアドレスを必要に応じてリアルタイムで効率的に計算することが望ましい可能性がある。]
[0005] プルーンインタリーバ（pruned interleavers）およびプルーンデインタリーバ（pruned de-interleavers）のアドレスを効率的に決定する技法を、本明細書で説明する。非プルーンインタリーバ（non-pruned interleavers）および非プルーンデインタリーバ（non-pruned de-interleavers）は、２のべきのサイズを有し、その結果、０からＭ−１までのアドレス範囲全体が有効であり、ここで、Ｍ＝２ｎであり、ｎは、アドレスのビット数である。プルーンインタリーバおよびプルーンデインタリーバは、２のべきではないサイズを有し、その結果、ＬからＭ−１までの範囲内のアドレスが無効であり、ここで、Ｌは、プルーンインタリーバまたはプルーンデインタリーバのサイズである。]
[0006] 一態様では、線形アドレスに対応する無効なマッピングの総数を決定することによって、線形アドレスを、プルーンインタリーバのインタリーブされたアドレスにマッピングすることができる。無効なマッピングは、非プルーンインタリーバ関数に基づく０からＬ−１までの範囲内にはないインタリーブされたアドレスへの線形アドレスのマッピングである。中間アドレスを入手するために、線形アドレスと無効なマッピングの総数との合計をとることができる。次に、プルーンインタリーバのインタリーブされたアドレスを、中間アドレスの非プルーンインタリーバ関数に基づいて決定することができる。]
[0007] ある設計では、プルーンインタリーバを、ビット逆転インタリーバ（bit-reversal interleaver、ＢＲＩ）とすることができる。中間アドレスのビット逆転版（bit-reversed version）を、プルーンＢＲＩのインタリーブされたアドレスとして提供することができる。もう１つの設計では、プルーンインタリーバを、２次元（２Ｄ）配列の複数の行に関するビット逆転関数および各行内の複数のエントリに関する線形合同シーケンス（linear congruential sequence、ＬＣＳ）関数を含むプルーンターボインタリーバとすることができる。プルーンターボインタリーバのインタリーブされたアドレスを、中間アドレスの非プルーンターボインタリーバ関数に基づいて決定することができる。]
[0008] ある設計では、無効なマッピングの総数を、反復的に、たとえば事前定義の回数の反復だけ、または無効なマッピングの同一の総数が２つの連続する反復について得られるまで、決定することができる。各反復を、下で説明するように、異なるタイプのプルーンインタリーバについて異なる形で実行することができる。]
[0009] もう１つの態様では、インタリーブされたアドレスに対応する無効なマッピングの総数を決定することによって、インタリーブされたアドレスを、プルーンデインタリーバの線形アドレスにマッピングすることができる。中間アドレスを、インタリーブされたアドレスの非プルーンデインタリーバ関数に基づいて決定することができる。次に、プルーンデインタリーバの線形アドレスを得るために、無効なマッピングの総数を中間アドレスから減算することができる。]
[0010] 本開示のさまざまな態様および特徴を、下でさらに詳細に説明する。]
図面の簡単な説明

[0011] 基地局および端末を示すブロック図。
送信（ＴＸ）データプロセッサを示すブロック図。
ターボ符号器を示すブロック図。
受信（ＲＸ）データプロセッサを示すブロック図。
ターボ復号器を示すブロック図。
無効なマッピングの総数の反復決定を示す図。
１回の反復に関する無効なマッピングの個数の計算を示す図。
プルーンＢＲＩのアドレスジェネレータを示すブロック図。
アドレスジェネレータ内の論理回路を示すブロック図。
ルックアヘッドプルーンＢＲＩを示すブロック図。
プルーンインタリーバのアドレスジェネレータを示すブロック図。
プルーンデインタリーバのアドレスジェネレータを示すブロック図。
データを並べ変えるプロセスを示す図。]
実施例

[0012] 本明細書で説明する技法を、通信、ネットワーキング、コンピューティング、その他など、さまざまな応用例に使用することができる。たとえば、この技法を、符号分割多元接続（ＣＤＭＡ）、時分割多元接続（ＴＤＭＡ）、周波数分割多元接続（ＦＤＭＡ）、直交ＦＤＭＡ（ＯＦＤＭＡ）、単一キャリアＦＤＭＡ（ＳＣ−ＦＤＭＡ）、および他のシステムなどの無線通信システムに使用することができる。用語「システム」および「ネットワーク」は、しばしば交換可能に使用される。符号分割多元接続システムは、ｃｄｍａ２０００、Ｕｎｉｖｅｒｓａｌ Ｔｅｒｒｅｓｔｒｉａｌ Ｒａｄｉｏ Ａｃｃｅｓｓ（ＵＴＲＡ）、その他などのラジオテクノロジを実施することができる。ｃｄｍａ２０００は、ＩＳ−２０００標準規格、ＩＳ−９５標準規格、およびＩＳ−８５６標準規格を包含する。ＵＴＲＡは、広帯域ＣＤＭＡ（ＷＣＤＭＡ）および符号分割多元接続の他の変形を含む。ＴＤＭＡシステムは、グローバル移動体通信システム（Global System for Mobile Communications：ＧＳＭ）などのラジオテクノロジを実施することができる。ＯＦＤＭＡシステムは、ウルトラ・モービル・ブロードバンド（Ultra Mobile Broadband：ＵＭＢ）、Ｅｖｏｌｖｅｄ ＵＴＲＡ（Ｅ−ＵＴＲＡ）、ＩＥＥＥ ８０２．１１（Ｗｉ−Ｆｉ）、ＩＥＥＥ ８０２．１６（ＷｉＭＡＸ）、ＩＥＥＥ ８０２．２０、Ｆｌａｓｈ−ＯＦＤＭ（登録商標）、その他などのラジオテクノロジを実施することができる。ＵＴＲＡ、Ｅ−ＵＴＲＡ、およびＧＳＭは、ユニバーサル・モービル・テレコミュニケーションシステム（Universal Mobile Telecommunication System：ＵＭＴＳ）の一部である。３ＧＰＰロングターム・エボルーション（Long Term Evolution：ＬＴＥ）は、Ｅ−ＵＴＲＡを使用する、ＵＭＴＳのやがて公開されるリリースである。ＵＴＲＡ、Ｅ−ＵＴＲＡ、ＧＳＭ、ＵＭＴＳ、およびＬＴＥは、「第３世代協力プロジェクト」（3rd Generation Partnership Project：３ＧＰＰ）という名前の組織からの文書に記載されている。ｃｄｍａ２０００およびＵＭＢは、「第３世代協力プロジェクト２」（3rd Generation Partnership Project 2：３ＧＰＰ２）という名前の組織からの文書に記載されている。明瞭にするために、本技法のいくつかの態様を、下ではＵＭＢについて説明する。]
[0013] 本明細書で説明する技法を、端末ならびに基地局に使用することができる。端末を、移動局、ユーザ機器、アクセス端末、加入者ユニット、ステーションなどと称する場合もある。端末は、セル電話機、携帯情報端末（ＰＤＡ）、無線通信デバイス、無線モデム、ハンドヘルドデバイス、ラップトップコンピュータ、コードレス電話機、無線ローカルループ（ＷＬＬ）ステーションなどとすることができる。基地局を、Ｎｏｄｅ Ｂ、ｅｖｏｌｖｅｄ Ｎｏｄｅ Ｂ（ｅＮＢ）、アクセスポイントなどと称する場合もある。]
[0014] 図１に、無線通信システム内の基地局１１０および端末１５０の設計のブロック図を示す。基地局１１０は、Ｔ個のアンテナを備え、端末１５０は、Ｒ個のアンテナを備え、一般にＴ≧１およびＲ≧１である。] 図１
[0015] 基地局１１０では、ＴＸデータプロセッサ１２０が、データ送信装置１１２からデータを受け取り、パケットフォーマットに基づいてそのデータを処理（たとえば、符号化、インタリーブ、変調）し、データシンボルを供給する。パケットフォーマットは、パケットサイズ、変調および符号化方式（ＭＣＳ）などを示すことができる。パケットフォーマットを、レート、トランスポートフォーマットなどと称する場合もある。ＴＸマルチプルインプットマルチプルアウトプット（multiple-input multiple-output、ＭＩＭＯ）プロセッサ１３０は、データシンボルをパイロットシンボルと多重化することができ、適用可能な場合にはプリコーディング（precoding）（たとえば、ビームフォーミングのために）を実行することができる。プロセッサ１３０は、Ｔ個の出力シンボル流れをＴ個の変調器（ＭＯＤ）１３２ａから１３２ｔに供給することができる。各変調器１３２は、出力サンプル流れを得るために、その出力シンボル流れを処理することができる（たとえば、ＯＦＤＭ、ＳＣ−ＦＤＭ、ＣＤＭＡなどのために）。各変調器１３２は、さらに、その出力サンプル流れを調整（たとえば、アナログに変換、フィルタリング、増幅、アップコンバート）し、順方向リンク信号を生成することができる。変調器１３２ａから１３２ｔからのＴ個の順方向リンク信号を、それぞれＴ個のアンテナ１３４ａから１３４ｔから送信することができる。]
[0016] 端末１５０では、Ｒ個のアンテナ１５２ａから１５２ｒが、順方向リンク信号を受信することができ、各アンテナ１５２は、受信信号をそれぞれの復調器（ＤＥＭＯＤ）１５４に供給することができる。各復調器１５４は、サンプルを入手するためにそれが受け取った信号を処理し（たとえば、フィルタリングし、増幅し、ダウンコンバートし、ディジタル化し）、さらに、受信されたシンボルを入手するためにサンプルを処理することができる（たとえば、ＯＦＤＭ、ＳＣ−ＦＤＭ、ＣＤＭＡなどのために）。ＭＩＭＯ検出器１６０は、受信されたパイロット信号から導出されたチャネル推定値を用いて、受信されたデータシンボルに対するＭＩＭＯ検出を実行することができ、データシンボル推定値を供給することができる。ＲＸデータプロセッサ１７０は、データシンボル推定値をさらに処理（たとえば、復調、デインタリーブ、復号）し、復号されたデータをデータ受信装置１７２に供給することができる。]
[0017] 端末１５０では、データ送信装置１８０からのデータを、ＴＸデータプロセッサ１８２によって処理し、パイロット信号と多重化し、ＴＸＭＩＭＯプロセッサ１８４によって処理し、さらに、アンテナ１５２ａから１５２ｒを介して送信できるＲ個の逆方向リンク信号を生成するために変調器１５４ａから１５４ｒによって処理することができる。基地局１１０では、逆方向リンク信号を、Ｔ個のアンテナ１３４ａから１３４ｔによって受信し、復調器１３２ａから１３２ｔによって処理し、ＭＩＭＯ検出器１３６によって検出し、端末１５０によって送信されたデータを回復するためにＲＸデータプロセッサ１３８によってさらに処理することができる。]
[0018] コントローラ／プロセッサ１４０および１９０は、それぞれ基地局１１０および端末１５０での動作を指示することができる。メモリ１４２および１９２は、それぞれ基地局１１０および端末１５０のデータおよびプログラムコードを格納することができる。]
[0019] 図２に、図１のＴＸデータプロセッサ１８２に使用することもできるＴＸデータプロセッサ１２０の設計のブロック図を示す。ＴＸデータプロセッサ１２０内では、パーティショニングユニット２１０が、送信すべきデータを受け取り、このデータを選択されたパケットサイズのパケットにパーティショニングすることができる。パケットを、トランスポートブロック、コードブロック、サブパケットなどと称する場合もある。各パケットを、別々に符号化し、復号することができる。各パケットは、固定サイズまたは可変サイズを有することができる。たとえば、パケットサイズを、送信すべきデータの量、使用可能なリソースの量、その他などのさまざまな要因に基づいて、サポートされるパケットサイズのセットから選択することができる。パケットサイズは、１２８ビットから１６３８４ビット（ＵＭＢの場合）の範囲またはある他の範囲内とすることができる。] 図１ 図２
[0020] 巡回冗長検査（ＣＲＣ）ジェネレータ２２０は、各パケットのＣＲＣ値を生成し、そのＣＲＣ値をパケットに付加することができる。ターボ符号器２３０は、ターボ符号に基づいて各パケットを符号化し、コーディングされたパケットを提供することができる。レートマッチングユニット２４０は、選択された符号レートに基づいて各コーディングされたパケット内のコードビットのサブセットを選択することができ、コーディングされたパケット内の残りのビットを削除することができる。チャネルインタリーバ２５０は、各コーディングされたパケット内の削除されなかったコードビットをインタリーブし、インタリーブされたパケットを提供することができる。インタリービングは、コードビットの時間ダイバーシティ、周波数ダイバーシティ、および／または空間ダイバーシティをもたらすことができる。シンボルマッパ２６０は、選択された変調方式に基づいて、インタリーブされたビットをデータシンボルにマッピングする。パケットサイズ、符号レート、および変調方式は、チャネル条件、端末機能、システムリソースの可用性などに基づいて選択できるパケットフォーマットに基づいて決定することができる。]
[0021] 図３に、図２のターボ符号器２３０の設計のブロック図を示す。ターボ符号器２３０は、並列連接畳込み符号（parallel concatenated convolutional code、ＰＣＣＣ）を実施し、２つの成分符号器（constituent encoder）３１０ａおよび３１０ｂ、ターボインタリーバ３２０、および多重化装置（Ｍｕｘ）３３０を含む。ターボ符号器２３０は、Ｌ個のデータビットのパケットを符号化し、Ｓ個のコードビットの対応するコーディングされたパケットを提供し、ここで、ＬおよびＳは、任意の適切な値とすることができる。] 図２ 図３
[0022] ターボ符号器２３０内で、ターボインタリーバ３２０は、ターボインタリーバ関数に基づいて、パケット内のデータビット（ｘと表される）をインタリーブすることができる。成分符号器３１０ａは、第１成分コードに基づいてデータビットを符号化し、第１パリティビット（ｙと表される）を供給することができる。同様に、成分符号器３１０ｂは、第２成分コードに基づいてターボインタリーバ３２０からのインタリーブされたデータビットを符号化し、第２パリティビット（ｚと表される）を供給することができる。成分符号器３１０ａおよび３１０ｂは、畳込み符号とすることのできる、２つの再帰的系統的成分コードを実施することができる。多重化装置３３０は、データビットおよびパリティビットを成分符号器３１０ａおよび３１０ｂから受け取り、データビットおよびパリティビットを多重化し、コーディングされたパケットのコードビットを提供することができる。コードビットは、データビットと、それに続く第１パリティビットと、それに続く第２パリティビットとを含むことができる。]
[0023] ある設計では、各成分符号器３１０は、レート１／３拘束長４成分畳込み符号を実施することができ、ターボ符号器２３０は、レート１／５ターボコードを実施することができる。ターボ符号器２３０は、可変サイズＬのパケットを受け取ることができ、コーディングされたパケットの５Ｌコードビットを生成することができる。ターボ符号器２３０を、他の符号レートおよび／または拘束長の成分畳込み符号を用いて実施することもできる。]
[0024] 図４に、図１のＲＸデータプロセッサ１３８にも使用できるＲＸデータプロセッサ１７０の設計のブロック図を示す。ＲＸデータプロセッサ１７０内では、対数尤度比（ＬＬＲ）計算ユニット４１０が、ＭＩＭＯ検出器１６０からデータシンボル推定値を受け取り、データシンボル推定値ごとにコードビットのＬＬＲを計算することができる。データシンボルは、信号コンステレーション（signal constellation）内の複素数値にＢ個のコードビットをマッピングすることによって得ることができる。Ｂ個のＬＬＲは、対応するデータシンボル推定値に基づいてデータシンボルのＢ個のコードビットについて計算することができる。各コードビットのＬＬＲは、そのコードビットのデータシンボル推定値を与えられて、コードビットが０または１である尤度を示すことができる。チャネルデインタリーバ４２０は、図２のチャネルインタリーバ２５０によるインタリービングに相補的な形でＬＬＲをデインタリーブすることができる。逆レートマッチング（de-rate matching）ユニット４３０は、図２のユニット２４０によるレートマッチングと相補的な形で、デインタリーブされたＬＬＲに対して逆レートマッチングを実行することができ、入力ＬＬＲを提供することができる。ターボ復号器４４０は、入力ＬＬＲの各パケットを復号し、復号されたパケットを提供することができる。ＣＲＣチェッカ４５０は、各復号されたパケットをチェックし、そのパケットの復号状況を提供することができる。アセンブラ４６０は、復号されたパケットをアセンブルし、復号されたデータを提供することができる。] 図１ 図２ 図４
[0025] 図５に、図４のターボ復号器４４０の設計のブロック図を示す。ターボ復号器４４０内では、逆多重化装置（Ｄｅｍｕｘ）５１０が、パケットの入力ＬＬＲを受け取り、入力ＬＬＲを、データビットｘのＬＬＲ Ｘ、第１パリティビットｙのＬＬＲ Ｙ、および第２パリティビットｚのＬＬＲ Ｚに逆多重化する。ソフト入力ソフト出力（soft-input soft-output：ＳＩＳＯ）復号器５２０ａは、データビットＬＬＲ Ｘおよび第１パリティビットＬＬＲ Ｙを逆多重化装置５１０から、ならびにデインタリーブされたデータビットＬＬＲ Ｘ２をターボデインタリーバ５４０から受け取ることができる。ＳＩＳＯ復号器５２０ａは、第１成分コードに基づいて、データビットの新しいＬＬＲ Ｘ１を導出することができる。ターボインタリーバ５３０は、図３のターボインタリーバ３２０に使用されるターボインタリーバ関数に基づいてデータビットＬＬＲ Ｘ１をインタリーブし、インタリーブされたデータビットＬＬＲ] 図３ 図４ 図５
[0026] を提供することができる。ＳＩＳＯ復号器５２０ｂは、データビットＬＬＲ Ｘおよび第２パリティビットＬＬＲ Ｚを逆多重化装置５１０から、ならびにインタリーブされたデータビットＬＬＲ]
[0027] をターボインタリーバ５３０から受け取ることができる。ＳＩＳＯ復号器５２０ｂは、第２成分コードに基づいて、データビットの新しいＬＬＲ]
[0028] を導出することができる。ターボデインタリーバ５４０は、ターボインタリーバ関数の逆に基づいてデータビットＬＬＲ]
[0029] をデインタリーブし、デインタリーブされたデータビットＬＬＲ Ｘ２を提供することができる。]
[0030] ＳＩＳＯ復号器５２０ａおよび５２０ｂは、ＢＣＪＲＭＡＰアルゴリズムまたはより少ない複雑さの派生物を実施することができる最大事後確率（maximum a posteriori：ＭＡＰ）復号器とすることができる。ＳＩＳＯ復号器５２０ａおよび５２０ｂは、ソフト出力ビタビ（ＳＯＶ）アルゴリズムまたは当技術分野で既知のある他の復号アルゴリズムを実施することもできる。ＳＩＳＯ復号器５２０ａおよび５２０ｂによる復号を、複数回、たとえば、６回、８回、１０回、またはより多い回数だけ反復することができる。復号結果は、各反復の後により信頼できるものである可能性がある。すべての復号反復が完了した後に、検出器５６０が、ＳＩＳＯ復号器５２０ａから最終データビットＬＬＲを受け取り、各ＬＬＲに対する硬判定を行い、復号されたビットを提供することができる。]
[0031] 図２のチャネルインタリーバ２５０を、ビット逆転インタリーバ（ＢＲＩ）、プルーンビット逆転インタリーバ（ＰＢＲＩ）、その他など、さまざまな設計を用いて実施することができる。ＢＲＩは、ｙのｎビットがｘのｎビットに関して逆順で現れるように、ビット逆転ルールに従って、ｎビット線形アドレスｘをｎビットのインタリーブされたアドレスｙにマッピングする。ｎビット線形アドレスｘのＢＲＩマッピングは、次のＢＲＩ関数によって指定することができる。] 図２
[0032] ここで、πｎ（）は、ＢＲＩ関数である。アドレスｘおよびｙは、０からＭ−１までの範囲内の値を有し、ここで、Ｍ＝２ｎは、ＢＲＩのサイズであり、２のべきである。任意の線形アドレスｘを、ｘのｎビットを反転することと反転されたｎビットをｙとして使用することとによって、対応するインタリーブされたアドレスｙに簡単にマッピングすることができる。]
[0033] プルーンＢＲＩは、Ｌ未満、ただしＬ＜Ｍ、のｎビット線形アドレスｘを、ビット逆転ルールに従って、Ｌ未満のｎビットのインタリーブされたアドレスｙにマッピングする。しかし、プルーンＢＲＩのサイズは、Ｌであるが、母インタリーバのサイズは、Ｍである。Ｌは、パケットサイズと等しくすることができ、ＵＭＢについて１２８から１３６８４までの範囲内にあるものとすることができる。アドレスＬからＭ−１までは、プルーンＢＲＩ関数によって切り詰められ、有効なマッピングとは考えられない。パラメータＬを有するｎビット線形アドレスｘに対するプルーンＢＲＩマッピングは、次のプルーンＢＲＩ関数によって指定することができる。]
[0034] ここで、βｎ，Ｌ（）は、プルーンＢＲＩ関数である。アドレスｘおよびｙは、０からＬ−１までの範囲内の値を有し、Ｌは、プルーンＢＲＩのサイズであり、２のべきではない。]
[0035] 所与のｘに関するマッピングｙ＝βｎ，Ｌ（ｘ）は、ｉ＝０から開始し、途中でスキップされる無効なマッピングの個数φ（ｘ）を維持することによって、シーケンシャルに決定することができる。φ（ｘ）を、０に初期化することができる。ｉ＋φ（ｘ）が、有効なインタリーブされたアドレスにマッピングされ、その結果、πｎ（ｉ＋φ（ｘ））＜Ｌになる場合には、ｉを１つだけ増分することができる。そうではなく、ｉ＋φ（ｘ）が無効なインタリーブされたアドレスにマッピングされる場合には、φ（ｘ）を１つ増分することができる。この動作は、ｉがｘに達し、πｎ（ｉ＋φ（ｘ））が有効になるまで繰り返すことができる。]
[0036] アルゴリズム１とも称するシーケンシャルプルーンＢＲＩアルゴリズムを、下の擬似コードを用いてインプリメントすることができる。]
[0037] アルゴリズム１は、本質的に、（ｉ）ｉ＝０から開始してＭ個の線形アドレスをトラバースし、（ｉｉ）各線形アドレスｉのインタリーブされたアドレスを決定することによって、Ｍ個のインタリーブされたアドレスの完全なリストを生成する。次に、この完全なリストは、Ｌ個のインタリーブされたアドレスの切り詰められたリスト（pruned list）を得るために、Ｌ以上のインタリーブされたアドレスを削除することによって切り詰められる。次に、線形アドレスｘが、切り詰められたリスト内のｘ番目のインタリーブされたアドレスにマッピングされる。]
[0038] 表１に、Ｌ＝１９およびＭ＝３２の場合の例のＢＲＩマッピングおよび例のプルーンＢＲＩマッピングを与える。表１では、「１０進」列は、１０進表現でのアドレスを与え、「２進」列は、２進表現でのアドレスを与える。例として、線形アドレスｘ＝７は、ＢＲＩマッピングを用いるとインタリーブされたアドレスｙ＝２８にマッピングされ、プルーンＢＲＩマッピングを用いるとインタリーブされたアドレスｙ＝１０にマッピングされる。無効なマッピングは、最後の２つの列で「ｘ」と表される。]
[0039] アルゴリズム１が、０からＬ−１までの範囲内のＬ個の線形アドレスを０からＬ−１までの範囲内のＬ個のインタリーブされたアドレスにマッピングするのにＭ−１回の反復を実行することを示すことができる。アルゴリズム１は、０からＬ−１までの範囲内の線形アドレスをマッピングする時に、Ｌの値とは独立に、範囲または０から２ｎ−１まで内のＭ個すべての線形アドレスをトラバースし、その過程でＭ−Ｌ−１個の無効なマッピングを切り詰める。したがって、プルーンＢＲＩの複雑さは、母インタリーバＭのサイズによって決定され、プルーンＢＲＩのサイズによって決定されるのではない。]
[0040] シーケンシャルプルーンＢＲＩアルゴリズムの主な不利益は、インタリーブされたアドレスがシーケンシャルに生成されることである。具体的に言うと、線形アドレスｘに対応するインタリーブされたアドレスｙを決定するために、ｘ未満のすべての線形アドレスのインタリーブされたアドレスが、まず決定される。これは、ｘをどこにマッピングすべきかを知るために、ｘの前のプルーンマッピングの回数を知らなければならないという事実から得られる。このシーケンシャルアドレス生成は、特に、たとえばＵＭＢで使用される１６キロビット（１６Ｋ）サイズの、インタリービング／デインタリービングおよびターボ符号化／復号ロングパケットの時に、遅延ボトルネックを導入する可能性がある。]
[0041] 一態様では、多くともｌｏｇ２（ｘ−１）ステップで線形アドレスｘのインタリーブされたアドレスｙを決定できる効率的なプルーンＢＲＩアルゴリズムを、本明細書で説明する。効率的なプルーンＢＲＩアルゴリズムは、基本的な論理ゲートを使用して実施できる単純なアーキテクチャを有し、さらに、短いクリティカルパス遅延を有することができる。]
[0042] 次の説明では、プルーンＢＲＩのサイズＬを、]
[0043] として与えることができると仮定する。式（３）の条件が満足されない場合には、プルーンＢＲＩを、ＭがＬ以上の最小の２のべきになるように再定式化することができる。さらに、Ｌ＝Ｍの場合に、ｘのすべての値についてφ（ｘ）＝０であり、βｎ，Ｌ（ｘ）＝πｎ（ｘ）である。この場合に、すべての線形アドレスが有効なマッピングを有するので、プルーンされるアドレスはない。したがって、下の説明では、式（３）で定義されたＬを仮定する。]
[0044] ビット逆転演算の定義および式（３）に示された条件から、πｎ（ｘ）≧Ｌの場合には、πｎ（ｘ＋１）＜Ｌになる。したがって、２つの連続する線形アドレスが、両方とも無効なマッピングを有することはできない。この事実を使用して、次のように、０≦ｘ＜Ｌについて、φ（ｘ）の再帰的定義を得ることができる。]
[0045] さらに、ｉ＞ｘの場合に、φ（ｉ）≧φ（ｘ）である。したがって、φ（）は、非減少関数である。]
[0046] アルゴリズム１の複雑さは、ＭのオーダーすなわちＯ（Ｍ）である。これは、どのインタリーブされたアドレスをｘにマッピングすべきかを確かめるために、ｘ未満のすべての線形アドレスをマッピングする際に発生した無効なマッピングの個数φ（ｘ）が、まず決定されるという事実から得られる。複雑さＯ（ｎ）を有し、ｎ＝ｌｏｇ２（Ｍ）である、φ（ｘ）を決定するアルゴリズムは、無効なマッピングのビット構造を分析することによって導出することができる。]
[0047] 量φ（ｘ）は、０からｘまでのすべての線形アドレスが有効なマッピングを有するように、スキップすべき無効なマッピングの最小個数を表す。同等に、φ（ｘ）は、０からｘ＋φ（ｘ）までの範囲内の正確にｘ＋１個の線形アドレスが有効なマッピングを有するように、ｘに加算すべき最小の数を表す。]
[0048] 図６に、所与の線形アドレスｘのφ（ｘ）の反復決定を示す。０からｘ（１）＝ｘまでの範囲内の無効なマッピングを有する線形アドレスの個数を、σ（１）（ｘ）＝σ（ｘ）と表すことができる。φ（ｘ）は、必ずしもσ（１）（ｘ）と等しくはなく、φ（ｘ）≧σ（１）（ｘ）として与えることができる。これは、０からｘまでの範囲内の無効なマッピングを有するσ（１）（ｘ）個の線形アドレスについて、ｘより大きいさらに少なくともσ（１）（ｘ）個の線形アドレスが、有効なマッピングを有するかどうかを調べるためにチェックされなければならないという事実から得られる。] 図６
[0049] したがって、φ（ｘ）は、少なくとも、０からｘ（２）＝ｘ＋σ（１）（ｘ）までの範囲内の無効なマッピングの個数と等しい。無効なマッピングを有する、０からｘ（２）までの範囲内の線形アドレスの個数を、σ（２）（ｘ）＝σ（ｘ＋σ（１）（ｘ））と表すことができる。ｘ（１）＋１からｘ（２）までの線形アドレスは、考慮に入れなければならない無効なマッピングを有する可能性がある。したがって、φ（ｘ）は、少なくとも、０からｘ（３）＝ｘ＋σ（２）（ｘ）までの範囲内の無効なマッピングの個数と等しい。ｘ（２）＋１からｘ（３）までの線形アドレスは、考慮に入れなければならない無効なマッピングを有する可能性がある。]
[0050] 一般に、０からｘ（ｋ）までの範囲内の、無効なマッピングを有する線形アドレスの個数を、σ（ｋ）（ｘ）＝σ（ｘ＋σ（ｋ−１）（ｘ））と表すことができ、ここで、ｋは反復のインデックスである。このプロセスは、]
[0051] として与えることができる、０からｘ（Ｋ＋１）＝ｘ＋σ（Ｋ）（ｘ）までの範囲が正確にｘ＋１個の有効なマッピングを含むまで、あるいは、同等に、]
[0052] まで、Ｋ＋１回の反復だけ繰り返すことができる。式（５）または（６）の条件が満足される時に、φ（ｘ）＝σ（Ｋ＋１）（ｘ）である。Ｋ＋１は、式（５）または（６）が満足されるようになる反復の最小回数であり、ｘの値に依存する可能性がある。]
[0053] アルゴリズム２とも称する、σ（ｋ）（ｘ）を反復的に使用してφ（ｘ）を計算するアルゴリズムを、下の擬似コードを用いて実施することができる。]
[0054] アルゴリズム２が、φ（ｘ）を多くともｎ−１回の反復に集束でき、その結果、Ｋ＜ｎ−１になることを示すことができる。]
[0055] φ（ｘ）を決定するという問題は、反復ｋごとにσ（ｋ）（ｘ）を決定するという問題に還元され、ここで、σ（ｋ）（ｘ）は、０からｘ（ｋ）＝ｘ＋σ（ｋ−１）（ｘ）までの範囲内の無効なマッピングの個数である。単純にするために、次の説明では、σ（ｋ）（ｘ）とｘ（ｋ）との両方から反復インデックスｋを省略し、これらを、それぞれ単純にσ（ｘ）およびｘと表す場合がある。σ（ｘ）は、ＬとＭ−１との間の無効なアドレスのビット表現を調査することによって決定することができる。ｘ＜２ｎの２進表現を、次式として表すことができ、]
[0056] ここで、ｘｎ−１は、最上位ビット（ＭＳＢ）であり、ｘ０は、最下位ビット（ＬＳＢ）である。表記ｘ［ｉ：ｊ］は、ＭＳＢからＬＳＢへ並べられた連続するビットｘｉ，ｘｉ−１，…，ｘｊの集合を表すものとすることができる。２つのビット列ｘ［ｉ１：ｊ１］およびｘ［ｉ２：ｊ２］の連結を、ｘ［ｉ１：ｊ１］｜ｘ［ｉ２：ｊ２］として表すことができる。]
[0057] ＬとＭ−１との間のアドレスを、次のようにＬ−１のビット表現に従ってそのＭＳＢによってグループ化することができる。Ｌ−１のビット表現の０ビットの個数を、ｚと表すことができる。ＭＳＢからＬＳＢへ並べられた、Ｌ−１のビット表現の０ビットのインデックスの集合を、Ｉ’と表すことができる。たとえば、Ｌ−１＝１０１０１００（２進数）の場合に、ｚ＝４およびＩ’＝｛５，３，１，０｝である。ＬからＭ−１までのアドレスまたは１０１０１０１≦ｘ≦１１１１１１１を、次のようにｚ＝４個のクラスにグループ化することができる。]
[0058] ・Ｃ’１：１１ｘｘｘｘｘ： １６個の整数、
・Ｃ’２：１０１１ｘｘｘ： ８個の整数、
・Ｃ’３：１０１０１１ｘ： ２個の整数、および
・Ｃ’４：１０１０１０１： １個の整数。]
[0059] この４つのクラスを定義するＭＳＢは、Ｌ−１のビット表現を左から右へスキャンし、０ビットを探索することによって決定することができる。第１のクラスＣ’１のＭＳＢは、最初の０までの、最初の０を１に反転した、Ｌ−１のＭＳＢに対応する。第２のクラスＣ’２のＭＳＢは、２番目の０までの、２番目の０を１に反転した、Ｌ−１のＭＳＢに対応する。各残りのクラスのＭＳＢは、同様の形で入手される。ｚ個のクラスのそれぞれの最小の数を、次式として表すことができる。]
[0060] ここで、]
[0061] は、次に小さい整数値を与えるフロア演算子である。]
[0062] 各クラスを、その最小の数δ’ｉによって指定することができる。Ｌ−１＝１０１０１００の上の例について、４つのクラスのそれぞれの最小の数を、δ’１＝１１０００００、δ’２＝１０１１０００、δ’３＝１０１０１１０、およびδ’４＝１０１０１０１として与えることができる。]
[0063] ビット逆転された時に無効になる整数の集合は、σ（ｘ）の決定において重要である。これらの整数は、ビット逆転された順序ではあるが、上で定義されたクラスに属する。ビット逆転順での無効な整数のクラスを、δｉ＝πｎ（δ’ｉ）ただしｉ＝１，２，…，ｚと表すことができ、対応するクラスをＣｉと表すことができる。ＬＳＢからＭＳＢへ並べられたπｎ（Ｌ−１）の０ビットのインデックスの集合を、Ｉと表すことができる。したがって、ｘ∈Ｃｉの場合に、πｎ（ｘ）≧Ｌおよびｘ［Ｉ（ｉ）：０］≧δｉ［Ｉ（ｉ）：０］であり、ここで、Ｉ（ｉ）は、集合Ｉの第ｉ要素である。Ｌ−１＝１０１０１００の上で与えた例について、πｎ（Ｌ−１）＝００１０１０１、ｚ＝４、およびＩ＝｛１，３，５，６｝である。ビット逆転された順序での無効な整数の４つのクラスを、次のように与えることができる。]
[0064] ・Ｃ１：ｘｘｘｘｘ１１： δ１＝０００００１１、
・Ｃ２：ｘｘｘ１１０１： δ２＝０００１１０１、
・Ｃ３：ｘ１１０１０１： δ３＝０１１０１０１、および
・Ｃ４：１０１０１０１： δ４＝１０１０１０１。]
[0065] ０からｘまでの範囲内の無効なマッピングの個数σ（ｘ）は、各クラスＣｉ、ただしｉ＝１，２，…，ｚの無効なマッピングの個数を数えることによって決定することができる。クラスＣｉの無効なマッピングの個数を、σｉ（ｘ）と表すことができ、これは、次を使用して決定することができる。]
[0066] ・δｉ、
・ｉ番目の０ビットの左までのｘのＭＳＢすなわちｘ［ｎ−１：Ｉ（ｉ）＋１］、および
・ｉ番目の０ビットを含むｘの残りのＬＳＢすなわちｘ［Ｉ（ｉ）：０］。]
[0067] ｘ［ｎ−１：Ｉ（ｉ）＋１］によって与えられるｘのｎ−Ｉ（ｉ）−１個のＭＳＢは、ｘの前に現れたＣｉに属する整数の個数を表す。これらの整数は、δｉと同一であるがｘ［ｎ−１：Ｉ（ｉ）＋１］｜δｉ［Ｉ（ｉ）：０］未満のＩ（ｉ）＋１個のＬＳＢを有する。ｘ［Ｉ（ｉ）：０］によって与えられるｘのＩ（ｉ）＋１個のＬＳＢは、ｘ≧ｘ［ｎ−１：Ｉ（ｉ）＋１］｜δｉ［Ｉ（ｉ）：０］であるかどうか、または、これと同等に、ｘ［Ｉ（ｉ）：０］≧δｉ［Ｉ（ｉ）：０］であるかどうかをチェックするのに使用することができる。これは、ｘ自体がＣｉに含まれる無効な整数にマッピングされるかどうか、または、ｘがＣｉに含まれる最後の無効な整数より大きい整数にマッピングされるかどうかをチェックする。どちらの場合でも、σｉ（ｘ）を１つ増分することができる。数学的には、σｉ（ｘ）を、]
[0068] と表すことができる。]
[0069] σ（ｘ）は、ｚ個のクラスのすべてのσｉ（ｘ）の合計と等しく、]
[0070] と表すことができる。]
[0071] アルゴリズム３とも称する、式（９）および（１０）を使用してσ（ｘ）を計算するアルゴリズムを、下の擬似コードを用いて実施することができる。]
[0072] ｚ＝Ｌ−１のビット表現内の０ビットの個数
Ｉ＝ＬＳＢからＭＳＢへの、Ｌ−１のビット表現内の０ビットのインデックスの集合]
[0073] 図７に、Ｌ−１＝１０１０１００、ｘ＝１００１１０１、πｎ（Ｌ−１）＝００１０１０１、ｚ＝４、およびＩ＝｛１，３，５，６｝の例に関するσ（ｘ）の計算を示す。ビット逆転された順序での無効な整数の４つのクラスＣ１からＣ４は、上で与えられる。] 図７
[0074] ｉ＝１について、δ１＝０００００１１およびＩ（１）＝１である。したがって、ｘ［６：２］＝１００１１、ｘ［１：０］＝０１、およびδ１［１：０］＝１１である。ｘ［１：０］＜δ１［１：０］なので、σ１（ｘ）＝ｘ［６：２］＝１００１１＝１９（１０）であり、ここで、「（１０）」は、１０進表現を表す。]
[0075] ｉ＝２について、δ２＝０００１１０１およびＩ（２）＝３である。したがって、ｘ［６：４］＝１００、ｘ［３：０］＝１１０１、およびδ２［３：０］＝１１０１である。ｘ［３：０］＝δ２［３：０］なので、σ２（ｘ）＝ｘ［６：４］＋１＝１０１＝５（１０）である。]
[0076] ｉ＝３について、δ３＝０１１０１０１およびＩ（３）＝５である。したがって、ｘ［６］＝１、ｘ［５：０］＝００１１０１、およびδ３［５：０］＝１１０１０１である。ｘ［５：０］＜δ３［５：０］なので、σ３（ｘ）＝ｘ［６］＝１＝１（１０）である。]
[0077] ｉ＝４について、δ４＝１０１０１０１およびＩ（４）＝６である。したがって、ｘ［６：０］＝１００１１０１およびδ４［６：０］＝１０１０１０１である。ｘ［６：０］＜δ４［６：０］なので、σ４（ｘ）＝０＝０（１０）である。次に、σ（ｘ）を１９＋５＋１＋０＝２５（１０）として計算することができる。]
[0078] 上で注記したように、φ（ｘ）を反復的に決定することができる。最初の反復ｋ＝１について、σ（１）（ｘ）を、上で説明したように線形アドレスｘについて決定することができる。次の反復ｋ＝２について、ｘ（２）を得るために、σ（１）（ｘ）をｘと合計することができる。次に、上で説明したように、ｘ（２）についてσ（２）（ｘ）を決定することができる。σ（Ｋ＋１）（ｘ）＝σ（Ｋ）（ｘ）になるまで、Ｋ＋１回の反復を実行することができる。その後、φ（ｘ）を、σ（Ｋ＋１）（ｘ）と等しくなるようにセットすることができる。]
[0079] パラメータＬを伴うプルーンＢＲＩマッピングｙ＝βｎ，Ｌ（ｘ）に基づく線形アドレスｘのインタリーブされたアドレスｙを、次のように決定することができる。まず、中間アドレスｖを、]
[0080] として計算することができ、ここで、φ（ｘ）は、上で説明したように、σ（ｋ）（ｘ）に基づいて反復的に決定することができる。]
[0081] 次に、インタリーブされたアドレスｙを、次のように、中間アドレスｖにＢＲＩマッピングを適用することによって決定することができる。]
[0082] 図８に、ｎ＝８の場合のプルーンＢＲＩのアドレスジェネレータ８００の設計のブロック図を示す。Ｌ−１のビット表現は、最大ｎ−１個の０ビットを含む。論理回路８１０は、Ｌ−１を受け取り、ｎ−１個の出力δｉ［ｉ：０］、ただしｉ＝１，…，ｎ−１を生成する。論理回路８１０は、δｉ［ｉ：０］出力が有効であるか否かを示すために、δｉ［ｉ：０］出力ごとにイネーブル信号ｅｎｉをも生成する。] 図８
[0083] ｎ−１個の比較器８１２ａから８１２ｇのセットが、論理回路８１０からのｎ−１個のδｉ［ｉ：０］出力およびｋ回目の反復の線形アドレスｘ（ｋ）から得られたやはりｎ−１個のｘ（ｋ）［ｉ：０］入力を受け取る。各比較器８１２は、そのｘ（ｋ）［ｉ：０］をそのδｉ［ｉ：０］と比較し、ｘ（ｋ）［ｉ：０］がδｉ［ｉ：０］未満である場合には０（たとえば、論理ロウ）を供給し、そうでない場合には１（たとえば、論理ハイ）を供給する。]
[0084] １ビット全加算器のバンク８２０が、線形アドレスｘ（ｋ）および比較器８１２の出力に基づいて、反復ｋごとにσ（ｋ）（ｘ）を計算する。バンク８２０は、ｎ−２個のδｉ［ｉ：０］出力のためのｎ−２行の加算器８２２ａから８２２ｆを含む。加算器８２２の各行は、ｘ［ｎ−１：ｉ＋１］および加算器の先行する行（存在する場合に）からの出力を受け取る。加算器８２２の各行は、関連する比較器８１２が論理ロウを供給する場合にはσｉ（ｘ）＝ｘ［ｎ−１：ｉ＋１］を、あるいは、関連する比較器８１２が論理ハイを供給する場合にはσｉ（ｘ）＝ｘ［ｎ−１：ｉ＋１］＋１を生成する。加算器８２２の各行は、ｅｎｉ信号が論理ロウの場合には先行する行からの出力を渡し、ｅｎｉ信号が論理ハイの場合には先行する行からの出力をσｉ（ｘ）と合計する。]
[0085] ｎ−２行の加算器８２２ａから８２２ｆは、集合的に、ｎ−２個の比較器８１２ａから８１２ｆからの制御信号に依存して、ｘ（ｋ）の右シフトされたコピー（σｉ（ｘ）である）を累算することによってアルゴリズム３を実施し、ここで、ｘ（ｋ）＝ｘ＋σ（ｋ−１）（ｘ）が、ｋ回目の反復について加算器の行に入力される。加算器８２２の各行は、ｅｎｉ信号が論理ハイの場合に、σｉ（ｘ）を加算器の先行する行からの出力と累算する。加算器の最後の行８２２ｆは、すべての反復が完了した後にφ（ｘ）と等しくなるσ（ｋ）（ｘ）を供給する。]
[0086] 各１ビット全加算器は、線形アドレスｘ（ｋ）からの第１入力ビット、上の別の加算器からの第２入力ビット、左の別の加算器からのキャリーインビット、および論理ユニット８１０からのｅｎｉ信号を受け取る。各加算器は、３つの入力ビットを合計し、下の加算器に合計ビットを、右または下の加算器にキャリーアウトビットを供給する。ｅｎｉ信号がデアサートされている場合には、第１入力ビットがゼロにされる。]
[0087] 各比較器８１２は、ｘ［ｉ：０］≧δｉ［ｉ：０］の場合には１、そうでない場合には０を生成する。各比較器８１２は、その出力をキャリーインビットとして同一行内の最初の加算器に供給する。これは、ｘ［ｉ：０］≧δｉ［ｉ：０］の場合に選択的にσｉ（ｘ）に１を加算する。最後の行８２４内の加算器は、δｎ−１（ｘ）≧Ｌ−１の場合にσｎ−１（ｘ）に１を加算することに対応する出力を生成する。δｎ−１（ｘ）の最大値はＬ−１なので、同等比較器８１２ｇが十分である。]
[0088] 加算器の最後の行８２２ｆからの出力は、ｋ回目の反復のσ（ｋ）（ｘ）に対応する。最初の反復について、ｘは、加算器バンク８２０に供給される。各後続の反復について、加算器の行８２４は、次の反復ｋ＋１の新しい線形アドレスとして供給されるｘ（ｋ＋１）＝ｘ＋σ（ｋ）（ｘ）を得るために、加算器の最後の行８２２ｆからのσ（ｋ）（ｘ）とｘを合計する。]
[0089] 加算器バンク８２０の出力を、φ（ｘ）を読み取るためにｎ−１クロックサイクルおきに標本化することができる。比較器を、早期終了のためにσ（ｋ）（ｘ）およびσ（ｋ＋１）（ｘ）を比較するために追加することができる（図８には図示せず）。加算器の行８２４は、式（１１）に示されているように、加算器の最後の行８２２ｆからのφ（ｘ）を線形アドレスｘと合計し、中間アドレスｖを供給する。ＢＲＩユニット８２６は、ｖを受け取り、式（１２）に示されているように、プルーンＢＲＩのインタリーブされたアドレスｙとしてｖのビット逆転を供給する。] 図８
[0090] 図８に示された設計について、クリティカルパス遅延は、重要なｎのほとんどの値について現在の集積回路（ＩＣ）プロセステクノロジによって満足できる２ｎ−２ステージである。比較器８１２は、ＸＯＲツリーを用いて実施することができ、無視できる遅延を導入することができる。] 図８
[0091] 図９に、図８の論理回路８１０の設計のブロック図を示す。論理回路８１０内では、ビット逆転ユニット９１０が、Ｌ−１を受け取り、ビット逆転されたＬ−１を供給する。ｎ−１個のユニット９１２ａから９１２ｇは、ビット逆転されたＬ−１を受け取り、ｎ−１個の出力δ１［１：０］からδ７［７：０］をそれぞれ生成する。δｉ［ｉ：０］出力のためのユニット９１２ｉ内では、インバータ９１６が、ビット逆転されたＬ−１の第ｉビットを受け取り、δｉ［ｉ：０］出力のｅｎｉ信号を供給する。ｅｎｉ信号は、第ｉビットが０の場合に論理ハイであり、そうでない場合に論理ロウである。ユニット９１２ｉは、図８の関連する比較器８１２へのδｉ［ｉ：０］出力としてインバータ９１６の出力ならびにビット０からｉ−１までを供給する。ＡＮＤゲート９１８は、ビットｉ＋１からｎ−１までを０にする。] 図８ 図９
[0092] 図１０に、アルゴリズム２に基づくルックアヘッドプルーンＢＲＩのアドレスジェネレータ１０００の設計のブロック図を示す。長さＮのパケットを、長さＬのＰ個のサブパケットに区分することができ、ここで、Ｌ、Ｐ、およびＮは、それぞれ、任意の適切な整数とすることができる。各サブパケットを、独立にインタリーブすることができる。Ｐ−１個のブロック１０１０ｂから１０１０ｐは、それぞれ、サブパケット１からＰ−１の無効なマッピングの個数を計算する。サブパケットｊのブロック１０１０は、φ（ｊ・Ｌ−１）、ただしｊ＝１，…，Ｐ−１と表される、０からｊ・Ｌ−１までの範囲内の無効なマッピングの個数を計算する。Ｐ−１個のコンポーネントプルーンＢＲＩ １０２０ｂから１０２０ｐは、それぞれブロック１０１０ｂから１０１０ｐからφ（ｊ・Ｌ−１）を受け取ることができる。コンポーネントプルーンＢＲＩ １０２０ａは、φ（０）の０を受け取ることができる。コンポーネントプルーンＢＲＩ １０２０ごとに、φ（ｊ・Ｌ−１）を、サブパケットｊをインタリーブするためのプルーンＢＲＩを初期化するのに使用することができる。] 図１０
[0093] ある設計では、シーケンシャルプルーンＢＲＩアルゴリズム（たとえば、アルゴリズム１）を、コンポーネントプルーンＢＲＩ １０２０ごとに使用することができる。別の設計では、各コンポーネントプルーンＢＲＩ １０２０は、２Ｌ個の加算器、２Ｌ個の比較器、多重化装置、および制御論理を使用して、Ｌ個の整数を並列にインタリーブすることができる。並列設計は、小さい値のＬ、たとえば１６までのＬに適切とすることができる。]
[0094] 図１０に示された設計は、長さＬのサブパケットについて、２Ｌ個の整数にまたがる範囲内に多くともＬ個の無効なマッピングがありえるという事実を活用するものである。したがって、第ｊコンポーネントプルーンＢＲＩは、Ｌ個の整数ｊ・Ｌから（ｊ＋１）・Ｌ−１を、範囲ｊ・Ｌ＋φ（ｊ・Ｌ−１）からｊ・Ｌ＋φ（ｊ・Ｌ−１）＋２Ｌ−１までの最初のＬ個の有効なインタリーブされたアドレスにマッピングする。コンポーネントプルーンＢＲＩは、２Ｌ個の合計ｊ・Ｌ＋φ（ｊ・Ｌ−１）からｊ・Ｌ＋φ（ｊ・Ｌ−１）＋２Ｌ−１を計算し、それらが有効なアドレスであるかどうかを決定するためにそのビット逆転された値をＮ−１と比較し、有効なアドレスを多重化装置に渡す。図１０のルックアヘッドプルーンＢＲＩは、完全シーケンシャルプルーンＢＲＩに対して、直列コンポーネントプルーンＢＲＩを使用してＰ倍、並列コンポーネントプルーンＢＲＩを使用してＬ倍だけ高い動作速度を有することができる。しかし、ルックアヘッドプルーンＢＲＩの複雑さは、Ｌのより大きい値に関してすばやく増える。] 図１０
[0095] 系統的フィードバック成分畳込み符号器と共に使用される時に符号語の乱数様重みスペクトルを作るために、ターボインタリーバをターボ符号器（たとえば、図３に示された）内で使用することができる。ターボインタリーバは、第１成分符号器３１０ａからの低重みパリティシーケンスを第２成分符号器３１０ｂからの高重みパリティシーケンスと対にすることによって、入力シーケンス内のパターンを壊す。ターボインタリーバは、線形アドレスのシーケンスを２Ｄ配列に一方の方向で（たとえば、行ごとに）書き込み、次に行エントリおよび列エントリに独立擬似乱数置換を適用し、次にシャッフルされたアドレスを他方の方向（たとえば、列ごとに）で読み取る、ブロックインタリーバに基づくものとすることができる。配列の各行内のエントリに適用される置換は、線形合同シーケンスに基づくものとすることができる。配列の各列内のエントリに適用される置換は、チャネルインタリーバで使用されるものに似たビット逆転関数に基づくものとすることができる。可変パケットサイズに対処するために、ターボインタリーバについて切り詰め（pruning）を使用することができる。] 図３
[0096] １つの設計で、ターボインタリーバを、次のように実施することができる。まず、小さい正の整数ｒを、ターボインタリーバのメモリバンクアーキテクチャに基づいて選択することができる。たとえば、ターボインタリーバメモリが３２行について２ｒ＝３２個のバンクからなるようにするために、ｒを５と等しい（ＵＭＢと同様に）ものとすることができる。次に、最小の正の整数ｎを、Ｌ≦２ｒ＋ｎになるように決定する。これは、Ｌ個のエントリを保持できる最小サイズの２ｒ×２ｎ配列を見つけることと同等である。この配列内の行の個数は、２ｒによって与えられ、この配列内の列の個数は、２ｎによって与えられる。]
[0097] ２ｒ行および２ｎ列を有する配列を、行ごとに上から下へ、０からＭ−１までの線形アドレスのシーケンスによって充てんすることができ、ここで、Ｍ＝２ｒ・２ｎである。次に、この配列のＭ個のエントリを、下で説明するようにシャッフルすることができる。次に、Ｍ個のシャッフルされたエントリを、線形アドレスのシーケンスに対応するインタリーブされたアドレスのシーケンスを得るために、列ごとに左から右に読み取ることができる。]
[0098] この配列のエントリを、２ｒ個の行の順序を置換し、各行の２ｎ個のエントリに独立の置換を適用することによってシャッフルすることができる。２ｒ個の行を、ビット逆転された順序でシャッフルすることができる。行シャッフリングの結果は、インタリーブされた行のセットである。各行の２ｎ個のエントリを、行インデックスおよびｎに基づくルックアップテーブル（ＬＵＴ）を使用してそのパラメータを決定できる線形合同シーケンス（ＬＣＳ）再帰を使用して独立にシャッフルすることができる。ＬＣＳ動作の結果は、行ごとのインタリーブされた列値のセットである。ＬＣＳ動作および行置換の順序を、入れ替えることもできる。最後に、線形アドレスの順序に関して反対の順序でインタリーブされた列値および行値を組み合わせることによって、インタリーブされたアドレスを得ることができる。最後のステップは、配列が充てんされた（たとえば、行ごと）のと反対の順序（たとえば、列ごと）で配列内のインタリーブされたエントリを読み取ることによって達成することができる。各インタリーブされたエントリは、インタリーブされたアドレスを含む。インタリーブされたアドレスが、Ｌ以上である場合に、そのアドレスを切り詰めることができる。]
[0099] 例のターボインタリーバのインタリーブされたアドレスの生成を、下で説明する。この例では、ｒ＝ｎ＝３およびＭ＝２６＝６４である。０から６３までの６ビット線形アドレスを、表２に示されているように、２３×２３配列に行ごとに書き込むことができる。Ｌ＝４４の例に関して、有効な線形アドレス０から４３までが、表２では太字のテキストで示され、無効な線形アドレス４４から６３までが、通常のテキストで示されている。]
[0100] この配列の８行を、ビット逆転された順序でシャッフルすることができる。表３に、行置換の後のこの配列内のエントリを示す。]
[0101] 各行内のエントリを、ＬＣＳ再帰に基づいてシャッフルすることができる。たとえば、８行の８ ＬＣＳ再帰の法を、５、７、５、７、１、１、１、および７とすることができる。各行のＬＣＳ再帰は、下で説明するように実行することができる。表４に、ＬＣＳ再帰の後の各行のシャッフルされたエントリを示す。]
[0102] 次に、インタリーブされたアドレスを、列ごとに読み取ることができる。切り詰めがなければ、インタリーブされたアドレスのシーケンスを、５、３９、２１、５５、９、４１、２５、６３、２などとして与えることができる。Ｌ＝４４以上のアドレスの切り詰めを用いると、インタリーブされたアドレスのシーケンスを、５、３９、２１、９、４１、２５、２などとして与えることができる。]
[0103] （ｒ＋ｎ）ビットのインタリーブされたアドレスｙへの（ｒ＋ｎ）ビット線形アドレスｘのマッピングは、次のターボインタリーバ関数によって指定することができる。]
[0104] ここで、ρｒ，ｎ（）は、ターボインタリーバ関数である。]
[0105] 切り詰めなしのターボインタリーバ関数は、]
[0106] として表すことができ、ここで、πｒ（）は、ｒビットＢＲＩ関数であり、ＬＵＴは、ｎおきの２ｒ個のＬＣＳ再帰の法を格納するルックアップテーブルである。]
[0107] 式（１４）は、インタリーブされたアドレスを２つの部分で提供する。第１部分は、所与の行内のすべての２ｎ個のエントリに適用可能な行値を提供するビット逆転関数２ｎ・πｒ（ｘ ｍｏｄ ２ｒ）によって決定される。第２部分は、０から２ｎ−１までの範囲内の列値を提供するＬＣＳ関数によって決定される。インタリーブされたアドレスは、行値と列値との合計をとることによって得られる。]
[0108] パラメータｒ＝ｎ＝３および切り詰めなしの上で説明した例のターボインタリーバについて、線形アドレスｘ＝０１０００１＝１７（１０）を、次のように式（１４）のターボインタリーバ関数に基づいて、インタリーブされたアドレスｙにマッピングすることができる。]
[0109] 式（１４）のターボインタリーバ関数を、切り詰めなしでインタリーブされたアドレスを生成するのに使用することができる。式（１４）によって生成されるインタリーブされたアドレスは、切り詰めを伴うと有効でない場合があり、０からｘまでの範囲内のすべての整数が、有効なマッピングを有するとは限らない。]
[0110] ０とｘとの間のすべての線形アドレスについて有効なインタリーブされたアドレスを生成できるプルーンターボインタリーバ関数を、]
[0111] と表すことができ、ここで、λｒ，ｎ（ｘ，Ｌ）は、プルーンターボインタリーバ関数であり、ｖは、０からｖまでの範囲が正確にｘ＋１個の有効なマッピングを含むようになる最小の整数である。]
[0112] Ｌ＝２ｒ＋ｎの場合に、プルーンアドレスはなく、ｖ＝ｘおよびλｒ，ｎ（ｘ，Ｌ）＝ρｒ，ｎ（ｘ）である。しかし、Ｌ＜２ｒ＋ｎの場合には、プルーンアドレスがあり、プルーンターボインタリーバ関数を、]
[0113] と表すことができ、ここで、ｖ＝ｘ＋τｒ，ｎ（ｘ，Ｌ）およびτｒ，ｎ（ｘ，Ｌ）は、０からｖまでの範囲が、ターボインタリーバ関数によってマッピングされる時に正確にｘ＋１個の有効なアドレスを含むようになる、ｘに加算される無効なマッピングの最小個数である。次に、τｒ，ｎ（ｘ，Ｌ）を決定できる場合に、プルーンターボインタリーバ関数を、このターボインタリーバ関数を用いて実施することができる。]
[0114] アルゴリズム４とも称するシーケンシャルプルーンターボインタリーバアルゴリズムを、下の擬似コードを用いて実施することができる。]
[0115] 式（１４）のターボインタリーバ関数は、ビット逆転関数とＬＣＳ関数との両方を含む。ビット逆転関数に関する無効なマッピングの個数は、プルーンＢＲＩに関して上で説明したように決定することができる。ＬＣＳ関数に関する無効なマッピングの個数は、下で説明するように決定することができる。ＬＣＳ関数の結果を、τｒ，ｎ（ｘ，Ｌ）を決定するためにビット逆転関数の結果と組み合わせることができる。]
[0116] 線形合同シーケンスを、次の再帰によって定義することができる。]
[0117] ここで、ｍ＞０は法であり、
ａは、０≦ａ＜ｍの乗数であり、
ｃは、０≦ｃ＜ｍの増分であり、
Ｙｉは、線形合同シーケンス内のｉ番目の要素である。]
[0118] ＬＣＳが、次の条件が満足される場合に限って、０とｍ−１との間のすべての整数を生成し、長さｍの全周期を有することを示すことができる。]
[0119] １．ｃおよびｍが互いに素であり、
２．（ａ−１）が、ｍのすべての素因子の倍数であり、
３．ｍが４の倍数である場合に、（ａ−１）が４の倍数である。]
[0120] ターボインタリーバの線形合同シーケンスは、たとえばＵＭＢの場合のように、ａ＝１およびｍ＝２ｎという固定パラメータを有することができる。増分ｃは、ルックアップテーブルに格納できる奇数定数とすることができる。このシーケンスの開始要素Ｙ０は、ｃまたはある他の値と等しくなるように選択することができる。この法ｍ、乗数ａ、および増分ｃの選択は、上で与えた３つの条件を満足する。したがって、線形合同シーケンスは、全周期を有する。この場合に、シーケンス要素をＸｉ＝ｓ（ｉ）によって与えることができ、ここで、ｓ（）は、次のように与えることができる。]
[0121] アドレスを、ｎビット加算器およびｎ×ｎ符号なし乗数を使用して、式（１８）に従ってハードウェアで生成することができる。]
[0122] 式（１８）を参照すると、重要なのは、式（１８）の下でのそのイメージが０とあるβ’との間にあり、α’≧０およびβ’≧０である、０とあるα’との間の整数の個数である。たとえば、α’を、ｘ＋１と等しいものとすることができ、β’を、プルーンインタリーバサイズＬと等しいものとすることができる。そのような整数の個数（すなわち、無効なマッピングの個数）は、式（１８）の値のシーケンスを通ってステップし、すべての０≦ｘ≦α’についてｓ（ｉ）をβ’と比較することによって、直接に数えることができる。無効なマッピングの個数を数えるこの直接法は、ｘに比例する複雑さを有する。ｌｏｇ２（ｘ）に比例する複雑さを有する、無効なマッピングの個数を効率的に数えることのできるアルゴリズムを、下で説明する。]
[0123] 整数の集合Ｉを、次のように定義することができる。]
[0124] 集合Ｉは、ＬＣＳ関数に基づく０とβ’との間の有効なマッピングを有する０からα’−１までのすべての数を含む。]
[0125] 集合Ｉの要素の個数は、｜Ｉ｜と表すことができ、]
[0126] として与えることができる。]
[0127] 集合Ｉの要素の個数は、式（２２）のＳ（ｃ，ｍ，α，β）の合計を決定することによって確かめることができる。この合計は、整数フロア関数を含み、閉形式表現を有しない。式（２２）は、フロア関数の代わりに「鋸歯（saw-tooth）」関数（（ｘ））を使用して表すことができる。鋸歯関数（（ｘ））は、]
[0128] として表すことができる。]
[0129] 一般化されたデデキンド和（Dedekind sum）ｄ（ｃ，ｍ，ｕ）を、次のように鋸歯関数を使用して定義することができる。]
[0130] 式（２２）を、次のように一般化されたデデキンド和を使用して表すことができる。]
[0131] ここで、ｃ１＝ｃ＋α・ｃ−β、ｃ２＝ｃ＋α・ｃ、ｃ３＝ｃ、ｃ４＝ｃ−β、およびＫは定数である。]
[0132] 式（２７）の４つのデデキンド和の組合せを、次のように多くともｌｏｇ２（ｍ）ステップで反復的に評価することができる。]
[0133] 式（２８）に基づいて４つのデデキンド和の組合せについてｄ’（ｃ，ｍ，ｃ１，ｃ２，ｃ３，ｃ４）を決定する効率的なアルゴリズムが、米国仮出願第６１／０１６０４５号に記載されている。４つのデデキンド和の組合せを、米国仮出願第６１／０１６０４５号に記載のハードウェアアーキテクチャを使用して効率的に決定することもできる。]
[0134] 整数の集合Ｊｒ，ｎ（α’，β’）を、次のように定義することができる。]
[0135] 集合Ｊｒ，ｎ（α’，β’）は、無効なマッピングを有する０からα’−１までのすべての整数を含み、その結果、ρｒ，ｎ（ｘ）≧β’になる。α’およびβ’は、それぞれ、ｒ＋ｎビットを用いて表すことができる。集合Ｊｒ，ｎ（α’，β’）に含まれる整数の個数を、μｒ，ｎ（ｘ，Ｌ）と表すことができる。]
[0136] 集合Ｊｒ，ｎ（α’，β’）を、]
[0137] と表すことができ、ここで、Ｈｒ，ｎ（α’，β’）は、ｘのｒ個のＬＳＢに対するビット逆転関数πｒ（）を考慮することによって決定される無効なマッピングを有する整数の集合であり、
Ｋｒ，ｎ（ｃ，α’，β’）は、ｘのｎ個のＭＳＢに対するＬＣＳ関数を考慮することによって決定される無効なマッピングを有する整数の集合であり、
「∪」は、和集合演算を表す。]
[0138] 集合Ｈｒ，ｎ（α’，β’）を、次のように定義することができる。]
[0139] 集合Ｈｒ，ｎ（α’，β’）は、そのｒ個のＬＳＢが、ビット逆転された時にβ’のｒ個のＭＳＢによって形成される数より大きいｒビット数を形成するα’未満の整数を含む。]
[0140] 集合Ｈｒ，ｎ（α’，β’）に含まれる整数の個数は、μ’ｒ，ｎ（α’，β’）と表すことができ、次のように決定することができる。]
[0141] 式（３２）では、それぞれが]
[0142] 個の無効なマッピングを有する]
[0143] 個のフル列がある。最後の列は、]
[0144] 個の無効なマッピングを有する。φｒ（）は、ｘ＝（α’−１） ｍｏｄ ２ｒ、]
[0145] およびＭ＝２ｒを用いて、プルーンＢＲＩに関するφ（）に関して上で説明したように決定することができる。]
[0146] 集合Ｋｒ，ｎ（ｃ，α’，β’）を、次のように定義することができる。]
[0147] 集合Ｋｒ，ｎ（ｃ，α’，β’）は、（ｉ）そのｒ個のＬＳＢが、ビット逆転された時に、β’のｒ個のＭＳＢとオーバーラップし、（ｉｉ）そのｎ個のＭＳＢが、法２ｎおよび適切に定義された乗数ｃを有するＬＣＳ関数によってマッピングされた時に、β’のｎ個のＬＳＢによって形成される数以上のｎビット数を形成する、α’未満の整数を含む。]
[0148] 集合Ｋｒ，ｎ（ｃ，α’，β’）に含まれる整数の個数を、]
[0149] と表すことができ、次のように決定することができる。]
[0150] Ｓ’（ｕ，２ｎ，α”，β”）は、式（２１）に示され、上で説明したように決定することができる。]
[0151] 集合Ｊｒ，ｎ（α’，β’）に含まれる整数の総数は、]
[0152] と表すことができる。]
[0153] ｎが、Ｌ≦２ｒ＋ｎになる最小の正の整数である、長さＬのプルーンターボインタリーバについて、線形アドレスｘを、次のように、インタリーブされたアドレスｙにマッピングすることができる。まず、０からｘ（１）＝ｘまでの範囲内の無効なマッピングの個数]
[0154] を、α’＝ｘ＋１およびβ’＝Ｌを用いて、式（３８）に基づいて決定することができる。次に、切り詰められたアドレスを含めるために、範囲を]
[0155] に拡張することができる。次に、０からｘ（２）までの範囲内の無効なマッピングの個数を決定することができる。このプロセスを、正確にｘ＋１個の有効なアドレスを含む最小サイズの範囲に達するまで繰り返すことができる。]
[0156] （ｋ＋１）番目の反復での無効なマッピングの個数は、]
[0157] として与えることができる。すべての反復が完了した後に、]
[0158] の最後の値を、式（１６）のτｒ，ｎ（ｘ，Ｌ）として提供することができる。次に、インタリーブされたアドレスｙを、式（１６）を使用してτｒ，ｎ（ｘ，Ｌ）に基づいて決定することができる。]
[0159] アルゴリズム５とも称する、τｒ，ｎ（ｘ，Ｌ）を反復的に決定するアルゴリズムを、下の擬似コードを用いて実施することができる。]
[0160] パラメータＬを用いるプルーンターボインタリーバ関数ｙ＝λｒ，ｎ（ｘ，Ｌ）に基づく線形アドレスｘのインタリーブされたアドレスｙは、次のように決定することができる。まず、中間アドレスｖを次のように計算することができる。]
[0161] 次に、インタリーブされたアドレスｙを、次のように、中間アドレスｖにターボインタリーバ関数ρｒ，ｎ（ｖ）を適用することによって決定することができる。]
[0162] ターボインタリーバ関数は、式（１４）に示されているように、またはある他の形で実施することができる。]
[0163] 図１１に、プルーンＢＲＩ、プルーンターボインタリーバなどとすることができるプルーンインタリーバのアドレスジェネレータ１１００の設計のブロック図を示す。アドレスジェネレータ１１００を、図２のチャネルインタリーバ２５０、図３のターボインタリーバ３２０、図５のターボインタリーバ５３０などに使用することができる。アドレスジェネレータ１１００内では、ユニット１１１０が、線形アドレスｘを受け取り、ｘに対応する無効なマッピングの総数（たとえば、φ（ｘ）またはτｒ，ｎ（ｘ，Ｌ））を決定する。ユニット１１１０は、プルーンＢＲＩのアルゴリズム２および３、プルーンターボインタリーバのアルゴリズム５、または他のタイプのインタリーバのある他のアルゴリズムを実施することができる。ユニット１１１０は、上で説明したように無効なマッピングの総数を反復的に計算することができる。] 図１１ 図２ 図３ 図５
[0164] 合計器１１１２は、線形アドレスｘを無効なマッピングの総数と合計し、中間アドレスｖを供給する。非プルーンインタリーバ関数１１２０は、中間アドレスｖを受け取り、インタリーブされたアドレスｙを供給する。関数１１２０は、ビット逆転関数を実施し、インタリーブされたアドレスｙとして中間アドレスｖのビット逆転された版を供給することができる。関数１１２０は、式（１４）に示されたターボインタリーバ関数、式（１７）または（１８）に示されたＬＣＳ関数、あるいはある他のインタリーバ関数を実施することもできる。]
[0165] 図１２に、プルーンビット逆転デインタリーバ、プルーンターボデインタリーバなどとすることができる、プルーンデインタリーバのアドレスジェネレータ１２００の設計のブロック図を示す。アドレスジェネレータ１２００を、図４のチャネルデインタリーバ４２０、図５のターボデインタリーバ５４０などに使用することができる。アドレスジェネレータ１２００内では、非プルーンデインタリーバ関数１２１０が、インタリーブされたアドレスｙを受け取り、中間アドレスｖを供給する。関数１２１０は、ビット逆転関数を実施し、中間アドレスｖとしてインタリーブされたアドレスｙのビット逆転された版を供給することができる。関数１２１０は、ターボデインタリーバ関数、ＬＣＳ関数、またはある他のデインタリーバ関数を実施することもできる。ユニット１２２０は、中間アドレスｖを受け取り、たとえば１回の反復だけで、ｖに対応する無効なマッピングの総数を決定する。ユニット１２２０は、プルーンビット逆転デインタリーバのアルゴリズム２および３、プルーンターボデインタリーバのアルゴリズム５、または他のタイプのデインタリーバのある他のアルゴリズムを実施することができる。合計器１２２２が、中間アドレスｖから無効なマッピングの総数を減算し、線形アドレスｘを供給する。] 図１２ 図４ 図５
[0166] 図１３に、データを並べ変えるプロセス１３００の設計を示す。プロセス１３００を、データ送信用の送信機、データ受信用の受話器、またはある他の実体によって実行することができる。プロセス１３００を、チャネルインタリービング、ターボインタリービング、チャネルデインタリービング、ターボデインタリービングなどに使用することができる。] 図１３
[0167] サイズＬのプルーンインタリーバの第１のアドレスを受け取ることができる（ブロック１３１２）。第１のアドレスに対応する無効なマッピングの総数（たとえば、φ（ｘ）またはτｒ，ｎ（ｘ，Ｌ））を決定することができる（ブロック１３１４）。次に、プルーンインタリーバの第２のアドレスを、第１のアドレスおよび無効なマッピングの総数に基づいて決定することができる（ブロック１３１６）。第１のアドレスおよび第２のアドレスは、それぞれｂビットを備えることができ、０からＬ−１までの範囲内にあることができ、ここで、（Ｍ／２）＜Ｌ＜ＭおよびＭ＝２ｂである。ｂは、プルーンＢＲＩではｎ、ターボインタリーバではｒ＋ｎと等しいものとすることができる。データを、第１のアドレスおよび第２のアドレスに基づいて並べ変えることができる（ブロック１３１８）。]
[0168] インタリービングについて、第１のアドレスは、線形アドレスを備えることができ、第２のアドレスは、インタリーブされたアドレスを備えることができる。ブロック１３１８について、線形アドレスのデータ値を、そのデータをインタリーブするためにインタリーブされたアドレスにマッピングすることができる。ある設計では、プルーンインタリーバは、プルーンビット逆転インタリーバを備えることができる。次に、インタリーブされたアドレスを、（ｉ）中間アドレスを得るために線形アドレスを無効なマッピングの総数と合計し、（ｉｉ）中間アドレスのビット逆転された版をインタリーブされたアドレスとして供給することによって、決定することができる。別の設計では、プルーンインタリーバは、プルーンターボインタリーバを備えることができる。インタリーブされたアドレスを、（ｉ）中間アドレスを得るために線形アドレスを無効なマッピングの総数と合計し、（ｉｉ）中間アドレスの非プルーンインタリーバ関数に基づいてインタリーブされたアドレスを決定することによって、決定することができる。非プルーンインタリーバ関数は、（ｉ）配列の複数の行に関する第１のマッピング関数（たとえば、ビット逆転関数）および（ｉｉ）各行の複数のエントリに関する第２のマッピング関数（たとえば、ＬＣＳ関数）を備えることができる。]
[0169] デインタリーブについて、第１のアドレスは、インタリーブされたアドレスを備えることができ、第２のアドレスは、線形アドレスを備えることができる。ブロック１３１８について、インタリーブされたアドレスのデータ値を、そのデータをデインタリーブするために線形アドレスにマッピングすることができる。ある設計では、プルーンインタリーバは、プルーンビット逆転インタリーバを備えることができる。次に、線形アドレスを、（ｉ）中間アドレスのビット逆転された版に基づいて中間アドレスを決定し、（ｉｉ）線形アドレスを得るために中間アドレスから無効なマッピングの総数を減算することによって、決定することができる。別の設計では、プルーンインタリーバは、プルーンターボインタリーバを備えることができる。線形アドレスを、（ｉ）インタリーブされたアドレスの非プルーンデインタリーバ関数に基づいて中間アドレスを決定し、（ｉｉ）線形アドレスを得るために中間アドレスから無効なマッピングの総数を減算することによって、決定することができる。]
[0170] ある設計では、無効なマッピングの総数を、反復的に、たとえば、所定の回数の反復（たとえば、ｎ−１回の反復）で、または無効なマッピングの同一の総数が２つの連続する反復について得られるまで、決定することができる。各反復を、異なるタイプのプルーンインタリーバについて異なる形で実行することができる。]
[0171] プルーンＢＲＩおよびおそらくは他のプルーンインタリーバに適用可能とすることができる、ある設計では、反復ｋごとに、一時アドレス（たとえば、ｘ（ｋ））を、第１のアドレスと反復の初期値との合計に基づいて決定することができる。初期値は、最初の反復について０と等しく、各後続の反復について、前の反復からの無効なマッピングの個数（たとえば、σ（ｋ−１）（ｘ））と等しいものとすることができる。０から一時アドレス（たとえば、σ（ｋ）（ｘ））までの範囲内の無効なマッピングの個数を決定することができる。プルーンＢＲＩについて、Ｌ−１のビット表現内の０ビットを識別することができる。Ｌ−１のビット表現内の各０ビットのカウント値（たとえば、σｉ（ｘ））を、たとえば上で説明したように、一時アドレス、Ｌ−１のビット表現、およびＬ−１のビット表現内の０ビットの位置に基づいて決定することができる。Ｌ−１のビット表現内のすべての０ビットのカウント値を、たとえば式（１０）に示されているように、０から一時アドレスまでの範囲内の無効なマッピングの個数を得るために合計することができる。]
[0172] プルーンターボインタリーバおよびおそらくは他のプルーンインタリーバに適用可能とすることのできる、ある設計では、反復ｋごとに、一時アドレス（たとえば、ｘ（ｋ））を、第１のアドレスと反復の初期値との合計に基づいて決定することができる。初期値は、最初の反復について０と等しく、各後続の反復について、前の反復からの無効なマッピングの組み合わされた個数（たとえば、]
[0173] ）と等しいものとすることができる。０から一時アドレスまでの範囲内の無効なマッピングの第１個数（たとえば、μ’ｒ，ｎ（α’，β’））を、たとえば式（３２）に示されているように、第１のマッピング関数によって決定される第１カウント関数に基づいて決定することができる。０から一時アドレスまでの範囲内の無効なマッピングの第２個数（たとえば、]
[0174] ）を、たとえば式（３４）に示されているように、第２のマッピング関数によって決定される第２カウント関数に基づいて決定することができる。反復に関する無効なマッピングの組み合わされた個数（たとえば、μｒ，ｎ（α’，β’））を、たとえば式（３８）に示されているように、無効なマッピングの第１個数および第２個数に基づいて決定することができる。第１カウント関数は、ビット逆転関数に基づくものとすることができる。第２カウント関数は、ＬＣＳ関数に基づくものとすることができ、デデキンド和の組合せを備えることができる。第１および第２のカウント関数を、他のマッピング関数について他の形で定義することもできる。]
[0175] 当業者は、情報および信号を、さまざまな異なるテクノロジおよび技法のいずれをも使用して表すことができることを理解するであろう。たとえば、上の説明全体を通じて参照される可能性があるデータ、命令、コマンド、情報、信号、ビット、シンボル、およびチップを、電圧、電流、電磁波、磁場または磁性粒子、光場または光粒子、あるいはその任意の組合せによって表すことができる。]
[0176] 当業者は、本明細書の開示に関連して説明されたさまざまな例示的な論理ブロック、モジュール、回路、およびアルゴリズムステップを、電子ハードウェア、コンピュータソフトウェア、またはこの両方の組合せとして実施できることを、さらに了解するであろう。ハードウェアおよびソフトウェアのこの交換可能性を明瞭に示すために、さまざまな例示的なコンポーネント、ブロック、モジュール、回路、およびステップを、上では一般にその機能性に関して説明した。そのような機能性がハードウェアまたはソフトウェアのどちらとして実施されるかは、特定の応用例および全体的なシステムに課せられる設計制約に依存する。当業者は、説明された機能性を各特定の応用例のためにさまざまな形で実施することができるが、そのような実施判断が、本開示の範囲からの逸脱を引き起こすと解釈してはならない。]
[0177] 本明細書の開示に関連して説明されたさまざまな例示的な論理ブロック、モジュール、および回路を、汎用プロセッサ、ディジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）もしくは他のプログラマブルロジックデバイス、ディスクリートゲートもしくはトランジスタロジック、ディスクリートハードウェアコンポーネント、または本明細書で説明される機能を実行するように設計されたその任意の組合せを用いて実施し、または実行することができる。汎用プロセッサは、マイクロプロセッサとすることができるが、代替案では、プロセッサを、任意の従来のプロセッサ、コントローラ、マイクロコントローラ、または状態機械とすることができる。プロセッサを、コンピューティングデバイスの組合せ、たとえば、ＤＳＰおよびマイクロプロセッサの組合せ、複数のマイクロプロセッサ、ＤＳＰコアに関連する１つまたは複数のマイクロプロセッサ、あるいは任意の他のそのような構成として実施することもできる。]
[0178] 本明細書の開示に関連して説明された方法またはアルゴリズムのステップを、ハードウェアで直接に、プロセッサによって実行されるソフトウェアモジュールで、またはこの２つの組合せで実施することができる。ソフトウェアモジュールは、ＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、リムーバブルディスク、ＣＤ−ＲＯＭ、または当技術分野で既知の任意の他の形の記憶媒体に常駐することができる。例示的な記憶媒体は、プロセッサが記憶媒体から情報を読み取り、これに情報を書き込むことができるように、プロセッサに結合される。代替案では、記憶媒体を、プロセッサに一体とすることができる。プロセッサおよび記憶媒体が、ＡＳＩＣに常駐することができる。そのＡＳＩＣが、ユーザ端末に常駐することができる。代替案では、プロセッサおよび記憶媒体が、ユーザ端末内に別個のコンポーネントとして常駐することができる。]
[0179] １つまたは複数の例示的設計では、説明された機能を、ハードウェア、ソフトウェア、ファームウェア、またはその任意の組合せで実施することができる。ソフトウェアで実施される場合に、機能を、コンピュータ可読媒体上の１つまたは複数の命令またはコードとして格納し、あるいは伝送することができる。コンピュータ可読媒体は、コンピュータ記憶媒体と、ある場所から別の場所へのコンピュータプログラムの転送を容易にするすべての媒体を含む通信媒体との両方を含む。記憶媒体は、汎用コンピュータまたは特殊目的コンピュータによってアクセスできるすべての使用可能な媒体とすることができる。限定ではなく例として、そのようなコンピュータ可読媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭもしくは他の光ディスクストレージ、磁気ディスクストレージもしくは他の磁気ストレージデバイス、あるいは命令もしくはデータ構造の形で所望のプログラムコード手段を担持しまたは格納するのに使用でき、汎用コンピュータもしくは特殊目的コンピュータまたは汎用プロセッサもしくは特殊目的プロセッサによってアクセスできる任意の他の媒体を備えることができる。また、すべての接続を、当然、コンピュータ可読媒体と呼ぶことができる。たとえば、ソフトウェアが、ウェブサイト、サーバ、または他の遠隔ソースから同軸ケーブル、光ファイバケーブル、より対線、ディジタル加入者回線（ＤＳＬ）、または赤外線、ラジオ、およびマイクロ波などの無線テクノロジを使用して伝送される場合に、同軸ケーブル、光ファイバケーブル、より対線、ＤＳＬ、または赤外線、ラジオ、およびマイクロ波などの無線テクノロジは、媒体の定義に含まれる。ディスク（ｄｉｓｋ ａｎｄ ｄｉｓｃ）は、本明細書で使用される時に、コンパクトディスク（ＣＤ）、レーザディスク、光ディスク、ディジタル多用途ディスク（ＤＶＤ）、フロッピディスク、およびｂｌｕ−ｒａｙディスクを含み、ディスク（ｄｉｓｋ）は、通常はデータを磁気的に再生し、ディスク（ｄｉｓｃ）は、レーザを用いてデータを光学的に再生する。上記の組合せも、コンピュータ可読媒体の範囲に含まれなければならない。]
[0180] 本開示の前の説明は、すべての当業者が本開示を作るか使用することを可能にするために提供される。本開示に対するさまざまな変更は、当業者に直ちに明白になり、本明細書で定義される包括的原理は、本開示の範囲から逸脱せずに他の変形形態に適用することができる。したがって、本開示は、本明細書で説明される例および設計に限定されることを意図されてはおらず、本明細書で開示される原理および新規の特徴と一貫する最も広い範囲に従わなければならない。]

权利要求:

請求項1
プルーンインタリーバ用の第１のアドレスを受け取ることと、前記第１のアドレスに対応する無効なマッピングの総数を決定することと、前記第１のアドレスおよび前記無効なマッピングの総数に基づいて前記プルーンインタリーバ用の第２のアドレスを決定することと、前記第１のアドレスおよび前記第２のアドレスに基づいてデータを並べ変えることとを含む、データを処理する方法。
請求項2
前記第１のアドレスは、線形アドレスを含み、前記第２のアドレスは、インタリーブされたアドレスを含み、データを並べ変えることは、前記データをインタリーブするために、前記線形アドレスにあるデータ値を前記インタリーブされたアドレスにマッピングすることを含む、請求項１に記載の方法。
請求項3
前記プルーンインタリーバは、プルーンビット逆転インタリーバを含み、前記第２のアドレスを決定することは、中間アドレスを得るために、前記線形アドレスを前記無効なマッピングの総数と合計することと、前記インタリーブされたアドレスとして、前記中間アドレスのビット逆転された版を提供することとを含む、請求項２に記載の方法。
請求項4
前記第２のアドレスを決定することは、中間アドレスを得るために、前記線形アドレスを前記無効なマッピングの総数と合計することと、前記中間アドレスの非プルーンインタリーバ関数に基づいて前記インタリーブされたアドレスを決定することとを含む、請求項２に記載の方法。
請求項5
前記非プルーンインタリーバ関数は、配列の複数の行に関する第１のマッピング関数および各行内の複数のエントリに関する第２のマッピング関数を含む、請求項４に記載の方法。
請求項6
前記非プルーンインタリーバ関数は、ビット逆転関数および線形合同シーケンス（ＬＣＳ）関数を含む、請求項４に記載の方法。
請求項7
前記第１のアドレスは、インタリーブされたアドレスを含み、前記第２のアドレスは、線形アドレスを含み、データを並べ変えることは、前記データをデインタリーブするために、前記インタリーブされたアドレスにあるデータ値を前記線形アドレスにマッピングすることを含む、請求項１に記載の方法。
請求項8
前記プルーンインタリーバは、プルーンビット逆転インタリーバを含み、前記第２のアドレスを決定することは、前記インタリーブされたアドレスのビット逆転された版に基づいて中間アドレスを決定することと、前記線形アドレスを得るために、前記中間アドレスから前記無効なマッピングの総数を減算することとを含む、請求項７に記載の方法。
請求項9
前記第２のアドレスを決定することは、前記インタリーブされたアドレスの非プルーンデインタリーバ関数に基づいて中間アドレスを決定することと、前記線形アドレスを得るために、前記中間アドレスから前記無効なマッピングの総数を減算することとを含む、請求項７に記載の方法。
請求項10
前記無効なマッピングの総数は、反復的に決定される、請求項１に記載の方法。
請求項11
前記無効なマッピングの総数は、反復の所定の回数についてまたは無効なマッピングの同一の総数が２つの連続する反復について得られるまで決定される、請求項１０に記載の方法。
請求項12
前記無効なマッピングの総数を決定することは、反復ごとに、前記第１のアドレスと前記反復の初期値との合計に基づいて一時アドレスを決定することと、０から前記一時アドレスまでの範囲内の無効なマッピングの個数を決定することとを含む、請求項１０に記載の方法。
請求項13
前記初期値は、最初の反復について０と等しく、各後続の反復について前の反復からの前記無効なマッピングの個数と等しい、請求項１２に記載の方法。
請求項14
前記プルーンインタリーバは、Ｌのサイズを有し、０から前記一時アドレスまでの前記範囲内の前記無効なマッピングの個数を決定することは、Ｌ−１のビット表現内の０ビットを識別することと、Ｌ−１の前記ビット表現内の各０ビットのカウント値を、前記一時アドレス、Ｌ−１の前記ビット表現、およびＬ−１の前記ビット表現内の前記０ビットの位置に基づいて決定することと、０から前記一時アドレスまでの前記範囲内の前記無効なマッピングの個数を得るために、Ｌ−１の前記ビット表現内のすべての０ビットのカウント値を合計することとを含む、請求項１２に記載の方法。
請求項15
前記無効なマッピングの総数を決定することは、前記第１のマッピング関数に基づいて前記第１のアドレスの無効なマッピングの第１の個数を決定することと、前記第２のマッピング関数に基づいて前記第１のアドレスの無効なマッピングの第２の個数を決定することと、前記無効なマッピングの第１の個数および第２の個数に基づいて前記無効なマッピングの総数を決定することとを含む、請求項５に記載の方法。
請求項16
前記無効なマッピングの総数は、反復的に決定され、前記無効なマッピングの総数を決定することは、反復ごとに、前記第１のアドレスおよび前記反復の初期値の合計に基づいて一時アドレスを決定することと、前記第１のマッピング関数によって決定される第１のカウント関数に基づいて０から前記一時アドレスまでの前記範囲内の無効なマッピングの第１の個数を決定することと、前記第２のマッピング関数によって決定される第２のカウント関数に基づいて０から前記一時アドレスまでの前記範囲内の無効なマッピングの第２の個数を決定することと、前記無効なマッピングの第１の個数および第２の個数に基づいて前記反復の無効なマッピングの組み合わされた個数を決定することとを含む、請求項５に記載の方法。
請求項17
前記初期値は、最初の反復について０と等しく、各後続の反復について前の反復からの無効なマッピングの前記組み合わされた個数と等しい、請求項１６に記載の方法。
請求項18
前記第１のカウント関数は、前記第１のマッピング関数のビット逆転関数に基づいて決定される、請求項１６に記載の方法。
請求項19
前記第２のカウント関数は、前記第２のマッピング関数の線形合同シーケンス（ＬＣＳ）関数に基づいて決定される、請求項１６に記載の方法。
請求項20
前記第２のカウント関数は、デデキンド和の組合せを含む、請求項１６に記載の方法。
請求項21
前記第１のアドレスおよび前記第２のアドレスは、それぞれ、ｂビットを含み、０からＬ−１までの範囲内にあり、Ｌは、前記プルーンインタリーバのサイズであり、（Ｍ／２）＜Ｌ＜ＭおよびＭ＝２ｂである、請求項１に記載の方法。
請求項22
プルーンインタリーバ用の第１のアドレスを受け取り、前記第１のアドレスに対応する無効なマッピングの総数を決定し、前記第１のアドレスおよび前記無効なマッピングの総数に基づいて前記プルーンインタリーバ用の第２のアドレスを決定し、前記第１のアドレスおよび前記第２のアドレスに基づいてデータを並べ変えるように構成された少なくとも１つのプロセッサを備える、データを処理する装置。
請求項23
前記少なくとも１つのプロセッサは、中間アドレスを得るために、前記第１のアドレスを前記無効なマッピングの総数と合計し、前記中間アドレスのビット逆転された版を前記第２のアドレスとして提供するように構成される、請求項２２に記載の装置。
請求項24
前記少なくとも１つのプロセッサは、中間アドレスを得るために、前記第１のアドレスを前記無効なマッピングの総数と合計し、前記中間アドレスの非プルーンインタリーバ関数に基づいて前記第２のアドレスを決定するように構成される、請求項２２に記載の装置。
請求項25
前記非プルーンインタリーバ関数は、ビット逆転関数および線形合同シーケンス（ＬＣＳ）関数を含む、請求項２４に記載の装置。
請求項26
前記少なくとも１つのプロセッサは、前記無効なマッピングの総数を反復的に決定し、反復ごとに、前記第１のアドレスおよび前記反復の初期値の合計に基づいて一時アドレスを決定し、０から前記一時アドレスまでの範囲内の無効なマッピングの個数を決定するように構成される、請求項２２に記載の装置。
請求項27
前記プルーンインタリーバは、Ｌのサイズを有し、反復ごとに、前記少なくとも１つのプロセッサは、Ｌ−１のビット表現内の０ビットを識別し、Ｌ−１の前記ビット表現内の各０ビットのカウント値を、前記一時アドレス、Ｌ−１の前記ビット表現、およびＬ−１の前記ビット表現内の前記０ビットの位置に基づいて決定し、０から前記一時アドレスまでの前記範囲内の前記無効なマッピングの個数を得るために、Ｌ−１の前記ビット表現内のすべての０ビットのカウント値を合計するように構成される、請求項２６に記載の装置。
請求項28
前記非プルーンインタリーバ関数は、配列の複数の行に関する第１のマッピング関数および各行内の複数のエントリに関する第２のマッピング関数を含み、前記少なくとも１つのプロセッサは、前記無効なマッピングの総数を反復的に決定し、反復ごとに、前記第１のアドレスおよび前記反復の初期値の合計に基づいて一時アドレスを決定し、前記第１のマッピング関数によって決定される第１のカウント関数に基づいて０から前記一時アドレスまでの範囲内の無効なマッピングの第１の個数を決定し、前記第２のマッピング関数によって決定される第２のカウント関数に基づいて０から前記一時アドレスまでの前記範囲内の無効なマッピングの第２の個数を決定し、前記無効なマッピングの第１の個数および第２の個数に基づいて前記反復の無効なマッピングの組み合わされた個数を決定するように構成される、請求項２４に記載の装置。
請求項29
前記装置は、集積回路である、請求項２２に記載の装置。
請求項30
前記装置は、無線通信デバイスである、請求項２２に記載の装置。
請求項31
プルーンインタリーバ用の第１のアドレスを受け取るための手段と、前記第１のアドレスに対応する無効なマッピングの総数を決定するための手段と、前記第１のアドレスおよび前記無効なマッピングの総数に基づいて前記プルーンインタリーバ用の第２のアドレスを決定するための手段と、前記第１のアドレスおよび前記第２のアドレスに基づいてデータを並べ変えるための手段とを備える、データを処理する装置。
請求項32
前記第２のアドレスを決定するための手段は、中間アドレスを得るために、前記第１のアドレスを前記無効なマッピングの総数と合計するための手段と、前記中間アドレスのビット逆転された版を前記第２のアドレスとして提供するための手段とを備える、請求項３１に記載の装置。
請求項33
前記第２のアドレスを決定するための前記手段は、中間アドレスを得るために、前記第１のアドレスを前記無効なマッピングの総数と合計するための手段と、前記中間アドレスの非プルーンインタリーバ関数に基づいて前記第２のアドレスを決定するための手段とを備える、請求項３１に記載の装置。
請求項34
前記非プルーンインタリーバ関数は、ビット逆転関数および線形合同シーケンス（ＬＣＳ）関数を含む、請求項３３に記載の装置。
請求項35
前記無効なマッピングの総数は、反復的に決定され、前記無効なマッピングの総数を決定するための手段は、反復ごとに、前記第１のアドレスおよび前記反復の初期値の合計に基づいて一時アドレスを決定するための手段と、０から前記一時アドレスまでの範囲内の無効なマッピングの個数を決定するための手段とを備える、請求項３１に記載の装置。
請求項36
前記プルーンインタリーバは、Ｌのサイズを有し、０から前記一時アドレスまでの前記範囲内の前記無効なマッピングの個数を決定するための手段は、Ｌ−１のビット表現内の０ビットを識別するための手段と、Ｌ−１の前記ビット表現内の各０ビットのカウント値を、前記一時アドレス、Ｌ−１の前記ビット表現、およびＬ−１の前記ビット表現内の前記０ビットの位置に基づいて決定するための手段と、０から前記一時アドレスまでの前記範囲内の前記無効なマッピングの個数を得るために、Ｌ−１の前記ビット表現内のすべての０ビットのカウント値を合計するための手段とを備える、請求項３５に記載の装置。
請求項37
前記非プルーンインタリーバ関数は、配列の複数の行に関する第１のマッピング関数および各行内の複数のエントリに関する第２のマッピング関数を含み、前記無効なマッピングの総数は、反復的に決定され、前記無効なマッピングの総数を決定するための前記手段は、反復ごとに、前記第１のアドレスおよび前記反復の初期値の合計に基づいて一時アドレスを決定するための手段と、前記第１のマッピング関数によって決定される第１のカウント関数に基づいて０から前記一時アドレスまでの範囲内の無効なマッピングの第１の個数を決定するための手段と、前記第２のマッピング関数によって決定される第２のカウント関数に基づいて０から前記一時アドレスまでの前記範囲内の無効なマッピングの第２の個数を決定するための手段と、前記無効なマッピングの第１の個数および第２の個数に基づいて前記反復の無効なマッピングの組み合わされた個数を決定するための手段とを備える、請求項３３に記載の装置。
請求項38
少なくとも１つのコンピュータにプルーンインタリーバ用の第１のアドレスを受け取らせるコードと、前記少なくとも１つのコンピュータに前記第１のアドレスに対応する無効なマッピングの総数を決定させるコードと、前記少なくとも１つのコンピュータに前記第１のアドレスおよび前記無効なマッピングの総数に基づいて前記プルーンインタリーバ用の第２のアドレスを決定させるコードと、前記少なくとも１つのコンピュータに前記第１のアドレスおよび前記第２のアドレスに基づいてデータを並べ変えさせるコードとを含む、コンピュータ可読媒体を備える、コンピュータプログラム製品。