跳到主要内容

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

标签：

Author​

zephyr, 祭音Myyura

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 门（如有必要）。

题目描述​

回答下列数字电路问题。

（1）仅用至多五个二输入 NAND 门，设计并画出等价于异或门的电路。

（2）仅用两个二输入 XOR 门和三个二输入 NAND 门，设计并画出一位全加器。

（3）用四个一位全加器设计并画出四位加法器；必要时可使用二输入 NAND 门、二输入 NOR 门和非门，并标明该四位加法器的关键路径。

（4）设计并画出四位时钟同步二进制加减计数器。电路有一位时钟输入 CLK、一位控制输入 X 和四位输出 Y，计数范围为 00 至 1515： 每个时钟上升沿，当 X=1 时加一，否则减一；允许模 1616 溢出，即 1515 加一变为 00，00 减一变为 1515。假定满足建立时间与保持时间约束。 必要时可使用一位全加器、D 触发器、二输入 NAND/NOR 门及非门。

Kai​

(1)​

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

Steps:

  • N1=NAND(A,B)N1 = \mathrm{NAND}(A,B)
  • N2=NAND(A,N1)N2 = \mathrm{NAND}(A,N1)
  • N3=NAND(B,N1)N3 = \mathrm{NAND}(B,N1)
  • XOR=N4=NAND(N2,N3)=A⊕BXOR = N4 = \mathrm{NAND}(N2,N3)=A\oplus B

The circuit can be depicted as:

A ----+--------[N2]----\
     |          ^       \
     +--[N1]----+        [N4]---- XOR
     |          v       /
B ----+--------[N3]----/

(2)​

A 1-bit full-adder has three inputs: AA, BB, and CinC_{in}, and two outputs: SS (sum) and CoutC_{out} (carry out).

  1. S=(A⊕B)⊕CinS = (A \oplus B) \oplus C_{in}
  2. Cout=(A⋅B)+(Cin⋅(A⊕B))C_{out} = (A \cdot B) + (C_{in} \cdot (A \oplus B))

Using XOR and NAND gates:

  • X1=XOR(A,B)X1 = \mathrm{XOR}(A, B) which is A⊕BA \oplus B
  • X2=XOR(X1,Cin)X2 = \mathrm{XOR}(X1, C_{in}) which is SS
  • N1=NAND(A,B)N1 = \mathrm{NAND}(A, B) which is A⋅B‾\overline{A \cdot B}
  • N2=NAND(X1,Cin)N2 = \mathrm{NAND}(X1, C_{in}) which is (A⊕B)⋅Cin‾\overline{(A \oplus B) \cdot C_{in}}
  • N3=NAND(N1,N2)N3 = \mathrm{NAND}(N1, N2) which is CoutC_{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: AiA_i, BiB_i, Cin,iC_{in,i}
  • Outputs: SiS_i, Cout,iC_{out,i}

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

(A0,B0,Cin) -> FA0 -> S0,C1
(A1,B1,C1)  -> FA1 -> S1,C2
(A2,B2,C2)  -> FA2 -> S2,C3
(A3,B3,C3)  -> FA3 -> S3,Cout

The critical carry path is Cin→C1→C2→C3→CoutC_{in}\to C_1\to C_2\to C_3\to C_{out} through all four full-adders.

(4)​

令 QiQ_i 为第 ii 个 D 触发器当前保存的位，SiS_i 和 Cout,iC_{out,i} 分别为第 ii 个全加器的和与进位输出。四个 D 触发器共用 CLK，且

Y=(Q3Q2Q1Q0)2,qquadQi(t+1)=Si(t).Y=(Q_3Q_2Q_1Q_0)_2,qquad Q_i(t+1)=S_i(t).

四个全加器组成行波加法器，计算

D=Y+K(mod16),K={0001,X=1,1111,X=0.D=Y+K\pmod {16},\qquad K=\begin{cases}0001,&X=1,\\1111,&X=0.\end{cases}

令最低位加法器的进位输入 Cin,0=0C_{in,0}=0，第 ii 位的输入为

Ai=Qi,Bi=Ki,K0=1,K1=K2=K3=X‾.A_i=Q_i,\qquad B_i=K_i,\qquad K_0=1,\quad K_1=K_2=K_3=\overline X.

每个全加器满足

Si=Ai⊕Bi⊕Cin,i,S_i=A_i\oplus B_i\oplus C_{in,i},
Cout,i=AiBi+BiCin,i+AiCin,i.C_{out,i}=A_iB_i+B_iC_{in,i}+A_iC_{in,i}.

连接 Cin,i=Cout,i−1C_{in,i}=C_{out,i-1}（i=1,2,3i=1,2,3）。各 SiS_i 接相应 D 触发器的 D 输入，Q 输出既构成 YY，也反馈到加法器；最高位进位丢弃。

Q[3:0] ----\
             4-bit ripple adder ---- S[3:0] ---- DFF[3:0] ---- Y=Q[3:0]
K[3:0] ----/          (C0=0)                         ^
                                                    CLK

11111111 是模 1616 下的 −1-1，故上升沿时 X=1X=1 得到 Y+1Y+1，X=0X=0 得到 Y−1Y-1，溢出也自动满足题意。

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
本页目录