JP4328487B2 - 組合せ回路、暗号回路、その生成方法及びプログラム - Google Patents
組合せ回路、暗号回路、その生成方法及びプログラム Download PDFInfo
- Publication number
- JP4328487B2 JP4328487B2 JP2002017959A JP2002017959A JP4328487B2 JP 4328487 B2 JP4328487 B2 JP 4328487B2 JP 2002017959 A JP2002017959 A JP 2002017959A JP 2002017959 A JP2002017959 A JP 2002017959A JP 4328487 B2 JP4328487 B2 JP 4328487B2
- Authority
- JP
- Japan
- Prior art keywords
- selector
- bdd
- circuit
- input
- output
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000000034 method Methods 0.000 title claims description 40
- 230000014509 gene expression Effects 0.000 claims description 34
- 201000003231 brachydactyly type D Diseases 0.000 claims description 23
- 238000010586 diagram Methods 0.000 claims description 12
- 239000000872 buffer Substances 0.000 claims description 11
- 238000013507 mapping Methods 0.000 claims description 9
- 230000002194 synthesizing effect Effects 0.000 claims description 4
- 230000015572 biosynthetic process Effects 0.000 description 12
- 238000003786 synthesis reaction Methods 0.000 description 12
- 230000006870 function Effects 0.000 description 9
- 238000005516 engineering process Methods 0.000 description 5
- 238000004891 communication Methods 0.000 description 3
- 238000001308 synthesis method Methods 0.000 description 3
- PXFBZOLANLWPMH-UHFFFAOYSA-N 16-Epiaffinine Natural products C1C(C2=CC=CC=C2N2)=C2C(=O)CC2C(=CC)CN(C)C1C2CO PXFBZOLANLWPMH-UHFFFAOYSA-N 0.000 description 2
- 238000006243 chemical reaction Methods 0.000 description 2
- 238000013478 data encryption standard Methods 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 241000209507 Camellia Species 0.000 description 1
- 235000018597 common camellia Nutrition 0.000 description 1
- 239000002131 composite material Substances 0.000 description 1
- 238000010276 construction Methods 0.000 description 1
- 230000007274 generation of a signal involved in cell-cell signaling Effects 0.000 description 1
- 230000003287 optical effect Effects 0.000 description 1
- 238000005457 optimization Methods 0.000 description 1
- 239000004065 semiconductor Substances 0.000 description 1
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/06—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols the encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions; Pseudorandom sequence generators
- H04L9/0618—Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
- H04L2209/12—Details relating to cryptographic hardware or logic circuitry
- H04L2209/122—Hardware reduction or efficient architectures
Landscapes
- Engineering & Computer Science (AREA)
- Computer Security & Cryptography (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Logic Circuits (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、組合せ回路の構成及びその論理合成方法に関し、とくに暗号回路に用いられるＳ−Ｂｏｘなどの組合せ回路の構成及びその論理合成方法に関する。
【０００２】
【従来の技術】
コンピュータネットワークによる情報通信、特に公衆ネットワークを専用線のように利用するＶＰＮ（Virtual Private Network）通信においては、暗号技術が必要不可欠である。そして、情報通信の高速化に伴って、より高速な暗号技術が要求される。
【０００３】
今日、コンピュータネットワークで用られている主要な暗号技術である共通鍵暗号として、ＤＥＳ（Data Encryption Standard）やＡＥＳ（Advanced Encryption Standard）、Camelliaなどが存在するが、この暗号技術を実現する論理回路（暗号回路）には、いずれもＳ−Ｂｏｘと呼ばれる非線形変換部が存在している。そして、このＳ−Ｂｏｘの処理速度は、論理回路自体の処理速度に大きく影響する。
【０００４】
ここで、共通鍵暗号におけるＳ−Ｂｏｘ演算とその回路構成法について説明する。なお、ここではＡＥＳのＳ−Ｂｏｘを例に説明する。
ＡＥＳにおけるＳ−Ｂｏｘは、８ビット入力に対し、まず（ｉ）既約多項式ｘ8＋ｘ4＋ｘ3＋ｘ＋１により構成されたＧＦ（２8）上での乗法逆元演算を適用し、続いて（ｉｉ）下記数１式のAffine変換を適用して８ビット値を出力する。
【数１】
Ｓ−Ｂｏｘ-1はこの逆演算である。
【０００５】
このＳ−Ｂｏｘの回路実装の手法には、（１）上記の定義に従ってＧＦ逆元演算回路とAffine変換回路とを別々に作ってから直列につなぐ方法と、（２）入出力関係（真理値表）から直接回路を導出する方法とがある。
（１）の場合、フェルマーの小定理Ｐ-1＝Ｐ254（ＧＦ(２8)の場合）を用いて計算する方法、拡張ユークリッド法を用いて計算する方法、及び合成体（composite field）上の逆元演算に帰着する方法がある。しかし、これらのいずれも高速実装には向いておらず、（２）の方法の数倍程度の回路遅延が生ずる。なお、これらの手法については、例えば下記文献１、２に詳細に記載されている。
文献１：S.Morioka and Y.Katayama, "O(log2m) Iterative Algorithm for Multiplicative Inverse in GF(2m)," IEEE Intl. Symp. On Info. Theory (ISIT2000), pp.449, 2000.
文献２：A.Satoh, S.Morioka, K.Takano and S.Munetoh, "Compact Rijndael Hardware Architecture with S-Box Optimization," ASIACRYPT2001, 2001.
一方、（２）の場合、積和形、和積形、各種リード・マラー形式の論理式を構成する方法や、各種関数展開を行う方法が知られている。
【０００６】
次に、組合せ回路の汎用論理合成アルゴリズムについて説明する。
関数展開を用いた論理構成法の１つとして、ＲＯ−ＢＤＤ（Reduced Ordered Binary Decision Diagrams）を用いる方法が知られている。ＲＯ−ＢＤＤは、論理関数の表現形式の１つであり、一定の変数順で論理関数をＳｈａｎｎｏｎ展開していく過程を、閉路なしの二分決定グラフとして表現したうえで冗長ノードを除去したものである。このＲＯ−ＢＤＤの各ノードを２：１セレクタ（ＭＵＸ：マルチプレクサ）に置き換えることにより、ＲＯ−ＢＤＤの回路化を行うことができる。かかるＲＯ−ＢＤＤを用いた論理構成法については、例えば下記文献３に詳細に記載されている。
文献３：R.E.Bryant；Graph-Based Algorithms for Boolean Function Manipulation, IEEE transactions on computers, Vol.C-25, No.8, 1986.
ＲＯ−ＢＤＤのグラフ構造と得られる回路構造（＝セレクタの接続関係）とはほぼ１対１に対応するので、どのような形のＲＯ−ＢＤＤを構成するかを決めることが回路構造を規定する。与えられた論理関数に対するＲＯ−ＢＤＤは１通りではなく、ノード共有をどのように行うか、あるいは変数順をどうするかに設計自由度がある。
【０００７】
図５は、従来の論理合成アルゴリズムにて作成されたＲＯ−ＢＤＤに基づく、ＡＥＳのＳ−Ｂｏｘの構成例を示す図である。なお、図５において、組合せ回路を構成するセレクタ及び各段のセレクタどうしの接続は、適宜省略されて記載されている。
図５に示すように、従来の論理合成アルゴリズムにより作成されたＲＯ−ＢＤＤに基づくＳ−Ｂｏｘの組合せ回路は、一般の論理関数にはない、次のような大きな特徴がある。
特徴１：回路の出力側では、出力間ないし同一出力のセレクタ群においてセレクタがほとんど共有されていない。共有がなされているのは回路入力側の１、２段のみである。すなわち、出力側から入力側に行くにつれセレクタ数が１＊８、２＊８、４＊８、８＊８、・・・と指数的に増えていき（そのとき、ほぼ全てのセレクタで、その出力のファンアウトは１）、入力側の最後の１、２段では各セレクタ出力のファンアウトが急に大きくなる（３０前後）。これに対し、一般の多くの論理関数では、より出力に近い段まで多くのセレクタが共有されるため、図５のような木構造にはならない。また、出力間で多くのノードを共有できるのが普通である。
特徴２：全体的なセレクタ結合の形が、入力のビット順（入力の何ビット目が、何段目のセレクタをドライブするか）にほとんど依存せず、どのようなビット順でも上記特徴１を有する形になる。これに対し、一般の多くの論理関数では、入力ビット順を変えると回路の全体的な形は非常に大きく変化する。
【０００８】
【発明が解決しようとする課題】
上述したように、従来、ＲＯ−ＢＤＤを用いて回路構造を規定し、組合せ回路をデザインすることが行われていた。一方、Ｓ−Ｂｏｘとして最も高速なものは、Ｓ−Ｂｏｘの真理値表から自動論理合成で得られる回路であったが、Ｓ−Ｂｏｘは乱数テーブルに近い入出力定義を有するため、汎用の論理合成手法との相性は良くない。そのため、上記の暗号技術の用途などにおいて十分な速度を得ることができなかった。
【０００９】
すなわち、ＲＯ−ＢＤＤを用いて回路構造を規定する手法でＳ−Ｂｏｘのような組合せ回路をデザインすると、従来の論理合成アルゴリズムにより作成されたＲＯ−ＢＤＤは、上述した特徴１、２を有するため、高速回路を設計する上で、次の２点が問題となっていた。
（１）回路の入力側セレクタのセレクト信号・出力データ信号のファンアウトが大きくなること（たとえば図５では、入力から２段目のセレクタは１４９個あるので、そのセレクト信号のドライブは非常に重い。また、入力から１段目の各セレクタ出力は、２段目セレクタの入力信号を３０本近くドライブしなければならず、これも非常に重い）。
（２）セレクタを直列に多段つないだ回路となるため、信号通過時間が長くなること。
【００１０】
そこで本発明は、上記の課題を解決し、高速なＳ−Ｂｏｘなどの組合せ回路を実現すると共に、かかる組合せ回路の回路構造を規定するＲＯ−ＢＤＤを作成する手法を提供することを目的とする。
【００１１】
【課題を解決するための手段】
上記の目的を達成するため、本発明は、複数個のセレクタにて構成される次のような組合せ回路として実現される。すなわち、この組合せ回路は、出力ビットを個別に生成する、出力ビット数に対応する数の独立したセレクタ群と、各セレクタ群にプライマリ入力を供給するドライバとを備え、各セレクタ群は、プライマリ入力のビット数以下の数の段を形成して接続された複数個のセレクタを備え、各段のセレクタのセレクト信号が１つのプライマリ入力でドライブされることを特徴とする。
【００１２】
ここで詳細には、このドライバは、入力ビットごとに、バッファまたはインバータを連鎖的につなげて設けられたドライバチェインにて構成される。そして、各ドライバチェインは、入力側からバッファまたはインバータを経て出力側へ進むと共に相異なる順番でセレクタ群に接続され、このセレクタ群を構成するセレクタの各段にセレクト信号を供給する。これにより、各セレクタ群におけるｉ段目セレクタ（全段数≧ｉ≧１）のセレクト信号を制御するプライマリ入力が各セレクタ群で異なり、さらに各段に入力されるセレクト信号の順番がセレクタ群ごとに異なることとなる。
【００１３】
また、本発明による他の組合せ回路は、プライマリ入力のビット数以下の段数分の２：１セレクタが相互に接続され、かつ少なくとも出力側の所定数ｎ段分の２：１セレクタにおいて、複数の出力ビットを生成する２：１セレクタの一群どうしの間でこの２：１セレクタが共有されていないことを条件に、このｎ段分の２：１セレクタを置き換えて設けられた２n：１セレクタと、この２n：１セレクタに置き換えられた残りの２：１セレクタとを備える。そして、この２n：１セレクタは、２n本の入力のうちどれをセレクトするかを決定するセレクト信号を生成する生成回路と、この生成回路にて生成されたセレクト信号を用いて２n本の入力のうち一本を選び出すための選択回路とを備えることを特徴とする。
さらに、上述した出力ビット数に対応する数の独立したセレクタ群を有する組合せ回路において、このセレクタ群を構成する２：１セレクタに対して、このような２n：１セレクタへの置き換えを行うことができる。
【００１４】
また、上記の目的を達成する他の本発明は、ＲＯ−ＢＤＤを用いた組合せ回路の生成方法として、次のように実現される。すなわち、この組合せ回路の生成方法は、まず、出力ビット数に対応する数のＲＯ−ＢＤＤであって、このＲＯ−ＢＤＤ間でノードを共有せず、かつ各ＲＯ−ＢＤＤにおける変数順が相互に異なるＲＯ−ＢＤＤの一群を生成する。そして、各ＲＯ−ＢＤＤの各ノードをセレクタに置き換える。さらに、各セレクタの制御信号を生成するためのドライバチェインを作り、このＲＯ−ＢＤＤに基づくセレクタの段と、このドライバチェインとを対応させて、セレクタとドライバチェインとを接続することを特徴とする。
【００１５】
さらに本発明による組合せ回路の他の生成方法は、まず、出力側の所定数ｎ段分のノードが出力ビット数に対応する数の完全木の構造を有するＲＯ−ＢＤＤを生成する。次に、このＲＯ−ＢＤＤにおけるｎ段分のノードを、２n本の入力のうちどれをセレクトするかを決定するセレクト信号を生成する生成回路と当該セレクト信号を用いて２n本の入力のうち一本を選び出すための選択回路とを備えた２n：１セレクタに置き換え、他のノードを２：１セレクタに置き換えることを特徴とする。
【００１６】
さらにまた、本発明は、コンピュータを制御して、組合せ回路の回路構造を論理合成する次のようなプログラムとしても実現される。このプログラムは、処理対象である組合せ回路の論理式または真理値表を出力ビットごとに分割し、出力１ビット分の論理式または真理値表を生成する処理と、この出力１ビット分の論理式または真理値表ごとに、他の論理式または真理値表と重複しないようにＲＯ−ＢＤＤの変数順を決定し、決定された変数順で論理式または真理値表のShared-RO-BDDを構築し、その各ノードを２：１セレクタにマップする処理と、この各２：１セレクタの制御信号を生成するためのドライバチェインを作り、ＲＯ−ＢＤＤの制御信号とつなぐ処理とをコンピュータに実行させることを特徴とする。そして、さらに詳細には、ＲＯ−ＢＤＤに対してセレクタをマッピングする際に、Shared-RO-BDDのルート側の所定数ｎ段をUnshared-RO-BDDに変換する処理と、このUnshared-RO-BDDに変換されたｎ段分のノードを２n：１セレクタにマップする処理と、他のノードを２：１セレクタにマップする処理とをコンピュータに実行させる。
【００１７】
上述したプログラムは、磁気ディスクや光ディスク、半導体メモリ、その他の記録媒体に格納して配布したり、ネットワークを介して配信したりすることにより提供することができる。
また、本発明は、Ｓ−Ｂｏｘとして上述した組合せ回路を含む暗号回路として実現することができる。
【００１８】
【発明の実施の形態】
以下、添付図面に示す実施の形態に基づいて、この発明を詳細に説明する。
本実施の形態では、Ｓ−Ｂｏｘなどの組合せ回路において、次の２つの課題を実現する。
１．回路のプライマリ入力側セレクタ群の制御信号乃至出力信号について、それらのファンアウトを減少させる。
２．回路のプライマリ出力側の部分における通過ディレイ（遅延）を、単純にセレクタを多段接続した回路よりも減少させる。
【００１９】
図１は、上記の課題が解決された、本実施の形態によるＳ−Ｂｏｘの組合せ回路の構成を示す図である。
図１を参照すると、この組合せ回路は、複数個のセレクタ１０１をｍ段以下（ｍはプライマリ入力のビット数）の段数分接続し、所定の１段を形成するセレクタのセレクト信号が１つのプライマリ入力でドライブされる構造を有する。すなわち、Ｓ−ＢｏｘのＲＯ−ＢＤＤの各ノードを２：１セレクタで置換して得られる回路である。例えば、１段目のセレクタは全て入力ビット０でドライブされ、２段目は全て入力ビット１でドライブされるようにする（これ以降の段数においても同様）。言い換えれば、真理値表から得られるＲＯ−ＢＤＤの各節点（ノード）をそのままセレクタに置換し、各セレクタをＲＯ−ＢＤＤの枝の通りに接続した構造の回路である。
なお、図１において、各セレクタ群１００を構成するセレクタ１０１及び各段のセレクタ１０１どうしの接続は、適宜省略されて記載されている。
【００２０】
また、図１に示す組合せ回路は、各出力ビットが別々のセレクタ群１００〜１７０で作られており、それらの間でセレクタを一切共有していない。すなわち、各セレクタ群１００〜１７０は独立している。そして、ｉ段目セレクタ（全段数≧ｉ≧１）のセレクト信号を制御するプライマリ入力が各セレクタ群１００〜１７０で異なっている。
例えば、図１の例では、出力ビット０を作る回路（セレクタ群１００）では、１段目セレクタが入力ビット０（図１に示す信号００）、２段目セレクタが入力ビット１（信号０１）で制御されている（以下同様に、順次、信号０２、０３・・・で制御される）。そして、出力ビット１を作る回路（セレクタ群１１０）では、１段目セレクタが入力ビット０ではなく入力ビット１（信号１１）で制御されており、以下順次、２段目セレクタが入力ビット２（信号１２）で制御されるというように、各段におけるセレクト信号の順番がローテートされている。
なお、ここでは、セレクト信号（入力ビット）の順番が各セレクタ群１００〜１７０で異なることによって負荷分散されていれば良く、図１に示したローテートされた順番に限らないことは言うまでもない。
【００２１】
また、本実施の形態の組合せ回路は、図１に示したセレクタ群１００〜１７０にプライマリ入力を供給するドライバを備える。本実施の形態では、バッファまたはインバータを連鎖させたドライバチェインが用いられる。
図２は、ドライバチェインの構成及びドライバチェインによるセレクト信号の入力の分配を示す図である。
図２を参照すると、このドライバチェイン３００〜３７０は、バッファまたはインバータを連鎖的につなげて構成されており、入力ビット（０〜７）ごとに用意されている。そして、ドライバチェイン３００〜３７０の構成と上述したセレクタ群１００〜１７０におけるセレクタの段とを対応させ、各段のセレクタをドライブする制御信号を供給する。ここで、ドライバチェイン３００〜３７０とセレクタ群１００〜１７０との接続関係は、セレクタ群１００〜１７０における入力側セレクタの制御信号はチェインの入力側から取り、出力側セレクタの制御信号はチェインの出力側から取るようになっている。さらに上述したように、各セレクタ群１００〜１７０においてセレクト信号（入力ビット）の順番が異なるように接続されている。
例えば、入力ビット０を供給するドライバチェイン３００（図２参照）は、最も入力側において、図１に示したセレクタ群１００に接続され、信号００を供給する。そして、バッファまたはインバータを経て出力側へ進むと共に順次セレクタ群１７０、１６０、・・・、１１０に接続され、信号７０、６０、・・・、１０を供給する。同様にして、他のドライバチェイン３１０〜３７０も、異なる順番でセレクタ群１００〜１７０に接続されることにより、各セレクタ群１００〜１７０において、段ごとのセレクタに対するセレクト信号の順番が異なることとなり、セレクト信号を供給する上での負荷を分散することができる。
【００２２】
かかる構造によって、セレクト信号のファンアウトや各セレクタの出力信号のファンアウトが減少する。例えば、図１に示した個々のセレクタ群１００〜１７０では、２段目のセレクタは３０個程度となり、図５に示した１４９個のセレクタがある場合と比べて、セレクト信号のドライブが大幅に軽くなる。また、前段セレクタのファンアウトも２〜５程度に減少する。さらに、ドライバチェインを通すことによって、各セレクト信号のファンアウトが減少する（２〜５程度）。これにより、高速な回路が実現される。
なお、図２に示したドライバチェイン３００〜３７０の入力から出力に向かって正論理のセレクト信号と負論理の制御信号が交互に現れるようにし、負論理の信号で制御されるセレクタについては、その２つのデータ信号入力を入れ替えるように構成することができる。このような構成とすることにより、組合せ回路のさらなる高速化を図ることができる場合がある。ＣＭＯＳではバッファを用いるよりもインバータを用いた方が通常は高速だからである。
【００２３】
図３は、図１に示した各出力ビットに対応するセレクタ群の構成を示す図である。
図３を参照すると、本実施の形態による組合せ回路は、各セレクタ群において、さらに次のような構成を有する。なお、図３において、各セレクタ１０１及び各段のセレクタ１０１どうしの接続は、適宜省略されて記載されている。
すなわち、各セレクタ群は、出力側から数えてｎ段分のセレクタは、２：１セレクタをｎ段接続するのではなく、２n：１セレクタ２１０（２n個の２入力ＡＮＤと１個の入力ＯＲで構成）を１個用いた回路である。
具体的には、出力側ｎ段分について、共有しているセレクタがあれば、その共有をなくした上で、各セレクタをまとめて２n：１セレクタ２１０に置換する。ここで、２n：１セレクタ２１０は、２入力ＡＮＤと２n入力ＯＲを結合した選択回路２１１と、当該ｎ段分のプライマリ入力を選択回路２１１への入力に置換するためのｎビットバイナリから２nビットワンホットへのデコーダ２１２とを備える（図３では単にデコーダと表記）。このデコーダ２１２は、２n本の入力のうちどれをセレクトするかを決定するセレクト信号の生成回路である。また、セレクタの共有をなくすには、当該共有しているセレクタを複製すればよい。
なお、ｎの具体的な値については任意に設定することができるが、高速化の効果を最大化するため、次のようにして決めることができる。すなわち、出力から数えてｎ段目のセレクタ数が２(n-1)個かそれに近い値であり、なおかつ、ｎビットバイナリから２nビットワンホットへのデコーダ２１２の遅延がプライマリ入力から出力側ｎ＋１段目セレクタまでの遅延以下であるようなｎの場合、ｎ段の２：１セレクタを２入力ＡＮＤと２n入力ＯＲを結合した選択回路２１１に置換することによって、回路の高速化を図ることができる。これによれば、例えばＡＥＳでは、ｎの値は４または５となる。
【００２４】
かかる構造によって、出力側のセレクタ部分を、単に２：１セレクタをｎ段つなぐよりも高速化する。残りのセレクタについては、通常通り２：１セレクタで構成しても良いし、可能ならば、上記のｎと同様にして求められたｋ段分のセレクタを、さらに２k：１セレクタに置き換えて構成しても良い。
【００２５】
また、各セレクタ群を、各セレクタを論理否定出力のセレクタに置換し、負論理出力のセレクタと正論理出力のセレクタを、入力から出力に向かって交互に配置した回路構造とすることにより、組合せ回路のさらなる高速化を図ることができる場合がある。ＣＭＯＳ等では正論理出力のセレクタよりも負論理出力のセレクタの方が高速な場合が多いからである。
【００２６】
なお、上述した組合せ回路の構造において、図２に示したドライバチェイン３００〜３７０によるセレクト信号の入力の分配と、図３に示したセレクタ群におけるｎ段分のセレクタの置換は、両方を採用しても良いし、いずれか一方のみを用いても良い。すなわち、図１に示したセレクタ群の内部構造を、従来の２：１セレクタのみからなる構成としても良い。また、出力ビットごとに独立したセレクタ群１００〜１７０を有しない場合でも、少なくとも出力側のｎ段のセレクタが出力ビットに対応した一群ごとに独立し当該一群どうしの間でセレクタの共有がない場合に、このｎ段のセレクタを２n：１セレクタ２１０で置き換えた構成としても良い。いずれか一方の回路構造を用いた場合でも、従来の論理合成アルゴリズムにより作成されたＲＯ−ＢＤＤに基づく組合せ回路よりも高速な回路が実現されるが、両方の回路構造を用いることによって、一層の高速化を図ることが可能となる。
【００２７】
次に、Ｓ−Ｂｏｘの組合せ回路を作成するために、上記の回路構造を規定するためのＲＯ−ＢＤＤを作る論理合成アルゴリズムについて説明する。
ここで、ＲＯ−ＢＤＤを作成するためには、組合せ回路の真理値表または論理式からＲＯ−ＢＤＤのグラフを構成するアルゴリズムが不可欠であるが、このアルゴリズム自体は公知なので、ここでは詳細は省略する。かかるグラフ構成アルゴリズムを利用して、上述したＳ−Ｂｏｘの組合せ回路アーキテクチャを自動合成するアルゴリズムを、以下に説明する。
【００２８】
図４は、本実施の形態によるＲＯ−ＢＤＤを作成するための論理合成アルゴリズムを説明するフローチャートである。
なお、この論理合成アルゴリズムに基づくＲＯ−ＢＤＤの作成は、パーソナルコンピュータやワークステーション、その他のコンピュータ装置にて実行される。コンピュータ装置は、各種のデータ処理を実行するＣＰＵ（Central Processing Unit）と、ＣＰＵを制御するプログラム及び各種のデータを格納したメモリとを備える。
この論理合成アルゴリズムにおいて、入力は、各種Ｓ−Ｂｏｘの真理値表または論理式である。ここで、論理式の形式は任意である。また、出力は、上記の回路構造（セレクタの接続関係）に対応する論理式である。したがって、ＣＰＵは、処理対象としてメモリに格納されているＳ−Ｂｏｘの真理値表または論理式を読み出し、上記の回路構造に対応する真理値表または論理式を生成し、メモリに格納する。なお、以下の説明では、真理値表及び論理式を総括して論理式と称する。
【００２９】
図４を参照すると、ＣＰＵは、メモリから処理対象であるＳ−Ｂｏｘの論理式を読み込んで、出力ビットごとに分割し、出力１ビット分の論理式（以下、単位論理式と称す）を生成する（ステップ４０１）。
次にＣＰＵは、ステップ４０１で分割した各単位論理式に対して、順次、次の一連の処理を行う。
すなわち、まず、１つの単位論理式を処理対象とし、ＲＯ−ＢＤＤの変数順を決定する（ステップ４０２）。この変数順は、既に当該処理が行われた単位論理式に用いた変数順とは異なるもの（未使用の変数順）とする。次に、決定された変数順で、当該単位論理式について、共有可能なノードを共有させたＲＯ−ＢＤＤ（Shared-RO-BDD）を構築する（ステップ４０３）。次に、作成されたＲＯ−ＢＤＤ（Shared-RO-BDD）のルート側のｎ段分について、共有しているノードを個々のノードに分けたＲＯ−ＢＤＤ（Unshared-RO-BDD）に変換する（ステップ４０４）。この共有しているノードを分けたＲＯ−ＢＤＤの部分（Unshared-RO-BDD）は、完全木（完全二分木）となる。次に、ＲＯ−ＢＤＤノードのルート側ｎ段分をまとめて２n：１セレクタにマップし（ステップ４０５）、残りのＲＯ−ＢＤＤノードを２：１セレクタにマップする（ステップ４０６）。
【００３０】
上記ステップ４０２乃至ステップ４０６の処理を、全ビット分の単位論理式に対して行ったならば、次にＣＰＵは、各プライマリ入力に対してドライバチェインを作り、ＲＯ−ＢＤＤの制御信号とつなぐ（ステップ４０７、４０８）。このとき、ＲＯ−ＢＤＤの入力側（リーフ側）のノード（セレクタ）をドライブする信号はチェインの入力側から取り、ＲＯ−ＢＤＤの出力側（ルート側）をドライブする信号はチェインの出力側から取る。
【００３１】
以上のようにして、図１乃至図３に示した回路構造を有する組合せ回路が生成される。なお、ステップ４０４〜４０６の処理は、図３に示した各セレクタ群の構成を実現するための処理であり、個々のセレクタ群において図３に示した回路構造を採らない場合は、これらの処理は不要である。
【００３２】
本実施の形態の回路構造が有効な組合せ回路は、セレクタ接続構造（ＲＯ−ＢＤＤの構造）が、
・回路の出力側では、出力間ないし同一出力のセレクタ群においてセレクタがほとんど共有されていない。
・全体的なセレクタ結合の形が、入力のビット順にほとんど依存せず、どのようなビット順でも上記特徴１を有する形になる。
といった特徴を持つ回路であり、その代表例が各種Ｓ−Ｂｏｘや、その他の乱数テーブルを含む組合せ回路である。
【００３３】
【発明の効果】
以上説明したように、本発明によれば、Ｓ−Ｂｏｘなどを高速な組合せ回路として実現すると共に、かかる組合せ回路の回路構造を規定するＲＯ−ＢＤＤを作成する好適な手法を提供することができる。
【図面の簡単な説明】
【図１】 本実施の形態によるＳ−Ｂｏｘの組合せ回路の構成を示す図である。
【図２】 本実施の形態に用いられるドライバチェインの構成及びドライバチェインによるセレクト信号の入力の分配を示す図である。
【図３】 図１に示した各出力ビットに対応するセレクタ群の構成を示す図である。
【図４】 本実施の形態によるＲＯ−ＢＤＤを作成するための論理合成アルゴリズムを説明するフローチャートである。
【図５】 従来の論理合成アルゴリズムにて作成されたＲＯ−ＢＤＤに基づく、Ｓ−Ｂｏｘの組合せ回路の構成例を示す図である。
【符号の説明】
１００、１１０、１７０…セレクタ群、１０１…セレクタ（２：１セレクタ）、２１０…２n：１セレクタ、２１１…選択回路、２１２…デコーダ、３００、３１０、３７０…ドライバチェイン
【発明の属する技術分野】
本発明は、組合せ回路の構成及びその論理合成方法に関し、とくに暗号回路に用いられるＳ−Ｂｏｘなどの組合せ回路の構成及びその論理合成方法に関する。
【０００２】
【従来の技術】
コンピュータネットワークによる情報通信、特に公衆ネットワークを専用線のように利用するＶＰＮ（Virtual Private Network）通信においては、暗号技術が必要不可欠である。そして、情報通信の高速化に伴って、より高速な暗号技術が要求される。
【０００３】
今日、コンピュータネットワークで用られている主要な暗号技術である共通鍵暗号として、ＤＥＳ（Data Encryption Standard）やＡＥＳ（Advanced Encryption Standard）、Camelliaなどが存在するが、この暗号技術を実現する論理回路（暗号回路）には、いずれもＳ−Ｂｏｘと呼ばれる非線形変換部が存在している。そして、このＳ−Ｂｏｘの処理速度は、論理回路自体の処理速度に大きく影響する。
【０００４】
ここで、共通鍵暗号におけるＳ−Ｂｏｘ演算とその回路構成法について説明する。なお、ここではＡＥＳのＳ−Ｂｏｘを例に説明する。
ＡＥＳにおけるＳ−Ｂｏｘは、８ビット入力に対し、まず（ｉ）既約多項式ｘ8＋ｘ4＋ｘ3＋ｘ＋１により構成されたＧＦ（２8）上での乗法逆元演算を適用し、続いて（ｉｉ）下記数１式のAffine変換を適用して８ビット値を出力する。
【数１】
【０００５】
このＳ−Ｂｏｘの回路実装の手法には、（１）上記の定義に従ってＧＦ逆元演算回路とAffine変換回路とを別々に作ってから直列につなぐ方法と、（２）入出力関係（真理値表）から直接回路を導出する方法とがある。
（１）の場合、フェルマーの小定理Ｐ-1＝Ｐ254（ＧＦ(２8)の場合）を用いて計算する方法、拡張ユークリッド法を用いて計算する方法、及び合成体（composite field）上の逆元演算に帰着する方法がある。しかし、これらのいずれも高速実装には向いておらず、（２）の方法の数倍程度の回路遅延が生ずる。なお、これらの手法については、例えば下記文献１、２に詳細に記載されている。
文献１：S.Morioka and Y.Katayama, "O(log2m) Iterative Algorithm for Multiplicative Inverse in GF(2m)," IEEE Intl. Symp. On Info. Theory (ISIT2000), pp.449, 2000.
文献２：A.Satoh, S.Morioka, K.Takano and S.Munetoh, "Compact Rijndael Hardware Architecture with S-Box Optimization," ASIACRYPT2001, 2001.
一方、（２）の場合、積和形、和積形、各種リード・マラー形式の論理式を構成する方法や、各種関数展開を行う方法が知られている。
【０００６】
次に、組合せ回路の汎用論理合成アルゴリズムについて説明する。
関数展開を用いた論理構成法の１つとして、ＲＯ−ＢＤＤ（Reduced Ordered Binary Decision Diagrams）を用いる方法が知られている。ＲＯ−ＢＤＤは、論理関数の表現形式の１つであり、一定の変数順で論理関数をＳｈａｎｎｏｎ展開していく過程を、閉路なしの二分決定グラフとして表現したうえで冗長ノードを除去したものである。このＲＯ−ＢＤＤの各ノードを２：１セレクタ（ＭＵＸ：マルチプレクサ）に置き換えることにより、ＲＯ−ＢＤＤの回路化を行うことができる。かかるＲＯ−ＢＤＤを用いた論理構成法については、例えば下記文献３に詳細に記載されている。
文献３：R.E.Bryant；Graph-Based Algorithms for Boolean Function Manipulation, IEEE transactions on computers, Vol.C-25, No.8, 1986.
ＲＯ−ＢＤＤのグラフ構造と得られる回路構造（＝セレクタの接続関係）とはほぼ１対１に対応するので、どのような形のＲＯ−ＢＤＤを構成するかを決めることが回路構造を規定する。与えられた論理関数に対するＲＯ−ＢＤＤは１通りではなく、ノード共有をどのように行うか、あるいは変数順をどうするかに設計自由度がある。
【０００７】
図５は、従来の論理合成アルゴリズムにて作成されたＲＯ−ＢＤＤに基づく、ＡＥＳのＳ−Ｂｏｘの構成例を示す図である。なお、図５において、組合せ回路を構成するセレクタ及び各段のセレクタどうしの接続は、適宜省略されて記載されている。
図５に示すように、従来の論理合成アルゴリズムにより作成されたＲＯ−ＢＤＤに基づくＳ−Ｂｏｘの組合せ回路は、一般の論理関数にはない、次のような大きな特徴がある。
特徴１：回路の出力側では、出力間ないし同一出力のセレクタ群においてセレクタがほとんど共有されていない。共有がなされているのは回路入力側の１、２段のみである。すなわち、出力側から入力側に行くにつれセレクタ数が１＊８、２＊８、４＊８、８＊８、・・・と指数的に増えていき（そのとき、ほぼ全てのセレクタで、その出力のファンアウトは１）、入力側の最後の１、２段では各セレクタ出力のファンアウトが急に大きくなる（３０前後）。これに対し、一般の多くの論理関数では、より出力に近い段まで多くのセレクタが共有されるため、図５のような木構造にはならない。また、出力間で多くのノードを共有できるのが普通である。
特徴２：全体的なセレクタ結合の形が、入力のビット順（入力の何ビット目が、何段目のセレクタをドライブするか）にほとんど依存せず、どのようなビット順でも上記特徴１を有する形になる。これに対し、一般の多くの論理関数では、入力ビット順を変えると回路の全体的な形は非常に大きく変化する。
【０００８】
【発明が解決しようとする課題】
上述したように、従来、ＲＯ−ＢＤＤを用いて回路構造を規定し、組合せ回路をデザインすることが行われていた。一方、Ｓ−Ｂｏｘとして最も高速なものは、Ｓ−Ｂｏｘの真理値表から自動論理合成で得られる回路であったが、Ｓ−Ｂｏｘは乱数テーブルに近い入出力定義を有するため、汎用の論理合成手法との相性は良くない。そのため、上記の暗号技術の用途などにおいて十分な速度を得ることができなかった。
【０００９】
すなわち、ＲＯ−ＢＤＤを用いて回路構造を規定する手法でＳ−Ｂｏｘのような組合せ回路をデザインすると、従来の論理合成アルゴリズムにより作成されたＲＯ−ＢＤＤは、上述した特徴１、２を有するため、高速回路を設計する上で、次の２点が問題となっていた。
（１）回路の入力側セレクタのセレクト信号・出力データ信号のファンアウトが大きくなること（たとえば図５では、入力から２段目のセレクタは１４９個あるので、そのセレクト信号のドライブは非常に重い。また、入力から１段目の各セレクタ出力は、２段目セレクタの入力信号を３０本近くドライブしなければならず、これも非常に重い）。
（２）セレクタを直列に多段つないだ回路となるため、信号通過時間が長くなること。
【００１０】
そこで本発明は、上記の課題を解決し、高速なＳ−Ｂｏｘなどの組合せ回路を実現すると共に、かかる組合せ回路の回路構造を規定するＲＯ−ＢＤＤを作成する手法を提供することを目的とする。
【００１１】
【課題を解決するための手段】
上記の目的を達成するため、本発明は、複数個のセレクタにて構成される次のような組合せ回路として実現される。すなわち、この組合せ回路は、出力ビットを個別に生成する、出力ビット数に対応する数の独立したセレクタ群と、各セレクタ群にプライマリ入力を供給するドライバとを備え、各セレクタ群は、プライマリ入力のビット数以下の数の段を形成して接続された複数個のセレクタを備え、各段のセレクタのセレクト信号が１つのプライマリ入力でドライブされることを特徴とする。
【００１２】
ここで詳細には、このドライバは、入力ビットごとに、バッファまたはインバータを連鎖的につなげて設けられたドライバチェインにて構成される。そして、各ドライバチェインは、入力側からバッファまたはインバータを経て出力側へ進むと共に相異なる順番でセレクタ群に接続され、このセレクタ群を構成するセレクタの各段にセレクト信号を供給する。これにより、各セレクタ群におけるｉ段目セレクタ（全段数≧ｉ≧１）のセレクト信号を制御するプライマリ入力が各セレクタ群で異なり、さらに各段に入力されるセレクト信号の順番がセレクタ群ごとに異なることとなる。
【００１３】
また、本発明による他の組合せ回路は、プライマリ入力のビット数以下の段数分の２：１セレクタが相互に接続され、かつ少なくとも出力側の所定数ｎ段分の２：１セレクタにおいて、複数の出力ビットを生成する２：１セレクタの一群どうしの間でこの２：１セレクタが共有されていないことを条件に、このｎ段分の２：１セレクタを置き換えて設けられた２n：１セレクタと、この２n：１セレクタに置き換えられた残りの２：１セレクタとを備える。そして、この２n：１セレクタは、２n本の入力のうちどれをセレクトするかを決定するセレクト信号を生成する生成回路と、この生成回路にて生成されたセレクト信号を用いて２n本の入力のうち一本を選び出すための選択回路とを備えることを特徴とする。
さらに、上述した出力ビット数に対応する数の独立したセレクタ群を有する組合せ回路において、このセレクタ群を構成する２：１セレクタに対して、このような２n：１セレクタへの置き換えを行うことができる。
【００１４】
また、上記の目的を達成する他の本発明は、ＲＯ−ＢＤＤを用いた組合せ回路の生成方法として、次のように実現される。すなわち、この組合せ回路の生成方法は、まず、出力ビット数に対応する数のＲＯ−ＢＤＤであって、このＲＯ−ＢＤＤ間でノードを共有せず、かつ各ＲＯ−ＢＤＤにおける変数順が相互に異なるＲＯ−ＢＤＤの一群を生成する。そして、各ＲＯ−ＢＤＤの各ノードをセレクタに置き換える。さらに、各セレクタの制御信号を生成するためのドライバチェインを作り、このＲＯ−ＢＤＤに基づくセレクタの段と、このドライバチェインとを対応させて、セレクタとドライバチェインとを接続することを特徴とする。
【００１５】
さらに本発明による組合せ回路の他の生成方法は、まず、出力側の所定数ｎ段分のノードが出力ビット数に対応する数の完全木の構造を有するＲＯ−ＢＤＤを生成する。次に、このＲＯ−ＢＤＤにおけるｎ段分のノードを、２n本の入力のうちどれをセレクトするかを決定するセレクト信号を生成する生成回路と当該セレクト信号を用いて２n本の入力のうち一本を選び出すための選択回路とを備えた２n：１セレクタに置き換え、他のノードを２：１セレクタに置き換えることを特徴とする。
【００１６】
さらにまた、本発明は、コンピュータを制御して、組合せ回路の回路構造を論理合成する次のようなプログラムとしても実現される。このプログラムは、処理対象である組合せ回路の論理式または真理値表を出力ビットごとに分割し、出力１ビット分の論理式または真理値表を生成する処理と、この出力１ビット分の論理式または真理値表ごとに、他の論理式または真理値表と重複しないようにＲＯ−ＢＤＤの変数順を決定し、決定された変数順で論理式または真理値表のShared-RO-BDDを構築し、その各ノードを２：１セレクタにマップする処理と、この各２：１セレクタの制御信号を生成するためのドライバチェインを作り、ＲＯ−ＢＤＤの制御信号とつなぐ処理とをコンピュータに実行させることを特徴とする。そして、さらに詳細には、ＲＯ−ＢＤＤに対してセレクタをマッピングする際に、Shared-RO-BDDのルート側の所定数ｎ段をUnshared-RO-BDDに変換する処理と、このUnshared-RO-BDDに変換されたｎ段分のノードを２n：１セレクタにマップする処理と、他のノードを２：１セレクタにマップする処理とをコンピュータに実行させる。
【００１７】
上述したプログラムは、磁気ディスクや光ディスク、半導体メモリ、その他の記録媒体に格納して配布したり、ネットワークを介して配信したりすることにより提供することができる。
また、本発明は、Ｓ−Ｂｏｘとして上述した組合せ回路を含む暗号回路として実現することができる。
【００１８】
【発明の実施の形態】
以下、添付図面に示す実施の形態に基づいて、この発明を詳細に説明する。
本実施の形態では、Ｓ−Ｂｏｘなどの組合せ回路において、次の２つの課題を実現する。
１．回路のプライマリ入力側セレクタ群の制御信号乃至出力信号について、それらのファンアウトを減少させる。
２．回路のプライマリ出力側の部分における通過ディレイ（遅延）を、単純にセレクタを多段接続した回路よりも減少させる。
【００１９】
図１は、上記の課題が解決された、本実施の形態によるＳ−Ｂｏｘの組合せ回路の構成を示す図である。
図１を参照すると、この組合せ回路は、複数個のセレクタ１０１をｍ段以下（ｍはプライマリ入力のビット数）の段数分接続し、所定の１段を形成するセレクタのセレクト信号が１つのプライマリ入力でドライブされる構造を有する。すなわち、Ｓ−ＢｏｘのＲＯ−ＢＤＤの各ノードを２：１セレクタで置換して得られる回路である。例えば、１段目のセレクタは全て入力ビット０でドライブされ、２段目は全て入力ビット１でドライブされるようにする（これ以降の段数においても同様）。言い換えれば、真理値表から得られるＲＯ−ＢＤＤの各節点（ノード）をそのままセレクタに置換し、各セレクタをＲＯ−ＢＤＤの枝の通りに接続した構造の回路である。
なお、図１において、各セレクタ群１００を構成するセレクタ１０１及び各段のセレクタ１０１どうしの接続は、適宜省略されて記載されている。
【００２０】
また、図１に示す組合せ回路は、各出力ビットが別々のセレクタ群１００〜１７０で作られており、それらの間でセレクタを一切共有していない。すなわち、各セレクタ群１００〜１７０は独立している。そして、ｉ段目セレクタ（全段数≧ｉ≧１）のセレクト信号を制御するプライマリ入力が各セレクタ群１００〜１７０で異なっている。
例えば、図１の例では、出力ビット０を作る回路（セレクタ群１００）では、１段目セレクタが入力ビット０（図１に示す信号００）、２段目セレクタが入力ビット１（信号０１）で制御されている（以下同様に、順次、信号０２、０３・・・で制御される）。そして、出力ビット１を作る回路（セレクタ群１１０）では、１段目セレクタが入力ビット０ではなく入力ビット１（信号１１）で制御されており、以下順次、２段目セレクタが入力ビット２（信号１２）で制御されるというように、各段におけるセレクト信号の順番がローテートされている。
なお、ここでは、セレクト信号（入力ビット）の順番が各セレクタ群１００〜１７０で異なることによって負荷分散されていれば良く、図１に示したローテートされた順番に限らないことは言うまでもない。
【００２１】
また、本実施の形態の組合せ回路は、図１に示したセレクタ群１００〜１７０にプライマリ入力を供給するドライバを備える。本実施の形態では、バッファまたはインバータを連鎖させたドライバチェインが用いられる。
図２は、ドライバチェインの構成及びドライバチェインによるセレクト信号の入力の分配を示す図である。
図２を参照すると、このドライバチェイン３００〜３７０は、バッファまたはインバータを連鎖的につなげて構成されており、入力ビット（０〜７）ごとに用意されている。そして、ドライバチェイン３００〜３７０の構成と上述したセレクタ群１００〜１７０におけるセレクタの段とを対応させ、各段のセレクタをドライブする制御信号を供給する。ここで、ドライバチェイン３００〜３７０とセレクタ群１００〜１７０との接続関係は、セレクタ群１００〜１７０における入力側セレクタの制御信号はチェインの入力側から取り、出力側セレクタの制御信号はチェインの出力側から取るようになっている。さらに上述したように、各セレクタ群１００〜１７０においてセレクト信号（入力ビット）の順番が異なるように接続されている。
例えば、入力ビット０を供給するドライバチェイン３００（図２参照）は、最も入力側において、図１に示したセレクタ群１００に接続され、信号００を供給する。そして、バッファまたはインバータを経て出力側へ進むと共に順次セレクタ群１７０、１６０、・・・、１１０に接続され、信号７０、６０、・・・、１０を供給する。同様にして、他のドライバチェイン３１０〜３７０も、異なる順番でセレクタ群１００〜１７０に接続されることにより、各セレクタ群１００〜１７０において、段ごとのセレクタに対するセレクト信号の順番が異なることとなり、セレクト信号を供給する上での負荷を分散することができる。
【００２２】
かかる構造によって、セレクト信号のファンアウトや各セレクタの出力信号のファンアウトが減少する。例えば、図１に示した個々のセレクタ群１００〜１７０では、２段目のセレクタは３０個程度となり、図５に示した１４９個のセレクタがある場合と比べて、セレクト信号のドライブが大幅に軽くなる。また、前段セレクタのファンアウトも２〜５程度に減少する。さらに、ドライバチェインを通すことによって、各セレクト信号のファンアウトが減少する（２〜５程度）。これにより、高速な回路が実現される。
なお、図２に示したドライバチェイン３００〜３７０の入力から出力に向かって正論理のセレクト信号と負論理の制御信号が交互に現れるようにし、負論理の信号で制御されるセレクタについては、その２つのデータ信号入力を入れ替えるように構成することができる。このような構成とすることにより、組合せ回路のさらなる高速化を図ることができる場合がある。ＣＭＯＳではバッファを用いるよりもインバータを用いた方が通常は高速だからである。
【００２３】
図３は、図１に示した各出力ビットに対応するセレクタ群の構成を示す図である。
図３を参照すると、本実施の形態による組合せ回路は、各セレクタ群において、さらに次のような構成を有する。なお、図３において、各セレクタ１０１及び各段のセレクタ１０１どうしの接続は、適宜省略されて記載されている。
すなわち、各セレクタ群は、出力側から数えてｎ段分のセレクタは、２：１セレクタをｎ段接続するのではなく、２n：１セレクタ２１０（２n個の２入力ＡＮＤと１個の入力ＯＲで構成）を１個用いた回路である。
具体的には、出力側ｎ段分について、共有しているセレクタがあれば、その共有をなくした上で、各セレクタをまとめて２n：１セレクタ２１０に置換する。ここで、２n：１セレクタ２１０は、２入力ＡＮＤと２n入力ＯＲを結合した選択回路２１１と、当該ｎ段分のプライマリ入力を選択回路２１１への入力に置換するためのｎビットバイナリから２nビットワンホットへのデコーダ２１２とを備える（図３では単にデコーダと表記）。このデコーダ２１２は、２n本の入力のうちどれをセレクトするかを決定するセレクト信号の生成回路である。また、セレクタの共有をなくすには、当該共有しているセレクタを複製すればよい。
なお、ｎの具体的な値については任意に設定することができるが、高速化の効果を最大化するため、次のようにして決めることができる。すなわち、出力から数えてｎ段目のセレクタ数が２(n-1)個かそれに近い値であり、なおかつ、ｎビットバイナリから２nビットワンホットへのデコーダ２１２の遅延がプライマリ入力から出力側ｎ＋１段目セレクタまでの遅延以下であるようなｎの場合、ｎ段の２：１セレクタを２入力ＡＮＤと２n入力ＯＲを結合した選択回路２１１に置換することによって、回路の高速化を図ることができる。これによれば、例えばＡＥＳでは、ｎの値は４または５となる。
【００２４】
かかる構造によって、出力側のセレクタ部分を、単に２：１セレクタをｎ段つなぐよりも高速化する。残りのセレクタについては、通常通り２：１セレクタで構成しても良いし、可能ならば、上記のｎと同様にして求められたｋ段分のセレクタを、さらに２k：１セレクタに置き換えて構成しても良い。
【００２５】
また、各セレクタ群を、各セレクタを論理否定出力のセレクタに置換し、負論理出力のセレクタと正論理出力のセレクタを、入力から出力に向かって交互に配置した回路構造とすることにより、組合せ回路のさらなる高速化を図ることができる場合がある。ＣＭＯＳ等では正論理出力のセレクタよりも負論理出力のセレクタの方が高速な場合が多いからである。
【００２６】
なお、上述した組合せ回路の構造において、図２に示したドライバチェイン３００〜３７０によるセレクト信号の入力の分配と、図３に示したセレクタ群におけるｎ段分のセレクタの置換は、両方を採用しても良いし、いずれか一方のみを用いても良い。すなわち、図１に示したセレクタ群の内部構造を、従来の２：１セレクタのみからなる構成としても良い。また、出力ビットごとに独立したセレクタ群１００〜１７０を有しない場合でも、少なくとも出力側のｎ段のセレクタが出力ビットに対応した一群ごとに独立し当該一群どうしの間でセレクタの共有がない場合に、このｎ段のセレクタを２n：１セレクタ２１０で置き換えた構成としても良い。いずれか一方の回路構造を用いた場合でも、従来の論理合成アルゴリズムにより作成されたＲＯ−ＢＤＤに基づく組合せ回路よりも高速な回路が実現されるが、両方の回路構造を用いることによって、一層の高速化を図ることが可能となる。
【００２７】
次に、Ｓ−Ｂｏｘの組合せ回路を作成するために、上記の回路構造を規定するためのＲＯ−ＢＤＤを作る論理合成アルゴリズムについて説明する。
ここで、ＲＯ−ＢＤＤを作成するためには、組合せ回路の真理値表または論理式からＲＯ−ＢＤＤのグラフを構成するアルゴリズムが不可欠であるが、このアルゴリズム自体は公知なので、ここでは詳細は省略する。かかるグラフ構成アルゴリズムを利用して、上述したＳ−Ｂｏｘの組合せ回路アーキテクチャを自動合成するアルゴリズムを、以下に説明する。
【００２８】
図４は、本実施の形態によるＲＯ−ＢＤＤを作成するための論理合成アルゴリズムを説明するフローチャートである。
なお、この論理合成アルゴリズムに基づくＲＯ−ＢＤＤの作成は、パーソナルコンピュータやワークステーション、その他のコンピュータ装置にて実行される。コンピュータ装置は、各種のデータ処理を実行するＣＰＵ（Central Processing Unit）と、ＣＰＵを制御するプログラム及び各種のデータを格納したメモリとを備える。
この論理合成アルゴリズムにおいて、入力は、各種Ｓ−Ｂｏｘの真理値表または論理式である。ここで、論理式の形式は任意である。また、出力は、上記の回路構造（セレクタの接続関係）に対応する論理式である。したがって、ＣＰＵは、処理対象としてメモリに格納されているＳ−Ｂｏｘの真理値表または論理式を読み出し、上記の回路構造に対応する真理値表または論理式を生成し、メモリに格納する。なお、以下の説明では、真理値表及び論理式を総括して論理式と称する。
【００２９】
図４を参照すると、ＣＰＵは、メモリから処理対象であるＳ−Ｂｏｘの論理式を読み込んで、出力ビットごとに分割し、出力１ビット分の論理式（以下、単位論理式と称す）を生成する（ステップ４０１）。
次にＣＰＵは、ステップ４０１で分割した各単位論理式に対して、順次、次の一連の処理を行う。
すなわち、まず、１つの単位論理式を処理対象とし、ＲＯ−ＢＤＤの変数順を決定する（ステップ４０２）。この変数順は、既に当該処理が行われた単位論理式に用いた変数順とは異なるもの（未使用の変数順）とする。次に、決定された変数順で、当該単位論理式について、共有可能なノードを共有させたＲＯ−ＢＤＤ（Shared-RO-BDD）を構築する（ステップ４０３）。次に、作成されたＲＯ−ＢＤＤ（Shared-RO-BDD）のルート側のｎ段分について、共有しているノードを個々のノードに分けたＲＯ−ＢＤＤ（Unshared-RO-BDD）に変換する（ステップ４０４）。この共有しているノードを分けたＲＯ−ＢＤＤの部分（Unshared-RO-BDD）は、完全木（完全二分木）となる。次に、ＲＯ−ＢＤＤノードのルート側ｎ段分をまとめて２n：１セレクタにマップし（ステップ４０５）、残りのＲＯ−ＢＤＤノードを２：１セレクタにマップする（ステップ４０６）。
【００３０】
上記ステップ４０２乃至ステップ４０６の処理を、全ビット分の単位論理式に対して行ったならば、次にＣＰＵは、各プライマリ入力に対してドライバチェインを作り、ＲＯ−ＢＤＤの制御信号とつなぐ（ステップ４０７、４０８）。このとき、ＲＯ−ＢＤＤの入力側（リーフ側）のノード（セレクタ）をドライブする信号はチェインの入力側から取り、ＲＯ−ＢＤＤの出力側（ルート側）をドライブする信号はチェインの出力側から取る。
【００３１】
以上のようにして、図１乃至図３に示した回路構造を有する組合せ回路が生成される。なお、ステップ４０４〜４０６の処理は、図３に示した各セレクタ群の構成を実現するための処理であり、個々のセレクタ群において図３に示した回路構造を採らない場合は、これらの処理は不要である。
【００３２】
本実施の形態の回路構造が有効な組合せ回路は、セレクタ接続構造（ＲＯ−ＢＤＤの構造）が、
・回路の出力側では、出力間ないし同一出力のセレクタ群においてセレクタがほとんど共有されていない。
・全体的なセレクタ結合の形が、入力のビット順にほとんど依存せず、どのようなビット順でも上記特徴１を有する形になる。
といった特徴を持つ回路であり、その代表例が各種Ｓ−Ｂｏｘや、その他の乱数テーブルを含む組合せ回路である。
【００３３】
【発明の効果】
以上説明したように、本発明によれば、Ｓ−Ｂｏｘなどを高速な組合せ回路として実現すると共に、かかる組合せ回路の回路構造を規定するＲＯ−ＢＤＤを作成する好適な手法を提供することができる。
【図面の簡単な説明】
【図１】 本実施の形態によるＳ−Ｂｏｘの組合せ回路の構成を示す図である。
【図２】 本実施の形態に用いられるドライバチェインの構成及びドライバチェインによるセレクト信号の入力の分配を示す図である。
【図３】 図１に示した各出力ビットに対応するセレクタ群の構成を示す図である。
【図４】 本実施の形態によるＲＯ−ＢＤＤを作成するための論理合成アルゴリズムを説明するフローチャートである。
【図５】 従来の論理合成アルゴリズムにて作成されたＲＯ−ＢＤＤに基づく、Ｓ−Ｂｏｘの組合せ回路の構成例を示す図である。
【符号の説明】
１００、１１０、１７０…セレクタ群、１０１…セレクタ（２：１セレクタ）、２１０…２n：１セレクタ、２１１…選択回路、２１２…デコーダ、３００、３１０、３７０…ドライバチェイン
Claims (11)
- 複数個のセレクタにて構成される組合せ回路において、
出力ビットを個別に生成する、出力ビット数に対応する数の独立したセレクタ群と、
前記各セレクタ群にプライマリ入力を供給するドライバとを備え、
前記各セレクタ群は、
前記プライマリ入力のビット数以下の数の段を形成して接続された複数個のセレクタを備え、
各段の前記セレクタのセレクト信号が１つの前記プライマリ入力でドライブされ、
ｉ段目のセレクタ（全段数≧ｉ≧１）のセレクト信号を制御するプライマリ入力が個々の前記セレクタ群で異なり、かつ、個々のプライマリ入力によりセレクト信号を制御されるセレクタが前記セレクタ群ごとに異なっていることを特徴とする組合せ回路。 - 前記ドライバは、入力ビットごとに、バッファまたはインバータを連鎖的につなげて設けられたドライバチェインであり、
前記各ドライバチェインは、入力側からバッファまたはインバータを経て出力側へ進むと共に、当該各ドライバチェインにおける個々のバッファまたはインバータの出力が相異なる順番で前記各セレクタ群に接続され、前記セレクタ群を構成するセレクタの各段にセレクト信号を供給することを特徴とする請求項１に記載の組合せ回路。 - 前記各セレクタ群における出力側から所定数ｎ段分の２：１セレクタが、２n：１セレクタに置き換えられており、
前記２n：１セレクタは、
２n本の入力のうちどれをセレクトするかを決定するセレクト信号を生成する生成回路と、
前記生成回路にて生成されたセレクト信号を用いて２n本の入力のうち一本を選び出すための選択回路と
を備えることを特徴とする請求項１に記載の組合せ回路。 - Ｓ−Ｂｏｘを含む暗号回路において、
前記Ｓ−Ｂｏｘに対応する組合せ回路は、
出力ビットを個別に生成する当該出力ビット数に対応する数の独立したセレクタ群と、
前記各セレクタ群にプライマリ入力を供給するドライバとを備え、
前記各セレクタ群は、
プライマリ入力のビット数以下の数の段を形成して接続された複数個のセレクタを備え、
各段の前記セレクタのセレクト信号が１つの前記プライマリ入力でドライブされ、
ｉ段目のセレクタ（全段数≧ｉ≧１）のセレクト信号を制御するプライマリ入力が個々の前記セレクタ群で異なり、かつ、個々のプライマリ入力によりセレクト信号を制御されるセレクタが前記セレクタ群ごとに異なっていることを特徴とする暗号回路。 - 前記ドライバは、入力ビットごとに、バッファまたはインバータを連鎖的につなげて設けられたドライバチェインであり、
前記各ドライバチェインは、入力側からバッファまたはインバータを経て出力側へ進むと共に、当該各ドライバチェインにおける個々のバッファまたはインバータの出力が相異なる順番で前記各セレクタ群に接続され、前記セレクタ群を構成するセレクタの各段にセレクト信号を供給することを特徴とする請求項４に記載の暗号回路。 - 前記各セレクタ群における出力側から所定数ｎ段分の２：１セレクタが、２n：１セレクタに置き換えられており、
前記２n：１セレクタは、
２n本の入力のうちどれをセレクトするかを決定するセレクト信号を生成する生成回路と、
前記生成回路にて生成されたセレクト信号を用いて２n本の入力のうち一本を選び出すための選択回路と
を備えることを特徴とする請求項４に記載の暗号回路。 - ＲＯ−ＢＤＤ（Reduced Ordered Binary Decision Diagrams）を用いた組合せ回路の生成方法において、
出力ビット数に対応する数のＲＯ−ＢＤＤであって、当該ＲＯ−ＢＤＤ間でノードを共有せず、かつ各ＲＯ−ＢＤＤにおける変数順が相互に異なるＲＯ−ＢＤＤの一群を生成し、
前記各ＲＯ−ＢＤＤの各ノードをセレクタに置き換え、
前記各セレクタの制御信号を生成するためのドライバチェインを作り、当該ドライバチェインの各出力を、前記ＲＯ−ＢＤＤに基づく各セレクタ群を構成する各段のセレクタに対して、各セレクタ群で相異なる順番となるように接続することを特徴とする組合せ回路の生成方法。 - コンピュータを制御して、組合せ回路の回路構造を論理合成するプログラムであって、
メモリから処理対象である組合せ回路の論理式または真理値表を読み込んで、出力ビットごとに分割し、出力１ビット分の論理式または真理値表を生成する処理と、
前記出力１ビット分の論理式または真理値表ごとに、他の論理式または真理値表と重複しないようにＲＯ−ＢＤＤ（Reduced Ordered Binary Decision Diagrams）の変数順を決定し、当該変数順に基づいて当該論理式または真理値表のShared-RO-BDDを構築し、当該Shared-RO-BDDの各ノードを２：１セレクタにマップする処理と、
前記各２：１セレクタの制御信号を生成するためのドライバチェインを作り、当該ドライバチェインの各出力を、前記ＲＯ−ＢＤＤに基づく各セレクタ群を構成する各段のセレクタに対して、各セレクタ群で相異なる順番となるように接続する処理と、
セレクタがマッピングされドライバチェインを設定された組合せ回路の論理式または真理値表を前記メモリに格納する処理と
を前記コンピュータに実行させることを特徴とするプログラム。 - 前記ＲＯ−ＢＤＤに対してセレクタをマッピングする際に、
前記Shared-RO-BDDのルート側の所定数ｎ段をUnshared-RO-BDDに変換する処理と、
前記Unshared-RO-BDDに変換されたｎ段分のノードを、２n本の入力のうちどれをセレクトするかを決定するセレクト信号を生成する生成回路と、当該セレクト信号によって２n本の入力のうち一本を選び出すための、２n個の２入力ＡＮＤおよび１個の２n入力ＯＲを結合してなる選択回路とを備えた２n：１セレクタにマップする処理と、
他のノードを２：１セレクタにマップする処理と
を前記コンピュータに実行させることを特徴とする請求項８に記載のプログラム。 - コンピュータを制御して組合せ回路の回路構造を論理合成するプログラムを、当該コンピュータが読み取り可能に記録した記録媒体であって、
前記プログラムは、
メモリから処理対象である組合せ回路の論理式または真理値表を読み込んで、出力ビットごとに分割し、出力１ビット分の論理式または真理値表を生成する処理と、
前記出力１ビット分の論理式または真理値表ごとに、他の論理式または真理値表と重複しないようにＲＯ−ＢＤＤ（Reduced Ordered Binary Decision Diagrams）の変数順を決定し、当該変数順に基づいて当該論理式または真理値表のShared-RO-BDDを構築し、当該Shared-RO-BDDの各ノードを２：１セレクタにマップする処理と、
前記各２：１セレクタの制御信号を生成するためのドライバチェインを作り、当該ドライバチェインの各出力を、前記ＲＯ−ＢＤＤに基づく各セレクタ群を構成する各段のセレクタに対して、各セレクタ群で相異なる順番となるように接続する処理と、
セレクタがマッピングされドライバチェインを設定された組合せ回路の論理式または真理値表を前記メモリに格納する処理と
を前記コンピュータに実行させることを特徴とする記録媒体。 - 前記プログラムは、前記ＲＯ−ＢＤＤに対してセレクタをマッピングする際に、
前記Shared-RO-BDDのルート側の所定数ｎ段をUnshared-RO-BDDに変換する処理と、
前記Unshared-RO-BDDに変換されたｎ段分のノードを、２n本の入力のうちどれをセレクトするかを決定するセレクト信号を生成する生成回路と、当該セレクト信号によって２n本の入力のうち一本を選び出すための、２n個の２入力ＡＮＤおよび１個の２n入力ＯＲを結合してなる選択回路とを備えた２n：１セレクタにマップする処理と、
前記２n：１セレクタに置き換えられた出力側の前記ｎ段を除く他のノードを２：１セレクタにマップする処理と
を前記コンピュータに実行させることを特徴とする請求項１０に記載の記録媒体。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2002017959A JP4328487B2 (ja) | 2002-01-28 | 2002-01-28 | 組合せ回路、暗号回路、その生成方法及びプログラム |
| US10/349,519 US7460666B2 (en) | 2002-01-28 | 2003-01-22 | Combinational circuit, encryption circuit, method for constructing the same and program |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2002017959A JP4328487B2 (ja) | 2002-01-28 | 2002-01-28 | 組合せ回路、暗号回路、その生成方法及びプログラム |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2003223100A JP2003223100A (ja) | 2003-08-08 |
| JP4328487B2 true JP4328487B2 (ja) | 2009-09-09 |
Family
ID=27742897
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2002017959A Expired - Fee Related JP4328487B2 (ja) | 2002-01-28 | 2002-01-28 | 組合せ回路、暗号回路、その生成方法及びプログラム |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US7460666B2 (ja) |
| JP (1) | JP4328487B2 (ja) |
Families Citing this family (17)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP1573956A1 (en) * | 2002-12-13 | 2005-09-14 | Koninklijke Philips Electronics N.V. | A small hardware implementation of the subbyte function of rijndael |
| KR100800468B1 (ko) * | 2004-01-29 | 2008-02-01 | 삼성전자주식회사 | 저전력 고속 동작을 위한 하드웨어 암호화/복호화 장치 및그 방법 |
| US7506278B1 (en) * | 2005-03-08 | 2009-03-17 | Xilinx, Inc. | Method and apparatus for improving multiplexer implementation on integrated circuits |
| JP5203594B2 (ja) | 2006-11-07 | 2013-06-05 | 株式会社東芝 | 暗号処理回路及び暗号処理方法 |
| JP4453697B2 (ja) | 2006-12-15 | 2010-04-21 | ソニー株式会社 | 演算処理装置、および演算処理制御方法、並びにコンピュータ・プログラム |
| DE102007012726A1 (de) * | 2007-03-16 | 2008-09-18 | Micronas Gmbh | Verschlüsselungsvorrichtung mit einem mehrstufigen Verschlüsselungsblock |
| JP4849140B2 (ja) * | 2009-02-20 | 2012-01-11 | ソニー株式会社 | データ変換装置、演算処理装置、および演算処理制御方法、並びにコンピュータ・プログラム |
| US20100246815A1 (en) * | 2009-03-31 | 2010-09-30 | Olson Christopher H | Apparatus and method for implementing instruction support for the kasumi cipher algorithm |
| US8832464B2 (en) * | 2009-03-31 | 2014-09-09 | Oracle America, Inc. | Processor and method for implementing instruction support for hash algorithms |
| US9317286B2 (en) * | 2009-03-31 | 2016-04-19 | Oracle America, Inc. | Apparatus and method for implementing instruction support for the camellia cipher algorithm |
| US8654970B2 (en) * | 2009-03-31 | 2014-02-18 | Oracle America, Inc. | Apparatus and method for implementing instruction support for the data encryption standard (DES) algorithm |
| US20100250965A1 (en) * | 2009-03-31 | 2010-09-30 | Olson Christopher H | Apparatus and method for implementing instruction support for the advanced encryption standard (aes) algorithm |
| US8488783B2 (en) * | 2010-02-19 | 2013-07-16 | Nokia | Method and apparatus for applying recipient criteria in identity-based encryption |
| CN102902510B (zh) * | 2012-08-03 | 2016-04-13 | 华南理工大学 | 一种有限域求逆器 |
| US9390292B2 (en) * | 2013-12-30 | 2016-07-12 | Wisconsin Alumni Research Foundation | Encrypted digital circuit description allowing circuit simulation |
| US9960910B2 (en) | 2016-02-25 | 2018-05-01 | Wisconsin Alumni Research Foundation | Encrypted digital circuit description allowing signal delay simulation |
| US11513799B2 (en) * | 2019-11-04 | 2022-11-29 | Apple Inc. | Chained buffers in neural network processor |
Family Cites Families (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH04103213A (ja) | 1990-08-22 | 1992-04-06 | Nec Corp | マルチプレクサ回路 |
| JP3004589B2 (ja) | 1995-07-26 | 2000-01-31 | 松下電器産業株式会社 | パストランジスタ論理設計方法 |
| US5917728A (en) * | 1995-07-26 | 1999-06-29 | Matsushita Electric Industrial Co., Ltd. | Method for designing path transistor logic circuit |
| JPH10254920A (ja) | 1997-03-07 | 1998-09-25 | Toshiba Corp | 論理回路の遅延最適化装置 |
| US6026222A (en) * | 1997-12-23 | 2000-02-15 | Nec Usa, Inc. | System for combinational equivalence checking |
| JP3499810B2 (ja) * | 2000-03-06 | 2004-02-23 | 株式会社東芝 | 暗号化装置、暗号化方法及び暗号化装置としてコンピュータを機能させるためのプログラムを記録したコンピュータ読取り可能な記録媒体並びに復号装置、復号方法及び復号装置としてコンピュータを機能させるためのプログラムを記録したコンピュータ読取り可能な記録媒体 |
| JP3753925B2 (ja) * | 2000-05-12 | 2006-03-08 | 株式会社ルネサステクノロジ | 半導体集積回路 |
| US6587990B1 (en) * | 2000-10-01 | 2003-07-01 | Lsi Logic Corporation | Method and apparatus for formula area and delay minimization |
| US20030068038A1 (en) * | 2001-09-28 | 2003-04-10 | Bedros Hanounik | Method and apparatus for encrypting data |
| US7801301B2 (en) * | 2001-10-10 | 2010-09-21 | Stmicroelectronics S.R.L. | Method and circuit for data encryption/decryption |
-
2002
- 2002-01-28 JP JP2002017959A patent/JP4328487B2/ja not_active Expired - Fee Related
-
2003
- 2003-01-22 US US10/349,519 patent/US7460666B2/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| US7460666B2 (en) | 2008-12-02 |
| US20030198343A1 (en) | 2003-10-23 |
| JP2003223100A (ja) | 2003-08-08 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4328487B2 (ja) | 組合せ回路、暗号回路、その生成方法及びプログラム | |
| Dandalis et al. | A comparative study of performance of AES final candidates using FPGAs | |
| US8411853B2 (en) | Alternate galois field advanced encryption standard round | |
| Morioka et al. | A 10-Gbps full-AES crypto design with a twisted BDD S-box architecture | |
| Mozaffari-Kermani et al. | Efficient and high-performance parallel hardware architectures for the AES-GCM | |
| US7502463B2 (en) | Methods and apparatus for implementing a cryptography engine | |
| Satoh et al. | ASIC-hardware-focused comparison for hash functions MD5, RIPEMD-160, and SHS | |
| WO2010107114A1 (ja) | パターンマッチング装置 | |
| Güneysu | Utilizing hard cores of modern FPGA devices for high-performance cryptography | |
| Hilewitz et al. | Comparing fast implementations of bit permutation instructions | |
| CN104238995B (zh) | 一种非线性反馈移位寄存器 | |
| US7366300B2 (en) | Methods and apparatus for implementing a cryptography engine | |
| Opirskyy et al. | Heuristic method of finding bitsliced-description of derivative cryptographic s-box | |
| Ahmad et al. | A new cryptographic scheme utilizing the difficulty of big Boolean satisfiability | |
| Gaj et al. | Hardware performance of the AES finalists-survey and analysis of results | |
| Disser et al. | Breaking the size barrier: Universal circuits meet lookup tables | |
| CN113711533A (zh) | 用于面积受限硬件的低深度AES SBox架构 | |
| Shi et al. | Implementation complexity of bit permutation instructions | |
| JP4120193B2 (ja) | 暗号復号回路 | |
| CN108804379B (zh) | 可重构处理器及其配置方法 | |
| Standaert et al. | Efficient FPGA implementations of block ciphers KHAZAD and MISTY1 | |
| Majzoub et al. | MorphoSys reconfigurable hardware for cryptography: the twofish case | |
| Satoh et al. | High-Speed MARS Hardware. | |
| US11309896B2 (en) | Reconfigurable logic circuit | |
| Dimitrakopoulos et al. | Sorter based permutation units for media-enhanced microprocessors |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20060117 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20060412 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20060523 |
|
| RD14 | Notification of resignation of power of sub attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7434 Effective date: 20060602 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20060727 |
|
| A911 | Transfer to examiner for re-examination before appeal (zenchi) |
Free format text: JAPANESE INTERMEDIATE CODE: A911 Effective date: 20060904 |
|
| A912 | Re-examination (zenchi) completed and case transferred to appeal board |
Free format text: JAPANESE INTERMEDIATE CODE: A912 Effective date: 20070302 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20090508 |
|
| RD03 | Notification of appointment of power of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7423 Effective date: 20090528 |
|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
| RD14 | Notification of resignation of power of sub attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7434 Effective date: 20090604 |
|
| RD14 | Notification of resignation of power of sub attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7434 Effective date: 20090610 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20090615 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120619 Year of fee payment: 3 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120619 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130619 Year of fee payment: 4 |
|
| LAPS | Cancellation because of no payment of annual fees |