how Fig 7 works

This is the Title PhL 3.26.05 This has been installed. Operation of the Figure 7 Polynomial Multiplier As we have seen, the polynomial multiplier of Figure 7 generates a product of this form O(z) = z-k H(z) I(z) Recall that the input polynomial, output polynomial, and divisor polynomial have these forms, where for each we put the highest power of z on the left: I(z) = i0 + i1 z-1 + i2 z-2 + ....... O(z) = o0 + o1 z-1 + o2 z-2 + ....... H(z) = h3z3 + h2z2 + h1z + h0 . Although one can draw pictures for general k, things are very much clearer of we take a specific k value, so consider the following k=3 case of Figure 7. Recall that the registers are all initialized to zero. Figure 7 Multiplier with k = 3 To demonstrate the operation, we first write out a bunch of symbols, then explain them below: h3z3 + h2z2 + h1z1 + h0z0 .... + i3z-3+ i2z-2 + i1 z-1 + i0z0 --------------------------------------- i0h3z3 + i0h2z2 + i0h1z1 + i0h0z0 i1h3z2 + i1h2z1 + i1h1z0 + i1h0z-1 i2h3z1 + i2h2z0 + i2h1z-1 + i2h0z-2 i3h3z0 + i3h2z-1 + i3h1z-2 + i3h0z-3 i4h3z-1 + i4h2z-2 + i4h1z-3 + i4h0z-4 i5h3z-2 + i5h2z-3 + i5h1z-4 + i5h0z-5 **** + ***** + ***** + ... ***** + ***** + ... ***** + ... ------------------------------------------------------------------------------------------- o0z3 + o1z2 + o2z1 + o3z0 + o4z-1 + o5z-2 + o6z-3 + o7z-4 + o8z-5 .. = z3 [ o0z0 + o1z-1 + o2z-2 + o3z-3 + o4z-4 + o5z-5 + o6z-6 + o7z-7 + o8z-8 .. ] First of all, when multiplying two polynomials by hand, one is certainly allowed to arbitrarily order the powers in each polynomial as one wants. In the above we have H(z) with its highest power on the left, but we show I(z) with its highest power on the right. We then mechanically do the multiplication as we were taught in grade school. The rightmost element i0z0 of I(z) is multiplied by H(z) as shown to get the first row. Then the next multiplier element i1z-1 of I(z) is multiplied by H(z) as shown to get the second row, and so on. The rows are aligned so that powers of z match in each column. Normally these rows march to the left, but because I(z) has negative powers, they march to the right. After all the rows are written out, we add up the columns to get the overall product, as shown under the second dotted line. Since z3O(z) = H(z) I(z), we factor out z3 on the very last line to expose O(z) in the bracket. The idea here is that, for example, o2 = i0h1 + i1h2 + i2h3. To get each oj symbol, we have to add up the column of expressions above it. This column addition is performed by the set of adders appearing in Figure 7! We can associate a clock tick with each column going left to right. Each clock tick causes another input symbol to shift into the left end of the shift register, and causes all the symbols already in the register to shift to the right one position. At clock tick 0 the output is o0= i0h3 . At clock tick 1 the output is o1 = i0h2 + i1h3, and so on. By clock tick 3, the registers contain (i3,i2,i1,i0) and all three adders are "active" to produce a sum of four numbers as shown in the column above o3. As time moves on, the three adders continue to add four symbols of a column. If the input polynomial is finite so the last non-zero input is ir and all subsequent inputs are 0, the rows taper off the way they began. For example, if i5 were the last input, the above picture applies if we delete all the rows with asterisks. In this case, looking at the two polynomials being multiplied, it is clear that the largest power in the result is z3 and the smallest is z-5, so there will be 3-(-5)+1 = 9 symbols in the product, namely o0 through o8. In the general case where the last input is ir and H(z) has degree k, the product will have k-(-r)+1 = k+r+1 symbols. Not needed: i0h3z3 + i0h2z2 + i0h1z1 + i0h0z0 i1h3z2 + i1h2z1 + i1h1z0 + i1h0z-1 i2h3z1 + i2h2z0 + i2h1z-1 + i2h0z-2 i3h3z0 + i3h2z-1 + i3h1z-2 + i3h0z-3 i4h3z-1 + i4h2z-2 + i4h1z-3 + i4h0z-4 i5h3z-2 + i5h2z-3 + i5h1z-4 + i5h0z-5 ------------------------------------------------------------------------------------------- o0z3 + o1z2 + o2z1 + o3z0 + o4z-1 + o5z-2 + o6z-3 + o7z-4 + o8z-5 = z3 [ o0z0 + o1z-1 + o2z-2 + o3z-3 + o4z-4 + o5z-5 + o6z-6 + o7z-7 + o8z-8 ] *************************************************************************** [ ----------------- H(z) -------------------] .... + i3z-3 + i2z-2 + i1 z-1 + i0z0 --------------------------------------- i0[ ----------------- H(z) -------------------] i1 z-1[ ----------------- H(z) -------------------] i2 z-2[ ----------------- H(z) -------------------] i3 z-3[ ----------------- H(z) -------------------] i4 z-4[ ----------------- H(z) -------------------] i5 z-5[ ----------------- H(z) -------------------] ------------------------------------------------------------------------------------------- o0z3 + o1z2 + o2z1 + o3z0 + o4z-1 + o5z-2 + o6z-3 + o7z-4 + o8z-5 .. = z3 [ o0z0 + o1z-1 + o2z-2 + o3z-3 + o4z-4 + o5z-5 + o6z-6 + o7z-7 + o8z-8 .. ] Operation of the Figure 8 Polynomial Multiplier Again we consider the case k = 3 and this time we assume a finite input stream (i0, i1, i2, i3, i4). Figure 8 Multiplier with k = 3 We first write down the math, and then explain it below: h0z0 + h1z1 + h2z2 + h3z3 i4z-3 + i3z-3 + i2z-2 + i1 z-1 + i0z0 --------------------------------------- partial product #0 i0h0z0 + i0h1z1 + i0h2z2 + i0h3z3 i1h0z-1 + i1h1z0 + i1h2z1 + i1h3z2 -------------------------------------------------------- partial product #1 i1h0z-1 + a0z0 + a1z1 + a2z2 + i0h3z3 i2h0z-2 + i2h1z-1 + i2h2z0 + i2h3z1 --------------------------------------------------------------------- partial product #2 i2h0z-2 + b-1z-1 + b0z0 + b1z1 + a2z2 + i0h3z3 i3h0z-3 + i3h1z-2+ i3h2z-1 + i3h3z0 ---------------------------------------------------------------------------------- etc. i3h0z-3 + c-2z-2 + c-1z-1 + c0z0 + b1z1 + a2z2 + i0h3z3 i4h0z-4 + i4h1z-3+ i4h2z-2 + i4h3z-1 -------------------------------------------------------------------------------------------------- i4h0z-4 + d-3z-3 + d-2z-2 + d-1z-1 + c0z0 + b1z1 + a2z2 + i0h3z3 0 0 0 0 (since i5 = 0) -------------------------------------------------------------------------------------------------------------- 0 i4h0z-4 + d-3z-3 + d-2z-2 + d-1z-1 + c0z0 + b1z1 + a2z2 + i0h3z3 0 0 0 0 (since i6 = 0) ---------------------------------------------------------------------------------------------------------------------- 0 0 i4h0z-4 + d-3z-3 + d-2z-2 + d-1z-1 + c0z0 + b1z1 + a2z2 + i0h3z3 0 0 0 0 (since i7 = 0) ---------------------------------------------------------------------------------------------------------------------------- 0 0 0 i4h0z-4 + d-3z-3 + d-2z-2 + d-1z-1 + c0z0 + b1z1 + a2z2 + i0h3z3 This time, both the multiplicand H(z) and the multiplier I(z) are written with the largest power on the right. We then carry out the usual grade school multiplication method as shown which yields a sequence of partial products. For example, partial product #0 is the product if we account only for i0's contribution to the full product. Then partial product #1 is the full product if only i0 and i1 are accounted for. As we go down, we make up names for coefficients. For example, a0 ≡ i0h0 + i1h1 and later b0 ≡ a0 + i2h2. When i0 is at the input, the output is o0 = i0h3 as shown in red on the partial product #0 line. In each partial product, the three expressions shown in green are the contents of the three registers q1, q2, q3 and we could regard the expression in red as the output o captured by some register not shown off to the right. The black expression underneath each partial product represents the other set of inputs to the array of adders in Fig 7. On each clock, the result of an addition is strobed into the registers (green), an output in red is strobed out off the o bus, and the blue expressions are no longer stored anywhere since we don't need them. The first output (ignoring powers of z) is o0 = i0h3 and the second is o1 = a2 = i0h0 + i1h1, both in agreement with the Figure 8 circuit analysis. Since i4 is assumed to be the last non-zero input symbol, the machinery keeps running in its endgame with all-zero lines added in, and during this phase the three register contents are just shifted right to produce the last 3 output symbols, out after which the output goes to zero. h3z3 + h2z2 + h1z + h0z0 .... + i3z-3 + i2z-2 + i1 z-1 + i0z0 --------------------------------------- i0h3z3 + i0h2z2 + i0h1z1 + i0h0z0 i1h3z2 + i1h2z1 + i1h1z0 + i1h0z-1 ------------------------------------------- i0h3z3 + a1z2 + a2z1 + a3z0 + i1h0z-1 i2h3z1 + i2h2z0 + i2h1z-1 + i2h0z-2 i3h3z0 + i3h2z-1 + i3h1z-2 + i3h0z-3 i4h3z-1 + i4h2z-2 + i4h1z-3 + i4h0z-4 i5h3z-2 + i5h2z-3 + i5h1z-4 + i5h0z-5 **** + ***** + **** ... ***** + ****... *****... ------------------------------------------------------------------------------------------- o0z3 + o1z2 + o2z1 + o3z0 + o4z-1 + o5z-2 + o6z-3 + o7z-4 + o8z-5 .. = z3 [ o0z0 + o1z-1 + o2z-2 + o3z-3 + o4z-4 + o5z-5 + o6z-6 + o7z-7 + o8z-8 .. ] Operation of the Figure 2 Polynomial Divider Again we consider the case k = 3: Figure 2: The standard polynomial divider circuit with k = 3. To demonstrate the operation, we first write out a bunch of symbols, then explain them below: o3z-3 + o4z-4 + o5z-5 + o6z-6 + o7z-7 + o8z-8 + .... ______________________________________________________________________________________________________________________________ h3z3 + h2z2+ h1z1 + h0z0 | i0z0 + i1z-1 + i2z-2 + i3z-3 + i4z-4 + i5z-5 + ..... – o3h3z0 – o3h2z-1 – o3h1z-2 – o3h0z-3 ---------------------------------------------------------------- Current Dividend #1 a1z-1 + a2z-2 + a3z-3 + i4z-4 + i5z-5 + ..... – o4h3z-1 – o4h2z-2 – o4h1z-3 – o4h0z-4 ------------------------------------------------------- Current Dividend #2 b2z-2 + b3z-3 + b4z-4 + i5z-5 + .... – o5h3z-2 – o5h2z-3 – o5h1z-4 – o5h0z-5 ----------------------------------------------- Current Dividend #3 c3z-3 + c4z-4 + c5z-5 + .... – o6h3z-3 – o6h2z-4 – o6h1z-5 – o6h0z-6 ------------------------------------------ and on forever The divisor H(z) and dividend I(z) are written in the usual manner with the highest power to the left. We then perform the usual grade school long division process. In every vertical column, the powers of z match. The original dividend appears under the radical (current dividend #0). At each stage of the long division process we have a new "current dividend" as shown. The first three terms of each current dividend are shown in green. To give things a compact look, we define a lot of new symbols along the way, in this order (down each column, then to the next column): o3 ≡ i0/h3 o4 ≡ a1/h3 o5 ≡ b2/h3 o6 ≡ c3/h3 a1 ≡ i1 - o3h2 b2 ≡ a2 - o4h2 c3 ≡ b3 - o5h2 *** a2 ≡ i2 - o3h1 b3 ≡ a3 - o4h1 c4 ≡ a3 - o5h1 *** a3 ≡ i3 - o3h0 b4 ≡ i4 - o4h0 c5 ≡ i4 - o5h0 *** and so on. Notice how the output sequence o3, o4, o5 ...... is being computed in the first row of this little table. The three green terms (without the z powers) indicate the contents of the three registers, but in the order (q3, q2, q1) which is backwards from the ordering in Figure 2. Looking at the sequence of symbol definitions above, one realizes that only the green register contents are necessary to compute all the output coefficients on. It is assumed as usual that the shift register is cleared before i0 comes in. The input symbols just shift right in and appear as (i2, i1, i0) in registers (q1, q2, q3). This is so because up to this point there is no feedback on the o bus. These register contents are indicated by i0z0 + i1z-1+ i2z-2 in the original dividend, and as just noted, the order is reversed. After this point, the feedback is activated, and things progress as shown above. Even if the input sequence truncates after some ir, the output sequence in general continues forever. The exception of course is the case that I(z) is an exact multiple of H(z). Operation of the Figure 1 Polynomial Divider Again we consider the case k = 3: Figure 1: The scrambler style polynomial divider circuit with k = 3. We assume the registers are pre-cleared. When input i0 appears on the i bus, the D input to register q2 is then (i0/h3) and on the next clock edge this becomes the contents of q2. In two more clocks, this value will appear in q0 so (i0/h3) must be o3 ! In fact, at any instant in time, the three registers always hold the next three oj outputs since the registers form a simple shift register. This fact is crucial to understanding how this circuit works. We repeat the above long division layout but with different "coloration": o3z-3 + o4z-4 + o5z-5 + o6z-6 + o7z-7 + o8z-8 + .... ______________________________________________________________________________________________________________________________ h3z3 + h2z2+ h1z1 + h0z0 | i0z0 + i1z-1 + i2z-2 + i3z-3 + i4z-4 + i5z-5 + ..... – o3h3z0 – o3h2z-1 – o3h1z-2 – o3h0z-3 ---------------------------------------------------------------- Current Dividend #1 a1z-1 + a2z-2 + a3z-3 + i4z-4 + i5z-5 + ..... – o4h3z-1 – o4h2z-2 – o4h1z-3 – o4h0z-4 ------------------------------------------------------- Current Dividend #2 b2z-2 + b3z-3 + b4z-4 + i5z-5 + .... – o5h3z-2 – o5h2z-3 – o5h1z-4 – o5h0z-5 ----------------------------------------------- Current Dividend #3 c3z-3 + c4z-4 + c5z-5 + .... – o6h3z-3 – o6h2z-4 – o6h1z-5 – o6h0z-6 ------------------------------------------Current Dividend #4 d4z-4 + d5 z-5 + d6z-6 + .... – o7h3z-4 – o7h2z-5 – o7h1z-6 .... ---------------------------------- Current Dividend #5 e5 z-5 + e6z-6+ ... – o8h3z-5 – o8h2z-6 ------------------------------ Let's start in the middle of things to see what the adders in Figure 1 are doing. Consider the column of red expressions which has i4 at the top. At this time, the output is o4 and the input is i4. The adders are therefore computing the following sum at this time (based on the fact just stated about outputs-to-be) D input to q2 = (1/h3) * [i4 + (-h0)o4 + (-h1)o5 + (-h2)o6] where the expressions inside [...] match those of the red column just noted. On the next clock edge, this value is strobed into register q2 and it is then destined to become o7, which is shown in blue underneath the red column of expressions just noted. With the previous Figure 2 circuit, this same sum was in effect computed, but in a set of steps associated with the current dividends. Here the sum is computed in a single shot. If we look one clock later, we have the next column of red expressions being added to determine o8. And one clock earlier, we have a column adding up expressions to determine o6. Before this time, some of the adder inputs are 0 so the column of red expressions added has fewer than 4 elements. ************************************************************************* To demonstrate the operation, we first write out a bunch of symbols, then explain them below: (i0/h3)z-3+(b1/h3)z-4 + (d2/h3)z-5 + (f3/h3)z-6 + (j4/h3)z-7. ________________________________________________________ h3z3 + h2z2+ h1z1 + h0z0 | i0z0 + i1z-1 + i2z-2 + i3z-3 + i3z-4 – i0z0 – (i0/h3)h2z-1 – (i0/h3)h1z-2– (i0/h3)h0z-3 -------------------------------------------------------- b1z-1 + b2z-2 + b3z-3 + b4z-4 – b1z-1 – c2z-2 – c3z-3 – c4z-4 -------------------------------------------- d2z-2 + d3z-3 + d4z-4 – d2z-2 – e3z-3 – e4z-4 – e5z-5 ------------------------------------------- f3z-3 + f4z-4 + f5z-5 –f3z-3 – g4z-4 – g5z-5 – g6z-6 -------------------------------- j4z-4 + j5 z-5 + ... –j4z-4 – k5 z-5 + ... --------------------------- m5z-5 + ..... –m5z-5 – ..... ------------- and on forever o3z-3 + o4z-4 + o5z-5 + o6z-6 + o7z-7 + o8z-8 + .... ______________________________________________________________________________________________________________________________ h3z3 + h2z2+ h1z1 + h0z0 | i0z0 + i1z-1 + i2z-2 + i3z-3 + i4z-4 + i5z-5 + ..... – o3h3z0 – o3h2z-1 – o3h1z-2 – o3h0z-3 – o4h3z-1 – o4h2z-2 – o4h1z-3 – o4h0z-4 – o5h3z-2 – o5h2z-3 – o5h1z-4 – o5h0z-5 – o6h3z-3 – o6h2z-4 – o6h1z-5 – o6h0z-6 ------------------------------------------ and on forever (i0/h3)z-3+(b1/h3)z-4+(d2/h3)z-5+(f3/h3)z-6+(j4/h3)z-7 +(m5/h3)z-8 + ... ________________________________________________________ h3z3 + h2z2+ h1z1 + h0z0 | i0z0 + i1z-1 + i2z-2 + i3z-3 + i3z-4 – i0z0 – a1z-1 – a2z-2 – a3z-3 -------------------------------------------------------- b1z-1 + b2z-2 + b3z-3 + b4z-4 – b1z-1 – c2z-2 – c3z-3 – c4z-4 -------------------------------------------- d2z-2 + d3z-3 + d4z-4 – d2z-2 – e3z-3 – e4z-4 – e5z-5 ------------------------------------------- f3z-3 + f4z-4 + f5z-5 –f3z-3 – g4z-4 – g5z-5 – g6z-6 -------------------------------- j4z-4 + j5 z-5 + ... –j4z-4 – k5 z-5 + ... --------------------------- m5z-5 + ..... –m5z-5 – ..... ------------- and on forever The divisor and dividend are written in the usual manner with the highest power to the left. We then perform the usual grade school long division process. To give things a compact look, we define a lot of new symbols along the way, For example: a1 ≡ (i0/h3)h2 b1 ≡ i1 - a1 c2 ≡ (b1/h3)h2 d2 ≡ b2 - c2 and so on a2 ≡ (i0/h3)h1 b2 ≡ i2 - a2 c3 ≡ (b1/h3)h1 d3 ≡ b3 - c3 a3 ≡ (i0/h3)h0 b3 ≡ i3 - a3 c4 ≡ (b1/h3)h0 d4 ≡ b4 - c4 b4 ≡ i3 In general, even with a finite dividend as in this example, the quotient sequence goes on forever.