G4.5.1 Full Adder from Gates

EasyImplementIcarus · browser samples / server checksReview the topic

Build a full adder from at most five two-input cells by sharing one XOR between the sum and the carry.

Hardware context: One bit of a gate-array adder and an 8-bit ripple-carry adder built from tested full adders. Build a full adder from five two-input cells.

A gate array has room for five small cells per bit of an adder. The textbook majority carry, ab + a·ci + b·ci, does not fit beside the sum.

This is an Implement problem. Write fa_gates as a netlist of two-input cells from the read-only library, at most five of them. {co, s} must equal a + b + ci on every row.

The check applies the eight rows, one every 4 ns, and records co and s after each. It also counts your cells.

Signals in the Timeline

SignalWidthRole
script24input of each check
Full specification
The module (keep the name and the ports)
module fa_gates (
  input  logic a, b, ci,
  output wire  s, co           // {co, s} = a + b + ci
);
  // your netlist
endmodule
cells.sv: the cell library (read-only). Use only the inverter and the two-input cells
// 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 row.
CellsAt most five; only the inverter and two-input cells (AND, OR, NAND, NOR, XOR, XNOR).
NetsDeclare each internal net as a wire. The outputs s and co are wires too.

The result shows co and s after each of the eight rows, and whether you used more than five cells.

Examples

Example 1

Rows 0 to 7
Input
000, 001, 010, 011, 100, 101, 110, 111 (a b ci)
Output
co_step0 = no, s_step0 = no, co_step1 = no, s_step1 = yes, co_step2 = no, s_step2 = yes, co_step3 = yes, s_step3 = no, co_step4 = no, s_step4 = yes, co_step5 = yes, s_step5 = no, co_step6 = yes, s_step6 = no, co_step7 = yes, s_step7 = yes, over_budget = no

The rows in order: the sum is 1 for an odd number of 1s, and the carry for two or more.

Example 2

Only the Carry in Changes
Input
000, 001, 110, 111, 010, 011, 100, 101 (a b ci)
Output
co_step0 = no, s_step0 = no, co_step1 = no, s_step1 = yes, co_step2 = yes, s_step2 = no, co_step3 = yes, s_step3 = yes, co_step4 = no, s_step4 = yes, co_step5 = yes, s_step5 = no, co_step6 = no, s_step6 = yes, co_step7 = yes, s_step7 = no, over_budget = no

Each pair of steps differs in ci only. With a = b = 1 the carry stays 1 and only the sum follows ci.

Example 3

Rows with Two 1s
Input
011, 101, 110, 000, 110, 011, 101, 111 (a b ci)
Output
co_step0 = yes, s_step0 = no, co_step1 = yes, s_step1 = no, co_step2 = yes, s_step2 = no, co_step3 = no, s_step3 = no, co_step4 = yes, s_step4 = no, co_step5 = yes, s_step5 = no, co_step6 = yes, s_step6 = no, co_step7 = yes, s_step7 = yes, over_budget = no

Every row with exactly two 1s gives co = 1 and s = 0, whichever two inputs they are.

Constraints and Contract

  • Inputs are known 0/1 values. Each row is held for 4 ns before the outputs are read.
  • Keep the module name and the ports.

Hints

Hint 1

A half adder is one XOR and one AND. A full adder can be built from two of them and one more gate.

Hint 2

The first XOR gives p = a XOR b. The sum is p XOR ci, so the XOR of a and b is needed anyway.

Hint 3

A carry comes from a AND b, or from p AND ci. These two can never both be 1, so one OR joins them.

What the grader checks: Five directed and six seeded cases apply eight rows each, so every row appears several times. co and s are compared with a + b + ci computed in JavaScript. The source may hold only instances of the inverter and the two-input cells, at most five.

11 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

Rows 0 to 7

Input
000, 001, 010, 011, 100, 101, 110, 111 (a b ci)
Expected output
co_step0 = no, s_step0 = no, co_step1 = no, s_step1 = yes, co_step2 = no, s_step2 = yes, co_step3 = yes, s_step3 = no, co_step4 = no, s_step4 = yes, co_step5 = yes, s_step5 = no, co_step6 = yes, s_step6 = no, co_step7 = yes, s_step7 = yes, over_budget = no

The rows in order: the sum is 1 for an odd number of 1s, and the carry for two or more.

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

Icarus · browser samples / server checks