long division drawings and notes REVD

Not sure what this is, but it ends with my current drawing of one of the division how works. I guess there was some setup work to do before that drawing could be made. I do remember now that I had to decide exactly WHAT I was going to divide into what before doing the drawings. Can I talk about remainder without my "proper" polys? Let's go back to O(z) = I(z) / H(z) I(z) = i0 + i1z-1 + i2z-2 + ..... O(z) = okz-k + ok+1z-k-1 + ok+2z-k-2 + ..... Why is there no remainder showing in this equation? It is because O(z) is not truncated. Suppose we write O(z) = [okz-k + ok+1z-k-1 + ok+2z-k-2 + ... ok+sz-k-s] + [ok+s+1z-k-s-1 + ..... to ∞ ] = Otr(z) + tail(z) Then we have O(z) = I(z) / H(z) = Otr(z) + tail(z) = Otr(z) + Rem(z)/H(z) The whole idea of remainder does not work well here because Rem(z) could have any degree you want, there is no shape or form to anything. Remainder Concept #1 Let us now consider an input stream which has this form ........0,0,0, i0, i1, ......ir,0,0,0........ The input polynomial in this case ( the Z Transform of the above signal) is, I(z) = i0 + i1 z-1 + i2 z-2 + ........ + ir z-r . (1.3.3) We can rewrite this input sequence as: I(z) = z-r [ i0 zr + i1 zr-1 + i2 zr-2 + ........ + ir ] ≡ z-r Ir(z). (1.3.4) Here we have defined Ir(z) to be the proper polynomial shown in [..], having degree r. Since H(z) has degree k, and since I(z) has degree 0 (largest exponent in (1.3.3)), we know from (1.2.5) that O(z) must have degree 0-k = -k. This means that its first k symbols all vanish. This is easily interpreted in terms of Figure 1.1 since one has to wait k clocks before any non-zero symbols emerge from the circuit output, after i0 hits the input. (This will also be true of our second divider circuit to be given below. ) Thus we have, with a common time base, and assuming r > k, ij: ........0,0,0, i0, i1, ................ir,0,0,0........ oj ........0,0,0, 0,0,0......ok,ok+1 ....................  The output polynomial is then O(z) = ok z-k + ok+1 z-k-1 + .......... (1.3.5) = z-r [ ok zr-k + ok+1 zr-k-1 + ........ ]  z-r Or-k(z) where Or-k(z) is a (generally) infinite and non-proper polynomial of degree r-n (since in general it will have negative powers of z). Since a common factor z-r has been extracted in the last two definitions, we can write O(z) = I(z)/H(z) => Or-k(z) = Ir(z)/H(z) where now the polynomial ratio Ir(z)/H(z) is completely conventional since both Ir(z) and H(z) are proper polynomials, of degree r and k respectively. We can then talk about a quotient Q and a remainder R as follows, Ir(z)/H(z) = Q(z) + R(z)/H(z) where Q(z) = qr-kzr-k + qr-k=1zr-k-1 + .... q1z + q0 // r-k+1 terms, degree r-k R(z) = rk-1zk-1 + rk-2zk-2 + .... + r1z + r0 // k terms, degree k-1 But then O(z) = I(z) / H(z) = z-r Ir(z) / H(z) = z-r[ Q(z) + R(z)/H(z)] = [z-rQ(z)] + [z-rR(z)] / H(z) = [ qr-kz-k + qr-k-1z-k-1 + .... q1z-r+1 + q0z-r ] + [z-r R(z)] / H(z) Comparing this to O(z) = [ okz-k + ok+1z-k-1 + ok+2z-k-2 + ... + orz-r] + [ or+1z-r-1 + or+2z-r-2 + ... ] we can identify the first r-k+1 terms of O(z) with [z-rQ(z)] so that ok = qr-k ok+1 = qr-k-1 ..... ok+s = qr-k-s => oj = qr-j for j = k to r ..... or = q0 The remaining infinite number of terms of O(z) are then associated with [z-r R(z)] / H(z) [z-r R(z)] / H(z) = or+1z-r-1 + or+2z-r-2  + ...... which says R(z) / H(z) = or+1z-1 + or+2z-2  + ........ In the above discussion point of view, there is only one remainder, it is R(z). There is no sequence of remainders. The non-terminating Remainder in polynomial division. In Chapter 1 we discussed the use of either Figure 1.1 or Figure 1.5 as a polynomial divider. Both circuits perform the same function. In Figure 1.1, the remainder is "hidden", but in Figure 1.5 it is exposed: the state vector always holds the "current remainder". If we let the divider continue for n clocks after the last non-zero input symbol ir has arrived, we showed that Ir+n(z) / H(z) = Or+n-k(z) + R(n)(z)/H(z) (1.3.10) where I(z) = z-r-n Ir+n(z) = z-r-n [ i0zr+n + i1zr+n-1 + Ir(z) / H(z) = Or-k(z) + R(0)k-1(z)/H(z) (1.3.10) I(z) = z-r Ir(z) (1.3.4) O(z) = z-r Or-k(z) (1.3.5) O(z) = I(z) / H(z) (1.2.5) where ir was last non-zero input symbol. To review, Ir(z) was an Input polynomial of degree r, H(z) was the divisor polynomial of degree k, and Or-k(z) was the Output quotient polynomial of degree r-k. The Remainder R(0)k-1(z) is at most of degree k-1 . If some of its leading coefficients happen to vanish, it is of degree less than k-1. In Chapter 1 we used upper-case polynomial names to stress the notion of the Z Transform, and for the same reason we used the variable z. We were also trying to show explicitly how the degrees of all the polynomials come out right. Here we shall ignore all this baggage and rewrite the above in the simple form i0(x)/ h(x) = o0(x) + r0(x)/h(x) . We have not changed anything, we are just simplifying the notation. The 0 subscript is a relative time index. We think now of time t=0 just after the last non-zero symbol of the input stream has been shifted in to the divider. If the input stream is always zero from this point on, we can think of the circuit as the shift register generator discussed above which has its register state initialized with the remainder appearing in the above equation, r0(x). That is, the coefficients of this polynomial are the starting contents of the k registers. After one clock, we have: i1(x) / h(x) = [ x i0(x) ] / h(x) = o1(x) + r1(x)/h(x) The input polynomial i1(x) = x i0(x), because we have added a trailing 0 to the input symbol stream. After s clocks we would have is(x) / h(x) = [ xs i0(x) ] / h(x) = os(x) + rs(x)/h(x) If at some point the remainder vanished, the subsequent quotient symbols would be zeros. Conversely, if the remainder were never to vanish, the quotient symbol stream would go on forever. Fact 9: If h(x) of degree k is irreducible over GF(p), and if the first remainder r0(x) = Rem[ i0(x) / h(x) ] is non-zero, then all subsequent remainders rs(x)= Rem[ xs i0(x) / h(x) ] are non-zero, and the quotient sequence never terminates. Moreover, the sequence of remainders has period N which is the state vector period discussed above. This period N divides evenly into pk - 1. Furthermore, if h(x) is a primitive polynomial of GF(pk), then the state vector period is exactly pk - 1. Proof: Once we identify the remainder with the shift register state, everything follows directly from the Facts given above. Comment: In Appendix A we show an example of polynomial division (coefficients in Mod(10)) where the quotient polynomial never terminates and has a repeating sequence of symbols. Fact 9 gives us many examples of the same thing, where now coefficients are in GF(p) and where h(x) is an irreducible polynomial of order k. Fact 10: The state vector period of a Figure 1.5 shift register generator is the same as the period of h(x) . Proof: The period of a monic irreducible h(x) was defined rather mysteriously in Ref [GA] Chapter 5 as being the smallest value of n such that h(x) divides evenly into xn - 1. Let us assume that h(x) has period n, so we can then write (xn - 1)/h(x) = g(x), where g(x) is whatever quotient polynomial we get by this division. Then consider the remainder sequence noted above, for time s clocks after the input polynomial coefficients resume being 0, rs(x)= Rem[ xs i0(x) / h(x) ] Then we can evaluate rs+n(x) - rs(x) = Rem[ ( xn - 1)xs i0(x) / h(x) ] = Rem[ xs g(x)i0(x)] = 0. This shows that rs+n(x) = rs(x) , which says that the state vector period is n. Recall that the period n refers to the smallest power n such that (xn - 1)/h(x) = g(x). Similarly, the state vector period is the smallest integer n that makes the register state ( = remainder) repeat. Thus, we see that these two entities are one in the same. Summary: This section has focused on the state vector as being an element of a Galois Field GF(pk). For the Figure 1.5 circuit, this state vector can be identified with the remainder of polynomial division. We learned that the state vector period N of a Figure 1.5 style shift register generator is determined by the nature of h(x). We did not in this section have much to say about any particular register. For example, the output symbol sequence is basically the contents of the rightmost register in Figure 1.5. One wonders what the periodicity of the contents of a particular register might be, and thus, one wonders about the periodicity of the output data stream of a shift register generator. For the moment, we settle for the following: Fact 11: The period of any particular register of the Figure 1.5 circuit must integrally divide the state vector period N. Proof: Certainly the period of one register cannot exceed the period of the register set as a whole. If the whole register state repeats with period N, then so must any one register. However, it is easy to imagine that a particular register might have a smaller period. To be compatible with the state vector period, the state vector period would have to consist of an integral multiple of these smaller periods. Corollary: The output period of a Figure 1.5 shift register generator must be a divisor of the state vector period N. In the next section, we shall find a much stronger statement about the output period. **************************************************** If we trivially rewrite the above division as [z5O(z)] = [z5I(z)] / H(z) and then rename things so z5O(z) → O(z) and z5I(z) → I(z), and if we have the input stream terminate with i5, then the above "layout" for long division is exactly the same but the powers are all shifted by +5 : o3z2 + o4z1 + o5 ______________________________________________________________________________________________________________________________ h3z3 + h2z2+ h1z1 + h0z0 | i0z5 + i1z4 + i2z3 + i3z2 + i4z1 + i5 – o3h3z5 – o3h2z4 – o3h1z3 – o3h0z2 ---------------------------------------------------------------- Current Dividend #1 a1z4 + a2z3 + a3z2 + i4z1 + i5 – o4h3z4 – o4h2z3 – o4h1z2 – o4h0z1 ------------------------------------------------------- Current Dividend #2 b2z3 + b3z2 + b4z1 + i5 – o5h3z3 – o5h2z2 – o5h1z1 – o5h0 ----------------------------------------------- Current Dividend #3 c3z2 + c4z1 + c5 We now have a the division of two "proper" polynomials. In this case our timing diagram above looks like this: L1 L2 L2 C1 C2 C3 i: 0 i0 i1 i2 i3 i4 i5 o: 0 0 0 0 o3 o4 o5 o5 current dividend: #0 #1 #2 #3 After clock C3, the output bus has symbol o5 and the registers hold Current Dividend #3 which is in fact the remainder polynomial, since this is the first current dividend of degree less than that of the divisor H(z). The remainder is arranged such that (q3, q2, q1) = (c3, c4, c5) so the highest power coefficient c3 is sitting in the rightmost register q3. Application of another clock C4 will destroy this remainder. However, the registers after clock C4 will hold the remainder of a new division problem -- one in which a new symbol i6 is added to the input stream. In this case we write things using [z6O(z)] = [z6I(z)] / H(z) and here is the new diagram o3z3 + o4z2 + o5z1 + o6 ______________________________________________________________________________________________________________________________ h3z3 + h2z2+ h1z1 + h0z0 | i0z6 + i1z5 + i2z4 + i3z3 + i4z2 + i5z1 + i6 – o3h3z6 – o3h2z5 – o3h1z4 – o3h0z3 ---------------------------------------------------------------- Current Dividend #1 a1z5 + a2z4 + a3z3 + i4z2 + i5z1 + i6 – o4h3z5 – o4h2z4 – o4h1z3 – o4h0z2 ------------------------------------------------------- Current Dividend #2 b2z4 + b3z3 + b4z2 + i5z1 + i6 – o5h3z4 – o5h2z3 – o5h1z2 – o5h0z1 ----------------------------------------------- Current Dividend #3 c3z3 + c4z2 + c5z1 + i6 – o6h3z3 – o6h2z2 – o6h1z1 – o6h0z0 ------------------------------------------Current Dividend #4 d4z2 + d5z1 + d6z0 and the new timing diagram L1 L2 L3 C1 C2 C3 C4 i: 0 i0 i1 i2 i3 i4 i5 i6 o: 0 0 0 0 o3 o4 o5 o5 o6 current dividend: #0 #1 #2 #3 #4 Now after clock C4 the registers contain the Current Dividend #4 which is in fact the remainder of this new division problem, and now we have (q3, q2, q1) = (d4, d5, d6) . Even if it happens that i6 = 0, we still have a new division problem with a new remainder when we clock in i6 = 0. For example, suppose the first proper division problem was this (as shown above) (i0z5 + i1z4 + i2z3 + i3z2 + i4z1 + i5)/h(z) remainder = c3z2 + c4z + c5 If we then clock in i6 and it happens to be zero, the new proper division problem is this: (i0z6 + i1z5 + i2z4 + i3z3 + i4z2 + i5z + 0)/h(z) = { z (i0z5 + i1z4 + i2z3 + i3z2 + i4z1 + i5) } / h(z) remainder = d4z2 + d5z + d6 where d6 = – o6h0. The remainder is different because the dividend has one higher degree and so the division process has to continue through one more current dividend to get a current dividend of degree less than the original dividend. Conclusion: If we have an endless input stream i0, i1....... , then we can regard the contents of the registers of a Type B divider at any clock as holding the remainder of a certain proper polynomial division problem, while the output bus o will have delivered the quotient for that problem. Here is a list of these division problems for the case k = 3, where the first three rows correspond to 0 quotient and involve only the loading clocks: I(z) Remainder Quotient Clk i0 i0 0 L1 i0z + i1 i0z + i1 0 L2 i0z2 + i1z + i2 i0z2 + i1z + i2 0 L3 i0z3 + i1z2 + i2z + i3 a1z2 + a2z + a3 o3 C1 i0z4 + i1z3 + i2z2 + i3z + i4 b2z2 + b3z + b4 o3z + o4 C2 i0z5 + i1z4 + i2z3 + i3z2 + i4z + i5 c3z2 + c4z + c5 o3z2 + o4z + o5 C3 i0z6 + i1z5 + i2z4 + i3z3 + i4z2 + i5z + i6 d4z2 + d5z + d6 o3z3 + o4z2 + o5z + o6 C4 etc.