SOLUTIONS FOR Computer Science 150 Homework Assignment 1 Spring 1997 Due: Thursday, February 5th, 5:00 pm ---------------------------------------------------------------------------- 1. (a) Represent the following sentences by a single Boolean equation "The tape drive motor for a computer tape drive should be running iff: (i) the tape cassette has been inserted, (ii) the tape drive is in the manual mode and the motor start button has been pressed, or it is in the automatic mode and the "tape on" signal from the computer is present." SOLUTION: ( * == AND, + == OR, / == NOT ) Step 1: Define symbols RUNNING => Is Tape Drive Running? ( Running = 1 ) CI => Cassette Inserted ( Inserted = 1 ) MODE => Manual Mode (1), Auto Mode (0) MS => Motor Start Signal ( Start Signal Value = 1 ) TO => Tape On ( Signal From Computer When On = 1 ) Step 2: Write Out Equation RUNNING = CI*( MODE*MS + /MODE*TO) (b) Draw a Truth Table for the function indicating when the computer tape drive should be running. SOLUTION: Complete Table Table With Don't Cares CI MODE MS TO | RUNNING CI MODE MS TO | RUNNING -------------------+----------- -------------------+----------- 0 0 0 0 | 0 0 X X X | 0 0 0 0 1 | 0 1 0 X 1 | 1 0 0 1 0 | 0 1 1 1 X | 1 0 0 1 1 | 0 0 1 0 0 | 0 0 1 0 1 | 0 0 1 1 0 | 0 0 1 1 1 | 0 1 0 0 0 | 0 1 0 0 1 | 1 1 0 1 0 | 0 1 0 1 1 | 1 1 1 0 0 | 0 1 1 0 1 | 0 1 1 1 0 | 1 1 1 1 1 | 1 2. The Search for Extra-Terrestrial Intelligence (SETI). Your task is to construct a synchronous finite state machine (FSM) for SETI that can perform pattern matching automatically. The output of the FSM should be a single bit which indicates a pattern match. The desired pattern is 011, repeated twice. Your boss at SETI suggests a Mealy machine be used for simplicity, although this is not required. (a) A state diagram for the FSM. Assume a single state transistion will happen at each clock tick. Be sure to indicate the reset state on your diagram. SOLUTION: ( Notation: On Arches: INPUT VALUE/OUTPUT VALUE In States: Human-Understandable-State-name Finite State Machine State Name ) 1/0 0/0 ____ ____ / \ / \ | | | | _V____|__ _V____|__ _________ RESET / RESET \ 0/0 / "0" \ 1/0 / "01" \ ------>| |------>| |------>| | \ 0 / +---->\ 1 /<--------\ 2 / ~~~/\~~~~ | ~~~/\~~~~ 0/0 ~~~~|~~~~ | / | | 1/0 |______/____________|___________ | / | \ | / | \ | 0/0 / | 0/0 1/0 \ | _______/_ ____|____ \____V____ / "01101" \ 1/0 / "0110" \ 0/0 / "011" \ | |<------| |<------| | \ 5 / \ 4 / +-> \ 3 / ~~~~~~~\~ ~~~~~~~~~ | ~~~~~~~~~ \ | \_________________________/ 1/1 (b) The state transition table corresponding to the state diagram. SOLUTION: Note: 6 States so we need 3 bits to hold state information if we count them in binary. Present State | Next State RESET PS (Binary) IN | NS (Binary) OUT ----------------------+---------------------- 1 X (XXX) X | 0 (000) 0 0 0 (000) 0 | 1 (001) 0 0 0 (000) 1 | 0 (000) 0 0 1 (001) 0 | 1 (001) 0 0 1 (001) 1 | 2 (010) 0 0 2 (010) 0 | 1 (001) 0 0 2 (010) 1 | 3 (011) 0 0 3 (011) 0 | 4 (100) 0 0 3 (011) 1 | 0 (000) 0 0 4 (100) 0 | 1 (001) 0 0 4 (100) 1 | 5 (101) 0 0 5 (101) 0 | 1 (001) 0 0 5 (101) 1 | 3 (011) 1 Bonus: Your boss at SETI wants you to come up with a circuit which performs the same task which only uses one D- latch,a 2-bit shift register and no more than 6 gates SOLUTION: I don't have the energy to try to draw this in text... There's already a solution made up for this and we should get it in the next day or so. We'll put it up when we get it. 3. (a) Show how the two-input XOR and EQ functions can be implemented using just NAND gates. Hand in the schematics and a truth table showing the values of each gate output in your circuit. SOLUTION: XOR Equation: /A*B + A*/B = XOR Original Logic Diagram -----\ A --O| AND | ____ B ---| |--\ \ -----/ \ OR | -----\ / |--- XOR A ---| AND |--/ / B --O| | ~~~~~ -----/ Push 2 Bubbles From XOR End. Pushing 2 Bubbles Doesn't Change Value Through Line. -----\ A --O| AND | ____ B ---| |--\ \ -----/ \ OR | -----\ / |OO--- XOR A ---| AND |--/ / B --O| | ~~~~~ -----/ Push 1 Bubbles Through OR Gate To Turnm It Into A NAND With Negated Inputs... -----\ A --O| AND | ____ B ---| |--O| \ -----/ |AND | -----\ | |O--- XOR A ---| AND |--O| / B --O| | ~~~~ -----/ Slide Bubbles To Output Of Leftmost AND Gates To Make Them NANDs. -----\ A --O| AND | ____ B ---| |O--| \ -----/ |AND | -----\ | |O--- XOR A ---| AND |O--| / B --O| | ~~~~ -----/ To Replace Bubbles On Inputs, Notice That: |\ _____ X ---| \O---- OUT == x -+--| \ | / | | AND |O---- OUT |/ +--| / ~~~~~ Finally: _____ A -+--| \ AB0 -----\ | | AND |O---------| AND | AB1 ____ +--| / B ---| |O-----| \ ~~~~~ -----/ |AND | _____ -----\ AB3 | |O--- XOR B -+--| \ A ---| AND |O-----| / | | AND |O---------| | ~~~~ +--| / AB2 -----/ ~~~~~ A B | AB0 AB1 AB2 AB3 XOR ------+-------------------------- 0 0 | 1 1 1 1 0 0 1 | 1 0 0 1 1 1 0 | 0 1 1 0 1 1 1 | 0 1 0 1 0 SOLUTION: EQ Equation: A*B + /A*/B = EQ _____ A -+--| \ -----\ | | AND |O-+ A ---| AND | AB1 ____ +--| / | B ---| |O-----| \ ~~~~~ | -----/ |AND | _____ | AB0 -----\ AB3 | |O--- EQ B -+--| \ +-------| AND |O-----| / | | AND |O---------| | ~~~~ +--| / AB2 -----/ ~~~~~ A B | AB0 AB1 AB2 AB3 EQ ------+-------------------------- 0 0 | 1 1 1 0 1 0 1 | 1 1 0 1 0 1 0 | 0 1 1 1 0 1 1 | 0 0 0 1 1 (b) Show how the two-input XOR and EQ functions can be implemented using just NOR gates. Hand in the schematics and a truth table showing the values of each gate output in your circuit. SOLUTION: XOR ( Note: OUTPUT Is /XOR. That should be replaced with a NOT Gate Implemented With NAND but my typing finger is getting tired... ) _____ A -+--\ \ AB0 -----\ | | OR |O---------\ OR | AB1 ____ +--/ / B ---/ |O-----\ \ ~~~~~ -----/ | OR | _____ -----\ AB3 | |O--- /XOR B -+--\ \ A ---\ OR |O-----/ / | | OR |O---------/ | ~~~~ +--/ / AB2 -----/ ~~~~~ A B | AB0 AB1 AB2 AB3 /XOR ------+-------------------------- 0 0 | 1 0 1 0 1 0 1 | 1 0 0 1 0 1 0 | 0 1 1 0 0 1 1 | 0 0 0 0 1 SOLUTION: EQ ( Note: Same Comment As Above Except The NOT Gate Should Be Implemented With A NOR Gate Instead. ) Equation: A*B + /A*/B = EQ _____ A -+--\ \ -----\ | | OR |O-+ A ---\ OR | AB1 ____ +--/ / | B ---/ |O-----\ \ ~~~~~ | -----/ | OR | _____ | AB0 -----\ AB3 | |O--- /EQ B -+--\ \ +-------\ OR |O-----/ / | | OR |O---------/ | ~~~~ +--/ / AB2 -----/ ~~~~~ A B | AB0 AB1 AB2 AB3 /EQ ------+-------------------------- 0 0 | 1 1 1 0 0 0 1 | 1 0 0 0 1 1 0 | 0 0 1 0 1 1 1 | 0 0 0 1 0 ----------------------------------------------------------------------- Newton/Pister