東京大学 情報理工学系研究科 創造情報学専攻 2019年8月実施 筆記試験 第2問

标签：

• Tokyo-University
• Synchronous-Circuit

Author

tomfluff, 祭音Myyura

Description

Consider making a memory that can be accessed randomly, using D-FFs (Flip Flop) and 2:1 multiplexers. Assume that the D-FF is a circuit that stores 1 bit as shown in Fig. 1. A 1-bit signal given to d is written to this circuit at the rise of the clock signal clk, and this circuit continues to output the written signal to q. As shown in Fig. 2, the 2:1 multiplexer is a circuit that selects one of the two input signals a and b according to the selection signal s and outputs it to c.

(1) Give a truth table for the 2:1 multiplexer shown in Fig. 2. Assume that this multiplexer selects a when s is $0$ and selects b when s is $1$.

(2) Draw a circuit diagram of a memory that stores 4 bits and outputs 1 bit at the position specified by a 2-bit address according to the following instructions:

• Use only two kinds of components, which are the D-FF shown in Fig. 1 and the 2:1 multiplexer in Fig. 2.
• Ignore circuits related to clock and write (do not connect anything to clk and d).
• Specify the address of data stored in each D-FF in the circuit diagram.
• Specify the lower bit of the 2-bit address signal wires as addr_low and the upper bit of it as addr_high in the circuit diagram.
• Specify the output wire of the memory as output in the circuit diagram.

(3) In the similar way as in (2), consider a memory that stores $2^n$ bits and outputs 1 bit at the position specified by an n-bit address using the D-FF shown in Fig. 1 and the 2:1 multiplexer shown in Fig. 2. Give how many multiplexers you need to make this memory.

(4) The D-FF shown in Fig. 3 is a D-FF with write control. In this D-FF, the signal given to d is written only when the input to the write enable signal we is $1$ at the rise of the clock signal clk. If we is $0$, a previously written signal continues to be output to q without updating the stored contents. Give a circuit diagram of this D-FF in Fig. 3 using only the D-FF in Fig. 1 and the 2:1 multiplexer in Fig. 2. Assume that this multiplexer selects a when s is $0$ and selects b when s is $1$.

(5) Draw a circuit diagram of a memory that stores 4 bits according to the following instructions:

• Assume that, at the rise of the clock signal, 1 bit data is written at the position specified by a 2-bit address.
• Use only three kinds of components, which are the D-FF with write control shown in Fig. 3, the AND gate shown in Fig. 4, and the NOT gate shown in Fig. 5.
• You can use up to four AND gates and up to two NOT gates.
• Ignore circuits related to clock output (do not connect anything to clk and q).
• Specify the address of data stored in each D-FF in the circuit diagram.
• Specify the lower bit of the 2-bit address signal wires as addr_low and the upper bit of it as addr_high in the circuit diagram.
• Specify the data input wire of the memory as input in the circuit diagram.

题目描述

使用 D 触发器（D-FF）和 2:1 多路选择器制作可随机访问的存储器。图 1 的 D-FF 存 1 位：在时钟 clk 上升沿把输入 d 写入，随后从 q 持续输出。图 2 的 2:1 多路选择器根据选择信号 s 从输入 a,b 中选一个输出到 c。

1. 写图 2 多路选择器真值表：s=0 选 a，s=1 选 b。
2. 只用图 1 D-FF 和图 2 多路选择器，画一个存 4 位、由 2 位地址选择并输出其中 1 位的电路。忽略时钟与写入电路，不连接 clk,d；标明每个 D-FF 所存数据的地址；把地址低、高位线分别标为 addr_low、addr_high，存储器输出线标为 output。
3. 类似地，用上述元件制作存 $2^n$ 位、由 $n$ 位地址选 1 位输出的存储器，求所需多路选择器数量。
4. 图 3 是带写使能的 D-FF：只有 clk 上升沿时 we=1 才把 d 写入；we=0 时保持原内容并继续从 q 输出。只用图 1 普通 D-FF 和图 2 多路选择器实现图 3，画电路；多路选择器仍为 s=0 选 a、s=1 选 b。
5. 按以下要求画存 4 位的写入电路：在时钟上升沿，把 1 位输入写到 2 位地址指定位置；只用图 3 带写控 D-FF、图 4 AND 门、图 5 NOT 门；AND 最多 4 个，NOT 最多 2 个；忽略时钟和读出，不连接 clk,q；标明每个 D-FF 地址；地址线标 addr_low、addr_high，数据输入线标 input。

Kai

(1)

a	b	s	MUX
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

(2)

(3)

Given the circumstances, we would need:

$$\sum_{i=1}^{n} {2^{n-i}}=2^n - 1$$

Since we gradually divide all inputs into 2 as inputs to the MUX, so the first layer would be $2^{n-1}$ the second $2^{n-2}$ and so on, until we have $2^{n-n}$ as the final MUX which would give the correct output.

(4)

itsuitsuki's solution

The multiplexer selects the feedback value $q$ when we is 0 and the external input d when we is 1; its output drives the D-FF input.

tomfluff's solution

Of the two circuits in this figure, only the bottom one implements the specified D-FF. The top circuit samples d in an extra D-FF, so a write reaches the output one clock edge late. An unspecified initial output is allowed because the problem gives no reset or initial value.

(5)