Submission: Sequential Circuits

Discussion in 'Feedback and Suggestions' started by Georacer, Oct 18, 2010.

  1. Georacer

    Thread Starter Moderator

    Nov 25, 2009
    5,142
    1,266
    Finite State Machines

    Up to now, every circuit that was presented was a combinatorial circuit. That means that its output was dependent only by its current inputs. Previous inputs of that type of circuits have no effect on the output.

    However, there are many applications where there is a need for our circuits to have "memory"; to remember previous inputs and calculate their outputs according to them. A circuit whose output depends not only on the present input but also on the history of the input is called sequential circuit.

    In this section we will learn how to design and build such sequential circuits. In order to see how this procedure works, we will use an example, on which we will study our topic.

    So let's suppose we have a digital quiz game that works on a clock and reads an input from a manual button. However, we want the switch to transmit only one HIGH pulse to the circuit. If we hook the button directly on the game circuit it will transmit HIGH for as few clock cycles as our finger can achieve. On a common clock frequency our finger can never be fast enough.

    The desing procedure has specific steps that must be followed in order to get the work done:

    Step 1
    The first step of the design procedure is to define with simple but clear words what we want our circuit to do:
    "Our mission is to design a secondary circuit that will transmit a HIGH pulse with duration of only one cycle when the manual button is pressed, and won't transmit another pulse until the button is depressed and pressed again."

    Step 2
    The next step is to design a State Diagram. This is a diagram that is made from circles and arrows and describes visually the operation of our circuit. In mathematic terms, this diagram that describes the operation of our sequential circuit is a Finite State Machine.

    The State Diagram of our circuit is the following:

    [​IMG]
    Figure 1: A State Diagram

    Every circle represents a "state", a well-defined condition that our machine can be found at.
    In the upper half of the circle we describe that condition. The description helps us remember what our circuit is supposed to do at that condition.
    • The first circle is the "stand-by" condition. This is where our circuit starts from and where it waits for another button press.
    • The second circle is the condition where the button is just pressed and our circuit needs to transmit a HIGH pulse.
    • The third circle is the condition where our circuit waits for the button to be depressed before it returns to the "stand-by" condition.
    In the lower part of the circle is the output of our circuit. If we want our circuit to transmit a HIGH on a specific state, we put a 1 on that state. Ohterwise we put a 0.

    Every arrow represents a "transition" from one state to another. A transition happens once every clock cycle. Depending on the current Input, we may go to a different state each time. Notice the number in the middle of every arrow. This is the current Input.
    For example, when we are in the "Initial-Stan by" state and we "read" a 1, the diagram tells us that we have to go to the "Activate Pulse" state. If we read a 0 we must stay on the "Initial-Stand by" state.

    So, what does our "Machine" do exactly? It starts from the "Initial - Stand by" state and waits until a 1 is read at the Input. Then it goes to the "Activate Pulse" state and transmits a HIGH pulse on its output. If the button keeps being pressed, the circuit goes to the third state, the "Wait Loop". There it waits until the button is depressed (Input goes 0) while transmitting a LOW on the output. Then it's all over again!

    This is possibly the most difficult part of the design procedure, because it cannot be described by simple steps. It takes exprerience and a bit of sharp thinking in order to set up a State Diagram, but the rest is just a set of predetermined steps.

    Step 3
    Next, we replace the words that describe the different states of the diagram with binary numbers. We start the enumeration from 0 which is assigned always on the initial state. We then continue the enumeration with any state we like, until all states have their number.

    The result looks something like this:

    [​IMG]
    Figure 2: A State Diagram with Coded States

    Step 4
    Afterwards, we fill the State Table. This table has a very specific form. I will give the table of our example and use it to explain how will fill it in.

    [​IMG]
    Figure 3: A State Table

    The first columns are as many as the bits of the highest number we assigned the State Diagram. If we had 5 states, we would have used up to the number 100, which means we would use 3 columns. For our example, we used up to the number 10, so only 2 columns will be needed. These columns describe the Current State of our circuit.
    To the right of the Current State columns we write the Input Columns. These will be as many as our Input variables. Our example has only one Input.
    Next, we write the Next State Columns. These are as many as the Current State columns.
    Finally, we write the Outputs Columns. These are as many as our outputs. Our example has only one output. In this example, the output is dependant only on the current states. This is the reason the outputs column has two 1: to result in an output Boolean function that is independant of input I. Keep on reading for further details.

    The Current State and Input columns are the Inputs of our table. We fill them in with all the binary numbers from 0 to 2^{\text{(Number of Current State columns + Number of Input columns})}-1.
    It is simpler than it sounds fortunately. Usually there will be more rows than the actual States we have created in the State Diagram, but that's ok.

    Each row of the Next State columns is filled as follows: We fill it in with the state that we reach when, in the State Diagram, from the Current State of the same row we follow the Input of the same row. If we get to a row whose Current State number doesn't correspond to any actual State in the State Diagram we fill it with Don't Care terms (X). After all, we don't care where we can go from a State that doesn't exist. We wouldn't be there in the first place! Again it is simpler than it sounds.

    The outputs column is filled by the output of the corresponding Current State in the State Diagram.

    The State Table is complete! It describes the behaviour of our circuit as fully as the State Diagram does.

    Step 5a
    The next step is to take that theoretical "Machine" and implement it in a circuit. Most often than not, this implementation involves Flip Flops. This guide is dedicated to this kind of implementation and will describe the procedure for both D - Flip Flops as well as JK - Flip Flops. T - Flip Flops will not be included as they are too similar to the two previous cases.

    The selection of the Flip Flop to use is arbitrary and usually is determined by cost factors. The best choice is to perform both analysis and decide which type of Flip Flop results in minimum number of logic gates and lesser cost.

    First we will examine how we implement our "Machine" with D-Flip Flops.

    We will need as many D - Flip Flops as the State columns, 2 in our example. For every Flip Flop we will add one one more column in our State table with the name of the Flip Flop's input, "D" for this case. The column that corresponds to each Flip Flop describes what input we must give the Flip Flop in order to go from the Current State to the Next State. For the D - Flip Flop this is easy: The necessary input is equal to the Next State. In the rows that contain X's we fill X's in this column as well.

    [​IMG]
    Figure 4: A State Table with D - Flip Flop Excitations

    Step 5b
    We can do the same steps with JK - Flip Flops. There are some differences however. A JK - Flip Flop has two inputs, therefore we need to add two columns for each Flip Flop. The content of each cell is dictated by the JK's excitation table:

    JK - Flip Flop Excitation Table
     \begin{array}{|c|c||c|c|} \hline\\<br />
Q_\ & Q_{next} & J & K\\<br />
\hline\\<br />
\hline<br />
0 & 0 & 0 & X\\<br />
\hline<br />
0 & 1 & 1 & X\\<br />
\hline<br />
1 & 0 & X & 1 \\<br />
\hline<br />
1 & 1 & X & 0\\<br />
\hline<br />
\end{array}

    This table says that if we want to go from State Q to State Q_{next} we need to use the specific input for each terminal. For example, to go from 0 to 1, we need to feed J with 1 and we don't care wich input we feed to terminal K.

    [​IMG]
    Figure 5: A State Table with JK - Flip Flop Excitations

    Step 6
    We are in the final stage of our procedure. What remains, is to determine the Boolean functions that determine the inputs of our Flip Flops and the Output. We will extract one Boolean funtion for each Flip Flop input we have. This can be done with a Karnaugh Map. The input variables of this map are the Current State variables as well as the Inputs.
    That said, the input functions for our D - Flip Flops are the following:

    [​IMG]
    Figure 6: Karnaugh Maps for the D - Flip Flop Inputs

    D_A=A \cdot I + B \cdot I=(A+B) \cdot I\\<br />
D_B=\bar{A} \cdot \bar B \cdot I
     
    Last edited: Oct 29, 2010
  2. Georacer

    Thread Starter Moderator

    Nov 25, 2009
    5,142
    1,266
    <Stash Point>
     
    Last edited: Oct 18, 2010
  3. Georacer

    Thread Starter Moderator

    Nov 25, 2009
    5,142
    1,266
    <Stash Point 2>
     
    Last edited: Oct 18, 2010
  4. Georacer

    Thread Starter Moderator

    Nov 25, 2009
    5,142
    1,266
    If we chose to use JK - Flip Flops our functions would be the following:

    [​IMG]
    [​IMG]
    Figure 7: Karnaugh Map for the JK - Flip Flop Inputs

    J_A=B \cdot I\\<br />
K_A=\bar{I}\\<br />
J_B=\bar{A} \cdot I\\<br />
K_B=1

    A Karnaugh Map will be used to determine the function of the Output as well:

    [​IMG]
    Figure 8: Karnaugh Map for the Output variable Y

    Y=\bar{A} \cdot B


    Step 7
    We design our circuit. We place the Flip Flops and use logic gates to form the Boolean functions that we calculated. The gates take input from the output of the Flip Flops and the Input of the circuit. Don't forget to connect the clock to the Flip Flops!

    The D - Flip Flop version:

    [​IMG]
    Figure 9: The completed D - Flip Flop Sequential Circuit

    The JK - Flip Flop version:

    [​IMG]
    Figure 10: The completed JK - Flip Flop Sequential Circuit


    This is it! We have successfully designed and constructed a Sequential Circuit. At first it might seem a daunting task, but after practice and repetition the procedure will become trivial. Sequential Circuits can come in handy as control parts of bigger circuits and can perform any sequential logic task that we can think of. The sky is the limit! (or the circuit board, at least)


    • REVIEW:
    • A Sequential Logic function has a "memory" feature and takes into account past inputs in order to decide on the output.
    • The Finite State Machine is an abstract mathematical model of a sequential logic function. It has finite inputs, outputs and number of states.
    • FSMs are implemented in real-life circuits through the use of Flip Flops
    • The implementation procedure needs a specific order of steps (algorithm), in order to be carried out.

    Bibliography:
    C.L. Liu, Elements of Discrete Mathematics, 2nd Edition
    M. Morris Mano, Digital Design, 3rd Edition
    en.wikipedia.org/wiki/Sequential_circuit
    en.wikipedia.org/wiki/JK_flip_flop#JK_flip-flop
     
    Last edited: Oct 19, 2010
  5. Georacer

    Thread Starter Moderator

    Nov 25, 2009
    5,142
    1,266
    The submission is ready for proofreading!

    I will take a break after 6 hours of continous writting and editting. In the to-do list:
    Make the circuits black and white
    Add bridges over wire crossing on the circuits

    Awaiting corrections.

    Should this reach the e-book I will make sure to upgrade it to AAC standards, concerning Image and Circuit, as well as Text format.
     
    Last edited: Oct 18, 2010
  6. Wendy

    Moderator

    Mar 24, 2008
    20,766
    2,536
    Just did a quick scan, looks good. I'll read a bit more in depth when I'm feeling better.

    Dennis tends to move stuff where he will, but do you have a slot you think it needs to be put in?
     
  7. Georacer

    Thread Starter Moderator

    Nov 25, 2009
    5,142
    1,266
    I think it fits best in the Digital Volume, after or before the Counters. Might as well merge with them in a Chapter named Sequential Circuits. Counters are sequential circuits after all.
     
  8. Wendy

    Moderator

    Mar 24, 2008
    20,766
    2,536
    Pick a title, it will need added to the 1st post.
     
  9. Georacer

    Thread Starter Moderator

    Nov 25, 2009
    5,142
    1,266
    Title modified - First post has the title of my choice.
     
  10. Wendy

    Moderator

    Mar 24, 2008
    20,766
    2,536
    OK, but it will need to be part of the text similar to how I've done it. Look at the book to see what I mean.
     
  11. Georacer

    Thread Starter Moderator

    Nov 25, 2009
    5,142
    1,266
    Is that more like it? I understand still little of the e-book standards and regulations, so please, correct me as many times as it takes.
     
  12. Wendy

    Moderator

    Mar 24, 2008
    20,766
    2,536
    When I set out to start writing, I looked to see what was out there in the book already, then did my best to imitate it. I've gotten better, but ultimately Dennis has the say on formatting. I try to save him as much effort as I can though, especially in packing the articles.

    Things I thought were good weren't, and some stuff slipped by. I have examples of SubML packed files for most of my stuff, I hang it out there for all to see. If you're user status isn't updated soon I'll email some of the files you will need. Please PM me your email address.

    Couple of minor points, I don't think there is anything wrong with color, and we're going to have to figure out how to do Q not in SubML (it has the feature).

    Something like BB code Q...\overline Q
     
    Last edited: Oct 19, 2010
  13. Georacer

    Thread Starter Moderator

    Nov 25, 2009
    5,142
    1,266
    Doesn't SubML support LaTex? Oh, dear, my day just got worse...

    I 'll try once more to make a title, hope I get what you want to pass over this time...

    edit: I hope I interpreted correctly your comment as "put a big blue title over the text, you dumb @@$!". I don't know how I didn't see that earlier. I just couldn't dial in the exact tone of blue that the other titles have on the e-book. I don't think there is the right one on the 25-colour palette available on post editor...

    Isn't the "mail me" option showing up on my user page?

    I bumped onto this page (http://www.allaboutcircuits.com/l_tutorial.html) and got reading it. It generated some questions:

    • What is the final format of the file I have to submit? Will the text of this thread do or I have to write in SubML? If the latter is valid, does that mean a simple .txt file or something else?
    • Is there the possibility to partially translate the SubML text to LaTex for the sake of mathematical formulas and tables? If not, how will I incorporate those features on the text?
    • Do the images have to be packed in a file folder and that on a .zip file and sent somewhere? If so, where to?
    The more information I have the merrier.

    I would like to thank AAC for giving me a chance to help the site in a significant manner and especially Bill_Mardsen for his patience while coaching my first submission effort.
     
    Last edited: Oct 19, 2010
  14. Georacer

    Thread Starter Moderator

    Nov 25, 2009
    5,142
    1,266
  15. Wendy

    Moderator

    Mar 24, 2008
    20,766
    2,536
    That was an early version, there is a later one for the same article. Part of my learning process I would like to spare you.

    You will see several PMs.
     
  16. Georacer

    Thread Starter Moderator

    Nov 25, 2009
    5,142
    1,266
    Okay, converted it to SubML and Htm. I upload my work. I 'd like some comments before I send it to Dcrunkilton.

    I don't seem to like SubML much, the AAC forum editor is much better in my opinion.

    My primary concern for now is that I can't add a new line character (enter). I resort to creating a new paragraph which spaces the two lines and makes the text incoherent. Does anybody know a solution?

    Update Log:

    • Fixed the spacing between sections
    • Fixed the quotation on Step 1. <quotation> command seems to need a special format to be accepted. Used <italic>.
     
    Last edited: Oct 29, 2010
  17. Wendy

    Moderator

    Mar 24, 2008
    20,766
    2,536
    There is a command called <bigspace>. I have to go through this almost every time, it is not very intuitive.

    You already know this page...

    http://www.allaboutcircuits.com/l_contribute.html

    I have it bookmarked. I also access these two more or less regularly.

    http://www.ibiblio.org/kuphaldt/electricCircuits/Devel/tutorial.sml

    http://www.allaboutcircuits.com/l_tutorial.html

    You'll note another site popped up, ibiblio.org. It is the true home of the book, this site is there to help modify it. I also have this site bookmarked.

    http://www.openbookproject.net//electricCircuits/

    Which yet another site for the book. The primary one, as near as I can tell.

    Historically there is a certain disconnect between all these sites. The common threads are Dennis Crunkilton (editor) and Tony R. Kuphaldt (original author). Jrap does a really good job of taking care of the background stuff here, which includes grabbing the book files where ever they are and updating the sites version of the ebook. Occasionally you will see updates that aren't on all the sites, a quick note will take care of it.

    The characters I really miss are ¼, ½, ¾. They didn't make the transition in SubML. Characters I wish existed (but don't) are 1/3 and 2/3, since they are key to 555 circuits.
     
    Last edited: Oct 21, 2010
  18. Dcrunkilton

    E-book Co-ordinator

    Jul 31, 2004
    416
    11
    Thanks Georacer,

    I have downloaded the finite State Machines material. I will work on inegrating it into the Digital Volume.

    Dennis Crunkilton
     
Loading...