G4.6.1 Carry Lookahead, Four Bits

MediumImplementIcarus · browser samples / server checksReview the topic

Build a 4-bit adder from unit-delay cells that settles within four gate delays by computing each carry from generate and propagate.

Hardware context: A 4-bit adder for a timer block, built from unit-delay cells. Build the carry-lookahead adder whose top carry does not wait for the carries below it.

A ripple-carry adder is correct but slow. Its carry passes through two gates in every bit, so the top carry of a 4-bit adder can need nine gate delays. A timer block needs the sum sooner: every output must stop changing within four gate delays of any input change.

This is an Implement problem. Write cla4 as a netlist of cells from the read-only cell library. Every cell takes one gate delay, whatever its number of inputs. The check changes the inputs, waits, and measures when the last output changed.

The idea is carry lookahead. For each bit, compute generate g = a AND b and propagate p = a XOR b. Then write every carry directly from g, p and the carry in, so that no carry waits for the carry before it.

Use only cell instances and wire or logic declarations without initial values. Port connections may use wires, literal bit or part selects, constants and concatenations. Operators, assignments and procedural code are refused before simulation. The cell count must be from 16 to 40.

Signals in the Timeline

SignalWidthRole
gate_delays32stimulus, the same for every design
Full specification
The module (keep the name and the ports)
module cla4 (
  input  logic [3:0] a,
  input  logic [3:0] b,
  input  logic       ci,
  output wire  [3:0] s,
  output wire        co
);
  // your netlist
endmodule
cells.sv: the cell library (read-only). Ports are (y, inputs...): the output comes first
// cells.sv: the unit-delay cell library (read-only).
// Every cell takes 1 time unit, whatever its fan-in. Ports are (y, inputs...): output first.
// Each cell adds 1 to the bench's cell counter when the simulation starts.
module INV   (output wire y, input wire a);                 not #1 (y, a);               initial tb.cells++; endmodule
module AND2  (output wire y, input wire a, b);              and #1 (y, a, b);            initial tb.cells++; endmodule
module AND3  (output wire y, input wire a, b, c);           and #1 (y, a, b, c);         initial tb.cells++; endmodule
module AND4  (output wire y, input wire a, b, c, d);        and #1 (y, a, b, c, d);      initial tb.cells++; endmodule
module AND5  (output wire y, input wire a, b, c, d, e);     and #1 (y, a, b, c, d, e);   initial tb.cells++; endmodule
module OR2   (output wire y, input wire a, b);              or #1 (y, a, b);             initial tb.cells++; endmodule
module OR3   (output wire y, input wire a, b, c);           or #1 (y, a, b, c);          initial tb.cells++; endmodule
module OR4   (output wire y, input wire a, b, c, d);        or #1 (y, a, b, c, d);       initial tb.cells++; endmodule
module OR5   (output wire y, input wire a, b, c, d, e);     or #1 (y, a, b, c, d, e);    initial tb.cells++; endmodule
module NAND2 (output wire y, input wire a, b);              nand #1 (y, a, b);           initial tb.cells++; endmodule
module NOR2  (output wire y, input wire a, b);              nor #1 (y, a, b);            initial tb.cells++; endmodule
module XOR2  (output wire y, input wire a, b);              xor #1 (y, a, b);            initial tb.cells++; endmodule
module XNOR2 (output wire y, input wire a, b);              xnor #1 (y, a, b);           initial tb.cells++; endmodule

RuleDetail
Function{co, s} = a + b + ci for every input.
Delay budgetAfter any input change, the last change of s or co comes at most 4 gate delays later.
Gate delayOne cell, of any size: an AND5 takes the same 1 ns as an AND2 in this model.
CellsOnly instances of the library cells, from 16 to 40 of them. Connect by position (output first) or by name: .y, .a, .b, .c, .d, .e.
NetsDeclare each net as a wire. The outputs s and co are wires too.
Names to avoidcell and bit are reserved words; do not use them as names.

Each case sets a starting input and then makes four input changes. The result shows {co, s} after each change. It also shows how far the slowest change was over the budget, in gate delays. The last field says whether the cell count is out of range.

Examples

Example 1

A Carry That Crosses All Four Bits
Input
start at f + 0 + 0; then f + 0 + 1, f + 0 + 0, f + 1 + 0, f + 0 + 0 (a + b + ci, hex digits)
Output
sum_change1 = 16, sum_change2 = 15, sum_change3 = 16, sum_change4 = 15, gate_delays_over_budget = 0, cell_count_out_of_range = no

With a = f and b = 0, raising ci sends a carry through every bit: the sum goes from 15 to 16. A ripple adder needs 9 gate delays here. Lookahead needs 4.

Example 2

Every Bit Generates
Input
start at 0 + 0 + 0; then f + f + 0, f + f + 1, 0 + 0 + 1, 0 + 0 + 0 (a + b + ci, hex digits)
Output
sum_change1 = 30, sum_change2 = 31, sum_change3 = 1, sum_change4 = 0, gate_delays_over_budget = 0, cell_count_out_of_range = no

f + f is 30 and f + f + 1 is 31. Each bit makes its own carry, so no carry has far to travel.

Example 3

A Carry Born in Bit 0 and Killed in Bit 3
Input
start at 7 + 0 + 0; then 7 + 1 + 0, 7 + 0 + 0, 7 + 0 + 1, 7 + 8 + 1 (a + b + ci, hex digits)
Output
sum_change1 = 8, sum_change2 = 7, sum_change3 = 8, sum_change4 = 16, gate_delays_over_budget = 0, cell_count_out_of_range = no

7 + 1 is 8. The carry from bit 0 passes bits 1 and 2. It stops in bit 3, where neither operand has a 1.

Constraints and Contract

  • Inputs are known 0/1 values. Each input change is held for 12 ns before the outputs are read.
  • Keep the module name and the ports. A carry between your own cells may use any net names.

Hints

Hint 1

Start with the first level: four two-input XOR cells give p and four two-input AND cells give g. Every later signal is built from these and ci.

Hint 2

The carry into bit 1 is g0 OR (p0 AND ci). Write the carry into bit 2 the same way. Then replace the earlier carry inside it by its own expression. Only g, p and ci remain.

Hint 3

Count the levels on your slowest path: p and g, then one AND, then one OR, then the sum XOR. That is four. If a carry passes through an AND and an OR in every bit, it ripples and misses the budget.

What the grader checks: Eight directed and twelve seeded scripts each make four input changes. After each change, the sum is compared with a + b + ci computed in JavaScript. The time of the last output change is compared with a budget of 4 gate delays. In this model every cell takes one time unit. The cell count must be from 16 to 40. The model ignores fan-in, fan-out and wires, so it shows the structure of the adder and not a real delay.

20 checks on Icarus · browser samples / server checks. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 2 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

A Carry That Crosses All Four Bits

Input
start at f + 0 + 0; then f + 0 + 1, f + 0 + 0, f + 1 + 0, f + 0 + 0 (a + b + ci, hex digits)
Expected output
sum_change1 = 16, sum_change2 = 15, sum_change3 = 16, sum_change4 = 15, gate_delays_over_budget = 0, cell_count_out_of_range = no

With a = f and b = 0, raising ci sends a carry through every bit: the sum goes from 15 to 16. A ripple adder needs 9 gate delays here. Lookahead needs 4.

Run samples executes all 3 public checks. Check all tests runs 20 checks on the server.

Icarus · browser samples / server checks