数电 | Info Church X.

数制

数制关注：范围range、分辨率resolution、精度accuracy

定点数fixed point numbers

一个固定的模或者基数base/radix

Binary-2 Decimal-10 Octal-8 Hex-16

Why do computer programmers confuse Christmas and Halloween? Because Dec 25=Oct 31

bit=1 nibble=4 byte=8 word=16 double word=32 (单位bit)

进制转换

r进制转10进制

, where

十进制转r进制

整数部分：不断//r；从→ 小数部分：不断*r，取出整数部分作为结果，然后再对小数部分操作；从→

Complement code

Def (r-1)’s complement反码

，按位取反（变成）即可

Def r’s complement补码

，反码+1

Note 小数取补码，只需要当做小数点不存在。因为两个定点小数的加减法只需要先乘使其变成整数，按照整数加减后再乘还原小数点的位置。

N-M 就是 N+M的补码。如果最高位有进位说明N>M得到正数，否则说明N<M得到负数（的补码）

a+b=c溢出分析

insight：不同符号数的运算一定不会溢出

方法1：如果ab符号位相同，且不同于c的符号位，发生溢出

方法2：如果（符号位进位）与（符号位前一位进位）不同，则发生溢出

符号位扩展

当需要扩展数据的位数而不改变其值的时候，在左侧复制其符号位

BCD code(8-4-2-1)

把十进制每一位变成4bit二进制，然后拼接

例

加法：4位一起处理，如果超过9则在该位+(0110)

减法：求10’s complement。BCD码本质还是Dec

2421 code

MSB权重从8变成了2。十进制下0~4MSB=0，5~9MSB=1 好处是相对于9互补。

Excess-3 code

在BCD码的基础上+3，这样也能形成互补

Gray code

相邻两个码字之间仅有1位不同。这样避免了各个bit的变化有快慢、在变化过程中出现错误码字的情况

构造方法：逐位向高位扩展，保持镜像对称

二进制转格雷码：若则，否则为1。（）最高位与0比较

格雷码默认生成个码字，但任意偶数个码字都可以对称的截取且仍然满足相邻两个码字之间仅有1位不同，例如excess-3 gray code

Error-detecting code

接收到异常码字，如BCD接收1011

校验位。比如奇偶校验，加入一位后使得编码中1的个数为奇/偶数个。

Error-correcting code

Def code distance编码距离：有效码字之间最小bit差异

将非编码码字就近判定为正确的码字。比如码距为3时，可以纠正1bit的错误。

mindis=2c+d+1，c为可纠错bit数，d为可追加检错bit数（即错1~c个能纠正，错c+1~c+d个能检出错）

Hamming code dis=3

例，引入124位作为校验位，对其余信息位进行交叉的奇偶校验

二维编码

比如先对每一行生成校验码，再对每一列（包括刚才生成的校验码）生成校验码。这样信息位变动一个，会导致有列变化一个码字。而每一列变一个码字就会贡献的码距。

故而

布尔代数

Properties of Bool Algebra

Duality: and与or互换，0与1互换（输入变量不需要取补！），等式仍然成立

Distribution law:

(from duality)

Absorption law:

Merge law:

De Morgan’s law:

Inclusion law: （）

（）

AND OR XOR XNOR满足交换律和结合律，可以很方便的级联扩展

但NAND NOR只满足交换律不满足结合律，直接级联并不能扩展为多输入门

单单用NAND门或者NOR门就可以实现所有的电路

电路的逻辑有两种，组合逻辑（输出只与当前输入有关）和时序逻辑（输出还与之前时刻的状态有关）

组合逻辑

优化指标

输入个数literal：一般门电路最大输入个数fan-in为4

门的个数：实际应用中比输入个数更重要。由于连线也要占用面积，所以在尺寸不断微缩下，这个指标的重要性也在下降

门的级数：关键路径的传播延迟。信号从栅极到漏极产生一单位的延迟

积之和&和之积

最小项：单个字符相乘

最大项：单个字符相加

正则（全部是最小项/最大项，没有经过化简）SOP和POS是布尔逻辑的两种规范表达canonical form

正则积之和(SOP)：所有f=1的最小项加起来，如。注意每一项都必须是最小项，才能称为正则积之和。

正则和之积(POS)：所有f=0的最小项的非乘起来，如。注意每一项都必须是最大项，才能称为正则和之积。

用卡诺图化简POS：圈出所有的0，把最小项求非，比如M(3)=(AB)’=A’+B’（M(x)x二进制中0→A，1→A’，与m相反）。然后把这些项乘起来

任何“与-或”电路可以用具有相同拓扑结构的“与非-与非”电路实现；任何“或-与”电路可以用具有相同拓扑结构的“或非-或非”电路实现

卡诺图

注意4变量卡诺图除了左右边、上下边相邻，四个角也是相邻的

5变量卡诺图由两张4变量卡诺图组成，对应位置都为1则可以消去x5

无关项：永远不会出现的输入的组合。可以根据方便任意的赋值为0或1，在卡诺图中用d或x表示

最小化策略

对SOP形式，覆盖所有1；对POS形式，覆盖所有0。两种方法的消去变量的方法是一致的，下面均以SOP为例

字符(literal)：乘积里有几项就是几个字符，x和x’是不同的字符，重复出现重复计算。例AB’+AC+A’B是6个字符

蕴含项(Implicant)：该项对应框内全是1

质蕴含项/素项(Prime Implicant)：不能被包含进字符数更少（框更大）的蕴含项中

基本质蕴涵项(Essential Prime Implicant)：包含了一个最小项，该最小项不在其他质蕴涵项中。容易发现，基本质蕴涵项必须被包括在一个覆盖中

覆盖：所有框加起来盖住所有1

成本：总逻辑门数量+所有逻辑门的输入数，并假定原始输入的非可以无成本获得

二级电路

卡诺图和SOP/POS给出了两级电路的实现方式：0级对应变量或其补，1级对应最小项/最大项，2级对应求和或求积

通过在1级输出、2级输入同时取非，把SOP变成全NAND电路，把POS变成全NOR电路。相同面积下，NAND速度比NOR快，因此一般选择SOP的NAND-NAND结构

多级电路

通过放松延迟的要求，可能得到更少的门的方案

多输出电路

对多输出电路，由于部分电路可以共享，整体成本最小的方式可能不是让各自的成本都最小，以上寻找基本质蕴涵项的方法不成立

竞争和冒险（动态特性）

静态0/1型冒险：本该是维持0/1不变，但中途短暂跳变到1/0。SOP容易出现静态1型冒险，POS容易出现静态0型冒险

可以理解为x+x’=1,xx’=0都不再成立。对SOP，从最小项之和化简会用到x+x’=1；对POS，从最大项之积化简会用到xx’=0

当1bit的变化被包含在不同的两个蕴含项中，因为非门一般都有延迟，可能使得两个蕴含项都不被满足，就有产生冒险的可能。

解决方法是，对POS，添加一些蕴含项，使得卡诺图上相邻1都被包含在同一个蕴含项中（这样输出结果就跟那个变量的变化无关，事实上也确实应该如此）；对SOP，添加一些蕴含项，使得卡诺图上相邻0都被包含在同一个蕴含项中

多bit的冒险难以解决，也没有必要解决。

动态冒险：在0→1,1→0的切换中，电平来回跳变。一般是因为单bit或其补到输出有三条及以上路径，前级电路产生静态冒险，加上后级电路的信号延迟。常见于多级电路

CMOS

基本结构

上拉网络用PMOS（图上有圈），输入自带非；下拉网络用NMOS，输出自带非

如果下拉网络的函数为，上拉网络函数应与其相等，为。又因为上拉网络输入自带非，下拉网络输出自带非，故PMOS网络只需要在结构上与NMOS形成对偶（串↔并互换），即可构成CMOS结构

下面我们需要关注MOS器件的静/动态电气特性，主要是为了保证我们设计的电路确实呈现出预期的逻辑运算

测试条件中Min=5V*(1-10%)=4.5V，Max=5V*(1+10%)=5.5V

Typ.代表条件为VCC=5V，25°C时的typical value

噪声容限Noise Margins(DC)

输出0/1极限、与输入判定的0/1极限、之间的差距。

输入极限一般为VCC的30%和70%

以右图为例，输入判定0/1的极限为1.35V/3.15V；输出0/1的极限为0.1V/4.4V，故高低电平噪声容限均为1.25V

和有两个值，取决于输出电流是大还是小（TTL逻辑orCMOS逻辑），在这里我们关注纯CMOS电路，此时输出电流很小(<20uA)。图中划线是错误的

输入电流

、分别表示在输入高/低电平时能（从Gate）流入MOS管的最大电流。负号表示流出

Fan-out(DC)

、表示在维持输出电平满足的条件下，能从输出端流入(sink)MOS管的最大电流。负号表示流出(source)

sink：从电源流经负载，由MOS再到地（负载→MOS）

source：从电源流经MOS，由负载再到地（MOS→负载）

fan-out表示MOS管的输出能驱动器件的个数，为和中的较小值

如果负载是阻性网络，简化为戴维宁电路，在极端输出电压情况下看有没有超过输出电流的限制

导通电阻

对CMOS而言，输出高电平可以认为上拉电阻Rp很小，下拉电阻Rn很大；输出低电平反之

💡

！！这里电阻不是等效MOS管内部的电阻，而是把整个PMOS/NMOS网络等效成一个电阻！

当输入较理想时，可以认为较大的=inf，较小的可以通过和计算。一般地，我们考虑极端情况下的，我们只关心电路能不能正确运行，并不关心具体的电压是多少

当输入电平没有那么理想，Rp+Rn将会变小，此时将会有一个不小的静态电流和静态功耗

转换时间Transition Time

输出在高低电平之间转换需要的时间，在实际波形图中，计算两个阈值之间的时间（即在undefined区域所花的时间）。0→1和1→0的转换时间可能不同

传输延迟Propagation Delay

对某个信号线路而言，输入变化引起输出变化所需时间

关键路径：传输延迟最大的路径，决定了工作频率的上限

MAX：路径上器件tpLHmax,tpHLmax中的较大者的和，取所有路径中最大值

MIN：路径上器件tpLHmin,tpHLmin中的较小者的和，取所有路径中最小值

Typical：

f一定时，VDD越大，等效的Rp/Rn越小，从而传输延迟越小。这里有功耗和性能的trade-off

然而，在功率密度一定的时候，降低VDD能提升速度，这是因为我们可以取更大的f

功耗

静态功耗一般很小（16nm以下就不能忽略了）

动态功耗

其中为power-dissipation capacitance。MOS管在转换时会有短暂的上下均导通，引入等效电容来衡量

f代表切换的频率。当然负载电容上信号变化频率可能与系统工作频率不同

代表负载电容。为负载电路切换的频率，两次切换才是一个周期！

尺寸微缩

功率密度

.当尺寸变为1/S，N→S^2N，C→1/SC

如果我们同时让V→1/SV，那么f→Sf

因此功率密度一定时，通过缩小尺寸，我们可以提升晶体管数量，同时提升频率

但实际上电压不能一直反比缩放，过小的电压难以控制电流。因此现在微缩时电压基本不变，这就会导致P→S^2P

延迟

R~L/W，C~WL，因此延时T~L^2。通过缩小L我们可以降低延迟；W的影响不大

漏极开路门电路

把上拉回路变成电阻。当NMOS输出1，等效的Rn很大，与Rup分压，差不多可以实现输出Vcc

好处：

能实现较大电流驱动，如果PMOS上拉电流就会比较小

方便驱动多源总线，比三态门管子少

直接把输出的导线接在一起而没有烧毁的风险，因为Rup可以控制最大输入电流，从而实现“线与”

坏处：

集成电路中电阻难以实现，一般需要用MOS管钳位

电阻一般较大，从而时延较大

三态输出门

高阻态”Z”，类似于电压表，“悬浮”，不对电路产生影响

用于把多个输出挂到总线上而不至于烧毁

传输门

EN=0两个管均不导通，EN=1总有一个管导通

可以传递模拟信号，是双向的

闩锁效应

如果输入信号低于GND或者高于VCC，容易形成自锁，在电源和GND之间形成大电流。解锁只能切断电源

USB设计：电源线长于信号线，确保先接上信号

组合逻辑电路的实现技术

常用器件

Encoder编码器：2^n输入，n输出。将2^n取1码编码为n位二进制

最低位为1的输出和全0的输出都是000，因此需要加一个或门来判断2^n个输入中是否至少有一个非0

典型应用：仲裁器+编码器=优先级编码器。比如多个设备同时向CPU通信，优先级编码器告诉CPU优先级最高的是哪个。仲裁器选出2^n个信号（可能有多个1）中优先级最高的一个

Decoder译码器：n输入，2^n输出。输出2^n取1码，即最小项。同一时刻有且仅有一个最小项输出被激活为1（低有效情况则是只有一个0）可能还有一个Enable输入

实际电路中，低有效（即只有一个为0，作为激活信号）有更好的area&latency，因为与非、或非只需要一级电路

译码器的级联

例如，用5个3-8decoder实现1个5-32decoder。一个3-8decoder作为2-4decoder使用（enable signal片选使能信号），根据前两位控制后级4个3-8线译码器

典型应用：指令译码，选通某个功能模块/外设；在存储器中选择不同的Bank/不同的row(word)
在存储器中一般地址较长，经由一个Decoder选择的话Decoder会非常大。可以先选择一部分地址，输出多个word；再用剩余地址控制MUX，选择究竟要输出哪个word，这样Decoder和MUX都不会太大

Multiplexer(Mux)多路复用器：2^n个输入，1个输出，用n个控制信号决定输出采用哪个输入

Mux的实现

逻辑门。需要MOS管数量较多（最少14个）。

传输门。需要MOS管较少，但信号没有再生，且输出采用线与，必须保证任何时刻最多只有一个D的通路开启。

decoder。译码器输出用于激活开关。

Mux的级联

Demultiplexer(DeMux)解多路复用器：1个输入，n个控制信号，2^n个输出。由n个控制型号控制，决定2^n个输出中哪个与其相连。

Demux可以用Decoder实现：Demux输入相当于Decoder的enable信号

基于基本单元

卡诺图化简给出了基于二级电路的统一实现方案。然而这对于电路扇入有很高要求。如果要求只能用二扇入的门，则必须增加电路级数，进而会增加latency；另外中间化简过程也比较耗时耗力

基于译码器

用decoder实现任意组合逻辑，只需要把所有最小项取OR即可。一般电路中最大基本译码器是3-8线译码器，这样只要最多4输入的或门就能实现，因为>4个最小项可以用剩余<4个最小项的或再取非

预先构造AND-OR全连接整列，把不需要的连结熔断

PAL：固定OR阵列，只有AND阵列可编程

基于查找表(MUX)

如果我们把真值表“存储”在2^n个输入中，用控制信号代表输入，那么输出就是真值表需要的输出。

一种简化方式：Mux的输入可以是其中一个变量

基于查找表(ROM)

ROM：横的是word line字线，竖的是bit line位线

bit line上端置1，用Mux选择激活哪条word line（仅激活一根）表示读出那个word，此时各条bit line上会同时读出这个word各个位上的值

具体而言，如果交叉点有MOS管，bit line下端读出0，否则读出1。bit line采用了线与的形式，类似总线结构

ROM有两个开关：Chip Selection(CS)控制ROM是否有电工作，Output Enable(OE)控制ROM的输出是否是高阻态。只有CS和OE均开启，ROM才能输出到总线上。

假设word line有2^N条，bit line有M条，那么这个ROM阵列存储的就是2^N个Mbit数据，可以用来实现任意N输入-M输出的真值表。

现在的FPGA多采用ROM或者RAM实现，可以吃到先进工艺的红利

算术运算电路

比较器

Equality Comparator相等比较器

两种方法，左边串行，右边并行。

串行latency高，容易扩展；并行对或门扇入要求高，相对不容易扩展

Magnitude Compatator幅度比较器

可以输出是否大于，是否小于，是否等于

大于的判断：所有更高位是否相等+当前位比较⇒当前位是否大于

是否小于用大于和等于加一个或非来输出

更大位宽比较器

级联。前一个比较器结果作为下一个比较器的最低位输入。容易扩展，时延较高。
并行/树状。分组比较，把分组比较的结果再比较。不太容易扩展，时延低。

加法器

Ripple-Carry Adder(RCA，行波进位加法器)

全加器两种实现方式：

左边6个门，2级延时；右边5个门，3级延时。（如果认为所有门的延时都一样）

n位加法需要2n/3n级延时

Carry Lookahead Circuits（超前进位电路）

每一个进位信号都是Ai~A0,Bi~B0的函数，我们可以先通过组合逻辑得到这些进位信号，然后同步给到所有全加器，从而减少时延

定义，

（*）

容易发现，定义Pi=Ai+Bi也不影响结果，实际电路中or比xor更容易实现。

第一级计算Gi@1,Pi@1，再两级电路得到Ci@3，再用AiBiCi得到Si@4

故4bit超前进位全加器Si@4,cout@3

4位以上，计算Ci时对OR的扇入要求太高，怎么办？

对每一个4bit超前进位全加器，定义gG（本加法器在无进位时能不能给下一个加法器提供进位）和gP（如果前级有进位，本加法器能不能把进位传递到下一个加法器）

注意gP、gG均与进位无关，因此gP@2，gG@3

4bit加法器的进位gCi逻辑与（*）相同，需要@2，从而gCi@5。

把gCi作为第i个4bit加法器的Cin，每个4bit加法器再用@3得到S[0:3]@8（第一步算Gi和Pi不计入延时，因为之前已经做完了，所以会比单独4bit加法器延时少1）

故如上扩展的16bit超前进位全加器总延时@8

Carry Select Adder进位选择加法器

用两个加法器分别算进位为01的情况，再用MUX选择

减法器

加入sub信号连到C0。如果sub=0，正常做加法；如果sub=1，将所有bi变成bi’，然后做加法。此时由于C0=1，实现了取补码中+1的动作

bi的控制可以用来实现，当sub=1时翻转

乘法器

组合式/阵列乘法器

同时实现N个部分积，然后一次性求和

时序逻辑

RS-Latch锁存器

RS=01 ⇒ Q=1

RS=10 ⇒ Q=0

RS=00 ⇒ Q=hold

RS=11 ⇒ forbidden

时钟clock

周期period：完整变化一次的时间

占空比duty-cycle（%）：有效时间占比

D-Latch（电平敏感）

RS-Latch对RS的毛刺很敏感。为了避免冒险，引入clock来控制何时取样RS的值。这是一种电平敏感型锁存器level-sensitive latch，当有效电平时“透明”（取样），否则维持原状

这样改进之后，在clock=1时仍然对毛刺敏感。我们可以去掉RS=00的保持功能，强制使得RS永远相反

上面的结构称为D Latch（D锁存器）

D-Flip-Flop（下降/上升沿敏感）

我们希望占空比越小越好，这样信号需要维持不变的时间就越短。为此，我们尝试构造对时钟的变化敏感的控制。

clock=1，P=S，Q保持；clock=0，P保持，Q=P

因此只有在下降沿的时候，来自S的信号才会被传到Q。

问题：clock=1的时候，P仍然对RS的毛刺敏感。比如P=0，RS在00中有一个01的毛刺，P本该保持为0，但由于01的毛刺就会变成1。注意这个1会延续到下降沿，进而影响Q的输出

解决：用两个D-Latch

这个整体称为D Flip-Flop（D触发器）

如果还想要有保持的功能，“加入”逻辑（就是把一个输入扩展成两个，跟高阻没关系）

比较

以下从左到右依次为：D-Latch，上升沿触发D-FlipFlop，下降沿触发D-FlipFlop

实际的DFF

优化之后只需要6个门来实现

复位、置位：同步or异步？哪个优先级高？

时序参数与时序规则

建立时间setup time ：时钟触发前，输入需要保持稳定的最小时间

保持时间hold time ：时钟触发后，输入需要保持稳定的最小时间

输入传输延迟：时钟有效触发时，输入端D的变化传递到Q所需的时间。触发器没有这个参数。

时钟传输延迟：时钟C触发后，输入传递到Q所需的时间

D-Latch

和分别看g→q，d→q的关键路径即可，没有什么特别的

g从高到低（从有效到无效）之前，d的值必须要传递到q和q’并稳定。

g从高到低（从有效到无效）之后，d不会影响输出，

为什么关注下降沿而非上升沿？因为对高有效DLatch，上升沿不存在亚稳态的问题。

D-FlipFlop

对DFF，没有意义。

，考察m传到q的时间，因为clock上升沿的时候m已经稳定了

，上升沿之前d需要稳定传递到m或m‘

，上升沿信号经过U1后关闭了U3U4，使得d的变化不会影响后续电路

时序规则

要保证电路正确工作，以上参数需要满足某些关系

对，考虑前后两个上升沿。前级1变化要在下一个上升沿前及时到达后级2

对，考虑单个上升沿。前级1变化不能太快地到达后级2而干扰后级2这一次上升沿的赋值。

💡

如果有多个同步DFF，Tpmax需要取所有输入→输出中延时的最大值！！Tpmin同理

考虑时钟偏移和抖动。把加到不等号小的那边（考虑极端情况）

最后我们得到图中的式子。

如果违反时序规则，可能出现亚稳态，电平介于01之间。最后因为温度的扰动，不确定地落到0或1。

寄存器电路

存储寄存器

每个时钟上升沿将IN存储并输出到OUT

扩展：RAM

可以作为pipeline memory，将上一级的输出与时钟对齐

移位寄存器Shift Registers

顺序存储最近输入的4个值，每个上跳沿往后移位一个

可以用于串并变换。（比如串行通信，并行接收）

通用移位寄存器

CLR可以作为低有效的ENABLE。

有四种功能：保持，右移，左移，写入

QA→RIN可以实现更多bit的移位寄存器

模式识别器

判断输入序列中有没有给定序列（下图左）

计数器

环形计数器（上图右）

输出独热编码001→010→100

问题：编码数量少，且有多个计数环路（不robust）

解决方案：引入自校准机制（下图左是原方案，下图右是改进方案）

优点：没有毛刺

应用：轮询各个外设的状态

扭环计数器Johnson Counter

每次把最后一位的非返回到输入端，这样能有2N个状态000→100→110→111→011→001→000

异常循环：010→101→010

存在2^N-2N个异常状态，仍然要引入自校正机制。只要当前状态为0xxx0，就强制load 000使之进入正常循环

线性反馈移位计数器

通过组合逻辑可以实现2^N-1个状态的计数器。全0是自锁状态

异步二进制计数器

Q’接下级时钟：累加计数 000→001→010→…（前级1→0后级翻转）

Q 接下级时钟：递减计数 111→110→…

问题：异步电路，延迟大，时钟不对齐

同步二进制计数器

根据上一次的状态OUT[3:0]，用组合逻辑计算出下一个状态OUT*[3:0]

通用4bit计数器

ENABLE=1时计数

可以并行的载入数据

RCO：当状态为1111时为高电平，用于计数器级联

Starting Offset Counter

到达1111后复位成0110，实现模10分频器

Cutoff Limit Counter

到达1101后复位成0000，实现模10分频器

有限状态机(FSM)

Moore机&Mealy机

从当前状态Sn，当前输入In得到下一个状态Sn+1和当前输出On

如果输出只与Sn有关，与In无关，则称为摩尔机（Moore Machine）；否则称为米利机（Mealy Machine）。核心区别在于输入的控制是同步/异步

激励方程（存储单元前）：（组合逻辑）

特征方程（存储单元）：（时序逻辑）

输出方程（存储单元后）：(Moore) (Mealy，任意时刻输入变化都可能引起输出变化，因为G是组合逻辑)

转移方程：结合激励方程和特征方程得到

💡

！关于Mealy机的异步性，假设当前在状态A，A→(x=0,out=1)→B; A→(x=1,out=0)→C

那么如果x在下个触发沿之前从0→1，out会跳变1→0，但次态只看触发沿时候的x，因此不会跳变！会稳定的A→C

因此Mealy机可以看成x变化是在不断的“选线”，线不同输出也不同；但最终去向哪个次态取决于触发沿的时候“选”在哪根线上

转化

Moore→Mealy：把输出放到“入边”上

Mealy→Moore：把输出放到下一个状态上，如有多种输出则克隆状态

状态机的优化

状态优化

相同输出的状态可以合并。但状态数最少的状态机不一定是最优的

编码优化

通过给每个状态分配恰当的编码来优化组合逻辑

数制