# Difficulty in understanding the analysis of worst-case signal propagation delay in an array multiplier

I was going through the text "Computer Organization" by Hamacher et. al. where I came across the concept of array multiplier. The design of 4 x 4 array multiplier is shown below.

What I could not figure out is the analysis of the gate delay in the text:

The worst-case signal propagation delay path is from the upper right corner of the array to the high-order product bit output at the bottom left corner of the array. This critical path consists of the staircase pattern that includes the two cells at the right end of each row, followed by all the cells in the bottom row. Assuming that there are two gate delays from the inputs to the outputs of a full-adder block, FA, the critical path has a total of 6(n − 1) − 1 gate delays, including the initial AND gate delay in all cells, for an n × n array. In the ﬁrst row of the array, no full adders are needed, because the incoming partial product PP0 is zero. This has been taken into account in developing the delay expression.

What I could figure out (possibly wrong) the start of the path and the end of the path is as shown with the red arrow in the figure below.

Since I could not figure out the line: "This critical path consists of the staircase pattern that includes the two cells at the right end of each row, followed by all the cells in the bottom row.", I cannot understand the analysis at all.

Can anyone help me trace out the path (with a rough diagram if possible) which the authors are talking about and briefly mark out the delays introduced?

I tried to work out on my own (not the method used by the book) and I found that the gate delay of producing the MSB by an nx n array as 9+3(n-1), which gives a gate delay of 18 for n=4 but as per the formula of the book the gate delay of nx n multiplier is 6(n-1)-1 which for n=4 gives 17. Given below is my work:

The values in red denote the gate delay (no. of gates involved in the path). And assuming the full adder to be as:

Where each gate (irrespective of the type) has a delay of 1 unit.

• Multiplying consists of a shift left which explains the latency in a combinational solution with prop delay shift left from the carry Nov 6, 2021 at 17:03
• You need to show us all of your work. If you didn't use the method used by the book, then show us the method that you used. Don't you understand what the book means by "two cells at the right end of each row"? Since this could be a homework or exam problem we expect to see substantial effort on your part. Nov 6, 2021 at 18:04
• The first row doesn't need full adders. Considering that, I think author's calculations are wrong here. Nov 6, 2021 at 21:13
• The first row doesn't need adders at all. The rightmost adder on each remaining row only needs to be a half-adder (presumably, only one gate delay, not two). Also, the leftmost adder on the second row is a half-adder. Therefore, I count a total of 14 gate delays from the upper-right inputs to the two MSBs of the product. However, even this estimate is overly pessimistic. There is in fact no combination of inputs that would actually cause a change to propagate along the entire length of that path. Nov 6, 2021 at 21:40
• The second row doesn't need a full adder at the left because there is no carry-out from the first row. Nov 6, 2021 at 22:03

## 1 Answer

Here's a version of the multiplier that shows the actual half- and full-adders required. I'm going to assume that AND gates and half-adders have one unit of delay from any input to any output, and full-adders have two units of delay.

simulate this circuit – Schematic created using CircuitLab

The longest path from any input to any output is highlighted in red. It runs from the m0, m1, q0 and q1 inputs to the p6 and p7 outputs. The numbers show the accumulated delay to that node from the inputs.

A general formula would be derived as follows:

• The first two rows have 4 units of gate delay
• The rows after that, except for the last, add 3 units each.
• The last row has 2 units per full adder, plus 1 unit for the half adder.

So, 4 + (N-3) × 3 + (N-1) × 2 + 1 reduces to 5 × N - 6. If N = 4, we get 20 - 6 = 14, as shown above.

But here's the thing — there's no combination of inputs that will actually cause a change to propagate along the full length of this path. There are only a few combinations in which a change in the LSB of either input will cause the MSBs of the output to change. As just one example, 12 × 10 = 120 (01111000), while 13 × 10 = 130 (10000010) and 12 × 11 = 132 (10000100). But if you write out the actual adding-up of the partial products, you'll find that the carries never propagate all the way from the beginning to the end of this chain of logic — instead, the output always changes as the result of a significantly shorter chain of logic.