プログラマブル・ロジック・デバイス
【課題】ダイナミック・リコンフィギュラブル・ＬＳＩ等のプログラマブル・ロジック・デバイスにおいて、算術論理演算以外の演算であるデータの並べ替えや適切なビット配置等の処理を行う場合においても、演算器を使用するために回路規模が大きくなる。
【解決手段】プログラマブル・ロジック・デバイス１０１は、各々外部からの設定によって毎サイクル機能変更が可能であり、かつ６４ビットの入力信号を任意の順番に並べ替えて６４ビット信号を出力することが可能な第１の並べ替えセル１０４を複数内蔵する。
【解決手段】プログラマブル・ロジック・デバイス１０１は、各々外部からの設定によって毎サイクル機能変更が可能であり、かつ６４ビットの入力信号を任意の順番に並べ替えて６４ビット信号を出力することが可能な第１の並べ替えセル１０４を複数内蔵する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム可能な演算エレメントを行・列の方向に複数配置するプログラマブル・ロジック・デバイス、又はリコンフィギュラブル回路に関するものである。
【背景技術】
【０００２】
近年、情報処理端末での情報処理に対するニーズは多様化し、通信方式や信号処理の規格はめまぐるしく変化しているため、製品のライフサイクルはますます短くなる傾向にある。この製品サイクルの短縮化に対応するためには、プログラムによって機能の変更が可能なデバイスが有用である。これらの中で、ＡＳＩＣ（Application Specific Integrated Circuit：特定用途向けＩＣ）に匹敵する処理性能とマイクロプロセッサのプログラマビリティとを併せ持つデバイスとして、プログラムによって柔軟に回路構成を変更できるプログラマブル・ロジック・デバイスが注目を集めている。プログラマブル・ロジック・デバイスにはいくつかの種類があるが、代表的な例としてはＦＰＧＡ（Field Programmable Gate Array）やダイナミック・リコンフィギュラブル・ＬＳＩを挙げることができる。
【０００３】
ダイナミック・リコンフィギュラブル・ＬＳＩにおいては、プログラムに柔軟に対応するため、データ処理を実施する際には必ず算術論理演算回路（ＡＬＵ）やシフタ等の演算器を通過する。このため、算術論理演算以外の演算であるデータの並べ替えや適切なビット配置等の処理を行う場合においても、入力データを処理する際に常に演算器を使用する必要がある。これらのデータ処理を並列に多数実施するようなアプリケーションを上記のダイナミック・リコンフィギュラブル・ＬＳＩを用いて実現させた場合、本来のデータ処理には必要のない演算器リソースを多数必要としてしまい、チップ面積の増大や処理サイクル数の増加等の効率低下を招く可能性があった。そこで、これらを改善するために、入力データの並び替え等の演算を実現することができる並べ替えセルと呼ばれる回路が提案された。
【０００４】
データの並べ替え演算用の回路に関しては、暗号における６４ビットデータの並べ替え演算である、転置と呼ばれる演算を行う回路に関して、例えば、以下のようなものがある（特許文献１参照）。特許文献１においては、暗号の転置、換字操作において、暗号化のための鍵とは別の“通し番号”と呼ばれる新たな鍵を入力とし、転置、換字の操作をこの通し番号に依存して変更する暗号化技術が開示されている。特許文献１によれば、従来の転置、換字の操作がハードウェアで固定されている場合に比較して、より解読されにくい暗号化を実現することができる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平８−２２７２６９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、特許文献１に記載の手法においては、暗号化の鍵とは別の新たな鍵を用いることによって秘匿性は向上しているものの、この新たな鍵はユーザーがキー入力等の方法で暗号化回路に与えること、かつ１回のデータ通信の間にこの鍵は変更されないため、仮にこの新たな鍵を盗まれてしまうと暗号の解読が可能となってしまうという課題があった。
【０００７】
本発明は、このような事情に鑑みて創作したものであり、暗号処理における転置と呼ばれる演算の仕方を毎サイクル変更することでより秘匿性が高い暗号処理を実現することができる並べ替えセルと呼ばれる回路を考案し、更に並べ替えセルと呼ばれるこの回路を他のアプリケーションにも使用することで、暗号処理だけでなく、画像認識処理やＨ．２６４コーデック処理を本発明のプログラマブル・ロジック・デバイス上でチップ面積の観点で効率良く実現する方法を提供することを目的としている。
【課題を解決するための手段】
【０００８】
（１）本発明による第１のプログラマブル・ロジック・デバイスは、内部に少なくとも演算器と配線スイッチとを持つ演算エレメントと、プログラムによって配線経路を変更することによって６４ビットの入力信号を任意の順番に並べ替えて６４ビット信号を出力する第１の並べ替えセルを複数内蔵し、かつ前記第１の並べ替えセルは外部からの設定によって毎サイクル機能変更が可能な制御回路を持つ。
【０００９】
この構成によれば、６４ビットのデータに対して１ビット単位でのデータの並べ替えやコピー等の演算を、演算エレメントを用いずに第１の並べ替えセルを用いて実施することが可能となり、プログラマブル・ロジック・デバイスでアプリケーションを実行する際に必要となる演算エレメントの数を削減することが可能となる。
【００１０】
（２）本発明による第２のプログラマブル・ロジック・デバイスは、内部に少なくとも演算器と配線スイッチとを持つ演算エレメントと、６４ビットの入力信号のうち連続する８ビットの信号を１つのグループとして８個のグループに分け、プログラムによって配線経路を変更することによって８個の８ビット信号グループを任意の順番に並び替えて、６４ビットの出力信号を生成する第２の並べ替えセルを複数内蔵し、かつ前記第２の並べ替えセルは外部からの設定によって毎サイクル機能変更が可能な制御回路を持つ。
【００１１】
この構成によれば、６４ビットのデータのうち連続する８ビットの信号グループに対して、信号グループ単位でのデータの並べ替えやコピー等の演算を、演算エレメントを用いずに第２の並べ替えセルを用いて実施することが可能となり、プログラマブル・ロジック・デバイスでアプリケーションを実行する際に必要となる演算エレメントの数を削減することが可能となる。
【００１２】
（３）本発明による第３のプログラマブル・ロジック・デバイスは、内部に少なくとも演算器と配線スイッチとを持つ演算エレメントと、１２８ビットの入力信号のうち連続する８ビットの信号を１つのグループとして１６個のグループに分け、プログラムによって配線経路を変更することによって１６個の８ビット信号グループのうち偶数番目又は奇数番目の８ビット信号グループを選択して出力６４ビットの出力信号を生成する第３の並べ替えセルを複数内蔵し、かつ前記第３の並べ替えセルは外部からの設定によって毎サイクル機能変更が可能な制御回路を持つ。
【００１３】
この構成によれば、１２８ビットのデータのうち連続する８ビットの信号グループに対して、偶数番目又は奇数番目の８ビット信号グループを選択するようなデータの並べ替え等の演算を、演算エレメントを用いずに第３の並べ替えセルを用いて実施することが可能となり、プログラマブル・ロジック・デバイスでアプリケーションを実行する際に必要となる演算エレメントの数を削減することが可能となる。
【発明の効果】
【００１４】
本発明によれば、プログラマブル・ロジック・デバイスでのアプリケーション実行において、データの並べ替えやコピー等の演算を、演算エレメントを用いずに並べ替えセルを用いて実施することが可能となる。これにより、プログラマブル・ロジック・デバイスでアプリケーションを実行する際に必要となる演算エレメントの数を削減することが可能となり、チップ面積の増大を抑えることができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の第１の実施の形態に係るプログラマブル・ロジック・デバイスの構造図である。
【図２】図１中の第１の並べ替えセルの内部構造を示したブロック図である。
【図３】図１中の演算エレメントの内部構造を示したブロック図である。
【図４】図１のプログラマブル・ロジック・デバイスを用いて実現するアプリケーションの例である暗号処理のフロー図である。
【図５】図４中のＦ関数の内部構造を示したフロー図である。
【図６】図１のプログラマブル・ロジック・デバイスによる暗号処理の実装概略図である。
【図７】図１のプログラマブル・ロジック・デバイスを用いて暗号処理を実現する場合のマッピング例を示した図である。
【図８】演算エレメントのみを用いた場合の並べ替え回路の構成例を示したブロック図である。
【図９】本発明の第１の並べ替えセルを使用した場合の並べ替え回路の構成例を示したブロック図である。
【図１０】本発明の第２の実施の形態に係るプログラマブル・ロジック・デバイスの構造図である。
【図１１】図１０の変形例を示した構造図である。
【図１２】図１０及び図１１中の第２の並べ替えセルの内部構造を示したブロック図である。
【図１３】図１０及び図１１のプログラマブル・ロジック・デバイスを用いて実現するアプリケーションの例である画像処理回路のブロック図である。
【図１４】（ａ）、（ｂ）及び（ｃ）は、図１３中の予測画像生成回路における種々の予測モードを説明するための図である。
【図１５】演算エレメントのみを用いた場合の予測画像生成回路の構成例を示したブロック図である。
【図１６】本発明の第２の並べ替えセルを使用した場合の予測画像生成回路の構成例を示したブロック図である。
【図１７】（ａ）、（ｂ）、（ｃ）及び（ｄ）は、図１６中の第２の並べ替えセルの動作を説明するための図である。
【図１８】図１０及び図１１のプログラマブル・ロジック・デバイスを用いて実現するアプリケーションの例である画像認識における人物検出処理回路のブロック図である。
【図１９】（ａ）、（ｂ）及び（ｃ）は、図１８中のプログラマブル接続のサイクル毎の遷移を示す概念図である。
【図２０】本発明の第３の実施の形態に係るプログラマブル・ロジック・デバイスの構造図である。
【図２１】図２０中の第３の並べ替えセルの内部構造を示したブロック図である。
【図２２】図２０のプログラマブル・ロジック・デバイスを用いて実現するアプリケーションの例である携帯電話のデジタルベースバンド処理のフロー図である。
【図２３】図２２中のインターリーブ処理の詳細を示した概念図である。
【図２４】図２３のインターリーブ処理を実現する際の第３の並べ替えセルの１サイクル目の動作を示した概念図である。
【図２５】図２３のインターリーブ処理を実現する際の第３の並べ替えセルの２サイクル目の動作を示した概念図である。
【図２６】演算エレメントのみを用いた場合のインターリーブ回路の構成例を示したブロック図である。
【図２７】本発明の第３の並べ替えセルを使用した場合のインターリーブ回路の構成例を示したブロック図である。
【発明を実施するための形態】
【００１６】
以下、本発明に関わるプログラマブル・ロジック・デバイスの実施の形態について、図面を用いて詳細に説明する。
【００１７】
《第１の実施の形態》
図１は、第１の実施の形態のプログラマブル・ロジック・デバイスを示した構造図である。図１において、プログラマブル・ロジック・デバイス１０１は内部に少なくとも４ビットの演算器と４ビットの配線スイッチと、４ビットの入出力とを持つ演算エレメント１０２と、演算エレメント１０２を１６個×１６個の正方形状に配置し、４ビット×１６個＝６４ビットの入出力を持つ演算エレメント群１０３と、演算エレメント群１０３に隣接して配置され、プログラムによって配線経路を変更することによって６４ビットの入力信号を任意の順番に並べ替えて６４ビット信号を出力し、かつ外部からの設定によって毎サイクル機能変更が可能な６４ビットの入出力を持つ制御回路を持つ第１の並べ替えセル１０４と、演算エレメント群１０３の６４ビット入力と第１の並べ替えセル１０４の６４ビット出力とを接続し、又は演算エレメント群１０３の６４ビット出力と第１の並べ替えセル１０４の６４ビット入力とを接続する配線１０５とを備える。
【００１８】
図２は、図１のプログラマブル・ロジック・デバイス１０１に搭載する第１の並べ替えセル１０４の内部構造を示した図である。第１の並べ替えセル１０４は、８ビット×８並列＝６４ビットのデータ入力２０１と、入力信号をクロック信号の立ち上がりエッジで取り込むフリップフロップ２０２と、外部からの設定入力２０３と、外部からの設定入力２０３を受けてアドレスを生成するアドレスカウンタ２０４と、セレクタを制御するための制御信号を読み出すメモリ２０５と、６４ビットのデータ入力２０１から任意の１ビットを選択する６４対１出力セレクタ２０６と、セレクタ２０６の出力信号をクロック信号の立ち上がりエッジで取り込むフリップフロップ２０７と、６４個のフリップフロップ２０７の出力信号からなる６４ビットのデータ出力２０８とからなる。
【００１９】
図２の構造を持つ第１の並べ替えセル１０４は、外部からの設定入力２０３を受けてアドレスを生成するアドレスカウンタ２０４と、セレクタを制御するための制御信号を読み出すメモリ２０５と、６４ビットのデータ入力２０１から任意の１ビットを選択する６４対１出力セレクタ２０６とを内蔵しているため、データのコピーや並べ替えといった演算を、１サイクルで実行することができる。これらの演算を、ＡＬＵ、シフタ等の演算器から構成される演算エレメント１０２を用いて実現する場合を考えると、各々のデータ演算に対して少なくとも１つの演算エレメント１０２を使用し、なおかつ算術等の演算を行わないにもかかわらず、演算器を使用する必要がある。したがって、図２の構成を持つ第１の並べ替えセル１０４を搭載するプログラマブル・ロジック・デバイス１０１を用いた場合は、ターゲットとするアプリケーションの信号処理のうち、データの並べ替え演算等を、第１の並べ替えセル１０４を用いて実現すれば、全ての信号処理を演算エレメント１０２を用いて実現する場合に比較して、効率良くアプリケーションの信号処理を実現することができる。
【００２０】
図３は、図１のプログラマブル・ロジック・デバイス１０１に搭載する演算エレメント１０２の詳しい構成を示したブロック図である。演算エレメント１０２は、コンフィギュレーションデータの設定によって複数の種類の演算が可能な４ビットの算術論理演算回路（ＡＬＵ）からなる演算ブロック２３０１と、ＡＬＵの４ビット出力値を保持するレジスタ２３０２と、演算エレメント１０２を外部又は別の演算エレメント１０２と接続するための配線２３０３と、配線２３０３とＡＬＵの４ビット入力とを接続し、また配線２３０３をＡＬＵの４ビット出力又はレジスタ２３０２の出力と接続するためのスイッチボックス（ＳＢ）２３０４と、演算ブロック２３０１の演算の種類や、スイッチボックス２３０４の接続状態を決定又は変更することを可能とするためのコンフィギュレーションデータを保持するコンフィギュレーションメモリ２３０５とを持つ。
【００２１】
以上のように構成された本実施の形態について、以下、その動作を説明する。図１、図２に記載のプログラマブル・ロジック・デバイス１０１を用いて実現するアプリケーションの例として、ＤＥＳ（Data Encryption Standard）方式の暗号回路を想定する。
【００２２】
図４は、ＤＥＳの暗号処理を記載したフロー図である。６４ビットの平文入力３０１に対して、初期転置３０２と呼ばれる１ビット単位での並べ替え処理を実施する。更に暗号化に用いる６４ビットの鍵入力３０３については、６４ビットから５６ビットへの転置３０４を実施したのち、上位と下位の２８ビットずつに分離し、シフト３０８の処理を実施する。更に２つの２８ビットのシフト結果は再び５６ビットに結合され、更に５６ビットから４８ビットへの転置処理３０５が実施される。初期転置３０２を行った６４ビットの平文入力は上位と下位の３２ビットに分けられ、下位の３２ビットと転置３０５の４８ビットの鍵データとはＦ関数３０６と呼ばれる関数に入力される。Ｆ関数３０６からは処理された３２ビットデータが出力され、初期転置３０２の６４ビット出力のうち上位３２ビットの出力と排他的論理和が算出される。これによって出力された上位の３２ビットのデータは、Ｆ関数３０６に入力された下位の３２ビットデータと上位下位を入れ替えられ、新たに２つ目のＦ関数３０６にて同様の処理がなされる。その際に、２つ目のＦ関数３０６に入力される鍵データは、更に上位２８ビットと下位２８ビットの鍵入力に対して更にシフト３０８を施したものに、５６ビットから４８ビットへの転置３０５を施したものである。
【００２３】
この処理を１６回繰り返して、最後に最終転置３０７と呼ばれるビットの並べ替え演算を行って、暗号化された６４ビットのデータとして出力される。
【００２４】
図５は、図４の暗号処理フロー図のうち、Ｆ関数３０６の演算の内部構造を示した図である。３２ビットの入力データは、３２ビットから４８ビットに拡張する転置４０１を実施した後、鍵の４８ビット入力との排他的論理和を算出する。４８ビットの排他的論理和の出力は、連続する６ビットが８個のグループに分けられ、それぞれの６ビットデータはＳｂｏｘ４０２と呼ばれる演算を実施する。Ｓｂｏｘ４０２は６ビット入力を４ビット出力に変換する。Ｓｂｏｘ４０２の処理を終えた８個の４ビット出力は、３２ビットの信号に再び結合され、３２ビットの信号を並べ替える転置４０３の処理を施し、３２ビットデータとして出力される。本実施形態で想定する暗号化処理においては、秘匿性の向上のために、３０２、３０４、３０５、３０７、４０１、４０３の転置の処理において、毎サイクル並び替えの処理を変更することを想定する。
【００２５】
図６は、図４、図５で示した暗号処理の処理フローを実際の回路で実装する場合の実装概略図である。図４の６４ビットの平文入力３０１は、図６では平文入力５０１に対応する。図４の初期転置３０２は、図６では初期転置回路５０２に対応する。初期転置回路５０２の出力は、入力データセレクタ５０３に入力される。図５の３２ビットから４８ビットに拡張する転置４０１は、図６では転置回路５０４に対応する。また、図５の排他的論理和は、図６では排他的論理和回路５０５に対応する。図５のＳｂｏｘ４０２は、図６ではＳｂｏｘ回路５０６に対応する。図５の３２ビットの信号を並べ替える転置４０３は、図６では転置回路５０７に対応する。図４の上位３２ビットの出力とＦ関数３０６の３２ビット出力との排他的論理和は、図６の排他的論理和回路５０８に対応する。図４の最終転置３０７は、最終転置回路５０９に対応する。
【００２６】
更に、図４の６４ビット鍵入力３０３は、図６では６４ビット鍵入力５１０に対応する。図４の６４ビットから５６ビットへの転置３０４は、図６では転置回路５１１に対応する。転置回路５１１の出力は、入力データセレクタ５１２に入力される。更に入力データセレクタ５１２の出力は、シフト回路５１３に入力される。シフト回路５１３は、図４のシフト３０８に対応する。図４の５６ビットから４８ビットへの転置３０５は、図６では転置回路５１４に対応する。
【００２７】
次に、図６のＤＥＳ回路を図１のプログラマブル・ロジック・デバイス１０１を用いて実現する場合の回路のマッピングの例を説明する。マッピングの考え方としては、図６のＤＥＳ回路のうち、転置を行う回路においては、入力信号のビットの並び替えは、演算エレメント１０２を用いた場合は面積が非常に大きくなるため、第１の並べ替えセル１０４を使用することとし、これ以外の回路に関しては、演算エレメント１０２を使用するという考え方とする。なお、転置を行う回路を、演算エレメント１０２を用いずに第１の並べ替えセル１０４を用いて実現した場合にどの程度回路面積が削減できるかについては、後述する。
【００２８】
図６の初期転置回路５０２は、第１の並べ替えセル１０４を使用する。ここに使用する第１の並べ替えセル１０４を並べ替えセル（１）と呼ぶ。図６の初期転置回路５０２は６４ビット入力・６４ビット出力であるので、第１の並べ替えセル１０４の６４ビット入出力をフルに使用する。
【００２９】
次に、入力データセレクタ５０３は演算エレメント１０２を使用する。演算エレメント１０２は４ビットの入出力を持つことから、３２ビット×２の入出力を持つ入力データセレクタ５０３を実現するためには、６４／４＝１６個の演算エレメント１０２が必要となる。ここで使用する演算エレメント群を演算エレメント群（１）と呼ぶ。
【００３０】
図６の転置回路５０４は第１の並べ替えセル１０４を使用する。ここに使用する並べ替えセルを並べ替えセル（３）と呼ぶ。図６の転置回路５０４は３２ビット入力・４８ビット出力であるため、第１の並べ替えセル１０４の６４ビット入出力のうち必要なビット数のみ使用し、残りのビットに関しては未使用とする。図６の排他的論理和回路５０５は、演算エレメント１０２を使用する。図６の排他的論理和回路５０５は４８ビット入出力を持つため、４８／４＝１２個の演算エレメント１０２が必要となる。ここで使用する演算エレメント群を演算エレメント群（２）と呼ぶ。図６ではＳｂｏｘ回路５０６は、同様に演算エレメント１０２を使用する。１つのＳｂｏｘ回路５０６は８個の演算エレメント１０２が必要であると仮定すると、８個のＳｂｏｘ回路５０６を実現するためには６４個の演算エレメント１０２が必要となる。ここで使用する演算エレメント群を演算エレメント群（３）と呼ぶ。図６の転置回路５０７は第１の並べ替えセル１０４を使用する。ここに使用する並べ替えセルを並べ替えセル（４）と呼ぶ。図６の転置回路５０７は３２ビット入出力であるため、第１の並べ替えセル１０４のうち半数の入出力を使用し、残りのビット数に関しては未使用とする。図６の排他的論理和回路５０８は、演算エレメント１０２を使用する。図６の排他的論理和回路５０８は３２ビットの入出力を持つため、３２／４＝８個の演算エレメント１０２を使用する。ここで使用する演算エレメント群を演算エレメント群（４）と呼ぶ。図６の最終転置回路５０９は第１の並べ替えセル１０４を使用する。ここに使用する並べ替えセルを並べ替えセル（６）と呼ぶ。図６の最終転置回路５０９は６４ビットの入出力を使用するので、第１の並べ替えセル１０４の６４ビット入出力をフルに使用する。
【００３１】
更に、図６の転置回路５１１は第１の並べ替えセル１０４を使用する。ここに使用する並べ替えセルを並べ替えセル（５）と呼ぶ。図６の転置回路５１１は６４ビット入力と５６ビット出力とを持つため、出力の８ビットは未使用となる。また図６の入力データセレクタ５１２は演算エレメント１０２を使用する。図６の入力データセレクタ５１２は２８ビット×２の入出力を持つため、４ビットの入出力を持つ演算エレメント１０２は５６／４＝１４個必要となる。ここで使用する演算エレメント群を演算エレメント群（５）と呼ぶ。更に図６のシフト回路５１３は演算エレメント１０２を使用する。シフト回路５１３は２８ビット×２の入出力を持つため、４ビットの入出力を持つ演算エレメント１０２は５６／４＝１４個必要となる。ここで使用する演算エレメント群を演算エレメント群（６）と呼ぶ。更に、図６の５６ビットから４８ビットへの転置回路５１４は第１の並べ替えセル１０４を使用する。ここに使用する並べ替えセルを並べ替えセル（２）と呼ぶ。転置回路５１４は５６ビット入力・４８ビット出力を持つため、第１の並べ替えセル１０４の６４ビット入出力のうち必要なビット数のみ使用し、残りのビットに関しては未使用とする。
【００３２】
図７に、図１のプログラマブル・ロジック・デバイス１０１を用いた場合のＤＥＳ回路の実現方法に関して、実際のマッピング例を示す。並べ替えセル（１）は図７の左の列の演算エレメント群１０３の一番上の第１の並べ替えセル１０４を使用する（図７において、並べ替えセル（１）の記載がある箇所）。当該の並べ替えセル（１）はその６４ビット入力がプログラマブル・ロジック・デバイス１０１の上辺のＩＯ部に接続しているため、この上辺のＩＯ部を経由して、プログラマブル・ロジック・デバイス１０１の外部から６４ビットの平文を入力することができる。更に並べ替えセル（１）は、６４ビットの平文入力をもとに、外部からの設定によって、初期転置回路５０２として動作し、６４ビット信号の出力を行う。
【００３３】
次に、演算エレメント群（１）は、図７の左の列の演算エレメント群１０３のうち、一番上の演算エレメント群１０３を使用してマッピングする（図７において、演算エレメント群（１）の記載がある箇所）。演算エレメント群（１）は、配線１０５を経由して、並べ替えセル（１）からの６４ビット出力信号を入力として、外部からの設定によって入力データセレクタ５０３として動作し、上位と下位の３２ビット出力信号を出力する。
【００３４】
次に、並べ替えセル（３）は、図７の左の列の演算エレメント群１０３のうち、一番上の演算エレメント群とその次の演算エレメント群との間にある第１の並べ替えセル１０４を使用する（図７において、並べ替えセル（３）の記載がある箇所）。並べ替えセル（３）は配線１０５を経由して、演算エレメント群（１）の下位の３２ビット出力を入力として、外部からの設定によって、転置回路５０４として動作し、４８ビットの出力信号を出力する。
【００３５】
一方、並べ替えセル（５）は図７の右の列の演算エレメント群１０３の一番上から２番目の演算エレメント群の右隣にある並べ替えセルを使用する（図７において、並べ替えセル（５）の記載がある箇所）。当該の並べ替えセル（５）はその６４ビット入力がプログラマブル・ロジック・デバイス１０１の右辺のＩＯ部に接続しているため、この右辺のＩＯ部を経由して、プログラマブル・ロジック・デバイス１０１の外部から６４ビットの鍵データを入力することができる。更に並べ替えセル（５）は、６４ビットの鍵入力をもとに、外部からの設定によって、転置回路５１１として動作し、上位と下位の２８ビット信号の出力を行う。
【００３６】
次に、演算エレメント群（５）と演算エレメント群（６）は図７の右の列の演算エレメント群のうち、上から２番目の演算エレメント群を使用してマッピングする（図７において、演算エレメント群（５）（６）の記載がある箇所）。この演算エレメント群は、配線１０５を経由して、並べ替えセル（５）からの上位と下位の２８ビット出力信号を入力として、外部からの設定によって入力データセレクタ５１２とシフト回路５１３として動作し、上位と下位の２８ビットを出力する。
【００３７】
次に、並べ替えセル（２）は図７の右の列の演算エレメント群の一番上から２番目の演算エレメント群の左隣にある並べ替えセルを使用する（図７において、並べ替えセル（２）の記載がある箇所）。当該の並べ替えセル（２）は、配線１０５を経由して演算エレメント群（５）（６）からの上位と下位の２８ビット出力を入力として、外部からの設定によって、転置回路５１４として動作し、４８ビット信号の出力を行う。
【００３８】
次に、演算エレメント群（２）と演算エレメント群（３）は図７の左の列の演算エレメント群のうち、上から２番目の演算エレメント群を使用してマッピングする（図７において、演算エレメント群（２）（３）の記載がある箇所）。この演算エレメント群は、配線１０５を経由して、並べ替えセル（３）からの４８ビット出力信号と、配線１０５を経由して、並べ替えセル（２）からの４８ビット出力信号とを入力として、外部からの設定によって排他的論理和回路５０５と、Ｓｂｏｘ回路５０６として動作し、３２ビット出力信号を出力する。
【００３９】
次に、並べ替えセル（４）は図７の右の列の演算エレメント群の一番上から２番目の演算エレメント群と上から３番目の演算エレメント群との間にある並べ替えセルを使用する（図７において、並べ替えセル（４）の記載がある箇所）。当該の並べ替えセル（４）は、配線１０５を経由して演算エレメント群（２）（３）からの３２ビット出力を入力として、外部からの設定によって、転置回路５０７として動作し、３２ビット信号の出力を行う。
【００４０】
次に、演算エレメント群（４）は、図７の左の列の演算エレメント群のうち、上から３番目の演算エレメント群を使用してマッピングする（図７において、演算エレメント群（４）の記載がある箇所）。演算エレメント群（４）は、配線１０５を経由して、並べ替えセル（４）からの３２ビット出力信号を入力として、外部からの設定によって排他的論理和回路５０８として動作し、３２ビット出力信号を出力する。
【００４１】
最後に、並べ替えセル（６）は図７の左の列の演算エレメント群の一番上から３番目の演算エレメント群の下にある並べ替えセルを使用する（図７において、並べ替えセル（６）の記載がある箇所）。当該の並べ替えセル（６）は、配線１０５を経由して、演算エレメント群（４）の３２ビット出力信号と、プログラマブル・ロジック・デバイス１０１の配線ネットワーク（図示せず）を経由して、演算エレメント群（１）の下位３２ビット出力信号を入力として、外部からの設定によって最終転置回路５０９として動作し、６４ビット出力信号を出力する。更に並べ替えセル（６）はその６４ビット出力がプログラマブル・ロジック・デバイス１０１の下辺のＩＯ部に接続しているため、この下辺のＩＯ部を経由して、プログラマブル・ロジック・デバイス１０１の外部に６４ビットの暗号化されたデータを出力することができる。
【００４２】
以上が、図１、図２に記載のプログラマブル・ロジック・デバイス１０１を用いてＤＥＳ方式の暗号回路を実現した場合の実施形態であるが、ここで、図１、図２に記載のプログラマブル・ロジック・デバイス１０１の第１の並べ替えセル１０４を６４ビットの入出力構成とした理由を説明する。まず、ＤＥＳ処理は図４、図５に示すとおり、最大６４ビットを単位とした転置と呼ばれる並べ替え演算が多数存在する。これらの転置の処理を並べ替えセルを用いて実現すると仮定すると、並べ替えセルの入出力ビット数が６４ビットより少ない場合、ＤＥＳの転置処理に必要な６４ビットのランダムな並べ替えが実現できないので、並べ替えセルを用いた並べ替え演算は不可能である。したがって、並べ替え演算は、演算エレメント又は配線ネットワーク（図示せず）を使用する必要がある。
【００４３】
一方、並べ替えセルの入出力ビット数が６４ビットより多い場合は、ＤＥＳの転置処理に必要なビット幅は６４ビットであり、ＤＥＳの処理においては、６４ビットより多いビット数の処理は存在しないため、並べ替えセルの入出力のうち６４ビット分しか使用せず、余剰分は遊びとなり、チップ面積の観点で無駄が生じる。
【００４４】
また、暗号の処理として、新しい方式であるＡＥＳ（Advanced Encryption Standard）の処理を考慮した場合、ＡＥＳでは１２８ビットの並べ替え演算が存在する。しかしながら、実際のＡＥＳの処理では、１２８ビットは４つの３２ビット処理に分割されており、並べ替え演算は３２ビット内で閉じている。したがってＡＥＳの並べ替え演算を並べ替えセルで実現することを考慮した場合、並べ替えセルの入出力信号のビット幅は３２ビット、６４ビット、１２８ビットのうちのいずれかであれば、効率的に処理を行うことができる。
【００４５】
以上の内容を考慮すると、図１、図２に記載のプログラマブル・ロジック・デバイス１０１の第１の並べ替えセル１０４は６４ビットの入出力を持つ構成にすることが最適であると言うことができる。
【００４６】
また、図１、図２に記載のプログラマブル・ロジック・デバイス１０１の演算エレメント群１０３を、演算エレメント１０２を縦方向１６個×横方向１６個配置する構成とした理由を説明する。第１の並べ替えセル１０４は上記の理由で６４ビットの入出力を持つ構成としている。この６４ビットの入出力を演算エレメント群１０３の入出力と接続する構成を考慮すると、１つの演算エレメント１０２の処理ビット数及び入出力ビット数は４ビットのため、６４ビット／４ビット＝１６個の演算エレメント１０２が必要である。このように、演算エレメント群１０３の一辺に１６個の演算エレメント１０２を配置し、正方形状の配置とすることにより、演算エレメント群１０３からの６４ビット入出力を全て第１の並べ替えセル１０４に接続できる構成とすることで、演算エレメント１０２の入出力信号に無駄を生じさせない構成とすることができる。第１の並べ替えセル１０４に接続する演算エレメント１０２の数が１６個より少ないと、第１の並べ替えセル１０４の入出力端子に余剰のピンを生じるため、適さない。また、１６個より多いと、第１の並べ替えセル１０４に接続できない演算エレメント１０２が存在し、この演算エレメント１０２は動作させられず、無駄となる。したがって、演算エレメント群１０３の一辺の演算エレメント１０２の個数は１６個が最適な数となる。
【００４７】
更に、図６に示したＤＥＳの６４ビットの転置を行う回路を、演算エレメント１０２を用いずに第１の並べ替えセル１０４を用いて実現した場合にどの程度回路面積が削減できるかについて説明する。転置回路を、第１の並べ替えセル１０４を配置しない従来のプログラマブル・ロジック・デバイスを用いた場合に必要な演算エレメント１０２の数を、図８を使って説明する。演算エレメントは４ビット単位での処理を実施するので、６４ビットを４ビットずつ１６個の処理に分割する。４ビットから１ビットを抽出するために、図８に示すとおり、４ビットのうち、所定の１ビットのみ“１”で、その他のビットが“０”である定数を入力し、演算エレメントでＡＮＤの演算を行う。これを１ビットから３ビットの間でシフトする回路を生成する。１ビットのシフト演算は、同じデータを足し合わせる演算によって実現するので、図８に示すように、シフトするビット数分、演算エレメントを用いて自身の値の足し算を行う。その後、１ビットから３ビットの間でシフトを行ったデータのうち、所望のデータを選択する。この際にも、演算エレメントをマルチプレクサとして使用する。以上の構成により、１ビットの並べ替えに９個の演算エレメントを使用する。このようにして作成した１ビットシフト結果を、ＯＲ演算により４ビット分を合成して４ビットの出力データを作成する。４ビット分のデータの合成には、３つの演算エレメントを用いてＯＲ演算を実施する。
【００４８】
したがって、必要となる演算エレメントは全部で９個×６４ビット＋３個×（６４／４）＝６２４個となる。演算エレメントの回路を論理合成で作成し、ゲート数の見積もりを行ったところ、約１６０ゲートであったため、６２４×１６０＝９９８４０ゲートとなる。
【００４９】
一方、第１の並べ替えセル１０４を用いた場合に関しては、図９に示すとおり、第１の並べ替えセル１０４を１個使用することで実現できる。図２の構造を持つ第１の並べ替えセル１０４のゲート数は、３ゲートを有する２対１セレクタでの実現を考慮した場合、（６４−１）×６４＝４０３２個必要となる。したがってゲート数は、３×４０３２＝１２０９６ゲートとなる。これを演算エレメントのみで実現した場合と比較すると、約１／８のゲート数に削減していることが分かる。
【００５０】
以上のように、本実施の形態によれば、暗号処理を、第１の実施の形態のプログラマブル・ロジック・デバイス１０１を用いて実現することによって、アプリケーション内の算術演算を必要とする処理に関しては演算エレメント１０２を用いて実現し、暗号処理のデータの１ビット単位での並べ替えのような処理は第１の並べ替えセル１０４を用いて実現することにより、並べ替えの仕方を毎サイクル変更することでより秘匿性が高い暗号処理を実現することができ、更に暗号処理を効率良く本発明のプログラマブル・ロジック・デバイス１０１上で実現することができる。
【００５１】
《第２の実施の形態》
図１０及び図１１は、第２の実施の形態のプログラマブル・ロジック・デバイスを示した構造図である。図１０及び図１１において、プログラマブル・ロジック・デバイス１００１は内部に少なくとも４ビットの演算器と４ビットの配線スイッチと、４ビットの入出力とを持つ演算エレメント１０２と、演算エレメント１０２を１６個×１６個の正方形状に配置し、４ビット×１６個＝６４ビットの入出力を持つ演算エレメント群１０３と、演算エレメント群１０３に隣接して配置され、６４ビットの入力信号のうち連続する８ビットの信号を１つのグループとして８個のグループに分け、プログラムによって配線経路を変更することによって８個の８ビット信号グループを任意の順番に並び替えて６４ビットの出力信号を生成し、かつ外部からの設定によって毎サイクル機能変更が可能な６４ビットの入出力を持つ制御回路を持つ第２の並べ替えセル１００２と、演算エレメント群１０３の６４ビット入力と第２の並べ替えセル１００２の６４ビット出力とを接続し、又は演算エレメント群１０３の６４ビット出力と第２の並べ替えセル１００２の６４ビット入力とを接続する配線１０５とを備える。第２の並べ替えセル１００２の配置については、図１０に示すように、演算エレメント群１０３の行と隣接する演算エレメント群１０３の行との間に、行方向に配置する場合でもよく、また図１１に示すように、演算エレメント群１０３の列と隣接する演算エレメント群１０３の列との間に、列方向に配置する場合でもよい。また図示はしていないが、行方向と列方向の両方に配置してもよい。
【００５２】
図１２は、図１０及び図１１のプログラマブル・ロジック・デバイス１００１に搭載する第２の並べ替えセル１００２の内部構造を示した図である。第２の並べ替えセル１００２は、８ビット×８並列＝６４ビットのデータ入力１１０１と、入力信号をクロック信号の立ち上がりエッジで取り込むフリップフロップ１１０２と、外部からの設定入力１１０３と、外部からの設定入力１１０３を受けてアドレスを生成するアドレスカウンタ１１０４と、セレクタを制御するための制御信号を読み出すメモリ１１０５と、図１２に示すように入力６４ビットのうち、連続する８ビットを１つのデータグループとして、８個のデータグループに分割した場合、８個のデータグループの中から任意の１つのデータグループを選択する８対１出力セレクタ１１０６と、セレクタ１１０６の出力信号をクロック信号の立ち上がりエッジで取り込むフリップフロップ１１０７と、６４個のフリップフロップ１１０７の出力信号からなる６４ビットのデータ出力１１０８とからなる。
【００５３】
図１２の構造を持つ第２の並べ替えセル１００２は、外部からの設定入力１１０３を受けてアドレスを生成するアドレスカウンタ１１０４と、セレクタを制御するための制御信号を読み出すメモリ１１０５と、８個のデータグループの中から任意の１つのデータグループを選択する８対１出力セレクタ１１０６とを内蔵しているため、データのコピーや並べ替えといった演算を、１サイクルで実行することができる。これらの演算を、ＡＬＵ、シフタ等の演算器から構成される演算エレメント１０２を用いて実現する場合を考えると、各々のデータ演算に対して少なくとも１つの演算エレメント１０２を使用し、なおかつ算術等の演算を行わないにもかかわらず、演算器を使用する必要がある。したがって、図１２の構成を持つ第２の並べ替えセル１００２を搭載するプログラマブル・ロジック・デバイス１００１を用いた場合は、ターゲットとするアプリケーションの信号処理のうち、データの並べ替え演算等を、第２の並べ替えセル１００２を用いて実現すれば、全ての信号処理を演算エレメント１０２を用いて実現する場合に比較して、効率良くアプリケーションの信号処理を実現することができる。
【００５４】
以上のように構成された本実施の形態について、以下、その動作を説明する。図１０、図１１、図１２に記載のプログラマブル・ロジック・デバイス１００１を用いて実現するアプリケーションの例として、Ｈ．２６４動画像のエンコード処理を想定する。
【００５５】
図１３及び図１４（ａ）〜図１４（ｃ）は、Ｈ．２６４の処理の概要を示した図面である。入力画像のマクロブロック１２０１は縦８画素×横８画素の６４個の画素からなり、１画素当たりのビット精度は８ビットである。入力画像のマクロブロック１２０１に対する信号処理として、画像データのサイズを圧縮するため、あるマクロブロックを予測するための予測画像生成回路１２０２、予測したマクロブロックと実際の画像データのマクロブロックとの差分値の生成回路１２０３、更にその差分値に対する直交変換回路１２０４、量子化回路１２０５等の処理を実施する。
【００５６】
このうち、画素の数に対応してマトリックス状に多数かつ並列に算術演算を必要とする直交変換回路１２０４や、予測したマクロブロックと実際の画像データのマクロブロックとの差分値の生成回路１２０３に対しては、演算エレメント１０２を多数使用して実現することで、データ演算を並列に効率的に実行することができる。
【００５７】
一方、予測画像生成回路１２０２は、既に信号処理の終わった、現在のマクロブロックよりも以前のマクロブロックデータのうち、現在のマクロブロックに隣接する行又は列のデータを使用し、これを単純にコピー、又は並べ替えてコピーしながらマクロブロック内を埋めることによって予測画像を生成する処理を行う。これらの並べ替えの方法は、データ圧縮を効率的に実現するために、入力された画像の特徴によって複数の方法（以下、予測モードと呼ぶ）が存在する。したがって、処理対象のマクロブロックに対して最適な予測画像を決定するため、一旦全ての予測モードで生成した予測画像を準備する必要がある。
【００５８】
予測画像生成回路１２０２に関して、図１４（ａ）〜図１４（ｃ）を用いて説明する。図１４（ａ）の予測モード０においては、近接のマクロブロックの１列又は１行をそのままコピーしてマクロブロックを埋める。図１４（ｂ）の予測モード１においては、近接のマクロブロックの１列又は１行を、マクロブロックを１行埋めるごとに画素を一個ずつずらしてマクロブロックを埋めていく。図１４（ｃ）の予測モード２においては、近接のマクロブロックの１列又は１行を平均して、これをコピーしてマクロブロックを埋める。したがって、予測画像生成回路１２０２を実現するためには、演算エレメント１０２ではなく、第２の並べ替えセル１００２を用いた方が、より良い面積効率で処理を実現することができる。理由については後述する。
【００５９】
ここで、図１０、図１１、図１２に記載のプログラマブル・ロジック・デバイス１００１の第２の並べ替えセル１００２を６４ビットの入出力構成とした理由を説明する。予測画像生成回路１２０２は８ビットの画像データを８画素分並列に処理を実施するため、第２の並べ替えセル１００２に必要な入出力の構成としては、図１２に示した８ビット×８並列入力＝６４ビットの構成となる。第２の並べ替えセル１００２の入出力ビット数が６４ビットより少ない場合、予測画像生成に必要な８ビット×８画素分の並べ替え処理が実現できないので、第２の並べ替えセル１００２を用いた並べ替え処理は不可能である。したがって、並べ替え処理は、演算エレメント又は配線ネットワーク（図示せず）を使用する必要がある。
【００６０】
一方、第２の並べ替えセル１００２の入出力ビット数が６４ビットより多い場合は、予測画像生成に必要なビット幅は８ビット×８画素分＝６４ビットであり、予測画像生成処理においては、６４ビットより多いビット数の処理は存在しないため、並べ替えセルの入出力のうち６４ビット分しか使用せず、余剰分は遊びとなり、チップ面積の観点で無駄が生じる。
【００６１】
以上の内容を考慮すると、図１０、図１１、図１２に記載のプログラマブル・ロジック・デバイス１００１の第２の並べ替えセル１００２は６４ビットの入出力を持つ構成にすることが最適であると言うことができる。
【００６２】
また、図１０、図１１、図１２に記載のプログラマブル・ロジック・デバイス１００１の演算エレメント群１０３を、演算エレメント１０２を縦方向１６個×横方向１６個配置する構成とした理由を説明する。第２の並べ替えセル１００２は上記の理由で６４ビットの入出力を持つ構成としている。この６４ビットの入出力を演算エレメント群１０３の入出力と接続する構成を考慮すると、１つの演算エレメント１０２の処理ビット数及び入出力ビット数は４ビットのため、６４ビット／４ビット＝１６個の演算エレメント１０２が必要である。このように、演算エレメント群１０３の一辺に１６個の演算エレメント１０２を配置し、正方形状の配置とすることにより、演算エレメント群１０３からの６４ビット入出力を全て第２の並べ替えセル１００２に接続できる構成とすることで、演算エレメント１０２の入出力信号に無駄を生じさせない構成とすることができる。第２の並べ替えセル１００２に接続する演算エレメント１０２の数が１６個より少ないと、第２の並べ替えセル１００２の入出力端子に余剰のピンを生じるため、適さない。また、１６個より多いと、第２の並べ替えセル１００２に接続できない演算エレメントが存在し、この演算エレメント１０２は動作させられず、無駄となる。したがって、演算エレメント群１０３の一辺の演算エレメント１０２の個数は１６個が最適な数となる。
【００６３】
ここで、予測画像生成回路１２０２を実現するに当たって、演算エレメント１０２ではなく、第２の並べ替えセル１００２を用いた方が、より良い面積効率で実現できる理由を説明する。図１４（ｂ）に示した予測画像生成の予測モード１の処理に関して、第２の並べ替えセル１００２を配置しない従来のプログラマブル・ロジック・デバイスを用いた場合に必要な演算エレメント１０２の数を、図１５を使って説明する。予測モード１では８ビットの任意の画素の中から１つの画素を選んで出力するため、演算エレメントはセレクタとして使用する（図中のＭＵＸ）。８画素の入力の中から任意の１つの画素を選び出すため、演算エレメントは図１５に示すとおり、全部で７個必要となる。同様の回路を、８個並列に持つ必要がある。また、演算エレメントの入力ビット数は４ビットのため、８ビットの画素処理を実行するためには、上記の回路をもう一組用意する必要がある。したがって、全部で必要な演算エレメントの数は、７×８×２＝１１２個となる。演算エレメントを論理合成で作成し、ゲート数の見積もりを行ったところ、約１６０ゲートであったため、この並べ替え処理に必要なゲート数は、１６０×１１２＝１７９２０個となる。
【００６４】
一方、第２の並べ替えセル１００２を用いた場合に関しては、図１６に示すとおり、図１２の第２の並べ替えセル１００２を１つ使用することで実現できる。第２の並べ替えセル１００２の動作に関しては図１７（ａ）〜図１７（ｄ）に示すとおり、１サイクル目ではデータの並び替えを実施せずに出力する。２サイクル目では、１画素分をずらして出力を実施する。以降、１サイクル毎に１画素分のデータをずらして出力してゆく。第２の並べ替えセル１００２のゲート数は、３ゲートを有するセレクタで実現した場合、（８−１）×６４＝４４８個必要となる。したがってゲート数は、３×４４８＝１３４４ゲートとなる。これを従来の演算エレメントで実現した場合と比較すると、約１／１０のゲート数に削減していることが分かる。
【００６５】
以上のように、本実施の形態によれば、Ｈ．２６４画像処理を、第２の実施の形態のプログラマブル・ロジック・デバイス１００１を用いて実現することによって、アプリケーション内の算術演算を必要とする処理に関しては演算エレメント１０２を用いて実現し、データのコピーや並べ替えのような信号処理は第２の並べ替えセル１００２を用いて実現することにより、Ｈ．２６４画像処理全体を効率良く本発明のプログラマブル・ロジック・デバイス１００１上で実現することができる。
【００６６】
更に、図１０、図１１、図１２に記載のプログラマブル・ロジック・デバイス１００１を用いて実現するアプリケーションの例として、画像認識の人物検出処理を想定する。
【００６７】
図１８及び図１９（ａ）〜図１９（ｃ）は、画像認識の人物検出処理の概要を示した図面である。入力画像のマクロブロックは縦８画素×横８画素の６４個の画素からなり、１画素当たりのビット精度は８ビットである。この入力画像は、ＨｏＧ（Histgram of Gradient）と呼ばれる方式によって、特徴量の算出が行われる。特徴量の算出の演算は、ある画素を基準として、それに縦方向又は横方向に隣接する画素との輝度の差分を算出し、この差分値に対して、予め求められた画像認識の学習結果に基づく係数を乗じ、隣接する数画素分の値を合計する処理である。ゆえに、特徴量算出においては、算術演算を多数実施する。特徴量算出はマクロブロックの１ライン分が並列に算出され、全体として１つのマクロブロック分の画像データは６４個の特徴量×８カラム分の特徴量データとなる。なお、１つの特徴量データは、８ビット精度の画素を入力として演算を行うため、ビット精度が途中で増減するが、最終的にクリッピング又は伸長の処理を実施して、再び８ビット精度のデータに変換される。
【００６８】
特徴量算出を行ったあと、識別器によってそれぞれの特徴量に対して、画像が人物か否かの判定を行うため、相関計算が実施される。ここでは、６４個の識別器が存在するものとする。なお、識別器の数は、必要とする検出精度に応じて多くても少なくしてもよい。この識別器による相関計算は、１カラム分の６４個の特徴量に関して並列に実行される。
【００６９】
一方、特徴量の算出はマクロブロックの行方向に実施されるため、特徴量の算出結果は８カラム×６４個の特徴量保持レジスタに一旦保持して、特徴量算出による特徴量保持レジスタへのデータ書き込みが完了したのち、識別器による相関計算を開始する必要がある。識別器による相関計算は、特徴量保持レジスタの８つのカラムのうち、１サイクル毎に選択するカラムを変更して、識別器による相関計算を実施する。図１８中の特徴量保持レジスタでは、カラム４が選択されている場合を想定して、カラム４を太線で囲んでいる。
【００７０】
ここで、識別器で相関計算を実施する際に、特徴量保持レジスタのあるカラムの６４の特徴量データのうち、どの特徴量を参照して相関計算を行うかは、選択するカラムに依存して異なる。これについて、図１９（ａ）〜図１９（ｃ）を用いて説明する。まず相関計算の１サイクル目、すなわちカラム０を選択している場合は、図１９（ａ）に示したような接続状態（すなわち参照状態）となる。次のサイクル、すなわちカラム１を選択している場合は、図１９（ｂ）に示したような接続状態（すなわち参照状態）に変更される。このとき、図１９（ｂ）の接続状態のように１つの特徴量が複数の識別器に参照されるような状態もありうる。このように１サイクル毎に選択されるカラムが変更されるに当たって、毎サイクル接続状態が変更されて行き、８サイクル目の接続状態（図１９（ｃ）参照）まで変更され、識別器による相関計算が完了した際に、特徴量保持レジスタに蓄えられた８カラム×６４個分の特徴量に対する相関計算が完了する。このあとは、また新たなマクロブロックによる特徴量の算出が開始される。以上が画像認識の人物検出処理の概要である。
【００７１】
また、画像認識アプリケーションに関しては認識率の向上や誤検出率の低下等の改善が日々なされており、ＬＳＩ開発後にも改善が可能であることが望ましい。そこで、本画像認識の人物検出処理においては、学習結果をＬＳＩ開発後も更新できる構成とする。そのためには、学習結果に応じて識別器と特徴量保持レジスタとの接続をプログラムによって変更可能としておくことが必要である。
【００７２】
以上の要件を満たすため、図１８及び図１９（ａ）〜図１９（ｃ）に示した画像認識の人物検出処理を図１０、図１１、図１２に示した本発明のプログラマブル・ロジック・デバイスを用いて実現することを検討する。まず、図１８の特徴量算出の処理は多数の算術演算を持つことから、演算エレメント１０２を用いて実現する。次に、特徴量保持レジスタとカラム選択用のセレクタも演算エレメント１０２を用いて実現する。一方、８ビット８並列の入出力を持つ８個のプログラマブル接続に関しては、図１９（ａ）〜図１９（ｃ）に示したとおり毎サイクル接続状態を変更する必要があり、また学習結果の更新によっても接続状態を変更する必要があるため、図１１に記載の第２の並べ替えセル１００２を８個用いて実現する。更に後段の識別器に関しては、８個の識別器を一組として、１つの演算エレメント群１０３を用いて実現する。したがって、識別器は全部で６４個存在するため、識別器の処理として使用する演算エレメント群１０３は８個となる。この８個の演算エレメント群１０３は、図１１において、第２の並べ替えセル１００２に対して右側の演算エレメント群１０３を使用することによって、第２の並べ替えセル１００２を８個用いて実現する８個のプログラマブル配線からの出力を直接演算エレメント群１０３で受け取ることができ、チップ面積の観点で効率良く人物検出処理を実現することができる。また同様に、図１８の特徴量算出、特徴量保持レジスタ、及びカラム選択用のセレクタは、図１１において、第２の並べ替えセル１００２に対して左側の演算エレメント群１０３を使用することによって、演算エレメント群１０３の出力を直接、第２の並べ替えセル１００２を８個用いて実現する８個のプログラマブル配線に渡すことができ、チップ面積の観点で効率良く人物検出処理を実現することができる。なお、図１８のプログラマブル配線に関しては、演算エレメント１０２ではなく第２の並べ替えセル１００２を使用して実現した方が、より良い面積効率で処理を実現することができる。この理由は、Ｈ．２６４動画像のエンコード処理を想定した場合の説明内容と同じである。
【００７３】
《第３の実施の形態》
図２０は、第３の実施の形態のプログラマブル・ロジック・デバイス１６０１を示した構造図である。図２０において、プログラマブル・ロジック・デバイス１６０１は、内部に少なくとも４ビットの演算器と４ビットの配線スイッチと、４ビットの入出力とを持つ演算エレメント１０２と、演算エレメント１０２を１６個×１６個の正方形状に配置し、４ビット×１６個＝６４ビットの入出力を持つ演算エレメント群１０３と、更に複数の演算エレメント群１０３とＩＯ部との間に配置され、１２８ビットの入力信号のうち連続する８ビットの信号を１つのグループとして１６個のグループに分け、プログラムによって配線経路を変更することによって１６個の８ビット信号グループのうち偶数番目又は奇数番目の８ビット信号グループを選択して出力６４ビットの出力信号を生成し、かつ外部からの設定によって毎サイクル機能変更が可能な制御回路を持つ第３の並べ替えセル１６０２と、演算エレメント群１０３の６４ビット入力と第３の並べ替えセル１６０２の６４ビット出力とを接続し、第３の並べ替えセル１６０２の１２８ビット入力とＩＯ部とを接続する配線１０５とを備える。第３の並べ替えセル１６０２の配置については、図２０に示すように、演算エレメント群１０３とＩＯ部との間の一部の箇所に配置していてもよいし、全ての箇所に配置していてもよい。
【００７４】
図２１は、図２０のプログラマブル・ロジック・デバイス１６０１に搭載する第３の並べ替えセル１６０２の内部構造を示した図である。第３の並べ替えセル１６０２は、８ビット×１６並列＝１２８ビットのデータ入力１７０１と、入力信号をクロック信号の立ち上がりエッジで取り込むフリップフロップ１７０２と、外部からの設定入力１７０３と、外部からの設定入力１７０３を受けてアドレスを生成するアドレスカウンタ１７０４と、セレクタを制御するための制御信号を読み出すメモリ１７０５と、図２１に示すように入力１２８ビットのうち、連続する８ビットを１つのデータグループとして、１６個のデータグループに分割した場合、１６個のデータグループの中から隣接する奇数番目と偶数番目のデータグループを選択する２対１出力セレクタ１７０６と、セレクタ１７０６の出力信号をクロック信号の立ち上がりエッジで取り込むフリップフロップ１７０７と、６４個のフリップフロップ１７０７の出力信号からなる６４ビットのデータ出力１７０８とからなる。
【００７５】
図２１の構造を持つ第３の並べ替えセル１６０２は、外部からの設定入力１７０３を受けてアドレスを生成するアドレスカウンタ１７０４と、セレクタを制御するための制御信号を読み出すメモリ１７０５と、１６個のデータグループの中から隣接する奇数番目と偶数番目のデータグループを選択する２対１出力セレクタ１７０６とを内蔵しているため、データのコピーや並べ替えといった演算を、１サイクルで実行することができる。これらの演算を、ＡＬＵ、シフタ等の演算器から構成される演算エレメント１０２を用いて実現する場合を考えると、各々のデータ演算に対して少なくとも１つの演算エレメント１０２を使用し、なおかつ算術等の演算を行わないにもかかわらず、演算器を使用する必要がある。したがって、図２１の構成を持つ第３の並べ替えセル１６０２を搭載するプログラマブル・ロジック・デバイス１６０１を用いた場合は、ターゲットとするアプリケーションの信号処理のうち、データの並べ替え演算等を、第３の並べ替えセル１６０２を用いて実現すれば、全ての信号処理を演算エレメント１０２を用いて実現する場合に比較して、効率良くアプリケーションの信号処理を実現することができる。
【００７６】
図２０、図２１に記載のプログラマブル・ロジック・デバイス１６０１を用いて実現するアプリケーションの例として、ＧＳＭ（Global System for Mobile Communications）方式携帯電話のデジタルベースバンド処理を想定する。
【００７７】
図２２及び図２３に、ＧＳＭ方式携帯電話のデジタルベースバンド処理の概略を示す。この信号処理では、１ビット単位での入力信号に対し、決まったビット数を一旦メモリ又はレジスタ等の記憶素子に格納し、これを所定の手順で並べ替えるインターリーブ処理を施した後、リードソロモン復号やパンクチュアリング等の信号処理を実施する。インターリーブ処理は上記のようにデータの並べ替えの演算を含んでおり、しかも１ビット単位での信号処理を含むため、演算エレメントを用いて信号処理を実施するのではなく、並べ替えセルを使用して実現した方が効率的である。更に、これらの信号処理は、デジタルベースバンド処理のうち初期の段階で実施する必要がある。
【００７８】
インターリーブ処理に関して、その動作の詳細について図２４及び図２５を用いて説明する。図２４及び図２５は、図２１に記載の第３の並べ替えセル１６０２を模式的に描いたものである。ここでは、入力信号を取り込む１２８ビットのフリップフロップ１７０２を６４ビットずつ２つの組に分ける。
【００７９】
デジタルベースバンド処理における入力データは、１ビット単位の入力データが所定の符号長を持ったデータとして順次レジスタに蓄えられる。これを最初は第３の並べ替えセル１６０２の１組目の６４ビットのフリップフロップ１７０２に入力する。この１組目の６４ビットのフリップフロップ１７０２内にデータが満杯に蓄えられた後は、デジタルベースバンド処理の入力データは順次２組目の６４ビットのフリップフロップ１７０２に蓄えられる。
【００８０】
これらのデータが蓄えられた後は、アドレスカウンタ１７０４が外部から所定の値に設定されることにより、下記の要領にてデータの並べ替え演算が実施される。
【００８１】
１サイクル目の設定値では、アドレスカウンタ１７０４とメモリ１７０５との動作により、入力の８ビット×１６並列入力と出力の８ビット×８並列出力との接続関係は図２４に示す状態となる。１組目の６４ビットのフリップフロップ１７０２の奇数番目の８ビットデータと、２組目の６４ビットのフリップフロップ１７０２の奇数番目の８ビットデータとが出力の６４ビットフリップフロップ１７０７に接続され、データが転送される。
【００８２】
次のサイクルでは、外部の設定値が変更され、アドレスカウンタ１７０４とメモリ１７０５との動作により、入力の８ビット×１６並列入力と出力の８ビット×８並列出力との接続関係は図２５に示す状態となる。１組目の６４ビットのフリップフロップ１７０２の偶数番目の８ビットデータと、２組目の６４ビットのフリップフロップ１７０２の偶数番目の８ビットデータとが出力の６４ビットフリップフロップ１７０７に接続され、データが転送される。このようにインターリーブ処理は第３の並べ替えセル１６０２を用いて２サイクルで実施することができる。
【００８３】
ここで、図２０、図２１に記載のプログラマブル・ロジック・デバイス１６０１の第３の並べ替えセル１６０２を１２８／６４ビットの入出力構成とした理由を説明する。インターリーブ処理では、８ビット８並列のデータが２組入力されるため、第３の並べ替えセル１６０２に必要な入力の構成としては、図２１に示した８ビット×１６並列入力＝１２８ビットの構成となる。第３の並べ替えセル１６０２の入力ビット数が１２８ビットより少ない場合、８ビット×１６並列データの並べ替え処理が実現できないので、第３の並べ替えセル１６０２を用いた並べ替え処理は不可能である。したがって、並べ替え処理は、演算エレメント又は配線ネットワーク（図示せず）を使用する必要がある。
【００８４】
一方、第３の並べ替えセル１６０２の入力ビット数が１２８ビットより多い場合は、インターリーブ処理に必要なビット幅は８ビット×１６画素分＝１２８ビットであり、１２８ビットより多いビット数の処理は存在しないため、第３の並べ替えセル１６０２の入力のうち１２８ビット分しか使用せず、余剰分は遊びとなり、チップ面積の観点で無駄が生じる。
【００８５】
以上の内容を考慮すると、図２０、図２１に記載のプログラマブル・ロジック・デバイス１６０１の第３の並べ替えセル１６０２は１２８ビットの入力と６４ビットの出力とを持つ構成にすることが最適であると言うことができる。
【００８６】
また、図２０、図２１に記載のプログラマブル・ロジック・デバイス１６０１の演算エレメント群１０３を、演算エレメント１０２を縦方向１６個×横方向１６個配置する構成とした理由を説明する。第３の並べ替えセル１６０２は上記の理由で１２８ビットの入力と６４ビットの出力とを持つ構成としている。このうち６４ビットの出力を演算エレメント群１０３の入力と接続する構成を考慮すると、１つの演算エレメント１０２の処理ビット数及び入出力ビット数は４ビットのため、６４ビット／４ビット＝１６個の演算エレメントが必要である。このように、演算エレメント群１０３の一辺に１６個の演算エレメント１０２を配置し、正方形状の配置とすることにより、演算エレメント群１０３の６４ビット入力を全て第３の並べ替えセル１６０２の出力に接続できる構成とすることで、演算エレメント１０２の入力信号に無駄を生じさせない構成とすることができる。第３の並べ替えセル１６０２に接続する演算エレメント１０２の数が１６個より少ないと、第３の並べ替えセル１６０２の出力に余剰のピンを生じるため、適さない。また、１６個より多いと、第３の並べ替えセル１６０２に接続できない演算エレメント１０２が存在し、この演算エレメント１０２は動作させられず、無駄となる。したがって、演算エレメント群１０３の一辺の演算エレメント１０２の個数は１６個が最適な数となる。
【００８７】
ここで、インターリーブ処理を実現するに当たって、演算エレメント１０２ではなく、第３の並べ替えセル１６０２を用いた方が、より良い面積効率で実現できる理由を説明する。
【００８８】
まず、インターリーブ処理に関して、並べ替えセルを配置しない従来のプログラマブル・ロジック・デバイスを用いた場合に必要な演算エレメントの数を、図２６を使って説明する。インターリーブ処理では１組目の８入力データに対して、奇数側と偶数側との入力を選択して４組の出力を得るので、演算エレメントを２対１のマルチプレクサとして使用した場合、４つの演算エレメントを使用する。更に２組目の８入力データに対して、奇数側と偶数側との入力を選択して４組の出力を得るので、更に４つの演算エレメントを使用する。合計で８個の演算エレメントが必要となる。更に１つの演算エレメントで処理できるビット数は４ビットのため、８ビットのデータを処理するためには、２倍の演算エレメントが必要となる。よって、必要な演算エレメントの総数は８×２＝１６個となる。演算エレメント１つあたりに約１６０個ゲートを使用するため、全体でのゲート数は１６×１６０＝２５６０ゲートとなる。
【００８９】
一方、第３の並べ替えセル１６０２を用いた場合に関しては、図２７に示すとおり、第３の並べ替えセル１６０２を１つ使用することで実現できる。第３の並べ替えセル１６０２のゲート数は、３ゲートを有する２対１セレクタで実現した場合、８×８＝６４個必要となる。したがってゲート数は、３×６４＝１９２ゲートとなる。これを従来の演算エレメントで実現した場合と比較すると、約１／１０以下のゲート数に削減していることが分かる。
【００９０】
以上のように、本実施の形態によれば、ＧＳＭ方式携帯電話のデジタルベースバンド処理を、第３の実施の形態のプログラマブル・ロジック・デバイス１６０１を用いて実現することによって、デジタルベースバンド処理内の算術演算を必要とする処理に関しては演算エレメント１０２を用いて実現し、インターリーブ処理のようなデータの並べ替え処理は第３の並べ替えセル１６０２を用いて実現することにより、ＧＳＭ方式携帯電話のデジタルベースバンド処理全体を効率良く本発明のプログラマブル・ロジック・デバイス１６０１上で実現することができる。
【００９１】
なお、上記各実施の形態において、４ビットの演算エレメント１０２に代えて８ビットの演算エレメントを利用することも可能である。
【産業上の利用可能性】
【００９２】
本発明のプログラマブル・ロジック・デバイスは、外部からの設定によって毎サイクル機能変更が可能な制御回路を持ち、かつプログラムによって配線経路を変更することによって６４ビット又は１２８ビットの入力信号を並べ替えて６４ビット信号を出力する並べ替えセルを複数内蔵するため、プログラマブル・ロジック・デバイスで実行するアプリケーションのうち、データの並び替えやコピー等の演算を、演算エレメントを用いずに、小面積で実現することができる。これによって、アプリケーションを実行する際に必要となる演算エレメントの数を削減することができるという効果を有し、複数の演算エレメントと、演算エレメント間を相互に接続する複数の配線及びスイッチからなるプログラマブル・ロジック・デバイス回路として有用である。
【符号の説明】
【００９３】
１０１ プログラマブル・ロジック・デバイス
１０２ 演算エレメント
１０３ 演算エレメント群
１０４ 並べ替えセル（６４ビット入出力）
１０５ 配線
２０１ データ入力（６４ビット）
２０２ フリップフロップ
２０３ 設定入力
２０４ アドレスカウンタ
２０５ メモリ
２０６ ６４対１出力セレクタ
２０７ フリップフロップ
２０８ データ出力（６４ビット）
３０１ 平文入力（６４ビット）
３０２ 初期転置（並べ替え）
３０３ 鍵入力（６４ビット）
３０４ 転置（６４ビット−＞５６ビット）
３０５ 転置（５６ビット−＞４８ビット）
３０６ Ｆ関数
３０７ 最終転置（並べ替え）
３０８ シフト
４０１ 転置（３２ビット−＞４８ビット）
４０２ Ｓｂｏｘ
４０３ 転置（３２ビット−＞３２ビット）
５０１ 平文入力（６４ビット）
５０２ 初期転置回路（並べ替え）
５０３ 入力データセレクタ
５０４ 転置回路（３２ビット−＞４８ビット）
５０５ 排他的論理和回路
５０６ Ｓｂｏｘ回路
５０７ 転置回路（３２ビット−＞３２ビット）
５０８ 排他的論理和回路
５０９ 最終転置回路（並べ替え）
５１０ 鍵入力（６４ビット）
５１１ 転置回路（６４ビット−＞５６ビット）
５１２ 入力データセレクタ
５１３ シフト回路
５１４ 転置回路（５６ビット−＞４８ビット）
１００１ プログラマブル・ロジック・デバイス
１００２ 第２の並べ替えセル（６４ビット入出力）
１１０１ データ入力（６４ビット）
１１０２ フリップフロップ
１１０３ 設定入力
１１０４ アドレスカウンタ
１１０５ メモリ
１１０６ ８対１出力セレクタ
１１０７ フリップフロップ
１１０８ データ出力（６４ビット）
１２０１ マクロブロック入力
１２０２ 予測画像生成回路
１２０３ 差分値生成回路
１２０４ 直交変換回路
１２０５ 量子化回路
１６０１ プログラマブル・ロジック・デバイス
１６０２ 第３の並べ替えセル（１２８ビット入力・６４ビット出力）
１７０１ データ入力（１２８ビット）
１７０２ フリップフロップ
１７０３ 設定入力
１７０４ アドレスカウンタ
１７０５ メモリ
１７０６ ２対１出力セレクタ
１７０７ フリップフロップ
１７０８ データ出力（６４ビット）
２３０１ 演算ブロック
２３０２ レジスタ
２３０３ 配線
２３０４ スイッチボックス（ＳＢ）
２３０５ コンフィギュレーションメモリ
【技術分野】
【０００１】
本発明は、プログラム可能な演算エレメントを行・列の方向に複数配置するプログラマブル・ロジック・デバイス、又はリコンフィギュラブル回路に関するものである。
【背景技術】
【０００２】
近年、情報処理端末での情報処理に対するニーズは多様化し、通信方式や信号処理の規格はめまぐるしく変化しているため、製品のライフサイクルはますます短くなる傾向にある。この製品サイクルの短縮化に対応するためには、プログラムによって機能の変更が可能なデバイスが有用である。これらの中で、ＡＳＩＣ（Application Specific Integrated Circuit：特定用途向けＩＣ）に匹敵する処理性能とマイクロプロセッサのプログラマビリティとを併せ持つデバイスとして、プログラムによって柔軟に回路構成を変更できるプログラマブル・ロジック・デバイスが注目を集めている。プログラマブル・ロジック・デバイスにはいくつかの種類があるが、代表的な例としてはＦＰＧＡ（Field Programmable Gate Array）やダイナミック・リコンフィギュラブル・ＬＳＩを挙げることができる。
【０００３】
ダイナミック・リコンフィギュラブル・ＬＳＩにおいては、プログラムに柔軟に対応するため、データ処理を実施する際には必ず算術論理演算回路（ＡＬＵ）やシフタ等の演算器を通過する。このため、算術論理演算以外の演算であるデータの並べ替えや適切なビット配置等の処理を行う場合においても、入力データを処理する際に常に演算器を使用する必要がある。これらのデータ処理を並列に多数実施するようなアプリケーションを上記のダイナミック・リコンフィギュラブル・ＬＳＩを用いて実現させた場合、本来のデータ処理には必要のない演算器リソースを多数必要としてしまい、チップ面積の増大や処理サイクル数の増加等の効率低下を招く可能性があった。そこで、これらを改善するために、入力データの並び替え等の演算を実現することができる並べ替えセルと呼ばれる回路が提案された。
【０００４】
データの並べ替え演算用の回路に関しては、暗号における６４ビットデータの並べ替え演算である、転置と呼ばれる演算を行う回路に関して、例えば、以下のようなものがある（特許文献１参照）。特許文献１においては、暗号の転置、換字操作において、暗号化のための鍵とは別の“通し番号”と呼ばれる新たな鍵を入力とし、転置、換字の操作をこの通し番号に依存して変更する暗号化技術が開示されている。特許文献１によれば、従来の転置、換字の操作がハードウェアで固定されている場合に比較して、より解読されにくい暗号化を実現することができる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平８−２２７２６９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、特許文献１に記載の手法においては、暗号化の鍵とは別の新たな鍵を用いることによって秘匿性は向上しているものの、この新たな鍵はユーザーがキー入力等の方法で暗号化回路に与えること、かつ１回のデータ通信の間にこの鍵は変更されないため、仮にこの新たな鍵を盗まれてしまうと暗号の解読が可能となってしまうという課題があった。
【０００７】
本発明は、このような事情に鑑みて創作したものであり、暗号処理における転置と呼ばれる演算の仕方を毎サイクル変更することでより秘匿性が高い暗号処理を実現することができる並べ替えセルと呼ばれる回路を考案し、更に並べ替えセルと呼ばれるこの回路を他のアプリケーションにも使用することで、暗号処理だけでなく、画像認識処理やＨ．２６４コーデック処理を本発明のプログラマブル・ロジック・デバイス上でチップ面積の観点で効率良く実現する方法を提供することを目的としている。
【課題を解決するための手段】
【０００８】
（１）本発明による第１のプログラマブル・ロジック・デバイスは、内部に少なくとも演算器と配線スイッチとを持つ演算エレメントと、プログラムによって配線経路を変更することによって６４ビットの入力信号を任意の順番に並べ替えて６４ビット信号を出力する第１の並べ替えセルを複数内蔵し、かつ前記第１の並べ替えセルは外部からの設定によって毎サイクル機能変更が可能な制御回路を持つ。
【０００９】
この構成によれば、６４ビットのデータに対して１ビット単位でのデータの並べ替えやコピー等の演算を、演算エレメントを用いずに第１の並べ替えセルを用いて実施することが可能となり、プログラマブル・ロジック・デバイスでアプリケーションを実行する際に必要となる演算エレメントの数を削減することが可能となる。
【００１０】
（２）本発明による第２のプログラマブル・ロジック・デバイスは、内部に少なくとも演算器と配線スイッチとを持つ演算エレメントと、６４ビットの入力信号のうち連続する８ビットの信号を１つのグループとして８個のグループに分け、プログラムによって配線経路を変更することによって８個の８ビット信号グループを任意の順番に並び替えて、６４ビットの出力信号を生成する第２の並べ替えセルを複数内蔵し、かつ前記第２の並べ替えセルは外部からの設定によって毎サイクル機能変更が可能な制御回路を持つ。
【００１１】
この構成によれば、６４ビットのデータのうち連続する８ビットの信号グループに対して、信号グループ単位でのデータの並べ替えやコピー等の演算を、演算エレメントを用いずに第２の並べ替えセルを用いて実施することが可能となり、プログラマブル・ロジック・デバイスでアプリケーションを実行する際に必要となる演算エレメントの数を削減することが可能となる。
【００１２】
（３）本発明による第３のプログラマブル・ロジック・デバイスは、内部に少なくとも演算器と配線スイッチとを持つ演算エレメントと、１２８ビットの入力信号のうち連続する８ビットの信号を１つのグループとして１６個のグループに分け、プログラムによって配線経路を変更することによって１６個の８ビット信号グループのうち偶数番目又は奇数番目の８ビット信号グループを選択して出力６４ビットの出力信号を生成する第３の並べ替えセルを複数内蔵し、かつ前記第３の並べ替えセルは外部からの設定によって毎サイクル機能変更が可能な制御回路を持つ。
【００１３】
この構成によれば、１２８ビットのデータのうち連続する８ビットの信号グループに対して、偶数番目又は奇数番目の８ビット信号グループを選択するようなデータの並べ替え等の演算を、演算エレメントを用いずに第３の並べ替えセルを用いて実施することが可能となり、プログラマブル・ロジック・デバイスでアプリケーションを実行する際に必要となる演算エレメントの数を削減することが可能となる。
【発明の効果】
【００１４】
本発明によれば、プログラマブル・ロジック・デバイスでのアプリケーション実行において、データの並べ替えやコピー等の演算を、演算エレメントを用いずに並べ替えセルを用いて実施することが可能となる。これにより、プログラマブル・ロジック・デバイスでアプリケーションを実行する際に必要となる演算エレメントの数を削減することが可能となり、チップ面積の増大を抑えることができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の第１の実施の形態に係るプログラマブル・ロジック・デバイスの構造図である。
【図２】図１中の第１の並べ替えセルの内部構造を示したブロック図である。
【図３】図１中の演算エレメントの内部構造を示したブロック図である。
【図４】図１のプログラマブル・ロジック・デバイスを用いて実現するアプリケーションの例である暗号処理のフロー図である。
【図５】図４中のＦ関数の内部構造を示したフロー図である。
【図６】図１のプログラマブル・ロジック・デバイスによる暗号処理の実装概略図である。
【図７】図１のプログラマブル・ロジック・デバイスを用いて暗号処理を実現する場合のマッピング例を示した図である。
【図８】演算エレメントのみを用いた場合の並べ替え回路の構成例を示したブロック図である。
【図９】本発明の第１の並べ替えセルを使用した場合の並べ替え回路の構成例を示したブロック図である。
【図１０】本発明の第２の実施の形態に係るプログラマブル・ロジック・デバイスの構造図である。
【図１１】図１０の変形例を示した構造図である。
【図１２】図１０及び図１１中の第２の並べ替えセルの内部構造を示したブロック図である。
【図１３】図１０及び図１１のプログラマブル・ロジック・デバイスを用いて実現するアプリケーションの例である画像処理回路のブロック図である。
【図１４】（ａ）、（ｂ）及び（ｃ）は、図１３中の予測画像生成回路における種々の予測モードを説明するための図である。
【図１５】演算エレメントのみを用いた場合の予測画像生成回路の構成例を示したブロック図である。
【図１６】本発明の第２の並べ替えセルを使用した場合の予測画像生成回路の構成例を示したブロック図である。
【図１７】（ａ）、（ｂ）、（ｃ）及び（ｄ）は、図１６中の第２の並べ替えセルの動作を説明するための図である。
【図１８】図１０及び図１１のプログラマブル・ロジック・デバイスを用いて実現するアプリケーションの例である画像認識における人物検出処理回路のブロック図である。
【図１９】（ａ）、（ｂ）及び（ｃ）は、図１８中のプログラマブル接続のサイクル毎の遷移を示す概念図である。
【図２０】本発明の第３の実施の形態に係るプログラマブル・ロジック・デバイスの構造図である。
【図２１】図２０中の第３の並べ替えセルの内部構造を示したブロック図である。
【図２２】図２０のプログラマブル・ロジック・デバイスを用いて実現するアプリケーションの例である携帯電話のデジタルベースバンド処理のフロー図である。
【図２３】図２２中のインターリーブ処理の詳細を示した概念図である。
【図２４】図２３のインターリーブ処理を実現する際の第３の並べ替えセルの１サイクル目の動作を示した概念図である。
【図２５】図２３のインターリーブ処理を実現する際の第３の並べ替えセルの２サイクル目の動作を示した概念図である。
【図２６】演算エレメントのみを用いた場合のインターリーブ回路の構成例を示したブロック図である。
【図２７】本発明の第３の並べ替えセルを使用した場合のインターリーブ回路の構成例を示したブロック図である。
【発明を実施するための形態】
【００１６】
以下、本発明に関わるプログラマブル・ロジック・デバイスの実施の形態について、図面を用いて詳細に説明する。
【００１７】
《第１の実施の形態》
図１は、第１の実施の形態のプログラマブル・ロジック・デバイスを示した構造図である。図１において、プログラマブル・ロジック・デバイス１０１は内部に少なくとも４ビットの演算器と４ビットの配線スイッチと、４ビットの入出力とを持つ演算エレメント１０２と、演算エレメント１０２を１６個×１６個の正方形状に配置し、４ビット×１６個＝６４ビットの入出力を持つ演算エレメント群１０３と、演算エレメント群１０３に隣接して配置され、プログラムによって配線経路を変更することによって６４ビットの入力信号を任意の順番に並べ替えて６４ビット信号を出力し、かつ外部からの設定によって毎サイクル機能変更が可能な６４ビットの入出力を持つ制御回路を持つ第１の並べ替えセル１０４と、演算エレメント群１０３の６４ビット入力と第１の並べ替えセル１０４の６４ビット出力とを接続し、又は演算エレメント群１０３の６４ビット出力と第１の並べ替えセル１０４の６４ビット入力とを接続する配線１０５とを備える。
【００１８】
図２は、図１のプログラマブル・ロジック・デバイス１０１に搭載する第１の並べ替えセル１０４の内部構造を示した図である。第１の並べ替えセル１０４は、８ビット×８並列＝６４ビットのデータ入力２０１と、入力信号をクロック信号の立ち上がりエッジで取り込むフリップフロップ２０２と、外部からの設定入力２０３と、外部からの設定入力２０３を受けてアドレスを生成するアドレスカウンタ２０４と、セレクタを制御するための制御信号を読み出すメモリ２０５と、６４ビットのデータ入力２０１から任意の１ビットを選択する６４対１出力セレクタ２０６と、セレクタ２０６の出力信号をクロック信号の立ち上がりエッジで取り込むフリップフロップ２０７と、６４個のフリップフロップ２０７の出力信号からなる６４ビットのデータ出力２０８とからなる。
【００１９】
図２の構造を持つ第１の並べ替えセル１０４は、外部からの設定入力２０３を受けてアドレスを生成するアドレスカウンタ２０４と、セレクタを制御するための制御信号を読み出すメモリ２０５と、６４ビットのデータ入力２０１から任意の１ビットを選択する６４対１出力セレクタ２０６とを内蔵しているため、データのコピーや並べ替えといった演算を、１サイクルで実行することができる。これらの演算を、ＡＬＵ、シフタ等の演算器から構成される演算エレメント１０２を用いて実現する場合を考えると、各々のデータ演算に対して少なくとも１つの演算エレメント１０２を使用し、なおかつ算術等の演算を行わないにもかかわらず、演算器を使用する必要がある。したがって、図２の構成を持つ第１の並べ替えセル１０４を搭載するプログラマブル・ロジック・デバイス１０１を用いた場合は、ターゲットとするアプリケーションの信号処理のうち、データの並べ替え演算等を、第１の並べ替えセル１０４を用いて実現すれば、全ての信号処理を演算エレメント１０２を用いて実現する場合に比較して、効率良くアプリケーションの信号処理を実現することができる。
【００２０】
図３は、図１のプログラマブル・ロジック・デバイス１０１に搭載する演算エレメント１０２の詳しい構成を示したブロック図である。演算エレメント１０２は、コンフィギュレーションデータの設定によって複数の種類の演算が可能な４ビットの算術論理演算回路（ＡＬＵ）からなる演算ブロック２３０１と、ＡＬＵの４ビット出力値を保持するレジスタ２３０２と、演算エレメント１０２を外部又は別の演算エレメント１０２と接続するための配線２３０３と、配線２３０３とＡＬＵの４ビット入力とを接続し、また配線２３０３をＡＬＵの４ビット出力又はレジスタ２３０２の出力と接続するためのスイッチボックス（ＳＢ）２３０４と、演算ブロック２３０１の演算の種類や、スイッチボックス２３０４の接続状態を決定又は変更することを可能とするためのコンフィギュレーションデータを保持するコンフィギュレーションメモリ２３０５とを持つ。
【００２１】
以上のように構成された本実施の形態について、以下、その動作を説明する。図１、図２に記載のプログラマブル・ロジック・デバイス１０１を用いて実現するアプリケーションの例として、ＤＥＳ（Data Encryption Standard）方式の暗号回路を想定する。
【００２２】
図４は、ＤＥＳの暗号処理を記載したフロー図である。６４ビットの平文入力３０１に対して、初期転置３０２と呼ばれる１ビット単位での並べ替え処理を実施する。更に暗号化に用いる６４ビットの鍵入力３０３については、６４ビットから５６ビットへの転置３０４を実施したのち、上位と下位の２８ビットずつに分離し、シフト３０８の処理を実施する。更に２つの２８ビットのシフト結果は再び５６ビットに結合され、更に５６ビットから４８ビットへの転置処理３０５が実施される。初期転置３０２を行った６４ビットの平文入力は上位と下位の３２ビットに分けられ、下位の３２ビットと転置３０５の４８ビットの鍵データとはＦ関数３０６と呼ばれる関数に入力される。Ｆ関数３０６からは処理された３２ビットデータが出力され、初期転置３０２の６４ビット出力のうち上位３２ビットの出力と排他的論理和が算出される。これによって出力された上位の３２ビットのデータは、Ｆ関数３０６に入力された下位の３２ビットデータと上位下位を入れ替えられ、新たに２つ目のＦ関数３０６にて同様の処理がなされる。その際に、２つ目のＦ関数３０６に入力される鍵データは、更に上位２８ビットと下位２８ビットの鍵入力に対して更にシフト３０８を施したものに、５６ビットから４８ビットへの転置３０５を施したものである。
【００２３】
この処理を１６回繰り返して、最後に最終転置３０７と呼ばれるビットの並べ替え演算を行って、暗号化された６４ビットのデータとして出力される。
【００２４】
図５は、図４の暗号処理フロー図のうち、Ｆ関数３０６の演算の内部構造を示した図である。３２ビットの入力データは、３２ビットから４８ビットに拡張する転置４０１を実施した後、鍵の４８ビット入力との排他的論理和を算出する。４８ビットの排他的論理和の出力は、連続する６ビットが８個のグループに分けられ、それぞれの６ビットデータはＳｂｏｘ４０２と呼ばれる演算を実施する。Ｓｂｏｘ４０２は６ビット入力を４ビット出力に変換する。Ｓｂｏｘ４０２の処理を終えた８個の４ビット出力は、３２ビットの信号に再び結合され、３２ビットの信号を並べ替える転置４０３の処理を施し、３２ビットデータとして出力される。本実施形態で想定する暗号化処理においては、秘匿性の向上のために、３０２、３０４、３０５、３０７、４０１、４０３の転置の処理において、毎サイクル並び替えの処理を変更することを想定する。
【００２５】
図６は、図４、図５で示した暗号処理の処理フローを実際の回路で実装する場合の実装概略図である。図４の６４ビットの平文入力３０１は、図６では平文入力５０１に対応する。図４の初期転置３０２は、図６では初期転置回路５０２に対応する。初期転置回路５０２の出力は、入力データセレクタ５０３に入力される。図５の３２ビットから４８ビットに拡張する転置４０１は、図６では転置回路５０４に対応する。また、図５の排他的論理和は、図６では排他的論理和回路５０５に対応する。図５のＳｂｏｘ４０２は、図６ではＳｂｏｘ回路５０６に対応する。図５の３２ビットの信号を並べ替える転置４０３は、図６では転置回路５０７に対応する。図４の上位３２ビットの出力とＦ関数３０６の３２ビット出力との排他的論理和は、図６の排他的論理和回路５０８に対応する。図４の最終転置３０７は、最終転置回路５０９に対応する。
【００２６】
更に、図４の６４ビット鍵入力３０３は、図６では６４ビット鍵入力５１０に対応する。図４の６４ビットから５６ビットへの転置３０４は、図６では転置回路５１１に対応する。転置回路５１１の出力は、入力データセレクタ５１２に入力される。更に入力データセレクタ５１２の出力は、シフト回路５１３に入力される。シフト回路５１３は、図４のシフト３０８に対応する。図４の５６ビットから４８ビットへの転置３０５は、図６では転置回路５１４に対応する。
【００２７】
次に、図６のＤＥＳ回路を図１のプログラマブル・ロジック・デバイス１０１を用いて実現する場合の回路のマッピングの例を説明する。マッピングの考え方としては、図６のＤＥＳ回路のうち、転置を行う回路においては、入力信号のビットの並び替えは、演算エレメント１０２を用いた場合は面積が非常に大きくなるため、第１の並べ替えセル１０４を使用することとし、これ以外の回路に関しては、演算エレメント１０２を使用するという考え方とする。なお、転置を行う回路を、演算エレメント１０２を用いずに第１の並べ替えセル１０４を用いて実現した場合にどの程度回路面積が削減できるかについては、後述する。
【００２８】
図６の初期転置回路５０２は、第１の並べ替えセル１０４を使用する。ここに使用する第１の並べ替えセル１０４を並べ替えセル（１）と呼ぶ。図６の初期転置回路５０２は６４ビット入力・６４ビット出力であるので、第１の並べ替えセル１０４の６４ビット入出力をフルに使用する。
【００２９】
次に、入力データセレクタ５０３は演算エレメント１０２を使用する。演算エレメント１０２は４ビットの入出力を持つことから、３２ビット×２の入出力を持つ入力データセレクタ５０３を実現するためには、６４／４＝１６個の演算エレメント１０２が必要となる。ここで使用する演算エレメント群を演算エレメント群（１）と呼ぶ。
【００３０】
図６の転置回路５０４は第１の並べ替えセル１０４を使用する。ここに使用する並べ替えセルを並べ替えセル（３）と呼ぶ。図６の転置回路５０４は３２ビット入力・４８ビット出力であるため、第１の並べ替えセル１０４の６４ビット入出力のうち必要なビット数のみ使用し、残りのビットに関しては未使用とする。図６の排他的論理和回路５０５は、演算エレメント１０２を使用する。図６の排他的論理和回路５０５は４８ビット入出力を持つため、４８／４＝１２個の演算エレメント１０２が必要となる。ここで使用する演算エレメント群を演算エレメント群（２）と呼ぶ。図６ではＳｂｏｘ回路５０６は、同様に演算エレメント１０２を使用する。１つのＳｂｏｘ回路５０６は８個の演算エレメント１０２が必要であると仮定すると、８個のＳｂｏｘ回路５０６を実現するためには６４個の演算エレメント１０２が必要となる。ここで使用する演算エレメント群を演算エレメント群（３）と呼ぶ。図６の転置回路５０７は第１の並べ替えセル１０４を使用する。ここに使用する並べ替えセルを並べ替えセル（４）と呼ぶ。図６の転置回路５０７は３２ビット入出力であるため、第１の並べ替えセル１０４のうち半数の入出力を使用し、残りのビット数に関しては未使用とする。図６の排他的論理和回路５０８は、演算エレメント１０２を使用する。図６の排他的論理和回路５０８は３２ビットの入出力を持つため、３２／４＝８個の演算エレメント１０２を使用する。ここで使用する演算エレメント群を演算エレメント群（４）と呼ぶ。図６の最終転置回路５０９は第１の並べ替えセル１０４を使用する。ここに使用する並べ替えセルを並べ替えセル（６）と呼ぶ。図６の最終転置回路５０９は６４ビットの入出力を使用するので、第１の並べ替えセル１０４の６４ビット入出力をフルに使用する。
【００３１】
更に、図６の転置回路５１１は第１の並べ替えセル１０４を使用する。ここに使用する並べ替えセルを並べ替えセル（５）と呼ぶ。図６の転置回路５１１は６４ビット入力と５６ビット出力とを持つため、出力の８ビットは未使用となる。また図６の入力データセレクタ５１２は演算エレメント１０２を使用する。図６の入力データセレクタ５１２は２８ビット×２の入出力を持つため、４ビットの入出力を持つ演算エレメント１０２は５６／４＝１４個必要となる。ここで使用する演算エレメント群を演算エレメント群（５）と呼ぶ。更に図６のシフト回路５１３は演算エレメント１０２を使用する。シフト回路５１３は２８ビット×２の入出力を持つため、４ビットの入出力を持つ演算エレメント１０２は５６／４＝１４個必要となる。ここで使用する演算エレメント群を演算エレメント群（６）と呼ぶ。更に、図６の５６ビットから４８ビットへの転置回路５１４は第１の並べ替えセル１０４を使用する。ここに使用する並べ替えセルを並べ替えセル（２）と呼ぶ。転置回路５１４は５６ビット入力・４８ビット出力を持つため、第１の並べ替えセル１０４の６４ビット入出力のうち必要なビット数のみ使用し、残りのビットに関しては未使用とする。
【００３２】
図７に、図１のプログラマブル・ロジック・デバイス１０１を用いた場合のＤＥＳ回路の実現方法に関して、実際のマッピング例を示す。並べ替えセル（１）は図７の左の列の演算エレメント群１０３の一番上の第１の並べ替えセル１０４を使用する（図７において、並べ替えセル（１）の記載がある箇所）。当該の並べ替えセル（１）はその６４ビット入力がプログラマブル・ロジック・デバイス１０１の上辺のＩＯ部に接続しているため、この上辺のＩＯ部を経由して、プログラマブル・ロジック・デバイス１０１の外部から６４ビットの平文を入力することができる。更に並べ替えセル（１）は、６４ビットの平文入力をもとに、外部からの設定によって、初期転置回路５０２として動作し、６４ビット信号の出力を行う。
【００３３】
次に、演算エレメント群（１）は、図７の左の列の演算エレメント群１０３のうち、一番上の演算エレメント群１０３を使用してマッピングする（図７において、演算エレメント群（１）の記載がある箇所）。演算エレメント群（１）は、配線１０５を経由して、並べ替えセル（１）からの６４ビット出力信号を入力として、外部からの設定によって入力データセレクタ５０３として動作し、上位と下位の３２ビット出力信号を出力する。
【００３４】
次に、並べ替えセル（３）は、図７の左の列の演算エレメント群１０３のうち、一番上の演算エレメント群とその次の演算エレメント群との間にある第１の並べ替えセル１０４を使用する（図７において、並べ替えセル（３）の記載がある箇所）。並べ替えセル（３）は配線１０５を経由して、演算エレメント群（１）の下位の３２ビット出力を入力として、外部からの設定によって、転置回路５０４として動作し、４８ビットの出力信号を出力する。
【００３５】
一方、並べ替えセル（５）は図７の右の列の演算エレメント群１０３の一番上から２番目の演算エレメント群の右隣にある並べ替えセルを使用する（図７において、並べ替えセル（５）の記載がある箇所）。当該の並べ替えセル（５）はその６４ビット入力がプログラマブル・ロジック・デバイス１０１の右辺のＩＯ部に接続しているため、この右辺のＩＯ部を経由して、プログラマブル・ロジック・デバイス１０１の外部から６４ビットの鍵データを入力することができる。更に並べ替えセル（５）は、６４ビットの鍵入力をもとに、外部からの設定によって、転置回路５１１として動作し、上位と下位の２８ビット信号の出力を行う。
【００３６】
次に、演算エレメント群（５）と演算エレメント群（６）は図７の右の列の演算エレメント群のうち、上から２番目の演算エレメント群を使用してマッピングする（図７において、演算エレメント群（５）（６）の記載がある箇所）。この演算エレメント群は、配線１０５を経由して、並べ替えセル（５）からの上位と下位の２８ビット出力信号を入力として、外部からの設定によって入力データセレクタ５１２とシフト回路５１３として動作し、上位と下位の２８ビットを出力する。
【００３７】
次に、並べ替えセル（２）は図７の右の列の演算エレメント群の一番上から２番目の演算エレメント群の左隣にある並べ替えセルを使用する（図７において、並べ替えセル（２）の記載がある箇所）。当該の並べ替えセル（２）は、配線１０５を経由して演算エレメント群（５）（６）からの上位と下位の２８ビット出力を入力として、外部からの設定によって、転置回路５１４として動作し、４８ビット信号の出力を行う。
【００３８】
次に、演算エレメント群（２）と演算エレメント群（３）は図７の左の列の演算エレメント群のうち、上から２番目の演算エレメント群を使用してマッピングする（図７において、演算エレメント群（２）（３）の記載がある箇所）。この演算エレメント群は、配線１０５を経由して、並べ替えセル（３）からの４８ビット出力信号と、配線１０５を経由して、並べ替えセル（２）からの４８ビット出力信号とを入力として、外部からの設定によって排他的論理和回路５０５と、Ｓｂｏｘ回路５０６として動作し、３２ビット出力信号を出力する。
【００３９】
次に、並べ替えセル（４）は図７の右の列の演算エレメント群の一番上から２番目の演算エレメント群と上から３番目の演算エレメント群との間にある並べ替えセルを使用する（図７において、並べ替えセル（４）の記載がある箇所）。当該の並べ替えセル（４）は、配線１０５を経由して演算エレメント群（２）（３）からの３２ビット出力を入力として、外部からの設定によって、転置回路５０７として動作し、３２ビット信号の出力を行う。
【００４０】
次に、演算エレメント群（４）は、図７の左の列の演算エレメント群のうち、上から３番目の演算エレメント群を使用してマッピングする（図７において、演算エレメント群（４）の記載がある箇所）。演算エレメント群（４）は、配線１０５を経由して、並べ替えセル（４）からの３２ビット出力信号を入力として、外部からの設定によって排他的論理和回路５０８として動作し、３２ビット出力信号を出力する。
【００４１】
最後に、並べ替えセル（６）は図７の左の列の演算エレメント群の一番上から３番目の演算エレメント群の下にある並べ替えセルを使用する（図７において、並べ替えセル（６）の記載がある箇所）。当該の並べ替えセル（６）は、配線１０５を経由して、演算エレメント群（４）の３２ビット出力信号と、プログラマブル・ロジック・デバイス１０１の配線ネットワーク（図示せず）を経由して、演算エレメント群（１）の下位３２ビット出力信号を入力として、外部からの設定によって最終転置回路５０９として動作し、６４ビット出力信号を出力する。更に並べ替えセル（６）はその６４ビット出力がプログラマブル・ロジック・デバイス１０１の下辺のＩＯ部に接続しているため、この下辺のＩＯ部を経由して、プログラマブル・ロジック・デバイス１０１の外部に６４ビットの暗号化されたデータを出力することができる。
【００４２】
以上が、図１、図２に記載のプログラマブル・ロジック・デバイス１０１を用いてＤＥＳ方式の暗号回路を実現した場合の実施形態であるが、ここで、図１、図２に記載のプログラマブル・ロジック・デバイス１０１の第１の並べ替えセル１０４を６４ビットの入出力構成とした理由を説明する。まず、ＤＥＳ処理は図４、図５に示すとおり、最大６４ビットを単位とした転置と呼ばれる並べ替え演算が多数存在する。これらの転置の処理を並べ替えセルを用いて実現すると仮定すると、並べ替えセルの入出力ビット数が６４ビットより少ない場合、ＤＥＳの転置処理に必要な６４ビットのランダムな並べ替えが実現できないので、並べ替えセルを用いた並べ替え演算は不可能である。したがって、並べ替え演算は、演算エレメント又は配線ネットワーク（図示せず）を使用する必要がある。
【００４３】
一方、並べ替えセルの入出力ビット数が６４ビットより多い場合は、ＤＥＳの転置処理に必要なビット幅は６４ビットであり、ＤＥＳの処理においては、６４ビットより多いビット数の処理は存在しないため、並べ替えセルの入出力のうち６４ビット分しか使用せず、余剰分は遊びとなり、チップ面積の観点で無駄が生じる。
【００４４】
また、暗号の処理として、新しい方式であるＡＥＳ（Advanced Encryption Standard）の処理を考慮した場合、ＡＥＳでは１２８ビットの並べ替え演算が存在する。しかしながら、実際のＡＥＳの処理では、１２８ビットは４つの３２ビット処理に分割されており、並べ替え演算は３２ビット内で閉じている。したがってＡＥＳの並べ替え演算を並べ替えセルで実現することを考慮した場合、並べ替えセルの入出力信号のビット幅は３２ビット、６４ビット、１２８ビットのうちのいずれかであれば、効率的に処理を行うことができる。
【００４５】
以上の内容を考慮すると、図１、図２に記載のプログラマブル・ロジック・デバイス１０１の第１の並べ替えセル１０４は６４ビットの入出力を持つ構成にすることが最適であると言うことができる。
【００４６】
また、図１、図２に記載のプログラマブル・ロジック・デバイス１０１の演算エレメント群１０３を、演算エレメント１０２を縦方向１６個×横方向１６個配置する構成とした理由を説明する。第１の並べ替えセル１０４は上記の理由で６４ビットの入出力を持つ構成としている。この６４ビットの入出力を演算エレメント群１０３の入出力と接続する構成を考慮すると、１つの演算エレメント１０２の処理ビット数及び入出力ビット数は４ビットのため、６４ビット／４ビット＝１６個の演算エレメント１０２が必要である。このように、演算エレメント群１０３の一辺に１６個の演算エレメント１０２を配置し、正方形状の配置とすることにより、演算エレメント群１０３からの６４ビット入出力を全て第１の並べ替えセル１０４に接続できる構成とすることで、演算エレメント１０２の入出力信号に無駄を生じさせない構成とすることができる。第１の並べ替えセル１０４に接続する演算エレメント１０２の数が１６個より少ないと、第１の並べ替えセル１０４の入出力端子に余剰のピンを生じるため、適さない。また、１６個より多いと、第１の並べ替えセル１０４に接続できない演算エレメント１０２が存在し、この演算エレメント１０２は動作させられず、無駄となる。したがって、演算エレメント群１０３の一辺の演算エレメント１０２の個数は１６個が最適な数となる。
【００４７】
更に、図６に示したＤＥＳの６４ビットの転置を行う回路を、演算エレメント１０２を用いずに第１の並べ替えセル１０４を用いて実現した場合にどの程度回路面積が削減できるかについて説明する。転置回路を、第１の並べ替えセル１０４を配置しない従来のプログラマブル・ロジック・デバイスを用いた場合に必要な演算エレメント１０２の数を、図８を使って説明する。演算エレメントは４ビット単位での処理を実施するので、６４ビットを４ビットずつ１６個の処理に分割する。４ビットから１ビットを抽出するために、図８に示すとおり、４ビットのうち、所定の１ビットのみ“１”で、その他のビットが“０”である定数を入力し、演算エレメントでＡＮＤの演算を行う。これを１ビットから３ビットの間でシフトする回路を生成する。１ビットのシフト演算は、同じデータを足し合わせる演算によって実現するので、図８に示すように、シフトするビット数分、演算エレメントを用いて自身の値の足し算を行う。その後、１ビットから３ビットの間でシフトを行ったデータのうち、所望のデータを選択する。この際にも、演算エレメントをマルチプレクサとして使用する。以上の構成により、１ビットの並べ替えに９個の演算エレメントを使用する。このようにして作成した１ビットシフト結果を、ＯＲ演算により４ビット分を合成して４ビットの出力データを作成する。４ビット分のデータの合成には、３つの演算エレメントを用いてＯＲ演算を実施する。
【００４８】
したがって、必要となる演算エレメントは全部で９個×６４ビット＋３個×（６４／４）＝６２４個となる。演算エレメントの回路を論理合成で作成し、ゲート数の見積もりを行ったところ、約１６０ゲートであったため、６２４×１６０＝９９８４０ゲートとなる。
【００４９】
一方、第１の並べ替えセル１０４を用いた場合に関しては、図９に示すとおり、第１の並べ替えセル１０４を１個使用することで実現できる。図２の構造を持つ第１の並べ替えセル１０４のゲート数は、３ゲートを有する２対１セレクタでの実現を考慮した場合、（６４−１）×６４＝４０３２個必要となる。したがってゲート数は、３×４０３２＝１２０９６ゲートとなる。これを演算エレメントのみで実現した場合と比較すると、約１／８のゲート数に削減していることが分かる。
【００５０】
以上のように、本実施の形態によれば、暗号処理を、第１の実施の形態のプログラマブル・ロジック・デバイス１０１を用いて実現することによって、アプリケーション内の算術演算を必要とする処理に関しては演算エレメント１０２を用いて実現し、暗号処理のデータの１ビット単位での並べ替えのような処理は第１の並べ替えセル１０４を用いて実現することにより、並べ替えの仕方を毎サイクル変更することでより秘匿性が高い暗号処理を実現することができ、更に暗号処理を効率良く本発明のプログラマブル・ロジック・デバイス１０１上で実現することができる。
【００５１】
《第２の実施の形態》
図１０及び図１１は、第２の実施の形態のプログラマブル・ロジック・デバイスを示した構造図である。図１０及び図１１において、プログラマブル・ロジック・デバイス１００１は内部に少なくとも４ビットの演算器と４ビットの配線スイッチと、４ビットの入出力とを持つ演算エレメント１０２と、演算エレメント１０２を１６個×１６個の正方形状に配置し、４ビット×１６個＝６４ビットの入出力を持つ演算エレメント群１０３と、演算エレメント群１０３に隣接して配置され、６４ビットの入力信号のうち連続する８ビットの信号を１つのグループとして８個のグループに分け、プログラムによって配線経路を変更することによって８個の８ビット信号グループを任意の順番に並び替えて６４ビットの出力信号を生成し、かつ外部からの設定によって毎サイクル機能変更が可能な６４ビットの入出力を持つ制御回路を持つ第２の並べ替えセル１００２と、演算エレメント群１０３の６４ビット入力と第２の並べ替えセル１００２の６４ビット出力とを接続し、又は演算エレメント群１０３の６４ビット出力と第２の並べ替えセル１００２の６４ビット入力とを接続する配線１０５とを備える。第２の並べ替えセル１００２の配置については、図１０に示すように、演算エレメント群１０３の行と隣接する演算エレメント群１０３の行との間に、行方向に配置する場合でもよく、また図１１に示すように、演算エレメント群１０３の列と隣接する演算エレメント群１０３の列との間に、列方向に配置する場合でもよい。また図示はしていないが、行方向と列方向の両方に配置してもよい。
【００５２】
図１２は、図１０及び図１１のプログラマブル・ロジック・デバイス１００１に搭載する第２の並べ替えセル１００２の内部構造を示した図である。第２の並べ替えセル１００２は、８ビット×８並列＝６４ビットのデータ入力１１０１と、入力信号をクロック信号の立ち上がりエッジで取り込むフリップフロップ１１０２と、外部からの設定入力１１０３と、外部からの設定入力１１０３を受けてアドレスを生成するアドレスカウンタ１１０４と、セレクタを制御するための制御信号を読み出すメモリ１１０５と、図１２に示すように入力６４ビットのうち、連続する８ビットを１つのデータグループとして、８個のデータグループに分割した場合、８個のデータグループの中から任意の１つのデータグループを選択する８対１出力セレクタ１１０６と、セレクタ１１０６の出力信号をクロック信号の立ち上がりエッジで取り込むフリップフロップ１１０７と、６４個のフリップフロップ１１０７の出力信号からなる６４ビットのデータ出力１１０８とからなる。
【００５３】
図１２の構造を持つ第２の並べ替えセル１００２は、外部からの設定入力１１０３を受けてアドレスを生成するアドレスカウンタ１１０４と、セレクタを制御するための制御信号を読み出すメモリ１１０５と、８個のデータグループの中から任意の１つのデータグループを選択する８対１出力セレクタ１１０６とを内蔵しているため、データのコピーや並べ替えといった演算を、１サイクルで実行することができる。これらの演算を、ＡＬＵ、シフタ等の演算器から構成される演算エレメント１０２を用いて実現する場合を考えると、各々のデータ演算に対して少なくとも１つの演算エレメント１０２を使用し、なおかつ算術等の演算を行わないにもかかわらず、演算器を使用する必要がある。したがって、図１２の構成を持つ第２の並べ替えセル１００２を搭載するプログラマブル・ロジック・デバイス１００１を用いた場合は、ターゲットとするアプリケーションの信号処理のうち、データの並べ替え演算等を、第２の並べ替えセル１００２を用いて実現すれば、全ての信号処理を演算エレメント１０２を用いて実現する場合に比較して、効率良くアプリケーションの信号処理を実現することができる。
【００５４】
以上のように構成された本実施の形態について、以下、その動作を説明する。図１０、図１１、図１２に記載のプログラマブル・ロジック・デバイス１００１を用いて実現するアプリケーションの例として、Ｈ．２６４動画像のエンコード処理を想定する。
【００５５】
図１３及び図１４（ａ）〜図１４（ｃ）は、Ｈ．２６４の処理の概要を示した図面である。入力画像のマクロブロック１２０１は縦８画素×横８画素の６４個の画素からなり、１画素当たりのビット精度は８ビットである。入力画像のマクロブロック１２０１に対する信号処理として、画像データのサイズを圧縮するため、あるマクロブロックを予測するための予測画像生成回路１２０２、予測したマクロブロックと実際の画像データのマクロブロックとの差分値の生成回路１２０３、更にその差分値に対する直交変換回路１２０４、量子化回路１２０５等の処理を実施する。
【００５６】
このうち、画素の数に対応してマトリックス状に多数かつ並列に算術演算を必要とする直交変換回路１２０４や、予測したマクロブロックと実際の画像データのマクロブロックとの差分値の生成回路１２０３に対しては、演算エレメント１０２を多数使用して実現することで、データ演算を並列に効率的に実行することができる。
【００５７】
一方、予測画像生成回路１２０２は、既に信号処理の終わった、現在のマクロブロックよりも以前のマクロブロックデータのうち、現在のマクロブロックに隣接する行又は列のデータを使用し、これを単純にコピー、又は並べ替えてコピーしながらマクロブロック内を埋めることによって予測画像を生成する処理を行う。これらの並べ替えの方法は、データ圧縮を効率的に実現するために、入力された画像の特徴によって複数の方法（以下、予測モードと呼ぶ）が存在する。したがって、処理対象のマクロブロックに対して最適な予測画像を決定するため、一旦全ての予測モードで生成した予測画像を準備する必要がある。
【００５８】
予測画像生成回路１２０２に関して、図１４（ａ）〜図１４（ｃ）を用いて説明する。図１４（ａ）の予測モード０においては、近接のマクロブロックの１列又は１行をそのままコピーしてマクロブロックを埋める。図１４（ｂ）の予測モード１においては、近接のマクロブロックの１列又は１行を、マクロブロックを１行埋めるごとに画素を一個ずつずらしてマクロブロックを埋めていく。図１４（ｃ）の予測モード２においては、近接のマクロブロックの１列又は１行を平均して、これをコピーしてマクロブロックを埋める。したがって、予測画像生成回路１２０２を実現するためには、演算エレメント１０２ではなく、第２の並べ替えセル１００２を用いた方が、より良い面積効率で処理を実現することができる。理由については後述する。
【００５９】
ここで、図１０、図１１、図１２に記載のプログラマブル・ロジック・デバイス１００１の第２の並べ替えセル１００２を６４ビットの入出力構成とした理由を説明する。予測画像生成回路１２０２は８ビットの画像データを８画素分並列に処理を実施するため、第２の並べ替えセル１００２に必要な入出力の構成としては、図１２に示した８ビット×８並列入力＝６４ビットの構成となる。第２の並べ替えセル１００２の入出力ビット数が６４ビットより少ない場合、予測画像生成に必要な８ビット×８画素分の並べ替え処理が実現できないので、第２の並べ替えセル１００２を用いた並べ替え処理は不可能である。したがって、並べ替え処理は、演算エレメント又は配線ネットワーク（図示せず）を使用する必要がある。
【００６０】
一方、第２の並べ替えセル１００２の入出力ビット数が６４ビットより多い場合は、予測画像生成に必要なビット幅は８ビット×８画素分＝６４ビットであり、予測画像生成処理においては、６４ビットより多いビット数の処理は存在しないため、並べ替えセルの入出力のうち６４ビット分しか使用せず、余剰分は遊びとなり、チップ面積の観点で無駄が生じる。
【００６１】
以上の内容を考慮すると、図１０、図１１、図１２に記載のプログラマブル・ロジック・デバイス１００１の第２の並べ替えセル１００２は６４ビットの入出力を持つ構成にすることが最適であると言うことができる。
【００６２】
また、図１０、図１１、図１２に記載のプログラマブル・ロジック・デバイス１００１の演算エレメント群１０３を、演算エレメント１０２を縦方向１６個×横方向１６個配置する構成とした理由を説明する。第２の並べ替えセル１００２は上記の理由で６４ビットの入出力を持つ構成としている。この６４ビットの入出力を演算エレメント群１０３の入出力と接続する構成を考慮すると、１つの演算エレメント１０２の処理ビット数及び入出力ビット数は４ビットのため、６４ビット／４ビット＝１６個の演算エレメント１０２が必要である。このように、演算エレメント群１０３の一辺に１６個の演算エレメント１０２を配置し、正方形状の配置とすることにより、演算エレメント群１０３からの６４ビット入出力を全て第２の並べ替えセル１００２に接続できる構成とすることで、演算エレメント１０２の入出力信号に無駄を生じさせない構成とすることができる。第２の並べ替えセル１００２に接続する演算エレメント１０２の数が１６個より少ないと、第２の並べ替えセル１００２の入出力端子に余剰のピンを生じるため、適さない。また、１６個より多いと、第２の並べ替えセル１００２に接続できない演算エレメントが存在し、この演算エレメント１０２は動作させられず、無駄となる。したがって、演算エレメント群１０３の一辺の演算エレメント１０２の個数は１６個が最適な数となる。
【００６３】
ここで、予測画像生成回路１２０２を実現するに当たって、演算エレメント１０２ではなく、第２の並べ替えセル１００２を用いた方が、より良い面積効率で実現できる理由を説明する。図１４（ｂ）に示した予測画像生成の予測モード１の処理に関して、第２の並べ替えセル１００２を配置しない従来のプログラマブル・ロジック・デバイスを用いた場合に必要な演算エレメント１０２の数を、図１５を使って説明する。予測モード１では８ビットの任意の画素の中から１つの画素を選んで出力するため、演算エレメントはセレクタとして使用する（図中のＭＵＸ）。８画素の入力の中から任意の１つの画素を選び出すため、演算エレメントは図１５に示すとおり、全部で７個必要となる。同様の回路を、８個並列に持つ必要がある。また、演算エレメントの入力ビット数は４ビットのため、８ビットの画素処理を実行するためには、上記の回路をもう一組用意する必要がある。したがって、全部で必要な演算エレメントの数は、７×８×２＝１１２個となる。演算エレメントを論理合成で作成し、ゲート数の見積もりを行ったところ、約１６０ゲートであったため、この並べ替え処理に必要なゲート数は、１６０×１１２＝１７９２０個となる。
【００６４】
一方、第２の並べ替えセル１００２を用いた場合に関しては、図１６に示すとおり、図１２の第２の並べ替えセル１００２を１つ使用することで実現できる。第２の並べ替えセル１００２の動作に関しては図１７（ａ）〜図１７（ｄ）に示すとおり、１サイクル目ではデータの並び替えを実施せずに出力する。２サイクル目では、１画素分をずらして出力を実施する。以降、１サイクル毎に１画素分のデータをずらして出力してゆく。第２の並べ替えセル１００２のゲート数は、３ゲートを有するセレクタで実現した場合、（８−１）×６４＝４４８個必要となる。したがってゲート数は、３×４４８＝１３４４ゲートとなる。これを従来の演算エレメントで実現した場合と比較すると、約１／１０のゲート数に削減していることが分かる。
【００６５】
以上のように、本実施の形態によれば、Ｈ．２６４画像処理を、第２の実施の形態のプログラマブル・ロジック・デバイス１００１を用いて実現することによって、アプリケーション内の算術演算を必要とする処理に関しては演算エレメント１０２を用いて実現し、データのコピーや並べ替えのような信号処理は第２の並べ替えセル１００２を用いて実現することにより、Ｈ．２６４画像処理全体を効率良く本発明のプログラマブル・ロジック・デバイス１００１上で実現することができる。
【００６６】
更に、図１０、図１１、図１２に記載のプログラマブル・ロジック・デバイス１００１を用いて実現するアプリケーションの例として、画像認識の人物検出処理を想定する。
【００６７】
図１８及び図１９（ａ）〜図１９（ｃ）は、画像認識の人物検出処理の概要を示した図面である。入力画像のマクロブロックは縦８画素×横８画素の６４個の画素からなり、１画素当たりのビット精度は８ビットである。この入力画像は、ＨｏＧ（Histgram of Gradient）と呼ばれる方式によって、特徴量の算出が行われる。特徴量の算出の演算は、ある画素を基準として、それに縦方向又は横方向に隣接する画素との輝度の差分を算出し、この差分値に対して、予め求められた画像認識の学習結果に基づく係数を乗じ、隣接する数画素分の値を合計する処理である。ゆえに、特徴量算出においては、算術演算を多数実施する。特徴量算出はマクロブロックの１ライン分が並列に算出され、全体として１つのマクロブロック分の画像データは６４個の特徴量×８カラム分の特徴量データとなる。なお、１つの特徴量データは、８ビット精度の画素を入力として演算を行うため、ビット精度が途中で増減するが、最終的にクリッピング又は伸長の処理を実施して、再び８ビット精度のデータに変換される。
【００６８】
特徴量算出を行ったあと、識別器によってそれぞれの特徴量に対して、画像が人物か否かの判定を行うため、相関計算が実施される。ここでは、６４個の識別器が存在するものとする。なお、識別器の数は、必要とする検出精度に応じて多くても少なくしてもよい。この識別器による相関計算は、１カラム分の６４個の特徴量に関して並列に実行される。
【００６９】
一方、特徴量の算出はマクロブロックの行方向に実施されるため、特徴量の算出結果は８カラム×６４個の特徴量保持レジスタに一旦保持して、特徴量算出による特徴量保持レジスタへのデータ書き込みが完了したのち、識別器による相関計算を開始する必要がある。識別器による相関計算は、特徴量保持レジスタの８つのカラムのうち、１サイクル毎に選択するカラムを変更して、識別器による相関計算を実施する。図１８中の特徴量保持レジスタでは、カラム４が選択されている場合を想定して、カラム４を太線で囲んでいる。
【００７０】
ここで、識別器で相関計算を実施する際に、特徴量保持レジスタのあるカラムの６４の特徴量データのうち、どの特徴量を参照して相関計算を行うかは、選択するカラムに依存して異なる。これについて、図１９（ａ）〜図１９（ｃ）を用いて説明する。まず相関計算の１サイクル目、すなわちカラム０を選択している場合は、図１９（ａ）に示したような接続状態（すなわち参照状態）となる。次のサイクル、すなわちカラム１を選択している場合は、図１９（ｂ）に示したような接続状態（すなわち参照状態）に変更される。このとき、図１９（ｂ）の接続状態のように１つの特徴量が複数の識別器に参照されるような状態もありうる。このように１サイクル毎に選択されるカラムが変更されるに当たって、毎サイクル接続状態が変更されて行き、８サイクル目の接続状態（図１９（ｃ）参照）まで変更され、識別器による相関計算が完了した際に、特徴量保持レジスタに蓄えられた８カラム×６４個分の特徴量に対する相関計算が完了する。このあとは、また新たなマクロブロックによる特徴量の算出が開始される。以上が画像認識の人物検出処理の概要である。
【００７１】
また、画像認識アプリケーションに関しては認識率の向上や誤検出率の低下等の改善が日々なされており、ＬＳＩ開発後にも改善が可能であることが望ましい。そこで、本画像認識の人物検出処理においては、学習結果をＬＳＩ開発後も更新できる構成とする。そのためには、学習結果に応じて識別器と特徴量保持レジスタとの接続をプログラムによって変更可能としておくことが必要である。
【００７２】
以上の要件を満たすため、図１８及び図１９（ａ）〜図１９（ｃ）に示した画像認識の人物検出処理を図１０、図１１、図１２に示した本発明のプログラマブル・ロジック・デバイスを用いて実現することを検討する。まず、図１８の特徴量算出の処理は多数の算術演算を持つことから、演算エレメント１０２を用いて実現する。次に、特徴量保持レジスタとカラム選択用のセレクタも演算エレメント１０２を用いて実現する。一方、８ビット８並列の入出力を持つ８個のプログラマブル接続に関しては、図１９（ａ）〜図１９（ｃ）に示したとおり毎サイクル接続状態を変更する必要があり、また学習結果の更新によっても接続状態を変更する必要があるため、図１１に記載の第２の並べ替えセル１００２を８個用いて実現する。更に後段の識別器に関しては、８個の識別器を一組として、１つの演算エレメント群１０３を用いて実現する。したがって、識別器は全部で６４個存在するため、識別器の処理として使用する演算エレメント群１０３は８個となる。この８個の演算エレメント群１０３は、図１１において、第２の並べ替えセル１００２に対して右側の演算エレメント群１０３を使用することによって、第２の並べ替えセル１００２を８個用いて実現する８個のプログラマブル配線からの出力を直接演算エレメント群１０３で受け取ることができ、チップ面積の観点で効率良く人物検出処理を実現することができる。また同様に、図１８の特徴量算出、特徴量保持レジスタ、及びカラム選択用のセレクタは、図１１において、第２の並べ替えセル１００２に対して左側の演算エレメント群１０３を使用することによって、演算エレメント群１０３の出力を直接、第２の並べ替えセル１００２を８個用いて実現する８個のプログラマブル配線に渡すことができ、チップ面積の観点で効率良く人物検出処理を実現することができる。なお、図１８のプログラマブル配線に関しては、演算エレメント１０２ではなく第２の並べ替えセル１００２を使用して実現した方が、より良い面積効率で処理を実現することができる。この理由は、Ｈ．２６４動画像のエンコード処理を想定した場合の説明内容と同じである。
【００７３】
《第３の実施の形態》
図２０は、第３の実施の形態のプログラマブル・ロジック・デバイス１６０１を示した構造図である。図２０において、プログラマブル・ロジック・デバイス１６０１は、内部に少なくとも４ビットの演算器と４ビットの配線スイッチと、４ビットの入出力とを持つ演算エレメント１０２と、演算エレメント１０２を１６個×１６個の正方形状に配置し、４ビット×１６個＝６４ビットの入出力を持つ演算エレメント群１０３と、更に複数の演算エレメント群１０３とＩＯ部との間に配置され、１２８ビットの入力信号のうち連続する８ビットの信号を１つのグループとして１６個のグループに分け、プログラムによって配線経路を変更することによって１６個の８ビット信号グループのうち偶数番目又は奇数番目の８ビット信号グループを選択して出力６４ビットの出力信号を生成し、かつ外部からの設定によって毎サイクル機能変更が可能な制御回路を持つ第３の並べ替えセル１６０２と、演算エレメント群１０３の６４ビット入力と第３の並べ替えセル１６０２の６４ビット出力とを接続し、第３の並べ替えセル１６０２の１２８ビット入力とＩＯ部とを接続する配線１０５とを備える。第３の並べ替えセル１６０２の配置については、図２０に示すように、演算エレメント群１０３とＩＯ部との間の一部の箇所に配置していてもよいし、全ての箇所に配置していてもよい。
【００７４】
図２１は、図２０のプログラマブル・ロジック・デバイス１６０１に搭載する第３の並べ替えセル１６０２の内部構造を示した図である。第３の並べ替えセル１６０２は、８ビット×１６並列＝１２８ビットのデータ入力１７０１と、入力信号をクロック信号の立ち上がりエッジで取り込むフリップフロップ１７０２と、外部からの設定入力１７０３と、外部からの設定入力１７０３を受けてアドレスを生成するアドレスカウンタ１７０４と、セレクタを制御するための制御信号を読み出すメモリ１７０５と、図２１に示すように入力１２８ビットのうち、連続する８ビットを１つのデータグループとして、１６個のデータグループに分割した場合、１６個のデータグループの中から隣接する奇数番目と偶数番目のデータグループを選択する２対１出力セレクタ１７０６と、セレクタ１７０６の出力信号をクロック信号の立ち上がりエッジで取り込むフリップフロップ１７０７と、６４個のフリップフロップ１７０７の出力信号からなる６４ビットのデータ出力１７０８とからなる。
【００７５】
図２１の構造を持つ第３の並べ替えセル１６０２は、外部からの設定入力１７０３を受けてアドレスを生成するアドレスカウンタ１７０４と、セレクタを制御するための制御信号を読み出すメモリ１７０５と、１６個のデータグループの中から隣接する奇数番目と偶数番目のデータグループを選択する２対１出力セレクタ１７０６とを内蔵しているため、データのコピーや並べ替えといった演算を、１サイクルで実行することができる。これらの演算を、ＡＬＵ、シフタ等の演算器から構成される演算エレメント１０２を用いて実現する場合を考えると、各々のデータ演算に対して少なくとも１つの演算エレメント１０２を使用し、なおかつ算術等の演算を行わないにもかかわらず、演算器を使用する必要がある。したがって、図２１の構成を持つ第３の並べ替えセル１６０２を搭載するプログラマブル・ロジック・デバイス１６０１を用いた場合は、ターゲットとするアプリケーションの信号処理のうち、データの並べ替え演算等を、第３の並べ替えセル１６０２を用いて実現すれば、全ての信号処理を演算エレメント１０２を用いて実現する場合に比較して、効率良くアプリケーションの信号処理を実現することができる。
【００７６】
図２０、図２１に記載のプログラマブル・ロジック・デバイス１６０１を用いて実現するアプリケーションの例として、ＧＳＭ（Global System for Mobile Communications）方式携帯電話のデジタルベースバンド処理を想定する。
【００７７】
図２２及び図２３に、ＧＳＭ方式携帯電話のデジタルベースバンド処理の概略を示す。この信号処理では、１ビット単位での入力信号に対し、決まったビット数を一旦メモリ又はレジスタ等の記憶素子に格納し、これを所定の手順で並べ替えるインターリーブ処理を施した後、リードソロモン復号やパンクチュアリング等の信号処理を実施する。インターリーブ処理は上記のようにデータの並べ替えの演算を含んでおり、しかも１ビット単位での信号処理を含むため、演算エレメントを用いて信号処理を実施するのではなく、並べ替えセルを使用して実現した方が効率的である。更に、これらの信号処理は、デジタルベースバンド処理のうち初期の段階で実施する必要がある。
【００７８】
インターリーブ処理に関して、その動作の詳細について図２４及び図２５を用いて説明する。図２４及び図２５は、図２１に記載の第３の並べ替えセル１６０２を模式的に描いたものである。ここでは、入力信号を取り込む１２８ビットのフリップフロップ１７０２を６４ビットずつ２つの組に分ける。
【００７９】
デジタルベースバンド処理における入力データは、１ビット単位の入力データが所定の符号長を持ったデータとして順次レジスタに蓄えられる。これを最初は第３の並べ替えセル１６０２の１組目の６４ビットのフリップフロップ１７０２に入力する。この１組目の６４ビットのフリップフロップ１７０２内にデータが満杯に蓄えられた後は、デジタルベースバンド処理の入力データは順次２組目の６４ビットのフリップフロップ１７０２に蓄えられる。
【００８０】
これらのデータが蓄えられた後は、アドレスカウンタ１７０４が外部から所定の値に設定されることにより、下記の要領にてデータの並べ替え演算が実施される。
【００８１】
１サイクル目の設定値では、アドレスカウンタ１７０４とメモリ１７０５との動作により、入力の８ビット×１６並列入力と出力の８ビット×８並列出力との接続関係は図２４に示す状態となる。１組目の６４ビットのフリップフロップ１７０２の奇数番目の８ビットデータと、２組目の６４ビットのフリップフロップ１７０２の奇数番目の８ビットデータとが出力の６４ビットフリップフロップ１７０７に接続され、データが転送される。
【００８２】
次のサイクルでは、外部の設定値が変更され、アドレスカウンタ１７０４とメモリ１７０５との動作により、入力の８ビット×１６並列入力と出力の８ビット×８並列出力との接続関係は図２５に示す状態となる。１組目の６４ビットのフリップフロップ１７０２の偶数番目の８ビットデータと、２組目の６４ビットのフリップフロップ１７０２の偶数番目の８ビットデータとが出力の６４ビットフリップフロップ１７０７に接続され、データが転送される。このようにインターリーブ処理は第３の並べ替えセル１６０２を用いて２サイクルで実施することができる。
【００８３】
ここで、図２０、図２１に記載のプログラマブル・ロジック・デバイス１６０１の第３の並べ替えセル１６０２を１２８／６４ビットの入出力構成とした理由を説明する。インターリーブ処理では、８ビット８並列のデータが２組入力されるため、第３の並べ替えセル１６０２に必要な入力の構成としては、図２１に示した８ビット×１６並列入力＝１２８ビットの構成となる。第３の並べ替えセル１６０２の入力ビット数が１２８ビットより少ない場合、８ビット×１６並列データの並べ替え処理が実現できないので、第３の並べ替えセル１６０２を用いた並べ替え処理は不可能である。したがって、並べ替え処理は、演算エレメント又は配線ネットワーク（図示せず）を使用する必要がある。
【００８４】
一方、第３の並べ替えセル１６０２の入力ビット数が１２８ビットより多い場合は、インターリーブ処理に必要なビット幅は８ビット×１６画素分＝１２８ビットであり、１２８ビットより多いビット数の処理は存在しないため、第３の並べ替えセル１６０２の入力のうち１２８ビット分しか使用せず、余剰分は遊びとなり、チップ面積の観点で無駄が生じる。
【００８５】
以上の内容を考慮すると、図２０、図２１に記載のプログラマブル・ロジック・デバイス１６０１の第３の並べ替えセル１６０２は１２８ビットの入力と６４ビットの出力とを持つ構成にすることが最適であると言うことができる。
【００８６】
また、図２０、図２１に記載のプログラマブル・ロジック・デバイス１６０１の演算エレメント群１０３を、演算エレメント１０２を縦方向１６個×横方向１６個配置する構成とした理由を説明する。第３の並べ替えセル１６０２は上記の理由で１２８ビットの入力と６４ビットの出力とを持つ構成としている。このうち６４ビットの出力を演算エレメント群１０３の入力と接続する構成を考慮すると、１つの演算エレメント１０２の処理ビット数及び入出力ビット数は４ビットのため、６４ビット／４ビット＝１６個の演算エレメントが必要である。このように、演算エレメント群１０３の一辺に１６個の演算エレメント１０２を配置し、正方形状の配置とすることにより、演算エレメント群１０３の６４ビット入力を全て第３の並べ替えセル１６０２の出力に接続できる構成とすることで、演算エレメント１０２の入力信号に無駄を生じさせない構成とすることができる。第３の並べ替えセル１６０２に接続する演算エレメント１０２の数が１６個より少ないと、第３の並べ替えセル１６０２の出力に余剰のピンを生じるため、適さない。また、１６個より多いと、第３の並べ替えセル１６０２に接続できない演算エレメント１０２が存在し、この演算エレメント１０２は動作させられず、無駄となる。したがって、演算エレメント群１０３の一辺の演算エレメント１０２の個数は１６個が最適な数となる。
【００８７】
ここで、インターリーブ処理を実現するに当たって、演算エレメント１０２ではなく、第３の並べ替えセル１６０２を用いた方が、より良い面積効率で実現できる理由を説明する。
【００８８】
まず、インターリーブ処理に関して、並べ替えセルを配置しない従来のプログラマブル・ロジック・デバイスを用いた場合に必要な演算エレメントの数を、図２６を使って説明する。インターリーブ処理では１組目の８入力データに対して、奇数側と偶数側との入力を選択して４組の出力を得るので、演算エレメントを２対１のマルチプレクサとして使用した場合、４つの演算エレメントを使用する。更に２組目の８入力データに対して、奇数側と偶数側との入力を選択して４組の出力を得るので、更に４つの演算エレメントを使用する。合計で８個の演算エレメントが必要となる。更に１つの演算エレメントで処理できるビット数は４ビットのため、８ビットのデータを処理するためには、２倍の演算エレメントが必要となる。よって、必要な演算エレメントの総数は８×２＝１６個となる。演算エレメント１つあたりに約１６０個ゲートを使用するため、全体でのゲート数は１６×１６０＝２５６０ゲートとなる。
【００８９】
一方、第３の並べ替えセル１６０２を用いた場合に関しては、図２７に示すとおり、第３の並べ替えセル１６０２を１つ使用することで実現できる。第３の並べ替えセル１６０２のゲート数は、３ゲートを有する２対１セレクタで実現した場合、８×８＝６４個必要となる。したがってゲート数は、３×６４＝１９２ゲートとなる。これを従来の演算エレメントで実現した場合と比較すると、約１／１０以下のゲート数に削減していることが分かる。
【００９０】
以上のように、本実施の形態によれば、ＧＳＭ方式携帯電話のデジタルベースバンド処理を、第３の実施の形態のプログラマブル・ロジック・デバイス１６０１を用いて実現することによって、デジタルベースバンド処理内の算術演算を必要とする処理に関しては演算エレメント１０２を用いて実現し、インターリーブ処理のようなデータの並べ替え処理は第３の並べ替えセル１６０２を用いて実現することにより、ＧＳＭ方式携帯電話のデジタルベースバンド処理全体を効率良く本発明のプログラマブル・ロジック・デバイス１６０１上で実現することができる。
【００９１】
なお、上記各実施の形態において、４ビットの演算エレメント１０２に代えて８ビットの演算エレメントを利用することも可能である。
【産業上の利用可能性】
【００９２】
本発明のプログラマブル・ロジック・デバイスは、外部からの設定によって毎サイクル機能変更が可能な制御回路を持ち、かつプログラムによって配線経路を変更することによって６４ビット又は１２８ビットの入力信号を並べ替えて６４ビット信号を出力する並べ替えセルを複数内蔵するため、プログラマブル・ロジック・デバイスで実行するアプリケーションのうち、データの並び替えやコピー等の演算を、演算エレメントを用いずに、小面積で実現することができる。これによって、アプリケーションを実行する際に必要となる演算エレメントの数を削減することができるという効果を有し、複数の演算エレメントと、演算エレメント間を相互に接続する複数の配線及びスイッチからなるプログラマブル・ロジック・デバイス回路として有用である。
【符号の説明】
【００９３】
１０１ プログラマブル・ロジック・デバイス
１０２ 演算エレメント
１０３ 演算エレメント群
１０４ 並べ替えセル（６４ビット入出力）
１０５ 配線
２０１ データ入力（６４ビット）
２０２ フリップフロップ
２０３ 設定入力
２０４ アドレスカウンタ
２０５ メモリ
２０６ ６４対１出力セレクタ
２０７ フリップフロップ
２０８ データ出力（６４ビット）
３０１ 平文入力（６４ビット）
３０２ 初期転置（並べ替え）
３０３ 鍵入力（６４ビット）
３０４ 転置（６４ビット−＞５６ビット）
３０５ 転置（５６ビット−＞４８ビット）
３０６ Ｆ関数
３０７ 最終転置（並べ替え）
３０８ シフト
４０１ 転置（３２ビット−＞４８ビット）
４０２ Ｓｂｏｘ
４０３ 転置（３２ビット−＞３２ビット）
５０１ 平文入力（６４ビット）
５０２ 初期転置回路（並べ替え）
５０３ 入力データセレクタ
５０４ 転置回路（３２ビット−＞４８ビット）
５０５ 排他的論理和回路
５０６ Ｓｂｏｘ回路
５０７ 転置回路（３２ビット−＞３２ビット）
５０８ 排他的論理和回路
５０９ 最終転置回路（並べ替え）
５１０ 鍵入力（６４ビット）
５１１ 転置回路（６４ビット−＞５６ビット）
５１２ 入力データセレクタ
５１３ シフト回路
５１４ 転置回路（５６ビット−＞４８ビット）
１００１ プログラマブル・ロジック・デバイス
１００２ 第２の並べ替えセル（６４ビット入出力）
１１０１ データ入力（６４ビット）
１１０２ フリップフロップ
１１０３ 設定入力
１１０４ アドレスカウンタ
１１０５ メモリ
１１０６ ８対１出力セレクタ
１１０７ フリップフロップ
１１０８ データ出力（６４ビット）
１２０１ マクロブロック入力
１２０２ 予測画像生成回路
１２０３ 差分値生成回路
１２０４ 直交変換回路
１２０５ 量子化回路
１６０１ プログラマブル・ロジック・デバイス
１６０２ 第３の並べ替えセル（１２８ビット入力・６４ビット出力）
１７０１ データ入力（１２８ビット）
１７０２ フリップフロップ
１７０３ 設定入力
１７０４ アドレスカウンタ
１７０５ メモリ
１７０６ ２対１出力セレクタ
１７０７ フリップフロップ
１７０８ データ出力（６４ビット）
２３０１ 演算ブロック
２３０２ レジスタ
２３０３ 配線
２３０４ スイッチボックス（ＳＢ）
２３０５ コンフィギュレーションメモリ
【特許請求の範囲】
【請求項１】
内部に少なくとも演算器と配線スイッチとを持つ演算エレメントと、プログラムによって配線経路を変更することによって６４ビットの入力信号を任意の順番に並べ替えて６４ビット信号を出力する第１の並べ替えセルを複数内蔵し、かつ前記第１の並べ替えセルは外部からの設定によって毎サイクル機能変更が可能な制御回路を持つことを特徴とするプログラマブル・ロジック・デバイス。
【請求項２】
請求項１に記載のプログラマブル・ロジック・デバイスにおいて、
Ｌビットの入力とＬビットの出力とを持ち、演算ビット数がＬ（Ｌ＝４又は８）ビットである演算エレメントを縦（（８／Ｌ）×８）個かける横（（８／Ｌ）×８）個の正方形状に並べ、（（８／Ｌ）×８）×Ｌ＝６４ビットの入力と、同じく６４ビットの出力とを持つ演算エレメント群を備え、
１つの前記演算エレメント群に対して１つの前記第１の並べ替えセルを前記演算エレメント群の４辺のうち少なくとも１つの辺に隣接して配置し、
前記演算エレメント群の６４ビットの入力に前記第１の並べ替えセルの６４ビット出力を接続したことを特徴とするプログラマブル・ロジック・デバイス。
【請求項３】
請求項１に記載のプログラマブル・ロジック・デバイスにおいて、
Ｌビットの入力とＬビットの出力とを持ち、演算ビット数がＬ（Ｌ＝４又は８）ビットである演算エレメントを縦（（８／Ｌ）×８）個かける横（（８／Ｌ）×８）個の正方形状に並べ、（（８／Ｌ）×８）×Ｌ＝６４ビットの入力と、同じく６４ビットの出力とを持つ演算エレメント群を備え、
１つの前記演算エレメント群に対して１つの前記第１の並べ替えセルを前記演算エレメント群の４辺のうち少なくとも１つの辺に隣接して配置し、
前記演算エレメント群の６４ビットの出力に前記第１の並べ替えセルの６４ビット入力を接続したことを特徴とするプログラマブル・ロジック・デバイス。
【請求項４】
内部に少なくとも演算器と配線スイッチとを持つ演算エレメントと、６４ビットの入力信号のうち連続する８ビットの信号を１つのグループとして８個のグループに分け、プログラムによって配線経路を変更することによって８個の８ビット信号グループを任意の順番に並び替えて、６４ビットの出力信号を生成する第２の並べ替えセルを複数内蔵し、かつ前記第２の並べ替えセルは外部からの設定によって毎サイクル機能変更が可能な制御回路を持つことを特徴とするプログラマブル・ロジック・デバイス。
【請求項５】
請求項４に記載のプログラマブル・ロジック・デバイスにおいて、
Ｌビットの入力とＬビットの出力とを持ち、演算ビット数がＬ（Ｌ＝４又は８）ビットである演算エレメントを縦（（８／Ｌ）×８）個かける横（（８／Ｌ）×８）個の正方形状に並べ、（（８／Ｌ）×８）×Ｌ＝６４ビットの入力と、同じく６４ビットの出力とを持つ演算エレメント群を備え、
１つの前記演算エレメント群に対して１つの前記第２の並べ替えセルを前記演算エレメント群の４辺のうち少なくとも１つの辺に隣接して配置し、
前記演算エレメント群の６４ビットの入力に前記第２の並べ替えセルの６４ビット出力を接続したことを特徴とするプログラマブル・ロジック・デバイス。
【請求項６】
請求項４に記載のプログラマブル・ロジック・デバイスにおいて、
Ｌビットの入力とＬビットの出力とを持ち、演算ビット数がＬ（Ｌ＝４又は８）ビットである演算エレメントを縦（（８／Ｌ）×８）個かける横（（８／Ｌ）×８）個の正方形状に並べ、（（８／Ｌ）×８）×Ｌ＝６４ビットの入力と、同じく６４ビットの出力とを持つ演算エレメント群を備え、
１つの前記演算エレメント群に対して１つの前記第２の並べ替えセルを前記演算エレメント群の４辺のうち少なくとも１つの辺に隣接して配置し、
前記演算エレメント群の６４ビットの出力に前記第２の並べ替えセルの６４ビット入力を接続したことを特徴とするプログラマブル・ロジック・デバイス。
【請求項７】
内部に少なくとも演算器と配線スイッチとを持つ演算エレメントと、１２８ビットの入力信号のうち連続する８ビットの信号を１つのグループとして１６個のグループに分け、プログラムによって配線経路を変更することによって１６個の８ビット信号グループのうち偶数番目又は奇数番目の８ビット信号グループを選択して出力６４ビットの出力信号を生成する第３の並べ替えセルを複数内蔵し、かつ前記第３の並べ替えセルは外部からの設定によって毎サイクル機能変更が可能な制御回路を持つことを特徴とするプログラマブル・ロジック・デバイス。
【請求項８】
請求項７に記載のプログラマブル・ロジック・デバイスにおいて、
Ｌビットの入力とＬビットの出力とを持ち、演算ビット数がＬ（Ｌ＝４又は８）ビットである演算エレメントを縦（（８／Ｌ）×８）個かける横（（８／Ｌ）×８）個の正方形状に並べ、（（８／Ｌ）×８）×Ｌ＝６４ビットの入力と、同じく６４ビットの出力とを持つ演算エレメント群を備え、
１つの前記演算エレメント群に対して１つの前記第３の並べ替えセルを前記演算エレメント群の４辺のうち少なくとも１つの辺に隣接して配置し、
前記演算エレメント群の６４ビットの入力に前記第３の並べ替えセルの６４ビット出力を接続したことを特徴とするプログラマブル・ロジック・デバイス。
【請求項９】
請求項８に記載のプログラマブル・ロジック・デバイスにおいて、
前記第３の並べ替えセルの１２８ビットの入力信号は、当該プログラマブル・ロジック・デバイスの入力パッドに接続したことを特徴とするプログラマブル・ロジック・デバイス。
【請求項１】
内部に少なくとも演算器と配線スイッチとを持つ演算エレメントと、プログラムによって配線経路を変更することによって６４ビットの入力信号を任意の順番に並べ替えて６４ビット信号を出力する第１の並べ替えセルを複数内蔵し、かつ前記第１の並べ替えセルは外部からの設定によって毎サイクル機能変更が可能な制御回路を持つことを特徴とするプログラマブル・ロジック・デバイス。
【請求項２】
請求項１に記載のプログラマブル・ロジック・デバイスにおいて、
Ｌビットの入力とＬビットの出力とを持ち、演算ビット数がＬ（Ｌ＝４又は８）ビットである演算エレメントを縦（（８／Ｌ）×８）個かける横（（８／Ｌ）×８）個の正方形状に並べ、（（８／Ｌ）×８）×Ｌ＝６４ビットの入力と、同じく６４ビットの出力とを持つ演算エレメント群を備え、
１つの前記演算エレメント群に対して１つの前記第１の並べ替えセルを前記演算エレメント群の４辺のうち少なくとも１つの辺に隣接して配置し、
前記演算エレメント群の６４ビットの入力に前記第１の並べ替えセルの６４ビット出力を接続したことを特徴とするプログラマブル・ロジック・デバイス。
【請求項３】
請求項１に記載のプログラマブル・ロジック・デバイスにおいて、
Ｌビットの入力とＬビットの出力とを持ち、演算ビット数がＬ（Ｌ＝４又は８）ビットである演算エレメントを縦（（８／Ｌ）×８）個かける横（（８／Ｌ）×８）個の正方形状に並べ、（（８／Ｌ）×８）×Ｌ＝６４ビットの入力と、同じく６４ビットの出力とを持つ演算エレメント群を備え、
１つの前記演算エレメント群に対して１つの前記第１の並べ替えセルを前記演算エレメント群の４辺のうち少なくとも１つの辺に隣接して配置し、
前記演算エレメント群の６４ビットの出力に前記第１の並べ替えセルの６４ビット入力を接続したことを特徴とするプログラマブル・ロジック・デバイス。
【請求項４】
内部に少なくとも演算器と配線スイッチとを持つ演算エレメントと、６４ビットの入力信号のうち連続する８ビットの信号を１つのグループとして８個のグループに分け、プログラムによって配線経路を変更することによって８個の８ビット信号グループを任意の順番に並び替えて、６４ビットの出力信号を生成する第２の並べ替えセルを複数内蔵し、かつ前記第２の並べ替えセルは外部からの設定によって毎サイクル機能変更が可能な制御回路を持つことを特徴とするプログラマブル・ロジック・デバイス。
【請求項５】
請求項４に記載のプログラマブル・ロジック・デバイスにおいて、
Ｌビットの入力とＬビットの出力とを持ち、演算ビット数がＬ（Ｌ＝４又は８）ビットである演算エレメントを縦（（８／Ｌ）×８）個かける横（（８／Ｌ）×８）個の正方形状に並べ、（（８／Ｌ）×８）×Ｌ＝６４ビットの入力と、同じく６４ビットの出力とを持つ演算エレメント群を備え、
１つの前記演算エレメント群に対して１つの前記第２の並べ替えセルを前記演算エレメント群の４辺のうち少なくとも１つの辺に隣接して配置し、
前記演算エレメント群の６４ビットの入力に前記第２の並べ替えセルの６４ビット出力を接続したことを特徴とするプログラマブル・ロジック・デバイス。
【請求項６】
請求項４に記載のプログラマブル・ロジック・デバイスにおいて、
Ｌビットの入力とＬビットの出力とを持ち、演算ビット数がＬ（Ｌ＝４又は８）ビットである演算エレメントを縦（（８／Ｌ）×８）個かける横（（８／Ｌ）×８）個の正方形状に並べ、（（８／Ｌ）×８）×Ｌ＝６４ビットの入力と、同じく６４ビットの出力とを持つ演算エレメント群を備え、
１つの前記演算エレメント群に対して１つの前記第２の並べ替えセルを前記演算エレメント群の４辺のうち少なくとも１つの辺に隣接して配置し、
前記演算エレメント群の６４ビットの出力に前記第２の並べ替えセルの６４ビット入力を接続したことを特徴とするプログラマブル・ロジック・デバイス。
【請求項７】
内部に少なくとも演算器と配線スイッチとを持つ演算エレメントと、１２８ビットの入力信号のうち連続する８ビットの信号を１つのグループとして１６個のグループに分け、プログラムによって配線経路を変更することによって１６個の８ビット信号グループのうち偶数番目又は奇数番目の８ビット信号グループを選択して出力６４ビットの出力信号を生成する第３の並べ替えセルを複数内蔵し、かつ前記第３の並べ替えセルは外部からの設定によって毎サイクル機能変更が可能な制御回路を持つことを特徴とするプログラマブル・ロジック・デバイス。
【請求項８】
請求項７に記載のプログラマブル・ロジック・デバイスにおいて、
Ｌビットの入力とＬビットの出力とを持ち、演算ビット数がＬ（Ｌ＝４又は８）ビットである演算エレメントを縦（（８／Ｌ）×８）個かける横（（８／Ｌ）×８）個の正方形状に並べ、（（８／Ｌ）×８）×Ｌ＝６４ビットの入力と、同じく６４ビットの出力とを持つ演算エレメント群を備え、
１つの前記演算エレメント群に対して１つの前記第３の並べ替えセルを前記演算エレメント群の４辺のうち少なくとも１つの辺に隣接して配置し、
前記演算エレメント群の６４ビットの入力に前記第３の並べ替えセルの６４ビット出力を接続したことを特徴とするプログラマブル・ロジック・デバイス。
【請求項９】
請求項８に記載のプログラマブル・ロジック・デバイスにおいて、
前記第３の並べ替えセルの１２８ビットの入力信号は、当該プログラマブル・ロジック・デバイスの入力パッドに接続したことを特徴とするプログラマブル・ロジック・デバイス。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【公開番号】特開２０１２−１０９８５４（Ｐ２０１２−１０９８５４Ａ）
【公開日】平成２４年６月７日（２０１２．６．７）
【国際特許分類】
【出願番号】特願２０１０−２５７８４５（Ｐ２０１０−２５７８４５）
【出願日】平成２２年１１月１８日（２０１０．１１．１８）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＧＳＭ
【出願人】（０００００５８２１）パナソニック株式会社 (73,050)
【Ｆターム（参考）】
【公開日】平成２４年６月７日（２０１２．６．７）
【国際特許分類】
【出願日】平成２２年１１月１８日（２０１０．１１．１８）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＧＳＭ
【出願人】（０００００５８２１）パナソニック株式会社 (73,050)
【Ｆターム（参考）】
[ Back to top ]