A4 - Boolean Algebra, due Tues, Oct. 9

01 Oct 2018 in CS 101 on Assignments

Assigned Monday, Oct. 1; Due Tues, Oct. 9 at 11:59 PM;

Read the lecture notes on Combinational Logic Circuits and complete the following.

Question 1 [Updated]

Given A · B + B · C + C′ · (A + B)

1. Write a complete truth table for the values of the Boolean expressions
2. Implement a circuit for the above Boolean expression

Question 2

The odometer effect is what happens when a mechanical mileage counter on a car reads 9999 and then “flips over” to 10000. The problem is that all the dials have to turn at the same time.

The odometer effect happens much more often in binary:

	increment 3 to 4: 	011 to 	100 (3 bits change)
	increment 5 to 6:	101 to 	110 (2 bits change)
	increment 7 to 8:  	0111 to 1000 (4 bits change)
	...

In many electro-mechanical systems, the process of flipping so many bits can consume a lot of power or produces excessive vibration.

In 1953, Frank Gray developed reflected binary code also called Gray code to avoid the odometer effect.

For a binary sequence, a two-bit Gray code looks like this:

	00 to 01 		(1 bit changes, flipped right bit)
	01 to 11 		(1 bit changes, flipped left bit)
	11 to 10 		(1 bit changes, flipped right bit)
	10 to 00 		(1 bit changes, flipped left bit)

This sequence covers all the two-bit binary numbers, although in a jumbled up order. However, it’s useful because exactly one bit changes each time.

To write sequences with more bits, you can mirror-image (aka reflect) a shorter sequence. For example, to write the three-bit Gray code, I’d start with the two-bit sequence above, and then write it backwards. I’ll leave the third bit empty (_) for now.

	_00 to _01 		(original two-bit sequence)
	_01 to _11 		
	_11 to _10 		
	_10 to _00
	
	_10 to _00 		(same sequence but in reverse)
	_00 to _01 		
	_01 to _11 		
	_11 to _10 		

So if this is a three-bit Gray code, what’s the third-bit? Now, we fill in zeros for the first half, and ones for the right half. The final three-bit Gray code.

	000 to 001 		(starts with zeros)
	001 to 011 		
	011 to 010 		
	010 to 000 	
	
	110 to 100 		(starts with ones)
	100 to 101 		
	101 to 111 		
	111 to 110 		

Now, your task is to build the circuit that allows me to click pins to enter four-bit gray codes, and convert that to the corresponding binary number. Check out how this will work in Prof. League’s 30-second video:

In this video, Prof. League is clicking just one gray-code bit at a time. The LEDs at the bottom are lighting up in standard binary order. To emphasize that, he used a seven-segment hexadecimal display to cycle through 0, 1, 2, 3, 4, ... 8, 9, A, B, C, D, E, and F.

	Decimal			Binary		Gray
	0			0000		0000
	1			0001		0001
	2			0010		0011
	3			0011		0010
	4			0100		0110
	5			0101		0111
	6			0110		0101
	7			0111		0100
	8			1000		1100
	9			1001		1101
	10 = A			1010		1111
	11 = B			1011		1110
	12 = C			1100		1010
	13 = D			1101		1011
	14 = E			1110		1001
	15 = F			1111		1000

Here are the formulas that govern Gray-to-binary conversion:

• B3 = G3
• B2 = B3 XOR G2
• B1 = B2 XOR G1
• B0 = B1 XOR G0

If you’re using the logic.ly demo to complete this homework, upload a screenshot using the submission portal below.

Submission Portal

Upload your related homework files at https://goo.gl/forms/JOGeregevSNgHVcg1.