سوال ۷۸ کنکور ارشد مهندسی کامپیوتر ۱۴۰۳

What one block can do

Each block of figure (a) is a programmable macrocell containing:

• a $16\times 1$ ROM, i.e. a lookup table that realizes any combinational function of its 4 address inputs $a,b,c,d$;
• one D flip-flop (so the block can store one registered bit);
• a 2-to-1 MUX with programmable select $S$ that drives the single output $Z$ either with the ROM (combinational) value or with the flip-flop (registered) value.

Key limits: a block produces one output, its ROM accepts at most 4 input variables, and its flip-flop registers the value that leaves that block (the FF is the registered form of the block's own output, not a free register for some other signal).

What circuit (b) requires

Tracing (b):

$Q_1 = \text{FF}(i_1)$ $g = \operatorname{NOR}\!\big(\overline{i_0},\, i_3,\, Q_1\cdot i_2\big)$ $\text{Out} = \text{FF}\big(g \oplus i_4 \oplus i_5 \oplus i_6\big)$

The bit clocked into the output flip-flop depends on $Q_1,i_0,i_2,i_3,i_4,i_5,i_6$ — the registered bit $Q_1$ plus 6 primary inputs = 7 variables, far beyond a single 4-input ROM. The design also needs two registered values ($Q_1$ and $\text{Out}$). We map it block by block, with no Boolean simplification (as required).

Minimum partition — three blocks

Block 1 — input register. Drives its flip-flop with $i_1$ and selects the registered value, producing $Z_1 = Q_1 = \text{FF}(i_1).$

Block 2 — front cone (combinational). ROM inputs $\{Q_1, i_0, i_2, i_3\}$ (exactly 4 variables); programmed to $Z_2 = \operatorname{NOR}\!\big(\overline{i_0},\, i_3,\, Q_1\cdot i_2\big) = g,$ with $S$ selecting the combinational ROM output.

Block 3 — XOR cone + output register. ROM inputs $\{g, i_4, i_5, i_6\}$ (4 variables); programmed to $Z_3 = g \oplus i_4 \oplus i_5 \oplus i_6,$ then the block's flip-flop registers it ($S$ = registered) to give $\text{Out}$.

Each ROM sees at most 4 inputs, each block emits a single output, both flip-flops are used, and nothing was simplified. The minimum is

$\boxed{3 \text{ blocks}}.$

Exam trick: Model each macrocell as "one 4-input LUT + one register feeding a single output." You cannot register an external signal and reuse that registered value inside the same block's ROM — the FF only registers the block's own output. So the input register, the 4-input front cone, and the XOR-plus-output-register cone each claim their own block.