Combinational Logic Design
CHAPTER 3: COMBINATIONAL LOGIC DESIGN
Author: Timothy Berner, Rutgers University
TOPICS COVERED
Hierarchical Design
Technology Mapping
Combinational Function Blocks
Rudimentary Logic Functions
Decoding
Encoding
Selecting
Binary Mathematics
BEGINNING HIERARCHICAL DESIGN
Divide and Conquer: A strategy to manage complexity by breaking down larger circuits into smaller, manageable blocks.
Hierarchy: Results are related through symbols and schematics that constitute a hierarchical structure in circuits.
Circuit Blocks: The entire circuit is divided into blocks.
Complexity Reduction: Hierarchical design reduces the complexity required to represent the schematic diagram of a circuit.
Leaves: The hierarchy culminates in basic leaves such as AND gates, OR gates, and Inverters.
Primitive Blocks: These are predefined blocks with rudimentary properties.
HIERARCHICAL DESIGN REUSE
Reuse of Blocks: Functional blocks can be reused, which allows for regular circuit designs.
Regular Circuit: A circuit function that can be constructed from a reasonably small set of distinct blocks.
Irregular Blocks: Instances of blocks that appear irregularly in the design, referred to as instantiation.
Functional Blocks: Predefined collections of interconnected gates that can be reused in various designs.
TECHNOLOGY MAPPING
Steps Involved:
Replace each AND and OR gate with equivalent NAND (or NOR) gates and inverters.
Cancel all inverter pairs without altering the logic function.
Move inverters located between circuit input and NAND/NOR gate outputs to the inputs of those gates.
Cancel series inverter pairs wherever feasible.
Consolidate parallel inverters into a single inverter driving all outputs of the parallel inverters.
Repeat these steps until a maximum of one inverter exists between circuit inputs or outputs and attached gate inputs.
COMBINATIONAL FUNCTIONAL BLOCKS
Definition: Functional blocks are combinations of functions that correspond to specific circuits. By using hierarchical construction, circuits are treated as instances of these functions at the gate-level.
Inputs/Outputs: Each functional block interacts with both internal and external sources of information.
RUDIMENTARY LOGIC FUNCTIONS
Fixing Value: Attaching a constant output to a variable.
Example: If $X = 0$, then $F = 0$; If $X = 1$, then $F = 1$.
Transferring: Moving a desired value from input to output.
Example: $F = X$.
Inverting: Changing a value to its opposite.
Example: $F = X'$.
DECODING
Definition: The process of converting an N-bit input code to an M-bit output code, with the condition that $n ext{ (number of inputs)} ext{ must satisfy } n ext{ ≤ m ≤ } 2^N$ such that each input code produces a unique output code.
Decoder: A combinational circuit with inputs and outputs; it may have unused inputs without corresponding outputs.
N-to-M Line Decoders: Functional blocks that implement decoding where $m$ is less than or equal to $2^n$.
Goal: To produce $2^n$ or fewer miniterms from $N$ input variables.
Drawback: Large decoders may require many gates, leading to high gate input costs.
STEPS TO GENERATE A DECODER STRUCTURE
Let $K = N$ and determine if $K$ is even or odd.
For even $K$: Divide $K/2$ and generate $2K$ AND gates.
For odd $K$: Compute $(K + 1)/2$ and $(K - 1)/2$, generating $2K+1/2$.
Repeat until $K = 1$, at which point, use a 1-to-2 decoder.
DECODER BASED COMBINATIONAL CIRCUITS
The decoder generates $2^N$ miniterms of $n$ input variables.
Boolean functions can be expressed as a sum of miniterms, allowing them to be constructed by using the decoder to create and combine outputs with an external OR gate.
A Boolean function defined by $k$ miniterms can be expressed in its complement form using $2^n - k$ miniterms.
When the main function $F$ has more miniterms than its complement $F'$, use fewer terms for $F'$.
Implementation Observation: NOR gates can be used instead of OR gates to create a logical sum of miniterms while generating the normal output of $F$.
ENCODING
Definition: The operation that inverses the function of a decoder. An encoder typically has $2^N$ or fewer input lines and $n$ output lines, producing binary codes corresponding to input values.
Limitation: Only one input can be active at any time. Activating multiple inputs can lead to incorrect combinations.
Priority Encoder: A combinational circuit designed to enforce a priority among active inputs, selecting the highest priority input.
ENCODER EXPANSION
Encoders can be expanded to handle larger numbers of inputs through the expansion of OR gates, decreasing the gate input cost when $N ext{ ≥ 5}$.
Use multi-level circuits with expanded OR gates for $N ext{ ≥ 3}$ to enhance design efficiency.
Shared gates in multi-level circuits help to reduce overall costs post-technology mapping.
SELECTING
Importance of Selection: Critical for effective communication between different parts of circuits and systems.
Typical Selection Circuits: Comprise a set of inputs to choose from, yielding one output, and are governed by a set of control lines that dictate the selection process.
MULTIPLEXER (MUX)
Definition: A combination circuit that selects binary information from one of many input lines and directs that information to a single output line.
Selection Inputs: Defined set of input variables that determine which input line is selected for output.
Data Selector: The component that chooses from many information inputs and channels it to the output line.
MULTIPLEXER BASED COMBINATION CIRCUITS
In MUX configurations, the first $n-1$ variables connect to the selection inputs, while remaining variables serve as information inputs.
The last variable may be used to connect rudimentary functions for processing.
ITERATIVE COMBINATION CIRCUITS
Arithmetic Functional Blocks: Constructed to work on binary input vectors and produce binary output vectors, often requiring a subfunction for each position in the vector.
Subfunction Blocks: Cells implementing subfunctions that contribute to overall circuitry.
Iterative Arrays: A special case of hierarchical circuits designed to manage arrays of bits.
BINARY ADDERS
Definition: Combinational circuits designed to perform addition, subtraction, multiplication, and division with binary or decimal numbers represented in binary code via hierarchical iterative design.
Half Adder: A circuit that adds two bits, producing a sum and carry output.
Typically implemented using an XOR gate and an AND gate.
Full Adder: A circuit designed to add three bits and produce two output bits.
Can be constructed from two half adders with an OR gate to combine results.
Binary Ripple Adder: A digital circuit that sums binary numbers using combinational logic; utilizes $N$ full adders operating in parallel.
Also known as a ripple carry adder.
BINARY SUBTRACTION
Subtracting $N$ from $M$ yields correct results under certain conditions; typically, the result is non-negative if $M ext{ ≥ N}$.
If an end borrow occurs ($N > M$), the result is computed as $M - N + 2^n$, subtracting this from $2^n$ and appending a negative sign to the final result.
COMPLEMENTS
Types: 1. Radix Complement; 2. Diminished Radix Complement.
To find the complement of $N$, use the formula $(2^n - 1) - N$.
Complementing involves changing bits to their opposites.
SUBTRACTING USING 2'S COMPLEMENT
To subtract by using $2's$ compliment:
Add the $2's$ complement of $N$ to $M$.
If $M ext{ ≥ N}$, the sum triggers an end carry ($2^n$), which is discarded, so the result is $M - N$.
If $M < N$, the sum does not yield an end carry; compute $2^n - (N - M)$ for the correction, applying the negative sign to get $-(N-M)$.
BINARY ADDER-SUBTRACTORS
Using $2's$ complement eliminates the need for distinct subtraction logic. Adder circuits are designed to handle both addition and subtraction through shared components.
Current systems integrate exclusive OR gates into each full adder for sign management and correct processing of both operations.
SIGNED BINARY NUMBERS
Signed Magnitude System: Use a + sign for positive decimal numbers and a - sign for negative numbers. In computing, this is denoted with a 0 for positive and a 1 for negative.
Signed Complement System: Negative numbers are represented by their complements.
Table of Decimal and Complement Representations:
+7: 0111 (Signed 2's Complement: 0111, Signed Magnitude: 0111)
+6: 0110 (Same representation)
-8: 1000 (Represented differently)
SIGNED BINARY ADDITION AND SUBTRACTION
Addition: Adding two signed binary numbers is achieved by including the sign bits, where any carry-out from the sign bit is discarded.
Subtraction: This is performed by taking the $2's$ complement of the second number (including the sign bit) and adding it to the first number. Again, any carry-out from the sign bit is discarded.
OVERFLOW IN ARITHMETIC OPERATIONS
Overflow is a significant issue at the computer level, as systems are designed to manage specific bit-lengths. It can disrupt program execution.
Monitoring for Overflow: This can be achieved through programmatic checks.
Overflow conditions vary based on whether the numbers involved are signed or unsigned:
Unsigned: Overflow occurs if an end carry extends outside the designated significant digit position.
Signed: Overflow occurs when two positive or two negative numbers are summed, leading to an incorrect result where the sign is misrepresented.
OTHER ARITHMETIC FUNCTIONS
Contraction: Introduces new functions on circuits or equations by simplifying them into simpler forms to meet design needs.
Incrementing: The act of adding a fixed value (usually 1) to a variable, potentially compromising logic cost and efficiency.
Decrementing: Similar to incrementing but adds a negative value (-1).
Multiplication/Division: Techniques exist for multiplication and division by constants; both operations impact design efficiency and are integrated into various systems.
Zero-Filled and Extension: Additional arithmetic processes related to binary operations, specifically designed to manage representations in different contexts.