東京大学 情報理工学系研究科 コンピュータ科学専攻 2022年2月実施 問題4
Author
Description
Answer the following questions on digital circuits.
(1) Provide a Boolean expression of the output
Truth table
(2) Depict the internal structure of a D-flip-flop, and explain how the D-flip-flop holds a 1-bit value.
(3) Consider a clock-synchronous sequential circuit with a 1-bit input
回答以下有关数字电路的问题。
(1) 根据以下真值表提供输出
真值表
(2) 描述 D 触发器的内部结构,并解释 D 触发器如何保持 1 位值。
(3) 考虑一个时钟同步顺序电路,具有 1 位输入
Kai
(1)
Karnaugh Map
The truth table can be represented as a Karnaugh map:
C\AB | 00 | 01 | 11 | 10 |
---|---|---|---|---|
0 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 1 | 1 |
We can circle the 1s in the Karnaugh map to simplify the expression:
and and
Simplified Expression
The simplified Boolean expression for the output
Combinational Circuit using 2-input NAND Gates
NAND:
Especially,
First, we simplify the expression further:
The corresponding combinational circuit using at most six 2-input NAND gates is as follows:
graph TD
subgraph Inputs
A
B
C
end
subgraph Processing
A & B --> NAND1[NAND]
A & C --> NAND2[NAND]
B & C --> NAND3[NAND]
NAND1 & NAND2 --> NAND4[NAND]
NAND4 --> NAND5[NAND]
NAND4 --> NAND5[NAND]
NAND5 & NAND3 --> NAND6[NAND]
end
subgraph Outputs
NAND6 --> D
end
The circuit uses six 2-input NAND gates to implement the simplified expression for
(2)
Internal Structure
A D-flip-flop consists of the following components:
- D input: The input data bit to be input to the flip-flop.
- Clock input: The clock signal that controls the operation of the flip-flop.
- Q output: The output of the flip-flop that stores the value of the D input.
- Q' output: The complement of the Q output.
The output Q table for a D-flip-flop is as follows:
D | CLK | Q(t) | Q(t+1) |
---|---|---|---|
0 | 0 | Q(t) | Q(t) |
1 | 0 | Q(t) | Q(t) |
0 | ↑ | Q(t) | 0 |
1 | ↑ | Q(t) | 1 |
0 | 1 | Q(t) | Q(t) |
1 | 1 | Q(t) | Q(t) |
0 | ↓ | Q(t) | Q(t) |
1 | ↓ | Q(t) | Q(t) |
To detect the rising edge of the clock signal, first, we need to build a circuit, using the delay of the signal to detect the rising edge. The circuit is called a "master-slave D flip-flop."
/-------------\
CLK----NOT---- NAND----P_1
\-----NOT-----/
graph TD
subgraph Inputs
CLK
end
subgraph Processing
CLK --> NOT1[NOT]
NOT1 --> NAND1[NAND]
NOT1 --> NOT2[NOT]
NOT2 --> NAND1[NAND]
end
subgraph Outputs
NAND1 --> P1
P1
end
This circuit uses two NOT gates and a NAND gate to detect the rising edge of the clock signa because the NOT gate introduces a delay in the signal.
With the signal
graph TD
subgraph Inputs
D-.->|NOT| D'
P1
end
subgraph Processing
D & P1 --> NAND_GATE1[NAND]
D' & P1 --> NAND_GATE2[NAND]
NAND_GATE1 --> R
NAND_GATE2 --> S
%% Highlight feedback loops
R --> NAND_GATE3
S --> NAND_GATE4
%% Feedback loops
NAND_GATE3 -->|Feedback| NAND_GATE4
NAND_GATE4 -->|Feedback| NAND_GATE3
end
subgraph Outputs
NAND_GATE3 --> Q
NAND_GATE4 --> Q'
end
The master-slave D flip-flop uses two NAND gates to store the value of the D input based on the rising edge of the clock signal.
Explanation
The D-flip-flop holds a 1-bit value by using the clock signal to control the transfer of the input data to the output. For example, suppose the input data is '1' and the clock signal has a rising edge. In that case, the P1 signal will be '1' for a short period, allowing the input data to be transferred to the output, which will then store the value '1' no matter how the input data changes after the rising edge of the clock signal. It is the same for the input data '0'. The D-flip-flop holds the value of the input data until the next rising edge of the clock signal.
(3)
Input: CLK, X Output: Y
Let
The output
State Diagram
The state diagram for the
graph TD
subgraph X_n-2/X_n-1
00 -->|0/0| 00
00 -->|1/0| 01
01 -->|0/0| 10
01 -->|1/1| 11
10 -->|0/0| 00
10 -->|1/1| 01
11 -->|0/1| 10
11 -->|1/1| 11
end
Truth Table
The truth table for the output
X_n\X_{n-1}X_{n-2} | 00 | 01 | 11 | 10 |
---|---|---|---|---|
0 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 1 | 1 |
Simplified Expression
Combinational Circuit
Based on the answer of (1) and (2), we can design the combinational circuit for the output
graph TD
subgraph Inputs
CLK
X
end
subgraph D-Flip-Flops
X & CLK --> D1 --> X_n-1
X_n-1 & CLK --> D2 --> X_n-2
end
subgraph Processing
%% Y = X(X_n-1 + X_n-2) + X_n-1X_n-2
X_n-1 & X_n-2 --> OR1[OR]
X & OR1 --> AND1[AND]
X_n-1 & X_n-2 --> AND2[AND]
AND1 & AND2 --> OR2[OR]
end
subgraph Outputs
OR2 --> Y
end
Knowledge
布尔代数 逻辑电路 D触发器
难点解题思路
对于第(3)问,考生需要理解D触发器的工作原理以及如何使用组合逻辑电路进行计数和比较。这需要扎实的时序电路基础和布尔代数知识。
解题技巧和信息
在解答涉及时序电路的题目时,先画出状态图或状态表,明确各个状态之间的转换关系。然后,根据状态图设计出D触发器的连接方式和所需的逻辑门。
重点词汇
- Boolean expression 布尔表达式
- NAND gate 与非门
- D-flip-flop D触发器
- Clock signal 时钟信号
- Sequential circuit 时序电路
参考资料
- "Digital Design" by M. Morris Mano, Chap. 5
- "Fundamentals of Logic Design" by Charles H. Roth, Chap. 7