CS 2110 Homework 3 Solution

1 Overview
For this assignment, we’ll be working with Sequential Logic components, state machines and K-maps. This will be a 3 part assignment.
Objectives:
1. Understand how information is stored in a computer
2. To learn how to make a state machine
3. To become familiar with different state machine style
4. To understand K-maps and their usefulness
2 Instructions
Part 1: For this part of the assignment you will build your own register from the ground up.
• Implement your circuits in the “latches.sim” file
Part 2: Given a simple state diagram, you will build a state machine in CircuitSim using the “one-hot” style of building state machines.
• The circuit will be implemented in the “One-Hot FSM” subcircuit of the “fsm.sim” file
Part 3: Given the same state diagram from part 1, you will be minimizing the logic by using K-Maps.
• Fill out the K-Maps located in the spreadsheet named “kmap.xlsx”
• The reduced circuit will be implemented in the “Reduced FSM” subcircuit of the “fsm.sim” file
Do not change/delete any of the input/output pins.
2.1 Part 1
For this part of the assignment you will build your own register from the ground up. For more information about each subcircuit refer to your textbook.
2.1.1 RS Latch
You will start by building a RS latch using NAND gates, as described in your textbook. RS Latch is the basic circuit for sequential logic. It stores one bit of information, and it has 3 important states:
1. R=1 S=1 : This is called the Quiescent State. In this state the latch is storing a value, and nothing is trying to change that value.
2. R=1 S=0 : By changing momentarily from the Quiescent State to this state, the value of the latch is changed so that it now stores a 1.
3. R=0 S=1 : By changing momentarily from the Quiescent State to this state, the value of the latch is changed so that it now stores a 0.
Once you set the bit you wish to store, change back to the Quiescent State to keep that value stored. Notice that the circuit has two output pins; one is the bit the latch is currently storing, and the other is the opposite of that bit.
Note: In order for the RS Latch to work properly, you must not set both R and S to 0 at the same time.

• Build your circuit in the “RS Latch” subcircuit in the “latches.sim” file
2.1.2 Gated D Latch
Using your RS latch subcircuit, implement a Gated D Latch as described on the textbook. The Gated D Latch is made up of an RS Latch as well as two additional gates that serve as a control. With that addition not only can we control what value is stored by the latch, but also when that value will be saved. The value of the output can only be changed when Write Enable is set to 1. Notice that the Gated D Latch subcircuit only has one output pin, so you should disregard the inverse output of your RS Latch.
• Implement this circuit in the “Gated D Latch” subcircuit in the “latches.sim” file
• You are not allowed to use the built-in SR Flip-Flop in CircuitSim to build this circuit

2.1.3 D Flip-Flop
Using the Gated D Latch circuit you built, create a D Flip-Flop. A D Flip-Flop is composed of two Gated D Latches back to back, and it implements edge triggered logic. Your D Flip-Flop output should be able to change on the rising edge, which means that the state of the D Flip-Flop should only be able to change at the exact instant the clock goes from 0 to 1.

• Implement this circuit in the “D Flip-Flop” subcircuit in the “latches.sim” file.
2.1.4 Register
Using the D Flip-Flop you just created, build a 4-bit Register. Your register should also use edge-triggered logic. The value of the register should change on the rising edge.

• This circuit will be implemented in the “Register” subcircuit in the “latches.sim” file
2.2 Part 2
For this part of the assignment you are given the state machine transition diagram of a new computer that is currently in the early stages of production. It works very similarly to the personal computers we are used to, the only difference is that it has a physical Reboot button that also performs the same functions as the F12 key (so pressing it can be used to reboot the computer or to access the BIOS depending on the current state of the computer). We are gonna name that input button G. This computer has four outputs (A, B, C, D) that are turned on depending on the current state (see diagram).

• You will be implementing this state transition diagram as a circuit using the one-hot style. Remember for one-hot you will have a register with the number of bits being the number of states of the FSM. Each bit corresponds to a state, and you are in that state if the corresponding bit is a 1. Since you can only be in one state at a time, exactly one of the bits can be 1 at each time (except when the machine starts up, when all the bits will be 0).
• You must implement this using one-hot. A template file fsm.sim has been given to you. Implement the state machine in the provided “one-hot state machine” subcircuit.
• Note that there are 3 inputs to the “one-hot state machine” subcircuit: CLK, G, and RST. The CLK input turning off and on repeatedly will be used to represent clock ticks in your circuit. The G input corresponds to whether or not G is on, as in the diagram above. RST resets the circuit (clears all the bits of your state register).
2.3 Part 3
Take a look at this state machine transition diagram. Again, this state machine represents a hypothetical computer in which the input G represents both a reboot button and the F12 key. The outputs A,B,C,D represent different hardware elements of the computer (Ex. Output B represents the computer screen, and it is on whenever B is true).

• First, produce the k-maps for the state diagram above on the provided spreadsheet named “kmap.xlsx”. Use the k-maps to produce the reduced boolean expressions for the state machine.
The inputs for the k-map are:
– S0 = Current State least significant bit
– S1 = Current State most significant bit
– G = Input button
The outputs for the k-maps are:
– N0 = Next State least significant bit
– N1 = Next State most significant bit
– A,B,C,D
– You will fill out one K-map per output and one per next state bit for a total of 6 K-maps (N1, N0, A, B, C, D). The respective K-maps are located in the kmap.xlsx file.
– Your K-map must give the BEST minimization possible to receive full credit. This means you must select the BEST values for the don’t cares in your K-maps to do this.
– IMPORTANT:The k-maps are gonna be autograded, and because of that there are a set of restrictions to how you must fill your k-maps to ensure you get full credit:
∗ When you fill the row and column headers for your k-maps you must only use the following variable names: S0, S1, G. They must be capitalized and have no space between them. To negate a variable you must use an apostrophe. Example: S00G
∗ When writing the boolean expresions resulted from your k-map groupings, you must use the same rules as the previous bullet point, but also use ”+” for OR with no spaces between and no space between variable for AND. Example: S0’+S1G
∗ When filling the cells of your k-map, you can use 0, 1, and x (lower case only).
• Implement this circuit in the “reduced state machine” subcircuit of the provided fsm.sim file. You will lose points if your circuit does not correspond to your K-map or if your circuit is not minimal. You should use only the minimal components possible to implement the state machine.
• HINT: We recommend you make a truth table for the state machine to help organize the logic, and then transfer it to the k-maps. We’ve provided truthtable.xlsx to help with this.
Note: you do not need to submit truthtable.xlsx anywhere, it’s just for your use in helping make K-maps.
3 Testing
To test your circuits locally, navigate to the directory with the latches.sim and fsm.sim files and run the tester jar file via
java -jar hw03-tester.jar
Make sure to run the local tester on Docker.
To test your K-maps, please submit your kmap.xlsx to the Homework 3 K-maps assignment on Gradescope.
4 Deliverables
You will need to submit latches.sim, fsm.sim, and kmaps.xlsx to the Homework 3 assignment on Gradescope. The sim files and the kmaps will be autograded on gradescope.
5 Rules and Regulations
5.1 General Rules
1. Starting with the assembly homeworks, any code you write must be meaningfully commented. You should comment your code in terms of the algorithm you are implementing; we all know what each line of code does.
3. Please read the assignment in its entirety before asking questions.
5. If you find any problems with the assignment it would be greatly appreciated if you reported them to the author (which can be found at the top of the assignment). Announcements will be posted if the assignment changes.
5.2 Submission Conventions
1. All files you submit for assignments in this course should have your name at the top of the file as a comment for any source code file, and somewhere in the file, near the top, for other files unless otherwise noted.
3. Do not submit compiled files, that is .class files for Java code and .o files for C code. Only submit the files we ask for in the assignment.
4. Do not submit links to files. The autograder does not understand it, and we will not manually grade assignments submitted this way as it is easy to change the files after the submission period ends.
5.3 Submission Guidelines
2. You are also responsible for ensuring that what you turned in is what you meant to turn in. After submitting you should be sure to download your submission into a brand new folder and test if it works. No excuses if you submit the wrong files, what you turn in is what we grade. In addition, your assignment must be turned in via Canvas/Gradescope. Under no circumstances whatsoever we will accept any email submission of an assignment. Note: if you were granted an extension you will still turn in the assignment over Canvas/Gradescope.
5.4 Syllabus Excerpt on Academic Misconduct
Academic misconduct is taken very seriously in this class. Quizzes, timed labs and the final examination are individual work.
Homework assignments are collaborative, In addition many if not all homework assignments will be evaluated via demo or code review. During this evaluation, you will be expected to be able to explain every aspect of your submission. Homework assignments will also be examined using computer programs to find evidence of unauthorized collaboration.
You are expressly forbidden to supply a copy of your homework to another student via electronic means. This includes simply e-mailing it to them so they can look at it. If you supply an electronic copy of your homework to another student and they are charged with copying, you will also be charged. This includes storing your code on any site which would allow other parties to obtain your code such as but not limited to public repositories (Github), pastebin, etc. If you would like to use version control, use github.gatech.edu
5.5 Is collaboration allowed?

Figure 1: Collaboration rules, explained colorfully