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

标签：

• Tokyo-University
• Computer-Science.Digital-Logic.Sequential-Circuit
• Computer-Science.Digital-Logic.Flip-Flop

Author

Codex

Description

Independent problem summary (English)

Official examination paper, Problem 4

Design a binary recurrence generator using AND, OR, NOT gates and positive-edge-triggered D flip-flops. Gates have negligible delay; the ideal clock has no skew and connects only to flip-flop clock inputs. For positive integers $0<j_1<\cdots<j_m\le256$, initial bits $x_0,\ldots,x_{255}$ determine

$$x_n=\bigoplus_{r=1}^{m}x_{n-j_r},\qquad n\ge256.$$

(1) Construct a two-input XOR circuit from the permitted gates.

(2) Three flip-flops are cascaded: the external input feeds $D_1$, $Q_1$ feeds $D_2$, and $Q_2$ feeds $D_3$. They share the clock and initially store zero. Draw all three outputs for the input and clock below.

(3) Use 512 flip-flops, $X_1,\ldots,X_{256}$ and $C_1,\ldots,C_{256}$. Initially $X_i=x_{256-i}$ and $C_i=1$ exactly at the selected tap indices. Design the circuit so that after $k$ clock edges, $X_i=x_{256-i+k}$.

(4) Add inputs $W,X_0,C_0$. When $W=0$, each rising edge must copy $X_{i-1}$ into $X_i$ and $C_{i-1}$ into $C_i$. When $W=1$, perform the recurrence from (3). Give the required circuit changes.

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

$$Q_1(k)=u_k,\qquad Q_2(k)=Q_1(k-1),\qquad Q_3(k)=Q_2(k-1).$$

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.