Tutorials: Microcontroller systems (MICSY)

Sequential logic

last updated: 02/04/20

Introduction

Song of this chapter: Supertramp > Breakfast in America > The logical song

As seen we can split the logic up in time-independent logic where no memory is needed called the combinational logic and the sequential logic.

In sequential logic the output depends on the present input but also on the history of the input. Sequential logic has memory!.

Modern computing would not be possible without sequential logic (memory). Often circuits are a mixture of combinational and sequential logic.

We distinguish synchronous and asynchronous circuits in digital sequential logic. Synchronous circuits have a clock signal and the state of the device changes only if the clock signal changes. Asynchronous circuits respond to changing inputs.

Let's begin with the basic circuit named flip-flop. Flip-flops can be asynchronous (transparent, level triggered) or synchronous (clocked). Commonly the more simple asynchronous flip-flops are named latches. The synchronous flip-flops using a clock signal are named flip-flops.

Asynchronous circuits: Latches

In asynchronous sequential logic we don't find a clock signal. A changing level at an input triggers with a very short delay a reaction of an output level. The very short delay depends of the manufacturing process, the temperature, the complexity of the circuit etc. and is never equal for two circuits. If we combine two incoming signals and one signal comes slightly later than the other, the state the receiving circuit goes into will depend on which signal gets to the gate first. Depending on very small differences in the delays the circuit can go into the wrong state. This is called a race condition.

Asynchronous sequential logic can be faster than synchronous logic because it must not wait for the clock signal, but is used only in a few critical circuits relying on speed as small parts of microprocessors and digital signal processing circuits.

Asynchronous logic is difficult to design and problematic to use, so normally only synchronous circuits with clock signal are used in devices and computers. So why a chapter on latches? They provide the possibility to fill the gap between combinational logic and synchronous sequential logic. Latches are building blocks of sequential circuits. They are build from logic gates and they help to understand how synchronous circuits work.

SR-latch

The latch is a memory element. Memory can only be created with a feedback from the output to the input. The two inputs of the latch are named Set and Reset, thus SR-latch. Let's look at a very simple circuit to understand how it works, the SR-AND-OR-latch:

First we omit the feedback line and will successively change the states, keeping in mind, that the F input takes the state of the Q output (this is no normal truth table, but a time related table!).

`F`	`R`	\|	`S`	`Q`	remark
0	0	\|	0	0	`system idle` (at rest)
0	0	\|	`1`	`1`	`Set` S HIGH → output Q HIGH, F gets HIGH
`1`	0	\|	1	`1`	output Q stays HIGH
1	0	\|	`0`	`1`	`system idle`: Q stays HIGH even when S goes back to LOW (memory!)
1	`1`	\|	0	`0`	`Reset` R HIGH → output Q LOW, F gets LOW
`0`	1	\|	0	`0`	output Q stays LOW
0	`0`	\|	0	`0`	`system idle`: Q stays LOW even when R goes back to LOW (memory!)

As F = Q let's draw the feedback line:

If we look as our table we see that Q is HIGH if S OR (NOT R AND F) The Boolean formula for this circuit will be:

This circuit is for learning purpose, because real latches are not build from 3 different gates. Let's change the circuit to NOR only or NAND only gates:

Let's first replace the AND using the De Morgan law:

Now we can realize the SR-latch with two NOR gates, but we get an negated output. But let's look at the system idle states (R = S = 0) of the table above.

Both NOR gates have one input on 0. Remember the truth table of a NOR. If input B is 0 we see that input A is inverted.

`B`	`A`	\|	`Z`
`0`	`0`	\|	`1`
`0`	`1`	\|	`0`
`1`	`0`	\|	`0`
`1`	`1`	\|	`0`

Circuit SR-NOR-latch

Redrawing the circuit gives us the typical circuit of a SR-NOR-latch:

Circuit SR-NAND-latch

A similar circuit is the SR-NAND-latch. The NAND-latch is active-low meaning the inputs are inverted:

SR-latch truth table

`S`	`R`	\|	`Q`	state
`0`	`0`	\|	`0`	hold (memory)
`0`	`1`	\|	`0`	`reset`
`1`	`0`	\|	`1`	`set`
`1`	`1`	\|	`X`	not allowed

Case number 4 in the truth table is a forbidden case, because if both inputs are 1, both NOR's outputs are 0. But than Q can not be the same as NOT Q.

Symbols for SR-latches

"Just do it" SL1:

Find the circuit of the SR-NAND-latch beginning with an SR-AND-OR-latch, by replacing the OR using the De Morgans law. The steps are similar to the steps we took to get the SR-NOR-latch (draw 3 circuits by hand!).

"Just do it" SL2:

A problem in the real (not simulated) world is the contact bouncing of switches, relays and push-buttons. As the contacts of switches are made of springy metals, they bounce apart one or more times before settling to a steady contact. This happens in some micro- or milliseconds. Fast digital circuits or our Arduino program look interpret the inputs often more than once a microsecond and will thus detect multiple states for the switch instead of one state and react accordingly. Try to catch the bouncing of a switch with an oscilloscope.

Use the following program to count the bouncing of a switch. Document the output (Screenshot).

  // Count bouncing

  const byte PIN_IN = 1;
  bool old_value = HIGH;
  bool new_value;
  int count = 0;

  void setup() {
    Serial.begin(115200);
    delay(500);
    pinMode(PIN_IN,INPUT_PULLUP); // HIGH if switch not pressed
  }

  void loop() {
    Serial.println("Press the button now!");
    while (old_value == HIGH) { //switch not pressed, wait
      old_value = digitalRead(PIN_IN);
    }
    for (int i=0 ; i<1000; i++) {
      new_value = digitalRead(PIN_IN);
      if (new_value != old_value) {
        count++;
        old_value = new_value;
      }
    }
    Serial.print("Number of bounces: ");
    Serial.println(count/2);
    count = 0;
    while (old_value == LOW) { //switch pressed, wait
      old_value = digitalRead(PIN_IN);
    }
  }

The bouncing of switches can easily be corrected in a software program with a delay() and a subsequent control of the switch state. Another option is to resolve the problem with hardware. And here our NAND-latch comes handily. Build and document a debounce circuit with a single pole double-throw switch (SPDT) two external pull-up resistors (10k) and a NAND-latch. Test the circuit with the program from above (without internal pull-up!). Note your findings.

R or S dominant latches

As seen for the SR-latch we have two problems:

Case number 4 in the truth table is a forbidden case, because if both inputs are 1, both NOR's output 0. But than Q can not be the same as NOT Q.
If both inputs go to LOW simultaneously after the forbidden case we get a race condition. The output gets either 1 or 0 depending on the propagation time relations between the gates.

To solve the problems, we can add combinational logic gates to the inputs to convert the last case S = R = 1 to the first (memory), second (reset) or third case (set). The first possibility is called an E-latch and seldom used, the second possibility is an R dominated latch and the third possibility an S dominated latch.

"Just do it" SL3:

Find the logic gates to convert an SR-latch to an R dominated latch. Draw the circuit by hand, and document the truth table. Test the circuit on a breadboard.

An alternative would be to make the restricted combination toggle the output. This circuit is named a JK-latch (see JK-flip-flop).

Gated SR-latch

Latches are transparent, meaning that changes to the input signal cause immediate changes in output. With additional logic we can make it non-transparent when an "Enable" input (E) is not active. This can be done with two supplementary AND-gates to pass the inputs only if the enable signal is HIGH. A simple way is to use two NAND's with a NAND-latch:

Such a latch is named a gated SR-latch.

With E LOW the latch is closed (opaque) and remains in the state it was left the last time E was high. The gated SR-latch is level-sensitive to the level of the clock signal (most flip-flops are edge-sensitive to the clock), so we don't name the input clock but "Enable".

"Just do it" SL4:

Write the truth table of a gated SR-latch.
Expand the circuit to an R dominant gated SR-latch with only NAND's (draw the circuit by hand) and test the latch on a breadboard. Document the truth table.

Gated D latch

If the S input is HIGH, the R input is LOW and vice versa. By connecting the S input through an inverter to the R input, we eliminate one input and get a gated D-latch:

Symbol of the gated D-latch

Timing diagrams

Timing diagrams help to understand the behavior of sequential logic circuits.

"Just do it" SL5:

Write the truth table of a gated D-latch.
Complete the following timing diagram for an SR-latch, a gated SR latch, an S dominant gated SR-latch and a gated D-latch.

Gated D-latches can be found in the 74xx75 chip.

Synchronous circuits: Flip-flops

As already mentioned asynchronous logic is difficult to design and problematic to use. If there are changes in the data of a gated D-latch when the enable pulse is HIGH, the output Q changes in sympathy with D. It remembers only the last input state that occurred during the clock pulse. This effect is called ‘Ripple Through’, and is not a desirable property, because states are not really predictable. In programmed logic (CPLD, FPGA) we even don't find cells with gated latches. So normally only synchronous circuits with clock signal are used in devices and computers.

Flip-flops are the building blocks of sequential and synchronous circuits. They change their output only at times determined by the clock. Most flip-flops are edge triggered, meaning that the output changes when there is a change in the clock pulse.

Flip-flops have a clock signal and change the their output only when the clock signal changes.

A simple clock circuit could be build with a high pass filter as seen in ELEctronic FUndamentals.

Symbols of clocked flip-flops

Positive edge triggered flip-flops get a triangle in the symbol. Here the symbols for a D-FF with a positive edge triggered clock and a negative edge triggered clock:

"Just do it" SL6:

Complete the following timing diagram for a gated D-latch, a positive edge D-FF and a negative edge triggered D-FF.

The D-FF is simple and useful. Upon a clock edge (normally rising) the input is passed to the output. It's often used as basic element in programmable logic design.

D-FFs can be found in the 74xx74 chip (with an additional S and R input) or the 74xx174.

Register (wiki)

With D-FFs we are able to build our first register, the base memory element of a computer.

The data is memorised in the register only when the clock signal rises from 0 to 1. An 8 bit edge triggered D-FF register can be found in IC's like the 74xx374 or 74xx574.

Register can easily be enlarged to interesting other circuits with a little combinational logic like the following shift register.

Shift register (wiki)

We have seen the shift operators in Arduino. The same shifting can also easily be done in hardware.

We find shift registers with both parallel and serial inputs and outputs. Especially interesting are PISO (Parallel-In, Serial-Out) and SIPO (Serial-In, Parallel-Out) register, because they allow to convert a parallel stream to serial and back, a feature needed for serial bus interfaces like EIA232 and SPI. They also allow to multiply the output and input pins of our microcontroller.

Serial In Parallel Out (SIPO)

Each rising edge of the D-FF's reads the input and shifts the content 1 bit to the right as seen in the timing diagram. A problem is the changing of the value at the parallel output for each clock pulse. If we drive e.g. 4 relays at the parallel output, they will change clatter for each change. To avoid this behavior we add a normal register to the output.

After shifting for times (4x SRCLK), the rising edge of the register clock (RCLK) passes the shifted nibble to the output.

The SIPO is often used to get more output pins for our microcontroller circuits. One pin on our microcontroller can drive 8 or more (by combining the shift register) output pins.

"Just do it" SL7:

We want to drive 8 LED's with one pin. A handy chip for this is the 74xx595. What role plays the /OE-pin (explain what tristate means)?
Build and test the following circuit (add a photo). Explain in a short text what happens in the software (function shiftx8()) respectively in the SIPO-Chip (look at the time diagrams in the data sheet!).

In Arduino an integrated function named shiftOut() (look here), does quite the same thing than our shiftx8() function. Change the program and use the shiftOut()-function instead of shiftx8().

  // SIPO_75595.ino
  // /OE to GND

  const byte PIN_SER = 0;    // SER = serial in
  const byte PIN_RCLK = 1;   // RCLK = register clock (STORE, load)
  const byte PIN_SRCLK = 2;  // SRCLK = shift register CLK
  const byte PIN_SRCLR = 3;  // SRCLR = shift register clear = /RESET

  byte pattern[16] = {0xC0, 0x60, 0x30, 0x18, 0x24, 0x42, 0x81, 0x42,
                      0x24, 0x18, 0x0C, 0x06, 0x03, 0x06, 0x0C, 0x18 };

  byte sipo_byte, bit_to_shift, i, j;

  void setup() {
    pinMode(PIN_SER, OUTPUT);
    pinMode(PIN_SRCLK, OUTPUT);
    pinMode(PIN_RCLK, OUTPUT);
    pinMode(PIN_SRCLR, OUTPUT);
    digitalWrite(PIN_SRCLK, LOW);     // CLK = low
    digitalWrite(PIN_RCLK,LOW);       // STORE = low
    digitalWrite(PIN_SRCLR,HIGH);     // RESET = high (active low)
  }

  void loop() {
    for (j=0; j<16; j++) {
      sipo_byte = pattern[j];
      shiftx8(sipo_byte);
      delay(100);
    }
  }

  void shiftx8(byte sipo_byte) {
    for (i=0; i<8; i++) {
      bit_to_shift = sipo_byte & 0x80; // mask MSB
      if (bit_to_shift == 0) {
        digitalWrite(PIN_SER,LOW);     // data in
      }
      else {
        digitalWrite(PIN_SER,HIGH);
      }
      digitalWrite(PIN_SRCLK,HIGH);    // clock positive edge SRCLK
      digitalWrite(PIN_SRCLK,LOW);
      sipo_byte <<= 1;                 // left shift data byte
    }
    digitalWrite(PIN_RCLK,HIGH);       // store to register
    digitalWrite(PIN_RCLK,LOW);
  }

Parallel In Serial Out (PISO)

To load data parallel to our shift register we need multiplexer.

The first serial input (IN) is only needed if cascading POSI to bigger register. If LOAD is LOW, the input nibble is switched to the D-FF's inputs. After a CLK signal, the nibble is loaded into the FF's. Than LOAD can go to HIGH, so that the shift register can work, and the nibble can be shifted out.

"Just do it" SL8:

We want to read 8 switches with one pin and show the result as HEX byte with Serial.print() on our serial monitor. We will use the 74HC165. Use the following link as help: https://playground.arduino.cc/Code/ShiftRegSN74HC165N/. Tip: We can use the Arduino shiftIn() function.
Draw the circuit and write the program. Document the output.

Other interesting an important circuits that can be realised with flip-flops are FIFO and LIFO shift register, Counters (asynchrone, synchrone, modulo, ring), frequency divider (T-FF) etc..