Skip to content

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

Author

zephyr

Description

Answer the following questions on digital circuits.

(1) Provide a Boolean expression of the output \(D\) according to the following truth table. Design and depict a corresponding combinational circuit by using at most six 2-input NAND gates.

Truth table

\[ \begin{array}{|ccc|c|} \hline & \text{Input} & & \text{Output} \\ \hline A & B & C & D \\ \hline 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ \hline \end{array} \]

(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 \(\mathbf{CLK}\), a 1-bit input \(\mathbf{X}\), and a 1-bit output \(\mathbf{Y}\), where the input \(\mathbf{CLK}\) is used for the clocking. The output \(\mathbf{Y}\) is '1' when the number of '1' in the input \(\mathbf{X}\) values in the past three clock cycles (excluding the current clock cycle) is greater than the number of '0'. Otherwise, the output \(\mathbf{Y}\) is '0'. The output \(\mathbf{Y}\) may be any value during the initial three clock cycles after the circuit is powered on. Assume that the circuit satisfies the setup-time and hold-time constraints. Design and depict the circuit. You may use at most two D-flip-flops and an arbitrary number of 2-input AND gates, 2-input OR gates, and NOT gates, if necessary.

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

(1) 根据以下真值表提供输出 \(D\) 的布尔表达式。设计并使用最多六个 2 输入 NAND 门绘制相应的组合电路。

真值表

\[ \begin{array}{|ccc|c|} \hline & \text{Input} & & \text{Output} \\ \hline A & B & C & D \\ \hline 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ \hline \end{array} \]

(2) 描述 D 触发器的内部结构，并解释 D 触发器如何保持 1 位值。

(3) 考虑一个时钟同步顺序电路，具有 1 位输入 \(\mathbf{CLK}\)、1 位输入 \(\mathbf{X}\) 和 1 位输出 \(\mathbf{Y}\)，其中输入 \(\mathbf{CLK}\) 用于时钟控制。当过去三个时钟周期内（不包括当前时钟周期）输入 \(\mathbf{X}\) 的值中 '1' 的数量多于 '0' 的数量时，输出 \(\mathbf{Y}\) 为 '1'。否则，输出 \(\mathbf{Y}\) 为 '0'。电路上电后的初始三个时钟周期内，输出 \(\mathbf{Y}\) 可以是任意值。假设电路满足建立时间和保持时间约束。设计并绘制电路。你可以使用最多两个 D 触发器和任意数量的 2 输入 AND 门、2 输入 OR 门和 NOT 门，如果需要的话。

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:

  • \(AB = 1\) and \(C = 0\)
  • \(A + B = 1\) and \(C = 1\)

Simplified Expression

The simplified Boolean expression for the output \(D\) is:

\[ D = AB\overline{C} + (A + B)C = AB\overline{C} + AC + BC = A(B\overline{C} + C) + BC = AB + AC + BC \]

Combinational Circuit using 2-input NAND Gates

NAND: \(A \text{ NAND } B = (A \cdot B)'\)

Especially, \(A \text{ NAND } A = A'\), so we can use the NAND gate to implement the NOT gate.

First, we simplify the expression further:

\[ D = AB + AC + BC = ((AB + AC + BC)')' = ((AB)' \cdot (AC)' \cdot (BC)')' = ((((AB)' \cdot (AC)')')' \cdot (BC)')' \]

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 \(D\).

(2)

Internal Structure

A D-flip-flop consists of the following components:

  1. D input: The input data bit to be input to the flip-flop.
  2. Clock input: The clock signal that controls the operation of the flip-flop.
  3. Q output: The output of the flip-flop that stores the value of the D input.
  4. 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."

1
2
3
              /-------------\
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 \(P_1\), we can build the master-slave D flip-flop:

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 \(X_n\) denote the value of input \(X\) at clock cycle \(n\). Using D-flip-flops, we can easily obtain the values of \(X_{n-1}\) and \(X_{n-2}\).

The output \(Y\) is '1' when the number of '1's in the input \(X\) values in the past three clock cycles (excluding the current clock cycle) is greater than the number of '0's. Otherwise, the output \(Y\) is '0'.

State Diagram

The state diagram for the \(X_{n-1}\) and \(X_{n-2}\) values with the current clock cycle input and output \(X_n/Y\) is as follows:

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 \(Y\) based on the values of \(X_{n-1}\) and \(X_{n-2}\) is as follows:

X_n\X_{n-1}X_{n-2} 00 01 11 10
0 0 0 1 0
1 0 1 1 1

Simplified Expression

\(Y = X_{n-1}X_{n-2} + X_{n-1}X_n + X_{n-2}X_n\)

Combinational Circuit

Based on the answer of (1) and (2), we can design the combinational circuit for the output \(Y\) using the D-flip-flops and the corresponding logic gates.

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 时序电路

参考资料

  1. "Digital Design" by M. Morris Mano, Chap. 5
  2. "Fundamentals of Logic Design" by Charles H. Roth, Chap. 7