03 Combinational Logic 2

Lecture from: 02.03.2023 | Video: YT

General CMOS Gate Structure: Pull-Up and Pull-Down Networks

In the previous lecture, we explored fundamental CMOS logic gates, including NOT, NAND, and AND. Now, let’s generalize the structure of CMOS gates and understand the rationale behind it.

A typical CMOS logic gate consists of two main networks:

1. pMOS Pull-Up Network (PUN): Located at the top of the circuit, connected to the power supply (Vdd). This network uses pMOS transistors to pull the output HIGH (logic 1) under certain input conditions.

2. nMOS Pull-Down Network (PDN): Located at the bottom of the circuit, connected to ground (GND). This network uses nMOS transistors to pull the output LOW (logic 0) under certain input conditions.

The input signals feed into both the PUN and PDN, and the output is taken from the point between these two networks.

Why this structure? The key principle is to ensure that, based on the input values, exactly one of the PUN or PDN is active (conducting), while the other is inactive (non-conducting).

• One Network ON, the Other OFF: This ensures that the output is reliably connected to either Vdd (logic 1) or GND (logic 0), providing a well-defined logic level.

• Analogy: Imagine a seesaw. One side must be down for the other to be up. Similarly, either the PUN must be pulling the output HIGH, or the PDN must be pulling it LOW.

What if both networks are ON or OFF simultaneously?

• Both ON (Short Circuit): If both the PUN and PDN are conducting simultaneously, a direct path is created between the power supply (Vdd) and ground (GND). This results in a short circuit, where a large amount of current flows, leading to excessive power consumption and potential damage to the circuit. This is an incorrect and undesirable operating condition. The output voltage in this scenario is undefined and likely between the expected high and low values, potentially causing issues for downstream logic.

• Both OFF (Floating): If both the PUN and PDN are non-conducting, the output is effectively disconnected from both Vdd and GND. The output is then said to be floating (or in a high-impedance state). This is also an undesirable operating condition because the output voltage is undefined and susceptible to noise, potentially causing unpredictable behavior in the circuit. The output state can be represented by “Z” or “High-Z”, indicating a high-impedance, floating state. This state has an indeterminate voltage and is susceptible to stray electrical fields.

Deeper Dive: Why This Specific Network Structure?

The use of both pMOS and nMOS transistors in this complementary fashion is driven by the inherent characteristics of these transistors as imperfect switches.

• Transistor Imperfections: MOS transistors don’t behave like perfect switches. They have limitations in their ability to efficiently pass certain voltage levels:

  • pMOS Transistors: pMOS transistors conduct logic 1’s (Vdd) well but are poor at passing logic 0’s (GND). They exhibit a voltage drop when trying to pull a node to ground.

  • nMOS Transistors: nMOS transistors conduct logic 0’s (GND) well but are poor at passing logic 1’s (Vdd). They exhibit a voltage drop when trying to pull a node to Vdd.

• CMOS Advantage: By using pMOS transistors in the PUN and nMOS transistors in the PDN, we overcome these limitations. The pMOS transistors ensure that the output is reliably pulled HIGH, while the nMOS transistors ensure that the output is reliably pulled LOW.

• Speed Considerations: nMOS transistors are generally faster than pMOS transistors due to the higher mobility of electrons compared to holes (the charge carriers in pMOS). However, the complementary CMOS structure balances speed and signal integrity.

NAND + NOT = AND

As discussed previously, an AND gate can be implemented by combining a NAND gate with an inverter.

Why this approach?

CMOS technology favors the NAND gate as a more efficient and compact implementation compared to the AND gate. The NAND gate’s series-parallel structure is more naturally suited for CMOS fabrication. By using a NAND gate followed by an inverter, we leverage the strengths of CMOS technology while achieving the desired AND functionality. In essence, by using the NAND and then a NOT gate, we are exploiting the properties of the nMOS and pMOS transistors in an optimal and easier to implement way. Directly implementing an AND using a parallel-series network would be more complex in CMOS.

Latency (Gate Delay)

The arrangement of transistors within a CMOS gate significantly impacts its speed or latency (gate delay).

• Transistors in Series vs. Parallel: Generally, transistors connected in series are slower than transistors connected in parallel. This is because the series connection increases the effective resistance, hindering the current flow required to charge or discharge the output capacitance. Less resistance equates to quicker signal transitions.

• Resistance Analogy: Imagine water flowing through a pipe. A narrower pipe (higher resistance) restricts the water flow more than a wider pipe (lower resistance). Similarly, series transistors present a narrower path for current compared to parallel transistors.

• Transistor-Level Optimizations: While the series/parallel rule generally holds, there are transistor-level design techniques where seemingly inefficient configurations can achieve better performance due to nuanced physical effects. These nuances can be only be revealed in the physical implementation.

Power Consumption

Energy consumption is a critical concern in computer architecture. Ultimately, energy consumption is the product of power and time.

Dynamic Power Consumption

Dynamic power is consumed due to the charging and discharging of circuit capacitances as signals switch between logic levels.

The dynamic power consumption is approximated by the following formula:

$P_{\text{dynamic}}=C\cdot V^2\cdot f$

Where:

• C: Represents the total capacitance being switched. This includes the gate capacitance of transistors, wiring capacitance, and other parasitic capacitances.
• V: Represents the voltage swing (the difference between the high and low voltage levels).
• f: Represents the switching frequency (how often the signal changes its state).

Explanation: Each time a signal transitions (e.g., from 0 to 1), the capacitance C needs to be charged to voltage V. This charging process requires energy, which is drawn from the power supply. The higher the capacitance, the larger the voltage swing, and the more frequent the switching, the greater the dynamic power consumption.

Static Power Consumption

Static power is consumed even when the circuit is not actively switching. It arises primarily from leakage currents through transistors.

The static power consumption can be approximated by the following formula:

$P_{\text{static}}=V\cdot I_{\text{leakage}}$

Where:

• V: Represents the supply voltage.
• $I_{\text{leakage}}$: Represents the total leakage current flowing through the transistors.

Explanation: Even when a transistor is supposed to be “off,” a small amount of current (leakage current) still flows through it. This leakage current contributes to static power consumption. Lowering the supply voltage helps reduce leakage power, but it also affects performance. Static power has become more important in modern transistors because as transistors get smaller leakage currents increase significantly.

Common Logic Gates

Here are some commonly used logic gates and their symbols:

Aside: Moore’s Law

Moore’s Law, an observation made by Gordon Moore in 1965, predicted that the number of transistors on a microchip would double approximately every two years (or sometimes cited as 18 months), leading to exponential increases in computing power and decreases in cost.

While Moore’s Law isn’t a physical law but rather an observation and a driving force for innovation in the semiconductor industry, it has held remarkably true for several decades, enabling significant advances in computing. We have been able to constantly push the limits and make smaller and smaller transistors.

Innovation: Driving the Shrink

Continued adherence to Moore’s Law has required constant innovation in materials, manufacturing processes, and circuit design.

One crucial example of this innovation is the development of Extreme Ultraviolet (EUV) lithography. EUV lithography uses light with a much shorter wavelength than previous lithography techniques. This allows for the creation of much smaller and more intricate patterns on silicon wafers, enabling the fabrication of smaller transistors and denser integrated circuits. This allows for smaller transistors meaning more transistors per die and thus an increase of capabilities.

Combinational Logic Circuits

Having explored the fundamentals of logic gates, we now move towards constructing more complex logic structures that form essential components of a computer’s microarchitecture.

A logic circuit can be viewed as a function with:

• Inputs: Data fed into the circuit.
• Outputs: The processed results generated by the circuit.

Therefore, describing a logic circuit requires both a functional specification that defines the relationship between inputs and outputs, and a timing specification that quantifies the circuit’s latency (delay). In this lecture, we will primarily focus on the functional aspects of combinational logic.

Combinational Logic: Deals with pure functions, meaning they are memoryless. The output at any given time depends solely on the current input values. The functions can only be based on the inputs (i.e. not based on previous states).

Sequential Logic: (To be covered later) Involves memory elements, making it “impure” and capable of storing values and history.

Functional Specification: Mapping Inputs to Outputs

The functional specification provides a unique and well-defined mapping from input combinations to output values. The same input combination will always produce the same output. This memoryless, deterministic behavior is a hallmark of combinational logic. The key aspect is that because the functions are totally defined and well defined, each possible input has a uniquely defined output.

Example: Full 1-bit Adder

Consider a full 1-bit adder, a fundamental building block for arithmetic operations. Let’s examine its functional specification:

The adder has three inputs:

• A, B: The two bits to be added.
• $C_{in}$: The carry-in bit from the previous stage.

And it produces two outputs:

• S: The sum bit.
• $C_{out}$: The carry-out bit to the next stage.

We can express these outputs as functions of the inputs:

• $S=F(A,B,C_{in})$
• $C_{out}=G(A,B,C_{in})$

Where:

• $F:(A,B,C_{in})\mapsto A\oplus B\oplus C_{in}$ This function represents a 3-input XOR operation. The sum bit (S) is 1 if an odd number of inputs (A, B, $C_{in}$) are 1, and 0 otherwise.

• $G:(A,B,C_{in})\mapsto AB+A{C}_{in}+B{C}_{in}$ This function represents a 3-input majority function. The carry-out bit ($C_{out}$) is 1 if at least two of the inputs (A, B, $C_{in}$) are 1, and 0 otherwise.

(Here, ”+” represents the OR operation, "$\oplus$" represents the XOR operation, and "$\cdot$" represents the AND operation.)

We can represent these functions in a truth table, listing all possible input combinations and their corresponding output values.

Boolean Algebra: The Foundation of Logic Design

Boolean algebra provides the mathematical framework for analyzing and designing digital circuits. It offers a set of rules and axioms for manipulating logical expressions, allowing us to simplify and optimize circuit designs.

Key Axioms and Theorems

The following are some fundamental axioms and theorems of Boolean algebra:

Axioms

• Identity:
  • $A+0=A$
  • $A\cdot 1=A$
• Complement:
  • $A+\overline{A}=1$
  • $A\cdot \overline{A}=0$
• Commutativity:
  • $A+B=B+A$
  • $A\cdot B=B\cdot A$
• Distributivity:
  • $A\cdot (B+C)=(A\cdot B)+(A\cdot C)$
  • $A+(B\cdot C)=(A+B)\cdot (A+C)$

Duality Principle

A crucial concept is the duality principle. Any valid Boolean equation remains valid if we interchange the AND and OR operations, and replace 1’s with 0’s and vice-versa.

DeMorgan’s Laws

These are fundamental theorems used extensively in logic simplification:

• $\overline{A+B}=\overline{A}\cdot \overline{B}$
• $\overline{A\cdot B}=\overline{A}+\overline{B}$

In essence, applying a NOT gate to the result of an operation (AND or OR) is equivalent to applying NOT gates to each operand and then performing the opposite operation (OR or AND, respectively).

Logic Synthesis and Computer-Aided Design (CAD)

The power of Boolean algebra lies in its ability to simplify complex logic expressions. By applying these rules and theorems, we can reduce the number of gates required to implement a particular function, leading to more efficient circuits in terms of area, power consumption, and delay. This process, called logic minimization or logic simplification, is often automated using Computer-Aided Design (CAD) or Electronic Design Automation (EDA) tools, making it possible to design and optimize complex digital systems with millions or even billions of gates. Because at such scales, hand optimisation is intractable.

Standardized Function Representations (Canonical Forms)

To facilitate communication, analysis, and automated design, it’s crucial to have standardized, universally accepted ways of representing Boolean functions. These are known as canonical representations, which start from a function’s truth table.

There are two primary canonical forms:

1. Sum of Products (SOP): Also known as Disjunctive Normal Form (DNF).
2. Product of Sums (POS): Also known as Conjunctive Normal Form (CNF).

Definitions

Before diving into the forms, let’s define some key terms:

• Complement: The complement of a variable is its negation (e.g., the complement of A is $\overline{A}$).
• Literal: A variable or its complement (e.g., A, $\overline{A}$, B, $\overline{B}$).
• Implicant: A product term (AND term) that implies the function (i.e., if the product term is 1, then the function is 1). It can be a single literal or a combination of literals ANDed together.
• Minterm: A product term (AND term) that includes all input variables, either in their true or complemented form. A minterm is 1 for exactly one row of the truth table.
• Maxterm: A sum term (OR term) that includes all input variables, either in their true or complemented form. A maxterm is 0 for exactly one row of the truth table.

Sum of Products (SOP) Form

The Sum of Products (SOP) form expresses a Boolean function as a sum (OR) of minterms. Each minterm corresponds to a row in the truth table where the function output is 1.

Steps:

1. Identify Minterms: For each row in the truth table where the output is 1, create a minterm by ANDing together the literals corresponding to that row. If an input variable is 0 in that row, use its complement; if it’s 1, use the variable itself.
2. Sum the Minterms: OR together all the minterms identified in step 1.

Example:

Standard Notation (Sigma Notation):

We can use a shorthand notation for SOP forms. We examine the rows of the truth table where the output is 1, treat the input combination as a binary number, and list the corresponding decimal numbers.

Where ‘m’ denotes minterms.

Canonical vs. Minimal Form:

The canonical SOP form is not necessarily the minimal form (the form with the fewest literals). However, it provides a starting point for logic minimization techniques (e.g., Karnaugh maps, Quine-McCluskey algorithm), which can be automated by computer tools.

Product of Sums (POS) Form

The Product of Sums (POS) form expresses a Boolean function as a product (AND) of maxterms. Each maxterm corresponds to a row in the truth table where the function output is 0.

Steps:

1. Identify Maxterms: For each row in the truth table where the output is 0, create a maxterm by ORing together the literals corresponding to that row. If an input variable is 0 in that row, use the variable itself; if it’s 1, use its complement.
2. Multiply the Maxterms: AND together all the maxterms identified in step 1.

Example:

Standard Notation (Pi Notation):

We look at rows where the output equals zero. We can use a shorthand notation, similar to SOP:

Where ‘M’ denotes maxterms.

Useful Conversions

Basic Combinational Blocks

Building upon our understanding of logic gates and Boolean algebra, we can now construct more complex combinational blocks. These blocks serve as fundamental components in larger digital systems, and by modularizing them, we can create hierarchical designs, abstracting away lower-level details.

We will examine the following combinational blocks:

• Decoder
• Multiplexer
• Full Adder
• PLA (Programmable Logic Array)

Decoder

A decoder is a combinational circuit that converts an n-bit binary input into $2^n$ unique outputs. It can be thought of as an “input pattern detector”. For any given input combination, exactly one of the outputs is asserted (logic 1), while all other outputs are deasserted (logic 0).

The output that is asserted corresponds to the binary value of the input.

Example: 2-to-4 Decoder

This decoder takes a 2-bit input (A, B) and produces four outputs.

Implementation:

The 2-to-4 decoder is built using AND gates and inverters. Each AND gate corresponds to a specific minterm of the input variables.

• $O_0=\overline{A}\cdot \overline{B}$ (detects input 00)
• $O_1=\overline{A}\cdot B$ (detects input 01)
• $O_2=A\cdot \overline{B}$ (detects input 10)
• $O_3=A\cdot B$ (detects input 11)

This construction ensures that for any given input combination, only one AND gate’s output will be 1, and all others will be 0. Each output represents a specific minterm corresponding to the binary input.

Applications of Decoders:

• Memory Addressing: Decoders are crucial in memory systems. Given a binary address, a decoder selects the corresponding memory location (word line in a RAM or ROM).
• Instruction Decoding: In a processor, a decoder can interpret the opcode (operation code) of an instruction and activate the corresponding control signals for the appropriate functional unit. Each instruction is encoded as a unique bit pattern.
• Selecting specific components in a system.

Multiplexer (MUX)

A multiplexer (MUX), also known as a selector, is a combinational circuit that selects one of N data inputs and forwards it to a single output. The selection is controlled by a set of select lines, whose number is ${\log }_{2}N$.

Example: 2-to-1 MUX

A 2-to-1 MUX has two data inputs ($I_0$, $I_1$), one select input (S), and one output (O).

• If S = 0, the output O is connected to $I_0$.
• If S = 1, the output O is connected to $I_1$.

Circuit Implementation (2-to-1 MUX):

The circuit uses AND gates and an OR gate.

$O=(\overline{S}\cdot I_0)+(S\cdot I_1)$

Module Representation:

This is a common way to represent a MUX as a reusable component.

Building Larger MUXes:

Larger multiplexers can be constructed using smaller ones. For example, a 4-to-1 MUX can be built using three 2-to-1 MUXes:

• Two 2-to-1 MUXes select between ($I_0$, $I_1$) and ($I_2$, $I_3$) based on the least significant select bit ($S_0$).
• A third 2-to-1 MUX selects between the outputs of the first two MUXes based on the most significant select bit ($S_1$).

Applications:

• Data Selection: Multiplexers are fundamental for selecting data from multiple sources. For example, in memory access, a MUX can be used to choose data from a specific memory location based on the address.

• Instruction Execution: In a processor, a MUX can be used to select the appropriate data source or functional unit output based on the decoded instruction. Imagine a processor with both an adder and a multiplier. The instruction’s opcode would be decoded, and the decoder’s output would control a MUX, selecting the output of either the adder or the multiplier as the result.

• Logic Function Implementation (Lookup Tables): Multiplexers can act as lookup tables to implement arbitrary Boolean functions.

  • AND Gate:

    

    Connect $I_0$, $I_1$, $I_2$ to 0 and $I_3$ to 1. The select lines A and B will act as the inputs to the and function.

  • XOR Gate:

    Connect $I_0$, $I_3$ to 0 and $I_1$, $I_2$ to 1. The select lines A and B will act as the inputs to the xor function.

  • Arbitrary Function:

    

    By connecting the data inputs ($I_0$ to $I_7$) to the appropriate logic levels (0 or 1) based on the desired function’s truth table, a MUX can implement any 3-input Boolean function. The select lines (A, B, C) are the function’s inputs.

• FPGAs: Multiplexers are key components in Field-Programmable Gate Arrays (FPGAs). They are used in Lookup Tables (LUTs) to implement logic functions and in routing networks to connect different parts of the FPGA.

Full Adder

Binary addition is analogous to decimal addition, proceeding from right to left, processing one column at a time, generating a sum and a carry bit for each column.

We can implement a 1-bit full adder using a decoder with 3 inputs, generating $2^3-1$ minterms (not $2^3$ because one output state is not required), followed by AND gates to generate the minterms and OR gates to combine the appropriate minterms to produce the Sum and Carry outputs. This is essentially creating a Sum-of-Products (SOP) representation for the 1-bit addition.

To construct a 4-bit adder from 1-bit full adders, we can cascade them together, connecting the carry-out of one full adder to the carry-in of the next. This process is called serializing the addition.

Programmable Logic Array (PLA)

A Programmable Logic Array (PLA) is a configurable circuit structure that implements any N-input, M-output logic function in a two-level Sum-of-Products (SOP) form.

It typically consists of a decoder for $n$ inputs followed by an array of AND gates and an array of OR gates.

This structure allows flexible implementation of a collection of desired logic functions. The decoder generates all possible minterms of the input variables. The AND gates form the minterms, and the OR gates combine selected minterms to generate the desired outputs.

The number of AND gates is $2^n$, and the number of OR gates is equal to the number of outputs $M$.

Implementing a Full Adder using a PLA

We can implement a full adder using a PLA, where the PLA is configured to generate the Sum and Carry outputs based on the input variables A, B, and Carry-in ($C_{in}$).

Summary

In this section, we covered:

• Decoders
• Multiplexers
• Full Adders
• PLAs

To recap, the function of:

• A decoder is to generate a unique output for each possible input combination.
• A multiplexer is to select one of several input signals and route it to a single output.
• A full adder is to perform binary addition of two bits and a carry-in bit, producing a sum and a carry-out.
• A PLA is to implement arbitrary logic functions in SOP form by programmably connecting minterms generated by an AND array to outputs via an OR array.

Continue here: 04 Sequential Logic Design