東京大学 情報理工学系研究科 コンピュータ科学専攻 2016年8月実施 専門科目I 問題3

标签：

• Tokyo-University
• D-Flip-Flop
• Bubble-Sort

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

Answer the following questions regarding sequential logic circuits. Assume that the clock is an ideal rectangular wave without skew, and that the gate delay is short enough compared with the clock cycle.

(1) Choose one from D flip-flop, JK flip-flop and T flip-flop, and explain how its output is determined by the clock, the inputs and the internal state.

(2) Design and depict a circuit ALT, whose output toggles between 0 and 1 every clock cycle as illustrated below. You can use the flip-flop you have chosen in Question (1), and the AND, OR and NOT gates.

Edge	Before first rising edge	First rising	First falling	Second rising	Second falling	Third rising	Third falling	Fourth rising	Fourth falling	Fifth rising
Clock	0	1	0	1	0	1	0	1	0	1
Output of ALT	0	1	1	0	0	1	1	0	0	1

(3) Design and depict a circuit that sorts 8 integers, each of which being a 4-bit unsigned integer, by the bubble sort algorithm. The inputs and the outputs of the sorting circuit are as follows:

• (i) Inputs $I_0,I_1,\ldots,I_7$. Each of them is a 4-bit unsigned integer.
• (ii) 1-bit input $L$.
• (iii) Outputs $O_0,O_1,\ldots,O_7$. Each of them is a 4-bit unsigned integer.
• (iv) 1-bit output $V$.

The sorting circuit should work as follows.

(a) When $L$ is 1, the inputs $I_0,I_1,\ldots,I_7$ are stored using 32 flip-flops. Those stored data are regarded as eight 4-bit unsigned integers, and called $v_0,v_1,\ldots,v_7$ in the following.

(b) After $L$ becomes 0, in the first clock cycle, the circuit compares $v_0$ and $v_1$, and if $v_0>v_1$, then it swaps them, and otherwise it keeps them. The same operations are applied to the three pairs $(v_2,v_3)$, $(v_4,v_5)$ and $(v_6,v_7)$. The new values of $v_0,v_1,\ldots,v_7$ are output to $O_0,O_1,\ldots,O_7$.

(c) In the second clock cycle after $L$ becomes 0, the circuit compares $v_1$ and $v_2$, and if $v_1>v_2$, then it swaps them, and otherwise it keeps them. The same operations are applied to the two pairs $(v_3,v_4)$ and $(v_5,v_6)$. The new values of $v_0,v_1,\ldots,v_7$ are output to $O_0,O_1,\ldots,O_7$.

(d) The circuit repeats steps (b) and (c) while $L$ is 0. If no swap of values happens for two consecutive clock cycles that execute (b) or (c), $V$ is set to 1, and otherwise $V$ is set to 0.

You can use the following circuits in your design: the flip-flop you have chosen in Question (1), the ALT circuit you have designed in Question (2), 4-bit comparator CMP, 4-bit 2-to-1 multiplexer MUX, and the AND, OR and NOT gates.

题目描述

回答有关时序逻辑电路的问题。设时钟为无偏斜的理想矩形波，门延迟相对时钟周期足够短。

（1）从 D、JK、T 触发器中任选一种，说明时钟、输入和内部状态如何决定其输出。

（2）设计并图示电路 ALT，使输出如上表所示，每个时钟周期在 $0,1$ 间翻转。可用第（1）问所选触发器及 AND、OR、NOT 门。

（3）设计并图示用冒泡排序将 $8$ 个 4 位无符号整数排序的电路。输入为 $I_0,\ldots,I_7$ 和 1 位装载信号 $L$；输出为 $O_0,\ldots,O_7$ 和 1 位完成信号 $V$，各 $I_i,O_i$ 均为 4 位无符号整数。$L=1$ 时用 32 个触发器保存输入，记为 $v_0,\ldots,v_7$。$L$ 变为 $0$ 后，首个时钟周期比较交换

$$(v_0,v_1),(v_2,v_3),(v_4,v_5),(v_6,v_7)$$

第二个时钟周期比较交换

$$(v_1,v_2),(v_3,v_4),(v_5,v_6).$$

每对中前者大于后者时交换，否则保持原值；每周期将更新后的 $v_0,\ldots,v_7$ 输出至 $O_0,\ldots,O_7$。$L=0$ 期间交替重复这两层比较。若执行这两层的连续两个周期均无交换则令 $V=1$，否则令 $V=0$。可使用所选触发器、ALT、4 位比较器 CMP、4 位 2 选 1 MUX 及 AND、OR、NOT 门。

Kai

(1)

选择上升沿触发的 D 触发器。在每个上升沿，

$$Q(t^+)=D(t),$$

其余时间输出保持原内部状态 $Q$。

(2)

把反相输出反馈到输入，即令 $D=\overline Q$，并以 $Q$ 为 ALT 输出。每个有效时钟沿都有 $Q^+=\overline Q$，故输出逐周期翻转；初始化 $Q=0$。

(3)

先定义比较交换单元 $\operatorname{CE}(x,y)$：CMP 产生 $c=[x>y]$，两个 MUX 输出

$$(x',y')= \begin{cases} (y,x),&c=1,\\ (x,y),&c=0. \end{cases}$$

用 8 个 4 位寄存器 $R_0,\ldots,R_7$ 保存 $v_i$。控制位 $P$ 在装载时置 $0$；$L=0$ 后每周期翻转。$P=0$ 时启用偶数边界的四个 CE，$P=1$ 时启用奇数边界的三个 CE；未启用边界上的寄存器保持原值。最外层 MUX 在 $L=1$ 时选择 $I_i$，在 $L=0$ 时选择本轮 CE 的结果。

令 $s$ 为当前启用的各 CMP 交换信号之 OR，即“本周期发生过交换”。再设 1 位寄存器 $H$ 记录上一周期是否无交换，并用 1 位寄存器输出 $V$：

$$\begin{aligned} L=1:&\quad P^+=0,\ H^+=0,\ V^+=0,\\ L=0:&\quad P^+=\overline P,\ H^+=\overline s,\ V^+=H\land\overline s. \end{aligned}$$

因此 $V$ 恰在连续一个偶层和一个奇层均无交换后变为 $1$。此时所有相邻对均有序，故 $O_0\le\cdots\le O_7$；若随后发生交换，$V$ 在该周期清零。