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
| Signal | Width | Role |
|---|---|---|
gate_delays | 32 | stimulus, the same for every design |
Full specification
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 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
| Rule | Detail |
|---|---|
| Function | {co, s} = a + b + ci for every input. |
| Delay budget | After any input change, the last change of s or co comes at most 4 gate delays later. |
| Gate delay | One cell, of any size: an AND5 takes the same 1 ns as an AND2 in this model. |
| Cells | Only 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. |
| Nets | Declare each net as a wire. The outputs s and co are wires too. |
| Names to avoid | cell 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