(57)【要約】      （修正有）【課題】大量のデータを処理する場合の演算時間を減少させる。【解決手段】デジタルデータ処理装置であり、より具体的には、２ｎコードのセットに属するデータの最大値あるいは最小値を読み出す装置であって、前記セットにおいては、順序関係が確立されるとともに、それぞれ、０から２ｎ−１から構成されるランクＲを有している。かかる装置は、X=1から２ｎ−１を有する２ｎの２進要素Ｔ[x]から構成される２進数の変換を生成するため処理される各デジタルデータ用の変換回路であって、Ｔ[2n−1]T[2n−2] T[x]...T[2] T[1]であり、ここで、ＸがＲより絶対に大きい場合にＴ(x)＝０、ＸがＲより小さいか、等しい場合にはＴ(x)＝１であるもの、を備えている。かかる変換の結果は、そのデジタル処理を実行する回路が受け取る。【選択図】図４
2004206721.tif 000002
【特許請求の範囲】
【請求項１】
２ｎコードのセットに属するデジタルデータを処理するための装置であって、前記セットにおいては、順序関係(relation of order)が確立されるとともに、それぞれ、０から２ｎ−１から構成されるランクＲを有しており、前記装置は、
X=1から２ｎ−１を有する２ｎ−１の２進要素Ｔ[x]から構成される２進数の変換を生成するため処理される各デジタルデータ用の変換回路であって、Ｔ[2n−1]T[2n−2] T[x]...T[2] T[1]であり、ＸがＲより絶対に大きい(strictly higher)場合にＴ(x)＝０、ＸがＲより小さいか、等しい場合にはＴ(x)＝１であるもの、  前記変換の結果を受け取るとともに、当該結果のデジタル処理を実行するための回路、を備えたこと、
を特徴とするもの。
【請求項２】
２ｎコードのセットに属するデジタルデータを処理するための装置であって、前記セットにおいては、順序関係が確立されるとともに、それぞれ、０から２ｎ−１から構成されるランクＲを有しており、前記装置は、
X=0から２ｎ−１を有する２ｎの２進要素Ｔ[x]から構成される２進数の変換を生成するため処理される各デジタルデータ用の変換回路であって、Ｔ[2n−1]T[2n−2] T[x]...T[1] T[0]であり、ＸがＲより絶対に大きい場合にＴ(x)＝０、ＸがＲより小さいか、等しい場合にはＴ(x)＝１であるもの、
前記変換の結果を受け取るとともに、当該結果のデジタル処理を実行するための回路、を備えたこと、
を特徴とするもの。
【請求項３】
請求項１又は請求項２にかかる装置において、前記デジタル処理は、前記変換されたデータの同じインデックスのビット上でビットシリアル法により実行されるブーリアンＯＲ(Boolean OR)であり、デジタル値セットの最大値を読み出すため、その後、前記変換の逆変換が行われること、
を特徴とするもの。
【請求項４】
請求項３にかかる装置において、前記最大値の前記読み出しは、他の値との比較後であること、
を特徴とするもの。
【請求項５】
請求項１又は請求項２にかかる装置において、前記デジタル処理は、前記変換されたデータの同じインデックスのビット上でビットシリアル法により実行されるブーリアンＡＮＤ(Boolean ＡＮＤ)であり、デジタル値セットの最小値を読み出すため、その後、前記変換の逆変換が行われること、
を特徴とするもの。
【請求項６】
請求項５の装置において、前記最小値の前記読み出しは、他の値との比較後であること、
を特徴とするもの。
【請求項７】
２ｎコードのセットに属するデジタルデータを処理するための装置であって、前記セットにおいては、順序関係が確立されるとともに、それぞれ、０から２ｎ−１から構成されるランクＲを有しており、前記装置は、
X=1から２ｎ−１を有する２ｎ−1の２進要素Ｔ[x]から構成される２進数の変換を生成するため処理される各デジタルデータ用の変換回路であって、Ｔ[2n−1]T[2n−2] T[x]...T[2] T[1]であり、ＸがＲより絶対に大きい場合にＴ(x)＝１、ＸがＲより小さいか、等しい場合にはＴ(x)＝０であるもの、  
前記変換の結果を受け取るとともに、当該結果のデジタル処理を実行するための回路、を備えたこと、
を特徴とするもの。
【請求項８】
２ｎコードのセットに属するデジタルデータを処理するための装置であって、前記セットにおいては、順序関係が確立されるとともに、それぞれ、０から２ｎ−１から構成されるランクＲを有しており、前記装置は、
X=０から２ｎ−１を有する２ｎの２進要素Ｔ[x]から構成される２進数の変換を生成するため処理される各デジタルデータ用の変換回路であって、Ｔ[2n−1]T[2n−2] T[x]...T[１] T[０]であり、ＸがＲより絶対に大きい場合にＴ(x)＝１、ＸがＲより小さいか、等しい場合にはＴ(x)＝０であるもの、  
前記変換の結果を受け取るとともに、当該結果のデジタル処理を実行するための回路、を備えたこと、
を特徴とするもの。
【請求項９】
請求項７又は請求項８にかかる装置において、前記デジタル処理は、前記変換されたデータの同じインデックスのビット上でビットシリアル法により実行されるブーリアンＡＮＤであり、デジタル値セットの最大値を読み出すため、その後、前記変換の逆変換が行われること、
を特徴とするもの。
【請求項１０】
請求項９の装置において、前記最大値の前記読み出しは、他の値との比較後であること、
を特徴とするもの。
【請求項１１】
請求項７又は請求項８にかかる装置において、前記デジタル処理は、前記変換されたデータの同じインデックスのビット上でビットシリアル法により実行されるブーリアンＯＲであり、デジタル値セットの最小値を読み出すため、その後、前記変換の逆変換が行われること、
を特徴とするもの。
【請求項１２】
請求項１１の装置において、前記最小値の前記読み出しは、他の値との比較後であること、
を特徴とするもの。
【請求項１３】
前記いずれかの請求項において、処理する前記デジタルデータの元のコードは、署名入りタイプ(signed type)、署名なし(not signed)、グレイ(Gray)、ジョンソン(Johnson)で構成されるか、あるいは、仮数(mantissa)および指数(exponent)を含むこと、
を特徴とするもの。
【請求項１４】
前記いずれかの請求項において、各データの様々な部分を順次処理するため、前記変換は、各データの２進要素のサブグループのみに適用されること、
を特徴とするもの。
【請求項１５】
２ｎコードのセットに属するデジタルデータのセットから最大値を読み出すための装置であって、前記セットにおいては、順序関係が確立されるとともに、それぞれ、0から２ｎ−１から構成されるランクＲを有しており、前記回路は、
前記デジタルデータのそれぞれを、X=1から２ｎ−１を有する２ｎ−1の２進要素Ｔ[x]から構成される２進数のコード形式によって表現するための回路であって、Ｔ[2n−1]T[2n−2] T[x]...T[2] T[1]であり、ＸがＲより絶対に大きい場合にＴ(x)＝0、ＸがＲより小さいか、等しい場合にはＴ(x)＝1であるもの、  前記デジタル値セットの最大値を読み出すため、前記デジタルデータの同じインデックスのビット上でビットシリアル法により論理ＯＲを実行する論理回路、を備えたこと、
を特徴とするもの。
【請求項１６】
２ｎコードのセットに属するデジタルデータのセットから最大値を読み出すための装置であって、前記セットにおいては、順序関係が確立されるとともに、それぞれ、０から２ｎ−１から構成されるランクＲを有しており、前記回路は、
前記デジタルデータのそれぞれを、X=0から２ｎ−１を有する２ｎの２進要素Ｔ[x]から構成される２進数のコード形式によって表現するための回路であって、Ｔ[2n−1]T[2n−2] T[x]...T[1] T[0]であり、ＸがＲより絶対に大きい場合にＴ(x)＝0、ＸがＲより小さいか、等しい場合にはＴ(x)＝1であるもの、  
前記デジタル値セットの最大値を読み出すため、前記デジタルデータの同じインデックスのビット上でビットシリアル法により論理ＯＲを実行する論理回路、を備えたこと、
を特徴とするもの。
【請求項１７】
２ｎコードのセットに属するデジタルデータのセットから最小値を読み出すための装置であって、前記セットにおいては、順序関係が確立されるとともに、それぞれ、０から２ｎ−１から構成されるランクＲを有しており、前記回路は、
前記デジタルデータのそれぞれを、X=1から２ｎ−１を有する２ｎ−1の２進要素Ｔ[x]から構成される２進数のコード形式によって表現するための回路であって、Ｔ[2n−1]T[2n−2] T[x]...T[2] T[1]であり、ＸがＲより絶対に大きい場合にＴ(x)＝0、ＸがＲより小さいか、等しい場合にはＴ(x)＝1であるもの、  
前記デジタル値セットの最小値を読み出すため、前記デジタルデータの同じインデックスのビット上でビットシリアル法により論理ＡＮＤを実行する論理回路、を備えたこと、
を特徴とするもの。
【請求項１８】
２ｎコードのセットに属するデジタルデータのセットから最小値を読み出すための装置であって、前記セットにおいては、順序関係が確立されるとともに、それぞれ、０から２ｎ−１から構成されるランクＲを有しており、前記回路は、
前記デジタルデータのそれぞれを、X=０から２ｎ−１を有する２ｎの２進要素Ｔ[x]から構成される２進数のコード形式によって表現するための回路であって、Ｔ[2n−1]T[2n−2] T[x]...T[1] T[0]であり、ＸがＲより絶対に大きい場合にＴ(x)＝0、ＸがＲより小さいか、等しい場合にはＴ(x)＝1であるもの、  
前記デジタル値セットの最小値を読み出すため、前記デジタルデータの同じインデックスのビット上でビットシリアル法により論理ＡＮＤを実行する論理回路、を備えたこと、
を特徴とするもの。
【請求項１９】
２ｎコードのセットに属するデジタルデータのセットから最大値を読み出すための装置であって、前記セットにおいては、順序関係が確立されるとともに、それぞれ、０から２ｎ−１から構成されるランクＲを有しており、前記回路は、
前記デジタルデータのそれぞれを、X=1から２ｎ−１を有する２ｎ−１の２進要素Ｔ[x]から構成される２進数のコード形式によって表現するための回路であって、Ｔ[2n−1]T[2n−2] T[x]...T[2] T[1]であり、
ここで、ＸがＲより絶対に大きい場合にＴ(x)＝1、ＸがＲより小さいか、等しい場合にはＴ(x)＝0であり、  
前記デジタル値セットの最大値を読み出すため、前記デジタルデータの同じインデックスのビット上でビットシリアル法により論理ＡＮＤを実行する論理回路、を備えたこと、
を特徴とするもの。
【請求項２０】
２ｎコードのセットに属するデジタルデータのセットから最大値を読み出すための装置であって、前記セットにおいては、順序関係が確立されるとともに、それぞれ、０から２ｎ−１から構成されるランクＲを有しており、前記回路は、
前記デジタルデータのそれぞれを、X=0から２ｎ−１を有する２ｎの２進要素Ｔ[x]から構成される２進数のコード形式によって表現するための回路であって、Ｔ[2n−1]T[2n−2] T[x]...T[1] T[0]であり、ＸがＲより絶対に大きい場合にＴ(x)＝1、ＸがＲより小さいか、等しい場合にはＴ(x)＝0であるもの、  
前記デジタル値セットの最大値を読み出すため、前記デジタルデータの同じインデックスのビット上でビットシリアル法により論理ＡＮＤを実行する論理回路、を備えたこと、
を特徴とするもの。
【請求項２１】
２ｎコードのセットに属するデジタルデータのセットから最小値を読み出すための装置であって、前記セットにおいては、順序関係が確立されるとともに、それぞれ、０から２ｎ−１から構成されるランクＲを有しており、前記回路は、
前記デジタルデータのそれぞれを、X=１から２ｎ−１を有する２ｎ−１の２進要素Ｔ[x]から構成される２進数のコード形式によって表現するための回路であって、Ｔ[2n−1]T[2n−2] T[x]...T[2] T[1]であり、ＸがＲより絶対に大きい場合にＴ(x)＝1、ＸがＲより小さいか、等しい場合にはＴ(x)＝0であるもの、
前記デジタル値セットの最小値を読み出すため、前記デジタルデータの同じインデックスのビット上でビットシリアル法により論理ＯＲを実行する論理回路、を備えたこと、
を特徴とするもの。
【請求項２２】
２ｎコードのセットに属するデジタルデータのセットから最小値を読み出すための装置であって、前記セットにおいては、順序関係が確立されるとともに、それぞれ、０から２ｎ−１から構成されるランクＲを有しており、前記回路は、
前記デジタルデータのそれぞれを、X=0から２ｎ−１を有する２ｎの２進要素Ｔ[x]から構成される２進数のコード形式によって表現するための回路であって、Ｔ[2n−1]T[2n−2] T[x]...T[1] T[0]であり、ＸがＲより絶対に大きい場合にＴ(x)＝1、ＸがＲより小さいか、等しい場合にはＴ(x)＝0であるもの、  
前記デジタル値セットの最小値を読み出すため、前記デジタルデータの同じインデックスのビット上でビットシリアル法により論理ＯＲを実行する論理回路、を備えたこと、
を特徴とするもの。
【請求項２３】
請求項１５から請求項２２のいずれか一つにかかる装置において、各データの様々な部分を順次処理するため、前記変換は、各データの２進要素のサブグループのみに適用されること、
を特徴とするもの。
【発明の詳細な説明】
【発明の属する分野】
【０００１】
本発明は、情報のデジタル処理に関し、より具体的には、大量の値およびデータの全体処理用装置に関する。
【関連技術の説明】
【０００２】
情報技術の発展につれ、システムによって処理されるデータの数は確実に増加している。データ処理は、通常、ＡＬＵ型（数値演算ユニット）電子回路内、あるいは、フルカスタム回路内で行われる。
【０００３】
大量のデータを処理しなければならない場合、例えば、最大値を読み出すのと同様に、かかる処理は、特に重く、多くのステップが必要とされる。
【０００４】
図１は、従来の、Ｎｄ値のセット(set of Nd vales)、例えば、８つの値ＤＡＴＡ１からＤＡＴＡ８（各々、信号Enable１からEnable８を伴う）の最大値の読み出し方法、を示す。これを行うため、８つの基本的な機能ブロック１１から１８までが、２つの値を２つづつ比較することを可能とする。次に、各機能ブロックは、必要に応じ、選択信号Enable_Maxとともに最大値を提供する。かかる方法において、＜＜比較して送る(compare and forward)＞＞により構成されるタイプは、処理を直列、すなわち、順々に行わなければならないので、処理時間が、多大な影響を受ける。かかる方法を用いた場合、通常、Ｎｄ−１の処理後、ここで、Ｎｄは処理されるデータの数を表す、に結果が得られる。
【０００５】
既知の他の方法によると、機能ブロックを、図２に示すようなツリー構造に再構成することにより、対象となる処理時間が短くなる。８つの値のセットについては、ブロック１１，１４、１６ならびに１８が同時にその処理を同時に開始することが出来るので、処理を行うために３つ以上のステップを要しないよう注意すべきである。
【０００６】
前述の他の既知の方法は、処理時間を短くするが、後者は、まだ長いままである（Ｎｄ対数を有する変数）。データの全体的な処理時間を短くするため、他のアプリケーションも数多く存在する。
【０００７】
かかる問題は、一般的なものであり、最大値の読み出しに限定されるものではない。これには、例えば、最小値の読み出し、目標値との比較等の、他のタイプデータの全体処理が含まれる。
【０００８】
複雑な分類処理を実行しなければならない大型コンピュータと同様に、時間の制約が厳しくなる場合、あるいは、同時処理が求められる場合、既知の方法により可能となるよりも、もっと早くデータ処理を実行する必要がある。
【０００９】
これらの理由から、プログラム可能な論理回路によってもたらされる可能性では、通常、満足できない。特定の電気回路を実現することにより、大量のデータの処理時間を短縮する可能性が幾分か残ってはいる。しかし、後者は、実質的に図１及び図２に示された方法を実行するだけなので、既知の合成ツールを用いても、性能の低い回路を作る可能性しか残されていない。
【００１０】
しかしながら、大量のデータを処理する場合、演算時間を減少させるとともに、データのデジタル処理を全体的に維持すること、が望ましい。
【発明の開示】
【００１１】
本発明は、特殊な電子装置用の新しいアーキテクチャであって、大量のデータ処理を可能し、例えば、最大値の読み出し動作を実行するもの、を提供する。
【００１２】
本発明の装置は、順序関係が確立されるとともに、各データが０から2n−1の間の数から構成されるランクＲを有する、順序付けられたデータセットに属するデジタルデータのセットを処理する。かかる装置は、以下のものを備えている：X=1から２ｎ−１を有する２ｎ−１の２進要素Ｔ[x]から構成される２進数の変換を処理するため処理される各デジタルデータ用の変換回路であって、Ｔ[2n−1]T[2n−2] T[x]...T[2] T[1]であり、ＸがＲより絶対に大きい場合にＴ(x)＝０、ＸがＲより小さいか、等しい場合にはＴ(x)＝１であるもの。これに代え、X=0から２ｎ−１を有する２ｎの２進要素Ｔ[x]から構成される２進数の変換であって、T[2n−2] T[x]...T[1] T[0]であるものが実行される。
【００１３】
実際のデジタル処理の場合、処理されるデータセットを与え、変換を行うのは、前記変換されたデータの同じインデックスのビット上でビットシリアル法により実行されるブーリアンＯＲ(Boolean OR)であり、その後、前記変換の逆変換が行われ、デジタル値セットの最大値を直接かつ高速で得ることができる。
【００１４】
反対に、デジタル処理の場合、処理されるデータセットを与え、変換を行うのは、前記変換されたデータの同じインデックスのビット上でビットシリアル法により実行されるブーリアンＡＮＤ(Boolean ＡＮＤ)であり、その後、前記変換の逆変換が行われ、デジタル値セットの最小値を直接かつ高速で得ることができる。
【００１５】
なお、Ｘが、前記順序セットにおけるランクＲよりも絶対に大きい場合にＴ（ｘ）＝１、ｘが、Ｒ以下である場合にＴ（ｘ）＝０であること、に基づく取り決め(convention)を採用した場合、同じインデックス上でビット・シリアル法により実行され、その後に前記変換の逆変換が行われるブーリアンＡＮＤによって最大値が読み出される。その代わりに、前記変換が行われたデータセットにおいて、同じインデックス上でビット・シリアル法により実行され、その後に前記変換の逆変換が行われるブーリアンＯＲを用いると、非常に短時間で最小値を読み出すことができる。
【００１６】
したがって、大量の処理を並行的に実行することができるだけでなく、かかる多数の最大値あるいは最小値を抽出するために、３つ以下の基本的な動作しか要求されることがない。また、仮数および指数、グレイ、ジョンソン等を有する、署名入りあるいは署名なし、の全ての種類のフォーマットを処理することができる。
【００１７】
本発明は、最大値および最小値を高速で読み出す回路を実現することができる。
【００１８】
本発明の他の特徴、目的ならびに効果は、限定を目的としたものでなく例示目的のみで添付された図面を参照しつつ、以下の説明を読むことによって明らかになる。
【発明の詳細な説明】
【００１９】
データ処理の全体的な時間を短縮するため、取り扱われる各ＤＡＴＡｘ値の中間コーデイング(intermediate coding)の実行を可能にする＜＜Ｔへの変換＞＞と呼ばれる変換機能を用いる。
【００２０】
かかる変換機能は、図３から図１２に示した全ての例であって、以下で述べるその第１形態において用いられる。
【００２１】
値Ｂは、ｎビットにコード化され（すなわち、nビットのコードを有する）、そこで順序関係の設定が行われるとともに、それに対して各データが、０と2n−１間の値から構成されるランクを有する2nの要素を備えた、順序付けられたセットに属することになっている。処理されるデータとＴへの変換との間のランクの関係は、以下の方法により定義される：
ベクトルB[n−1] Ｂ[n−2]...B[2]B[1]B[0]は、2n−１ビットから構成される以下の２進数に変換される：
X=1から２ｎ−１を有するＴ[2n−1]T[2n−2] T[x]...T[2] T[1]であり、Ｘが、前記順序ユニットにおけるランクであるＲよりも絶対に大きい場合にＴ（ｘ）＝０、ｘが、Ｒ以下である場合にＴ（ｘ）＝１である。すなわち、１０進値の例では、以下のように考えられる：
R= B[n−1]X2(n−1)+B[n−2]X2(n−2)   +...+B[2]X22 +B[1]X21+B[0]X20。
上記のようにランクＲを定義することで、現在のＴへの変換に以下のような特徴を与えることに注意すべきである：第１に、２進コードとそのＴへの変換の間で前単射関係(bijective relationship)が存在し；第２に、Ｔへの変換のいずれかの２進ビットＴ（ｘ）は、ウエイトの低いビットが値１を有する場合にのみ値１を有する。
【００２２】
このように、３ビットのコードを有するデータのため、以下の対応関係が成立する：
最初の２進コード                Ｔへの変換              ランク
０００                        ０００００００          ０
００１                        ００００００１          １
０１０                        ０００００１１          ２
０１１                        ００００１１１          ３
１００                        ０００１１１１          ４
１０１                        ００１１１１１          5
１１０                        ０１１１１１１          ６
１１１                        １１１１１１１          ７
図３は、本発明に基づく、デジタルデータの全体的な処理用の回路を示しており、かかる回路は、図示のため、ＤＡＴＡ１−ＤＡＴＡ８までの８つの値のどの種類の最大値の読み出しをも可能にする。図３の回路は、多くの例における一例を示しただけであり、当業者が、本発明を、種類、値を問わず他のいずれの処理動作に容易に適用可能であること、すなわち、何らの制限なく、最小値の読み出し、又は、大量の数値を処理する他の動作を実行可能であること、に注目すべきである。
【００２３】
また、数値の数は、８に限定されることはなく、いずれの数であってもよいことにも注意すべきである。さらに、データは、署名付きか否か(signed  or not)に拘わらず、どのようなフォーマットで表現してもよいが、それらは、そこで順序関係を定義するセットを構成する。
【００２４】
また、第２タイプのＴへの変換を用いてもよいことが予想(envisage)される。前述の第２タイプのＴへの変換は、前に定義されたランクの関係に基づく：その１０進の値<<０>>は、１に設定される最小有効ビット（ＬＳＢ）を有する<<０>>の列に変換される。図示のため、以下に、各々最初に４ビットコードを有する値と、前記第２タイプによる前記値のＴへの変換の後に得られたコード間の対応関係を示す。
【００２５】
最初の２進コード      Ｔへの変換                              ランク
００００              ０００００００００００００００１        ０
０００１              ００００００００００００００１１        １
００１０              ０００００００００００００１１１        ２
００１１              ００００００００００００１１１１        ３
０１００              ０００００００００００１１１１１        ４
０１０１              ００００００００００１１１１１１        ５
０１１０              ０００００００００１１１１１１１        ６
０１１１              ００００００００１１１１１１１１        ７
１０００              ０００００００１１１１１１１１１        ８
１００１              ００００００１１１１１１１１１１        ９
１０１０              ０００００１１１１１１１１１１１        １０
１０１１              ００００１１１１１１１１１１１１        １１
１１００              ０００１１１１１１１１１１１１１        １２
１１０１              ００１１１１１１１１１１１１１１        １３
１１１０              ０１１１１１１１１１１１１１１１        １４
１１１１              １１１１１１１１１１１１１１１１        １５
なお、Ｘが、前記順序セットにおけるランクＲよりも絶対に大きい場合にＴ（ｘ）＝１、ｘが、Ｒ以下である場合にＴ（ｘ）＝０であること、に基づく取り決め(convention)を採用した場合、同じインデックス上でビット・シリアル法により実行され、その後に前記変換の逆変換が行われるブーリアンＡＮＤによって最大値が読み出される。その代わりに、同じインデックス上でビット・シリアル法により実行され、その後に前記変換の逆変換が行われるブーリアンＯＲを用いると、非常に短時間で最小値を読み出すことができる。
以下で明らかなように、Ｔへの変換は、多くのデータの組み合わせ、ならびに、データ取り扱い動作に適している。
【００２６】
Ｔへの変換の最初の定義（すなわち、どの１０進値の’０’が変換<<000000...00>>に対応するか）を考える場合、変換された値のランクは、当該変換済みの値に含まれる様々な２進要素を加えることで、以下のように直接得られることに注意すべきである。
【００２７】
R=T[2n−1]+T[2n−2]+T[2n−3]+...+T[2]+T[1]
また、かかるＴへの変換は、全体的なデータ処理を非常に高速で行うことを可能にする回路を製造するため、非常にうまく用いることができる。かかる回路は、手動、あるいは、コンパイルおよび論理合成ツールにより設計された、新しいクラスの電子回路を構成する。
図３を再度参照すると、８つの各値、ＤＡＴＡ１からＤＡＴＡ８は、その出力において、前記値に対応するＴへの変換を提供する変換回路２０１から２０８にそれぞれ送られること、に注意すべきである。
【００２８】
前記８つの値は、次に、ブロック２１０から２０８により供給された様々な値間で、同じインデックス上でビットシリアル法により論理ＯＲを実行する変換回路２０９に送られる。
【００２９】
図４は、３ビットコードを有する３つの値と関連する、かかる変換回路を示している。しかし、当業者であれば、本発明を、いずれのビット数を有するどのような値の数の処理に適用可能であることは明かである。次に、回路２０９は、Ｔへの変換の逆を行う変換回路２１０により変換される値を出力する。
【００３０】
図３の装置を用いると、全てのＴへの変換を同時に行うことができ、その結果、８つの値の処理をたった３つのステップで完了することができること、に注目すべきである。図２を参照して説明した従来技術とは逆に、ステップの数は、もはや処理する値の数に左右されることがなく、例えば、１２８個の値を処理する場合でも、１２８個を超えるＴへの変換回路が必要とされることはない、ことにも注目すべきである。
【００３１】
このようにして、データセットの最大値の読み出しが、非常に高速で行われる。本発明を用いると、処理データの数が大きくなるほど、処理時間の節約の度合が大きくなる。
【００３２】
変換回路２０１から２０８、２０９および２１０は、同じ半導体回路内に組み込まれていることが好ましい。高速処理には、表面積の増大が必要とされ、かかる増大は処理される値のビット数と正比例する。したがって、８ビットの値を処理するためには、２８又は２８−１ワード、すなわち２５６又は２５５ビットを生成する、Ｔへの変換回路が必要となる。
【００３３】
以前定義されたＴへの変換は、より大きいビットを有するコードを生成しがちである。この結果、十分な２進数の値を同時に処理可能な数値演算ユニット（ＡＬＵｓ）が必要となる。処理されるデータのビット数と、Ｔへの変換回路により生成された値のビット数との間の対応関係を以下に示す：
ビット数：            Ｔへの変換回路により生成された値のビット数：
４                    １５（又は１６）
５                    ３１（又は３２）
６                    ６３（又は６４）
７                    １２７（又は１２８）
８                    ２５５（又は２５６）
９                    ５１１（又は５１２）
１０                  １０２３（又は１０２４）
ｎ                    ２ｎ−１（又は２ｎ）
実現された回路のサイズとその速度性能との間で、妥協が成立することは明かである。好ましい実施形態において、処理されるデータは、中間的なＴへの変換回路により、例えば、２Ｎｂ−１ビットの中間値の生成を可能とするため、Ｎｂビットのグループに分割される。最も高いウエイトのビットを含むグループが処理されると、次に、未処理Ｎｂビットであって最も高いウエイトのもの、の処理が行われる。このように、従来技術よりさらに高速に、しかも、少ない動作によって、最大値を読み出すことができる。
【００３４】
実際には、例えば、４ビットを有する値だけを処理すると判断するようにしてもよい。このことにより、簡単に取り扱うことができる１６ビットを有するＴへの変換を行うことができる。４ビットより大きい値の処理が所望される場合、処理される各値を４ビットのワードに分割するとともに、各ワードに対しＴへの変換を適用する。その際、データ処理方法において順次処理が再度行われること、に注意すべきである。前記順次処理は、ビット数の減少を可能にするとともに、半導体の表面積を減少させるが、処理時間が長くなってしまう、しかし、かかる処理時間は、既知の方法によって得られるものより短い。
【００３５】
図４は、同じインデックス上でビット・シリアル法により、３ビットコードを有する３つのデータの論理ＯＲ結合(OR combination)の実行を可能にする変換回路２０９を示している。回路２０９は、３ビットのＯＲ[3] OR{2] OR[1] にコード化されたベクトルを出力する。かかる３つのデータは、それぞれ、３ビット：DATA3[3]DATA3[2]DATA3[1](DATA2[3]DATA2[2]DATA2[1]DATA1[3]DATA1[2]DATA1[1])にコード化される。かかる操作は、それぞれが３つの入力を有する３つの論理ＯＲ回路２５１、２５２ならびに２５３によって実行される。論理ＯＲ回路２５１（２５２；２５３のそれぞれ）は、DATA1[1]（DATA1[2]；DATA1[3]のそれぞれ）に接続される第１入力、DATA2[1]（DATA2[2]；DATA2[3]のそれぞれ）に接続される第２入力、DATA3[1]（DATA3[2]；DATA3[3]のそれぞれ）に接続される第３入力、ならびに、ＯＲ[1](ＯＲ[2]ＯＲ[3]のそれぞれ）に接続される出力、を有している。いずれのビット数を有するいずれの数値の処理が所望される場合に、当業者が、必要な適合を行うことが可能であるのは、明かである。
【００３６】
図５は、データセットの最小値を読み出すための装置の実施形態を示している。８つの値ＤＡＴＡ１からＤＡＴＡ８は、それぞれ、入力値に対応するＴへの変換値を出力する変換回路３０１から３０８までの入力に各々送られる。かかる８つの値は、次に、同じインデックス上でビット・シリアル法によりブロック３０１から３０８により供給された様々な値の論理ＡＮＤの結合(AND combination)を実行する、変換回路３０９に送られる。次に、かかる変換回路３０９は、Ｔへの変換の逆を行う変換回路３１０によって変換される値を出力する。
【００３７】
いずれかのデータセットの最小値の読み出しは、非常に短い時間で実行されること、にも注目すべきである。したがって、たとえ特に重要なコンテキストであっても、リアルタイムの処理などの、全ての種類のアプリケーションを想起することが可能である。
【００３８】
図６は、３ビットの３つの値への適用に限定される変換回路３０９を示している。変換回路３０９は、同じインデックス上でビット・シリアル法により、それぞれが３ビットコードを有する３つのデータの論理ＡＮＤの結合を実行するとともに、３ビットET[3] ET[2] ET[1]にコード化されたベクトルを出力する。３つのデータのそれぞれは、３ビット：DATA3[3]DATA3[2]DATA3[1]、DATA2[3]DATA2[2]DATA2[1]およびDATA1[3]DATA1[2]DATA1[1]にそれぞれコード化される。かかる操作は、それぞれが３つの入力を有する３つの論理ＡＮＤ回路３５１、３５２ならびに３５３によって実行される。論理ＡＮＤ回路３５１（３５２、３５３のそれぞれ）は、DATA1[1]（DATA1[2]；DATA1[3]のそれぞれ）に接続される第１入力、DATA2[1]（DATA2[2]；DATA2[3]のそれぞれ）に接続される第２入力、DATA3[1]（DATA3[2]；DATA3[3]のそれぞれ）に接続される第３入力、ならびに、ET[1](ET[2]ET[3]のそれぞれ）に接続される出力、を有している。
【００３９】
変換回路２１０あるいは３１０の構成は、以下の２つのステップによりＴへの変換の逆変換を実現可能であれば、どのようなものであってもよい。
【００４０】
第１のステップは、トランスコードされる２進要素が２つづつ処理される専用の条件付トランスコーデイング(exclusive conditional transcoding)方式を採用する。かかる第１ステップの出力は、各ベクトルがｎの２進要素を備えたｋ個のベクトルで構成されたmatrix cond_transcodeである。
【００４１】
第２のステップは、同じインデックス上でビット・シリアル法により実行される論理ＯＲ結合によって、matrix cond_transcodeの全てのベクトルを単一のベクトルに減少させること、により構成される。前記単一ベクトルは、Ｔへの逆変換後に得られる値である。
【００４２】
図７は、３ビットコード専用の条件付トランスコーダーを機能ブロック形式で表している。隣接する２つの２進要素、すなわち、next_bit_indexおよびcurrent_bit_index、の比較は、ＡＮＤゲート４０２およびインバーター４０１によって実行される。next_bit_indexの値は、その出力がＡＮＤゲート４０２の第１入力に接続され、その第２出力がcurrent_bit_indexを受け取るＡＮＤゲート４０２の出力に接続される、インバーター４０１に送られる。また、ＡＮＤゲート４０２の出力は、３ビットにコード化されたベクトル（すなわち、conv_bin_index[0]からconv_bin_index[2]までのそれぞれ）を受け取る第２入力を別々に有する３つのＡＮＤゲート４０３、４０４、４０５のセットの第１入力に送られる。専用の条件付トランスコーダーは、自身の出力において、３つの２進要素、すなわち、code_transcode[0]からcode_transcode[2]をそれぞれ供給する。
【００４３】
図８は、E[1]からE[7]まで各々７ビットにコード化された値のＴへの逆変換を実現するため、専用の条件付トランスコーダー５０１から５０７を配列する方法を示している。３ビットにコード化された２進値によって表された７つの定数、ならびに、その左側にある、最大のインデックス、すなわち、const(001b)const(010b)const(011b)const(100b)const(101b)const(110b)const(111b)が、トランスコーダー５０１から５０７の入力ベクトルconv_bin_indexにそれぞれ与えられる。トランスコーダー５０１から５０６の入力next_bit_indexは、それぞれ、要素E[2]からE[7]を受け取る。E[1]については、トランスコーダー５０１の入力current_bit_indexに送られる。論理’０’と等しく、const(0b)と名付けられた１ビットにコード化された２進定数は、トランスコーダー５０７の入力next_bit_indexに送られる。トランスコーダー５０１から５０６の各入力next_bit_indexは、各々、トランスコーダー５０２から５０７の入力current_bit_indexに接続される。次に、トランスコーダー５０１から５０８の出力は、同じインデックス上でビットシリアル法によって論理ＯＲ結合を実現するとともに、３ビットコードの形式でＴへの変換の逆の値を出力する、ブール演算子ＯＲ(Boolean operator OR)５１０に与えられる。
【００４４】
一般に、Ｔへの変換用の変換回路３１０から３０８、ならびに、逆変換を行う回路３１０を実現するあらゆる方法を考えるようにしてもよい。
【００４５】
処理される値を、一旦、Ｔへの変換に基づいて変換すると、全て種類の動作を実行することが非常に容易となる。
【００４６】
図９から図１１は、Ｔへの変換に関して実行される動作例を示している。Ｔへ変換された値の処理は、非常に短い時間で実行可能であることに、再度注目すべきである。
【００４７】
図９は、ある値のＴへの変換と、例えば、前もって算出された最大値等の基準値との間で等価性の比較を可能にする、動作を示している。明らかなように、７ビットにコード化されたＴへの変換の各２進要素（DATAX[1]からDATAX[7]までのそれぞれ）は、その第２入力が７ビットにコード化された基準値（Max_value[1]からMax_value[7])までそれぞれ）を受ける専用ＯＲゲート（６０１から６０７までのそれぞれ）の入力に送られる。各専用ＯＲゲートの出力は、その出力がＡＮＤゲート６２０の入力に送られるインバーター（６１１から６１７までのそれぞれ）に接続される。ＡＮＤゲート６２０の第８入力は、enable_max_valueと名付けられたイネーブル信号を受ける。ＡＮＤゲート６２０は、比較される値（DATAX[1]からDATAX[7]までのそれぞれ)のＴへの変換と、前記基準値（Max_value[1]からMax_value[7])までそれぞれ）間での等価性の比較の結果である出力信号is_equalを供給する。
【００４８】
図１０は、７ビットにコード化されたＴへの変換（例えば、以前読み出された最大値）の絶対的優位性(strict superiority)と、基準値（trigger2)との比較動作を示している。処理されるＴへの変換の各２進要素、すなわち、Max_value[1]からMax_value[7]までは、インバーター（７１１から７１７のそれぞれ）の出力に接続された第２入力を有するＡＮＤゲート（７０１から７０７のそれぞれ）の第１入力に送られる。かかるインバーターは、基準値（trigger2[1]からtrigger2[7]までのそれぞれ）を受ける入力を有している。ＡＮＤゲート７０１から７０７は、それぞれがＡＮＤゲート７２０の入力に接続される出力を有し、かかるＡＮＤゲート７２０は、他の２つの入力が２の比較値（enable_max_valueおよびenable_trigger2)の信号ENABLEを受けるＡＮＤゲート７３０の第１入力に接続される、出力を有している。ＡＮＤゲート７３０は、出力信号Max_value_superiorを、前記２つの入力間の絶対的優位性の比較結果であるTrigger2へ供給する。
【００４９】
図１１は、図１０の応用例であり、ある値が他の一つより大きいかあるいは等しいかを判断するためのものである。以前行ったように、処理されるＴへの変換の各２進要素（Max_vallue[1]からMax_vallue[7]まで）は、その第２入力がイバーター（８１１から８１７のぞれぞれ）の出力に接続されたＡＮＤゲート（８１１から８１７のそれぞれ）の第１入力に送られる。前記インバーターは、基準値（trigger3[1]trigger3[7]までのそれぞれ）を受ける入力を有する。各ＡＮＤゲート８０１から８０６は、インバーター８４０を介してＡＮＤゲート８３０の第１入力に接続される、ＡＮＤゲート８２０の入力に接続する出力を有する。ＡＮＤゲート８３０の他の２つの入力は、比較される２つの値の２のイネーブリング信号、すなわち、enable_max_valueおよびenable_trigger3を受ける。
【００５０】
ＡＮＤゲート８３０は、信号Max_valueが基準値Trigger3より大きいか等しい場合、その出力において、プラスの信号Max_value_superiorをTrigger3へ供給する。
【００５１】
図１２は、Ｔへの変換が可能な回路の、考え得る構造を機能ブロック形式で示している。前記回路は、３ビットB[2]B[1]B[0]にコード化された値を、そのＴへの変換に変換し、当該変換は、それぞれ、T[7]からT[1]の７ビットにコード化される。前記回路は、復号器９０１および６つのＯＲ型の論理素子９２１から９２６を備えている。各ビットB[2]、B[1]およびB[0]は、それぞれ、is_equal[7]、is_equal[6]、is_equal[5]、is_equal[4]、is_equal[3]、is_equal[2]、is_equal[1]、と呼ばれる７つの値を出力する復号器９０１に送られる。B[2]が’０’、B[1]が’０’で、B[0]が’１’である場合、出力is_equal[1]は、論理値’１’となり、逆の場合には、論理値’０’となる。同様に、三重項(triplet)B[2]B[1]B[0]が、それぞれ値（０、１、０）、（０、１、１）、（１、０、０）、（１、０、１）（１、１、０）および（１、１、１）となる場合、出力is_equal[2]、is_equal[3]、is_equal[4]、is_equal[5]、is_equal[6]、is_equal[7]は、論理値’１’となり、逆の場合には、ヌル値(null value)となる。
【００５２】
６つのＯＲ素子（９２１から９２６）は、それぞれ、復号器９０１のいずれか一つの出力（is_equal[1]からis_equal[6]のそれぞれ)に接続される第１入力を有するとともに、信号Ｔ（１）からＴ（６）を出力する出力を有して設けられる。信号Ｔ（７）は、復号器９０１の出力is_equal[7]から直接入力する。各ＯＲ素子（９２１から９２６）には、さらに、出力Ｔ（２）からＴ（７）の一つにそれぞれ接続された第２入力が設けられている。
【００５３】
このような構成から、手動による最適化方法あるいは論理合成用ツールを使用することにより、Ｔへの変換を高速で行うとともに、最適化されたシリコン表面を有する電子装置を、シリコン上に直接製造することが可能となる。
【００５４】
図１２の回路は、多くの例の中の一つであり、当業者は、本発明を、提供されたどのようなデータフォーマットにも容易に適用することができるが、かかるデータは、順序関係が定義されたセットを構成すること、が明らかでなければならない。
【００５５】
明らかであるように、既に定義されたＴへの変換に基づく情報のコード化は、かなり高速でのデータの取り扱いを可能にする。当業者であれば、データ収集において実行されるどのような動作にも、かかる動作ならびにそれに代わる動作の使用を直接応用することができる。半導体回路内でＴへの変換を実行することにより、データ処理の速度が、従来技術と比べて５倍(in a ratio of 5)と著しく高速となる。
【図面の簡単な説明】
【００５６】
【図１】図１は、８つのデータセットの最大値の第１の既知の読み出し方法を示している。
【図２】図２は、８つのデータセットの最大値の第２の既知の読み出し方法を示している。
【図３】図３は、８つのデータセットの最大値の読み出し装置の好ましい実施形態を示している。
【図４】図４は、３ビットコードを有する３つの値に適用されるＯＲ結合を実行する回路２０９の詳細を示している。
【図５】図５は、８つのデータセットの最小値読み出し装置の好ましい実施形態をを示している。
【図６】図６は、３ビットコードを有する３つの値に適用されるＡＮＤ結合を実行する回路３０９の詳細を示している。
【図７】図７は、３ビットコード専用の条件付トランスコーダーを、機能ブロック図形式で示している。
【図８】図８は、Ｔへの変換前に、３ビットコードを有するデータのＴへの変換の逆の機能を実行するための、専用の条件付トランスコーダー５０１から５０７の配置方法を示している。
【図９】図９は、基準値と、７ビットコードを有する値のＴへの変換との間の等価性の比較動作を示している。
【図１０】図１０は、基準値(trigger2)と、７ビットコードを有する値のＴへの変換との間の絶対的優位性比較を提供する回路を示している。
【図１１】図１１は、図１０の回路の応用例であり、Ｔに変換される値が、他の一つより大きいかあるいは等しいかを判断するための回路、を示している。
【図１２】図１２は、３ビットコードを有する値のＴへの変換を実行する方法を示している。
【図１】
2004206721.tif 000003
【図２】
2004206721.tif 000004
【図３】
2004206721.tif 000005
【図４】
2004206721.tif 000006
【図５】
2004206721.tif 000007
【図６】
2004206721.tif 000008
【図７】
2004206721.tif 000009
【図８】
2004206721.tif 000010
【図９】
2004206721.tif 000011
【図１０】
2004206721.tif 000012
【図１１】
2004206721.tif 000013
【図１２】
2004206721.tif 000014
【外国語明細書】
2004206721.tif 000015
2004206721.tif 000016
2004206721.tif 000017
2004206721.tif 000018
2004206721.tif 000019
2004206721.tif 000020
2004206721.tif 000021
2004206721.tif 000022
2004206721.tif 000023
2004206721.tif 000024
2004206721.tif 000025
2004206721.tif 000026
2004206721.tif 000027
2004206721.tif 000028
2004206721.tif 000029
2004206721.tif 000030
2004206721.tif 000031
2004206721.tif 000032
2004206721.tif 000033
2004206721.tif 000034
2004206721.tif 000035
2004206721.tif 000036
2004206721.tif 000037
2004206721.tif 000038
2004206721.tif 000039
2004206721.tif 000040
2004206721.tif 000041
2004206721.tif 000042
2004206721.tif 000043
2004206721.tif 000044
2004206721.tif 000045
2004206721.tif 000046
2004206721.tif 000047
2004206721.tif 000048
2004206721.tif 000049
2004206721.tif 000050
2004206721.tif 000051