跳转至

3 Combinational Logic Design

文本统计：约 4470 个字

引言

按照功能，逻辑电路分为两类：

  • 组合电路(Combinational Circuit)
    • 拥有 m 个输入和 n 个输出，其中包含了 \(2^m\) 种输入组合，以及对应的 n 个不同的函数；
    • 最关键的是，它的 输出只依赖于这 m 个输入的组合（不包含回路）；
  • 时序电路(Sequential Logic Cirtuit)
    • 与之对应的，时序电路具有记忆功能，即它的输出可能会依赖之前的结果；

本章着眼于组合电路的相关内容，时序电路的相关内容将在下一章 介绍。

3.1 组合电路设计

表示逻辑的方法

  1. 真值表(Truth Table)；
  2. 布尔函数(Boolean Function)；
  3. 卡诺图(Karnaugh Maps)；
  4. 时序图(Timing Diagram)；
  5. 逻辑电路图(Logic Circuit)；

其中，下划线的方法在功能确定的情况下，其表示是唯一的。

而我们的设计，就是在满足功能的前提下，尽可能优化和找到最好的设计。

而主要的设计过程(Specification)如下：

  1. 确定系统的行为；
  2. 阐述输入和输出之间的逻辑关系，并用真值表或逻辑表达式(Formulation)表达出来；
  3. 优化逻辑表达以减少成本(比如使用卡诺图)；
  4. 将优化后的逻辑设计工艺映射到硬件实现上(Technology Mapping);
  5. 验证正确性（在仿真环境中）；
graph LR;

A["实际问题"] ===> B["真值表"]

B ==>|"化简"| C["最简功能"] ===>|"工艺映射"| D["网表"]

B ==>|"变换"| E["合适的表达式"] ===>|"工艺映射"| D

3.1.1 分层设计

分层设计即将复杂问题模块化分解为若干层次，然后逐个抽象解决。

其设计方法分为 自顶向下(Top-Down) 和 自底向上(Bottom-Up)。

前者从需求开始，自顶向下分解功能设计；后者根据现有的元件去组合成目标功能。

集成电路

集成电路(integrated circuits) 又叫 芯片(chip)，分为如下若干等级：

  • SSI(small-scale integrated) 内含不到 10 个 gates；
  • MSI(medium-scale integrated) 内含 10 ~ 100 个 gates；
  • LSI(large-scale integrated) 内含 成百上千 个 gates；
  • VLSI(very large-scale integrated) 内含 成千上亿 个 gates；

3.1.2 技术参数

门的实现主要通过这些参数特性来描述：

Name Description
Fan-in 一个门可用的输入
Fan-out 一个栅极输出驱动的标准负载数量
Logic Levels 被认为是高低电平的输入输出电压范围
Noise Margin 对外界噪声的容忍能力(具体来说是不会导致行为异变的最大噪声压值)
Cost for a gate 继承电路的门成本
Propagation Delay 信号改变后从输入到输出所需的变化时间
Power Dissipation 电源输出能耗和门的能耗

扇入扇出

扇入描述了一个门能够接受的最多输入量，如一个四输入与非门的扇入就是 4；而扇出描述的则是一个门的输出(栅极输出)在不降低工作性能的情况下能够负载多少门，例如一个非门的输出能够同时负载 4 个非门并且都能正常工作，则其扇出为 4，其也能通过标准负载来定义。

标准负载

所谓的标准负载，是衡量“负载”的一个“单位砝码”。其大小等于一个非门(逆变器)贡献的负载压力。

那么要如何评估负载呢？首先我们引入 过渡时间(transition time)：

转换时间 （Transition Time）

转换时间分为 \(\mathrm{t_{LH}}\)(rise time) 和 \(\mathrm{t_{HL}}\)(fall time) 两个部分。

  • rise time 等于栅极输出从 \(\mathrm{V_{CC}}\) 的 10% 升高到 90% 所需要的时间；
  • fall time 等于栅极输出从 \(\mathrm{V_{CC}}\) 的 90% 降低到 10% 所需要的时间；

通过时序图表示就是这样：

随着负载增加，转换时间也会增加（给电容充电的时间增加），而扇出定义中提到的“最大负载”，就是指它的转换时间不超过它预定的最大转换时间。

从左到右表示负载不断增加时，rise time 的变化趋势。

实际上，类似的，超出扇入后，门对输入的反应就太慢了。

传播延迟 （Propagation Delay）

传播延迟(propagation delay) 衡量了门的输入变化导致输出变化所需要的时间。由于从低电平转化到高电平和高电平转化到低电平所需要的时间不一样，所以传播延迟同样有两个部分，分别使用 \(\mathrm{t_{PHL}}\) 和 \(\mathrm{t_{PLH}} 来表示\)。

更具体的来说，传播延迟的计算方法是输入和输出的变化中点（即变化到 \(\frac{1}{2}V_{CC}\) 时）的时间差，通过时序图表示就是这样：

此外，我们还可以引入 \(\mathrm{ t_{pd} }\) 来统一表示 \(\mathrm{t_{PHL}}\) 和 \(\mathrm{t_{PLH}}\)。数值上，\(\mathrm{ t_{pd} } = average(\mathrm{t_{PHL}}, \mathrm{t_{PLH}})\) 或 \(\mathrm{ t_{pd} } = \max(\mathrm{t_{PHL}}, \mathrm{t_{PLH}})\)。

思考题

根据时序图，写出门的传播延迟，此处 \(\mathrm{ t_{pd} } = average(\mathrm{t_{PHL}}, \mathrm{t_{PLH}})\)。

Transition Time vs. Propagation Delay

转换时间专注于输出的变化，而传播延迟则包含了输入的变化和输出的变化整个过程。

从时序图上的表示来看，转换时间只需要输出的时序图即可表示；但传播延迟则是通过比较输入和输出的偏差来表示的。

3.1.3 延迟模型

为了研究为什么会存在门延迟，刻画门的 固有门延迟(inherent gate delay)，我们需要对其建模，常见的 延迟模型(delay model) 有以下两种：

  • 传输延迟(transport delay): 认为输入和输出之间的延迟是一个定值的；

  • 惯性延迟(inertial delay): 引入了 拒绝时间(rejection time)，只有当输入达到一定能量后，才会出发栅极输出（在这种模型下，噪音等会被过滤）；

将不存在延迟的模型、传输延迟模型和惯性延迟模型做比较地来看，就是如下情况：

Info

由于实际电路中实现延迟，数学上的逻辑表达式与实际电路情况会存在不同——即存在若干数学上无法直接解决的问题。

所以研究延迟是非常必要的。

延迟计算

计算一个电路的延迟时，有两方面需要考虑，一方面是电路自身所导致的一个固定延迟，另外一方面则是由于不同的负载导致的额外延迟。

在这个例子中，0.07 为固定延迟，0.021 为一个标准负载带来的延迟系数，SL(4.5 here) 则是标准化的负载量。

而具体的表达式，会在 Cell Library 里写。

延迟带来的问题

由于存在延迟，许多在数学意义上没有问题的逻辑表达式在电路中就存在非常大的问题。

例如，从数学角度看，\(\mathrm{Y=\overline{A}A}\) 的值恒为 0，但是实际上由于延迟，其仿真波形中会出现这样一个 毛刺(glitch)，而这在工程意义上有很大的问题。

更复杂的例子

让我们分析下面这个二路选择器，其功能是通过 S 控制输出表达的是 A 还是 B，在传输延迟模型下，其波形如下：

可以发现，Y 中出现了意料之外的毛刺。

而这中毛刺可以用添加冗余项来解决：

由此可见，表达式最简并不一定是最好的

3.1.4 正逻辑和负逻辑

正逻辑(positive logic) 就是 1 是有效信号，负逻辑(negative logic) 就是 0 是有效信号。而在正逻辑中 AND 门的作用就等效于负逻辑中 OR 门的作用，这也正是前几章的笔记中提到的对称。

而正逻辑的电路的符号一般就是正常的逻辑门符号，而负逻辑的逻辑门符号则可能有小三角标，即 极性指示器(polarity indicator)：

如图，左侧是正逻辑电路的符号，右侧是负逻辑电路的符号。

3.1.5 工艺映射

工艺映射(technology mapping) 是指将逻辑图或网表转化为可以用工艺实现的心的图或网表的过程。

有时我们会使用与非门和非门替换与门和或门(电路层面，与门实际上就是通过与非门实现的)，然后会发现有一些连续对非门可以相互抵消，例如下面的情况：

蓝绿色块中即为被替换后的内容，然后我们发现出现了若干可以抵消的非门。

当然，也可以通过或非门来实现，比如下面的情况：

3.1.6 验证正确性

画真值表验证（即实验时的仿真）或者布尔代数式

功能分析 - 定义对任⼀信号的作⽤以及整个电路的作⽤ - 画时序图

3.2 函数模块

3.2.1 基本逻辑函数

定值函数：\(F=0\) or \(F=1\)

传输函数：\(F=X\)

逆变函数：\(F=\overline X\)

使能函数：信号源有一个使能信号，一个是传输信号

  • 一种是与使能：\(F=X\cdot EN\)

  • 另一种是或使能：\(F =X+\overline{EN}\)

就是让EN为1使输出信号与输入信号相同，为0时，让输出恒为0（与）或1（或）

与三态门作区别：三态门的使能引脚是放在中间的，是控制的而不是信号源。同时三态门还有一个高阻状态（切断），而使能函数则是恒输出0/1

3.2.2 译码器

Decoding - the conversion of an n-bit input code to an m-bit output code with \(n\leq m \leq 2^n\) such that each valid code word produces a unique output code 输入n个，输出m个（\(n\leq m \leq 2^n\))

Types of decoder

  • Variable Decoder (minterm detector)

  • Display Decoder

  • Code Translation Decoder

1-to-2-Line Decoder

2-to-4-Line Decoder：由两个1-2译码器与4个与门构成的（分解的思想）

Warning

当译码器变得更大时，只是使用 n 个1-2译码器与 \(2^n\) 个与门，会造成扇入与GN暴增。

解决方法：层次性设计，比如说8-256分解成两个4-16和一个与门。

Top-Down Design

自顶向下设计是一种从最终输出开始，逐步向输入端进行的设计方法。这种方法适用于复杂电路的设计，特别是多级解码器。

The procedure can be modified to apply to decoders with the number of outputs ≠ \(2^n\)

这样的一个6-64译码器, 先变成两个 3-8 译码器，然后每个3-8 译码器变为 两个2-4 译码器，GN=182，而原先的方案需要390个。

同时译码器还可以加一个使能端EN，EN为1使与原先一样，为0时全为0.

如果将使能端与信号源互换位置，就可以做一个信号分离器（本质就是译码器）

自底向上设计3-8译码器

Using two 2-to-4-Line Decoders for implementing one 3-to-8-Line Decoder

译码器应用：加法器、显示器……

利用译码器也可以实现最小项的表达, 以一个加法器为例

3.2.3 编码器

Encoding: the opposite of decoding - the conversion of an m-bit input code to a n-bit output code with \(n\leq m \leq 2^n\) such that each valid code word produces a unique output code

编码器：译码器的反过程，输入m个，输出n个（\(n\leq m \leq 2^n\))

Types of encoder:

  • Decimal-to-BCD Encoder

  • Instruction Encoder

  • Priority Encoder (widely used in computer priority interrupt system and keyboard coding system)

  • Cypher Encoder

一些常用的编码器：

  1. One-Hot to binary code （优势：快速读取次优结果，读特征位 In the case of one-hot encoding, we can obtain optimized design results directly without K-map.

  1. Decimal-to-BCD encoder（1的特例）

  2. Priority encoder(只反应最高优先级的那个1)

怎么读次优解？读确定量，如Y1就读 \(D3+\overline {D3}D2\)，V读 \(D3+D2+D1+D0\)

3.2.4 多路选择器（MUX）

两种构成方法：译码器+AND-OR gates 和 三态缓冲器

基本构成：\(2^n\)个输入，n个选择，1个输出

第一种：译码器提供有效信号，然后提供给与门的使能端，然后再通过或门

​ 输入源规模扩展：注意最后 or 门会超出 fan-in 的限额

​ 输入源本身的扩展，输入的不仅仅只是一个信号，而是一个向量：对每一位分别作与或电路，译码信号共享

第二种：与或电路用三态门替代，使能端链接译码信号，并且可以直接连到一个路上，不需要或门（少了门输入代价）

​ GN=18

将选择做分级，Distributing the decoding across the three-state drivers

​ GN=16

作用：更灵活译码器的构造

  1. 列出真值表

  2. 将真值表作为信号源，将输入作为使能端，即可。

改变真值表就可以改变函数，所以更加灵活

格雷码到二进制码的转换

优化：（带参数的K-Maps)

降维的方法：将三维K-Maps化为二维，以C为参数，填入最终二维表格的值为四种情况\(C\)、\(\overline C\)、1、0。仅需考虑合并后的AB项后的状态即可。

Multiplexer and Demultiplexer

四种常用器件总结

3.3 可编程函数

可编程逻辑器件

ROM(Read Only Memory)

PAL(Programmable Array Logic)

PLA(Programmable Logic Array)

FGPAs(Field Programmable Gate Array)

3.3.1 ROM/PROM

基本构成：固定的译码器+可选择的或门

ROM大小的计算：address width * word width，上图就是32

构建ROM基本流程：首先列出真值表，然后选择ROM大小，接着根据真值表选择结点接入

3.3.2 PAL

基本构成：输入AND项可编程，固定OR门

缺点：只能选择一定数量的最小项

可用的解决方法：代入已得结果

优点：一定的内部复杂度，增加了输入与输出的规模

例子：

3.3.3 PLA

基本构成：可编程的AND与OR项，以及最后的异或项（本质是增加最小项）

3.3.4 LUPs（可多次重编程）

基本构成：多路选择器接静态内存

要实现输入的动态变化，将MUX拆分成多层

例子：用3个2-1MUX拼成1个4-1MUX（2输入LUT）

3.3.5 FPGAs

CLB 是一个MUX，其中输入端接到PROM做固定。

FGPAs 被位流文件所编程，输入位流文件后遍历所有模块并进行分配

3.4 算数函数

3.4.1 加法器

新的层次设计：迭代设计

半加器、全加器、行波进位加法器、提前进位加法器（CLA）

3.4.1.1半加器

两输入加法函数（\(X+Y=C:S\)），不进行互连，无低位的进位

本质上是一个2-2的译码器

3.4.1.2 全加器

三输入加法函数（\(X+Y+Z=C:S\)），带有低位的进位

本质上是一个3-2的译码器

从K-Maps中读取得到

\(S=X\overline {YZ}+\overline X Y\overline Z+\overline X \overline YZ+X YZ\)

\(C=XY+X\overline YZ+\overline XYZ\)

可转换为

\(S=X\bigoplus Y\bigoplus Z\)

\(C=XY+(X\bigoplus Y)Z\)

可以读出进位的原因，分别是XY均为1，XY为0/1同时有进位

仔细观察，可得全加器是由两个半加器和或门组成。

理解方式：先X和Y进行一次半加，然后与Z进行一次半加，两次半加进位通过或门得到最后的进位结果，第二次半加得到的sum即为最后的sum

进而，我们就可以制造出行波进位加法器（缺点：速度慢）。

最长的时间是\(S_3\)，时间复杂度O(n)

优化方法：将\(C_n\)递归的用\(C_0\)表示出来，这样就可以让每一项在O（1）时间算出（理论上，会造成OR门fan-in过大）。实际上，我们可以将两个方法结合起来（Group Carry Lookahead Logic）。比如说16位加法器就每四位提前进位，每组之间行波进位。

3.4.2 减法器

3.4.2.1 无符号减法

  • 出现最高位借位，先硬减然后修正（求补码）。

  • 补码(\(r^n-N\))与反码(\(r^n-1-N\))

    计算机求补码：找到最低有效位，将最低有效位前面的数据求反码，后面保持不变。

    exp: \(01101100 \rightarrow \underline{10010}100\)

  • 利用加法器构建减法器，先将减数作补码与被减数相加，若被减数大于减数，得到差。若减数大于被减数，将得到的差取补码。

3.4.2.2 有符号减法

有符号数的表示法：

  • 首位表示符号，剩余位是数值 正号为0，负号为1，加号为0，减号为1。

    有符号数的加减法： 对三个符号做奇函数，如果是0，则对值进行相加，并检查是否溢出，然后符号即为加数的符号；如果是1，先按无符号数硬减，然后检查是否够减，若够减，则取被减数符号即可；若不够减，只需取补码后，符号取被减数符号的相反即可。

  • 符号补码表示法（分为1‘s Comp.(取的是反码)，2's Comp.(取的是补码)，这里介绍第二种

    首位表示符号，剩余位在正数的情况下用原码，负数为补码，同时记\(-2^n\)为10……0，0仅仅表示为0……0

求补码对应的真实值：

法一：取后面数字的补码，加上符号位即可

法二：负权重法，第一位取权重为\(-2^{n-1}\)剩余依次取正的。

exp: \(10011 \rightarrow -2^4+2^1+2^0=-13\)

符号位的扩展：正数前面扩0，负数前面扩1（这样的扩展数值大小仍不变）。

如何判断溢出？不能通过进位来判断，判断加数与和的符号位的变化

在这种表示法中，\(A+B\)与\(A-B\)可统一为一个电路，之后还要加一个溢出检测

3.4.3 ALU(Arithmetic Logic Unit)

组成部分：输入，模式（逻辑or运算）选择，运算符选择，进位

核心：加法器。通过对输入的改变来进行不同的运算

其他

  1. 递增器/递减器：将加法器中的B改为1即可，同时可以大量简化电路
  2. 乘以除以\(2^n\)
  3. Zero Fill

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！