Combinational Logic Design¶

Abstract

组合电路定义（逻辑电路的两大类型：组合逻辑电路、时序逻辑电路）
Definition of Combinational Circuits
模块与层次设计
Hierarchical Design
逻辑事件的描述方法*
Description of logic events
逻辑门的主要参数
Technology Parameters
扇入（Fan-in）、扇出（Fan-out）、噪音容限（Noise Margin）、门的成本（Cost for a gate）、传输延迟（Propagation Delay）
器件状态值或状态表与正逻辑，负逻辑的概念
Positive and Negative Logic
三态门使用原则与总线（BUS）
BUS
信号系统延时、延时模型、上升和下降时间、时钟上升和下降沿概念。
Delay Models, Positive and Negative Edge
组合逻辑电路分析方法
Analysis of Combinational Circuits
组合逻辑电路的设计方法
Design of Combinational Circuits
函数与函数模块，基本逻辑功能
Functions and functional blocks
计算机中的常用组合逻辑电路（功能芯片）
Frequently used Combinational Circuit in Computer Design
译码器、编码器、数据选择器（多路复用选择器）、数据分配器。
组合函数的实现技术
Implementing Combinational Functions Using:
译码器和或门
Decoders and OR gates
多路复用器（加反相器）
Multiplexers (and inverter)
使能信号（EN，OE）的作用
Function of Enable Signal
组合电路的迭代结构
Iterative combinational circuits
算术函数：了解加、减、乘、除、增量函数及运算
Arithmetic function: Add, subtraction, multiplication, division, increment
补码运算
2’s complement
半加器及全加器函数及电路设计
Equations and Circuit implementation of 1 bit Half Adder and Full Adder
多位全加器、全减器及设计
Design of multiple-bit Full Adder/ Subtracter
超前进位：进位传递与延迟，进位函数：generate, Gi、propagate, Pi
Carry Lookahead: carry propagation and delay

Design Procedure¶

A combinational logic circuit has:

A set of m Boolean inputs,
A set of n Boolean outputs, and
n switching functions, each mapping the \(2^m\) input combinations to an output such that the current output depends only on the current input values

no state

Hierarchical Design¶

Decompose the function into smaller pieces called blocks
Decompose each block’s function into smaller blocks, repeating as necessary until all blocks are small enough
Any block not decomposed is called a primitive block
The collection of all blocks including the decomposed ones is a hierarchy

e.g.

实例化模块和函数调用的区别

电路上实例化模块：复制一块并嵌入到电路中。且同时实例的模块是同时在运行，如上图中四个实例化的奇函数模块。（实际上硬件里做串行是非常麻烦的，需要状态机来约束行为逻辑）
但 C 语言函数体只有一份代码，只是 PC 跳到函数部分。

Reusable Functions:
把常用的操作抽象成模块，并提前定义好延迟等等特性。当需要使用时，我们把电路引脚接入即可。

Top-Down versus Bottom-Up

A top-down design proceeds from an abstract, high-level specification to a more and more detailed design by decomposition and successive refinement
A bottom-up design starts with detailed primitive blocks and combines them into larger and more complex functional blocks

Design Procedure¶

Specification
Write a specification for the circuit if one is not already available
Formulation
- Derive a truth table or initial Boolean equations that define the required relationships between the inputs and outputs, if not in the specification
- Apply hierarchical design if appropriate 3. Optimization
- Apply 2-level and multiple-level optimization
- Draw a logic diagram or provide a netlist for the resulting circuit using ANDs, ORs, and inverters
Technology Mapping
Map the logic diagram or netlist to the implementation 为什么需要这步？
很多时候需要用预先定义好的与非门，或者其他基本模块（如 XOR）直接套入电路中去，可以降低电路的成本和延迟。 technology selected
Verification Verify the correctness of the final design manually or using simulation.(仿真)

BCD to Excess-3 code converter

Specification
- Transforms BCD code for the decimal digits to Excess-3 code for the decimal digits
- BCD code words for digits 0 through 9: 4-bit patterns 0000 to 1001, respectively
  其他输入认为是无关项。
- Excess-3 code words for digits 0 through 9: 4-bit patterns consisting of 3 (binary 0011) added to each BCD code word
- Implementation:
  - multiple-level circuit.
  - NAND gates(including inverters)
Formulation
Optimization
- two-level
  W X Y Z 输出也需要四个逻辑函数。
  单独 ABCD 四输入对应一个输出 W, 用卡诺图化简。
得到 \(W=A+BC+BD, X=\overline B C+\overline B D+B \overline C\overline D, Y=CD+\overline C\overline D, Z=\overline D\)
- multiple-level
  \(G=7+10+6+0=23\).
  优化后: \(T_1=C+D, W=A+BT_1, X=\overline B T_1B \overline C\overline D, Y=CD+\overline C\overline D, Z=\overline D\)
  \(G=2+4+7+6+0=19\), 最多是三级电路。 \(\overline C\overline D=\overline{C+D}=\overline{T_1},T_1=C+D, W=A+BT_1, X=\overline B T_1B \overline C\overline D, Y=CD+\overline C\overline D, Z=\overline D\)
  \(G = 2 +1 + 4 + 6 + 4 + 0 = 17\)，最多是四级电路。为什么要算 T1 非：ABCD 是外部输入的引脚，一般同时有原变量和反变量。但 T1 是内部产生的信号，对这个信号的非要自己计算得到。
Technology Mapping
Mapping with a library containing inverters and 2-input NAND, 2-input NOR, and 2-2 AOI(与或非) gates
Verification

(为什么有的时候算 G, 有的时候算 GN. 因为触发器同时有原变量和反变量，所以很多时候不需要单独算 GN.）

Chip Design Styles¶

Full custom: 全部自己定制化，不用先定义好的模型。（因为库会考虑通用性，完整，带来成本开销比较高，延迟也相对大）
这种实现方式，研发成本高，但生产成本最低。用于高性能，或者生产量非常大的时候。 Justifiable only for dense, fast chips with high sales volume.
Standard cell: 使用预先规定好的标准库(如几输入的与门)
Gate array: 研发成本低。买现成的芯片，写进代码即可执行。成本最低（不用流片）

Cell Libraries

Cell - a pre-designed primitive block
Cell library - a collection of cells available for design using a particular implementation technology
Cell characterization - a detailed specification of a cell for use by a designer - often based on actual cell design and fabrication and measured values
包括原理图，芯片面积，输入负载，延迟，工艺映射的模板库，硬件描述语言如何实现。

e.g.

Mapping to NAND gates¶

如何只用 NAND/NOR 做工艺映射
假设：不考虑 gate loading 和 delay. 可以有任意输入的与非/或非门。 The mapping is accomplished by:

Replacing AND and OR symbols

Pushing inverters through circuit fan-out points

Canceling inverter pairs

Example

b -> c 就是把 5 推出散出点，随后和其他非门相消。

NONR 与 NAND 基本相同，除了 replace 这步。

Verification¶

验证方法：真值表/仿真/逻辑函数

小细节：仿真输出中有小脉冲，因为延迟产生。如果没有惯性延迟，我们要考虑把它吸收掉。
Behaviour Simulation 看不到，因为他不考虑传输延迟。多考虑使用有延迟的仿真

Combinational Logic¶

functional block: 偏高层逻辑应用，如译码器，选择器。

Rudimentary Logic Functions¶

b 中表示接地和接电源。

Multiple-bit Rudimentary Functions¶

A wide line is used to represent a bus which is a vector signal.

b 中 4 表示位宽，4 位信号。

Sets of bits can be split from the bus as shown in © for bits 2 and 1 of F.
The sets of bits need not be continuous as shown in (d) for bits 3, 1, and 0 of F.

Enabling Function¶

Enabling permits an input signal to pass through to an output
Disabling blocks an input signal from passing through to an output, replacing it with a fixed value

The value on the output when it is disable can be Hi-Z (as for three-state buffers and transmission gates), 0 , or 1

Example

(a) when disabled, 0 output
(b) when disabled, 1 output. 其中也可以写 \(\overline {EN}\) 然后直接接或门，不用标 inverter.

Decoding¶

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.
Circuits that perform decoding are called decoders.

3-8 译码器

其真值表：

Example

朴素实现 n-to-m 的译码器有 \(n\times m\) 门输入成本.(\(2\times 2^n\))

译码器常用于内存，接在地址总线。 \(32-2^{32}\) 译码. 成本 \(32\times 2^{32}\)
如何减少实现成本？

Decode Expansion¶

3-8 译码器，输入分成两部分，A 用 1-2 译码器, B C 用 2-4 译码器

抽象为行列译码：一组是行译码，一组是列译码。对于 \(n - 2^n\) 设计两个译码器，一个 \(\dfrac{n}{2}\) 输入 \(2^{\frac{n}{2}}\) 的行译码器，一个 \(\dfrac{n}{2}\) 输入 \(2^{\frac{n}{2}}\) 输出的列译码器。

这样再把行列的输出用 2-AND 连接，我们只需要 \(2^{\frac{n}{2}}\times 2^{\frac{n}{2}}=2^n\) 个 AND 门, 中间与门阵列的成本是 \(2^n\times 2 =2^{n+1}\).

译码延迟加大，但降低成本。

Decoder with Enable¶

Note

Alternatively, (b) can be viewed as distributing value of signal EN to 1 of 4 outputs In this case, called demultiplexer(分配器).
把 D1 看作 D1=EN. 即 \(A_1, A_0\) 决定把 EN 的信号分配到哪个引脚。

Combinational Logic Implementation - Decoder and OR Gates¶

Implement m functions of n variables with:

Sum-of-minterms expressions
One n-to-2n-line decoder
m OR gates, one for each output

把最小项或起来，得到任意的逻辑函数

Binary Adder

BCD-to-Segment Decoder

七段数码管里，亮不同的段即可表示不同的数字

上为共阳极（输出 0 才能亮，阴极相反）下为共阴极
输入不同的数字，亮对应的数码管，使其可以显示在数码管上

Encoding¶

Encoding - the opposite of decoding - the conversion of an m-bit input code to a n-bit output code with \(n <=m <= 2^n\) such that each valid code word produces a unique output code
一个译码器 \(2^n\) 输入，n 个输出。常用于中断信号，计算机响应，告诉 CPU 哪一号的中断发生了（这里就要进行编码）

decimal-BCD encoder

Inputs: 10 bits corresponding to decimal digits 0 through 9, (D0, …, D9)
Outputs: 4 bits with BCD codes
Function: If input bit Di is a 1, then the output (A3, A2, A1, A0) is the BCD code for i.
A3 = D8 + D9;
A2 = D4 + D5 + D6 + D7;
A1 = D2 + D3 + D6 + D7;
A0 = D1 + D3 + D5 + D7 + D9

如果输入的 10 根线里，有两个输入都为 1, 可能会得到没有意义的输出，需要优先级。

Priority Encoder¶

如果这里有多个输入为 1, encoder 会将优先级最高的值编码。

Example

V 表示是是否有有效信号进入 \(A2 = D4\)
\(A1 = \overline{D4} D3 + \overline{D4} D2 = \overline{D4}F1, F1 = (D3 + D2)\)
\(A0 = \overline{D4} D3 + \overline{D4}\overline{D3}\overline{D2} D1 = \overline{D4} (D3 + \overline{D2} D1)\)
\(V = D4 + F1 + D1 + D0\)

Multiplexers¶

Circuits that perform selecting have:

A set of information inputs from which the selection is made
A single output
A set of control lines for making the selection

Logic circuits that perform selecting are called multiplexers.

A typical multiplexer has n control inputs \((S{n - 1},... S_0)\) called selection inputs, \(2^n\) information inputs \((I_{2^n - 1}, … I_0)\), and one output Y.
如果输入 \(m<2^n\) 也可以设计为 n select lines 的 multiplexers.

2-to-1-Line Multiplexer

S = 0 时选择 \(I_0\); S = 1 时选择 \(I_1\).
Equation: \(Y=\overline S I_0+SI_1\) 画电路图时，要分成两块：第一部分 1-2 译码器，后一部分是 2-2 与或结构。（结构复杂后，其实就是将这两部分扩展）

In general, \(2^n\)-to-1-line multiplexers:

n-to-\(2^n\)-line decoder
\(2^n \times 2\) AND-OR

Example

任何时刻译码器只有一个输出是 1, 相当于只有一个与门被 enable, 其余都 disable. 这样就能选择出 enable 的信号。

多位的数据选择。这里有四组信号，每组信号都是四个输入的一位，但选择逻辑对于四组信号是一样的，因此最后选出来的都是同一组信号。即最后输出的四位信号都来自同一根总线，

我们也可以不用与或结构，使用三态门实现 mux.

三态门改进 Mux

(利用三态门可以将输出并在一起，同时最多只有一个三态门有有效输出。我们这里译码器只会有一个输出为 1, 保证了电路安全；这样还可以降低成本)
我们还可以将译码器也使用三态门：

这里我们是两层选择的逻辑，S0 = 0 时先选出 I0(00) 和 I2(10), S1 再进行第二层的选择。

Combinational Logic Implementation- Multiplexer Approach¶

对于一个 n 变量的逻辑函数，我们可以把它抽象为 n 个输入对应一个输出。我们可以用 Mux 对应真值表中的 \(2^n\) 行的结果，用 n 输入作为选择线来查表。

Gray to Binary Code

相当于利用 ABC 查表，如果 mux 选择出一位（根据真值表得到）
注意引脚顺序！

我们可以做进一步改进，\(n+1\) 变量用 \(2^n-1\) mux

对于 \(F(A,B,C)\) 当 A B 确定时，最后可能输出只可能为 \(1,0,C,\overline C\)
利用这点我们可以改造真值表，

理论上还可以放更多变量到另一边

Arithmetic Functions¶

Cell - subfunction block 单元模块，处理每位

Functional Blocks: Addition¶

Addition Development:

Half-Adder (HA), a 2-input bit-wise addition functional block.(no carry input)
Full-Adder (FA), a 3-input bit-wise addition functional block.
Ripple Carry Adder, an iterative array to perform binary addition.
Carry-Look-Ahead Adder (CLA), a hierarchical structure to improve performance.

Half-Adder¶

\(S=X\oplus Y, C=XY\).

Full Adder¶

S 无法化简，但可以表示为奇函数（异或）

\(S=X\overline Y\overline Z+\overline X Y \overline Z + \overline X\overline YZ+XYZ=X\oplus Y\oplus Z\) \(C=XY+XZ+YZ=XY+(X\oplus Y)Z\).
The term \(XY\) is carry generate.(\(XY=1\) 时一定会有进位)
The term \(X\oplus Y\) is carry propagate.(\(X\oplus Y=1\) 时 X,Y有一个是 0, 一定会把进位传下去，即 \(C=Z\))

Note

注意 C 的改写，这里改为异或不改变结果，同时因为已经有 xor 了，可以节约一个门。

Implementation:

Binary Adders¶

实现二进制多位加法

4-bit Ripple-Carry Binary Adder¶

存在一个问题：随着加法器位数的增加，延迟会越来越大。
如下图中，最长的路径是从 A0 或 B0 到 S3.

Carry Lookahead¶

对于状态 i, 我们称 \(G_i\) 为 generate, \(P_i\) 为 propagate.

\(G_i\), \(P_i\), and \(S_i\) are local to each cell of the adder
\(C_i\) is also local each cell

全加器的更新可以定义为

\[ \begin{align*} P_i & =A_i\oplus B_i, \ G_i = A_iB_i\\ S_i & =P_i\oplus C_i,\ C_{i+1} = G_i+P_iC_i \end{align*} \]

这样 \(C_{i+1}\) 可以从 cells 中去掉，同时我们可以推导得到一组跨越多个单元的进位方程：

于是我们可以得到下面的 Carry Look-ahead Adder:

这样的超前进位全加器，避免了因为位过多而造成延迟过大。高位的结果直接由低位的结果得到。

This could be extended to more than four bits; in practice, due to limited gate fan-in, such extension is not feasible.

The concept is extended another level by considering group generate(\(G_{0-3}\)) and group propagate(\(P_{0-3}\)) functions:

这样我们就得到了 16-bits adder

Exactly the same structure. So CLA could be used to generate Group Carry.
类似思路可得到 64 位的加法器。

Example

Unsigned Subtraction¶

Subtract the subtrahend(减数) N from the minuend(被减数) M
If no end borrow occurs, then \(M\geq N\), and the result is a non-negative number and correct.
If an end borrow occurs, the \(N > M\) and the difference \(M - N + 2^n\) is subtracted from \(2^n\), and a minus sign is appended to the result.

To do both unsigned addition and unsigned subtraction requires:

复杂，成本高

Complements¶

Diminished Radix Complement of N 反码
defined as \(r^n-1-N\)(\(r^n-1\) 是 bits[n-1:0] 全为 1 的二进制数，用它减去 N 即可得到 N 按位取反的结果，即反码)
The 1's complement is obtained by complementing each individual bit (bitwise NOT).
2’s complement 补码 defined as \(r^n-N\)
- 反码按位取反再加一
- 也可以这样求补码：从右往左第一个 1 之前不变，此后其他位全部求反

Subtraction is done by adding the complement of the subtrahend.

Subtraction with 2’s Complement
- Add the 2's complement of the subtrahend N to the minuend M: \(M + (2^n -N) = M - N + 2^n\)
- if \(M\geq N\), the sum produces end carry \(r^n\) which is discarded; from above, \(M - N\) remains.
- If \(M < N\), the sum does not produce an end carry and, from above, is equal to \(2^n - ( N - M )\), the 2's complement of \(( N - M )\).
  To obtain the result \((N – M)\), take the 2's complement of the sum and place a \(-\) to its left.

Example

进位是 1 表明结果为正，不需对结果修正
进位是 0 表明结果为负，需对结果修正

Signed Integers¶

Signed Integer Representations: 第 n-1 位表示正负，后面 bits[n-2:0] 表示绝对值大小
Signed-Complement
- Signed 1's Complement
- Signed 2's Complement

详见 ICS notes

Signed-Magnitude Arithmetic¶

检查三个符号位的奇偶性（两个操作数的符号位和加减法的符号位，我们一般认为加法是 0, 减法是 1）用于判断溢出
可能溢出的情况：正加正(000), 正减负(011), 负减正(101), 负加负(110)
If the parity of the three signs is 0:(overflow may happen)
- Add the magnitudes.
- Check for overflow (a carry out of the MSB)
- The sign of the result is the same as the sign of the first operand.
If the parity of the three signs is 1:
- Subtract the second magnitude from the first.
- If a borrow occurs:
  take the two’s complement of result and make the result sign the complement of the sign of the first operand.
- Overflow will never occur.

Signed-Complement Arithmetic¶

Addition:
- Add the numbers including the sign bits, discarding a carry out of the sign bits (2's Complement), or using an end-around carry (1's Complement).
- If the sign bits were the same for both numbers and the sign of the result is different, an overflow has occurred.
- The sign of the result is computed in step 1.
Subtraction:
Form the complement of the number you are subtracting and follow the rules for addition.

Signed 2’s Complement Examples

1101 + 0011
Result is 0000. The carry out of the MSB is discarded.
1101 - 0011
Complement 0011 to 1101 and add. Result is 1010. The carry out of the MSB is discarded.

2’s Complement Adder/Subtractor

利用异或门，当 S=0 时异或门相当于保持另一个信号，当 S=1 时异或门相当于对另一个信号取反。

Overflow Detection
Overflow occurs if n + 1 bits are required to contain the result from an n-bit addition or subtraction

Example

Simplest way to implement overflow \(V = C_n \oplus C_{n - 1}\) \(C_n\) 是溢出去的位，\(C_{n-1}\) 是运算后的符号位。截断

Arithmetic Logic Unit (ALU)¶

Decompose the arithmetic circuit into:

An n-bit parallel adder
A block of logic that selects four choices for the B input to the adder

Example

其中 \(Y_i=B_iS_0+\overline B_iS_1\)
S0 S1 的变化可以给加法器提供不同的输入，包括 -1(二进制每一位都是 1) 0 \(B\) \(\overline B\)

Combinational Logic Design¶

Design Procedure¶

Hierarchical Design¶

Design Procedure¶

Chip Design Styles¶

Mapping to NAND gates¶

Verification¶

Combinational Logic¶

Rudimentary Logic Functions¶

Multiple-bit Rudimentary Functions¶

Enabling Function¶

Decoding¶

Decode Expansion¶

Decoder with Enable¶

Combinational Logic Implementation - Decoder and OR Gates¶

Encoding¶

Priority Encoder¶

Multiplexers¶

Combinational Logic Implementation- Multiplexer Approach¶

Arithmetic Functions¶

Functional Blocks: Addition¶

Half-Adder¶

Full Adder¶

Binary Adders¶

4-bit Ripple-Carry Binary Adder¶

Carry Lookahead¶

Unsigned Subtraction¶

Complements¶

Signed Integers¶

Signed-Magnitude Arithmetic¶

Signed-Complement Arithmetic¶

Arithmetic Logic Unit (ALU)¶

评论