(57)【要約】【課題】LSIの低消費電力化を実現するバス反転決定回路生成装置バス反転決定回路生成のためのプログラムを提供。【解決手段】対象とするバスの幅を入力するバス幅入力手段と、条件に対する緩和の大きさを入力する緩和条件入力手段と、バス幅入力手段からの信号に基づき、初期反転決定回路を生成する初期反転決定回路生成手段と、初期反転決定回路生成手段及び緩和条件入力手段からの信号に基づき、初期反転決定回路の比較器を簡単化する比較器簡単化手段と、比較器簡単化手段からの出力を受けて、さらに反転決定回路のハミング距離計算回路を簡単化するハミング距離計算回路簡単化手段と、ハミング距離計算回路簡単化手段から出力される簡単化された反転決定回路を出力する反転決定回路出力手段とを備えてなる。【選択図】図６
2015041354.tif 000002
【特許請求の範囲】
【請求項１】
対象とするバスの幅を入力するバス幅入力手段と、
条件に対する緩和の大きさを入力する緩和条件入力手段と、
前記バス幅入力手段からの信号に基づき、初期反転決定回路を生成する初期反転決定回路生成手段と、
該初期反転決定回路生成手段及び前記緩和条件入力手段からの信号に基づき、初期反転決定回路の比較器を簡単化する比較器簡単化手段と、
該比較器簡単化手段からの出力を受けて、さらに反転決定回路のハミング距離計算回路を簡単化するハミング距離計算回路簡単化手段と、
該ハミング距離計算回路簡単化手段から出力される簡単化された反転決定回路を出力する反転決定回路出力手段と、
を備えてなることを特徴とするバス反転決定回路生成装置
【請求項２】
コンピュータに、対象とするバスの幅を入力するバス幅入力ステップと、
コンピュータに、条件に対する緩和の大きさを入力する緩和条件入力ステップと、
前記バス幅入力ステップによる信号に基づき、初期反転決定回路を生成する初期反転決定回路生成ステップと、
該初期反転決定回路生成ステップ及び前記緩和条件入力ステップからの信号に基づき、初期反転決定回路の比較器を簡単化する比較器簡単化ステップと、
該比較器簡単化ステップからの信号を受けて、反転決定回路のハミング距離計算回路を簡単化するハミング距離計算回路簡単化ステップと、
該ハミング距離計算回路簡単化ステップから出力される簡単化された反転決定回路を出力する反転決定回路出力ステップと、
を備えてなることを特徴とするバス反転決定回路生成のためのプログラム
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、LSIの低消費電力化を実現するバス反転決定回路生成装置及びバス反転決定回路生成のためのプログラムに関する。
【背景技術】
【０００２】
近年、携帯電話やノート PC などの LSI を利用したポータブルデバイスの普及に伴い、低消費電力の LSI が求められており、LSI の低消費電力化の研究が行われている。その中で複数のデバイスを接続するバス (データバス、アドレスバス、コントローラバスなど) も消費電力が比較的大きいことから低消費電力化の研究の対象とされており、バスの低消費電力化手法として、バスの信号値を反転することによるトグル削減手法 （非特許文献１，２） やバスの信号値を符号化することによるトグル削減手法（非特許文献３）などが提案されている。
【０００３】
例えば非特許文献１に記載のバス反転法では、バスに流れる信号値を適切に反転するバス反転回路をバスの送信側に、そして反転された信号値を元に戻すための回路をバスの受信側に挿入し、バスに流すベクトル系列において連続する 2 ベクトルのハミング距離がバス幅 W の半分以下になるように、 ベクトルを適切に反転する。これによりバスのトグル数を削減することができ、バスの低消費電力化ができる。このようなバスの低消費電力化は、エラートレラントアプリケーションの 1 つであると考えられる。エラートレラントアプリケーションとはそのアプリケーションを実装する回路の出力誤りに対する許容性が高いアプリケーションのことである（非特許文献４，５，６，７，８）。
【０００４】
主なアプリケーションとしては、動画像や音声を処理して出力するアプリケーション（非特許文献９）や、プロセッサの分岐予測や今回対象としている低消費電力化のように出力がベストエフォート型のアプリケーションが挙げられる（非特許文献４）。バスの低消費電力化（非特許文献１）はパフォーマンスを向上する (電力量を削減する)ことを目的とした処理であり、この処理が正しく行われなかったとしても、データを正しく転送するというバスの本来の機能は損なわれない。例えば、バス反転回路において、連続する 2 ベクトルのハミング距離の計算結果に誤りが生じ、バスの反転の判定が間違った場合でも、バスのトグル数 (つまり、消費電力) の削減効果が低下するだけで、バスの転送機能には影響がない。つまり、この回路は出力誤りに対する許容性が高く、バスの低消費電力化はエラートレラントアプリケーションである。
【０００５】
エラートレラントアプリケーションを実現する論理回路においては、その誤りに対する許容性を利用して、許容範囲内で回路が簡単化できるように設計する方法が研究されている （非特許文献６，７）。
【０００６】
以下、従来のバス反転回路について述べる。図７において、１１は他の装置からのデータが入力する入力データ保持回路、１２は入力データ保持回路１１から出力されたデータ信号が入力するバス反転決定回路で、予め設定された値と比較してデータ信号を反転するか否か決定する。１３は、入力データ保持回路１１にて保持されたデータ情報信号が入力するデータ反転回路で、バス反転決定回路１２からの信号により、データ情報信号を反転させ、又は反転させず元の状態を維持する。１４は、データ反転回路１３から出力された信号を入力とする出力データ保持回路であり、そのデータ信号は、バスへ出力される。バス反転決定回路１２は、出力データ保持回路１４により、反転させるか否かが制御される。
【０００７】
バス反転決定回路１２は、図８に示すように、データ入力保持回路１１の出力データ信号及び出力データ保持回路１４からの制御信号が入力するハミング距離計算回路１２と、このハミング距離計算回路１２に入力されハミング距離計算された信号を比較する比較器１６よりなり、その出力信号がデータ反転回路１３へ加えられる。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】M.R.Stan and W.P.Burleson,“Bus-invert coding for low-power I/O,”IEEE Trans.VLSI,Vol.3,No.1,pp.49&#8211;58,1995.
【非特許文献２】S.Hong,U.Narayanan,K.-S.Chung, and T.Kim,“Bus-invertcoding  for low-power I/O a decomposition approach, ”IEEE Proc. MWSCAS,pp.750&#8211;753,2000.
【非特許文献３】M.Madhu,V.Srinivasa Murty and V.Kamakoti,“Dy namic Coding Technique For Low-Power DataBus,”IEEE Proc.ISVLSI,pp.252&#8211;253,2003.
【非特許文献４】T.-Y.Hsieh,M.Breuer,M.Annavaram,S.Gupta,andK.-J.Lee,“Tolerance of performance degrading faultsfor effective yield improvement,”Proc.ITC, pp.1&#8211;10,2009.
【非特許文献５】M.Breuer,“Hardware that produces boundedrather than exact results,”Proc.DAC,pp.871&#8211;876, 2010.
【非特許文献６】D.Shin and S.Gupta,“Approximate logic synthesisfor error tolerant applications,”Proc.DATE,pp.957&#8211;960,2010.
【非特許文献７】D.Shin and S.K.Gupta,“A new circuitsimpli&#64257;cation method for error tolerantapplications, ”Proc.DATE,pp.1&#8211;6,2011.
【非特許文献８】亀井惇平,松木伸伍,岩垣剛,市原英行,井上智生,“エラートレラントアプリケーションのための多重縮退故障を用いた論理簡単化アルゴリズム,” 信学技報(VLD2012-136),Vol.112,No.451,pp.1-6,2013 年3月.
【非特許文献９】D.Shin and S.Gupta,“A Re-design Techniquefor Datapath Modulesin Error Tolerant Applications, ”17th Asian Test Symposium 2008 (ATS ’08), pp. 431-437,2008.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明は、バス反転による低消費電力化が持つ誤りに対する許容性を利用して、バスの反転条件を緩和することでバス反転回路を簡単化する、バス反転決定回路生成装置及びバス反転決定回路生成のためのプログラムを提供するものである。本発明におけるバス反転回路の簡単化に際しては、一般的な冗長な論理簡単化とは異なり、簡単化後のバス反転回路が簡単化前にそれとは異なる値を出力するように設計される。ただし、このとき、バス反転による低消費電力化がエラートレラントアプリケーションであることを踏まえて、この 2 つの回路の出力の差分をエラー (誤り) と考え、その誤りが許容できる範囲で設計を変更される。
【課題を解決するための手段】
【００１０】
本発明に係るバス反転決定回路生成装置は、対象とするバスの幅を入力するバス幅入力手段と、条件に対する緩和の大きさを入力する緩和条件入力手段と、前記バス幅入力手段からの信号に基づき、初期反転決定回路を生成する初期反転決定回路生成手段と、該初期反転決定回路生成手段及び前記緩和条件入力手段からの信号に基づき、初期反転決定回路の比較器を簡単化する比較器簡単化手段と、該比較器簡単化手段からの出力を受けて、さらに反転決定回路のハミング距離計算回路を簡単化するハミング距離計算回路簡単化手段と、該ハミング距離計算回路簡単化手段から出力される簡単化された反転決定回路を出力する反転決定回路出力手段と、を備えてなるものである。
【００１１】
また、本発明に係るバス反転決定回路生成のためのプログラムは、コンピュータに、対象とするバスの幅を入力するバス幅入力ステップと、コンピュータに、条件に対する緩和の大きさを入力する緩和条件入力ステップと、前記バス幅入力ステップによる信号に基づき、初期反転決定回路を生成する初期反転決定回路生成ステップと、該初期反転決定回路生成ステップ及び前記緩和条件入力ステップからの信号に基づき、初期反転決定回路の比較器を簡単化する比較器簡単化ステップと、該比較器簡単化ステップからの信号を受けて、反転決定回路のハミング距離計算回路を簡単化するハミング距離計算回路簡単化ステップと、該ハミング距離計算回路簡単化ステップから出力される簡単化された反転決定回路を出力する反転決定回路出力ステップと、を備えてなるものである。
【発明の効果】
【００１２】
本発明におけるバス反転回路の論理簡単化は、十分に許容することができる反転条件の緩和に基づいている。具体的なバス反転回路の設計とその簡単化アルゴリズムにより、計算機シミュレーションを行うことで、反転の効果がもともと高い場合にはバス反転の効果をほとんど落とすことなく大幅な回路簡単化ができる。すなわち、バスの低消費電力化の効果を大きく損なうことなく、回路の論理素子数を大幅に減らすことができる。バス反転回路の論理簡単化がバス反転回路自身の低消費化につながり、結果としてバスとバス反転回路の両方が消費する電力を削減することができる。
【図面の簡単な説明】
【００１３】
【図１】８ビットハミング距離計算回路を示すブロック図である。
【図２】８ビット比較器を示す回路図である。
【図３】反転の条件を緩和して簡単化したハミング距離計算回路図である。
【図４】簡単化した８ビット比較器を示す回路図である。
【図５】本発明実施の形態に係るバス反転決定回路生成装置のブロック図である。
【図６】本発明実施の形態に係るバス反転決定回路生成のためのプログラムを説明するためのフローチャートである。
【図７】従来のバス反転回路を示すブロック図である。
【図８】従来のバス反転決定回路の構成を示すブロック図である。
【発明を実施するための形態】
【００１４】
バス反転とバスのトグル数削減バスの消費電力は、バスの信号値のトグル（0 から 1、または、1 から 0 に変化すること）の回数に比例する。表 1（ベクトル系列とバストグル数） の 1 列目に示すように、バス幅 8 ビット (バス幅W = 8) のデータバスに流す信号値（ベクトル）系列 A : a0 , a1 ,…, a9を考える。表 1 の 2列目にはベクトル系列Aの現時刻のベクトルatと前時刻のベクトル
at&#8722;1のハミング距離dis(at,at&#8722;1) を示している。このとき、例えば、ベクトルa0とa1のハミング距離dis(a0,a1)は 7であるため、ベクトルa0後にa1をバスに流した場合、7本の信号線の値がトグルすることになる。
【００１５】
バスが消費する電力はトグル数に比例するため、このベクトル系列をそのままバスに流した場合、バストグル数
TB は 49 となり、これに比例した電力が消費されることになる。バス反転によるトグル数削減手法（バス反転法）は、バスに流すベクトル系列における時刻 t&#8722; 1とtのベクトル間のハミング距離を計算し、ハミング距離がバス幅Wの半分よりも大きければ、時刻tの信号値を反転する手法である。
【００１６】
表 1 の 3 列目にハミング距離が W/2=4 以下（dis(bt,bt&#8722;1)&#8804;4）になるように反転したベクトル系列Bを示す。ベクトル系列Bでは、ベクトル系列Aのa1,a3,a4,a7,a9 を反転しており、表の 4 列目に示すようにベクトル間のハミング距離は必ず 4 以下になっている（括弧の中の数字は削減数）。例えば、時刻t=1では前のベクトルb0=(01101111) とベクトルa1=(11010000)のハミング距離が 7 であるため、ベクトルa1を反転したベクトル b1 =(00101111)をバスに流すことで、ハミング距離は 1 となり 6 回のトグルを削減している。  
【００１７】
また、時刻 2 では、ベクトルb1がベクトルa1の反転ベクトルであることから、ベクトルa2とのハミング距離が2となっているため、ベクトルa2をそのままベクトルb2としている。このように連続する 2 ベクトルのハミング距離に応じて反転を行うことで、ベクトル系列Bによるバスの総トグル数TBは21となり、バスの消費電力削減率は21/49 &#8773;
43%となる。
【００１８】
バス反転法では、前述した図７，８に示すように、バスに流れる信号値を適切に反転するバス反転回路をバスの送信側に、そして反転した信号値をもとに戻すための反転回路をバスの受信側に挿入する。また、信号値が反転しているのかどうかを示す反転信号r（バス反転決定回路１２から出力）をバスの信号値とは別に用意する（つまり、バス幅W+1ビットのベクトルを実際には送信することになる）。このため、反転信号 のトグル率も消費電力に影響することになる。例えば、表 1 のベクトル系列では反転信号は 7 回トグルするため、最終的な反転信号まで含めたバスの総トグル数は 21+7 =28となる。以下の説明では反転信号のトグル数については考慮しないが、最後に示す実施例の結果ではこの反転信号のトグル数も含めてバストグル数を計算している。
【表１】
2015041354.tif 000003
【００１９】
反転条件の緩和によるバス反転回路の簡単化
バス反転法によるバスの低消費電力化は、エラートレラントアプリケーションであるため、それを実現するバス反転回路は、その誤りに対する許容性を利用して回路簡単化することができる。バス反転法では、誤りに対する許容性を反転条件の緩和として表現する。
【００２０】
まず 一般的なバス反転回路について説明し、次にそのバス反転回路を用いてバス反転法におけるバス反転回路の簡単化について詳述する。バス反転回路の簡単化は、バスを反転する条件を緩和し、バスの多少の消費電力の増加を許容することで行う。
【００２１】
バス反転回路
バス反転の条件は次のように表現できる。
バス反転の条件
バス幅 Wと、ベクトル r1と r2のハミング距離
dis(r1,r2) に対して、
【数１】
2015041354.tif 000004
【００２２】
バス反転回路の実現方法は様々な方法があるが 、ここではバス反転決定回路とデータ反転回路を持つ設計とする。なお、簡単化の対象とするのはバス反転決定回路内部のハミング距離計算回路と比較器であるため、ここではこの 2 つの回路について説明する。
【００２３】
ハミング距離計算回路
図１に示すように、ハミング距離計算回路は、入力された 2 つのベクトルr1と r2のハミング距離 dis(r1,r2) を計算する回路である。バス幅 W（以下では、Wは2のべき乗と仮定）のハミング距離計算回路は、2 つのベクトルの差分ベクトルを計算するW個の排他的論理和（エクスクルーシブオアゲートEXOR）ゲート列と、その差分ベクトル内の論理値 1 の数を数える加算器からなる。加算器は部分加算器
ADDを頂点とする高さlog2Wの２分木構造をしており、k段目のADD(k)（入力側を1段目とする。1&#8804;k&#8804;log2W ）は、kビット加算器である。同図は、部分加算器 ADD を桁上げ加算器
(RCA)で構成したW=8のハミング距離計算回路を示しており、４個の加算器ADD(1)、２個の加算器ADD(2)及び１個の加算器ADD(3)にて構成される。
【００２４】
１段目の加算器ADD(1)は、１個のANDゲートと１個のEXORゲートから構成され、２段目の加算器ADD(2)は、２個のANDゲート、２個のEXORゲート、１個のORゲートにて構成され、３段目の加算器ADD(3)は、４個のANDゲート、４個のEXORゲート、２個のORゲートにて構成される。
【００２５】
入力ベクトル r1 =(r10, r11, .. . ,r17 ) とr2=(r20, r21,…,r27 )とすると、８個のEXORゲート列でR1とR2の差分ベクトルd =(d0, d1,. . .,d7) を求める。ここでdiはr1iと r2iの排他的論理和である。後半のツリー型加算器は、まず差分ベクトル dの隣り合う 2 ビットdiとdi+1(i= 0,2,4,6) を1段目の1ビット加算器ADD(1)で足しあわせ、出力s1i= (s1i0,s1i1) として出力する。次に、s1jとs1(j+1)(j =0,2)をADD(2)で加算し、3ビット出力s2j= (s2j2,s2j1,s2j0)を得る。最後に、s20とs21を3ビット加算器 ADD(3)で足しあわせて、ハミング距離dis=(dis3,dis2,dis1,dis0)を得る。
【００２６】
表２(a) に3段目の加算器ADD(3)の真理値表を示す。加算器ADD(3)の入力s20とs21は入れ換え可能であるため、入れ換えた場合の出力値は省略している。また、信号値はすべて 10 進数で表記している。この真理値表が示すように入力 s20とs21の変域は0から4までの範囲であるため、加算器ADD(3)は一般的な3ビット加算器よりも簡単な構造となっている。
【００２７】
比較器
比較器は、計算されたハミング距離dis(r1,r2) がバス幅W/2より大きいとき、反転符号 r =1を、バス幅 W/2 以下であればr=0を出力する定数比較器である。表 4(a)はバス幅W が 8のときの比較器の真理値表を示す。この真理値表に基づく論理回路は、図２に示すように２個のORゲートと１個のANDゲートにて構成される。
【００２８】
簡単化の方針
バス反転法では、連続するベクトル間のハミング距離が大きいと反転の効果（トグル数の削減効果）は大きく、ハミング距離がW/2に近づくにつれて反転の効果は小さくなる。例えば、ハミング距離が W の場合は現時刻のベクトルを反転することでバスのトグル回数を 0 にできるが、ハミング距離がW/2+1のときは、現時刻のベクトルを反転したとしてもバスのトグル数はW/2&#8722;1となり、その差は2である。
【００２９】
そこで、ハミング距離がW/2よりも大きくてもW/2に近いとき、つまり反転することの効果が小さいときには、反転を必ずしもしなくてもよいように反転の条件を緩和することにする。表 1 の 5、6 列目に、ハミング距離dis(ct, ct &#8722;1) がW/2+2以下（dis(ct, ct &#8722;1 ) &#8804; 6）になるように反転したベクトル系列 C と、そのベクトル間ハミング距離 dis(ct, ct &#8722;1) を示している。ベクトル系列Cでは、時刻t=3と時刻t=9においてそれぞれの前時刻とのベクトル間ハミング距離が5であるため反転していない。この結果、バスのトグル数TBは25に増え、トグル数の削減率は25/49 &#8773; 51% となり、簡単化前に比べるとわずかな増加（簡単化前は 43%）となっている。
【００３０】
一方、このバス反転条件の緩和は、バス反転決定回路のハミング距離計算回路や比較器の簡単化につながる。図３は、同様な反転の条件緩和により簡単化した 8 ビットハミング距離計算回路である。加算器ADD(1),ADD(2), ADD(3)とEXORゲートよりなり、加算器ADD(1) 、ADD(2)は、それぞれ１個のANDゲートにて、加算器ADD(3)は、１個のANDゲートと１個のEXORゲートにて構成され、簡単化されていることが分かる。この簡単化で、論理ゲート数を 28 から 16 に削減できる。このように、バスのトグル数のわずかな増加で、バス反転決定回路の論理ゲート数を半分以下にすることができる。反転条件の緩和を考えるために、次のように反転の条件を再定義する。
【００３１】
緩和を考慮したバス反転の条件
バス幅Wと、ベクトルr1とr2のハミング距離
dis(r1,r2)に対して、
【数２】
2015041354.tif 000005
【００３２】
変数dは条件の緩和の程度を表現するパラメータであり、出力ドントケアの範囲W/2&#8804;dis(r1,r2)&#8804;W/2+d（以下では、変数dを「出力ドントケアの範囲」と呼ぶ）を表している。d=0の場合は、ハミング距離がW/2のときのみ反転の有無をドントケアにすること (r=X )を意味しており、dを大きくするほど出力ドントケアの範囲は広がり（条件は緩和され）、その結果バス反転決定回路は簡単化できることになる。
【００３３】
例えば表 1 に示した条件緩和の例は出力ドントケアの範囲がd=2に相当し、ベクトル系列Bでは反転を行っていた時刻3と9では、ベクトル系列Cでは反転を行っていない。なお、時刻2ではdis(a2,a1)=6であるが、ベクトル系列BやCでは時刻1のベクトルが反転しているため前時刻とのハミング距離は2となっているため、出力ドントケアの範囲には含まれない。
【００３４】
バス反転の条件緩和によるバスのトグル数の増加は、連続する2ベクトルのハミング距離が出力ドントケアの範囲 d に含まれる場合が多いほど大きくなるため、与えられるベクトル系列がこのような場合をできるだけ含まないものであれば、バス反転決定回路の簡単化の効果は大きくなる。
【００３５】
例えば、表1に示したベクトル系列 A において連続する 2 ベクトル間のハミング距離が 5 および6のものが1つも存在しなければ、ドントケア出力の範囲d=2で条件を緩和したとしても、バスのトグル数の増加はないことになる。また、バスの判定条件の緩和により簡単化したバス反転決定回路は消費する電力も減るため、バスのトグル数が増えてバスの消費電力が増加したとしても、バス反転決定回路とバスの両方をあわせた消費電力は削減する可能性がある。
【００３６】
バス反転決定回路の簡単化
出力ドントケアの範囲dが与えられたとき、このバス反転決定回路を簡単化する方法を説明する。バス反転決定回路の簡単化は、比較器とハミング距離計算回路を対象とする。
【００３７】
比較器の簡単化
比較器の論理関数は上で示した「緩和を考慮したバス反転の条件」そのものであるため、この条件を満たす比較器の論理のうち、できるだけ論理素子数が少なくなるようにな設計法を考える。一般的には論理関数の入力変数数（リテラル数）が少ないほど論理素子数が少ない設計になると考えられるため、出力ドントケアを入力数が減るように0または1に設定する。これは言い換えれば、rの論理関数を最小積和標準形で表現したときに、もっとも相乗項数とリテラル数が少なくなるようにドントケアを決めることになる。具体的には、W/2+ d+1を超えない最大の2のべき乗を2Mとすると、比較器の論理を
【数３】
2015041354.tif 000006
【００３８】
とすれば、入力変数数が最も小さくなるようにドントケアを0または1に決定したことになる。例えば、W=8、 d=2の場合を考えると比較器の論理関数は表２（８ビット比較器の真理値表）(b) に示したように出力値にドントケアを含んだものとなる。このとき、W/2+2=6を超えない最大の2 のべき乗は 4= 22であるため、ハミング距離 dis(r1,r2)が4以上のときは1、それ以外のときは0となるように（つまり出力のドントケアをすべて 1 になるように）設計すると、真理値表は表 4に示す(c) のようになる。この結果、上位 2 ビットのdis3とdis2だけで出力が決まることになる。よって、簡単化した比較器は図４に示すように１個のORゲートにて済み、簡単化前の図２に示す比較器よりも論理素子数が少ないことがわかる。以上をまとめると、比較器の簡単化は次のようになる。
【表２】
2015041354.tif 000007
【００３９】
比較器の簡単化
バス幅Wと出力ドントケアの範囲dが与えられたとき、W/2+dを超えない最大の2のべき乗 2Mを求め、比較器の入力下位
Mビットを削除する。
【００４０】
ハミング距離計算回路の簡単化
ハミング距離計算回路の簡単化も、構成要素である各部分加算器 ADD(k)の入力信号線数（入力変数数）を削減することで、論理を簡単化することを考える。ハミング距離計算回路では、簡単化によって出力結果が変化しても、後に続く比較器の出力 r が反転の条件にあっていればその簡単化は許容できる。比較器は 2M が出力rの閾値となるように簡単化を行っているため、ハミング距離計算回路の論理関数は次のように表される。
【数４】
2015041354.tif 000008
【００４１】
この条件の満たす範囲内で、入力変数をできるだけ削減する。表 2(b)、 (c) には、バス幅W=8のときのADD(3)の2つの入力s20とs21の最下位ビット(s200とs210 ）を削除した場合（削除後の入力は s20′とs21′）と、下位 2 ビット（さらにs201とs211 ）を削除した場合（削除後の入力は s20′′と s21′′）の入力値の変化と、それに伴う出力値の変化（dis′と dis′′ ）を示している。それぞれの表には、上で示したハミング距離計算回路の論理関数に関する 3 つの範囲を、d =2場合について示している。つまり、表３（加算器ADD(3)の真理値表）(a) に示すdis が 3 以下の範囲、4 以上 6 以下の範囲、7 以上の範囲の 3 つである。これから分かるように下位2ビットの削除を行っても、W =8、d=2の場合は上記のハミング距離計算回路の論理関数を満たすことが分かる。
【表３】
2015041354.tif 000009
【００４２】
以 上 より ハ ミ ン グ 距 離 計 算 回 路 の 各 加 算 器ADD(k)の入力のうち、削減できる最大の下位入力数はバス幅Wと変数dにより一意に求まることがわかり、削減できる最大の下位入力数はlog2 (d+2)&#8722;(log2W&#8722;k)を超えない最大の整数値である。よって、ハミング距離計算回路の各部分加算器ADD(k)の入力信号線を削除することによる簡単化は次のようになる。
【００４３】
ハミング距離計算回路の論理簡単化
バス幅Wと条件緩和の範囲dが与えられたとき、k段目のADD(k)の入力の下位 log2(d+2)&#8722;(log2W&#8722;k)ビット（ただし整数でない場合はこれを超えない最大の整数とする）を削除する。なお、表 ２(a) において、a20とa21の和（ハミング距離）が同じであっても、表２(b) や
(c) に示すように簡単化後ハミング距離計算回路では出力結果が異なる場合がある。
【００４４】
例えば、(a20,a21)=(2,4)のときと(a20,a21)=(3,3)のときは簡単化前のハミング距離計算回路の出力はどちらも 6 であるが、簡単化後は前者は 4 で後者は0となっている。その結果、同じハミング距離でも反転するかどうかは入力に依存し、この例では前者は反転信号rが1となり後者は0となる。
【００４５】
バス反転決定回路の簡単化アルゴリズム
これまでに述べた比較器とハミング距離計算回路の簡単化方法をまとめると、バス反転決定回路のアルゴリズムは次のように表すことができる。
【００４６】
入力：バス幅 W 、緩和条件（出力ドントケアの範囲を意味する変数）d
(1) 簡単化していないバス幅Wのバス反転決定回路Cを生成する。
(2)  C の比較器の簡単化を行う。D(k)はlog2(d+2)&#8722;(log2W&#8722;k)を超えない最大の整数とする。
(3) k=log2Wとし、D(k)>0の間以下の処理を繰り返す。ただし、繰り返す毎にkは1ずつ減少させる。
(3-1) CのADD(k)で出力が削除されているゲートと関連する信号線を削除
(3-2) CのADD(k)の下位D(k)ビットの入力を削除し、関係するゲートと信号線を削除
このアルゴリズムはまず比較器の簡単化を行い、それに伴ってハミング距離計算回路の最上段の部分加算器ADD(log2W )の不要な論理を削減する。その後、改めてADD(log2W )の簡単化を行い、それに伴って不要となる次段の部分加算器ADD(log2W&#8722;1)の論理を削減する。以下、同様な手順で部分加算器の簡単化を繰り返し、部分加算器の簡単化ができなくなれば終了する。
【００４７】
これらの処理は、バス反転決定回路生成装置にてなされる。すなわち、図５に示すように、バス反転決定回路生成装置は、対象とするバスの幅を入力するバス幅入力手段１と、条件に対する緩和の大きさを入力する緩和条件入力手段２と、バス幅入力手段からの信号に基づき、初期反転決定回路を生成する初期反転決定回路生成手段３と、初期反転決定回路生成手段３及び緩和条件入力手段４からの信号に基づき、初期反転決定回路の比較器を簡単化する比較器簡単化手段４と、比較器簡単化手段４からの出力を受けて、さらに反転決定回路のハミング距離計算回路を簡単化するハミング距離計算回路簡単化手段５と、ハミング距離計算回路簡単化手段５から出力される簡単化された反転決定回路を出力する反転決定回路出力手段６にて構成される。
【００４８】
バス反転決定回路生成装置においてなされる処理はコンピュータを用いて行われる。そのプログラムは以下の通りである。すなわち、バス反転決定回路生成のためのプログラムは、コンピュータに、対象とするバスの幅を入力するバス幅入力ステップS1と、コンピュータに、条件に対する緩和の大きさを入力する緩和条件入力ステップS2と、バス幅入力ステップS1による信号に基づき、初期反転決定回路を生成する初期反転決定回路生成ステップS3と、初期反転決定回路生成ステップS3及び緩和条件入力ステップS2からの信号に基づき、初期反転決定回路の比較器を簡単化する比較器簡単化ステップS4と、比較器簡単化ステップS4からの信号を受けて、反転決定回路のハミング距離計算回路を簡単化するハミング距離計算回路簡単化ステップS5と、ステップS5においてハミング距離計算回路は十分に簡単化されたかどうかを判定する判定ステップS6と、このステップS6で十分に簡単化されたと判定されたとき、その信号を受けてバス反転決定信号を出力するバス反転決定回路出力ステップS7と、を備える。ステップS6において、ハミング距離計算回路が十分に簡単化されていないと判定されたときは、その信号は、前段のハミング距離計算回路簡単化ステップS5に戻され、再度簡単化処理がなされる。ステップS5,6ハミング距離計算回路簡単化手段が構成される。
【実施例】
【００４９】
バス反転回路の面積とバストグル数に関する実施例
簡単化手法によるバス反転回路の面積削減の効果を調べるために、バス幅Wを32,64としたときをバス反転回路を設計した。そして、それぞれの回路を出力ドントケアの範囲dを0,2,6として、バス反転回路簡単化アルゴリズムで簡単化した。また、反転の条件を緩和したことによりバストグル数が増加することが予想されるため、計算機シミュレーションによりバストグル数を調べた。シミュレーションには 4 種類の JPEG、BMP画像ファイル（lena.jpg,pica.jpg,pict.jpg,miku.bmp）と4種類の Mach-O 64ビット実行ファイル（fs,mv cover,sample,short）を用いた。
【００５０】
表４（バス反転回路の面積とバストグル数の削減率）に、バス幅 W = 32,64 に対する、簡単化前（「緩和無し」）と簡単化後（「緩和 (d=0)」「緩和 (d=2)」「緩和 (d=6)」）のバス反転回路の面積とバストグル数の削減率を示す。回路面積は NOTゲートのサイズを1として計算しており、3列目にその値を示している。括弧の中には「緩和無し」のバス反転回路の面積を1としたときのそれぞれの面積の比率を示している。また、バストグル数の削減率は、バス反転法を用いない場合のバストグル数に対する用いた場合のトグル数の割合として示している。
【表４】
2015041354.tif 000010
【００５１】
表４から分かるように、バス反転回路面積はd が増加するほど小さくなっており、W =32、 d =6では 40%、W=64、d=6では、20%の面積削減が可能となっている。一方でバスのトグル数の増加はW=32の場合では高々5 ポイント、W=64の場合では 3 ポイント程度の増加にとどまっている。このことからバスのトグル数をほとんど増加させることなく、バス反転回路の面積を大幅に削減することができることがわかる。
【００５２】
表４において、ベクトル系列 lena.jpg よりも fs の方が（特にW=64のとき）バス反転法の効果が高く、さらに条件を緩和したとしてもバストグル数の増加が小さいことが分かる。これは 前述したように、fsのほうが、W/2よりも大きなハミング距離をもつ連続2ベクトルを多く持っており、かつ、出力ドントケアの範囲に属するハミング距離を持つものは少ないためと考えられる。
【００５３】
総消費電力に関する実施例
バス反転回路の面積削減は、バス反転回路自身の消費電力の削減に貢献すると考えられるため、バス反転回路の論理簡単化がバス部分の消費電力を多少増加させたとしても、バスとバス反転回路の消費電力を足しあわせた総消費電力はバス反転回路の簡単化により削減できる可能性がある。バスのトグル数をTB 、バス反転回路の論理ゲートのトグル数をTL 、さらにバス1トグルあたりの消費電力をPB 、バス反転回路の論理ゲートにおける1トグルの消費電力をPLとすると、バス反転法による総消費電力TP は、以下のように表現できる。
【数５】
2015041354.tif 000011
【００５４】
なお一般的には、バスの 1 つの信号線がトグルしたときに消費する電力は、バス反転回路の 1 つのゲートの出力値がトグルしたときに消費する電力より大きいことが想定されるため、PB/PL>1と考えられる。バス反転回路の簡単化が総消費電力T P に与える影響を調べるために、バスの信号値のトグル数に加えて、バス反転回路自身の論理ゲートのトグル数を調べるためのシミュレーションを行った。なお、バス反転回路のトグル数として数えているのは、簡単化の対象であるハミング距離計算回路と比較器の論理ゲートのトグル数のみであり、バスにつながるレジスタとその前後に位置する反転回路はバスの消費電力に含まれると考えられる。
【００５５】
表５（総消費電力TP）に系列lena.jpg、表に系列 fs の結果を示す。それぞれの系列に対して、バス反転回路のトグル数TL 、バスのトグル数TB 、そして 2 つの電力比PL:PB =1:50の場合とPL:PB=1:100の場合の総消費電力T Pとそのうちバス反転回路の消費電力の割合ρL=PL&middot;TL/T P(%)を示している。条件を緩和しないものと複数の緩和によるバス反転法の結果のうち、最も総消費電力T Pが小さいものを太字で示している。
【表５】
2015041354.tif 000012
【００５６】
この結果から lena.jpg,fsともに、反転条件を緩和することでわずかではあるが総消費電力が下げられる場合があることがわかる。バス反転回路の消費電力が総消費電力に占める割合は、条件を緩和するほど小さくなっていることが分かる。総消費電力が最も小さくなるところが「緩和 (d=0)」や「緩和(d=2)」であることを併せて考えると、全く緩和しないときはバス反転回路の消費電力が高いことが原因で、緩和しすぎた場合（d=6）はバスのトグル数が増加しすぎることが原因で、総消費電力が大きくなっていると考えられる。
【符号の説明】
【００５７】
１          バス幅入力手段
２          緩和条件入力手段
３          初期バス反転決定回路生成手段
４          比較器簡単化手段
５          ハミング距離計算回路簡単化手段
６          バス反転決定回路出力手段
【図１】
2015041354.tif 000013
【図２】
2015041354.tif 000014
【図３】
2015041354.tif 000015
【図４】
2015041354.tif 000016
【図５】
2015041354.tif 000017
【図６】
2015041354.tif 000018
【図７】
2015041354.tif 000019
【図８】
2015041354.tif 000020