The data path shown in the figure computes the number of 1s in the 32-bit input word corresponding to an unsigned even integer stored in the shift register. The unsigned counter, initially zero, is incremented if the most significant bit of the shift register is 1. The microprogram for the control is shown in the table below:
| Microinstruction | Reset_Counter | Shift_left | Load_output |
|-----------------|---------------|------------|-------------|
| BEGIN | 1 | 0 | 0 |
| I1 | 0 | 1 | 0 |
| I1 | 0 | 1 | 0 |
| ... | ... | ... | ... |
| I1 | 0 | 1 | 0 |
| END | 0 | 0 | 1 |
The counter width (k), the number of missing microinstructions (n), and the control word for microinstructions I1, I2, ..., In are, respectively.
A. 32,5,010
B. 5,32,010
C. 5,31,011
D. 5,31,010
GATE 2006 · Computer Organization and Architecture · Microprogramming · medium
Answer: Counter width k=5, missing microinstructions n=31, control word=010. Answer: D. 5,31,010
Determine counter width k: The input is a 32-bit unsigned even integer, meaning its LSB is always 0. Therefore at most 31 bits can be 1. The counter must count from 0 to 31, requiring ceil(log_2(32)) = ceil(5) = 5 bits. So k = 5.
Determine number of missing microinstructions n: To examine all 32 bits of the shift register, we need exactly 32 left-shift operations, each done by one I1 microinstruction. The microprogram table shows BEGIN, then one I1, then n missing I1s, then END. Total I1 count = 1 + n = 32 (one shown + n hidden). But checking options: option D says n=31. So 1 shown + 31 missing = 32 total I1 microinstructions = 32 shifts. This is consistent. n = 31.
Encode the control word for I1: For the I1 (counting) microinstructions: Reset_Counter = 0 (do not reset), Shift_left = 1 (shift the register), Load_output = 0 (not done yet). Binary encoding: 0, 1, 0 → control word = 010.
Match to options: k=5, n=31, control word=010 matches option D: 5, 31, 010.