Problem 1: https://blog.yexca.net/archives/198
Problem 2: https://blog.yexca.net/archives/201
Problem 3: https://blog.yexca.net/archives/200
Problem 4: https://blog.yexca.net/archives/202
Problem 5: This Article

Introduction

It’s almost two weeks, and I’ve finally gone through this exam paper. My efficiency is pretty low, honestly. Overall, I’d say the difficulty is a bit lower than China’s 408 exam, but the style and focus are different, so it’s hard to make a direct comparison. Hopefully, I can pick up the pace next time!

Ramblings

Haven’t written much in this ‘ramblings’ section lately. Honestly, it’s because when I think about publishing an article, I’m usually already exhausted and just don’t have the energy. This makes me think about how I used to just consider ‘should I learn this?’ Now, I have to factor in time, energy, and everything else. Saw a meme recently that nails it:

Can’t you just handle civil service exams with one hand, selected civil service with another, national exams with another, provincial exams with another, teaching qualifications with another, overseas study with another, internships with another, interviews with another, probation to full employment with another, fall recruitment with another, capstone projects with another, and dating with another? Oh, and you still need to keep one hand free, because Chinese people believe in always having a backup plan.

That really hit home. Human energy is limited. Gaining something always means losing something else—time, energy, passion, you name it. These are all quantifiable variables, but before, their upper limits were so high (or perhaps I was just overdrawing, to be precise) that I didn’t even notice them. As I get older, or rather, as I experience more things, more and more variables need to be considered, which probably explains why I’m always tired and less efficient.

Sometimes, living is just exhausting. Maybe I’m too materialistic; a bit more idealism, and the world seems pretty good (I’m afraid to make definitive statements about anything now, I fear uncertainty, but life often lacks certainty, though this stems from not mastering all variables. Won’t elaborate further, or this section will become another novel).

Background

Consider logic circuit X, configured as shown in Fig. 5.1, with input $ck$ and outputs $z_2, z_1, z_0$. Here, $R_0, R_1, R_2$ are positive-edge triggered D flip-flops, with their outputs initialized to 0. F is a logic circuit with inputs $x_2, x_1, x_0$ and outputs $y_2, y_1, y_0$, configured as shown in Fig. 5.2. A and B are any of the 2-input gates shown in Fig. 5.3. A clock pulse with a period of 1 unit time is applied to the $ck$ input of circuit X. Hereafter, let $n$ be a positive integer and $t$ be the time. At time $t=0$, $R_0, R_1, R_2$ are initialized. The output $z_2, z_1, z_0$ is assumed to stabilize at time $t=n$ due to the rising edge of the $n$-th clock pulse after time 0. This behavior is illustrated in Fig. 5.4. For the rest of this problem, delays caused by circuit components (gates, flip-flops, and wiring) are considered negligibly small compared to the clock pulse period.

• Fig. 5.1: Logic Circuit X

• Fig. 5.2: Logic Circuit F

• Fig. 5.3: 2-input Gates

• Fig. 5.4: Operation of Circuit X

1

Answer the following questions a~f.

a) The outputs $y_2, y_1, y_0$ of circuit F are determined solely by the values of inputs $x_2, x_1, x_0$. Choose the most appropriate name for a circuit that performs this kind of operation from the following options.

A. Asynchronous circuit

B. Combinational circuit

C. Sequential circuit

D. Nonlinear circuit

b) The output $z_2, z_1, z_0$ of circuit X at time $t=n$ is equal to the values of $y_2, y_1, y_0$ at time $t=$ [blank]. Express [blank] as a function of $n$.

c) Complete the truth table representing the operation of circuit F, as shown in the table format of Fig. 5.5, so that circuit X operates as shown in Fig. 5.4.

• Fig. 5.5: Operation of Circuit F

d) Choose the most appropriate name for a circuit that performs the operation shown in Fig. 5.4 from the following options, and answer with the symbol ①~④.

① Decoder ② Multiplexer ③ Counter ④ Shift Register

e) To make circuit X operate as shown in Fig. 5.4, what gates should A and B in Fig. 5.2 be? Choose from Fig. 5.3 and answer with the symbols ①~⑥. The same gate may be used multiple times.

f) Represent the logical AND of Boolean variables $x$ and $y$ as $xy$, the logical OR as $x+y$, and the NOT of $x$ as $\bar{x}$. Express the output $y_2$ of circuit F.

1-Solutions

1-a

• An asynchronous circuit refers to a circuit that does not use a clock signal, where each part operates independently.
• A combinational circuit is one whose output is determined solely by the current values of its inputs.
• A sequential circuit’s output depends not only on the current inputs but also on its internal state (e.g., flip-flop outputs).
• A nonlinear circuit refers to a circuit with input-output characteristics that are not linear.

This problem clearly refers to a ‘Combinational circuit’.

1-b

Because a D flip-flop first receives an input and only transfers it to the output on the rising edge of the clock, due to synchronous state updates, D flip-flops introduce a one-cycle delay. So, [blank]: $n-1$.

1-c

1-d

• A Decoder is a combinational logic circuit that decodes a small number of input signals into a larger number of output signals. It activates the corresponding output line based on the input’s binary encoding.
• A Multiplexer is a combinational logic circuit that selects one signal from multiple input signals to output. It uses select lines to determine which input signal passes through to the output.
• A Counter is a sequential logic circuit used to count pulse signals. Its output value changes in a specific way based on the number of pulse signals.
• A Shift Register is a sequential logic circuit that stores data and can shift it in a specific direction. It consists of a series of flip-flops.

This problem clearly refers to a ‘Shift Register’.

1-e

A: ② (OR) B: ① (AND)

By analyzing the truth table and its circuit, since there are multiple outputs, we can examine them one by one. Since the circuit for $y_0$ is already determined, let’s first look at the inputs when $y_1$ is 1.

Analyzing the circuit, we can temporarily ignore input $x_2$ (from the circuit or the next question, we know $x_2$ is absent after simplification).

Then, by testing with inputs that result in 1, we find that A is an OR gate and B is an AND gate.

Analyzing the inputs for $y_2$ outputting 1 confirms the results as correct.

1-f

2

G, shown in Fig. 5.6, is a logic circuit with inputs $x_2,x_1,x_0$ and outputs $y_2,y_1,y_0$. Using G, logic circuit Y is constructed as shown in Fig. 5.7, with $ck$ as input and $z_2,z_1,z_0$ as output. Furthermore, logic circuit $X'$ shown in Fig. 5.8 is constructed using Y. C and D in Fig. 5.8 are any of the 2-input gates shown in Fig. 5.3. Answer the following questions a~e.

Fig. 5.6: Logic Circuit G

Fig. 5.7: Logic Circuit Y

Fig. 5.8: Logic Circuit $X'$

Fig. 5.9: Operation of Circuit Y

a) Circuit G uses 5 gates to obtain output $y_0$. Describe one circuit that can obtain the same output as $y_0$ in G, using 2 or fewer gates listed in Fig. 5.3.

b) A clock pulse with a period of 1 unit time is applied to the $ck$ input of circuit Y. Assume $R_0,R_1,R_2$ are initialized at time $t=0$, and the output $z_2,z_1,z_0$ stabilizes at time $t=n$ due to the rising edge of the $n$-th clock pulse after time 0. Complete the table in Fig. 5.9 showing the output $z_2,z_1,z_0$ of circuit Y at times $t=1,4,7,12$.

c) Let $m$ be a non-negative integer. Under the conditions described in b), consider the output set $(z_2,z_1,z_0)$ of circuit Y at time $t=m$ as a vector and denote it as $z(m)$. What is the maximum Hamming distance between $z(m)$ and $z(m+1)$?

d) Circuit $X'$ in Fig. 5.8 and circuit X in Fig. 5.1 exhibit equivalent behavior. In this case, choose the gates for C and D in Fig. 5.8 from Fig. 5.3 and answer with the symbols ①~⑥. The same gate may be used multiple times. ‘Equivalent behavior’ here means the following: A clock pulse with a period of 1 unit time is applied from the same pulse generator P to the $ck$ input of both $X'$ and X, as shown in Fig. 5.10. When the outputs $w_2,w_1,w_0$ and $z_2,z_1,z_0$ respectively stabilize at time $t=n$ due to the rising edge of the D clock pulse within $X'$ and X at time $t=0$, then $w_2=z_2$, $w_1=z_1$, and $w_0=z_0$.

• Fig. 5.10

e) Consider a logic circuit like the one in Fig. 5.11. Assume inputs x and y simultaneously change from 0 to 1 at time $t=t_0$. Although output z is expected to remain 0, a pulse like that shown in Fig. 5.12 can occur due to delay in the NOT gate. This phenomenon is called a glitch (or hazard) and can cause malfunction depending on the connected circuit. In circuit $X'$ of Fig. 5.8, state whether a glitch can occur at output $w_0$ if delays in gates C and D are not negligible. If it can occur, suggest countermeasures; if not, explain why, in under 100 characters. Assume delays caused by components of circuit Y (gates, flip-flops, and wiring) are negligible, and the outputs of $R_0,R_1,R_2$ change simultaneously.

Fig. 5.11: Example of a logic circuit that can generate glitches

Fig. 5.12: Example of a glitch

2-Solutions

2-a

Circuit analysis shows that $y_0=x_1x_2+\bar{x_1}\bar{x_2}$, which is equivalent to $x_1\ \text{XNOR}\ x_2$. So, we can directly use one XNOR gate to simplify the circuit.

Only ⑥ can be used.

2-b

You can see the cycle starts from $t=7$.

2-c

Hamming distance represents the number of differing bits between two binary vectors of the same length.

From the truth table above, the maximum is 1.

2-d

C: ③ (XOR) D: ③ (XOR)

Analyzing the timing diagrams of both circuits, we can derive the truth table.

Analyzing the circuit, let’s first look at $w_1$ and find inputs that make $w_1$ equal to 1.

From the circuit, we can ignore $z_0$. The remaining $z_1$ and $z_2$ show an output of 1 when they are different, which is the form of an XOR gate. Thus, D is an XOR gate.

Analyzing inputs where $w_0$ is 1.

From the circuit, we can directly observe $z_0$ and $z_1 \oplus z_2$. They show an output of 1 when they are different, which is the form of an XOR gate. Thus, C is an XOR gate.

2-e

A glitch might occur at $w_0$. Countermeasures include adding a buffer to the output, adding a synchronous flip-flop, or re-evaluating the circuit design.

References

Boolean Algebra Simplification (Formula Method and Karnaugh Map Method)