Combinational Logic Circuits

In all cases, it is about "selecting one path." A MUX selects one data path, a decoder converts an address into a chip select, and a priority encoder decides which request gets service first among multiple requests. Understanding their input constraints, active polarities, and transition timing is more useful than memorizing device names. This article takes selection and arithmetic as the main thread, mapping truth tables, gate-level structures, and actual interfaces.

"Memoryless" Does Not Mean "Zero Delay"

An ideal combinational circuit satisfies Y=F(X): given the current inputs, the steady-state output is unique and does not require past inputs to explain. It is typically implemented using a gate network without combinational feedback. Latches, flip-flops, counters, and shift registers store state and belong to sequential logic. Having an external clock is not a sufficient criterion: a latch can store data while its enable level is active, and a clockless feedback circuit may still have state or oscillate.

Real combinational logic requires time to stabilize after input changes. Propagation delay depends on the input-to-output path, rise/fall direction, supply voltage, temperature, and load; transient errors can occur during transitions. A functional truth table describes the steady-state result and cannot be used to infer that the output is correct at any given moment.

MUX: Selection and Logic Decomposition Are the Same Thing

For a 2:1 MUX with data inputs A and B, and select input S:

Y=¬S·A+S·B.

The inversion must be applied to S; ¬A·S+B·S is constantly 0 when S=0 and cannot perform 2:1 selection. A 2:1 MUX with a width of 8 bits means 8 data bits share a single select signal, not that a single 1-bit MUX can accommodate a byte.

Generally, any Boolean function can be expanded with respect to variable S as F=¬S·F|S=0+S·F|S=1, known as Shannon expansion. Connecting two sub-functions to a MUX turns algebraic decomposition into a circuit. For example, for F=A⊕B, when A is the select signal, the sub-function for A=0 is B, and for A=1 is ¬B, requiring only one inverter and one MUX.

A 4:1 MUX requires two select bits and can also be implemented using three 2:1 MUX units in a two-level tree: the first level selects within groups, and the second level selects between two groups. This involves three MUXes and two levels of delay; do not confuse the number of units with the path depth. Larger selection networks are also affected by select line fan-out, routing, and load.

A MUX itself does not keep track of which input is next. Parallel-to-serial conversion requires counters/state and sampling timing; glitch-free clock switching cannot be guaranteed directly by a standard data MUX because the select line changes at different levels of the two clocks, potentially creating short pulses.

Decoder: Active Polarity and Address Coverage Determine Chip Select Behavior

For an active-high enable E and inputs A₁A₀, an ideal active-high 2-to-4 decoder is: Y₀=E¬A₁¬A₀, Y₁=E¬A₁A₀, Y₂=EA₁¬A₀, Y₃=EA₁A₀. When E=1, exactly one output is 1; when E=0, all outputs are 0. Here, the one-hot state is a steady-state functional constraint.

Actual chips do not necessarily output active-high. The selected outputs of a 74HC138 are active-low; its two active-low enables must be low, and the other active-high enable must be high, otherwise all outputs are high. Therefore, when reading the datasheet, first confirm the enables, then see which line is pulled low. Nexperia: 74HC/HCT138 Truth Table

For example, in a 16-bit address space, an 8 KiB memory is placed at 0x8000～0x9FFF. A₁₅A₁₄A₁₃ must be 100, and the lower 13 bits are used for internal device addressing. The active-high hit condition is hit=A₁₅¬A₁₄¬A₁₃; if an active-high access signal is used to constrain actual access, the active-low chip select is CS_n=¬(hit·access). Decoding only A₁₅ would select everything from 0x8000 to 0xFFFF, causing the same chip to appear as a mirror image at multiple address windows.

When multi-bit addresses switch, the bits cannot arrive absolutely simultaneously, and the decoder output may briefly select the wrong device. In particular, unfiltered address decoding glitches must not directly become write pulses; the bus protocol must guarantee an address stability window, and appropriate read/write/access controls must be applied. Adding a register can change the sampling method, but whether it solves the problem depends on setup/hold times and system delay requirements.

Seven-segment display decoding does not have a one-hot output: a single digit usually lights up multiple segments, and one must also distinguish between common-anode/common-cathode and drive current. Decoders solve logical mapping but do not automatically possess sufficient LED drive capability.

Encoder: The Code Must Be Transmitted Along With "Code Valid"

A standard encoder usually requires one-hot inputs. A priority encoder allows multiple requests to be active simultaneously and outputs the code for one of them based on a fixed order. Assuming active-high four-way requests R₃ has the highest priority, then:

• valid=R₃+R₂+R₁+R₀;
• code₁=R₃+R₂;
• code₀=R₃+¬R₂·R₁.

For example, if requests 0110 are active simultaneously (R₂, R₁), the result should be code=10, valid=1; 0001 yields code=00, valid=1; 0000 yields code=00, valid=0. Without valid, it is impossible to distinguish between "no request" and "request from channel 0." Real devices may also provide group select and enable outputs for cascading; the request inputs and encoded outputs of a 74HC148 use active-low logic, so the above active-high formulas cannot be directly applied. TI: SN74HC148

A fixed-priority encoder always prioritizes the highest request and does not remember who has been waiting the longest. If fair round-robin is required, the last served position must be saved, becoming a stateful arbiter; furthermore, the output code does not mean service is complete; grant, accept, and request cancellation should be defined by the protocol.

Adder: From Single-Bit Operation to Bit Width and Overflow

A half adder handles A+B, outputting S=A⊕B, C=AB, satisfying the integer equation A+B=S+2C. A full adder additionally receives the carry-in from the lower bit Cᵢ:

Sᵢ=Aᵢ⊕Bᵢ⊕Cᵢ, Cᵢ₊₁=AᵢBᵢ+(Aᵢ⊕Bᵢ)Cᵢ.

A half adder is suitable for adding two bits where there is no input carry; it is not a physical limitation that it "can only be used in the least significant bit"; multi-bit addition usually uses full adders to facilitate cascading and support carry input.

Ripple carry propagates sequentially from the least significant bit. Let the generate term be Gᵢ=AᵢBᵢ and the propagate term be Pᵢ=Aᵢ⊕Bᵢ, then Cᵢ₊₁=Gᵢ+PᵢCᵢ. Expanding two levels gives C₂=G₁+P₁G₀+P₁P₀C₀: there is no need to wait for the intermediate carry output; one can directly calculate using the original inputs.

Look-ahead carry utilizes this expansion, with group or prefix structures further controlling logic depth. If one naively expands all terms into a large fan-in gate, one will encounter fan-in, load, and routing limitations; one cannot simply label any "look-ahead carry" as having a fixed O(log n) delay. Balanced prefix networks can achieve logarithmic logic depth under limited fan-in models, but actual chips are also affected by routing.

Carry and Overflow Answer Different Questions

When a 4-bit adder keeps only the lower 4 bits, the result wraps around modulo 16. 1111+0001 yields lower bits 0000 and carry 1: unsigned 15+1 exceeds the range, but signed two's complement −1+1=0 has no overflow. 0111+0001 yields 1000 and carry 0: unsigned 7+1 is normal, but signed range −8～7 overflows.

The overflow condition for two's complement addition is "the two operands have the same sign, but the result has a different sign," which can also be detected by XORing the carry-in and carry-out of the sign bit. Subtraction can reuse the adder via A+¬B+1; in this implementation, the final carry 1 indicates no borrow for unsigned subtraction, but processor flag naming and polarity must be checked against the architecture definition.

Comparators also require sign conventions: 1000 compared with 0111 is 8>7 in unsigned comparison, but −8<7 in four-bit two's complement. Unsigned comparison starts from the most significant bit, and the first differing bit determines the magnitude; for signed comparison, if the signs are different, the sign bit determines the result first, and the unsigned carry judgment cannot be directly applied.

Same bits, different carry and overflow?

Default 7+1 has no final carry but crosses the signed range into 1000. Change A to 1111: adding 1 carries, while signed −1+1 does not overflow. The last trace column is carry to the next bit, not the sum bit.

$$V=C_{in,MSB}\oplus C_{out,MSB}$$

LUT and HDL: How Combinational Functions Map to Programmable Devices

An n-input, 1-output LUT requires 2ⁿ truth table bits; it is not a "2ⁿ-input LUT." For example, a three-input function has eight input combinations, storing eight output bits, with the inputs serving as select addresses. SRAM-based FPGAs commonly implement this structure using configuration storage bits and select networks; actual implementations may split LUTs, use multi-output cells, dedicated carry chains, and logic blocks that vary by architecture, so it is inappropriate to summarize all products using a single LUT count.

When describing combinational logic in HDL, every output should be defined in all branches. Below is a continuous assignment for a 2:1 MUX in SystemVerilog:

assign y = sel ? b : a;

Omitting the output for a branch in a procedural block may imply "the branch holds the old value," inferring a latch; the key is not whether a clock is written, but whether the description requires memory. After synthesis, one should also check the inferred cells and timing paths. The product-term structure of PAL/GAL, macrocells of CPLDs, and LUTs of FPGAs are different implementation resources; the scale of functions and timing they can implement are limited, and one cannot assume that logic of any scale can be loaded into any device.

From Combinational Delay to Synchronous Timing Budget

After inserting combinational logic between registers, the simplified setup time condition for zero clock skew is:

Tclk ≥ tCQ,max + tcomb,max + tsetup + additional timing margin.

For example, for a teaching budget of tCQ=1 ns, worst-case combinational delay 7 ns, setup time 1 ns, and additional margin 1 ns, the period is at least 10 ns, with an ideal budget upper limit of 100 MHz. This is not the chip's measured frequency, nor does it replace static timing analysis for every path. The fastest path must also satisfy hold requirements; one cannot only check the longest path; clock skew, jitter, and external I/O constraints must be included in the actual analysis. MIT: Synchronous Combinational and Timing Constraints

The final register only masks intermediate glitches if sampling conditions are met. If glitches enter sensitive control paths such as clock, asynchronous reset, or write enable, side effects may have already occurred; clock domain crossing issues cannot be summarized as "just take one clock cycle."

Verify Functionality by Exhaustive Checking, Not Just One Example

The following verifies a 2:1 MUX, full adder, and priority encoder, and traverses the carry and signed overflow of four-bit addition. It verifies discrete functions and does not simulate gate delays, glitches, or electrical characteristics.

from itertools import product

for a, b, s in product((0, 1), repeat=3):
    assert ((1-s)*a | s*b) == (b if s else a)
    total = a+b+s
    out = a ^ b ^ s
    carry = (a & b) | ((a ^ b) & s)
    assert total == out + 2*carry

for req in range(16):
    r0, r1, r2, r3 = [(req >> i) & 1 for i in range(4)]
    valid = r0 | r1 | r2 | r3
    code = ((r3 | r2) << 1) | (r3 | ((1-r2) & r1))
    assert valid == int(req != 0)
    assert code == (req.bit_length()-1 if req else 0)

signed = lambda x: x if x < 8 else x-16
for a, b in product(range(16), repeat=2):
    result = (a+b) & 15
    carry = (a+b) >> 4
    overflow = ((a ^ b) & 8) == 0 and ((a ^ result) & 8) != 0
    assert carry == int(a+b > 15)
    assert overflow == (not -8 <= signed(a)+signed(b) <= 7)

print("MUX, Full Adder, Priority Encoder, and 256 four-bit addition checks passed")

Continue Reading

• Logic Gates and Boolean Algebra: Karnaugh maps, redundant coverage, and static hazards.
• Sequential Logic Circuits: State, flip-flops, setup/hold, and synchronization.
• Logic Levels and Interface Physical Layers: Voltage ranges, output drive, and bus connections.