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) − 1gate delays, including the initial AND gate delay in all cells, for an
n × narray. 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
n=4 but as per the formula of the book the gate delay of
nx n multiplier is
6(n-1)-1 which for
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.