Boolean Algebra & Combinatorial Circuits

Combinatorial Circuits for Computer Implementation

• Topics covered include: Boolean algebra, logic operators in VHDL, logic gates, transistor implementation of logic gates, Boolean functions, Karnaugh diagrams, and relevant combinatorial circuits.

Boolean Algebra

• Boolean algebra is a 3-tuple (A, +, •) where A is a set and +, • are mappings from A × A to A.
• Special elements 1,0 ∈ A satisfy N1 and N2.
• For every x ∈ A, there exists an x that satisfies I1 and I2.
• The commutative law states that for all x, y ∈ A, x • y = y • x (K1) and x + y = y + x (K2).
• The distributive law states that x • (y + z) = (x • y) + (x • z) (D1) and x + (y • z) = (x + y) • (x + z) (D2).
• The neutral elements are defined as x • 1 = x (N1) and x + 0 = x (N2).
• The inverse elements are defined as x • x = 0 (I1) and x + x = 1 (I2).
• The theorems include:
  • Elimination: x • 0=0 (E1) and x + 1=1 (E1).
  • Absorption: x • (x + y) = x (AB1) and x + (x • y) = x (AB1).
  • Associative Law: (x • y) • z = x • (y • z) (A1) and (x + y) + z = x + (y + z) (A2).
  • Idempotency: x • x = x (ID1) and x + x = x (ID2).
  • Double Negation: (x) = x (DN).
  • DeMorgan: (x + y) = (x • y) (M1) and (x • y) = (x + y) (M2).

De Morgan's Theorem

• De Morgan's Theorem is verified using truth tables to show the relationships between inputs and their complements.

Simplification of Boolean Functions

• Boolean functions can be simplified using rules like the consensus rule: XY + XZ + YZ = XY + XZ.
• The dual consensus rule is: (X + Y)(X + Z)(Y + Z) = (X + Y)(X + Z).
• An example formula is (A + B)(Ā + C) = AĀ + AC + ĀB + BC which simplifies to AC + ĀB + BC and further to AC + ĀB.
• Function complements can also be simplified using boolean algebra such as:
  • F₁ = XYZ + XYZ = (XYZ) • (XYZ) = (X + Y + Z)(X + Y + Z)
  • F2 = X(YZ + YZ) = X + (YZ + YZ) = X + YZ•YZ = X + (Y + Z)(Y + Z)

VHDL Logic Operators

• VHDL (Hardware Description Language) is used to describe hardware.
• VHDL logic operators include:
  • not: F <= not X;
  • and: F <= X and Y;
  • or: F <= X or Y;
  • nand: F <= X nand Y;
  • nor: F <= X nor Y;
  • xor: F <= X xor Y;
  • xnor: F <= X xnor Y.

Logic Gates

• Common logic gates include AND, OR, NOT (Inverter), NAND, NOR, XOR, and XNOR.
• Each gate has a specific truth table that defines its output based on the inputs.

Truth Tables

• Truth tables can be used to verify the equivalence of logic functions, presenting the outputs of the functions for all possible input combinations.
• A logic circuit diagram is utilized to illustrate the implementation of logic functions.
• It's relevant to simplifying Boolean functions.

CMOS Logic

• CMOS (Complementary Metal-Oxide-Semiconductor) logic uses both p-channel and n-channel transistors on a common substrate.
• CMOS technology encompasses both the semiconductor process for realizing integrated digital circuits and the CMOS logic family, which is widely used.
• CMOS logic consists of two types of transistors, N-Channel and P-Channel, that act as switches.
• An N-Channel transistor has no conductive connection without positive voltage at the gate, but becomes conductive with positive voltage at the gate.
• A P-Channel transistor has exchanged regions for N-Type and P-Type semiconductors.

CMOS Gates

• Positive voltage at the gate results in no conductive connection in a P-Channel transistor.
• Key components of a CMOS gate include:
  • Pull-Up network with P-transistors.
  • Pull-Down network with N-transistors.
  • Vdd (positive supply voltage)
  • Gnd (ground).

CMOS Gate Implementation

• Pull-Up/Down networks implement Boolean functions using switches.
• OR functions use a parallel circuit.
• AND functions use a series circuit.
• A complementary function is f(a,b,c,...) = f(a,b,c,...).

NAND Gates

• NAND gates are created when switches in the pull up network are parallel.
• NAND gates are created when switches in the pull down network are in series.

Addierschaltungen

• A half-adder is described as a <= a xor b; c <= a and b;
• A full-adder is described as <= a xor b xor d; c <= (a and b) or (a and d) or (b and d);
• A full adder with 6 Gates and 44 Transistors.
• A half adder with 5 Gates and 38 transistors.

Definitions - Terms

• Product term: Simple variables or conjunction of multiple potentially negated variables.
• Sum term: Simple variable or disjunction of multiple potentially negated variables.
• Minterm: A product term in which each variable of a Boolean function occurs exactly once.
• Maxterm: A sum term in which each variable of a Boolean function occurs exactly once.
• Sum of products: A single product term or disjunction of multiple product terms.
• Product of sums: A single sum term or conjunction of multiple sum terms.

Normal Forms

• Disjunctive Normal Form (DNF): Unique representation of a Boolean function f as a disjunction of all minterms m with f(m)=1.
• Conjunctive Normal Form (KNF): Unique representation of a Boolean function f as a conjunction of all maxterms m with f(m)=1.
• From a DNF (KNF), a simple, i.e. minimal sum of products can be generated:
  • Repeated application of axioms and theorems of Boolean algebra.
  • Use of Karnaugh diagrams.
  • Algorithmic minimization using software.

Sum of Minterms

• DNF equation.
• In this table, a minterm is a product term in which each variable of a Boolean function occurs exactly once.

Product Of Maxterms.

• KNF Equation.
• In this table, a maxterm is a sum term in which each variable of a Boolean function occurs exactly once.

Sum of Product Terms

• Two level and three level implementation
• The equations are F = AB + C(D + E)= AB + CD + CE

Karnaugh Diagrammes

• Karnaugh diagram grows with Problemgröße.
• Karnaugh is not graphical for Entwürfe with 1000 or 10.000 Gattern?

BCD to Seven-Segment Displays

• Truth tables can be utilized for BCD-to-Seven-Segment Decoders, detailing the specific segments that need to be activated for each input combination to display the corresponding numerical values.

Component Implementation

• Multiple gate usage is possible, thus reducing the necessary AND-Gatter to 14.

Relevant Logic Circuits

• Decoders
• Coder
• Multiplex
• Priority Encoder
• BCD Circuit

First VHDL Example

• VHDL, or Very High Speed Hardware Description Language, is a hardware description language
• Elements: inputs, outputs, entity, architecture, logic
• VHDL used for a digital comparator and compact Vector Notation

VHDL for a 2-to-4 Decoder with Enable

• Exemplifies structural VHDL implementation with IEEE library inclusion.

Combinational Circuits on the Basis of Decoders

• Can be utilized for a full adder.

Multiplexer

• Defined as a combinational circuit to select data.