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

标签：

• 东京大学
• 时序逻辑电路
• 触发器

Author

Codex

Description

Let us consider implementing a linear recurrence sequence generator as a sequential circuit. Assume that the clock is an ideal rectangular wave without skew, and that the gate delays are negligible. The clock signal must be used for the Clock inputs of all the flip-flops, and must not be used otherwise.

Let $m$ and $0<j_1<j_2<\cdots<j_m\le256$ be positive integers. Given initial values $x_0,x_1,\ldots,x_{255}$, the value of $x_n$ for $n\ge256$ is defined by the recurrence equation:

$$x_n=x_{n-j_1}\oplus x_{n-j_2}\oplus\cdots\oplus x_{n-j_m},$$

where $x_i\in\{0,1\}$, and $\oplus$ represents the exclusive-or (XOR) operator.

You can use AND, OR and NOT gates and positive-edge-triggered D flip-flops in your circuit design. Recall that a positive-edge-triggered D flip-flop has two inputs $D$ and Clock, and one output $Q$. At the positive-edge of the Clock signal, the $D$ input is sampled and stored as the current value of $Q$. The value of $Q$ is kept unchanged until the next positive-edge of the Clock signal. A flip-flop is depicted as the following figure in this problem.

Answer the following questions.

(1) Design a 2-input XOR circuit with AND, OR and NOT gates.

(2) Consider the following circuit and the Input and Clock signals depicted by the timing diagram below. Assume that the initial values of $Q_1,Q_2$ and $Q_3$ are zeros. Depict the timing diagram for $Q_1,Q_2$ and $Q_3$ along with the Input and Clock signals.

(3) Suppose that we have 512 positive-edge-triggered D flip-flops $X_1,X_2,\ldots,X_{256}$ and $C_1,C_2,\ldots,C_{256}$. Assume that initially $X_i$ stores the value of $x_{256-i}$ and $C_i$ stores 1 if $i\in\{j_1,j_2,\ldots,j_m\}$ and 0 otherwise, for $i=1,2,\ldots,256$. Design a circuit so that $X_i$ stores the value of $x_{256-i+k}$ at the $k$th clock cycle.

(4) Modify the circuit you have answered in question (3) as follows, in order to enable the initialization of the flip-flops. It is enough to show only the difference. Add three inputs $W$, $X_0$ and $C_0$. At the positive edge of Clock, the circuit should execute the following. If input signal $W$ is 0, the value of $X_{i-1}$ is moved to $X_i$, and the value of $C_{i-1}$ is moved to $C_i$, for $i=1,2,\ldots,256$. If input signal $W$ is 1, the circuit works as described in question (3).

题目描述

考虑用时序电路实现一个线性递推序列生成器。假设时钟为无偏斜的理想矩形波，门延迟可忽略。时钟信号必须用于全部触发器的 Clock 输入，且不得用于其他用途。

设 $m$ 及 $0<j_1<j_2<\cdots<j_m\le256$ 为正整数。给定初值 $x_0,x_1,\ldots,x_{255}$，对 $n\ge256$，由递推式

$$x_n=x_{n-j_1}\oplus x_{n-j_2}\oplus\cdots\oplus x_{n-j_m}$$

定义 $x_n$，其中 $x_i\in\{0,1\}$，$\oplus$ 表示异或运算。

设计电路时可使用 AND、OR、NOT 门和上升沿触发的 D 触发器。上升沿触发的 D 触发器有两个输入 $D$、Clock，以及一个输出 $Q$。在 Clock 信号的上升沿，对 $D$ 输入采样并存储为 $Q$ 的当前值。$Q$ 的值保持不变，直到 Clock 信号的下一个上升沿。本题以如下图形表示触发器。

回答下列问题。

(1) 用 AND、OR、NOT 门设计一个双输入异或电路。

(2) 考虑下图电路以及时序图所示的 Input 和 Clock 信号。假设 $Q_1,Q_2,Q_3$ 初值均为0。画出 $Q_1,Q_2,Q_3$ 的时序图，并同时画出 Input 和 Clock 信号。

(3) 假设有512个上升沿触发的 D 触发器 $X_1,X_2,\ldots,X_{256}$ 和 $C_1,C_2,\ldots,C_{256}$。对于 $i=1,2,\ldots,256$，初始时 $X_i$ 存储 $x_{256-i}$；若 $i\in\{j_1,j_2,\ldots,j_m\}$，$C_i$ 存储1，否则存储0。设计电路，使 $X_i$ 在第 $k$ 个时钟周期存储 $x_{256-i+k}$。

(4) 为了能够初始化触发器，按下述要求修改你在 (3) 中设计的电路。只须表示改变的部分。增加三个输入 $W,X_0,C_0$。在 Clock 上升沿，电路应执行：若输入信号 $W=0$，则对 $i=1,2,\ldots,256$，将 $X_{i-1}$ 的值移入 $X_i$，将 $C_{i-1}$ 的值移入 $C_i$；若 $W=1$，电路按 (3) 中所述方式工作。

Kai

(1)

For two input bits $a,b$,

$$a\oplus b=(a\land\neg b)\lor(\neg a\land b).$$

Use two NOT gates, two AND gates and one OR gate. The two AND outputs are disjoint: the result is one precisely for $(a,b)=(1,0)$ or $(0,1)$.

(2)

At every rising edge, all flip-flops sample their inputs simultaneously. If $u_k$ is the external input at the $k$-th edge, then

$$\begin{gathered} Q_1(k)=u_k,\\ Q_2(k)=Q_1(k-1),\\ Q_3(k)=Q_2(k-1). \end{gathered}$$

All three outputs retain their values between rising edges. With the given initial zeros:

Rising edge $k$	1	2	3	4	5	6
Input $u_k$	1	1	0	1	0	0
$Q_1(k)$	1	1	0	1	0	0
$Q_2(k)$	0	1	1	0	1	0
$Q_3(k)$	0	0	1	1	0	1

(3)

Let $X_i$ and $C_i$ also denote the current output bits of their flip-flops. Form the combinational feedback

$$T_i=C_i\land X_i,\qquad F=\bigoplus_{i=1}^{256}T_i.$$

A cascade or tree of 255 two-input XOR circuits from (1) implements this expression; each tap term requires an AND gate. Connect the D inputs as follows:

$$\begin{aligned} D(X_1)&=F,\\ D(X_i)&=X_{i-1} &&(2\le i\le256),\\ D(C_i)&=C_i &&(1\le i\le256). \end{aligned}$$

All 512 flip-flops share the unchanged clock. Each $C_i$ retains its initialized tap bit.

To prove correctness, suppose that after $k$ edges, $X_i=x_{256-i+k}$. Immediately before edge $k+1$,

$$F=\bigoplus_{r=1}^{m}x_{256-j_r+k}=x_{256+k}.$$

Thus the next value of $X_1$ is $x_{256+k}$, and for $i\ge2$ the next value is

$$X_{i-1}=x_{256-(i-1)+k}=x_{256-i+(k+1)}.$$

The initialization supplies the induction base $k=0$.

(4)

A multiplexer selecting $b$ when $W=0$ and $a$ when $W=1$ can be implemented as

$$\operatorname{mux}_W(a,b)=(W\land a)\lor(\neg W\land b).$$

Use it at the D inputs:

$$\begin{aligned} D(X_1)&=\operatorname{mux}_W(F,X_0),\\ D(X_i)&=X_{i-1} &&(2\le i\le256),\\ D(C_i)&=\operatorname{mux}_W(C_i,C_{i-1}) &&(1\le i\le256). \end{aligned}$$

Here $X_0,C_0$ are external inputs. For $i\ge2$, both modes require the same shift of $X_i$, so no selection gate is needed there. The tap registers shift in load mode and retain their values in recurrence mode. The clock continues to connect only to the flip-flop clock pins.

To load prescribed values $X_i^*,C_i^*$, keep $W=0$ for 256 rising edges and supply $X_{257-k}^*,C_{257-k}^*$ at edge $k$. After the final load edge, all registers contain their prescribed values; set $W=1$ to begin generation.

Reference

• 大学公表の原題