Truncation keeps the low bits

Keeping the low k bits of a product is exact modulo 2^k. It suits wraparound arithmetic and silently corrupts anything else.

Only the specification decides which bits survive. The calc below pins the kept and dropped parts of one example.

a = 200, b = 150, exact product = 30000 = 0x7530
keep low 8 bits: 0x30 = 48
check: 30000 = 117 x 256 + 48 = 29952 + 48
keep low 12 bits: 30000 mod 4096 = 30000 - 7 x 4096 = 30000 - 28672 = 1328
kept value = product mod 2^k; the dropped 29952 is the truncation penalty at 8 bits

The final adder

Two compressed rows need one carry-propagate addition. A 4 by 4 product adds two 8-bit rows.

Ripple is fine at that width, and wider products favour the faster families from the Adders and Carry Structures topic. Which family wins varies with the library and the timing target.

Proving a small multiplier in Yosys

The script below builds a 4 by 4 array beside a behavioural multiply and proves them equivalent. It asserts the property with equivalence checking, not with brittle cell counts.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

read_verilog <<EOV
module mult_ref(input [3:0] a, input [3:0] b, output [7:0] p);
  assign p = a * b;
endmodule
module mult_arr(input [3:0] a, input [3:0] b, output [7:0] p);
  wire [7:0] pp0 = {4'b0, (a & {4{b[0]}})};
  wire [7:0] pp1 = {4'b0, (a & {4{b[1]}})} << 1;
  wire [7:0] pp2 = {4'b0, (a & {4{b[2]}})} << 2;
  wire [7:0] pp3 = {4'b0, (a & {4{b[3]}})} << 3;
  assign p = pp0 + pp1 + pp2 + pp3;
endmodule
EOV
hierarchy
proc
opt
equiv_make mult_ref mult_arr mult_equiv
equiv_simple
equiv_status -assert
log PASS: 4x4 array multiplier proved equivalent to behavioural multiply

Related topics

• Previous: Signed multiplication

• Adders and Carry Structures

• Equivalence Checking