Tutorials: Microcontroller systems (MICSY)

Combinational logic

last updated: 2022-05-09

Quick links to the subchapters

Introduction

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

We have seen in the first chapter, that digital circuits are often calculating (arithmetic) with numbers. A processor or micro-controller needs one or more Arithmetic logic units (ALU). Now let's look at the the logic part.

We can split the logic up in time-independent logic where no memory is needed called the combinational logic and the sequential logic, in which the output depends on the present input but also on the history of the input.

Combinational logic changes instantly, meaning the output of the circuit responds as soon as the input changes.

(Naturally there is a little delay because of the propagation of the signal through the circuit.)

Digital logic (Boolean algebra) (wiki)

Digital logic is based on Boolean (George Boole) algebra. The Boolean algebra is based on the truth values true and false (1 and 0). The main operations of Boolean algebra are the logical conjunction AND (∧), the logical disjunction OR (∨), and the logical negation NOT (¬).

Boolean algebra has been fundamental in the developing of digital electronics and thus all modern computer systems. It is a system of rules that allow to make extremely complicated decisions based on simple yes or no questions.

Digital logic is important in programming and provided for in all modern programming languages. Today circuits are often replaced with software in microcontroller.

Basic operations AND, OR, NOT

Truth tables help to quickly understand Boolean operations. :

    NOT  
A    Ā  
0 |  1 |
1 |  0 |


       AND    OR  
B A   A ∧ B   A ∨ B  
0 0 |   0 |   0 |
0 1 |   0 |   1 |
1 0 |   0 |   1 |
1 1 |   1 |   1 |


It is possible to to define the conjunction in terms of the negation and the disjunction, or to define the disjunction in terms of the negation and the conjunction. The corresponding rules are called De Morgan's laws:

boolean identities

So one basic operation with a NOT suffices to build all digital circuits.

We will see that the combination of the conjunction AND with the negation NOT gives one basic gate called NAND to be used as universal gate. The combination of OR with NOT gives a second universal gate called NOR.

Boolean laws:

boolean identities

Logic gates (wiki)

We have already build an AND-gate and OR-gate with diodes in chapter 7 of electronics fundamentals. Logic gates are devices implementing a Boolean function. They perform a logical operation on one or more binary inputs and produce one binary output. They can be constructed with diodes and transistors, but also with electromagnetic relays (relay logic), mechanical elements, molecules, fluidic logic, pneumatic logic, optics ....

Amplified logic gates can be cascaded and so allow the construction of physical models using all of the Boolean algorithms and mathematics. Thus are created circuits like multiplexers, registers, ALU's, computer memory an even complete microprocessors, which may contain more than 100 million gates.

Our simple diode logic gates from electronic fundamentals had no amplifying element. So we need transistors because they are capable of amplifying and can at the same time replace the diodes. Gates using bipolar transistors and resistors (resistor–transistor logic RTL) were used in early integrated circuits. After diodes in replacement for the resistors (diode–transistor logic DTL with higher speed and better density) bipolar transistors replaced the diodes for transistor–transistor logic (TTL). To reduce power consumption today gates are made from Complementary Metal–Oxide–Semiconductor (CMOS) field-effect transistor called MOSFET.

Prefabricated logic gates in integrated circuits, as the famous TTL 74xx series from Texas Instruments, simplified the life of the engineers.

Today these fixed-function logic gates are often replaced by programmable logic devices as Field-Programmable Gate Arrays (FPGA). With these, it is easily possible to change the logic design of a hardware system by reprogramming it. Even most of the controllers and processors of today are programmed into FPGA's (e.g. Cortex Processors from ARM).

Basic gates

To draw circuit diagrams, we need as in electronics standardized symbols. We will use DIN EN 60617-12 (IEC 60617-12:1997). Here the basic gates: AND, OR and NOT, and the also important gates NAND, NOR and XOR:

6 gates

"Just do it" CL1:

Arithmetic circuits

Half adder and full adder

Let’s do a little arithmetic using logic :) :

Do you remember the first 4 rules (truth table) of the binary addition? A circuit doing this calculations is called a half adder. It has two inputs and two outputs.

      Sum   Carry
S1 S2    S     C
 0  0 |  0 |   0
 0  1 |  1 |   0
 1  0 |  1 |   0
 1  1 |  0 |   1


For the sum we need an XOR-gate and for the carry an AND.

halfadder circuit

To get the Boole formula of a truth table we look at the cases where the output is 1. For these cases we make a conjunction (AND) of the inputs named a conjunction clause. We get the formula by a disjunction (OR) of these different clauses. The formula is called Disjunctive Normal Form (DNF) and is an OR of AND's.

Let’s try it on our half adder:

halfadder NAND

If we want to use NAND's we can transform our formulas. A double negation does not change the formula! The De Morgan’s law gives us our NAND gates:

halfadder NAND

halfadder NAND circuit

Though the found solution is not necessarily the solution with the fewest gates. By using the Boolean laws we can also find the following solution:

halfadder NAND

"Just do it" CL2:

To get circuits with a reduced number of gates we can use our intuition with the Boolean laws. An easier way are Karnaugh maps, a graphical method of simplifying Boolean algebra expressions. For big truth tables and more than 4 input variables the Karnaugh maps attain their limits. A similar method, the Quine–McCluskey algorithm can then be used. It is a tabulation method that makes it more efficient for use in computer algorithms.

To reduce formulas we can use today online tools like:

http://www.32x8.com/var3kmapn.html or
http://tma.main.jp/logic/index_en.html

"Just do it" CL3:
"Just do it" CL4:

Decoder circuits

We have already seen a decoder (in software) in our 7-segment display (SSD) example of the previous chapter. Naturally we could decode the SSD in hardware with logic gates. There exist actually complete SSD decoder in the he TTL 74xx series.

"Just do it" CL5:

Multiplexer and demultiplexer (wiki)

Often we need to chose one signal from more signals in a digital system. Here we see an analogy with rotary switches:

rotary mux demux

In digital electronics we use digital multiplexer and demultiplexer (mux and demux). They can easily be implemented with some basic gates. Beneath the inputs and one output for the multiplexer respectively one input and the outputs for the demultiplexer we need one or more control signals to choose the right input or output:

mux demux

Here is the truth table for a multiplexer 2 to 1:

C B A   Z
0 0 0 | 0
0 0 1 | 1
0 1 0 | 0
0 1 1 | 1
1 0 0 | 0
1 0 1 | 0
1 1 0 | 1
1 1 1 | 1

This truth table can be simplified intuitively even without using Boolean laws, because if C = 0, Z = A and if C = 1, Z = B:

C   Z
0 | A
1 | B


Using the disjunctive normal form we get:

formula mux

To demultiplex, we need only AND-gates to let pass the right signal and block the other signal with NOT's on the control line.

mux demux

"Just do it" CL6:

Logic levels (wiki)

Logic level are the voltages in which a signal can exist.

There are different logic families (e.g. DTL, TTL, CMOS) with varying logic levels.
As seen, binary 1 is referred to as a HIGH signal and a binary 0 is referred to as a LOW signal. The logic level voltages can be found in the data sheets. We distinguish:

TTL

One of the most used logic families is the Transistor-Transistor Logic TTL build with bipolar transistors and working with 5 V. The following logic levels apply for TTL:

ttl logic levels

The minimum input voltage level for a LOW signal VIL of a device is higher than the output voltage for LOW signal of a device VOL, because of possible noise adding to the signal. The maximum output voltage level for HIGH signal VOH is higher than the input voltage for HIGH signal of a device VIH, because of possible voltage losses on lengthy connection wires.

If the voltage lies in the floating zone, between VIL and VIH, we don't know if the chip decides for a HIGH or a LOW. The state can bounce arbitrarily between HIGH and LOW.

Arduino

The Arduino Uno uses an ATmega328 chip from ATMEL. Let's look at the ATmega328 data sheet. The typically supply voltage VCC is 5 V:

Arduino logic levels

The levels of Arduino make working with other hardware simpler because the invalid region of voltages is only between 1.5 V and 3.0 V. The noise margin is greater, as is the threshold for a LOW signal.

ESP8266 and ESP32 (3.3 V)

The ESP8266 and the ESP32 both work with 3.3 V, but there is a big difference between the chips! The ESP8266 is 5 V-tolerant means it will not be destroyed by 5 V on an input pin. This is not true for an ESP32.

An ESP32 will be destroyed by using voltages above 3.6V!

Here we must use a simple voltage divider or a logic level shifter to get 3.3 V from 5 V.

Logic level shifter

A simple bidirectional level shifter can be build with a transistor:

level shifter

This level shifter works good for frequencies up to 100 kHz and can be used for serial or I²C interfaces. It even exists as cheap breakout board for 4 signals.

If we need a level shifter for 3.3 V to 5 V working up to 1 MHz we can use an 74HCT125 chip. This chip provides 4 (unidirectional) level shifter. If we want e.g. to use NeoPixel LEDs with an ESP microcontroller this chip is a good solution, because the NeoPixel data line works with 800 kHz.

"Just do it" CL7:
Open collector (wiki)

Many gates and integrated circuits (IC) and also sensors have no voltage or current specified for their output. The output pin of these circuits is connected to the collector of an internal NPN transistor and called open collector. The transistor itself is wired as common emitter amplifier. The base terminal of the transistor is the input, the collector is the output, and the emitter is common to both. To get a functioning circuit we need to add a pull-up resistance going to VCC.

For a MOSFET such an output is called open drain.

open collector

As the pull-up resistor will be external, we can vary the current by the resistance and use another supply voltage than 3 V or 5 V!. Often open-collector transistors withstand higher voltage than the chip supply voltage, so that motors or relays van be driven.

Another advantage is that multiple open-collector outputs can be connected to a single line. When all outputs attached to the line are in an high-impedance state, the pull-up resistor holds the wire on HIGHlevel. If one or more devices outputs a LOW level (connection to ground) we get a LOW on the line. This allows shared buses like I²C.

Active-low and active-high

When working with IC's and microcontrollers, we see sometimes pins that are active-low.
The other "normal" pins are active-high, meaning they use the positive logic (activated with HIGH). For an active-low pin, we must pull that pin to LOW (ground) to activate the function (negative logic).

Often both active-low and active-high pins can be found on the same IC. The active-low pins have a NOT notation (line over pin description). For example, many IC's have a chip enable pin CE. If we find a line over CE then that pin is active-low and would need to be pulled to ground to enable the chip. With no line over CE, the pin is active high, and needs to be pulled to HIGH (VCC) to enable the chip.

active-low

Digital logic in programming

Very often programming is making decisions using Boolean logic: "if true, then do ...". So let's see how Boolean logic is used in programming.

Bitwise Logic

Our gates do their logic "bitwise". As we work with bytes the logic is applied on each single bit of our byte. The basic operators are:

Other interesting operators are:

Here some examples in Arduino and the corresponding output:

    // bitwise operations

    void setup() {
      byte a = 0b01100110;
      byte b = 0b10111010;
      Serial.begin(115200);
      delay(1000);
      Serial.println ("01100110 &     01100110 |   ~(01100110)");
      Serial.println ("10111010       10111010       -------- ");
      Serial.print   ("--------       --------       ");
      Serial.println (byte(~a),BIN);
      Serial.print   ("00");
      Serial.print   (a & b,BIN);
      Serial.print   ("       ");
      Serial.println (a | b,BIN);
      Serial.println ();
      Serial.println ("01100110 ^     01100110 >> 3  01100110 << 5");
      Serial.println ("10111010       --------       -------- ");
      Serial.print   ("--------       0000");
      Serial.print   (a >> 3,BIN);
      Serial.print   ("       ");
      Serial.println (byte(a << 5),BIN);
      Serial.println (a ^ b,BIN);
    }

    void loop() {}

Output:

    01100110 &     01100110 |   ~(01100110)
    10111010       10111010       --------
    --------       --------       10011001
    00100010       11111110

    01100110 ^     01100110 >> 3  01100110) << 5
    10111010       --------       --------
    --------       00001100       11000000
    11011100

We use some (dirty) tricks here to get a decent output. The NOT-operation and the "left-shift"-operation use more than one byte for their result, so we force the result in a byte with the byte() function. The BIN parameter of Serial.print() omits leading zeroes, so we adjust a little bit for this result. The right way would be to write a function to return the corrected string.

"Just do it (if you feel like it)":

Masking (wiki)

Masking is the voluntary setting of a bit or bits to 0 or 1 by using a bit-mask and a Boolean operation like AND, OR or XOR without changing the other bits of e.g a byte.

Masking with AND
A mask with AND sets bits to 0

An AND-operation with 0 sets the bit to 0!

 old
value		 AND mask   new
value
  0  &  0 =  0
  1  &  0 =  0

An AND-operation with 1 does not affect the state of a bit (new value = old value).

 old
value		 AND mask   new
value
  0  &  1 =  0
  1  &  1 =  1
Masking with OR
A mask with OR sets bits to 1

An OR-operation with 1 sets the bit to 1!

 old
value		 OR mask   new
value
  0 |  1 =  1
  1 |  1 =  1

An OR-operation with 0 does not affect the state of a bit (new value = old value).

 old
value		 OR mask   new
value
  0 |  0 =  0
  1 |  0 =  1
Masking with XOR
A mask with XOR toggles bits

An XOR-operation with 1 toggles the bit!

 old
value		 XOR mask   new
value
  0  ^  1 =  1
  1  ^  1 =  0

An XOR-operation with XOR does not affect the state of a bit (new value = old value).

 old
value		 XOR mask   new
value
  0  ^  0 =  0
  1  ^  0 =  1
Example: Masking SF-register in Arduino

As seen the Arduino Uno uses the ATmega328 (DIP) microcontroller. This controller has 23 programmable input/output pins (I/O, GPIO General Purpose Input Output). Often GPIO's are grouped to 8 pins forming one byte named a port. ATmega328 has two full 8-bit ports, portB and portD, and one portC with 6 usable digital pins PC0-PC5 (PC6 is needed for Reset). The pins can also be used as analog input ports, and have the Arduino notation A0-A5.

Arduino Uno circuit

If we use the pins for digital input or output, this is done inside our micro-controller with 3 Special-Function-registers (SFR) per port, sometimes named I/O-register.

Let's look at a simple setup from an Arduino program and do a little reverse engineering. We will use the Teensy 2.0 board because the code of the libraries is easier to understand and compiling generates a list file . Teensy 2.0 uses an ATmega32u4, the same chip as for the Arduino Leonardo. We get with this chip the whole portB and portD and 6 pins from portF.

Teensy 2.0 circuit

    void setup() {
      pinMode(2,INPUT);         // Teensy 2.0 digital pin 2 is PB2
      pinMode(8,OUTPUT);        // Teensy 2.0 digital pin 8 is PD3
      pinMode(A1,INPUT_PULLUP); // Teensy 2.0 digital pin 20 or analog pin A1 is PF1
    }

    void loop() {}

After compiling, we find in a temporary folder (/tmp on linux) the hex-file (.hex) and the list-file (.lst) of our program. The hex file doesn't help much, because it's our machine program in hexadecimal that is programmed to the chip. Here is the line with the setup commands, the interesting code is between the 2 vertical bars :) :

:1001B00027CF|22982A98539A8198899A|EEE7F0E0FF

The stripped list-file gives more information, because we also see the commands. 

000001b2 <setup>:
                CORE_PIN2_DDRREG  &= ~CORE_PIN2_BITMASK;
1b2:    22 98           cbi 0x04, 2
                CORE_PIN2_PORTREG &= ~CORE_PIN2_BITMASK;
1b4:    2a 98           cbi 0x05, 2 ; 5
                CORE_PIN8_DDRREG |= CORE_PIN8_BITMASK;
1b6:    53 9a           sbi 0x0a, 3 ; 10
                CORE_PIN20_DDRREG  &= ~CORE_PIN20_BITMASK;
1b8:    81 98           cbi 0x10, 1 ; 16
                CORE_PIN20_PORTREG |=  CORE_PIN20_BITMASK;
1ba:    89 9a           sbi 0x11, 1 ; 17
...
1c6:    08 95           ret

In the first column we see the address of the flash. The setup begins at 0x1B2. After the address comes the 2 byte machine code for the flash. And then the code in assembler language. There are only 2 assembler commands here, set bit (sbi) and clear bit (cbi). Both can handle single bits of our SF-register. So in assembly there is no masking needed for this register (but we need masks for other SF-register). After the commands we get the address of the SF-register. Here is a little table with the addresses for ATmega32u4:

address register address register address register
0x03 PINB 0x09 PIND 0x0F PINF
0x04 DDRB 0x0A DDRD 0x10 DDRF
0x05 PORTB 0x0B PORTD 0x11 PORTF

So we get:

pinMode(2,INPUT);            cbi DDRB,PB2  ; set Arduino digital Pin 2 as input `0`
                             cbi PORTB,PB2 ; no internal pull-up resistor! PORTB = `0`
pinMode(8,OUTPUT);           sbi DDRD,PD3  ; set Arduino digital Pin 8 as output `1`
pinMode(A1,INPUT_PULLUP);    cbi DDRF,PF1  ; set Arduino digital Pin 20 (A1) as input `0`
                             sbi PORTF,PF1 ; connect internal pull-up resistor! PORTB = `1`

The interesting part is the C-code in the list file used by the internal Arduino library:

    CORE_PIN2_DDRREG  &= ~CORE_PIN2_BITMASK;
    (or CORE_PIN2_DDRREG  = CORE_PIN2_DDRREG & ~CORE_PIN2_BITMASK;)

stands for cbi DDRB,PB2 to clear bit 2 in DDRB register. So the CORE_PIN2_DDRREG stands for DDRB, and the CORE_PIN2_BITMASK must be 0b00000100 or 0x04 because the byte is inverted. So we get:

    DDRB  = DDRB & ~(0b00000100);
    (or DDRB = DDRB & 0b11111011; or DDRB &= 0b11111011; or DDRB &= 0xFB;)

So we can rewrite our Arduino program this way using SF-register and masking:

    void setup() {
      DDRB =  DDRB & 0b11111011;   // Set PB2 in DDRB to 0 with and AND mask (PB2 = input)
      PORTB = PORTB & 0b11111011;  // Set PB2 in PORTB to 0 with and AND mask (PB2 has no pull-up)
      DDRD =  DDRD | 0b00001000;   // Set PD3 in DDRD to 1 with and OR mask (PD3 = output)
      DDRF =  DDRF & 0b11111101;   // Set PF1 in DDRF to 0 with and AND mask (PF1 = input)
      PORTF = PORTF | 0b00000010;  // Set PF1 in PORTF to 1 with and OR mask (PF1 has pull-up)
    }

    void loop() {}

Naturally we would not do it this way, because the code is less readable and not portable (it will not run on another Arduino not using the ATmega32u4 chip). But masking is often necessary in our programs, and working with ports can also simplify the programs as seen in our example with the seven segment display from the previous chapter.

Bit shifting

A very useful bitwise operation is the arithmetic bit shift to right or left (Arduino reference). With the shift operators >> or << we simply slide the data right or left by a certain number of places. The bits that are shifted out disappear. A zero is shifted in from the other end. This operation equates a logical shift in assembler (logical shift right lsr resp. logical shift right lsl).

    byte a = 0b10010110;
    a = a>>3;  // right shift three positions: a = 0b00010010
    a = a<<5;  // left shift five positions:   a = 0b01000000

The shift of one position to the right equates a division by 2 in binary! A right shift of two positions is a division by 4 etc..

    byte a = 0b00010110;  // = 22
    byte b = 0b00010110;  // = 22
    a = a>>1;  // right-shift one positions:   a = 0b00001011 = 11 = 22/2
    a = a>>1;  // right-shift two positions:   a = 0b00000101 = 5  = 11/2 = 22/2/2
    a = a>>1;  // right-shift three positions: a = 0b00000010 = 2  = 5/2 = 22/2/2/2
    a = b>>3;  // right-shift three positions: a = 0b00000010 = 2  = 22/8

On the other hand a shift of one position to the left equates a multiplication by 2 in binary! A left shift of two positions is a multiplication by 4 etc..

    byte a = 0b00010110;  // = 22(10)
    byte b = 0b00010110;  // = 22(10)
    a = a<<1;  // left shift one positions:  a = 0b00101100 = 44 = 22*2
    a = a<<1;  // left shift two positions:  a = 0b01011000 = 88 = 44*2 = 22*2*2
    a = b<<4;  // left-shift four positions: a = 0b01100000 = 96 error

In the last example we get an error because 22·16 = 352 and this can't fit in a byte. But shifting also works with integer or long!

Assignment operators

We often need to change a value on it's self (a = a << 1 or a = a + 1) in programming. In C++ language and thus in Arduino we have a a shorthand notation. The operator is placed before the equal sign. This is true for most operators.

Here some examples:

    int a = 2;  // 0b0000000000000010 = 2
    a += 4;     // 0b0000000000000110 = 6 = 4+2
    a <<= 4;    // 0b0000000001100000 = 6*16 = 96 = 64+32
    a |= 3;     // 0b0000000001100011 = 99 (mask 3 = 0b11)
    a &= ~64;   // 0b0000000000100011 = 35 (mask ~64 = 0b1111111110111111)
    a ^= 7;     // 0b0000000000100100 = 36 (mask 7 = 0b111)
    a ^= 7;     // 0b0000000000100011 = 35 (mask 7 = 0b111)
"Just do it" CL8:
"Just do it" CL9:
"Just do it" CL10:

Boolean (logical) and comparison operators

Boolean operators

Boolean operators interprete the whole variable as true or false. A seen in the previous chapter all values higher than zero mean true. Only zero is false.

It is important to not confound these Boolean operators with the bitwise operators!

Example with Boolean operators:

    // NAND and NOR gate
    // 2 switches to ground (pin 0, pin 1)
    // 2 LED with series resistor to ground (pin 2, pin 3)

    const byte PIN_IN1 = 0;
    const byte PIN_IN2 = 1;
    const byte PIN_OUT1 = 2;
    const byte PIN_OUT2 = 3;

    bool in1, in2, nand_out, nor_out;

    void setup() {
      pinMode(PIN_IN1,INPUT_PULLUP);
      pinMode(PIN_IN2,INPUT_PULLUP);
      pinMode(PIN_OUT1,OUTPUT);
      pinMode(PIN_OUT2,OUTPUT);
    }

    void loop() {
      in1 = !digitalRead(PIN_IN1); // invert to positive logic (Pull-Up!)
      in2 = !digitalRead(PIN_IN2);
      nand_out = !(in1 && in2);
      nor_out  = !(in1 || in2);    // alt. de Morgan !in1 && !in2
      digitalWrite(PIN_OUT1,nand_out);
      digitalWrite(PIN_OUT2,nor_out);
    }
Comparison operators

Often we have to compare values and need a Boolean true or false for result.

These operators are often used for flow control in if/else or switch/case statements but also in while()/do..while() or for() loops.

    if ((raining != true) && (windSpeed <= 3) && (holiday == true)) {
      flyDrone();
    }
    if ( holiday != true ) {
      work();
    }
    else if ((raining != true) && (windSpeed <= 3)) {
      flydrone();
    }
    else {
      goForAWalk();
    }
    while (windy != true) {
      flyDrone();
    }
    for (byte i = 0; i < 500; i++) {
      Serial.print("do your homework!");
    }

Use parentheses around the subclauses to keep your code as readable as possible by grouping subclauses together.

Lookup tables (LUT)

Every truth table can be programmed with a lookup table. The inputs are interpreted as number (case) and are used as index to access the table (e.g. truth table with 3 inputs gives the numbers from 0-7).

Here the same example as above using lookup tables.

    // NAND and NOR gate with Look Up Table (LUT)
    // 2 switches to ground (pin 0, pin 1)
    // 2 LED with series resistor to ground (pin 2, pin 3)

    const byte PIN_IN1 = 0;
    const byte PIN_IN2 = 1;
    const byte PIN_OUT1 = 2;
    const byte PIN_OUT2 = 3;

    // Look Up Tables (LUT's)
    bool nand[4] = {1, 1, 1, 0};
    bool nor[4]  = {1, 0, 0, 0};

    byte in1, in2, in;
    bool nand_out, nor_out;

    void setup() {
    pinMode(PIN_IN1,INPUT_PULLUP);
    pinMode(PIN_IN2,INPUT_PULLUP);
    pinMode(PIN_OUT1,OUTPUT);
    pinMode(PIN_OUT2,OUTPUT);
    }

    void loop() {
    in1 = !digitalRead(PIN_IN1); // invert to positive logic (Pull-Up!)
    in2 = !digitalRead(PIN_IN2);
    in = in2*2+in1;              // calculate index (case of the truth table)
    nand_out = nand[in];
    nor_out = nor[in];
    digitalWrite(PIN_OUT1,nand_out);
    digitalWrite(PIN_OUT2,nor_out);
    }
"Just do it" CL11:

Interesting links