Bit j of the multiplicand AND bit i of the multiplier is one partial product. Row i is the multiplicand masked by multiplier bit i, shifted left by i.
An N by M unsigned multiplier forms N rows of M bits. The product needs N + M bits.
Four rows of four bits need 16 AND gates. Column c holds every product with i + j = c, and the heights below add to 16.
4x4 unsigned: rows = 4, bits per row = 4, AND gates = 4 x 4 = 16
column c holds partial products with i + j = c:
c: 0 1 2 3 4 5 6
height: 1 2 3 4 3 2 1
total = 1 + 2 + 3 + 4 + 3 + 2 + 1 = 16
product width = 4 + 4 = 8 bitsAn array multiplier adds the rows pairwise with ripple adders. Its depth grows linearly with N, so it stays small and regular but slows past a few bits.
Tall middle columns set the cost. Column 3 above holds 4 bits and needs the most compression.
16 AND gates. The product is 8 bits wide.
Column 3, with 4 partial products. It bounds the compression work.