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

Question

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 first 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.

Answer 1

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.