-
跟随摩尔定律[1]的脚步,几十年来集成电路已从当初的30个晶体管发展到如今的几十亿,半导体工艺也从0.35 mm不断缩小到32 nm甚至更小,其标准供电电压也在不断下降。与此同时,由于动态功耗和供电电压成二次方正比例关系。为了满足信息系统的需求,降低电路功耗,需要进一步对电压进行放缩(voltage over scaling, VOS)。
但随着电压逐渐降低,系统会表现出较为明显的不稳定性。一方面由于电压的降低,其数字电路的容错能力下降[2]。另一方面,当芯片的特征尺寸以S为缩减因子(scaling factor)不断缩小的时候,噪声并没有同比例增加,而是以S2增加[3]。不仅如此,系统还出现了本征的随机噪声[4](random intrinsic noise),进一步增加了系统的不稳定性。
因此深亚微米(deep submicron technologies, DSM)条件下低电压供电的电路稳定性成为当前电路设计亟待解决的热点问题。文献[5, 6, 7, 8]关注于如何减少由IR压降[9]、电容和串扰[10]引起的噪声,但上述技术不能解决深亚微米中的随机固有噪声问题。于是研究者开始从概率的观点分析和解决电路的不确定性[11, 12, 13, 14]。文献[13]中的电压缩放技术可以对供电电压与精确度进行折中,文献[14]提出的基于噪声容忍算法(algorithmic noise-tolerance, ANT)检测器可以节省3倍系统能量。然而,以上所有工作都没有解决低电压供电条件下的容错问题。
有别于现有研究[15, 16, 17]的供电电压仅能降到0.4V,基于MRF[18]的电路却能够在超低电压供电条件下(Vdd=0.1~0.25V)工作,且具有很高的容错能力(BER优于10-5)。以能量的观点构造电路是MRF电路的核心思路,它并不着重于电路的每个节点在每个时刻的正确性,而是以电路正确的联合概率最大化为目的,从而实现电路的稳定可靠。MRF电路的核心步骤是通过映射将最大联合概率转化为最小簇能量问题,通过设计其簇能量Uc[19],保证电路的稳定性。
但是MRF电路分析与设计也存在一些问题,一方面是其电路面积比较庞大,很难向更大的模块电路发展,因此现有研究及设计还局限在基本门模块上。另一方面是其缺少系统的理论证明,现有的工作也仅给出了簇能量表达式和门级电路结构[20],而MRF电路在低电压条件下具有高容错的本质原因一直没有得到很好的解释。
基于此,本文旨在用信息论的观点对MRF电路的可靠性进行分析。以信息论分析指导电路是一热点[21, 22, 23],但现有工作多是将电路简化为对称电路,再用信息论分析电路,鲜有文献研究非对称电路的信息传递对其性能的影响。因此,本文从二输入与非门出发,基于信息论观点,首先提出了MRF分析模型,然后从熵、条件熵、互信息和归一化的互信息的角度分别证明了4条引理,最后基于该4条引理得出了MRF供电电压下界的表达式,通过与传统互补金属氧化物半导体(complementary metal oxide semiconductor, CMOS)电路作对比,证明MRF电路拥有更低的电压下界。本论文分析方法可用于其他模块电路的可靠性分析与比较。
-
典型的通信系统如图 1所示,该系统由输入X、输出Y、编码器、译码器、物理信道以及信道中的噪声构成。通信系统的等价表示如图 2所示,将编码器、译码器、物理信道等模块或信号处理单元看作变换Γ。通过等价,当把电路中的模块电路等价为变换Γ,电路中的噪声(软噪声,硬噪声)等价于信道噪声后,通信系统中的信息论观点同样可以用于电路系统中。本文将基于信息论观点对MRF的容错性进行理论分析与证明,其中信息论的基本理论如下。
设随机变量$ X = ({x_0}, {x_1}, \cdots, {x_{L - 1}}) $,$ Y = ({y_0}, {y_1}, \cdots, {y_{L - 1}}) $,则X的信息熵为:
$$ H(X){\text{ = }}\; - \sum\limits_{i = 0}^{L - 1} {p({x_i})\log } p({x_i}) $$ (1) 在已知Y条件下,随机变量X的条件熵为:
$$ H(X\left| Y \right.){\text{ = }}\; - \sum\limits_{y \in Y} {\sum\limits_{x \in X} {p\left( {x, y} \right)\log } p(x\left| y \right.)} $$ (2) 互信息量为:
$$ I(X;Y) = \sum\limits_{y \in Y} {\sum\limits_{x \in X} {p\left( {x, y} \right)\log } \frac{{p(x\left| y \right.)}}{{p(x)}}} $$ (3) 由式(2)和式(3)可得:
$$ I(X;Y) = H(X) - H(X\left| Y \right.) = H(Y) - H(Y\left| X \right.) $$ (4) 由定义可知,信息熵是X不确定性的度量,条件熵是在已知Y条件下,X不确定度的残余量,而互信息是在已知Y条件下,X不确定度的缩减量,反之亦然[24]。
为了简便,本文将二元离散随机变量的熵函数定义为H(p)函数:
$$ - p\log p - (1 - p)log(1 - p)\;\mathop = \limits^{{\text{def}}} H(p) $$ (5) -
本文首先提出了MRF分析模型,然后基于此分析模型利用信息论的观点对其进行分析证明。文献[20]给出了MRF的与非门结构,如图 3a所示。
将图 3a中的电路模块看作变换Γ,电路中的噪声看作信道噪声,从而利用信息论的观点对其信息熵、条件熵、互信息等进行分析。因为着重于输出不确定性的度量,将MRF与非门结构进行简化,如图 3b所示。通过简化,可以看出其主要分为主模块和反馈模块两个部分,其中主模块用于与非门输出,而反馈模块用于控制电路的容错特性。下文将基于PCMOS思想对MRF与非门进行建模。
-
传统两输入与非门概率模型如图 4所示。
根据文献[25]的建模,将噪声作为源加入到输入输出端。图中V1, V2代表软噪声,V3代表硬噪声,p1, p2, p3分别代表其正确的概率,且假设噪声是相互独立的。基于图 4的模型得到其正确输出概率如表 1所示,其中$ {p_{00}} = p({V_{{\text{out}}}} = 1|{V_{{\text{in}}}} = 00) $,$ {p_{01}} = p({V_{{\text{out}}}} = 1|{V_{{\text{in}}}} = 01) $,$ {p_{10}} = p({V_{{\text{out}}}} = 1|{V_{{\text{in}}}} = 10) $,$ {p_{11}} = p({V_{{\text{out}}}} = 0|{V_{{\text{in}}}} = 11) $。本文的非对称性体现在该电路正确输出0和1的概率不等上,即$ {p_{00}}, {p_{01}}, {p_{10}}, {p_{11}} $不一定相等。
表 1 两输入与非门输出正确概率
Vin1 Vin2 Vs1Vs2 Vout 正确概率 00 00 1 p00 $ {p_1}{p_2}{p_3} $ 01 $ {p_1}(1 - {p_2}){p_3} $ 10 $ (1 - {p_1}){p_2}{p_3} $ 11 $ (1 - {p_1})(1 - {p_2})(1 - {p_3}) $ 01 00 1 p01 $ {p_1}(1 - {p_2}){p_3} $ 01 ${p_1}{p_2}{p_3} $ 10 $ (1 - {p_1})(1 - {p_2}){p_3} $ 11 $ (1 - {p_1}){p_2}(1 - {p_3}) $ 10 00 1 p10 $ (1 - {p_1}){p_2}{p_3} $ 01 $ (1 - {p_1})(1 - {p_2}){p_3} $ 10 ${p_1}{p_2}{p_3} $ 11 $ {p_1}(1 - {p_2})(1 - {p_3}) $ 11 00 0 p11 $ (1 - {p_1})(1 - {p_2})(1 - {p_3}) $ 01 $(1 - {p_1}){p_2}(1 - {p_3}) $ 10 ${p_1}(1 - {p_2})(1 - {p_3}) $ 11 ${p_1}{p_2}{p_3} $ 当$ {p_1} = {p_2}, {p_3} = 1 $(假设硬噪声影响不计)时,有:
$$ \left\{ {\begin{array}{*{20}{c}} {{p_{00}} = 2{p_1} - {p_1}^2} \\ {{p_{01}} = 1 - {p_1} + {p_1}^2} \\ {{p_{10}} = 1 - {p_1} + {p_1}^2} \\ {{p_{11}} = {p_1}^2} \end{array}} \right. $$ (6) 由于$ 0.5 \leqslant {p_1} \leqslant 1 $,可证得$ {p_{00}} \geqslant {p_{01}} = {p_{10}} \geqslant {p_{11}} $,即具有非对称性。
-
本文以图 3b为例对MRF与非门进行分析,由于其主模块用于输出,因此对其主模块(三输入与非门)进行建模分析。
同样基于文献[25]的建模,得到图 5所示三输入与非门概率模型以及表 2所示的输出正确概率。对图 3b分析可知,反馈端口f与输入的关系如表 2中灰色部分所示(即实现了与非门功能)。即在无噪条件下,当Vin=00, 01, 10时,其反馈端口f=0;当Vin=11时,f=1。当p3*(假设硬噪声影响不计)时,有:
表 2 三输入与非门输出正确概率
$ {V_{{\text{in}}1}}^*{V_{{\text{in}}2}}^*{V_{{\text{in}}3}}^* $ $ {V_{s1}}^*{V_{s2}}^*{V_{s3}}^* $ $ {V_{{\text{out}}}}^* $ 正确概率 000 其他 1 $ [1 - {(1 - {p_1}^*)^2}(1 - {p_f})]{p_3}^* $ 111 $ {(1 - {p_1}^*)^2}(1 - {p_f})(1 - {p_3}^*) $ 001 其他 1 $ [1 - {(1 - {p_1}^*)^2}{p_f}]{p_3}^* $ 111 $ {(1 - {p_1}^*)^2}{p_f}(1 - {p_3}^*) $ 010 其他 1 $ [1 - (1 - {p_1}^*){p_1}^*(1 - {p_f})]{p_3}^* $ 111 $ (1 - {p_1}^*){p_1}^*(1 - {p_f})(1 - {p_3}^*) $ 011 其他 1 $ [1 - (1 - {p_1}^*){p_1}^*{p_f}]{p_3}^* $ 111 $ (1 - {p_1}^*){p_1}^*{p_f}(1 - {p_3}^*) $ 100 其他 1 $ [1 - {p_1}^*(1 - {p_1}^*)(1 - {p_f})]{p_3}^* $ 111 $ {p_1}^*(1 - {p_1}^*)(1 - {p_f})(1 - {p_3}^*) $ 101 其他 1 $ [1 - {p_1}^*(1 - {p_1}^*){p_f}]{p_3}^* $ 111 $ {p_1}^*(1 - {p_1}^*){p_f}(1 - {p_3}^*) $ 110 其他 1 $ [1 - {p_1}{*^2}(1 - {p_f})]{p_3}* $ 111 $ {p_1}{*^2}(1 - {p_f})(1 - {p_3}*) $ 111 其他 0 $ [1 - {p_1}{*^2}{p_f}](1 - {p_3}*) $ 111 $ {p_1}{*^2}{p_f}{p_3}* $ $$ \left\{ {\begin{array}{*{20}{c}} {{p_{00}}^* = 1 - {{(1 - {p_1}^*)}^2}(1 - {p_f})} \\ {{p_{01}}^* = 1 - ({p_1}^* - {p_1}{{^*}^2})(1 - {p_f})} \\ {{p_{10}}_* = 1 - ({p_1}^* - {p_1}{{^*}^2})(1 - {p_f})} \\ {{p_{11}}^* = {p_1}{{^*}^2}{p_f}} \end{array}} \right. $$ (7) 式中,$ {p_{00}}^* = p({V_{{\text{out}}}} = 1|{V_{{\text{in}}}} = 00) $;$ {p_{01}}^* = p({V_{{\text{out}}}} = 1|{V_{{\text{in}}}} = 01) $;$ {p_{10}}^* = p({V_{{\text{out}}}} = 1|{V_{{\text{in}}}} = 10) $;$ {p_{11}}^* = p({V_{{\text{out}}}} = 0|{V_{{\text{in}}}} = 11) $。
由于$ 0.5 \leqslant {p_1}^* \leqslant 1, 0.5 \leqslant {p_f} \leqslant 1 $,可证得$ {p_{00}}^* \geqslant {p_{01}}^* = {p_{10}}^* \geqslant {p_{11}}^* $,即同样也具有非对称性。
由与非门特性,得:
$$ \begin{array}{*{20}{c}} \begin{gathered} {p_{correct}} = p(x = 00)p(y = 1|x = 00) + p(x = 01) \times \\ p(y = 1|x = 01) + p(x = 10)p(y = 1|x = 10) + \\ \end{gathered} \\ {p(x = 11)p(y = 0|x = 11)} \end{array} $$ (8) 因此得到CMOS与非门与MRF与非门输出正确的概率为:
$$ \left\{ \begin{gathered} {p_{{\text{CMOS}}}} = \frac{1}{4}({p_{00}} + {p_{01}} + {p_{10}} + {p_{11}}) \hfill \\ {p_{{\text{MRF}}}} = \frac{1}{4}({p_{00}}^* + {p_{01}}^* + {p_{10}}^* + {p_{11}}^*) \hfill \\ \end{gathered} \right. $$ (9) 其中假设输入等概。
-
下文将基于MRF与非门与CMOS与非门输出正确概率相同的条件下,比较它们供电电压下界之间的关系。即有:
$$ {p_{00}}^* + {p_{01}}^* + {p_{10}}^* + {p_{11}}^* = {p_{00}} + {p_{01}} + {p_{10}} + {p_{11}} $$ (10) 根据式(7)和式(8)将其代入式(10)化简得:$ 2{p_1}^2 = {p_1}^{*2} + {p_f} $。在之前的工作中已证得$ {p_f} \geqslant {p_1}^* $,因此得:$ {p_1}{*^2} \leqslant {p_1}{*^2} \leqslant {p_f} $。
因实际电路$ {p_1} \geqslant 0.5, {p_f} \geqslant 0.5, {p_1}^* \geqslant 0.5 $,可证得:
$$ \left\{ {\begin{array}{*{20}{c}} {{p_{00}}^* \geqslant {p_{00}}} \\ {{p_{01}}^* \geqslant {p_{01}}} \\ {{p_{10}}^* \geqslant {p_{10}}} \\ {{p_{11}}^* \leqslant {p_{11}}} \end{array}} \right. $$ (11) 由于电路中要求正确概率大于等于0.5,又由式(11)知p11*最小,故有定义域:
$$ \left\{ {\begin{array}{*{20}{c}} {{p_{11}}^* = {p_1}^{*2}{p_f} \geqslant 0.5} \\ \begin{gathered} 2{p_1}^2 = {p_1}^{*2} + {p_f} \hfill \\ {p_f} \geqslant {p_1}^* \hfill \\ \end{gathered} \end{array}} \right. $$ (12) 即$ \sqrt 2 /2 \leqslant {p_1}^2 \leqslant 1 $,$ \sqrt 2 /2 \leqslant {p_f} \leqslant 1 $,$ 0.5 \leqslant {p_1}^{*2}{p_f} \leqslant 1 $,$ {p_f} \geqslant {p_1}^* $且$ 2{p_1}^2 = {p_1}^{*2} + {p_f} $。为表述方便,令其定义域为区域D,显然D是有界闭区域。
由数学知识可知,有如下求最大最小值方法:
假定函数在有界闭区域D上连续,在D内可微分且只有有限个驻点时,将函数f在D内所有驻点处的函数值以及D的边界上的最大值和最小值相互比较,其中最大值即为函数最大值,最小值即为函数最小值。
下文将利用此方法,基于信息论观点探讨在区域D上传统与非门与MRF与非门之间的关系。
-
基于上一节的基本模型,本文着重于在相同可靠性的条件下,比较MRF电路与传统CMOS电路供电电压下界之间的关系。
首先给出4条关于MRF电路与传统电路之间的信息熵、条件熵、互信息以及互信息与信息熵比值关系的引理,并给出相关证明以及物理意义。基于这4条引理证明电路供电电压下界与电路可靠性之间的关系,给出了MRF电路优于传统电路的理论支撑。
引理1 在输出正确概率相同的条件下,输出信息熵的关系为:
$$ H({Y_{{\text{CMOS}}}}) \geqslant H({Y_{{\text{MRF}}}}) $$ (13) 其中假设两者具有相同的输入X。
证明:由全概率公式:
$$ p(y = j) = \sum\limits_i {p(x = i)} p(y = j|x = i) $$ (14) 得到与非门输出概率分布如表 3所示。则有:
表 3 与非门输出概率分布
概率p 0 1 $ p({Y_{{\text{CMOS}}}}) $ $ p({Y_{{\text{MRF}}}}) $ $$ H({Y_{{\text{CMOS}}}}) = H(p), H({Y_{{\text{MRF}}}}) = H({p^*}) $$ (15) 式中,$ p = 0.25 + 0.25({p_{00}} + {p_{01}} + {p_{10}} - {p_{11}}) $;$ {p^*} = 0.25 + 0.25({p_{00}}^* + {p_{01}}^* + {p_{10}}^* - {p_{11}}^*) $。由式(7)和式(8)可得:$ p = 0.75, {p^*} = 0.75 + 0.25({p_1}^{*2} + {p_f} - 2{p_1}^{*2}{p_f}) $故有$ {p^*} \geqslant p \geqslant 0.5 $,$ H({Y_{{\text{CMOS}}}}) \geqslant H({Y_{{\text{MRF}}}}) $。证毕。
引理1说明了在相同的输入、输出正确概率条件下,CMOS与非门输出的不确定度大于MRF与非门,即说明与传统CMOS相比,MRF电路可以减少一定的不确定度。
引理2 在输出正确概率相同的条件下,条件熵的关系为:
$$ H({Y_{{\text{CMOS}}}}\left| X \right.) \geqslant H({Y_{{\text{MRF}}}}\left| X \right.) $$ (16) 其中假设两者具有相同的输入X。
证明:由条件概率得到其联合概率分布如表 4所示。
表 4 联合概率分布
$ p({x_1}{x_2},y) $ (00, 0) (00, 1) (01, 0) (01, 1) (10, 0) (10, 1) (11, 0) (11, 1) $ p{(X,Y)_{{\text{CMOS}}}} $ $ \frac{1}{4}(1 - {p_{00}}) $ $ \frac{1}{4}{p_{00}} $ $ \frac{1}{4}(1 - {p_{01}}) $ $ \frac{1}{4}{p_{01}} $ $ \frac{1}{4}(1 - {p_{10}}) $ $ \frac{1}{4}{p_{10}} $ $ \frac{1}{4}{p_{11}} $ $ \frac{1}{4}(1 - {p_{11}}) $ $ p{(X,Y)_{{\text{MRF}}}} $ $ \frac{1}{4}(1 - {p_{00}}^*) $ $ \frac{1}{4}{p_{00}}^* $ $ \frac{1}{4}(1 - {p_{01}}^*) $ $ \frac{1}{4}{p_{01}}^* $ $ \frac{1}{4}(1 - {p_{10}}^*) $ $ \frac{1}{4}{p_{10}}^* $ $ \frac{1}{4}{p_{11}}^* $ $ \frac{1}{4}(1 - {p_{11}}^*) $ 由其联合概率,得到条件熵为:
$$ \left\{ \begin{gathered} H({Y_{{\text{CMOS}}}}\left| X \right.) = 0.25[H({p_{00}}) + H({p_{01}}) + H({p_{10}}) + H({p_{11}})] \hfill \\ H({Y_{{\text{MRF}}}}\left| X \right.) = 0.25[H({p_{00}}^*) + H({p_{01}}^*) + H({p_{10}}^*) + {\kern 1pt} {\kern 1pt} H({p_{11}}^*)] \hfill \\ \end{gathered} \right. $$ (17) 辅助函数为:
$$ {\kern 1pt} \begin{array}{*{20}{c}} \begin{gathered} f = H({Y_{{\text{MRF}}}}\left| X \right.) - ({Y_{{\text{CMOS}}}}\left| X \right.) = \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} H({p_{00}}^*) + H({p_{01}}^*) + H({p_{10}}^*) + H({p_{11}}^*) - \\ \end{gathered} \\ {{\kern 1pt} H({p_{00}}) + H({p_{01}}) + H({p_{10}}) + H({p_{11}})} \end{array} $$ (18) 考虑函数f在条件$ {p_{00}}^* + {p_{01}}^* + {p_{10}}^* + {p_{11}}^* = {p_{00}} + {p_{01}} + {p_{10}} + {p_{11}} $下,且定义域为D的最大最小值。作函数为:
$$ \begin{array}{*{20}{c}} \begin{gathered} F = H({p_{00}}^*) + H({p_{01}}^*) + H({p_{10}}^*) + H({p_{11}}^*) - \\ H({p_{00}}) + H({p_{01}}) + H({p_{10}}) + H({p_{11}}) + \\ \end{gathered} \\ {\lambda ({p_{00}}^* + {p_{01}}^* + {p_{10}}^* + {p_{11}}^* - {p_{00}} - {p_{01}} - {p_{10}} - {p_{11}})} \end{array} $$ (19) 对F所有变量($ {p_{00}}^*, {p_{01}}^*, {p_{10}}^*, {p_{11}}^*, {p_{00}}, {p_{01}}, {p_{10}}, {p_{11}} $以及$ \lambda $)求偏导并令其为零解得(篇幅有限,因此略去求解过程):$ {p_{00}}^* = {p_{01}}^* = {p_{10}}^* = {p_{11}}^* = {p_{00}} = {p_{01}} = {p_{10}} = {p_{11}} $。此时$ {p_1}^* = {p_f} = {p_1} = 1 $,函数f=0。再通过比较在D的边界上的函数值求函数f的最大最小值。经过比较可知:f在边界点$ {p_1}^* = {p_f} = {p_1} = 1 $取得最大值0,又函数在驻点处的函数值为0。故在定义域有界区域D内$ f|\max = 0 $,即f≤0。证毕。
引理2说明了在相同的输入不确定度条件下,CMOS与非门在已知X的条件下,Y不确定度的残余量大于MRF与非门,即与传统CMOS相比,MRF电路可以减少一定的不确定度。
引理3 在输出正确概率相同的条件下,互信息的关系为:
$$ I(X;{Y_{{\text{CMOS}}}}) \geqslant I(X;{Y_{{\text{MRF}}}}) $$ (20) 其中假设两者具有相同的输入X。
证明:设辅助函数:
$$ \begin{array}{*{20}{c}} \begin{gathered} {f^*} = I(X{\text{;}}{Y_{{\text{CMOS}}}}) - I(X;{Y_{{\text{MRF}}}}) = H(p) - \frac{1}{4} \times \\ [H({p_{00}}) + H({p_{01}}) + H({p_{10}}) + H({p_{11}})] - H({p^*}) + \\ \end{gathered} \\ {\frac{1}{4}[H({p_{00}}^*) + H({p_{01}}^*) + H({p_{10}}^*) + H({p_{11}}^*)]} \end{array} $$ (21) 考虑函数f*在条件$ {p_{00}}^* + {p_{01}}^* + {p_{10}}^* + {p_{11}}^* = $$ {p_{00}} + {p_{01}} + {p_{10}} + {p_{11}} $下的条件极值。作函数为:
$$ \begin{array}{*{20}{c}} {{F^*} = {f^*} + \lambda ({p_{00}}^* + {p_{01}}^* + {p_{10}}^* + {p_{11}}^* - } \\ {{p_{00}} - {p_{01}} - {p_{10}} - {p_{11}})} \end{array} $$ (22) 同样对其所有变量($ {p_{00}}^*, {p_{01}}^*, {p_{10}}^*, {p_{11}}^*, {p_{00}}, {p_{01}}, {p_{10}}, {p_{11}} $及λ)求偏导并令所有偏导为0解得(篇幅有限,因此略去具体求解过程):$ {p_{00}}^* = {p_{01}}^* = {p_{10}}^* = $$ {p_{11}}^* = {p_{00}} = {p_{01}} = {p_{10}} = {p_{11}} $,即$ {p_1}^* = {p_1} = {p_f} $。此时函数f*=0。再通过比较在D的边界上的函数值求函数f的最大最小值。经过比较可知:f*在边界点$ {p_1}^* = {p_f} = {p_1} = 1 $处取得最小值0,又函数在在驻点处函数值等于0。故在定义域有界区域D内:$ {f^*}|\min = 0 $,即f*≥0。证毕。
引理3说明了在相同的输入不确定度条件下,CMOS与非门在已知X的条件下,Y不确定度的减少量大于MRF与非门。
引理4 在输出正确概率相同的条件下,互信息与信息熵比值$ I(X;Y)/H(Y) $的关系为:
$$ \frac{{I(X;{Y_{{\text{CMOS}}}})}}{{H({Y_{{\text{CMOS}}}})}} \leqslant \frac{{I(X;{Y_{{\text{MRF}}}})}}{{H({Y_{{\text{MRF}}}})}} $$ (23) 其中假设两者具有相同的输入X。
证明:设辅助函数:
$$ \begin{array}{*{20}{c}} \begin{gathered} G = \frac{{I(X;{Y_{{\text{CMOS}}}})}}{{H({Y_{{\text{CMOS}}}})}} - \frac{{I(X;{Y_{{\text{MRF}}}})}}{{H({Y_{{\text{MRF}}}})}} = \\ \frac{{H({Y_{{\text{MRF}}}}|X)}}{{H({Y_{{\text{MRF}}}})}} - \frac{{H({Y_{{\text{CMOS}}}}|X)}}{{H({Y_{{\text{CMOS}}}})}} = \\ \end{gathered} \\ {\frac{{H({Y_{{\text{MRF}}}}|X)H({Y_{{\text{CMOS}}}}) - H({Y_{{\text{CMOS}}}}|X)H({Y_{{\text{MRF}}}})}}{{H({Y_{{\text{MRF}}}})H({Y_{{\text{CMOS}}}})}}} \end{array} $$ (24) 考虑函数:
$$ \begin{array}{*{20}{c}} \begin{gathered} g = H({Y_{{\text{MRF}}}}|X)H({Y_{{\text{CMOS}}}}) - H({Y_{{\text{CMOS}}}}|X)H({Y_{{\text{MRF}}}}) = \\ {\kern 1pt} {\kern 1pt} \frac{1}{4}[H({p_{00}}^*) + H({p_{01}}^*) + H({p_{10}}^*) + H({p_{11}}^*)]H(p){\kern 1pt} - \\ \end{gathered} \\ {\frac{1}{4}[H({p_{00}}) + H({p_{01}}) + H({p_{10}}) + H({p_{11}})]H({p^*})} \end{array} $$ (25) 在条件$ {p_{00}}^* + {p_{01}}^* + {p_{10}}^* + {p_{11}}^* = {p_{00}} + {p_{01}} + {p_{10}} + {p_{11}} $下的条件极值。令:
$$ \begin{array}{*{20}{c}} {{g^*} = g + \lambda ({p_{00}}^* + {p_{01}}^* + {p_{10}}^* + {p_{11}}^* - } \\ {{p_{00}} - {p_{01}} - {p_{10}} - {p_{11}})} \end{array} $$ (26) 基于同样的方法,对g*关于$ {p_{00}}^*, {p_{01}}^*, {p_{10}}^*, {p_{11}}^*, $$ {p_{00}}, {p_{01}}, {p_{10}}, {p_{11}} $及λ求偏导,并令偏导为零解得(篇幅有限,因此略去具体求解过程):$ {p_{00}}^* = {p_{01}}^* = {p_{10}}^* = $$ {p_{11}}^* = {p_{00}} = {p_{01}} = {p_{10}} = {p_{11}} = 1 $,即$ {p_1}^* = {p_1} = {p_f} = 1 $。此时函数g=0。再通过比较在D的边界上的函数值求函数g的最大最小值。经过比较可知:g在边界点$ {p_1}^* = {p_f} = {p_1} = 1 $处取得最大值0,又函数在在驻点处函数值等于0。故在定义域有界区域D内:g|max=0,即g≤0。又因为$ G = g/[H({Y_{{\text{MRF}}}})H({Y_{{\text{CMOS}}}})] $,由g≤0得到G≤0。证毕。
由于I(X; Y)表征的是已知X的条件下,Y不确定度的减少量,H(Y)表征的是Y不确定度。因此认为I(X; Y)/H(Y)表征了已知X的条件下,Y不确定度减少的百分比。引理4说明了在相同的输入并已知X的条件下,MRF与非门的Y不确定度减少的百分比大于CMOS与非门,即与传统CMOS相比,MRF电路可以减少一定的不确定度。
定理 在输出正确概率相同,且负载电容相同的条件下,MRF电路与传统电路供电电压下界的关系为:
$$ {V_{{\text{dd}} - {\text{CMOS}}}}{|_{\min }} \geqslant {V_{{\text{dd}} - {\text{MRF}}}}{|_{\min }} $$ (27) 其中假设两者具有相同的输入X。
证明:由文献[23]知最小信息传输速率$ R = {f_s}H(Y) $,信道容量$ C = {C_u}{f_c} $,其中$ {C_u} = \mathop {\max }\limits_{\forall p(x)} I(X;Y) $为每用信道容量,$ {f_c} = {k_m}{({V_{{\text{dd}}}} - {V_t})^2}/ $ $ ({V_{{\text{dd}}}}{C_L}) $为信道速率,且km为NMOS/PMOS的跨导,Vdd为供电电压,Vt为阈值电压,CL为负载电容。因此由文献[23]可知,信道速率fc在电路中与电路特性息息相关,其与供电电压成正比,与负载电容成反比。
因此由R≤C可得$ {V_{{\text{dd}}}}{|_{\min }} = {C_L}{f_s}H(Y)/ $$ [I(X;Y){k_m}] $,其中假设$ {V_{{\text{dd}}}} \gg {V_t} $。又由引理4知$ I(X;{Y_{{\text{CMOS}}}})/H({Y_{{\text{CMOS}}}}) \leqslant I(X;{Y_{{\text{MRF}}}})/H({Y_{{\text{MRF}}}}) $,且负载电容相等,则有:
$$ {V_{{\text{dd}} - {\text{CMOS}}}}{|_{\min }} \geqslant {V_{{\text{dd}} - {\text{MRF}}}}{|_{\min }} $$ (28) 证毕。
利用MATLAB进行电路仿真实验。假设pf=1,互信息IX; Y、Vdd|min与p1*的关系曲线如图 6所示,其中$ {C_L} = {\kern 1pt} 6{\text{ }}\operatorname{fF} {\kern 1pt}, {k_m} = 80{\text{ }}\mu \operatorname{A} /{\operatorname{V} ^2} $。
从图 6可看出,$ I(X;{Y_{{\text{CMOS}}}}) \leqslant I(X;{Y_{{\text{MRF}}}}) $以及$ {V_{{\text{dd}} - {\text{CMOS}}}}{|_{\min }} \geqslant {V_{{\text{dd}} - {\text{MRF}}}}{|_{\min }} $。仿真结果与引理3、4及定理的结论一致。本文的方法同样可用于其他MRF电路或模块的可靠性与电压供电电压下界分析。
Supply Voltage Analysis of Asymmetry-Based MRF Circuits via Information Theory
-
摘要: 信息论是通信系统研究的基本数学方法,现有研究多是从信息论的角度对称等效电路模型进行能耗下界方面的分析,鲜有文献面向非对称电路模型开展信息传递对其容错性和供电电压关系进行研究。该文用信息论对非对称数字电路的可靠性和供电电压分析方法进行研究,并以新型超低功耗高容错马尔可夫(MRF)电路为切入点,通过4个关于熵、条件熵、和互信息的定理证明,得出了MRF电路的供电电压下界并且证明出其结构拥有较传统数字电路更低的电压下界。这些分析工作为非对称MRF电路的设计和研究提供了理论基础。Abstract: Information theory is the mathematic foundation for communication systems. The existing researches focus on low energy consumption bound analysis with the equivalent model of the symmetry circuits from the view point of information theory, and there are few works which focus on the analysis of the relationship among the information transmission, the reliability, and the supply voltage for the asymmetry circuits. The main contribution of this paper provides an analysis methodology for the reliability and supply voltage of asymmetry-based digital circuits with information theory. We use the new Markov random field (MRF) circuits, which can achieve ultra low power and high fault tolerance, as the analysis case. We demonstrate that the low supply voltage bound of MRF circuits is lower than that of traditional CMOS circuits through the proof of four lemmas of entropy, conditional entropy, and mutual information. This work can provide a theoretical basis for the research and design of the asymmetry-based MRF.
-
Key words:
- asymmetry /
- information theory /
- low power /
- MRF
-
表 1 两输入与非门输出正确概率
Vin1 Vin2 Vs1Vs2 Vout 正确概率 00 00 1 p00 $ {p_1}{p_2}{p_3} $ 01 $ {p_1}(1 - {p_2}){p_3} $ 10 $ (1 - {p_1}){p_2}{p_3} $ 11 $ (1 - {p_1})(1 - {p_2})(1 - {p_3}) $ 01 00 1 p01 $ {p_1}(1 - {p_2}){p_3} $ 01 ${p_1}{p_2}{p_3} $ 10 $ (1 - {p_1})(1 - {p_2}){p_3} $ 11 $ (1 - {p_1}){p_2}(1 - {p_3}) $ 10 00 1 p10 $ (1 - {p_1}){p_2}{p_3} $ 01 $ (1 - {p_1})(1 - {p_2}){p_3} $ 10 ${p_1}{p_2}{p_3} $ 11 $ {p_1}(1 - {p_2})(1 - {p_3}) $ 11 00 0 p11 $ (1 - {p_1})(1 - {p_2})(1 - {p_3}) $ 01 $(1 - {p_1}){p_2}(1 - {p_3}) $ 10 ${p_1}(1 - {p_2})(1 - {p_3}) $ 11 ${p_1}{p_2}{p_3} $ 表 2 三输入与非门输出正确概率
$ {V_{{\text{in}}1}}^*{V_{{\text{in}}2}}^*{V_{{\text{in}}3}}^* $ $ {V_{s1}}^*{V_{s2}}^*{V_{s3}}^* $ $ {V_{{\text{out}}}}^* $ 正确概率 000 其他 1 $ [1 - {(1 - {p_1}^*)^2}(1 - {p_f})]{p_3}^* $ 111 $ {(1 - {p_1}^*)^2}(1 - {p_f})(1 - {p_3}^*) $ 001 其他 1 $ [1 - {(1 - {p_1}^*)^2}{p_f}]{p_3}^* $ 111 $ {(1 - {p_1}^*)^2}{p_f}(1 - {p_3}^*) $ 010 其他 1 $ [1 - (1 - {p_1}^*){p_1}^*(1 - {p_f})]{p_3}^* $ 111 $ (1 - {p_1}^*){p_1}^*(1 - {p_f})(1 - {p_3}^*) $ 011 其他 1 $ [1 - (1 - {p_1}^*){p_1}^*{p_f}]{p_3}^* $ 111 $ (1 - {p_1}^*){p_1}^*{p_f}(1 - {p_3}^*) $ 100 其他 1 $ [1 - {p_1}^*(1 - {p_1}^*)(1 - {p_f})]{p_3}^* $ 111 $ {p_1}^*(1 - {p_1}^*)(1 - {p_f})(1 - {p_3}^*) $ 101 其他 1 $ [1 - {p_1}^*(1 - {p_1}^*){p_f}]{p_3}^* $ 111 $ {p_1}^*(1 - {p_1}^*){p_f}(1 - {p_3}^*) $ 110 其他 1 $ [1 - {p_1}{*^2}(1 - {p_f})]{p_3}* $ 111 $ {p_1}{*^2}(1 - {p_f})(1 - {p_3}*) $ 111 其他 0 $ [1 - {p_1}{*^2}{p_f}](1 - {p_3}*) $ 111 $ {p_1}{*^2}{p_f}{p_3}* $ 表 3 与非门输出概率分布
概率p 0 1 $ p({Y_{{\text{CMOS}}}}) $ $ p({Y_{{\text{MRF}}}}) $ 表 4 联合概率分布
$ p({x_1}{x_2},y) $ (00, 0) (00, 1) (01, 0) (01, 1) (10, 0) (10, 1) (11, 0) (11, 1) $ p{(X,Y)_{{\text{CMOS}}}} $ $ \frac{1}{4}(1 - {p_{00}}) $ $ \frac{1}{4}{p_{00}} $ $ \frac{1}{4}(1 - {p_{01}}) $ $ \frac{1}{4}{p_{01}} $ $ \frac{1}{4}(1 - {p_{10}}) $ $ \frac{1}{4}{p_{10}} $ $ \frac{1}{4}{p_{11}} $ $ \frac{1}{4}(1 - {p_{11}}) $ $ p{(X,Y)_{{\text{MRF}}}} $ $ \frac{1}{4}(1 - {p_{00}}^*) $ $ \frac{1}{4}{p_{00}}^* $ $ \frac{1}{4}(1 - {p_{01}}^*) $ $ \frac{1}{4}{p_{01}}^* $ $ \frac{1}{4}(1 - {p_{10}}^*) $ $ \frac{1}{4}{p_{10}}^* $ $ \frac{1}{4}{p_{11}}^* $ $ \frac{1}{4}(1 - {p_{11}}^*) $ -
[1] MOORE G E. Cramming more components onto integrated circuits[J]. IEEE Solid-State Circuits Society Newsletter, 2006, 11(5):33-35. http://cn.bing.com/academic/profile?id=2025516544&encoded=0&v=paper_preview&mkt=zh-cn [2] ZYUBAN V, STRENSKI P. Unified methodology for resolving power-performance tradeoffs at the micro architectural and circuit levels[C]//2002 international symposium on Low power electronics and design. Monterey:IEEE, 2002:166-171. http://cn.bing.com/academic/profile?id=2169065640&encoded=0&v=paper_preview&mkt=zh-cn [3] MEZHIBA A V, FRIEDMAN E G. Scaling trends of on-chip power distribution noise[J]. IEEE Transactions on VLSI, 2004, 12(4):386-394. doi: 10.1109/TVLSI.2004.825834 [4] JINDAL R P. Compact noise models for MOSFETs[J]. IEEE Transactions on Electron Devices, 2006, 53(9):2051-2061. doi: 10.1109/TED.2006.880368 [5] HUANG Yue-hui, ZHANG Mu-shui, TAN Hong-zhou. A novel method for IR-drop reduction in high-performance printed circuit boards[C]//201415th International Conference on Electronic Packaging Technology (ICEPT). Chengdu:IEEE, 2014:583-586. [6] SHIUE G H, SHIU J H, CHIU P W. Analysis and design of crosstalk noise reduction for coupled striplines inserted guard trace with an Open-Stub on Time-Domain in High-Speed digital circuits[J]. IEEE Transactions on Components, Packaging and Manufacturing Technology, 2011, 1(10):1573-1582. doi: 10.1109/TCPMT.2011.2163309 [7] TUUNA S, ISOAHO J, TENHUNEN H. Skewing-based method for reduction of functional crosstalk and power supply noise caused by on-chip buses[J]. Computers & Digital Techniques, 2012, 6(2):114-124. http://cn.bing.com/academic/profile?id=1991779897&encoded=0&v=paper_preview&mkt=zh-cn [8] SEKI K, KANAZAWA K, YASUNAGA M. Crosstalk-noise reduction in GHz domain using segmental transmission line[C]//2013 IEEE Electrical Design of Advanced Packaging and Systems Symposium (EDAPS). Nara:IEEE, 2013:96-99. [9] JIANG Zhong-wei, WANG Zheng, WANG L C, et al. Levelized low cost delay test compaction considering IR-drop induced power supply noise[C]//2011 IEEE 29th VLSI Test Symposium. California:IEEE, 2011:52-57. [10] MAJUMDAR A, CUNNINGHAM J E, KRISHNAMOORTHY A V. Alignment and performance considerations for capacitive, inductive, and optical proximity communication[J]. IEEE Transactions on Advanced Packaging, 2010, 33(3):690-701. doi: 10.1109/TADVP.2010.2049355 [11] AMARICAI A, NIMARA S, BONCALO O, et al. Probabilistic gate level fault modeling for near and Sub-Threshold CMOS circuits[C]//201417th Euromicro Conference on Digital System Design. Verona:IEEE, 2014:473-479. [12] LIU Kai-kai, AN Ting, CAI Hao. et al. A general cost-effective design structure for probabilistic-based noise-tolerant logic functions in nanometer CMOS technology[C]//2013 IEEE EUROCON. Zagreb:IEEE, 2013:1829-1836. [13] HEGDE R, SHANBHAG N R. Soft digital signal processing[J]. IEEE Transactions on VLSI, 2001, 9(6):813-823. doi: 10.1109/92.974895 [14] HEGDE R, SHANBHAG N R. Energy-efficient signal processing via algorithmic noise-tolerance[C]//1999 International Symposium on Low Power Electronics and Design. San Diego, CA, USA:IEEE, 1999:30-35. [15] LIN Y, DORIS K, HEGT H, et al. A dynamic latched comparator for low supply voltages down to 0.45V in 65-nm CMOS[C]//IEEE International Symposium on Circuits and Systems (ISCAS). Yeosu:IEEE, 2012:2737-2740. [16] YANG Y, BINKLEY D M, LI L. All-CMOS subbandgap reference circuit operating at low supply voltage[C]//IEEE International Symposium on Circuits and Systems (ISCAS). Rio de Janeiro:IEEE, 2011:15-18. http://www.researchgate.net/publication/221370723_All-CMOS_subbandgap_reference_circuit_operating_at_low_supply_voltage [17] GOPAL H V, GUPTA P, BAGHINI M S. Ultra low-supply voltage reference generator with low sensitivity to PVT variations[C]//20135th Asia Symposium on Quality Electronic Design (ASQED). Penang:IEEE, 2013:18-21. [18] NEPAL K, BAHAR R I, MUDDY J, et al. MRF reinforcer:A probabilistic element for space redundancy in nanoscale circuits[J]. IEEE Micro, 2006, 26(5):19-27 doi: 10.1109/MM.2006.96 [19] LU Zheng-hao, YU Xiao-peng, YEO Kiat-seng. Design of probabilistic-based Markov random field logic gates in 65nm CMOS technology[C]//2010 International SoC Design Conference (ISOCC). Seoul:IEEE, 2010:311-314. [20] LI Yan, HU Jian-hao. Extensional design for noise-tolerate MRF standard cells via global mapping[C]//2014 IEEE International Symposium on Circuits and Systems (ISCAS). Melbourne VIC:IEEE, 2014:1728-1731. [21] FAN X, TANIK M M, An experiment on evolutionary design of combinational logic circuits using information theory[C]//2011 Proceedings of IEEE Southeastcon. Nashville:IEEE, 2011:379-383. [22] GROVER P, GOLDSMITH A, SAHAI A, et al. Information theory meets circuit design:why capacity-approaching codes require more chip area and power[C]//49th Annual Allerton Conference on Communication, Control, and Computing. Monticello:IEEE, 2011:1392-1399. [23] WANG L, SHANBHAG N R. Energy-efficiency bounds for deep submicron VLSI systems in the presence of noise[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2003, 11(2):254-269. doi: 10.1109/TVLSI.2003.810783 [24] COVER T M, THOMAS J A. Elements of information theory[M]. 2nd. Oxford:Wiley-Blackwell, 2006:7-13. [25] KORKMAZ P. Probabilistic CMOS (PCMOS) in the nanoelectronics regime[D]. Atlanta:Georgia Institute of Technology, 2007.