This month we look at Sequential Logic, where the logic decisions we make results in changes to the output/s when different combinations on the inputs occur.
Logic doesn’t have to be something that simply gives a pre-defined output based upon a combination of inputs. Logic is intended to use that ‘Combination Logic’ progress to take another step, and yet another, and so on in a sequence of events. This is known as Sequential Logic.
In the past two issues, we have looked at the options we have for logic gates; AND, OR, NAND, NOR, XOR and NOT, and combined these building blocks into combinations of logic gates to perform more complex logic. We have even touched on the maths that can be used to engineer the technology. All of the circuits thus far have been Static logic in that the outputs depend purely on the combination of inputs, and the result will always be the same.
SEQUENTIAL LOGIC
Our next step is the world of Sequential Logic, where the logic decisions we make with combinations of gates results in changes to the output/s that may be held until another of the sometimes many possible combinations occurs.
We will begin with a simple de-bounced switch, to show the concept, and progress through various types of Flip-Flops used for building Counters, Latches, Registers, and more...
SEQUENTIAL LOGIC CIRCUIT DEFINITION
A Sequential Logic circuit is one that includes a Memory, sometimes known as a Latch. Anybody who has worked around machinery will have seen a “Start-Stop Station” combination switch. The start button causes an electric relay to turn on, that uses a set of contacts controlled by the relay to bypass the start button. (i.e. In parallel with the start button). Therefore, the relay remains on after the start button is released. The stop button is in series with the relay coil, so pressing that button breaks the circuit and the relay opens, also opening the “Hold In” contacts. This is an example of both Sequential Logic, and Relay Logic and the diagram below also shows an an “Overload Contact” as an extra combination logic element.
Makers might like to think about using such a circuit in a bench power supply, or even on a 3D printer or CNC router with a start button and a stop button, but adding safety through an emergency stop, and overcurrent cut-out, all logically designed, of course!
TRIGGERS AND TIMING
Events are triggered by many possibilities, including Event/Pulse/Clock/Reset inputs.
The common ‘Computer Reset’, for example, typically uses a logic ‘Low’ state to cause everything in the logic circuit to start in an expected logic state. To accomplish this, a resistor and capacitor are placed in series across the supply with the capacitor connected to ground. When the internal power supply is applied, the capacitor is initially uncharged and therefore shows as a dead short, but charges to the power supply voltage as current enters via the resistor until the capacitor behaves like an open circuit. The voltage across the capacitor is the ‘Reset’ control, connected to the reset on the CPU to hold operations until the supply voltage is high enough, or to reset old technology computers with bad operating systems.
Other pulses or trigger events can be from various inputs such as push buttons, micro switches, and any number of compatible sensors. Soon we will look at one type of sequential circuit to ‘de-bounce’ these inputs, to make them suitable to a logic environment.
SYNCHRONOUS/ASYNCHRONOUS
The Sequential Logic circuit can be Asynchronous, as the start-stop station example would be, or Synchronous requiring every event to be synchronised. The reasons for synchronous operation are many, but computers use a synchronising clock pulse to make sure that the memory is available exactly when the CPU asks for it, and every other task of course.
CLOCK GENERATION
As a clock is a simple square wave, the clock pulse may in some circuits be as simple as a push button. The Z80 computer, for example, can be clocked that way, allowing students of computing to ‘Single Step’ the CPU and then look to see what happened, cycle by cycle. Most clocks are however of a fixed frequency, controlled by an oscillator. Logic requires a square wave and therefore a square wave oscillator must be used. That can be from an LM555 IC through to a VCXO – Voltage Controlled Crystal Oscillator or anything between. We can go into square wave oscillators another time.
EDGE TRIGGERING
Circuits clocked by logic levels can be an issue as speed increases. Synchronous logic circuits often utilise edge triggering rather than logic level triggering, as timing is more accurate when based on the very fast transition from low to high or high to low. Computers often use both edges of the square wave; the first transition to ‘Set’ the address of the data, for example, and the second to fetch the data. We use a circuit in this article that shows one method of implementing edge triggering.
DE-BOUNCED SWITCH
When a switch with mechanical contacts is closed, the actual contacts may bounce resulting in multiple “on-off” transitions and therefore voltage levels. This is not an issue with relay circuits, normally, but computers run so fast and logic circuits also switch so fast they can literally turn a load on and off several times, or worse still count the switch action several times more than is intended.
Computers can be programmed to ignore switch-bounce, but logic circuits need a certain and single ‘on-off’ for a switching action. The circuit below shows two simple methods, a capacitive time constant, and two sequential logic circuits to overcome the bounce.
For the first, a capacitor is placed in parallel with the switch, and a resistor is placed to the opposite rail, +ve or -ve depending on the logic of the switch action. When the button is pressed the capacitor is shorted and therefore discharged. Any bounced contacts cannot re-charge the capacitor fast enough to give a false logic pulse. When the switch is released, the capacitor re-charges to rail voltage at a rate determined by the time constant (RC).
The second uses two inverters in series, switched between two points in the loop, one the inverse of the other. De-bouncing is accomplished because the switch is a two way switch, and therefore contact bouncing does not re-make the other switched position.
The circuit above uses two NAND gates and a circuit we are about to explain in detail.
SCHMIDT TRIGGER
One type of buffer or inverter, and even other gates and inputs to other devices is called a Schmidt Trigger. The Schmidt Trigger is not a different kind of logic device, but a different kind of logic level input. The Schmidt Trigger circuit is designed to switch very fast, both on and off (in turn), but also to turn on at an input voltage higher than that required to turn it off.
Therefore, a slowly changing input, perhaps with some voltage jitter on the line, will turn on at perhaps 2.7V, and not turn off again until the input voltage goes below 1.8V, for example. The action is called ‘Hysteresis’, resulting in the symbol shown within the inverter logic shown in the de-bounce circuit above as De-bounce circuits typically use Schmidt Trigger logic.
MULTIVIBRATORS AND FLIP-FLOPS
The term multivibrator normally refers to analogue circuits that create pulses (Monostable Multivibrators), oscillate in square waves (Astable Multivibrators), or simply toggle from one level to another (Bistable Multivibrators). All of these have long names and so it is maybe because of the 1960’s ‘Hippy Generation’ that the digital logic variety were named ‘Flip-Flops’.
SET-RESET FLIP-FLOP
The basic circuit of all Flip-Flops is called the Set-Reset (SR) Flip-Flop. In the simplest form, it requires two NAND gates as shown in the diagram below. The output Q is fed back to NAND 2, and the inverted Q output of NAND 2 (!Q) is fed back to NAND 1. The inputs to this simplest circuit are labelled as !S and !R (NOT S and NOT R) being the Set and Reset inputs that are using negative logic to operate. That means that both are normally high, but grounding !S causes a Set changing Q to logic ‘1’, and grounding !R causes a Reset changing Q to logic ‘0’.
To restate this, ignoring the initial states as they are impossible to know, when a logic 0 is applied on the !S input, NAND 1 changes state if necessary and Q becomes a logic 1, which is connected to NAND-2 causing NAND 2 to also change state causing !Q to go to logic ‘0’, and holds at that value. Nothing happens as !S is released as the logic does not change.
When !R is set to logic 0, exactly the same process takes place as detailed above (Replacing !S with !R and Q with !Q) because the circuit is symmetrical. Therefore !Q changes to logic ‘1’ and Q changes to logic ‘0’. The logic of !Q is always opposite to Q except for a slight period as the outputs change called the ‘Propagation Delay’. The two inputs, !S and !R, must never be active low at the same time, or the SR flip-flops will either ‘jam’ or oscillate at a high frequency.
GATED SR FLIP-FLOP
If two more NAND gates are added to the SR as shown below, two improvements occur. First, the Set and Reset inputs are inverted so they are logic 1 active instead of logic 0, (now ‘positive logic’) and second, another input may be used to help avoid the problem explained above. This input is sometimes called the ‘Enable’ input, (imaginatively!) or the Chip Enable (CE), or perhaps a ‘Clock’ input to synchronise a number of SR flip-flops, and other logic.
The S or R inputs must be high and remain high while the circuit is gated, and S and R must still not intentionally be selected together or the output will be random, but at least the circuit won’t oscillate!
Although SR flip-flops are available (eg. 74LS259), the circuit block is more commonly one of the building blocks of other Flip-Flops, and other logic blocks, including Counters and Latches, yet to be discussed.
D-TYPE FLIP FLOP
By making one simple modification to the SR flip-flop, placing an inverter between the Set input and the reset input, thus ensuring that the two are never the same logic, during gating at least, the set input becomes a ‘Data’ input changing the flip-flop into a volatile memory element. Volatile simply means it loses it’s memory when power is removed.
Note: In the diagram below that we have built the whole circuit from NAND gates, although the first NAND is wired as an Inverter, and the whole circuit could alternatively be made from NOR gates or a collection of logic, or discrete transistors inside an IC.
The extra input could be an ‘enable’ or a ‘clock’, or in the case of a memory bit, might be labelled as ‘write’, ‘write enable’ or ‘write/read’ (w/r), a control input. With the 'write' pin remaining at logic '0' the output 'Q' will not change. However, whatever the logic state of input 'D' is when the 'write' pin is logic '1', will cause the NANDs to Flip-Flop to reflect the value of 'D' at the output 'Q'. Therefore, the 'Data' on 'D' is remembered at 'Q' until the next 'write' event.
One more change may be added to create an ‘Edge Triggered’ write, by adding another input to each NAND gate and three Inverters as shown below. The propagation delay of each of the inverters causes a small delay between the two inputs to the AND, resulting in a short pulse lasting only long enough to set or reset the memory.
Note: OCD’ers; in actual memory ICs the pin is typically labelled ‘R/’; read that as ‘Read / NOT Write’, and therefore requires appropriate logic internally.
TOGGLED-D FLIP FLOP
If the !Q output is connected directly to the ‘D’ input with no external connection to the ‘D’ input, then D will always be equal to NOT Q (!Q). The data input is NOT what the ‘Q’ output is. When the Toggle flip-flop is clocked at the ‘clk’ input, ‘w/r’ in the previous circuit, ‘Q’ will simply toggle on or off. This becomes useful in frequency dividers and counters we will look at later, as the square wave output is half of the input clock rate for the D-flip-flop. A sequence of 5 x D-Flip-Flops in series can divide a 32kHz square wave (typically the frequency used with watches) down to 1kHz.
JK FLIP FLOP
The JK flip-flop is sometimes referred to as the ‘Universal Programmable’ flip-flop as it can do all of the functions listed for the other flip-flops. The pins J and K are the initials of the guy that designed the circuit, “Jack Kilby”, and have no apparent meaning otherwise as initials for functions.
The JK flip-flop has the now common building block of all of the flip-flops, two NANDs in what is actually a ‘Bistable Multivibrator’ circuit. The Q output going to an input of the NAND with the !Q output, and vice versa. Two 3-input NANDs feed the SR inputs of the basic flip-flop, but they also have the ‘Extra’ input that we use as ‘Enable’, ‘Clock’ or ‘Write/Read’ which may be an edge-triggered input.
However, the JK flip-flop also has the outputs Q and !Q cross-connected to the input NANDs. What effect might that have on the operation of the circuit? Before reading on, those adventurous enough might like to make a truth table, and attempt to work it out yourself. Trust me! You may become frustrated at first, but it is quite achievable; as a measure of your superior intellect! Consider it as far easier than a Rubik’s Cube!
For those less adventurous, you still have to read my description! Let us begin by noting that nothing will happen unless we have three ‘true’ inputs to at least one of the 3-input NANDs, and that can only happen when the clock (‘clk’) pin is high. So the outputs will not change without a clock pulse. Therefore, we can ignore the ‘clk’ at all other times by assuming it is active when we need it to be.
Also, if J and K are both ‘false’ nothing will happen anyway.
So we are left with just three remaining scenarios of interest, J is ‘true’, K is ‘true’, or J and K are both ‘true’.
If J is ‘true’ and Q is ‘true’ then !Q is ‘false’, and NAND-1 will have a ‘true’ (inverted false) output when the clock pulses, so the output Q will remain ‘true’.
If J is ‘true’ and Q is ‘false’ then !Q is ‘true’, and NAND-1 will have a ‘false’ output when the clock pulses, so regardless of !Q, the output Q will change to ‘true’.
If K is ‘true’ and Q is ‘true’ then NAND-2 will have a ‘ false’ output when the clock pulses. !Q is ‘false’ so NAND-1 has a ‘true’ output and the output Q will change to ‘false’.
If K is ‘true’ and Q is ‘false’ then NAND-2 remains ‘true’ when the clock pulses, as does NAND-1. Therefore, with !Q being true, NAND-1 is gated off, so the output Q will remain 'false'.
If J and K are both ‘true’ then NAND-1 or NAND-2 will change depending upon whether Q is ‘true’ or ‘false’, i.e. whether Q is ‘true’ or !Q is ‘true’. If Q is ‘true’ then NAND-2 will change to ‘false’ causing NAND-4 to change to ‘true’ forcing NAND-3 to change Q to ‘false’.
If Q is ‘false’, !Q is ‘true’, then NAND-1 will change to ‘false’ causing NAND-3 to change to ‘true’ changing Q to ‘true’.
Therefore:
When J = K = ‘0’: Nothing changes.
When J = ‘1’ and K = ‘0’: Q is Set
When J = ‘0’ and K = ‘1’: Q is Reset
When J = K = ‘1’: Q (and !Q) toggle.
JK MASTER SLAVE
Logic circuits can suffer from an issue called ‘Race’; meaning that sequential logic can form an oscillator. Even if it is a burst oscillator, where some rapid data streams are faster than the propagation speed of the logic, and feedback in flip-flops can become fast enough to set the logic running off!
To avoid this, many flip-flop based devices use a ‘Master-Slave’ arrangement where one flip-flop; the ‘Master’ drives a second flip-flop; the ‘Slave’. The separation increases propagation time overall but prevents the ‘Race’ issue.
Circuits for Master-Slave devices can be drawn as two block symbols together, but in real circuits, many simplifications and preventative measures may be made within the actual IC. Therefore, the circuit shown below is an example of how the JK-MS Flip-Flop can be built from gates, not meaning to say that this is what is inside the IC.
IN SUMMARY
Once again, what we set out to discuss rapidly took up all of the space allocated. We have looked at Sequential Logic concepts, simple examples, asynchronous and synchronous logic, and some applications. Along the way, we looked at clocking, de-bouncing, edge-triggering, what Flip-Flops are, and looked at SR types, D types, Toggle types, and the JK type. Surely that’s enough for one classroom!
So how much more is there to Digital Logic? While we can never cover all of the subjects, there are many topics that are useful to makers intent on understanding digital logic.
Many of the topics get into the heart of computers whether as microcontrollers or microcomputers. Makers are more at home when the little black box they use has all of its workings inside it, but what is inside the IC will be doing pretty much the same work that the old Apollo AGC, (Apollo Guidance Computer), that took man to the moon almost 50 years ago. Making it the first truly "Portable Computer"!
The AGC was made almost entirely from some of the first Logic ICs, having inside the TO5 metal IC case a pair of three input NOR gates made from just 6 transistors.
The gates formed all of the logic of the Apollo computers, except the non-volatile memory, which was made from tiny toroidal magnets known as Memory Cores. No doubt you thought that the Core Memory meant something more than a bunch of tiny magnets!
The NOR gates also formed the computer calculator or "Arithmetic Logic Unit" (ALU), and what we have described thus far is most of what we need to make our own ALU.
Next month, we will look at latches/registers, including the 74xx595 and some of its mates, and the "Universal Shift Register" that can receive or transmit data in serial streams, or parallel data, and perform many of the CPU/ALU functions.
Part 1