(57)【要約】  本発明は、第１の番号Ｘを含む前半部分と第２の番号Ｙを含む後半部分とを有するアドレス語を外部システムから受信するように構成されるアドレス部と、前記アドレス語により指定されるように構成されるＭ×Ｍ個のメモリセルを含み、ある特定のアドレス語により指定されるセルに第１の番号Ｘと第２の番号Ｙとの積Ｐが提供されるメモリ領域と、前記メモリ領域からの積Ｐを外部システムに提供するように構成される出力部とを具備する乗算装置又は構成に関する。本発明は、Ｙ＜Ｘであるアドレス語により指定されるメモリ領域内のセルは除去されていることを特徴とする。
2009516248.tif 000002
【特許請求の範囲】
【請求項１】
第１の番号Ｘを含む前半部分及び第２の番号Ｙを含む後半部分を有するアドレス語を外部システムから受信するように構成されるアドレス部（３２０）と、
前記アドレス語により指定されるように構成されるＭ×Ｍ個のメモリセルを含み、ある特定のアドレス語により指定されるセルに前記第１の番号Ｘと前記第２の番号Ｙとの積Ｐが提供されるメモリ領域（３１０）と、
前記メモリ領域（３２０）からの積Ｐを外部システムに提供するように構成される出力部（３３０）と、
を具備し、
Ｙ＜Ｘであるアドレス語により指定される前記メモリ領域（３１０）内の前記セルは除去されていることを特徴とする乗算装置（３００）。
【請求項２】
Ｘ＝Ｙであるアドレス語により指定される前記メモリ領域（３１０）内の前記セルの内容は、Ｘ＝０でありＹ＝Ｙであるアドレス語により指定される前記セルの内容を置換するように移動されていることを特徴とする請求項１記載の乗算装置（３００）。
【請求項３】
Ｘ≧Ｍ／２であるアドレス語により指定される前記メモリ領域（３１０）内のセルの内容は、Ｘ＝Ｍ−１−ＸでありＹ＝Ｍ−１−Ｙであるアドレス語により指定されるセルの内容を置換するように移動されていることを特徴とする請求項１又は２記載の乗算装置（３００）。
【請求項４】
前記アドレス部（３２０）は、Ｙ＜Ｘの場合に前記第１のアドレス番号Ｘの位置と前記第２のアドレス番号Ｙの位置とをスワップし、前記アドレス番号Ｘ、Ｙを前記メモリ領域（３１０）に転送するように構成されることを特徴とする請求項１記載の乗算装置（３００）。
【請求項５】
前記アドレス部（３２０）は、前記アドレス語の前半部分の前記位置と前記アドレス語の後半部分の前記位置とをスワップし、前記アドレス語を前記メモリ領域（３１０）に転送するように構成されることを特徴とする請求項１記載の乗算装置（３００）。
【請求項６】
前記出力部（３００）は、Ｘ＝０又はＹ＝０の場合に前記積Ｐを０に設定するように構成されることを特徴とする請求項２記載の乗算装置（３００）。
【請求項７】
前記アドレス部（３２０）は、
Ｙ＜Ｘの場合に前記第１のアドレス番号Ｘの前記位置と前記第２のアドレス番号Ｙの前記位置とをスワップし、
Ｘ＝Ｙの場合にＸを０に設定し、
前記アドレス番号Ｘ、Ｙを前記メモリ領域（３１０）に転送する
ように構成されることを特徴とする請求項２記載の乗算装置（３００）。
【請求項８】
前記アドレス部（３２０）は、
Ｙ＜Ｘの場合に前記第１のアドレス番号Ｘの前記位置と前記第２のアドレス番号Ｙの前記位置とをスワップし、
Ｘ＝Ｙの場合にＸを０に設定し、
前記第１の番号ＸのＭＳＢが設定される場合に前記第１の番号Ｘ及び前記第２の番号Ｙを反転し、
前記アドレス番号Ｘ、Ｙを前記メモリ領域（３１０）に転送する
ように構成されることを特徴とする請求項３記載の乗算装置（３００）。
【請求項９】
乗算装置（３００）をアドレス指定する方法であって、
前記乗算装置（３００）は
第１の番号Ｘを含む前半部分と第２の番号Ｙを含む後半部分とを有するアドレス語を外部システムから受信するように構成されるアドレス部（３２０）と、
前記アドレス語により指定されるように構成されるＭ×Ｍ個のメモリセルを含み、ある特定のアドレス語により指定されるセルに前記アドレス語の前記第１の番号Ｘと前記第２の番号Ｙとの積Ｐが提供されるメモリ領域（３１０）と、
前記メモリ領域（３２０）からの積Ｐを外部システムに提供するように構成される出力部（３３０）と、
を具備し、
Ｙ＜Ｘであるアドレス語により指定されている前記メモリ領域（３１０）内の前記セルを除去するステップと、
前記外部システムからアドレス語を受信するステップと、
Ｙ＜Ｘの場合に前記アドレス語における前記第１の番号Ｘの位置と前記第２の番号Ｙの位置とをスワップするステップと、
前記アドレス語の前記番号Ｘ、Ｙを前記メモリ領域（３１０）に転送するステップと、
を有する方法。
【請求項１０】
前記受信したアドレス語の前記前半部分の前記位置と前記後半部分の前記位置とをスワップするステップを含む請求項９記載の方法。
【請求項１１】
Ｘ＝０又はＹ＝０の場合に前記積Ｐを０に設定するステップと、
前記積Ｐを前記出力部（３３０）に転送するステップと、
を有する請求項９又は１０記載の方法。
【請求項１２】
Ｘ＝Ｙであるアドレス語により指定されている前記メモリ領域（３１０）内の前記セルの内容をＸ＝０でありＹ＝Ｙであるアドレス語により指定されているセルに移動するステップと、
Ｘ＝Ｙの場合に前記受信したアドレス語における前記アドレス番号Ｘを０に設定するステップと、
前記アドレス番号Ｘ、Ｙを前記メモリ領域（３１０）に転送するステップと、
を有する請求項９記載の方法。
【請求項１３】
Ｘ＝Ｍ−１−ＸでありＹ＝Ｍ−１−Ｙであるアドレス語により指定されているセルの内容を置換するように、Ｘ≧Ｍ／２であるアドレス語により指定されている前記セルの前記内容を移動するステップと、
前記第１の番号ＸのＭＳＢが設定される場合は、前記受信したアドレスにおける前記第１の番号Ｘ及び前記第２の番号Ｙを反転するステップと、
前記アドレス番号Ｘ、Ｙを前記メモリ領域（３１０）に転送するステップと、
を有する請求項１２記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルデータ処理に関連して数を乗算する装置又は構成に関する。特に、本発明は、有限な数の被乗数及び乗数からの積を含むテーブルに関する。より特定すると、本発明は、そのようなテーブルにより占有される空間又は領域に関する。
【背景技術】
【０００２】
デジタルデータ処理に関連して、例えばデジタル信号処理（ＤＳＰ）においては、有限インパルス応答（ＦＩＲフィルタ）等の異なるデジタルフィルタを実現するため、あるいは高速フーリエ変換（ＦＦＴ）等の異なる変換動作を実現するため等、ある特定の機能又は効果、あるいは他の結果を達成するために、多くの場合において種々の数を乗算する必要がある。そのような目的のために、ソフトウェアにより実現される乗算器及びハードウェアにより実現される乗算器を含む複数の周知の乗算器が従来技術において利用可能である。
【０００３】
しかしながら、実質的にソフトウェアにより実現される乗算器は、いくつかの状況において、特に、処理がリアルタイムで実行される場合、現在のデジタル信号処理の必要を満たすには速度が遅い。従って、リアルタイムの用途及び速度に対する要求が重要な他の用途においては、通常、ハードウェアにより実現されるか又は少なくとも実質的にハードウェアにより実現される乗算器を使用することが好ましい。
【０００４】
一般に、ハードウェア乗算器は当該技術において周知である。ハードウェア乗算器は、通常、ハードウェアにより実現されるアルゴリズムにより乗算を行う。これらのアルゴリズムが、人間が筆記で２つの多桁数の乗算を行う方法を再現又は模倣することは珍しいことではない。そのようなアルゴリズムは、例えば、乗算、桁移動及び加算を含んでもよい。
【０００５】
図１は、２つの４桁の２進数Ａ及びＢを乗算するそのようなアルゴリズムの使用を概略的に示す図である。周知のように、最初に、数Ｂの最も右の位置にある桁Ｂ0は数Ａを掛けて第１の２進部分積Ｂ0×Ａ２0を形成する。この場合、２0は第１の部分積の最下位ビットが重み２0を有することを示す。次に、数Ｂの次の位置の桁Ｂ1は数Ａを掛けて第２の２進部分積Ｂ1×Ａ２1を形成する。この場合、２1は第２の部分積の最下位ビットが重み２1を有することを示す。これは、数Ｂの全ての桁に数Ａを掛けるまで周知の方法で繰り返される。その後、図１に概略的に示すように、全ての部分積は周知の方法で適切に桁移動及び加算されて最終積Ｐを形成する。当然、種々のハードウェア乗算器は、他のアルゴリズム及び／又は上述の好適なアルゴリズムの変形を使用してもよい。
【０００６】
実質的にアルゴリズムに基づくハードウェア乗算器に対して、本発明は、有限な数の乗算に対応する事前に計算された積を含むルックアップテーブルに関する。
【０００７】
通常、ルックアップテーブルは、Ｍ列×Ｍ行（Ｎを「ビット解像度」とすると、Ｍは２Nに等しい）のサイズを有するメモリマトリクスであり、Ｍ−１は使用可能な最大被乗数である。有限な数の乗算からの積は事前に計算され、メモリマトリクスの適切なメモリセルに格納される。図２は、上述の種類の乗算メモリマトリクスの一例を概略的に示す図である。
【０００８】
図２に示す乗算メモリマトリクス内のセルは、通常、位置ｍ，ｎのセルがｍ×ｎの積を有するように構成される。これは、位置０，０のセルが０×０の積を有し、位置０，Ｍ−１のセルが０×（Ｍ−１）の積を有することを意味する。事前に計算されたｍ×ｎの積は、数値ｍ及びｎを含むアドレス又は数値ｍ及びｎに対応する番号を含むアドレスを使用して位置ｍ，ｎのセルをアドレス指定することによって周知の方法で検索される。
【０００９】
簡潔にするために、メモリセルの内容は整数であると考えられてもよいが、同一の説明は固定表現又は浮動表現等の他の形式にも同様に適用する。
【００１０】
通常、図２に概略的に示すような乗算メモリマトリクス及び同様のメモリ又はルックアップテーブルは、通常のデータメモリ又は同様の記憶装置、あるいはＤＳＰ装置に適し、通常使用されるシリコン又は他の物質上に実現される。
【００１１】
一般に、概略的に上述された乗算メモリマトリクス又はルックアップテーブルは、それらが実現されるシリコン又は同様の物質のかなり大きな領域を占有する。特に、被乗数Ｍ−１の値が大きい場合、かなり大きな領域を占有する。これは、大きい数を含むために大きなメモリセルを有する大きなマトリクス構造が形成されるためである。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
従って、より小さい領域又は空間を占有する改善された乗算メモリマトリクス又はルックアップテーブル、あるいは同様の物が必要とされる。
【課題を解決するための手段】
【００１３】
本発明は、より小さい領域又は空間を占有する改善された乗算メモリ装置又は構成を提供する。
【００１４】
これは、第１の番号Ｘを含む前半部分及び第２の番号Ｙを含む後半部分を有するアドレス語を外部システム、例えば外部デジタル信号処理システムから受信するように構成されるアドレス部を具備する乗算構成により達成される。乗算構成は、前記アドレス語により指定されるように構成されるＭ×Ｍ個のメモリセル又は同様の格納位置を有するメモリ領域を更に具備する。特定のアドレス語により指定されるセルには、当該アドレスの第１の番号Ｘと第２の番号Ｙとの積Ｐが提供される。更に、乗算構成は、メモリ領域からの積Ｐを外部システム、例えば外部デジタル信号処理システムに提供するように構成される出力部を具備する。
【００１５】
乗算構成は、Ｙ＜Ｘであるアドレス語により指定されるメモリ領域内のセル及びその内容が本発明により乗算される数の可換性によって重複するため、そのようなセルが除去されていることを特徴とする。従って、メモリ領域のほぼ半分は除去される。
【００１６】
縮小されたメモリ領域は、乗算構成のアドレス部がＹ＜Ｘの場合にアドレス語における前記第１のアドレス番号Ｘの位置と前記第２のアドレス番号Ｙの位置とをスワップし、２つのスワップされたアドレス番号をメモリ領域に転送するように構成される実施形態により利用される。あるいは、アドレス部は、前記アドレス語の前半部分の位置と後半部分の位置とをスワップするように構成されてもよい。これは、本発明のある特定の実施形態がこの２つの部分以外のアドレス語の部分をスワップしてもよいことを示す。アドレス部は乗算構成に一体化されてもよく、あるいは乗算構成と直接又は間接的に通信する外部装置として構成されてもよいことが強調されるべきである。
【００１７】
上述のような縮小されたメモリ領域の更なる実施形態は、Ｘ＝０でありＹ＝Ｙであるアドレス語により指定されるセルの内容を置換するように、Ｘ＝Ｙであるアドレス語により指定されるセルの内容が移動されていることを特徴とする。換言すると、Ｍ×Ｍメモリ領域の対角線にあるセルの内容は、Ｘ＝０であるメモリ領域の列にあるセルの内容を置換するように移動されている。これにより、メモリ領域の更なる縮小が可能になる。
【００１８】
メモリ領域は、前記出力部がＸ＝０又はＹ＝０の場合に積Ｐを０に設定するように構成される乗算構成の実施形態により利用されるのが好ましい。
【００１９】
このメモリ領域は、前記アドレス部がＹ＜Ｘの場合に前記第１のアドレス番号Ｘの位置と前記第２のアドレス番号Ｙの位置とをスワップするように構成され、Ｘ＝Ｙの場合にＸを０に設定するように構成され、アドレス番号Ｘ、Ｙをメモリ領域に転送するように更に構成される乗算構成の実施形態により更に利用される。
【００２０】
上述のようにセルを除去及び移動することにより、メモリ領域の更なる改善が可能である。これは、Ｘ＝Ｍ−１−ＸでありＹ＝Ｍ−１−Ｙであるアドレス語により指定されるセルの内容を置換するようにＸ≧Ｍ／２であるアドレス語により指定されるメモリ領域内のセルの内容が移動されている実施形態により実現される。換言すると、メモリ領域の区画はメモリ領域の対角線において鏡映される。
【００２１】
メモリ領域は、前記アドレス部が、Ｙ＜Ｘの場合に前記第１のアドレス番号Ｘの位置と前記第２のアドレス番号Ｙの位置とをスワップするように構成され、Ｘ＝Ｙの場合にＸを０に設定するように構成され、第１の番号ＸのＭＳＢが設定される場合に第１の番号Ｘ及び第２の番号Ｙを反転するように構成され、アドレス番号Ｘ、Ｙをメモリ領域に転送するように更に構成される乗算構成の実施形態により利用される。これにより、アドレスバス、又は乗算メモリマトリクスのメモリ領域をアドレス指定する同様の物の幅を減少できる。更に、より対称で小型のメモリ領域を実現できる。
【００２２】
本発明は、上述のような乗算メモリ構成をアドレス指定する方法を更に提供する。
【００２３】
これは、第１の番号Ｘを含む前半部分及び第２の番号Ｙを含む後半部分を有するアドレス語を外部システムから受信するように構成されるアドレス部と、前記アドレス語により指定されるように構成されるＭ×Ｍ個のメモリセルを含み、ある特定のアドレス語により指定されるセルにアドレス語の第１の番号Ｘと第２の番号Ｙとの積Ｐが提供されるメモリ領域と、メモリ領域（３２０）からの積Ｐを外部システムに提供するように構成される出力部（３３０）とを具備する乗算構成をアドレス指定する方法により実現される。方法は、Ｙ＜Ｘであるアドレス語により指定されているメモリ領域（３１０）内のセルを除去するステップと、前記外部システムからアドレス語を受信するステップと、Ｙ＜Ｘの場合に前記アドレス語における前記第１の番号Ｘの位置と前記第２の番号Ｙの位置とをスワップするステップと、アドレス語の番号Ｘ、Ｙをメモリ領域に転送するステップとを有する。
【００２４】
方法の一実施形態は、受信したアドレス語の前半部分の位置と後半部分の位置とをスワップするステップと、アドレス語をメモリ領域に転送するステップとを含む。
【００２５】
方法の別の実施形態は、Ｘ＝０又はＹ＝０の場合に積Ｐを０に設定するステップと、積Ｐを出力部（３３０）に転送するステップとを含む。
【００２６】
上述の方法ステップにおいて規定されるメモリ領域（３１０）に適用される方法の更に別の実施形態は、Ｘ＝Ｙであるアドレス語により指定されているセルの内容をＸ＝０でありＹ＝Ｙであるアドレス語により指定されているセルに移動するステップと、Ｘ＝Ｙの場合に受信したアドレス語におけるアドレス番号Ｘを０に設定するステップと、アドレス番号Ｘ、Ｙをメモリ領域に転送するステップとを含む。
【００２７】
上述の方法ステップにおいて規定されるメモリ領域（３１０）に適用される本方法の更に別の実施形態は、Ｘ＝Ｍ−１−ＸでありＹ＝Ｍ−１−Ｙであるアドレス語により指定されているセルの内容を置換するようにＸ≧Ｍ／２であるアドレス語により指定されているセルの内容を移動するステップと、第１の番号ＸのＭＳＢが設定される場合は受信したアドレスにおける第１の番号Ｘ及び第２の番号Ｙを反転するステップと、アドレス番号Ｘ、Ｙをメモリ領域（３１０）に転送するステップとを含む。
【００２８】
本発明の上記の面及びその他の面は、本発明の実施形態の以下の説明より明らかになるだろう。
【発明を実施するための最良の形態】
【００２９】
本発明の好適な実施形態を参照して、本発明をより詳細に説明する。本発明の更なる実施形態が考えられることは明らかであり、本発明は、以下に説明する乗算メモリマトリクス（ルックアップテーブル）の実施形態に限定されない。以下の説明において、同一又は同様の図中符号は、全ての説明及び添付の図面において同一又は同様の物体及び／又は機能を示す。
【００３０】
図３は、好適な乗算メモリマトリクス３００を概略的に示す図である。乗算メモリマトリクス３００は、メモリ領域３１０、アドレス部３２０及び出力部３３０を具備する。メモリマトリクス３００の基本構造は、シリコン構造又は他の任意の適切なハードウェア構造の上に周知の方法で実現される通常のデータメモリの構造と同一であるか又は少なくとも非常に類似しているのが好ましい。
【００３１】
図３のメモリ領域３１０は８×８個のメモリセル、すなわち、メモリセルの８行×８列に限定されている。この場合、３を「ビット解像度」とすると８は２3に等しく、８−１＝７は使用可能な最大被乗数である。しかしながら、例えば、図２に概略的に示すように、メモリ領域３１０がメモリセルのＭ行×Ｍ列を有してもよく、この場合、Ｎを「ビット解像度」とするとＭは２Nに等しく、Ｍ−１が使用可能な最大被乗数であることが理解されるべきである。
【００３２】
好適なアドレス部３２０は、例えば、通常のデータメモリ又は同様のアドレス指定可能な装置のアドレスバスと同一の方法又は非常に類似した方法で、デジタルデータ処理システム又は同様の物の外部２進アドレスバス又は同様の物に接続され、それから出力されるアドレス信号又は同様の物を受信するように構成される。図３において、アドレスバス接続をアドレス部３２０を指す矢印６ａで示す。符号６ａは、好適な２進アドレスバスが６ビットの幅を有することを示す。これは、２進アドレスバスが２6＝６４個のメモリセル、すなわち８×８個のセルを指定できることを示す。
【００３３】
好適な出力部３３０は、乗算メモリマトリクス３００からの乗算の積を外部デジタルデータ処理システムの２進データバスに提供するために、前記外部システムの前記データバスに接続されるように構成される。換言すると、出力部３３０は、通常のデータメモリ又は同様の格納装置の出力データ信号と同一又は同様の方法で外部データバスに接続されるように構成される。図３において、データバス接続を出力部３３０から外側を指す矢印６ｐで示す。符号６ｐは、好適な２進データバスが６ビットの幅を有することを示す。これは、データバスが６３（２進数１１１１１１）と大きな積を好適な乗算メモリマトリクス３００から転送できることを示す。出力部３３０は、メモリ領域３１０から出力される積を内部データバスを介して受信する。図３において、内部データバスをメモリ領域３１０から出力部３３０の方向を指す矢印６ｐで示す。この符号６ｐは、通信が６ビットの幅であることを示す。更に、出力部３３０には、以下に更に説明する上述の６ビットアドレスバスが更に設けられてもよい。図３において、このアドレスバスを出力部３３０の方向を指す破線６ａで示す。
【００３４】
図３の好適な乗算メモリマトリクス３００の基本機能は、通常のデータメモリの機能と同様である。従って、アドレス値がアドレス部３２０に書き込まれると、メモリ領域３１０内の１つのセルが指定され、その特定のセルに現在格納されている内容は出力部３３０を介して外部２進データバスに書き込まれる。その結果、特定のアドレスにある特定の方法で対応する積がこの特定のアドレスにより指定されるメモリセルに事前格納されている場合、図３のメモリマトリクス３００の基本機能によって乗算機能が実現可能になる。
【００３５】
図３において、好適な乗算メモリマトリクス３００内のメモリ領域３１０のアドレス指定をアドレスブロック３２０からメモリ領域３１０の方向を指す第１及び第２の矢印で概略的に示す。２つの矢印の各々の符号３は、上述の好適な６ビットアドレスバスがアドレスブロック３２０により半分に分割され、その結果、各々が３ビットを有する２つのバス又は部分になったことを示す。第１の矢印により表される３ビットは被乗数を搬送し、第２の矢印により表される３ビットは乗数を搬送する。あるいは、第１の矢印により表される３ビットは乗数を搬送し、第２の矢印により表される３ビットは被乗数を搬送する。従って、図３の２つの矢印は、６ビットアドレスバスの前半部分が被乗数を表し、６ビットアドレスの他方の半分が乗数を表すこと、あるいは６ビットアドレスバスの前半部分が乗数を表し、６ビットアドレスの他方の半分が被乗数を表すことを概略的に示す。
【００３６】
既に上述したように、乗算機能は、特定の６ビットアドレスにより指定されるセルに６ビットアドレスの前半部分の３ビットにより表される数値と６ビットアドレスの後半部分の３ビットにより表される数値との積を事前に格納することにより実現される。
【００３７】
換言すると、図３の乗算メモリマトリクス３００の個々のセルには、各々の特定のアドレスの前半部分及び後半部分に見出される被乗数及び乗数に対応する積がそれぞれ提供される。
【００３８】
従って、メモリ領域３１０内に概略的に示す８×８個のメモリセルは、Ｘ，Ｙによりアドレス指定されるセルがＸ×Ｙと示されるように、それぞれの乗算で示されている。すなわち、アドレス０，０により指定されるセルは０×０で示され、１，１により指定されるセルは１×１で示される。Ｘ，Ｙの表記は、図３の６ビットアドレスバス６ｐから受信される６ビットアドレスにより規定されるアドレスを表す。この場合、Ｘは６ビットアドレスの前半部分の値を表し、Ｙは６ビットアドレスの後半部分の値を表す。あるいは、Ｘは６ビットアドレスの後半部分の値を表し、Ｙは６ビットアドレスの前半部分の値を表してもよい。
【００３９】
簡潔にするために、メモリ領域３１０内のメモリセルの内容は整数として考えられてもよい。しかしながら、同一の説明は固定表現又は浮動表現等の他の形式にも同様に当てはまる。
【００４０】
図４は、図３の好適な乗算メモリマトリクス３００に対するアドレス、被乗数、乗数及び積の間の関係を示す表である。表の左上端部は、「アドレスバス（６ビット、２進）」と示される上部欄である。これは、下方の２つの列が図３の６ビットアドレスバス６ａで受信したアドレスの２進値を含むことを示す。前記上部欄の直下には２つの欄があり、左欄は「前半部分（３ビット２進）」と示され、右欄は「後半部分（３ビット２進）」と示される。これは、受信した６ビットアドレスの２進ビットが各々が３ビットを含む２つの集合に分割されていることを示す。前記上部欄の右側には４つの上部欄がある。第１の欄は「Ａｄｄｒ」、第２の欄は「Ｍ１」、第３の欄は「Ｍ２」、第４の欄は「Ｐ」と示される。略語「Ａｄｄｒ」は、メモリマトリクス３００におけるセルアドレスを表す。略語「Ｍ１」及び「Ｍ２」は、６ビットアドレスバスから受信されるアドレスの前記前半部分及び前記後半部分において見出される被乗数又は乗数を表す。略語「Ｐ」は、前記アドレスの前記前半部分及び前記後半部分において見出される前記被乗数と前記乗数との積を表す。従って、欄「Ａｄｄｒ」、「Ｍ１］、「Ｍ２」及び「Ｐ」の下方に続く列は、関連するアドレスの値、これらのアドレスに対応する被乗数／乗数及び当該被乗数／乗数の積を含む。上述の欄の下方には「Ｃ０」と示される行がある。同様の行は、図４の表の９行毎に繰り返さる。これらの行は「Ｃｎ」と示され、行が出現する度にｎが１ずつ増加される。これらの行は、図３の好適なメモリ領域３１０における列０〜７に対応し、図４の表における各行「Ｃｎ」（ｎ＝１〜７）の下方の異なる値は、図３のメモリ領域３１０の対応する列におけるセルのアドレス、被乗数、乗数及び積に対応する。
【００４１】
本発明は、乗算メモリマトリクス３００おけるアドレス指定及び積の格納は効率が悪いという観測に基づく。本発明の実施形態を参照して、これらの条件の改善を以下に説明する。
【００４２】
本発明の実施形態を説明する際の前提として、組Ｓの２つの任意の要素ｘ及びｙが以下の式を満たす場合、要素ｘ及びｙは２項演算において可換であるとする。
【００４３】
ｘ＊ｙ＝ｙ＊ｘ                                                        （１）
整数等の通常の数は、加算において可換である。
【００４４】
ｘ＋ｙ＝ｙ＋ｘ                                                        （２）
また、これらは乗算において可換である。
【００４５】
ｘ・ｙ＝ｙ・ｘ                                                        （３）
このことに注目することで、図３に示す乗算メモリマトリクス３００のサイズをいくつかの特定のステップによって縮小することが可能になる。そのような特定のステップは、以下に更に詳細に説明するように、変更され、サイズの縮小された乗算メモリマトリクスを達成する。
【００４６】
（対角線における分割）
２つの数の乗算が可換であるという事実は、図３のマトリクス３００のほぼ半分が他方の半分の複写であることを示す。すなわち、ほぼ全ての積がマトリクス３００内に２回出現することを示す。これは、図３の好適な乗算メモリマトリクス３００のメモリ領域３１０を確認することにより容易に立証される。このメモリ領域３１０においては、ほぼ全ての乗算が２回出現する。同じことは、図３のメモリ領域３１０におけるアドレス、被乗数、乗数及び積の間の関係を示す図４の表を確認することにより容易に立証される。本表において、ほぼ全ての積「Ｐ」は２回出現する。
【００４７】
従って、上述の数の可換性のため、マトリクス３００のほぼ半分は重複する。そのため、マトリクス３００を半分又はほぼ半分に縮小できる。
【００４８】
これは、Ｙ＜Ｘの場合に上述のアドレス値Ｘ及びＹが常にスワップされることにより実現される。これは非常に簡単な論理演算である。好適な乗算メモリマトリクス３００における６ビットアドレスバスに適用する場合、これは、６ビットバスの前半部分（３ビット）における値Ｘが６ビットバスの後半部分（３ビット）における値Ｙより大きい場合にこの２つのアドレス値に対してスワップが実行され、その結果、位置が交換されることを意味する。スワップの結果、前半部分の値がｍであって後半部分の値がｎであるか又は前半部分の値がｎであって後半部分の値がｍであるかに関係なく、同一の６ビットアドレスが常に指定される。番号Ｘ及びＹが可換であり、すなわち積ｘ・ｙが積ｙ・ｘと同一であるため、このスワップは明らかに受け入れられる。
【００４９】
図５は、Ｍビットの幅を有する２進のアドレス語によって２M個のメモリセルが指定される図２に先に示した一般的な乗算メモリマトリクスに対して実行された上述のスワップの結果を示す。図からわかるように、マトリクスをアドレス指定するアドレス語の前半部分におけるアドレス値Ｘが前記アドレス語の後半部分におけるアドレス値Ｙより大きい全てのメモリセルは除去される。これは、除去されるセルを斜線で網掛けにすることにより示される。
【００５０】
図６は、６ビットの幅を有する２進のアドレス語により２6個のメモリセルが指定される図３に先に示した特定の好適な乗算メモリマトリクス３００のメモリ領域３１０を示す。図からわかるように、メモリ領域３１０をアドレス指定する２進の語の前半部分におけるアドレス値Ｘが２進のアドレス語の後半部分におけるアドレス値Ｙより大きい全てのメモリセルは除去される。これは、除去されるセル内の二重取り消し線により示される。
【００５１】
図７の表は、図４に先に示した表と同一である。しかしながら、図６のメモリ領域３１０において除去されるセルと同一のアドレスを有するメモリセルは図７の表中で同様に除去されている。これは、除去されるセル内の二重取り消し線により示される。
【００５２】
図８は、Ｙ＜Ｘの場合にマトリクス３００における６ビットアドレスバスのＸ値及びＹ値の上述のスワップを実現する好適なハードウェア設計を概略的に示す図である。ハードウェア設計及びスワップ機能はアドレス部３２０の一部であるのが好ましいが、他の解決策が考えられることは明らかである。図８のハードウェア設計は、スワップ部８１０及び比較部８２０を具備する。スワップ部８１０には６ビットアドレスバスが設けられる。スワップ部８１０は、Ｘ及びＹの値をスワップし、それらの値がアドレス部３２０から２つの３ビット出力バスのいずれか一方に出力されるようにするように構成される。同様に、比較部８２０には６ビットアドレスバスが設けられる。比較部８２０は、Ｘ及びＹの値を比較し、Ｙ＜Ｘの場合にはスワップ部を動作してＸとＹとをスワップさせるように構成される。この動作は、比較部８２０からスワップ部８１０内の６個の二路スイッチを介して延出する破線により示されている。上述のスワップを実現するにはハードウェア設計が好ましいが、本発明の他の実施形態が完全又は少なくとも部分的にソフトウェアに基づく設計によりスワップを実現してもよいことが追記されるべきである。これは、例えば、リアルタイムに実行される用途ではない場合等、時間が重要ではない用途の場合に特に当てはまる。
【００５３】
（０番目の列の消去）
ｘ・０＝ｙ・０＝０が真であるため、これらの場合に対する計算は必要なく、そのため、図２及び図５の一般的な乗算メモリマトリクスにおける０番目の行及び０番目の列は除去される。しかしながら、０番目の行は上述のスワップ動作により既に除去されているため、除去するのは０番目の列だけである。
【００５４】
図９は、前述で図５に示した一般的な乗算メモリマトリクスにおける０番目の列の消去を示す。図からわかるように、アドレス値Ｘ＝０であるメモリセルの内容は消去されている。スワップ動作により一般的なマトリクスから事前に除去されたメモリセルは網点により網掛けされ、ここで消去される０番目の列は斜線で網掛けされる。尚、０番目の列のセルは、以下に更に説明するように後続のステップにおいて使用されるため、消去されるが除去されない。
【００５５】
図１０は、前述で図６に示した特定の乗算メモリマトリクス３００のメモリ領域３１０における０番目の列の消去を示す。図からわかるように、アドレス値Ｘ＝０であるメモリセルの内容は消去されている。スワップ動作によりマトリクス３００から事前に除去されたメモリセル及びここで消去される０番目の列は二重取り消し線で示される。尚、０番目の列のセルは、以下に更に説明するように後続のステップにおいて使用されるため、消去されるが除去されない。
【００５６】
図１１は、積ｘ・０＝ｙ・０＝０を生成する好適なハードウェア設計を概略的に示す図である。これは、例えば、切り替え部１１１０及び比較部１１２０を利用することにより実現される。切り替え部１１１０及び比較部１１２０は出力部３３０の一部であるのが好ましいが、他の解決策が考えられることは明らかである。切り替え部１１１０は、接地記号で示される２進のゼロ信号及びメモリ領域３１０からの積データを提供される。更に、切り替え部１１１０は、第１の切り替え位置においては６ビットデータバスに２進のゼロを送信し、第２の切り替え位置においては６ビットデータバスに２進の積データを送信するように構成される。出力部３３０内の比較部１１２０は、図３に概略的に示すように、６ビットアドレスバスからアドレスを提供される。比較部１１２０は、アドレスのＸ値とＹ値とを比較し、Ｘ＝０又はＹ＝０の場合は６ビットデータバスに２進のゼロを送信し、Ｘ≠０、Ｙ≠０の場合はメモリ領域３１０から受信される２進の積データを６ビットデータバスに送信するように切り替え部１１１０を動作するように構成される。この動作は、比較部１１２０から切り替え部１１１０内の６個の二路スイッチを介して延出する破線により示される。乗算ｘ・０＝ｙ・０＝０を行うためにメモリ領域３１０をアドレス指定する必要がないと考えられる。また、上述の切り替えを実現するにはハードウェア設計が好ましいが、本発明の他の実施形態が完全又は少なくとも部分的にソフトウェアに基づく設計により切り替えを実現してもよいことが追記されるべきである。これは、例えば、リアルタイムに実行される用途ではない場合等、時間が重要な用途ではない場合に特に当てはまる。
【００５７】
（消去された０番目の列への対角線の移動）
上述のように０番目の列における相対的に少ない要素の内容を消去することは不必要なことに見えるかもしれない。しかしながら、以下に説明するように、これは不必要なことではない。
【００５８】
以上では省略された特別な場合、すなわち、上述の値がＸ＝Ｙである場合がある。これを考慮しなければ、ここで説明するこの種類の乗算メモリマトリクスは大きくなりすぎる。解決策は、上述に従って事前に消去された０番目の列のメモリセルにこの特別な場合（Ｘ＝Ｙ）をマップすることである。これは、Ｘ＝Ｙの場合にＸ＝０を設定することにより実現される。これも迅速・簡単な論理演算である。従って、関連する積は新しいアドレスに移動される。
【００５９】
図１２は、前述で図９に示した一般的な乗算メモリマトリクスを示す。図からわかるように、アドレス値Ｘ＝Ｙであるメモリセルの内容は事前に消去された０番目の列に移動されている。この結果、図１２のメモリマトリクスにおいて左方向の水平移動が行われる。これは、左を指す矢印により示される。図１２において、スワップ動作により事前に除去されたメモリセルは網点により網掛けされる。ここで０番目の列に移動される対角線は斜線で網掛けされ、０番目の列は正方形の模様を形成する垂直な斜線で網掛けされる。
【００６０】
図１３は、前述で図１０に示した特定の乗算メモリマトリクス３００のメモリ領域３１０を示す。図からわかるように、アドレス値Ｘ＝Ｙであるメモリセルの内容は同一のアドレス値Ｙ及びＸ＝Ｙではなく新しいアドレス値Ｘ＝０を有する対応するメモリセルに移動されている。これは、メモリ領域３１０の対角線内の消去されたセルにおいて二重取り消し線で示される。
【００６１】
図１４は、Ｘ＝Ｙである特別な場合における上述の対角線の移動を実現する好適なハードウェア設計を概略的に示す図である。これは、例えば、図１４に示すような切り替え部１４１０及び比較部１４２０を利用することにより達成されてもよい。切り替え部１４１０及び比較部１４２０はアドレスブロック部３２０の一部であるのが好ましいが、他の解決策が考えられることは明らかである。切り替え部１４１０は、接地記号で示される２進のゼロ信号と、上述のように値Ｘ及びＹを含む６ビットアドレスバスからのアドレスとを提供される。切り替え部１４１０は、Ｘの値を２進のゼロと６ビットアドレスバスから受信されるＸの実際の値との間で切り替えるように構成される。同様に、比較部１４２０は６ビットアドレスバスからのアドレスを提供される。比較部１４２０は、値Ｘと値Ｙとを比較し、Ｘ＝Ｙの場合はＸの値を２進のゼロに設定し、Ｘ＝Ｙではない場合はＸの値をそのまま通過させるように切り替え部１４１０を動作するように構成される。この動作は、比較部１４２０から切り替え部１４１０内の３つのスイッチを介して延出する破線により示される。上述の切り替えを実現するにはハードウェア設計が好ましいが、本発明の他の実施形態が完全又は少なくとも部分的にソフトウェアに基づく設計により切り替えを実現してもよいことが追記されるべきである。これは、例えば、リアルタイムに実行される用途ではない場合等、時間が重要な用途ではない場合に特に当てはまる。
【００６２】
図１４からわかるように、６ビットアドレスバスのＸ値及びＹ値は前述のスワップ部８１０を介して切り替え部１４１０に提供される。これは、スワップ部はＸ＝Ｙの場合にＸ値及びＹ値を変更しないが、切り替え部１４１０はＸ＝Ｙの場合以外Ｘ値及びＹ値を変更しないため、この順番で行われる。
【００６３】
上述した図１３のメモリ領域３１０の対角線から０番目の列へのメモリセルの移動は、以下に示す表形式の再構成に対応する。
【００６４】
【表１】
2009516248.tif 000003
【００６５】
表は図７の表の一部である。図１３に示すメモリ領域３１０において新しい値を提供されたメモリセルは、上記の表中で新しい値を同様に受け取っており、メモリ領域３１０において除去されたメモリセルは、上記の表中で同様に消去されている。消去された値及び消去されたセルは表中で二重取り消し線により示され、新しい値は消去された値の隣に適切に追加されている。除去されたセルは表中の斜線部の下方に見られ、新しい値は斜線部の上方のセルに挿入される。
【００６６】
（対角線における鏡映）
上述のように達成される乗算メモリマトリクスは、マトリクスの半分より多くの部分が現在は除去されているにも関わらず、行及び列のほぼ全ての範囲を依然として使用する。特に、広いアドレスバスが狭いバスよりシリコン構造等に関連して多くの空間を必要とすることを考慮すると、これは多くの場合において不利である。従って、図１２の一般的な乗法メモリマトリクスの右上の三角形部分を同一サイズの空き領域に移動して再適合することにより、更なる改善が達成される。
【００６７】
図１５において、上述で図１２に示した変更された一般的な乗算メモリマトリクスのこの再構成は、メモリセルの移動方向を示す曲がり矢印により示されている。図１５に示す移動は、メモリマトリクスの対角線における鏡映に対応する。上述で達成された乗法メモリマトリクス、すなわち、図１２に示した一般的な乗算メモリマトリクスにおいて、Ｘ≧Ｍ／２の場合に列Ｘ＝Ｍ−１−Ｘとし、行Ｙ＝Ｍ−１−Ｙとすることにより、この移動は達成される。２進項に関しては、これはＸのＭＳＢが設定される場合にＸ及びＹを反転することに等しく、簡単な論理演算である。
【００６８】
図１６は、上述で図１３に示した特定の乗算メモリマトリクス３００のメモリ領域３１０の対角線における鏡映を示す。表形式において、以下の再構成が行われている。
【００６９】
【表２】
2009516248.tif 000004
【００７０】
上記の表は図７の表の一部である。図１６に示すメモリ領域３１０において新しい値を提供されたメモリセルは、上記の表中で新しい値を同様に受け取っており、メモリ領域３１０において除去されたメモリセルは、上記の表中で同様に除去されている。除去された値及び除去されたセルは表中で二重取り消し線により示され、新しい値は消去された値の隣に適切に追加されている。除去されたセルは表中の斜線部の下方に見られ、新しい値は斜線部の上方のセルに挿入される。
【００７１】
図１７は、特定の乗算メモリマトリクス３００のメモリ領域３１０における上述の鏡映を実現する好適なハードウェア設計を概略的に示す図である。これは、例えば、図１７に示すように反転部１７１０及び検出部１７２０を利用することにより実現される。反転部１７１０及び検出部１７２０はアドレス部３２０の一部であるのが好ましいが、他の解決策が考えられることは明らかである。反転部１７１０は、６ビットアドレスバス６ａ上の元のアドレスの変更バージョン６ａ’を提供される。変更バージョン６ａ’は、上述のように、Ｙ＜Ｘの場合は常に６ビットアドレスのＸ値とＹ値とをスワップし、Ｘ＝Ｙの場合は常に６ビットアドレスバスにおける上述のＸ値を０に設定することにより得られる。更に、反転部１７１０は、変更アドレス６ａ’の出力と変更アドレス６ａ’の反転バージョンの出力とを切り替えるように構成される。比較部１７２０は、変更アドレス６ａ’におけるＸ値のＭＳＢを提供される。比較部１７２０は、中間アドレス６ａ’におけるＸ値のＭＳＢが２進の０である場合に変更アドレス６ａ’を出力し、中間アドレス６ａ’におけるＸ値のＭＳＢが２進の１である場合に中間アドレス６ａ’の反転バージョンを出力するように反転部１７１０内のスイッチを動作するように構成される。この動作は、比較部１７２０から切り替え部１７１０内の６ビットスイッチを介して延出する破線により示される。上述の反転を実現するにはハードウェア設計が好ましいが、本発明の他の実施形態が完全又は少なくとも部分的にソフトウェアに基づく設計により反転機能を実現してもよいことが追記されるべきである。これは、例えば、リアルタイムに実行される用途ではない場合等、時間が重要な用途ではない場合に特に当てはまる。
【００７２】
図１８の表は、前述で図７に示した表と同一である。しかしながら、上述のようにメモリ領域３１０において新しい値を提供されたメモリセルは本表中で新しい値を同様に受け取っており、メモリ領域３１０において除去又は消去されたメモリセルは本表中で同様に除去又は消去されている。消去された値及び除去されたセルは表中で二重取り消し線で示され、新しい値は消去された値の隣に適切に追記されている。
【００７３】
本発明の上述の実施形態及び図１８の表からわかるように、特に、ハードウェア乗算器を利用する場合、メモリマトリクスのサイズを５０％より多く削減できることは明らかである。
【００７４】
好適な実施形態により本発明を説明した。しかしながら、本発明は説明されない実施形態により限定されないことが追記されるべきである。その反対に、本発明は添付の請求の範囲に含まれる全ての実施形態を含むことが意図される。例えば、乗算メモリマトリクスは通常の二次マトリクスとして示されてもよいが、本発明はマトリクスの特定の物理的設計に限定されない。その反対に、マトリクスのセルは、行、円、又は２次元構造及び３次元構造を含む他の任意の適切な方法で構成されてもよい。また、メモリマトリクスは、シリコン構造、磁気又は光学メモリ構造を含む他の適切なメモリ構造、あるいは他の任意の適切なメモリ構造又は媒体により実現されてもよいことが強調されるべきである。
【図面の簡単な説明】
【００７５】
【図１】２つの１０進数を乗算する場合に人間が通常使用する筆算のアルゴリズムを再現又は模倣する２進乗算アルゴリズムを概略的に示す図である。
【図２】乗算メモリマトリクスにより実現されるルックアップテーブルの一例を概略的に示す図である。
【図３】好適な乗算メモリマトリクス３００を概略的に示す図である。
【図４】図３の好適な乗算メモリマトリクス３００に対するアドレス、被乗数、乗数及び積の間の関連を示す表である。
【図５】図２の一般的な乗算メモリマトリクスをアドレス指定する語の前半部分及び後半部分のスワップによる結果を示す図である。
【図６】図３の特定の乗算メモリマトリクス３００をアドレス指定する語の前半部分Ｘ及び後半部分Ｙのスワップによる結果を示す図である。
【図７】図６のメモリ領域３１０において除去されたセルに対応するメモリセルが除去されるように図４の表を修正した表である。
【図８】メモリ領域３１０を指定する６ビットのアドレス語においてＹ＜Ｘの場合にＸ値及びＹ値のスワップを実現する好適なハードウェア設計を示す図である。
【図９】図５の一般的な乗算メモリマトリクスにおける０番目の列の消去を示す図である。
【図１０】図６の特定の乗算メモリマトリクス３００のメモリ領域３１０における０番目の列の消去を示す図である。
【図１１】積ｘ・０＝ｙ・０＝０を生成する好適なハードウェア設計を示す図である。
【図１２】アドレス値Ｘ＝Ｙが事前に消去された０番目の列に移動されたメモリセルの内容を有する図９の一般的な乗算メモリマトリクスを示す図である。
【図１３】アドレス値Ｘ＝Ｙが先に消去された０番目の列に移動されたメモリセルの内容を有する図１０に示すメモリ領域３１０を示す図である。
【図１４】Ｘ＝Ｙである特別な場合にメモリ領域３１０における対角線の移動を実現する好適なハードウェア設計を示す図である。
【図１５】図１２に示す一般的な乗算メモリマトリクスの一部の対角線鏡映を示す図である。
【図１６】図１３に示す特定の乗算メモリマトリクスにおけるメモリ領域３１０の一部の対角線鏡映を示す図である。
【図１７】乗算マトリクス３００の一部の対角線鏡映を実現する好適なハードウェア設計を示す図である。
【図１８】図１６のメモリ領域３１０において除去されたセルに対応するメモリセルが除去されるように図４の表を修正した表である。
【符号の説明】
【００７６】
３００  乗算メモリマトリクス
３１０  メモリ領域
３２０  アドレス部
３３０  出力部
８１０  スワップ部
８２０  比較部
１１１０  切り替え部
１１２０  比較部
１４１０  切り替え部
１４２０  比較部
１７１０  反転部
１７２０  検出部
６ａ  ６ビットアドレスバス
６ａ’  ６ビット変更アドレスバス
６ａ”  ６ビット変更アドレスバス
６ａ”’  ６ビット変更アドレスバス
６ｐ  ６ビットデータバス
【図１】
2009516248.tif 000005
【図２】
2009516248.tif 000006
【図３】
2009516248.tif 000007
【図４】
2009516248.tif 000008
【図５】
2009516248.tif 000009
【図６】
2009516248.tif 000010
【図７】
2009516248.tif 000011
【図８】
2009516248.tif 000012
【図９】
2009516248.tif 000013
【図１０】
2009516248.tif 000014
【図１１】
2009516248.tif 000015
【図１２】
2009516248.tif 000016
【図１３】
2009516248.tif 000017
【図１４】
2009516248.tif 000018
【図１５】
2009516248.tif 000019
【図１６】
2009516248.tif 000020
【図１７】
2009516248.tif 000021
【図１８】
2009516248.tif 000022
【国際調査報告】
2009516248.tif 000023
2009516248.tif 000024