(57)【特許請求の範囲】
【請求項１】
複数の入力を有するルックアップテーブルを実現するために要求されるプログラム可能なアーキテクチャエレメントの数を減じるための方法であって、
ルックアップテーブルにより実行される少なくとも１つの論理関数を選択するステップと、
各入力状態に対する出力状態をルックアップテーブルに対して決定するステップとを含み、その出力状態がルックアップテーブルの出力のアレイを含み、その出力のアレイが入力状態に対する論理関数の応答を含み、
出力状態のグループを形成するステップを含み、その出力状態のグループが同一の出力状態を含み、
選択されたグループの出力状態を排除するステップを含み、その選択されたグループがプログラム可能なアーキテクチャエレメントを必要とせず、さらに、
各々の残りのグループの出力状態に対しプログラム可能なアーキテクチャエレメントを与えるステップを含む、方法。
【請求項２】
プログラム可能なアーキテクチャエレメントがメモリセルを含む、請求項１に記載の方法。
【請求項３】
プログラム可能なアーキテクチャエレメントがスタティックランダムアクセスメモリセルを含む、請求項１に記載の方法。
【請求項４】
論理関数がＡＮＤ、ＯＲおよびＸＯＲのうちの少なくとも１つを含む、請求項１に記載の方法。
【請求項５】
限られた数の特定の多変数論理関数を実行するためのルックアップテーブルアーキテクチャであって、
ルックアップテーブル出力端子と、
プログラム可能なアーキテクチャエレメントのアレイとを含み、そのプログラム可能なアーキテクチャエレメントが特定の多変数論理関数により規定された出力状態をストアし、そのプログラム可能なアーキテクチャエレメントの数が異なる出力状態の数と同じであり、
前記ルックアップテーブルアーキテクチャがさらに、
プログラム可能なアーキテクチャエレメントのアレイおよびルックアップテーブル出力端子に結合された複数の論理ゲートを含み、その論理ゲートが、プログラム可能なアーキテクチャエレメントのアレイにストアされた出力状態をルックアップテーブル出力端子に
ゲーティングし、
論理ゲートに接続された複数の入力端子を含み、信号がその入力端子に与えられ、その信号が入力状態を規定して複数の論理ゲートを制御する、ルックアップテーブルアーキテクチャ。
【請求項６】
複数のインバータをさらに含み、そのインバータが入力状態の補信号を生成し、その補信号が論理ゲートを制御する、請求項５に記載のルックアップテーブルアーキテクチャ。
【請求項７】
プログラム可能なアーキテクチャエレメントがメモリセルを含む、請求項５に記載のルックアップテーブルアーキテクチャ。
【請求項８】
プログラム可能なアーキテクチャエレメントがスタティックランダムアクセスメモリセルを含む、請求項５に記載のルックアップテーブルアーキテクチャ。
【発明の詳細な説明】
【０００１】
【発明の背景】
本発明はルックアップテーブルアーキテクチャに関する。この発明は特に、必要とされるＳＲＡＭセルのようなプログラム可能なアーキテクチャエレメントの数を減じながら限られた数の特定の多変数論理関数を行なうことができるルックアップテーブルを構成するための技術に関する。
【０００２】
ルックアップテーブルは高度に構成可能な組合せ論理装置である。そのプログラミングに柔軟性があるので、それらはプログラム論理装置（ＰＬＤ）内の基本ビルディングブロックとして利用することが望ましい。一般に、ルックアップテーブルは、ＳＲＡＭセルのようなプログラム可能なアーキテクチャエレメントのアレイを用いて、出力信号として有効に用いられるデータビットをストアし、そのデータビットの各々は特定のセットの入力信号に対応する。特定のデータビットは、ルックアップテーブルへの入力信号（およびその補信号）により制御される論理ゲートにより、ルックアップテーブル出力端子にゲーティングされる。図１は一般的な４入力ルックアップテーブルの構成を示す。
【０００３】
ルックアップテーブルは１６個のプログラム可能なＳＲＡＭセル４４により制御されるが、他のタイプのメモリ装置が用いられてもよい。これらのＳＲＡＭセルの各々の出力信号は１６個のＡＮＤゲート８０のそれぞれに与えられる。ＡＮＤゲート８０は、交互に、それぞれ、第１のデータ入力Ｊの真および補の信号により制御され、入力Ｊの補信号はインバータＩ１により生成される。隣接して対になったＡＮＤゲート８０の出力はＯＲゲート８１により結合され、８個のＡＮＤゲート８２に与えられる。ＡＮＤゲート８２は、交互に、それぞれ、第２のデータ入力Ｋの真および補の信号により制御され、入力Ｋの補信号はインバータＩ２により生成される。隣接して対になったＡＮＤゲート８２の出力はＯＲゲート８３により結合され、４個のＡＮＤゲート８４に与えられる。ＡＮＤゲートは、交互に、それぞれ、第３のデータ入力Ｌの真および補の信号により制御され、入力Ｌの補信号はインバータＩ３により生成される。隣接して対になったＡＮＤゲート８４の出力はＯＲゲート８５により結合され、２つのＡＮＤゲート８６に与えられる。ＡＮＤゲート８６の一方は第４のデータ入力Ｍの真の信号により制御され、他方のＡＮＤゲート８６はその入力の補信号により制御され、入力Ｍの補信号はインバータＩ４により生成される。ＡＮＤゲート８６の出力はＯＲゲート８７により結合されてデータ出力を生成する。前述の文から、データ入力Ｊ−Ｍの何らかの所望された論理結合がＳＲＡＭセル４４からの所望された出力を生成することが明らかとなろう。
【０００４】
ルックアップテーブルを構成するのに通常必要とされるＳＲＡＭセルの数はルックアップテーブルの入力の数に依存する。ｎ個の入力を備えたルックアップテーブルに対し、確実にｎ変数の何らかの関数が与えられるようにするために２ｎ  のＳＲＡＭセルが必要とされる。しかしながら、特定のＰＬＤアーキテクチャのプログラマが多数のルックアップテーブルを使って限られた数の論理関数しか実行しないことがよくある。たとえば、特定のＰＬＤがプログラムされる際に、多数のルックアップテーブルが３つの４変数関数である、ＡＮＤ、ＯＲおよびＸＯＲのうちの１つだけしか実行しないことがよくある。そのような場合、３つの関数のうちのいずれであるかにかかわらず、個々のプログラマは最終的に、４入力ルックアップテーブル専用の１６（２４  ）のＳＲＡＭセル内にストアされたデータビットのうちのいくつかを使うだけであり、あり得る出力の全範囲にわたって無駄が生じる。結果的に、ＳＲＡＭセルは効率よく使われず、ＰＬＤ上のスペースは無駄になるだろう。
【０００５】
したがって、ある限られた演算機能を持つルックアップテーブルを構成するのに必要とされるプログラム可能なアーキテクチャエレメントの数を減じる技術およびルックアップテーブルアーキテクチャが必要である。
【０００６】
【発明の概要】
本発明により、限られた数だけの特定の論理関数を実行するルックアップテーブルが提供される。これらのルックアップテーブルは、いかなる所望された論理関数も可能であるルックアップテーブルよりも少ない数のプログラム可能なアーキテクチャエレメント（すなわちＳＲＡＭセル）により構成され、それらの場合に必要とされるエレメントの数は入力接続の数のみに依存する。
【０００７】
このシステムを実行するため、プログラム可能な論理装置の設計者は、ルックアップテーブルが実行可能であるべきなのはどの論理関数であるかを決定しなければならない。したがって各演算機能に対応する真理値表が開発されなければならない。すべての所望された論理関数に対する所与の入力に対する出力の範囲は、ここでは「出力状態」と呼ばれる。論理関数の数が限られるので、出力状態の多くはおそらく同一になるであろう。したがって設計者はすべての同一の出力状態を１つにまとめなければならず、プログラム可能なアーキテクチャエレメントを必要としないどんな出力状態をも排除する。たとえば、常に「０」の結果はプログラム可能なエレメントを必要としないが、代わりに論理「０」レベルにハードワイヤされ得る。したがって設計者はカスタムルックアップテーブルを実現するのに必要とされるプログラム可能なアーキテクチャエレメントの数を決定し、その数は異なる出力状態の数に等しい。
【０００８】
したがって、本発明は複数の入力を有するルックアップテーブルを実現するために必要とされるプログラム可能なアーキテクチャエレメントの数を減じるための方法を含む。この方法は、ルックアップテーブルにより実行される少なくとも１つの論理関数を選択することによりかつ各入力状態に対する出力状態をルックアップテーブルに対し決定することにより、実現される。各出力状態はルックアップテーブルの出力のアレイを含み、それらは入力状態に対し選択された論理関数に応答する。これは同一の出力状態のグループの形成に続いて行なわれ、かつプログラム可能なアーキテクチャエレメントを必要としないいかなる出力状態をも排除する。この方法は出力状態の各グループに対しあるプログラム可能なアーキテクチャエレメントを割り当てることにより達成される。
【０００９】
結果としてできるルックアップテーブルは、上述のように、プログラム可能なアーキテクチャエレメントの数が上述の技術により減じられることを除いては、従来のルックアップテーブルに似ている。以下で述べられる特定の実施例は本発明をより明確に説明するのに役立つ。
【００１０】
【実施例の詳細な説明】
以下の文は、ＡＮＤ、ＯＲおよびＸＯＲ論理関数を実行できる、数が減じられたプログラム可能なアーキテクチャエレメントを備えた、４入力カスタムルックアップテーブルの設計および実現についての説明である。この方法は何らかの簡略化されたセットになった論理関数の設計および実現のために一般化され得る。
【００１１】
図２は３つの異なる所望の機能、ＡＮＤ、ＯＲおよびＸＯＲを実行できる４入力ルックアップテーブルの出力状態を示す、論理真理値表である。Ｊ、Ｋ、ＬおよびＭで示された列は、４入力ルックアップテーブルの入力端子のあり得る状態を示す。ＡＮＤ、ＯＲおよびＸＯＲで示された列は、これらの３つのブール関数の出力端子のあり得る状態を示す。たとえば、Ｊ＝０、Ｋ＝１、Ｌ＝１およびＭ＝１の状態では、出力はＡＮＤ関数に対しては「０」、ＯＲ関数に対しては「１」、排他的ＯＲ関数（ＸＯＲ）に対しては「１」になるだろう。
【００１２】
図２を調べると、ただ４の別個の出力状態、すなわち「０００」、「０１１」、「０１０」、および「１１０」があるということが、すぐにわかるだろう。したがって、ただ４つのＳＲＡＭセルが、この特定のカスタムルックアップテーブルを実現するのに必要とされる。さらに、結果「０００」がどうでもよいならば、要求されたＳＲＡＭセルの数はさらに３に減じられる。いずれの場合にも、ここでは少なくとも７５％だけＳＲＡＭセルの数が減じられるという利点があることが、たやすく理解される。
【００１３】
さらに、これらの３つの論理関数、ＡＮＤ、ＯＲ、およびＸＯＲについて、出力状態の数が入力の数とは独立していることに留意されたい。すなわち、いかに多くの入力変数が含まれていようとも、ＡＮＤ、ＯＲおよびＸＯＲ関数に限られるカスタムルックアップテーブルに関しては４の出力状態（すなわち、「０００」、「０１１」、「０１０」および「１１０」または「１１１」）があるのみだろう。この結果は、ルックアップテーブルに対する入力の数が増えるにつれ、ＳＲＡＭセルの潜在的な節約も増えるということを意味する。
【００１４】
図３は上述の４入力のカスタムルックアップテーブルの構成を示す。この特定の構成は、図１に示された先行技術によるルックアップテーブルと同じだけの多さの論理回路を用いる。しかしながら、ＳＲＡＭセル４４′の数は上述の技術によりかなり減じられる。特定の出力状態を表わすＳＲＡＭ４４′は複数のＡＮＤゲート８０に接続され、それは、同じ出力状態の時に対応する図１のＳＲＡＭセル４４に接続されるようなＡＮＤゲートへの接続である。
【００１５】
たとえば、ＳＲＡＭセル４４′−２にストアされたデータビットは、次のような入力状態、「００１１」、「０１０１」、「０１１０」、「１００１」、「１０１０」、および「１１００」によりルックアップテーブル出力端子にゲーティングされるだろう。したがって、これらの入力状態に対応する出力状態「０１０」はＳＲＡＭセル４４′−２に与えられる。
【００１６】
上述のプログラム可能なアーキテクチャエレメントはＳＲＡＭセルと呼ばれるが、電気的に書込消去可能な読出専用メモリ（ＥＥＰＲＯＭ）のような何らかの他のタイプのメモリ装置がここで説明される発明を実現するのに用いられてもよい。
【００１７】
本発明がその特定の実施例について、特定的に示され説明されたが、この形態および詳細についての前述および他の変更が本発明の範囲から逸脱しないことが、当業者に理解されるだろう。結果として、本発明の範囲は前掲の特許請求の範囲に関してのみ決められるべきである。
【図面の簡単な説明】
【図１】一般的な４入力ルックアップテーブルの構成を示す図である。
【図２】ＡＮＤ、ＯＲおよびＸＯＲ論理関数を実行できる４入力ルックアップテーブルの出力状態を示す、論理真理値表の図である。
【図３】その機能が図２の論理真理値表により示される、４入力ルックアップテーブルの構成を示す図である。
【符号の説明】
４４′  ＳＲＡＭセル
８０  ＡＮＤゲート
８１  ＯＲゲート
８２  ＡＮＤゲート
８３  ＯＲゲート
８４  ＡＮＤゲート
【図１】
0003539997.tif 000002
【図２】
0003539997.tif 000003
【図３】
0003539997.tif 000004