In our first back to basics blog, we looked at Boolean Algebra. In this blog we are going to build on that and get to grips with digital logic, it is going to be a long one and hopefully will make you think a little.
At the heart of digital logic design are seven logic gates: NOT, AND, OR, XOR, NOR, NAND, and XNOR. These gates form the backbone of our designs, enabling us to create intricate logic functions through various combinations.
At the most fundamental level, these logic gates are built from transistor arrangements.
Each gate has a unique symbol and truth table, illustrating the output for given inputs.
To keep things straightforward, we'll demonstrate all gates, except the NOT gate, with two inputs.
Starting with the simplest, the NOT gate simply inverts the input logic value.
NOT Gate:
Next up is the AND gate, a staple in logic design. It performs Boolean multiplication, outputting the PRODUCT of its inputs.
AND Gate:
For Boolean addition, we turn to the OR gate, which produces the SUM of its inputs.
OR Gate:
The remaining gates—NAND, NOR, XOR, and XNOR—are derivatives of AND, OR, and NOT functions. NAND and NOR gates are particularly popular due to their universality, allowing us to implement any logic gate (AND, OR, NOT) using just these two, as we will soon see.
The NAND gate, representing NOT AND, is often depicted as an AND gate with an inversion bubble on its output.
NAND Gate:
Similarly, the NOR gate represents NOT OR and is shown as an OR gate with an inversion bubble.
NOR Gate:
Lastly, XOR and XNOR gates, constructed from the basic gates we've covered, offer valuable functions. They help determine if inputs differ (XOR) or agree (XNOR).
XOR Gate:
XNOR Gate:
Each of these gates comprises several transistors arranged to achieve the desired logic function. The NOT gate, for instance, uses two complementary transistors to invert the input signal.
Transistor-Level Implementation of a NOT Gate:
When the input is high, transistor Q1 is off, and Q2 is on, pulling the output low. Conversely, when the input is low, Q1 is on, and Q2 is off, pushing the output high.
This structure is the foundation for more complex gates, such as the AND gate.
Transistor-Level Implementation of an AND Gate:
In the AND gate, when both inputs (A and B) are high, Q1 and Q2 turn on while Q3 and Q4 turn off, pulling the input to Q5 and Q6 low. This inversion results in Q5 turning on and Q6 turning off, setting the output high.
For other input combinations, at least one of Q1, Q2, Q3, or Q4 is off, pulling the input to Q5 and Q6 high, turning Q6 on and Q5 off, thus pulling the output low.
When designing logic circuits with combinations of these gates, we create combinatorial logic circuits with no storage or feedback. Understanding input changes is crucial because logic gates, being transistor arrangements, take time to propagate changes from input to output.
This delay, known as PROPAGATION time, varies by logic family (e.g., CMOS or TTL) and affects the switching frequency of the design. If we are testing in the lab we measure the propagation delay, between the mid-point (50%) of the rising and falling edges as shown below.
Propagation delay is typically specified in datasheets, with separate times for high-to-low and low-to-high transitions. Factors such as ambient temperature, power supply conditions, driver resistance, and capacitive load also influence this delay.
The term FANOUT refers to the number of inputs driven by an output, impacting rise and fall times. Datasheets usually list propagation times from 5 ns to 35 ns, depending on the logic family and conditions.
In designs with multiple logic gate levels, differing propagation delays can cause glitches, or RACE Hazards. Mitigating these requires careful planning, often incorporating storage elements like D flip-flops and a clock to stabilize the output.
Example Logic Problem
Let's illustrate these concepts with an example. Imagine a system monitoring three motors, each with a fault output.
Our system should signal high if at least two motors work correctly. We'll start with a truth table for all possible input combinations and the desired output.
Truth Table for Motor Fault Detection:
From this truth table we can generate the following logic equations
OP = (A.B) + (A.C) + (B.C)
We call the format of this equation a SUM of PRODUCTS (SOP) equation as the op is the Boolean SUM (Logical OR) of the Boolean PRODUCTS (AND) equations.
If we so desired, we could calculate a PRODUCT of SUMS (POS) output by following the approach.
Firstly, we create the SOP logic equation for each entry on the truth table where the output is low
Next, we apply DeMorgan’s theorem to convert from the SOP to the POS format, the first step is to invert the SOP equation.
We can then apply the DeMorgan’s theorem and the ninth law of logic to create the final POS equation
For the remainder of this example however, we will work with the SOP format as that is the most common method for implementing logic functions.
As such we can realize our SOP equation using a two-level logic circuit as below
With this two-level network we need to consider the propagation delay through the first AND gate level and the impact it might have on the output.
Of course, this implementation uses two logic gate types (AND, OR) it is however possible to implement the same logical function using only NAND gates as they are universal.
Thanks to DeMorgan’s theorem the NAND gate also implements the Negative OR function
As such we can re draw the logic circuit as below
Let’s look at how we get the same functionality we desire using NAND gates, the output equation can be represented as
Using DeMorgan’s we can iterate through the following steps, changing the sign as we break the bar and applying other rules of Boolean algebra
If we are working with POS logic equations, we can use NOR gates to implement the logic equation and prove the functionality the same way using DeMorgan’s Theorem and Boolean Algebra rules.
Karnaugh maps
In the example above, we used a truth table to determine the logic equations and it works well for a simple application however, if we have more complex applications we need a better way of determining the logic equations.
This is where the Karnaugh map comes into play, KMaps are visual representation of the logic behavior which allows us to use our natural ability for pattern recognition to determine the logic equations.
Example Karnaugh Map used for four variables (A,B,C,D) – Note the gray scale count
How we use a Karnaugh Map is we group together adjacent 1’s for SOP and adjacent 0’s for POS. These groupings can then be used to determine the logic equation, using the rules of Boolean Algebra to implement the desired functionality.
Often if we use a Karnaugh Map we will obtain an equation which uses the minimum number of logic gates to implement.
Using the example below we can group together the 1’s within the design where they are adjacent to each other
The example groups together four 1’s within the center of the Karnaugh map (highlighted green) from this we can see that the logic equation is D.B as the C and A cancel each other out due to being across not C and C or not A and A respectively.
The blue elements in the corner can also be group together as they are also judged to be adjacent as the Karnaugh map is judged to wrap around edge to edge and top to bottom. As such the second equation to be extracted from the Karnaugh map is
Therefore, the resulting logic equation for the Karnaugh map is
We can also use Karnaugh maps to identify hazards which might result in glitches during operation and help us eliminate them. In the next example, we can extract the logical equation for the green and blue cells as
This however, leaves the equation highlighted by the red circle as a potential hazard, this occurs as when the input D changes from a 1 to a 0 the output is intended to stay high however, there is not a specific term in logic equation to address it. To remove the hazard, we should update the logic equation as below where the red text is the additional equation.
By this point now you should be familiar with Boolean Algebra, logic Gates and how they relate to each other to be used with truth tables and Karnaugh maps not only to determine logic equation but to also identify race conditions. You should also understand how we can use universal gates for implementing logic equations.
In our next instalment things will get even more interesting!
Workshops and Webinars
If you enjoyed the blog why not take a look at the free webinars, workshops and training courses we have created over the years. Highlights include
Professional PYNQ Learn how to use PYNQ in your developments
Introduction to Vivado learn how to use AMD Vivado
Ultra96, MiniZed & ZU1 three day course looking at HW, SW and PetaLinux
Arty Z7-20 Class looking at HW, SW and PetaLinux
Mastering MicroBlaze learn how to create MicroBlaze solutions
HLS Hero Workshop learn how to create High Level Synthesis based solutions
Perfecting Petalinux learn how to create and work with PetaLinux OS
Embedded System Book
Do you want to know more about designing embedded systems from scratch? Check out our book on creating embedded systems. This book will walk you through all the stages of requirements, architecture, component selection, schematics, layout, and FPGA / software design. We designed and manufactured the board at the heart of the book! The schematics and layout are available in Altium here Learn more about the board (see previous blogs on Bring up, DDR validation, USB, Sensors) and view the schematics here.
Comments