The question this layer answers
How do bits combine into arithmetic and control?
Switches become reasoning. This layer connects Gates, Adders, Registers, State machines to the rest of the computing stack.
Truth tables describe functions; circuits realize them
A combinational circuit's output is a function of its current inputs after propagation delay. A sequential circuit also depends on stored state. This distinction lets us separate an adder from a register, then combine them into a machine that computes over time.
A one-bit full adder receives A, B, and a carry-in C. The integer sum ranges from zero to three. Its low bit is S = A XOR B XOR C; its high bit is Cout = (A AND B) OR (C AND (A XOR B)). The carry expression says either A and B already produce a carry, or exactly one of them propagates the incoming carry.
| A | B | C | S | Cout |
|---|
| 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 |
Check each row by ordinary addition. This establishes the Boolean function for all eight input combinations; it says nothing yet about when outputs become valid.
Trace a ripple carry
Add unsigned 0111 and 0001, beginning at the right. Bit zero adds 1 + 1 + 0, emits 0, and carries 1. Bits one and two each add 1 + 0 + 1, again emitting 0 and carrying 1. Bit three adds 0 + 0 + 1, emitting 1. The four-bit result is 1000.
The bits are connected by a dependency chain. A ripple-carry design may need the low-bit carry to propagate through several stages before the high bit settles. Parallel-looking wires do not eliminate this dependency. Faster carry structures trade additional hardware and wiring for reduced carry depth.
Clocked state has a timing contract
A register samples its input around a clock edge. Inputs must meet setup and hold requirements. A simplified clock-period bound is Tclock ≥ clock-to-Q + maximum combinational delay + setup time + clock uncertainty. A separate minimum-delay check protects hold time. Raising the clock beyond the bound does not make the circuit compute faster correctly; it can make a register capture an intermediate value.
Unsigned carry and signed overflow also differ. Four-bit 0111 + 0001 = 1000 is valid unsigned 8, but overflows the signed two's-complement range −8 through 7. Meaning comes from the representation, not from the bit pattern alone.
Your explanation should cover: all input cases, the chain of dependencies, the capture time, and the intended numeric interpretation. Build the full-adder lab before assuming that a correct equation is already a reliable circuit.
Free Digital logic lessons
Composition turns switches into decisions
AND, OR, and NOT are sufficient to express any Boolean function; NAND or NOR alone are also functionally complete. A truth table specifies behaviour for every input combination. Algebra and circuit structure then provide implementations with different area, delay, power, and fan-out.
A 2-to-1 multiplexer outputs A when selector S is 0 and B when S is 1: (NOT S AND A) OR (S AND B). That one pattern routes register values, chooses ALU operands, and selects the next program counter. Control is often data selection expressed in gates.
Build arithmetic and see the carry path
For bits A, B, and carry-in, sum is their parity and carry-out is true when at least two inputs are true. Chaining full adders creates multi-bit addition. In a ripple-carry adder, each stage waits on the previous carry, making a simple local design into a global delay path.
In a fixed width, negating x means invert its bits and add one. Then subtraction x−y can use the same adder as x+(−y). Overflow is interpreted according to signed or unsigned meaning; the bit pattern alone does not carry that meaning.
Registers, clocks, and state over time
Feedback allows a circuit to retain a state. Latches and flip-flops constrain when that state may change; registers group bits; a clock creates agreed capture boundaries. Between boundaries, combinational logic computes the next state from current state and inputs.
Data must settle before a capture edge for setup time and remain stable after it for hold time. Violating either can leave a storage element metastable, temporarily neither a dependable 0 nor 1. Synchronizers reduce the probability that asynchronous uncertainty escapes into logic, but cannot make it mathematically impossible.
Make control explicit and test every transition
Name the states, inputs, transition function, and outputs. Moore-style outputs depend on state; Mealy-style outputs may also depend directly on inputs. Reachability analysis exposes dead or unsafe states, while temporal properties state what must always or eventually happen.
States can encode vehicle green, yellow, all-red, and pedestrian crossing. A button sets a pending-request bit so a brief press is not lost. Transitions respect minimum timing and the invariant that conflicting directions are never green together. The model cleanly separates request memory from phase control.
Derive, simplify, and verify a combinational circuit.
Track width, signedness, rounding, and overflow explicitly.
Calculate setup and hold margins, then handle asynchronous inputs.
Translate behavior into states, transitions, outputs, and register logic.
Practice lab: Construct a one-bit adder
About 30 minutes. Understand AND, OR, and NOT. XOR is true when exactly one of its two inputs is true. Write binary numbers using place values 1, 2, 4, 8.
A full adder takes bits a, b, and carry-in c. It produces sum bit s and carry-out k so that a + b + c = s + 2k. Define s = a XOR b XOR c and k = (a AND b) OR (c AND (a XOR b)).
- Enumerate all eight input combinations and verify the arithmetic identity for each.
- Connect four full adders to compute 0111 + 0001. Start with carry-in 0 and show each carry.
- Each adder has a worst-case carry delay of 2 ns. Estimate a four-stage ripple carry path, then explain why a real clock period needs more allowance.
Hint
Work from the least significant bit on the right. Decimal 7 + 1 is a useful cross-check, not a replacement for the trace.
Worked solution
For inputs 000, 001, 010, 011, 100, 101, 110, 111, the (s,k) results are (0,0), (1,0), (1,0), (0,1), (1,0), (0,1), (0,1), (1,1). In 0111 + 0001, the carry outputs from low to high positions are 1, 1, 1, 0 and the sum is 1000. The simple carry path is 4 × 2 = 8 ns. A registered circuit also needs clock-to-output delay, setup time, clock uncertainty, and any additional path delay. Sampling before signals settle can capture a transient value even when the truth table is correct.
- Cover all eight rows, including three input ones.
- Show carries rather than only the final answer.
- Explain the difference between logical correctness and timing correctness.
Change one assumption
Calculate 1111 + 0001. Explain what the fifth bit means and why dropping it gives a four-bit result of 0000.
Verify logic in both Boolean and physical time
A truth table is necessary for a combinational function, but temporal behavior and state transitions need their own contracts. Use exhaustive small cases before scaling a design.
1. Boolean proof and timing · allow 40 minutes
Simplify a function without overlooking a glitch
Let F=(A AND B) OR ((NOT A) AND C). Construct all eight truth-table rows. When B=C=1, prove that F should remain 1 as A changes. Explain how unequal physical delays through the two branches can briefly produce 0.
Show that adding the term B AND C leaves the Boolean function unchanged. Explain how that term can cover this particular static-1 hazard in an appropriate two-level implementation, and why the algebraic proof alone is not a proof that an arbitrary physical circuit is glitch-free.
Get a starting hint
Prove redundancy by splitting on A. To reason about the hazard, consider an interval when the old product term has turned off and the new one has not turned on.
Compare your reasoning with the worked solution
For ABC ordered 000,001,010,011,100,101,110,111, F is 0,1,0,1,0,0,1,1. With B=C=1, F=A OR NOT A=1. During a transition, the physical signals representing A and its inverted path need not change simultaneously; both product outputs can briefly be 0, giving a low pulse despite identical stable endpoint values.
If BC=1 and A=1, AB is already 1. If BC=1 and A=0, NOT(A)C is already 1. Thus every assignment enabled by BC was already enabled, so the additional term is logically redundant. While B and C remain high, a physically stable BC path can keep the OR output high across the A transition in the stated implementation.
This argument covers one transition pattern and assumes that path and its inputs behave as modeled. Multiple changing inputs, a different factorization, routing delays, or downstream sampling can introduce other hazards. Boolean equivalence describes settled values; a temporal guarantee requires a timing model and an implementation-level argument.
Check your reasoning
- Enumerate all eight rows consistently.
- Prove redundancy rather than assert a named identity.
- Separate stable truth values from transition behavior.
2. Bit-level trace · allow 35 minutes
One adder, two interpretations
Use a 4-bit adder that returns the low four result bits and a carry-out. Trace 7+3 and the two's-complement addition (−5)+(−4). Interpret each result as unsigned and signed. Derive the signed-overflow rule for addition from operand and result sign bits.
Explain why carry-out is neither necessary nor sufficient for signed overflow. Give a saturating signed result for both additions, and state why saturation and wraparound are different arithmetic contracts.
Get a starting hint
Write the input bit patterns first. Signed range is−8 through 7; unsigned range is 0 through 15.
Compare your reasoning with the worked solution
7=0111 and 3=0011 sum to 1010 with carry 0. Unsigned 10 is correct; signed interpretation−6 is wrong for the mathematical sum 10, so signed overflow occurs without carry-out. −5=1011 and−4=1100 sum to 10111: low bits 0111 and carry 1. Signed 7 is wrong for−9, again overflow; interpreting inputs as unsigned gives 11+12=23, outside the 4-bit unsigned range.
Signed addition overflows exactly when equal-sign operands produce an opposite-sign result. Adding different-sign operands cannot exceed either signed endpoint. Carry-out alone is insufficient:1111+0001 has carry 1 and result 0000, but signed−1+1=0 is valid.
Signed saturation returns 7 for 7+3 and−8 for−5−4. Wraparound returns the low bits interpreted under the selected representation. Saturation clamps at range endpoints; wraparound works modulo 16 at the bit-pattern level. A program, instruction set, or language must specify which behavior is intended; hardware carrying out an addition does not settle the higher-level contract.
Check your reasoning
- Keep unsigned values and signed interpretations separate.
- Supply counterexamples in both directions for carry-out.
- State the representable range before detecting overflow.
3. State-machine synthesis · allow 45 minutes
Build an overlapping sequence detector
Design a Mealy machine that reads one bit per clock and emits 1 exactly when the newest suffix is 101, allowing overlaps. Define states by the longest useful suffix already seen. Give a complete transition/output table and trace input 10101.
Explain why a machine that always returns to its empty state after detection misses an overlap. Add a synchronous reset input with priority over detection and state what happens when reset and the completing 1 arrive on the same edge. Propose exhaustive tests over every input string of length at most 6.
Get a starting hint
The useful suffixes before the next bit are empty,1, and 10. After recognizing 101, its final 1 can begin another match.
Compare your reasoning with the worked solution
Let S0 mean no useful suffix, S1 suffix 1, and S2 suffix 10. Transitions are: S0+0→S0/output 0; S0+1→S1/0; S1+0→S2/0; S1+1→S1/0; S2+0→S0/0; S2+1→S1/1. For 10101, states after bits are S1,S2,S1,S2,S1 and outputs 0,0,1,0,1.
Returning to S0 after the first detection forgets the final 1 at position 3, so it cannot use positions 3..5 as the second match. With a highest-priority synchronous reset, the sampled edge sets S0 and output 0 regardless of the incoming bit; therefore a simultaneous completion is suppressed by the specified policy. Another reset policy is possible but must be explicit.
Enumerate all 127 binary strings of lengths 0 through 6. For each position compare machine output with a separate oracle that checks whether the prefix ends in 101. Include reset before every possible state and reset concurrent with each input. The finite test suite is exhaustive for that length bound, while the state interpretation supports an induction proof for arbitrary lengths.
Check your reasoning
- Define states by information about the processed prefix.
- Include every state/input pair and reset priority.
- Distinguish bounded exhaustive tests from a general proof.
4. Timing constraints · allow 35 minutes
Fix hold timing without hiding setup timing
Two registers share an ideal zero-skew clock. Launch clock-to-Q is between 20 and 80 ps. The combinational path delay is between 20 and 500 ps. The receiving register requires 70 ps setup and 60 ps hold. Derive the minimum clock period and determine whether hold is satisfied.
You add a delay element with minimum delay 25 ps and maximum delay 40 ps. Recalculate both constraints. Explain why reducing clock frequency can repair one original violation but not the other in this zero-skew model.
Get a starting hint
The next-edge setup check uses maximum delays. Same-edge hold uses minimum delays.
Compare your reasoning with the worked solution
Setup requires T≥tCQ,max+tcomb,max+tsetup=80+500+70=650 ps, corresponding to at most about 1.538 GHz in this model. Hold requires tCQ,min+tcomb,min≥thold, but 20+20=40 ps<60 ps, so the path violates hold by 20 ps.
With the delay element, the minimum path becomes 20+20+25=65 ps, satisfying hold with 5 ps margin. The maximum path budget becomes 80+500+40+70=690 ps, lowering the maximum modeled frequency to about 1.449 GHz. The change helps the fast path but also slows the slow path.
Increasing the clock period gives data more time to arrive before the next capture edge and therefore helps setup. Hold concerns avoiding a too-early change after the current edge, so a longer period does not fix the original hold violation. Real analysis must include skew, jitter, uncertainty, and process variation with consistent signs; none should be silently assumed away outside this exercise.
Check your reasoning
- Use maximum delays for setup and minimum delays for hold.
- Recheck both constraints after the repair.
- Explain which clock edge each constraint references.
5. Boundary analysis · allow 40 minutes
A synchronizer cannot recover an unseen pulse
A source emits a 2 ns pulse. A destination clock samples every 10 ns. Draw an allowed alignment in which the destination never sees the pulse. Explain why adding a second flip-flop after the first does not guarantee event capture.
Design a request/acknowledgment handshake for infrequent events, stating when the source may send the next event. Contrast this with a toggle scheme and identify a rate assumption the toggle scheme needs. Explain the purpose and limits of a two-stage synchronizer for a single asynchronous control bit.
Get a starting hint
Metastability risk and missing an entire pulse are separate problems. A handshake can hold evidence of an event until it is observed.
Compare your reasoning with the worked solution
If destination edges are at 0 and 10 ns and the pulse is high from 3 to 5 ns, neither edge samples it. A second register only resamples the first register's output; it cannot reconstruct an event that never affected a sampled state.
For a level handshake, the source raises request and holds it until a synchronized acknowledgment is observed. The destination synchronizes request, handles it once, raises acknowledgment, then waits for request to fall before clearing acknowledgment. The source lowers request after acknowledgment and waits for acknowledgment to clear before issuing the next event. Explicit state prevents processing one held request repeatedly.
A toggle protocol changes a bit for each event; the destination detects a change after synchronization. If two toggles occur before observation, the bit can return to its old value and both events can disappear. It therefore requires a rate bound or acknowledgment.
A two-stage synchronizer gives an asynchronously sampled signal additional time to resolve before downstream use and reduces metastability-propagation probability. It does not make that probability zero, provide coherent multi-bit transfer, or guarantee that short pulses are sampled.
Check your reasoning
- Draw a missed pulse with explicit times.
- Define event ownership and handshake rearming.
- Separate pulse capture, metastability, and multi-bit coherence.
Study the underlying methods
Section project: Implement and verify a clocked digital controller
5 to 7 hours. Design a three-state traffic controller for a single vehicle direction and a pedestrian crossing. The states are vehicle-green, vehicle-yellow, and pedestrian-walk. Inputs are a clock tick, reset, and a one-bit pedestrian request. Use fixed integer durations, such as green at least three ticks, yellow two ticks, and walk three ticks. Latch requests until the crossing serves them. Define whether a request arriving during walk is already served or schedules a later crossing; choose one rule and apply it consistently. Outputs are vehicle-green, vehicle-yellow, vehicle-red, and pedestrian-walk signals plus the current state and timer. Implement a synchronous simulator in Python with an explicit current-state/next-state separation. Derive a transition table before coding and include a four-bit ripple-carry adder as an independently verified combinational component used to study arithmetic overflow, not as an unexplained library operation. Submit the transition specification, timing traces, and exhaustive checks of all adder inputs. This is a logic model, not a deployable traffic-safety controller. Connect the verified adder to the timer increment operation. Reject duration settings outside the four-bit range and show the reset or hold rule that prevents wraparound from accidentally prolonging a state.
Milestones
- Specify state encodings, reset behavior, request-latching policy, and exact tick boundaries.
- Build a full-adder truth table and compose four stages into a ripple-carry adder.
- Implement next-state logic and update all registers together on each simulated clock tick.
- Generate timing traces for isolated, repeated, and boundary-arriving requests.
- Check output safety invariants over exhaustive short input traces.
Acceptance criteria
- All 16*16*2 combinations of four-bit operands and carry-in match integer addition modulo 16 with the correct carry-out.
- Vehicle-green and pedestrian-walk are never asserted together on any checked trace.
- Reset has the documented priority over both timer expiration and a simultaneous request.
- A latched request cannot disappear before the explicitly defined service event.
- Every state duration matches the written tick convention, including requests arriving exactly at a boundary.
- The implementation computes next state from the old register snapshot, avoiding updates that depend on statement order.
Replace fixed durations with bounded programmable registers and determine which invalid configurations must be rejected to preserve the invariants.
Practise Digital logic free →