Skip to content

東京大学 情報理工学系研究科 コンピュータ科学専攻 2021年2月実施 問題2

Author

zephyr

Description

Answer the following questions on digital circuits.

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

(2) Design and depict a 1-bit full-adder by using only two 2-input XOR gates and three 2-input NAND gates.

(3) Design and depict a 4-bit adder circuit by using four 1-bit full-adders. You may use 2-input NAND gates, 2-input NOR gates, and NOT gates, if necessary. Indicate also the critical path of the 4-bit adder circuit.

(4) Consider a 4-bit clock-synchronous up-down binary counter circuit. The circuit has a 1-bit input CLK for the clocking. The circuit also has a 1-bit input X and a 4-bit output Y. The circuit counts a number from 0 to 15, and outputs the counter value to the output Y. When the input X is '1', the counter value is incremented by one for each positive clock edge. Otherwise, the counter value is decremented by one for each positive clock edge. The circuit allows overflows, i.e. the next counter value is 0 when the current counter value is 15 and the input X is '1', and the next counter value is 15 when the current counter value is 0 and the input X is '0'. Assume that the circuit satisfies the setup-time and hold-time constraints. Design and depict the 4-bit clock-synchronous up-down binary counter circuit. You may use 1-bit full-adders, D-flip-flops, 2-input NAND gates, 2-input NOR gates, and NOT gates, if necessary.

回答以下关于数字电路的问题。

(1) 设计并描绘一个等效于 XOR（异或）门的电路，最多使用五个 2 输入 NAND 门。

(2) 设计并描绘一个 1 位全加器，仅使用两个 2 输入 XOR 门和三个 2 输入 NAND 门。

(3) 设计并描绘一个 4 位加法器电路，使用四个 1 位全加器。可以使用 2 输入 NAND 门、2 输入 NOR 门和 NOT 门（如有必要）。同时标明 4 位加法器电路的关键路径。

(4) 考虑一个 4 位时钟同步上下计数二进制计数器电路。电路有一个用于时钟的 1 位输入 CLK。电路还有一个 1 位输入 X 和一个 4 位输出 Y。电路计数从 0 到 15，并将计数值输出到输出 Y。当输入 X 为 '1' 时，计数值在每个正时钟边沿递增 1。否则，计数值在每个正时钟边沿递减 1。电路允许溢出，即当当前计数值为 15 且输入 X 为 '1' 时，下一个计数值为 0，当当前计数值为 0 且输入 X 为 '0' 时，下一个计数值为 15。假设电路满足设置时间和保持时间约束。设计并描绘这个 4 位时钟同步上下计数二进制计数器电路。可以使用 1 位全加器、D 触发器、2 输入 NAND 门、2 输入 NOR 门和 NOT 门（如有必要）。

Kai

(1)

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

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

Steps:

  • \(N1 = \mathrm{NAND}(A, A)\) which is \(\overline{A}\)
  • \(N2 = \mathrm{NAND}(B, B)\) which is \(\overline{B}\)
  • \(N3 = \mathrm{NAND}(A, B)\) which is \(\overline{A \cdot B}\)
  • \(N4 = \mathrm{NAND}(N1, N2)\) which is \(\overline{\overline{A} \cdot \overline{B}} = A + B\)
  • \(XOR = N5 = \mathrm{NAND}(N3, N4)\) which is \(\overline{\overline{A \cdot B} \cdot (A + B)} = A \oplus B\)

The circuit can be depicted as:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
A -----|N1|----\
                \
                |N4|--\
                /      \
B -----|N2|----/        \
                        |N5|-------XOR
A -------------\        /
                \      /
                |N3|--/
                /
B -------------/

(2)

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

  1. \(S = (A \oplus B) \oplus C_{in}\)
  2. \(C_{out} = (A \cdot B) + (C_{in} \cdot (A \oplus B))\)

Using XOR and NAND gates:

  • \(X1 = \mathrm{XOR}(A, B)\) which is \(A \oplus B\)
  • \(X2 = \mathrm{XOR}(X1, C_{in})\) which is \(S\)
  • \(N1 = \mathrm{NAND}(A, B)\) which is \(\overline{A \cdot B}\)
  • \(N2 = \mathrm{NAND}(X1, C_{in})\) which is \(\overline{(A \oplus B) \cdot C_{in}}\)
  • \(N3 = \mathrm{NAND}(N1, N2)\) which is \(C_{out}\)

(3)

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_{out,i}\)

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

(4)

让我们定义以下符号：

  • \(D_n\): 第 n 个 D 触发器存储的值（对应于 \(Y_n\)）
  • \(X\): 控制输入（1 表示加法，0 表示减法）
  • \(A_i\), \(B_i\): 第 i 个全加器的两个输入
  • \(S_i\): 第 i 个全加器的和输出
  • \(C_{in_i}\): 第 i 个全加器的进位输入
  • \(C_{out_i}\): 第 i 个全加器的进位输出

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

  1. D 触发器:
\[ D_n(t+1) = S_n(t) \]

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

  1. 全加器输入:
\[ A_i = D_i \]
\[ B_i = X \]

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

  1. 全加器输出:
\[ S_i = A_i \oplus B_i \oplus C_{in_i} \]
\[ C_{out_i} = (A_i \cdot B_i) + (B_i \cdot C_{in_i}) + (A_i \cdot C_{in_i}) \]

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

  1. 进位连接:
\[ C_{in_0} = C_{out_3} \]
\[ C_{in_i} = C_{out_{i-1}} \quad \text{for} \quad i = 1,2,3 \]

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

  1. 减法操作: 当 \(X = 0\) 时，我们需要执行减法。这可以通过将 \(B_i\) 取反并设置 \(C_{in_0} = 1\) 来实现：
\[ B_i = \overline{X} \]
\[ C_{in_0} = \overline{X} + C_{out_3} \]
  1. 输出:
\[ Y_n = D_n \]

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

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

\[ D_n(t+1) = D_n(t) \oplus X \oplus C_{in_n} \]
\[ C_{out_n} = (D_n(t) \cdot X) + (X \cdot C_{in_n}) + (D_n(t) \cdot C_{in_n}) \]

其中，\(C_{in_n}\) 由前一级的 \(C_{out_{n-1}}\) 决定，除了最低位：

\[ C_{in_0} = \overline{X} + C_{out_3} \]

Knowledge

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

解题技巧和信息

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

重点词汇

  • exclusive OR 异或
  • full-adder 全加器
  • counter 计数器
  • clock-synchronous 时钟同步
  • up-down binary counter 二进制上下计数器

参考资料

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