(57)【要約】再構成可能並列ルックアップテーブルシステム(10)が、メモリ(18)と、メモリ上に格納された複数のルックアップテーブルと、ルックアップテーブル内でルックアップすべき値を保持する行インデックスレジスタ(12)と、メモリ内に格納されたルックアップテーブルの開始アドレスを表す値を格納する列インデックスレジスタ(14)と、列インデックスレジスタ(14)および行インデックスレジスタ(12)に応答し、行インデックスレジスタ(12)中の各値についてアドレスを同時に生成し、各ルックアップテーブル内のそうした値の関数の位置を並列に突き止めるアドレス変換回路(16)とを含む。
2005517233.tif 000002
【特許請求の範囲】
【請求項１】
メモリと、
前記メモリに格納された複数のルックアップテーブルと、
前記ルックアップテーブル内をルックアップすべき値を保持する行インデックスレジスタと、
前記メモリ内に格納された前記各ルックアップテーブルの開始アドレスを表す値を格納する列インデックスレジスタと、
前記列インデックスレジスタおよび前記行インデックスレジスタに応答し、前記行インデックスレジスタ中の各値についてアドレスを同時に生成し、各ルックアップテーブル内のそうした値の関数の位置を並列に突き止めるアドレス変換回路とを備える再構成可能並列ルックアップテーブルシステム。
【請求項２】
前記アドレス変換回路が、開始アドレスを表す値に各列の長さを掛ける乗算器回路と、前記行インデックスレジスタ内の値を前記乗算器回路の出力と組み合わせる加算器回路とを含む請求項1に記載の再構成可能並列ルックアップテーブルシステム。
【請求項３】
前記アドレス変換回路が、前記行インデックスレジスタ内の前記値を、前記行インデックスレジスタ内の値に対してNビットだけMSBに向けてシフトした前記列インデックスレジスタ内の前記値と組み合わせるOR回路を含む請求項1に記載の再構成可能並列ルックアップテーブルシステム。
【請求項４】
前記ルックアップテーブルがすべて同一サイズである請求項1に記載の再構成可能並列ルックアップテーブルシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、再構成可能な並列ルックアップテーブルシステムに関する。
【背景技術】
【０００２】
本願は、Stein等の8 WAY PARALLEL LOOK-UP TABLEという名称の2002年2月7日に郵送された米国仮出願の優先権を主張するものである。
【０００３】
現行の第2世代(2G)携帯情報端末(PDA)や新しい(3G)モバイルワイヤレスハンドセット/端末などの現在の通信応用例は、MPEG-4ストリーミングビデオプロトコルを求めている。最新世代のビデオ圧縮/解凍規格は、中速データ通信リンクを備える装置を主に対象としている。どちらの技術でもルックアップテーブルが大量に使用される。例えば、通信において、前方誤り訂正(リードソロモン)は通常256個のガロア域ルックアップテーブルを使用し、(DES/3DES、AES)のようなデータ暗号化アルゴリズムは、選択ボックス(S-Box)のために8個の64バイトルックアップテーブルを使用する。ビデオストリーミングでは、JPEG、MPEG-2、MPEG-4、Windows（登録商標） Mediaなどのプロトコルは、可変長コーディング(VLC)のためにハフマンルックアップテーブルを使用する。従来型のDSPおよびコントローラは、こうしたテーブルに順次アクセスし、その結果として応答時間が低速になる。
【０００４】
通常、特定の作業のためにこうしたテーブルを設計すると、こうしたテーブルは、他の用途に適合できない。その結果、順次アクセス可能ルックアップテーブルにより、通信およびイメージ処理応用例の動作速度が制限される。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
したがって本発明の目的は、改良型の再構成可能並列ルックアップテーブルシステムを提供することである。
【０００６】
本発明の別の目的は、いくつかのルックアップテーブルに同時にアクセスすることができる改良型の再構成可能並列ルックアップテーブルシステムを提供することである。
【０００７】
本発明の別の目的は、様々な数および様々なサイズのルックアップテーブルにアクセスするように容易に再構成可能な改良型の再構成可能並列ルックアップテーブルシステムを提供することである。
【０００８】
本発明の別の目的は、より高速かつ柔軟な改良型の再構成可能並列ルックアップテーブルシステムを提供することである。
【課題を解決するための手段】
【０００９】
本発明は、ルックアップすべき値をルックアップテーブルの開始アドレスを表す値と組み合わせ、各値をアドレスに同時に変換し、各ルックアップテーブル内のそうした値の関数の位置を並列に突き止めることによってメモリ内のいくつかのルックアップテーブルに同時にアクセスできるようにすることにより、真により高速かつ柔軟なルックアップテーブルシステムを達成できることの結果として得られる。
【００１０】
本発明は、メモリと、メモリ上に格納された複数のルックアップテーブルとを含む再構成可能並列ルックアップテーブルシステムを特徴とする。行インデックスレジスタが、ルックアップテーブル内でルックアップすべき値を保持し、列インデックスレジスタが、メモリ内に格納された各ルックアップテーブルの開始アドレスを表す値を格納する。アドレス変換回路が、列インデックスレジスタおよび行インデックスレジスタに応答し、行インデックスレジスタ中の各値についてアドレスを同時に生成し、各ルックアップテーブル内のそうした値の関数の位置を並列に突き止める。
【００１１】
好ましい実施形態では、アドレス変換回路は、開始アドレスを表す値に各列の長さを掛ける乗算器回路と、行インデックスレジスタの値を乗算器回路の出力と組み合わせる加算器回路とを含むことができる。アドレス変換回路は、行インデックスレジスタからの値を、行インデックスレジスタ内の値に対してNビットだけMSBに向けてシフトした列インデックスレジスタ内の値と組み合わせるOR回路を含むことができる。ルックアップテーブルはすべて同一サイズでよい。
【発明を実施するための最良の形態】
【００１２】
以下の好ましい実施形態の説明および添付の図面から、その他の目的、特徴、および利点が当業者には思い浮かぶであろう。
【００１３】
図1に、本発明による再構成可能並列ルックアップテーブルシステム10を示す。再構成可能並列ルックアップテーブルシステム10は、行インデックスレジスタR2、12、列インデックスレジスタR1、14、アドレス変換回路16、およびいくつかのルックアップテーブルを含むメモリ18を含む。メモリ18から出力は、出力レジスタ20に送達される。メモリ18は、いくつかのルックアップテーブルを含み、行インデックスレジスタ12は、そうしたルックアップテーブル内でルックアップすべき値を保持する。例えば、行インデックスレジスタ12は、メモリ18のルックアップテーブル内でルックアップすべき角度を保持することができ、ルックアップテーブルのそれぞれは、異なる関数、すなわちそうした角度についての正弦値、余弦値、正接値などのうち1つを有する。列インデックスレジスタ14は、メモリに格納された各ルックアップテーブルの開始アドレスを表す値を格納する。例えば、メモリ18が、それぞれ64バイトの8個のルックアップテーブルを保持する場合、列30、32、34、36、38、40、42、44と一致する、こうしたルックアップテーブルに関する開始点は、0、64、128、192、256、320、384、および448となる。アドレス変換回路16は、行インデックスレジスタ12内の値を、各ルックアップテーブルの開始アドレスの表現と組み合わせ、インデックスレジスタ内の各値についてのアドレスを同時に生成し、各ルックアップテーブル内のそうした値の関数の位置を並列に突き止める。
【００１４】
メモリは通常、製造上の都合で図3に示すように線形に作成される。したがって、各バイトが8ビットを含む512バイトの記憶容量を有するメモリは、図2のメモリ18aで示すように構築される。図2のメモリ18aには、次々に並べられ、バイト0-63、64-127、128-191、192-255、256-319、320-383、384-447、448-511の各列を含む8個の列30-44がある。列30-44のそれぞれの長さが等しいと仮定すると、メモリ18aは、図3のメモリ18bのように想定される可能性がより高い。図3のメモリ18bでは、各列30-44が並べられ、0-63まで番号を付けた64個の行46に及ぶと想定される。次いで、アドレス指定すべきエリアが第5列の第4行、すなわち影を付けたエリア48にあると想定すると、このエリアは、図2に示す0-511の行中の324番目の行であることがわかる。この特定の位置48をアドレス指定するために、図3のメモリルックアップテーブルでは、図4の列インデックスレジスタ14a内の列番号5に、図4の乗算器50でテーブルの長さ(64)を掛け、320という数を生成することができる。この320という数を、第4行に対応するインデックスレジスタ12aに加えた場合、加算器52の出力は324となり、これはまさに、図3の行4列5と示され、図2のアドレス324としても直接的に示される位置48のアドレスである。同じ概念を、図5に示すように、デジタル式にずっと効率的かつ単純に達成することができる。図5では、行インデックスレジスタ12bおよび列インデックスレジスタ14bを8個のステージレジスタとして示し、各ステージは、それぞれ8ビットの1バイトを表す。第1ステージ60には前と同様に4という数が常駐するが、レジスタ14bの第1ステージ62には40という数が常駐する。この数には、3ビットのハードワイヤードシフトのために8が掛けられ、前述と同様に320という数が得られるからである。より具体的には、図6のステージ60の拡大図に、2進数で4を表す第3ビット位置に「1」を有する8ビット構造を示す。8ビットの第4ビット位置および第6ビット位置に「1」を有するレジスタ14bのステージ62を示す。66の「1」ビットは8を表し、68の「1」ビットは32を表し、合計で40を表す。しかし、図6に図示す
るように、レジスタ14bのステージ62からの8ビットは、レジスタ12bからのステージ60の8ビットに対して左に3ビットシフトされている。これにより、実質上ステージ62内の値に8が掛けられる。次いでこの2つを組み合わせたとき(通常は論理和を取ったとき)、その結果は第3ビット72、第7ビット74、および第9ビット76に1が存在する9ビットアドレス70であり、9ビットアドレス70は265+64+4=324を表し、これは、図2および3に関連して先に説明したように適切なアドレスである。
【００１５】
512から1024または2048個のメモリ位置を超えるシステムを採用することが望ましい場合、使用可能な2つの追加のビット78、80がそれぞれ存在する。8バイトレジスタを使用しており、かつ8バイトサイズ内を並べ換えることは望ましくないので、乗数8を得るように3ビットのシフトが選ばれる。本発明の構造の結果として、容易に再構成可能なシステムが得られる。単に所望の開始点を選び、それを8で割り、その数をステージ62に格納することによって任意の特定のルックアップテーブルの開始点を確立することができ、レジスタ12b内の他の各ステージが、ルックアップテーブルの開始アドレスを表す同一の値または異なる値を有することができ、その結果ルックアップテーブルのすべてを同一サイズにすることができ、またはすべて異なるサイズにすることができるからである。例えば図7に示すように、8バイト長の64個のルックアップテーブルを有するメモリ18c、64バイト長の8個のルックアップテーブルを有するメモリ18d、またはメモリ18eで示すように、512バイト長の1つのルックアップテーブルを有することができる。
【００１６】
本発明の一実施形態では、図8の再構成可能並列ルックアップシステム10fが、図6に関連して先に説明したような8ステージをそれぞれ有する行インデックスレジスタ12fおよび列インデックスレジスタ14fと、図3に示したような64バイトの8個の列を含むメモリ18fとを含む。図8では、アドレス変換回路16fが、いくつかのOR回路を含む。1つのOR回路は、各レジスタ12fおよび14fからのステージの各対と関連付けられる。したがって8個のOR回路が存在するが、図が見やすいようにそのうちの3つ90、92と94だけを示す。動作の際に、OR回路90は、8ビットステージ60fからの8個の入力のうち5つを受け取り、ステージ60からの残りの最下位ビットは、メモリアドレスバス96に直接送達される。ORゲート90への他の入力は、レジスタ14fの第1ステージ62fからの6ビットである。これらが、図6に関連して説明したように組み合わされ、その結果、ステージ60fからの5ビットと、シフトしたステージ62fからの6ビットとの論理和が取られ、6ビット出力が生成され、次いで6ビット出力が、ステージ60fからの3つの最下位ビットと組み合わされ、アドレスバス96上で9ビットアドレスが得られる。OR回路92および94、ならびに図が見やすいように省略した他のOR回路は同様に動作し、メモリ18f内の位置をアドレス指定する。
【００１７】
図9のOR回路90で例示される各OR回路は、5個のORゲート100、102、104、106、および108を含む。ステージ62内のビットがステージ60f内のビットに対して3個分だけシフトされて、各ゲートは、ステージ60fの3、4、5、6、および7番目の位置からのビットを、ステージ62fの位置0、1、2、3、4からのビットとそれぞれ組み合わせる。ステージ60fの最初の3つのビット0、1、2は、ORゲートを介さずに直接送達され、出力110で9ビットアドレス0-8が得られる。ステージ62f内の位置5からの最上位ビットも、どんなORゲートも介さずに直接供給される。
【００１８】
64バイトの長さをそれぞれ有する8つのルックアップテーブル120、122、124、126、128、130、132、および134を有する再構成可能並列ルックアップテーブルシステム10gでは、レジスタ14gが、そのステージ62g1から62g8内に、ルックアップすべき値0、8、16、24、32、40、48、および56をそれぞれ格納する。したがって、こうした値のそれぞれに3ビットシフトによって因子8が掛けられたとき、各ルックアップテーブルの開始点は、前述のようにそれぞれ0、64、128、192、256、320、384、および448となる。ルックアップテーブル内でルックアップすべき値がステージ60g1-60g8のそれぞれに格納されるが、各列またはルックアップテーブル内に64個の行アドレスしか存在しないので、こうした値は、単に6ビットに格納することができる。レジスタ14gおよび12gのステージ内の2つの値の組合せは、OR回路150、152、154、156、158、160、162、および164で実施されるシフトおよび加算によって前述と同様に実施される。
【００１９】
図11に示すさらに別の例では、本発明による再構成可能並列ルックアップテーブルシステム10hを、ステージ62h1-62h4のそれぞれに値32を配置し、残りのステージ62h5-52h8にゼロを配置することにより、それぞれ256バイトの2つのルックアップテーブルを提供するように構成することができる。最初の4ステージに32を配置することにより、最初の4つの値が、256で始まり511まで行くルックアップテーブルを使用することになり、他の4つの値が、0で始まり255まで行くルックアップテーブルを使用することになる。ここでは、行インデックスレジスタ12hのステージ内の値は、行の数が256であるので、8ビット形式で表現される。
【００２０】
これまでの例では8ビット構造を使用したが、これは本発明の必要な制限ではない。例えば、行インデックスの2つの隣接するステージ内の値を反復し、ルックアップテーブルの長さに従って列インデックスレジスタ内の値を8ビットの基本バイトサイズの因子として調節することにより、16ビット、32ビット等のワードをアドレス指定およびルックアップすることができる。例えば、それぞれ256バイトの2つのルックアップテーブルを有するメモリでは、ステージ62h1-62h8に交互に値0および32をロードすることができ、ステージ60h1-60h8には、60h1と60h2が同一の値を有し、60h3と60h4が同一の値を有し、以下同様となるように、同様の対としてロードすることができ、その結果、16ビットワードを、0から開始して255まで行くテーブルを使用して最下位バイト(LSB)でアドレス指定およびルックアップすることができ、256から始まり511まで行くテーブルを使用して最上位バイト(MSB)でアドレス指定およびルックアップすることができる。本発明を行-列の点から論じたが、本発明を列-行あるいはその他の順序の配列で実装することもできる。
【００２１】
本発明の特定の機能をいくつかの図面で示し、他の図面では示さなかったが、便宜上そうしたに過ぎない。本発明によれば各機能を他の機能のいずれかまたはすべてと組み合わせることができるからである。本明細書で使用した「含む」、「備える」、および「有する」という語は、広く包括的に解釈すべきであり、何らかの物理的相互接続に限定されない。さらに、本願で開示される任意の実施形態を唯一の可能な実施形態とみなすべきではない。
【００２２】
他の実施形態が当業者には思い浮かぶであろう。そうした実施形態は添付の特許請求の範囲内にある。
【図面の簡単な説明】
【００２３】
【図１】本発明による再構成可能並列ルックアップテーブルシステムの概略ブロック図である。
【図２】典型的線形メモリ構造の略図である。
【図３】並列ルックアップテーブル構成として構成された図2の列を示す略図である。
【図４】行インデックスレジスタ値と列インデックスレジスタ値を組み合わせて、ルックアップテーブル内の値関数の位置を突き止めるアドレスを得る一手法を示す単純化した略図である。
【図５】図4に記載のアドレス生成を実施する、本発明による行インデックスレジスタおよび列インデックスレジスタの略図である。
【図６】実施された最後のアドレス生成を示す、図5のレジスタの各ステージ内の情報の8ビットのシフトおよび組合せを示すグラフ図である。
【図７】本発明で達成することができるルックアップテーブルのいくつかの異なる構成のサンプルを示す図である。
【図８】本発明による再構成可能並列ルックアップテーブルの一実施形態の略図である。
【図９】図8のOR回路のうちの1つのより詳細な略図である。
【図１０】本発明に従って実施することができる並列ルックアップテーブルの2つの異なる構成を示す略図である。
【図１１】本発明に従って実施することができる並列ルックアップテーブルの2つの異なる構成を示す略図である。
【符号の説明】
【００２４】
10 再構成可能並列ルックアップテーブルシステム
10f 再構成可能並列ルックアップシステム
10g 再構成可能並列ルックアップテーブルシステム
10h 再構成可能並列ルックアップテーブルシステム
12 行インデックスレジスタ
12a インデックスレジスタ
12f 行インデックスレジスタ
14 列インデックスレジスタ
14a 列インデックスレジスタ
14f 列インデックスレジスタ
14g レジスタ
16 アドレス変換回路
16f アドレス変換回路
18 メモリ
18a メモリ
18b メモリ
18c メモリ
18d メモリ
18e メモリ
18f メモリ
20 出力レジスタ
52 加算器
60 ステージ
60f ステージ
60g1-60g8 ステージ
62f ステージ
62g1-62g8 ステージ
62h1-62h8 ステージ
90 OR回路
92 OR回路
94 OR回路
96 メモリアドレスバス
100 ORゲート
102 ORゲート
104 ORゲート
106 ORゲート
108 ORゲート
110 出力
120 ルックアップテーブル
122 ルックアップテーブル
124 ルックアップテーブル
126 ルックアップテーブル
128 ルックアップテーブル
130 ルックアップテーブル
132 ルックアップテーブル
134 ルックアップテーブル
【図１】
2005517233.tif 000003
【図２】
2005517233.tif 000004
【図３】
2005517233.tif 000005
【図４】
2005517233.tif 000006
【図５】
2005517233.tif 000007
【図６】
2005517233.tif 000008
【図７】
2005517233.tif 000009
【図８】
2005517233.tif 000010
【図９】
2005517233.tif 000011
【図１０】
2005517233.tif 000012
【図１１】
2005517233.tif 000013
【国際調査報告】
2005517233.tif 000014