EECS 373 Winter 2005 Homework 1 (with solutions)

Problem 1 (address decoding)

A three hour tour took a bad turn and left you stranded on a desert island. Fortunately you have with you a digital emergency radio transceiver that you built as your EECS 373 final project. The project was all done and debugged, but when you turn it on, the Xilinx chip on the I/O board vaporizes in a foul smelling puff of smoke. Fortunately for you, all you were using this chip for was the address decoding. You happen to have a small breadboard with room for two integrated circuits, and you have one of each of the following logic circuits with you:

• quad 2-input OR gate
• quad 2-input NOR gate
• quad 2-input AND gate
• quad 2-input NAND gate
• triple 3-input NOR gate
• triple 3-input NAND gate
• dual 4-input AND gate
• single 8-input NAND gate

You will be rescued if you can build an address decoder with the following properties:

• Only address lines A[6:29] are available for decoding.
• Your decoder must decode a word (32-bit) register at address 0x02a00000.
• Your decoder must check all address lines A[6:11]
• You only need to decode the address lines; assume that other (still functional) circuitry still handles TS and TA timing and any other necessary signals.
• Your decoder must have an active low output (it should produce a logic zero output for the proper address).
• You may choose any two of the eight integrated circuits listed above (but no more than two).

Draw a suitable decoder circuit.

Solution (not unique; several solutions are possible):

0x02a00000 is as follows:

A[6] = 1
A[7] = 0
A[8] = 1
A[9] = 0
A[10] = 1
A[11] = 0
A[12] = 0
A[13] = 0
A[14] = 0
A[15] = 0
A[16] = 0
A[17] = 0
A[18] = 0
A[19] = 0
A[20] = 0
A[21] = 0
A[22] = 0
A[23] = 0
A[24] = 0
A[25] = 0
A[26] = 0
A[27] = 0
A[28] = 0
A[29] = 0

Use a triple 3-input NOR gate and a single 8-input NAND gate.
Connect all three NOR gate outputs to NAND gate inputs.
Connect A[6], A[8], A[10] to NAND gate inputs.
Connect A[7], A[9], and A[11:17] to NOR gate inputs.
The two extra unused NAND gate inputs can be tied high or connected to other NAND gate inputs.
The output of the NAND gate is the decoder output.

Problem 2 (address decoding, optimized)

Continuing the same scenario as problem 1...

You successfully contact a rescue ship with your radio. You learn that there are several other stranded logic designers on other islands. You also learn that the rescue ship captain has an intense fear of all shadows, including shadow locations from partial address decoding. You are informed that rescues will be made in order of those whose address decoders produce the fewest number of shadow locations.

Subject to the same constraints as in the previous problem, design a suitable decoder (your answer may or may not be the same as in the previous problem) optimized to minimize the number of shadow locations.

Draw the circuit for your optimized design.

Solution: the solution shown for problem 1 above is acceptable.

Problem 3 (shadow location counting)

Solution: A[18:29] are all not decoded, so they are essentially "don't care" values.
There are 12 such bits, so the decoder will respond to 2**12 = 4096 word addresses.

Problem 4 (assembly language programming, EABI)

int signum(int x) {
  if (x < 0) return -1;
  if (x == 0) return 0;
  if (x > 0) return 1;
}

Solution (not unique):

signum:	srawi	r4,r3,31	# x >> 31
	neg	r5,r3	# -x
	srwi	r5,r5,31	# t = (unsigned) -x >> 31
	or	r3,r4,r5	# sign(x) = (x >> 31) | t
	blr

The srawi does an algebraic (sign extending) right shift of x by 31 bits, so only the sign bit is retained (but it is sign extended to fill all 32 bits). The result is r4 = -1 if x is negative, r4 = 0 if x is zero or positive.

The neg and srwi does a logical (unsigned) right shift of x by 31 bits, and it is not sign extended. The result is r5 = 1 if (-x) is negative, r4 = 0 if (-x) is zero or positive. In other words, the result is r5 = 1 if x is positive, r4 = 0 if x is zero or negative.

The last step or's the results together to produce the final result. The table below shows the final register values for positive, zero, and negative input.

input	r4	r5	r3
positive	0	1	1
zero	0	0	0
negative	-1	0	-1

Problem 5

There is no problem 5.

Problem 6 (assembly language programming, EABI)

You are to write an EABI compliant PPC assembly language function to implement the blurfl function, which is defined as follows:

blurf(x,y) = smurfl(11,y) - smurfl(x,-7)

Assume an ABI compliant implementation of smurfl(u,v) exists that you may call as needed. Write only the code for blurfl; do not write any code for smurfl or for the caller of blurfl.

Solution: There is more than one way to do this, but in any case two things must be preserved: the parameter x must be preserved across the first call of smurfl to use it in the second call to smurfl, and the result of the first call to smurfl is an intermediate result that must be preserved across the second call. These aren't needed at the exactly same time, so nonvolatile register r31 can be shared to hold both of these. Thus, r31 must be saved on the stack on entry to blurfl and restored on exit.

blurfl:	mfspr	r0,LR
	stw	r0,4(r1)
	stwu	r1,-16(r1)
	stw	r31,12(r1)
	ori	r31,r3,0
	li	r3,11
	bl	smurfl
	ori	r4,r3,0
	ori	r3,r31,0
	ori	r31,r4,0
	li	r4,-7
	bl	smurfl
	sub	r3,r31,r3
	lwz	r31,12(r1)
	addi	r1,r1,16
	lwz	r0,4(r1)
	mtspr	LR,r0
	blr

Problem 7:

The following bit string is to be transmitted through a USB connection:

010110111011110111110111111011111110111111110001000001000000010000000001

Show the resulting bit string after both bit stuffing and NZRI encoding have been applied to this bit string. When determining the NZRI encoding, assume that the immediately preceding bit sent was "1". You must show your work to be eligible for partial credit.

Solution: after bit stuffing:

010110111011110111110111111001111110101111110110001000001000000010000000001

After NZRI encoding:

001110000111110000001l11111011111110011111110001011010100101010110101010100