IS CS-2021W-02

题目来源：Problem 2 日期：2024-07-24 题目主题：CS-数字电路-逻辑门设计与加法器

解题思路

这些题目涉及数字电路设计，使用基本的逻辑门（NAND、NOR、NOT）和组合逻辑模块（如全加器和触发器）来构建复杂的电路。

Solution

Question 1: Design and depict a circuit equivalent to XOR (exclusive OR) gate by using at most five 2-input NAND gates

The XOR gate can be constructed using NAND gates as follows:

Let $A$ and $B$ be the two inputs.
Create the expressions for $\overline{A \cdot B}$ and $\overline{A + B}$ using NAND gates.
Combine these intermediate results to achieve the XOR function.

Steps:

$N 1 = NAND (A, A)$ which is $\overline{A}$
$N 2 = NAND (B, B)$ which is $\overline{B}$
$N 3 = NAND (A, B)$ which is $\overline{A \cdot B}$
$N 4 = NAND (N 1, N 2)$ which is $\overline{\overline{A} \cdot \overline{B}} = A + B$
$XOR = N 5 = NAND (N 3, N 4)$ which is $\overline{\overline{A \cdot B} \cdot (A + B)} = A \oplus B$

The circuit can be depicted as:

A -----|N1|----\
                \
                |N4|--\
                /      \
B -----|N2|----/        \
                        |N5|-------XOR
A -------------\        /
				\      /
			    |N3|--/
	            /
B -------------/

Question 2: Design and depict a 1-bit full-adder by using only two 2-input XOR gates and three 2-input NAND gates

A 1-bit full-adder has three inputs: $A$ , $B$ , and $C_{in}$ , and two outputs: $S$ (sum) and $C_{o u t}$ (carry out).

$S = (A \oplus B) \oplus C_{in}$
$C_{o u t} = (A \cdot B) + (C_{in} \cdot (A \oplus B))$

Using XOR and NAND gates:

$X 1 = XOR (A, B)$ which is $A \oplus B$
$X 2 = XOR (X 1, C_{in})$ which is $S$
$N 1 = NAND (A, B)$ which is $\overline{A \cdot B}$
$N 2 = NAND (X 1, C_{in})$ which is $\overline{(A \oplus B) \cdot C_{in}}$
$N 3 = NAND (N 1, N 2)$ which is $C_{o u t}$

Question 3: Design and depict a 4-bit adder circuit by using four 1-bit full-adders

A 4-bit adder can be created by chaining four 1-bit full-adders. The carry-out from each adder becomes the carry-in for the next adder.

For each 1-bit full-adder:

Inputs: $A_{i}$ , $B_{i}$ , $C_{in, i}$
Outputs: $S_{i}$ , $C_{o u t, i}$

The critical path is the longest delay path through the adders, which goes through all carry-out to carry-in connections.

Question 4: Design and depict a 4-bit clock-synchronous up-down binary counter circuit

让我们定义以下符号：

$D_{n}$ : 第 n 个 D 触发器存储的值（对应于 $Y_{n}$ ）
$X$ : 控制输入（1 表示加法，0 表示减法）
$A_{i}$ , $B_{i}$ : 第 i 个全加器的两个输入
$S_{i}$ : 第 i 个全加器的和输出
$C_{i n_{i}}$ : 第 i 个全加器的进位输入
$C_{o u t_{i}}$ : 第 i 个全加器的进位输出

现在，我们可以用表达式来表示这些元件之间的关系：

D 触发器:

D_{n} (t + 1) = S_{n} (t)

这表示在下一个时钟周期，D 触发器将存储当前全加器的输出。

全加器输入:

A_{i} = D_{i}

B_{i} = X

第一个输入来自当前的 D 触发器值，第二个输入是控制信号 X。

全加器输出:

S_{i} = A_{i} \oplus B_{i} \oplus C_{i n_{i}}

C_{o u t_{i}} = (A_{i} \cdot B_{i}) + (B_{i} \cdot C_{i n_{i}}) + (A_{i} \cdot C_{i n_{i}})

这是标准的全加器逻辑表达式。

进位连接:

C_{i n_{0}} = C_{o u t_{3}}

C_{i n_{i}} = C_{o u t_{i - 1}} for i = 1, 2, 3

最低位的进位输入来自最高位的进位输出，其他位的进位输入来自前一位的进位输出。

减法操作: 当 $X = 0$ 时，我们需要执行减法。这可以通过将 $B_{i}$ 取反并设置 $C_{i n_{0}} = 1$ 来实现：

B_{i} = \overline{X}

C_{i n_{0}} = \overline{X} + C_{o u t_{3}}

输出:

Y_{n} = D_{n}

输出直接来自 D 触发器的存储值。

综合起来，我们可以得到每一位的完整表达式：

D_{n} (t + 1) = D_{n} (t) \oplus X \oplus C_{i n_{n}}

C_{o u t_{n}} = (D_{n} (t) \cdot X) + (X \cdot C_{i n_{n}}) + (D_{n} (t) \cdot C_{i n_{n}})

其中， $C_{i n_{n}}$ 由前一级的 $C_{o u t_{n - 1}}$ 决定，除了最低位：

C_{i n_{0}} = \overline{X} + C_{o u t_{3}}

知识点

逻辑电路布尔代数加法器 D触发器

解题技巧和信息

使用 NAND 门实现基本逻辑功能
将全加器串联实现多位加法器
设计同步计数器时注意正负边缘触发逻辑

重点词汇

exclusive OR 异或

full-adder 全加器

counter 计数器

clock-synchronous 时钟同步

up-down binary counter 二进制上下计数器

参考资料

Digital Design and Computer Architecture by David Harris and Sarah Harris - Chap. 3, 5
Fundamentals of Digital Logic with VHDL Design by Stephen Brown and Zvonko Vranesic - Chap. 4

Zephyr's Notes on ISCS & CBMS, UTokyo

Explorer