SYSTEMS Lecture Mon Nov 9th
Multiplexer Fundamentals and Multi-Bit Scaling
Multiplexers (MUX) function as digital switches that select one input signal from several options and direct it to a single output line based on control signals.
A basic single-bit 2-to-1 multiplexer selects between single-bit inputs and using a single select line to produce output .
When scaling multiplexers to handle multi-bit operands (such as registers), a single single-bit multiplexer is insufficient because multiple data bits must be switched simultaneously.
To multiplex two-bit numbers, defined as and , into a two-bit output , two separate 2-to-1 multiplexers are deployed in parallel:
One multiplexer processes the low-order bits ( and ) to generate .
A second multiplexer processes the high-order bits ( and ) to generate .
The select lines of both multiplexers are tied directly together into a common control line.
When the common select line shifts to select , routes to and routes to .
When the common select line shifts to select , routes to and routes to .
Expanding to a four-bit bus with inputs and to yield output follows the exact same modular principle:
Four individual 2-to-1 multiplexers are used (one for each corresponding bit position , , , and ).
All four multiplexer select lines are tied together so that all four output bits simultaneously switch to display either bus or bus .
Expanding to a 16-bit bus requires 16 single-bit multiplexers connected in parallel with their select lines tied together.
Historical Transistor Scaling and Register Architectures
Microprocessor evolution has been driven by the continuous physical shrinkage of transistors, which allows an increasing number of components to fit onto an integrated circuit.
Greater transistor density allows more logic gates (AND, OR, NOT) per chip, enabling larger register widths and data paths:
The earliest commercially available microcomputers utilized 8-bit registers.
Continued miniaturization enabled the production of 16-bit architectures.
Further scaling produced 32-bit computing architectures.
Contemporary general-purpose computing is standardized on 64-bit architectures.
The primary driver for transitioning from 32-bit to 64-bit architectures was address bus capacity:
A 32-bit address space provides distinct memory addresses, which limits native physical memory access to .
Operating with more than of RAM on a 32-bit processor requires memory swapping and paging workarounds, which are highly inefficient.
A 64-bit address space provides distinct addresses, doubling continuously past 32 bits (, , up to ), which yields an address space vastly larger than a terabyte.
General-purpose processors have diminishing returns beyond 64 bits:
Standard data types, such as 64-bit floating-point numbers and 32-bit integers, adequately handle the precision requirements of virtually all modern consumer and commercial applications.
Larger calculations that exceed these standard sizes can be handled via software algorithms.
Specialized computing hardware, such as Graphics Processing Units (GPUs), frequently implements data paths wider than 64 bits due to extreme parallel throughput demands, but standard central processing units do not currently require 128-bit scaling.
Historical technological forecasts often underestimate future demand; for example, early networking perspectives assumed that networks would exceed all future operational needs, whereas contemporary applications require significantly higher throughput.
Multi-Input Multiplexers and Internal Gate Logic
Multiplexers can be expanded along two distinct dimensions:
Increasing the bit width by replicating multiplexer units in parallel with synchronized select lines.
Increasing the number of selectable inputs by altering internal gate configurations to accept more channels (, etc.).
An architectural application of multi-channel multiplexing is the Little Computer 3 (LC-3) processor instruction
ADD R0, R1, R2:Source register 1 (
SR1) and source register 2 (SR2) can independently select any of the eight general-purpose registers (R0throughR7).Routing to the adder circuit is achieved by connecting all eight 16-bit register outputs to two large 8-to-1 multiplexers (one dedicated to
SR1and one toSR2).Specifying register
R1configures theSR1multiplexer to route all 16 bits of registerR1to the first adder terminal; specifyingR2configures theSR2multiplexer to route registerR2to the second adder terminal.
Number of select lines required is determined by the power of two of the input count ( inputs require select lines):
A 2-to-1 multiplexer requires 1 select line ().
A 4-to-1 multiplexer requires 2 select lines ().
An 8-to-1 multiplexer requires 3 select lines ().
A 16-to-1 multiplexer requires 4 select lines ().
Internal logic gate design of a 2-to-1 multiplexer:
Consists of an inverter, two AND gates, and one OR gate.
Input connects directly to the second AND gate and through an inverter to the first AND gate.
Applying places a logic on the second AND gate (blocking input ) and a logic on the first AND gate (allowing input to pass through to the OR gate).
Internal logic gate design of a 4-to-1 multiplexer:
Consists of four 3-input AND gates, four inverter stages on the select lines, and one 4-input OR gate.
Two select lines, and , decode into four discrete binary states:
00,01,10, and11.A logic applied to any input of an AND gate forces its output to , blocking that channel from reaching the final OR gate.
Inversion bubbles on the AND gate inputs ensure that exactly one AND gate receives logic on all of its select inputs for any given select code:
Code
00enables the AND gate for input while blocking , , and .Code
01enables the AND gate for input while blocking , , and .Code
10enables the AND gate for input while blocking , , and .Code
11enables the AND gate for input while blocking , , and .
Multiplexer Schematics, Notation, and Logisim Implementation
Dimensional notation for multiplexers is designated as :
The first number () specifies the total number of input lines.
The second number () specifies the bit width of the output (and the bit width of each input item).
Dividing the total inputs by the output bit width () gives the number of distinct choices/channels.
A 4-by-1 () multiplexer selects between 4 separate single-bit inputs to produce a 1-bit output using 2 select lines.
A 4-by-2 () multiplexer selects between two 2-bit inputs to produce a 2-bit output using 1 select line.
A 16-by-4 () multiplexer selects between four 4-bit numbers () to produce a 4-bit output ( channels).
Block diagram conventions:
Represented graphically as an isosceles trapezoid.
The longer parallel edge represents the data inputs.
The shorter parallel edge represents the data output.
Slanted sides represent control/select inputs.
Bus slash notation indicates multi-bit lines; a slash labeled with a number (e.g., or ) indicates a multi-wire bus rather than drawing individual parallel wires.
Schematics should never rely on physical spatial layout (such as top-to-bottom or left-to-right) to deduce select codes; explicit numeric labels (
0,1,2,3) identify the active binary state mapped to each input.
Implementation of a 16-by-4 multiplexer in Logisim:
Four 4-bit input buses are defined: , , , and .
The circuit is built using four 4-to-1 single-bit multiplexers:
Multiplexer 3 receives to produce .
Multiplexer 2 receives to produce .
Multiplexer 1 receives to produce .
Multiplexer 0 receives to produce .
Two select lines, and , are routed in parallel to the select inputs of all four multiplexers.
Once one single-bit 4-to-1 multiplexer block is constructed, it can be replicated via copy-and-paste for the remaining three bit positions.
In structured computer science curricula, pure programming assignments (typically five in total) terminate before transitioning into applied digital logic and electronics homework assignments.
Circuit Synthesis Methodologies and Universal Decoder Logic
Classical combinational logic design follows a four-step pipeline:
Construct a truth table defining desired outputs for every input permutation.
Extract the canonical Boolean sum-of-products equation from rows with an output of logic .
Simplify the equation using Boolean algebra theorems or Karnaugh mapping (K-maps).
Synthesize the optimized circuit using discrete AND, OR, and NOT gates.
An alternative approach uses an -to- decoder as a universal logic generator, completely eliminating the algebraic reduction step:
Any 3-input combinational function has possible input states.
An active-high 3-to-8 decoder takes inputs and activates exactly one of its eight output lines for each unique input combination.
To implement any desired function, an OR gate is connected to the specific decoder output lines corresponding to truth table rows that require a logic .
Demonstration of decoder-based synthesis:
Assume an arbitrary 3-input circuit must output logic exclusively for input patterns
010,011,100, and111.The canonical unreduced Boolean expression is:
Inputs are wired directly into a 3-to-8 decoder.
Decoder output lines (
010), (011), (100), and (111) are wired into the inputs of a 4-input OR gate.For input
000, the decoder asserts line 0; because line 0 is disconnected from the OR gate, the overall output is .For input
010, decoder line 2 outputs a , which propagates through the OR gate to generate an output of .
Engineering trade-offs of decoder-based logic:
Disadvantages: Contains unminimized, redundant internal gates that consume more silicon surface area, dissipate more thermal energy, and cost more to assemble when constructed from discrete integrated circuits.
Advantages: Requires zero minimization effort, eliminates algebraic reduction errors, and uses standardized, reusable hardware.
Contemporary microelectronics economics:
Massive silicon integration makes gate overhead negligible for non-specialized tasks.
For example, microcomputers like the Raspberry Pi are routinely utilized for low-complexity control tasks (such as garage door automation or simple light switching).
In these applications, the workload utilizes far less than (often less than ) of the processor's compute capacity, but high-volume semiconductor manufacturing makes using an over-provisioned chip more cost-effective than developing custom, minimal logic.
Full Adder Design, Truth Tables, and Computational Theory
Building complex arithmetic units begins by isolating the smallest repetitive functional unit of binary addition.
Adding arbitrary binary columns requires accounting for three inputs: bit , bit , and the carry-in bit () generated by the preceding lower-order column.
Binary adder classifications:
Half Adder: Adds two single bits ( and ) and produces a Sum and a Carry-out, but lacks an input for a Carry-in.
Full Adder: Adds three single bits (, , and ) to produce a Sum () and a Carry-out ().
While the least significant bit (LSB) of an addition operation does not receive a carry from an earlier column, multi-bit adders typically implement full adders across all stages and set the LSB carry-in permanently to logic .
Full adder circuit architecture:
Requires three inputs: , , and .
Requires two distinct outputs: Sum () and Carry-out ().
Designing a full adder requires creating two concurrent combinational logic circuits driven by the exact same set of three inputs.
Exhaustive Truth Table for a Full Adder ( rows):
Sum () | Carry-out () | |||
|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 0 |
0 | 1 | 0 | 1 | 0 |
0 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 |
1 | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 1 | 1 |
Computational and philosophical foundation of digital circuits:
Digital computers do not possess conscious intelligence or an innate comprehension of mathematical concepts (e.g., a computer does not conceptualize that ).
Arithmetic operations inside a processor consist entirely of voltage potentials routed through networks of logic gates.
A digital circuit is the physical, real-world hardware implementation of an abstract mathematical truth table and its corresponding Boolean equations.
Processing arithmetic consists entirely of looking up predefined output mappings programmed by human circuit designers into physical silicon structures.