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 AA and BB using a single select line SS to produce output OO.

  • 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 A=(A1,A0)A = (A_1, A_0) and B=(B1,B0)B = (B_1, B_0), into a two-bit output O=(O1,O0)O = (O_1, O_0), two separate 2-to-1 multiplexers are deployed in parallel:

    • One multiplexer processes the low-order bits (A0A_0 and B0B_0) to generate O0O_0.

    • A second multiplexer processes the high-order bits (A1A_1 and B1B_1) to generate O1O_1.

    • The select lines of both multiplexers are tied directly together into a common control line.

    • When the common select line shifts to select BB, B1B_1 routes to O1O_1 and B0B_0 routes to O0O_0.

    • When the common select line shifts to select AA, A1A_1 routes to O1O_1 and A0A_0 routes to O0O_0.

  • Expanding to a four-bit bus with inputs A=(A3,A2,A1,A0)A = (A_3, A_2, A_1, A_0) and B=(B3,B2,B1,B0)B = (B_3, B_2, B_1, B_0) to yield output O=(O3,O2,O1,O0)O = (O_3, O_2, O_1, O_0) follows the exact same modular principle:

    • Four individual 2-to-1 multiplexers are used (one for each corresponding bit position 00, 11, 22, and 33).

    • All four multiplexer select lines are tied together so that all four output bits simultaneously switch to display either bus AA or bus BB.

  • 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 2322^{32} distinct memory addresses, which limits native physical memory access to 4 GB4\,\text{GB}.

    • Operating with more than 4 GB4\,\text{GB} of RAM on a 32-bit processor requires memory swapping and paging workarounds, which are highly inefficient.

    • A 64-bit address space provides 2642^{64} distinct addresses, doubling continuously past 32 bits (2332^{33}, 2342^{34}, up to 2642^{64}), 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 10 Mbps10\,\text{Mbps} 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 (A,B,C,DA, B, C, D, 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 (R0 through R7).

    • 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 SR1 and one to SR2).

    • Specifying register R1 configures the SR1 multiplexer to route all 16 bits of register R1 to the first adder terminal; specifying R2 configures the SR2 multiplexer to route register R2 to the second adder terminal.

  • Number of select lines required is determined by the power of two of the input count (NN inputs require log⁡2(N)\log_2(N) select lines):

    • A 2-to-1 multiplexer requires 1 select line (21=22^1 = 2).

    • A 4-to-1 multiplexer requires 2 select lines (22=42^2 = 4).

    • An 8-to-1 multiplexer requires 3 select lines (23=82^3 = 8).

    • A 16-to-1 multiplexer requires 4 select lines (24=162^4 = 16).

  • Internal logic gate design of a 2-to-1 multiplexer:

    • Consists of an inverter, two AND gates, and one OR gate.

    • Input SS connects directly to the second AND gate and through an inverter to the first AND gate.

    • Applying S=0S = 0 places a logic 00 on the second AND gate (blocking input BB) and a logic 11 on the first AND gate (allowing input AA 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, S1S_1 and S0S_0, decode into four discrete binary states: 00, 01, 10, and 11.

    • A logic 00 applied to any input of an AND gate forces its output to 00, blocking that channel from reaching the final OR gate.

    • Inversion bubbles on the AND gate inputs ensure that exactly one AND gate receives logic 11 on all of its select inputs for any given select code:

    • Code 00 enables the AND gate for input AA while blocking BB, CC, and DD.

    • Code 01 enables the AND gate for input BB while blocking AA, CC, and DD.

    • Code 10 enables the AND gate for input CC while blocking AA, BB, and DD.

    • Code 11 enables the AND gate for input DD while blocking AA, BB, and CC.

Multiplexer Schematics, Notation, and Logisim Implementation

  • Dimensional notation for multiplexers is designated as M×NM \times N:

    • The first number (MM) specifies the total number of input lines.

    • The second number (NN) specifies the bit width of the output (and the bit width of each input item).

    • Dividing the total inputs by the output bit width (M/NM / N) gives the number of distinct choices/channels.

    • A 4-by-1 (4×14 \times 1) multiplexer selects between 4 separate single-bit inputs to produce a 1-bit output using 2 select lines.

    • A 4-by-2 (4×24 \times 2) multiplexer selects between two 2-bit inputs to produce a 2-bit output using 1 select line.

    • A 16-by-4 (16×416 \times 4) multiplexer selects between four 4-bit numbers (A,B,C,DA, B, C, D) to produce a 4-bit output (16/4=416 / 4 = 4 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., 22 or 44) 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: A=(A3,A2,A1,A0)A = (A_3, A_2, A_1, A_0), B=(B3,B2,B1,B0)B = (B_3, B_2, B_1, B_0), C=(C3,C2,C1,C0)C = (C_3, C_2, C_1, C_0), and D=(D3,D2,D1,D0)D = (D_3, D_2, D_1, D_0).

    • The circuit is built using four 4-to-1 single-bit multiplexers:

    • Multiplexer 3 receives A3,B3,C3,D3A_3, B_3, C_3, D_3 to produce O3O_3.

    • Multiplexer 2 receives A2,B2,C2,D2A_2, B_2, C_2, D_2 to produce O2O_2.

    • Multiplexer 1 receives A1,B1,C1,D1A_1, B_1, C_1, D_1 to produce O1O_1.

    • Multiplexer 0 receives A0,B0,C0,D0A_0, B_0, C_0, D_0 to produce O0O_0.

    • Two select lines, S1S_1 and S0S_0, 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:

    1. Construct a truth table defining desired outputs for every input permutation.

    2. Extract the canonical Boolean sum-of-products equation from rows with an output of logic 11.

    3. Simplify the equation using Boolean algebra theorems or Karnaugh mapping (K-maps).

    4. Synthesize the optimized circuit using discrete AND, OR, and NOT gates.

  • An alternative approach uses an nn-to-2n2^n decoder as a universal logic generator, completely eliminating the algebraic reduction step:

    • Any 3-input combinational function has 23=82^3 = 8 possible input states.

    • An active-high 3-to-8 decoder takes inputs A,B,CA, B, C 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 11.

  • Demonstration of decoder-based synthesis:

    • Assume an arbitrary 3-input circuit must output logic 11 exclusively for input patterns 010, 011, 100, and 111.

    • The canonical unreduced Boolean expression is:     AˉBCˉ+AˉBC+ABˉCˉ+ABC\bar{A}B\bar{C} + \bar{A}BC + A\bar{B}\bar{C} + ABC

    • Inputs A,B,CA, B, C are wired directly into a 3-to-8 decoder.

    • Decoder output lines 22 (010), 33 (011), 44 (100), and 77 (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 00.

    • For input 010, decoder line 2 outputs a 11, which propagates through the OR gate to generate an output of 11.

  • 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 1%1\% (often less than 0.01%0.01\%) 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 AA, bit BB, and the carry-in bit (CinC_{in}) generated by the preceding lower-order column.

  • Binary adder classifications:

    • Half Adder: Adds two single bits (AA and BB) and produces a Sum and a Carry-out, but lacks an input for a Carry-in.

    • Full Adder: Adds three single bits (AA, BB, and CinC_{in}) to produce a Sum (SS) and a Carry-out (CoutC_{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 00.

  • Full adder circuit architecture:

    • Requires three inputs: CinC_{in}, AA, and BB.

    • Requires two distinct outputs: Sum (SS) and Carry-out (CoutC_{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 (23=82^3 = 8 rows):

CinC_{in}

AA

BB

Sum (SS)

Carry-out (CoutC_{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 2+5=72 + 5 = 7).

    • 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.