GATE CSE 1992 | Question: 01-vi

Question

In an $11$-bit computer instruction format, the size of address field is $4$-bits. The computer uses expanding OP code technique and has $5$ two-address instructions and $32$ one-address instructions. The number of zero-address instructions it can support is ________

Comments

Expending opcode technique means encoding will be used instead of different opcode notation(ADD,SUB,MUL) in instruction format.

---

Detailed Video Solution with Complete Analysis & Two Methods to solve: https://youtu.be/BMNbc3Rbs80  

THIS Lecture contains solutions of ALL GATE PYQs on Expanding Opcode Technique with Complete Analysis & Quickest Approach to solve. 

Answer 1

No. of possible instruction encoding $=2^{11} = 2048$

No. of encoding taken by two-address instructions $=5 \times 2^4 \times 2^4 = 1280$

No. of encoding taken by one-address instructions $=32 \times 2^4 = 512$

So, no. of possible zero-address instructions $=2048 - (1280 + 512) = 256$

Comments

https://babbage.cs.qc.cuny.edu/courses/cs343/2004_02/Assignments/Assignment_04.html

---

Good to know.

Encoding of instruction must include opcode, operands & addressing information. Encoding: represent entire instruction as a binary value. the number of bytes needed depends on how much information must be encoded.

---

https://docs.google.com/viewer?url=http%3A%2F%2Fwww.sce.carleton.ca%2Fcourses%2Fsysc-3006%2Fs13%2FLecture%2520Notes%2Finstrencode.doc&embedded=true&chrome=false&dov=1

Answer 2

Out of 11 bits, 3 bits are for opcode in 2-Address. So 2^3=8 instructions(2-Address) are possible.

But 5 are being used. So 3 are free.

We use these 3 for 1-address instruction by using 4 bits of 1 of the addresses i.e. 3*16=48

Now out of 48 1-address instructions, 32 are being used. So we are left with 16.

Again use these 16 for 0-address instruction by using 4 bits of address i.e. 16*16=256

Comments

why have you done 16*16, can you explain this in more detail

---

@adactive18please explain in detail.

---

@amitqy

Coz out of 11 bits, 7 bits are fixed.

How? 

• While considering, for two-address instructions, we were left with 3 bits. So, we could have 8 combinations. From, those 8 combinations, we have assigned 5 combinations to two-address instructions. Now, we are left with 3 combinations.
• While considering, for one-address instructions, we were left with 7 bits (to be precised), therefore, we could have $2^7$ (128) combinations. BUT BUT, you might include the two-address instructions. So, we have $2^4$ * 3 (these are 3 combinations which were left in two-address instructions) = 48. But, we need only 32, therefore we are left with 16 combinations.

Now, coming to zero-address instructions, we don't have any address field, therefore, we can write $2^{11}$ combinations. BUT again, we might include one-address and two-address instructions, therefore out of 11 bits, we have used 7 bits (this is important) - coz we have counted them while calculating one-address instructions (those 16 combinations which were left). Hence, $2^{4}$ * 16 = 256. 

Answer 3

2-address instruction:

$opcode=3\ bits$

$address=4\ bits$

$address=4\ bits$

Total number of instruction: $2^3=8$ in which $5$ are $2-address\ instruction$. Therefore number of free opcodes=3

 

1-address instruction:

$opcode=7\ bits$

$address=4\ bits$

Total number of 1-address instruction possible: $3\times 2^4=48$. But only $'32'$ $1-address\ instructions$ are given. Hence $'16'$ instruction are free.

 

0-address instructions:

$opcode=11\ bits$

Total number of $0-address\ instructions$: $16\times 2^4=256$

---

$Ans: 256$

$Note:$

1. Identify the primitive instruction.Primitive instruction: smallest opcode.
2. Identify the total number of instructions possible in the CPU.
3. Identify the free opcodes after allocating primitive instruction.
4. Calculate the derived instruction by multiplying the free opcodes with a decoded form of a address field.

Answer 4

opcode = 3 bits

src addr = 4bits

destination addr = 4bits

Total 11 bit instruction format (given)

total possible opcodes = 2^3= 8 opcodes

for 2-address instruction

we have 5 double operand addresses so means 5 codes are for this so, 8-5 = 3 opcodes left.

now,

for 1-address instruction we must have allote opcode among these 3 opcodes which are left.

let's say opcode is p for 1-address  and 3 - p will be for 0-address

here for 1 -address we  p X 2^4 = p X 16 instructions

also it is given 32 1-address instruction we can have 

p will be 2 ( ie. 2 X 16 makes 32 1-addrees instruction)

for 0-address instruction

3 - p = 3-2 = 1 opcode for 0 address

1 X 2^4 X 2^4 = 1 X 16 X 16 = 256 zero-address instructions.

Note : Now I'm explaining in the simplest way possible.

you can think this problem like for 2-address instruction you fixed the src address and destination address ie just vary opcode bits 2^3 and subtract the given no of 2-address instructions.

for 1-address instruction you fixed only destination address thats why we did 2 X 2^4 , so we find the combination of first two fields.

for 0-address instruction nothing to fixed just do 1 X 2^4 X 2^4 every possible combination with 1 opcode.

I hope i am able to explained it in easiest way!