Storage of Scrambler Appendix 1_1

Storage of Scrambler Appendix 1.1 PhL 6.18.13 Appendix 1.1. Processing polynomials vs. processing integers. In this section, we will consider a series of questions which will bring out some distinctions between dealing with polynomials and dealing with integers. Question 1: Can we make a correspondence between multiplying polynomials and multiplying base-10 integers? For example, we might try to associate 5z2 + 1z + 4 with the base-10 integer 514. If we think of z = 10, this seems to be a reasonable association. Now let's multiply two polynomials: (3z+8)(5z+9) = (15z2 + 67 z + 72) On the other hand, we could write down this base-10 integer product: 38•59 = 2242 If we evaluate (15z2 + 67 z + 72) at z=10, we do in fact get 2242. However, note the following: 38•59 = 2242 (3z+8)(5z+9) = (2z3 + 2z2 + 4z + 2) We will now give a formal statement of why A B. ************************************************** Appendix A. A Tale of Two Rings Here we ask the question: Is there some kind of analogy between real numbers and polynomials when the real numbers are written in usual decimal notation and when the polynomials have coefficients which lie in Mod(10) so they can also be written in a decimal notation. We pursue this question first in terms of multiplication and then later division. 1. Multiplication Define an ∞-tuple of Mod(10) elements as something having this form .....xxxxxxx.xxxxxx....... For particular ∞-tuples, we need only show the required digits, as for example for 2242.457. That is, we ignore the infinite set of leading zeros and the infinite set of trailing zeros. (a) We can represent a base-10 number (like 2242.457) as an ∞-tuple of elements each of which lie in field Z10 = Mod(10). Such ∞-tuples themselves form a ring which has a 1-to-1 correspondence with the ring of real numbers R. Let's call this ring R1. We have a certain familiar rule for the multiplication of such ∞-tuples in R1. The rule is that we convert each ∞-tuple to a real number, get the product of the two real numbers, and then convert the result back to an ∞-tuple. This rule is very effectively implemented by a calculator. For example 22.16 * 3.42 = 75.7872 Since the real numbers form a field, R1 is also a field, but we are mostly concerned with its ring sense. (b) On the other hand, we can represent a polynomial f(z) having coefficients in Mod(10) as a an ∞-tuple of elements each in Z10 = Mod(10). For example, 22.16 = the ∞-tuple for polynomial f(z) = 2z1 + 2z0 + 1z-1 + 6z-2 The "decimal point" is placed just before any negative powers which might be present. Such ∞-tuples form a ring we shall call R2. We have a rule for multiplying these ∞-tuples; it is just "what we do" when we multiply polynomials whose coefficients lie in Mod(10). The result can also be represented as an ∞-tuple. For example (notice for example that 12z-4 is replaced by 2z-4 ) (2z + 2 + 1z-1+ 6z-2) (3 + 4z-1+ 2z-2) = (6z + 4 + 5z-1 + 6z-2 + 6z-3 + 2 z-4) It is easy to have Maple multiply polynomials in this manner, to verify the above hand calculation: The upshot is that, in ring R2 we have 22.16 3.42 = 64.5662 The ∞-tuple product here is not the real number 64.5622, it is the ∞-tuple which represents the polynomial shown above in R2. The point so far is that the product of two ∞-tuples depends on which ring these ∞-tuples belong to. In Section 3 (a) of Ref [Galois] this ring R2 is simply called R, and it is shown that it really is a ring and has a multiplicative identity. This ring can be defined just for "proper" polynomials (non-negative powers only), or for general polynomials (all powers allowed). (c) The real number multiplication shown in (1) above can be done as follows: 22.16 3.42 .4432 8.864 66.48 75.7872 In this process, carries are maintained both in computing partial product rows and then in adding up those rows. (d) The polynomial multiplication shown in (2) above can be done as follows: 22.16 3.42 .4422 8.844 66.38 64.5662 In this process, carries are discarded both in computing partial product rows and then in adding up those rows. This is the way Mod(10) math works. 2. Division Example 1 (a) We continue to represent a base-10 number (like 2242.457) as an ∞-tuple of elements each of which lie in field Z10 = Mod(10). As noted above, such ∞-tuples themselves form a ring R1 which has a 1-to-1 correspondence with the ring of real numbers R. We have a certain familiar rule for the division of such ∞-tuples in R1. The rule is that you convert each ∞-tuple to a real number, get the quotient of the two real numbers, and then convert the result back to an ∞-tuple. This rule is very effectively implemented by a calculator (such as Maple). For example 22.16 / 3.42 = 6.479532164...... Since this example is a rational number, the decimals go into a repeating pattern. For 70 digits, and one sees that 6.479532163742690058 479532163742690058 479532163742690058 479532163742690... (b) On the other hand, we can represent a polynomial f(z) as a an ∞-tuple of elements each in Z10 = Mod(10). For example 22.16 = the ∞-tuple for polynomial f(z) = 2z1 + 2z0 + 1z-1 + 6z-2 Such ∞-tuples form a ring R2. We have a rule for dividing these ∞-tuples; it is what we do when we do long division of polynomials whose coefficients lie in Mod(10). The result can also be represented as an ∞-tuple. For example (2z + 2 + 1z-1 + 6z-2) / (3 + 4z-1 + 2z-2) = 4z + 2 + 5z-1 + 4z-2 + 8z-3 + 0z-4 + 8z-5 + ... (c) To find the ratio of two ∞-tuples in R1, we can do long division by the usual method. For example, 6.479..... 342 | 22160000 2054 6 1640 1368 4 2720 2394 7 3260 3078 9 ....... Each time the divisor is multiplied by a quotient integer, there is carry. And each time there is a subtraction to obtain a new current dividend, there is borrow. (d) To carry out a polynomial division in R2, one method is to carry out the long division algorithm, armed with a multiplication and addition table for Mod(10). For example, things start off this way: 254808 ......... 342 | 2216.0000 268 4 636 684 2 520 500 5 200 268 4 420 426 8 40 00 0 400 426 8 ....... At each stage of the process, there is no carry when the divisor is multiplier by a quotient integer, and there is no borrow when the subtraction is done at each stage to get the new current divisor. Our conclusion about carries and borrows for division is thus very similar to that for multiplication found earlier. The above manual method for polynomial division in R2 is quite tedious but could of course be automated. For illustration, here is another method which allows a simple Maple evaluation of the quotient coefficients. We know that the division O(z) = I(z)/H(z) (with all positive and negative powers allowed) results in the following time-domain equation for the polynomial coefficients, in = . (1.9.5) Multiplying top and bottom by z2, our division example above becomes (we redefine I and H), (2z3 + 2z2 + 1z + 6) / (3z2 + 4z + 2) = I(z) / H(z) giving us a proper polynomial for H(z). In our ∞-tuple notation, this says 22.16/3.42 = 2216/342 . This last line is true not because we multiply top and bottom by 100, because the ratio does not refer to the division of real numbers. It is true because of the way polynomial division is defined: n(z)/d(z) = q(z) n(z) = q(z)d(z) [zsn(z)] = q(z) [zs d(z)] [zsn(z)]/ [zs d(z)] = q(z) . In general, we can therefore always slide the "decimal point" in numerator and denominator by the same number of positions in either direction, just as we can when dividing ∞-tuples in the real field R1. As a counterexample, suppose we were to multiply our division ratio above top and bottom by 5. We would get (everything is Mod(10)) : (2z3 + 2z2 + 1z + 6) / (3z2 + 4z + 2) = (10z3 + 10z2 + 5z + 30) / (15z2 + 20z + 10) = (5z) / (5z2) = z-1 // not true ! Now, given our new H(z) shown above, the time-domain equation simplifies to, in = = h0on + h1on+1 + h2on+2 . (1.9.5) This can be regarded as the following recursion relation, h2on+2 = in - h0on - h1on+1 or on+2 = (in/h2) - (h0/h2)on - (h1/h2)on+1 or on+2 = a in - bon - con+1 a ≡ (1/h2) b ≡ (h0/h2) c ≡ (h1/h2) in our example: a ≡ (1/3) = 7 b ≡ (2/3) = 4 c ≡ (4/3) = 8 The integer results for a,b,c are those of Mod(10). For example a = 3-1 = 7, since 3*7 = 21 = 1 b = 2*3-1 = 2*7 = 14 = 4 c = 4*3-1 = 4*7 = 28 = 8 . Using our usual manner of denoting the coefficients of I(z) and O(z) we have I(z) = i-3 z3 + i-2z2 + i-1z + i0 // in our example = 2z3 + 2z2 + 1z + 6 O(z) = o-1z + o0 + o1z-1 + o2z-2 + o3z-3 + ..... We know that the leading coefficient of O(z) is o-1 as shown just looking at our polynomial ratio. All oj prior to this vanish. Here then is Maple code to compute the oj coefficients for (2z3 + 2z2 + 1z + 6) / (3z2 + 4z + 2) : The first 20 terms of the quotient polynomial O(z) are then We can verify our truncated O(z) result by multiplying it times H(z) to see how close we come to I(z): We have now shown that our example polynomial division has this result, (2z + 2 + 1z-1+ 6z-2) / (3 + 4z-1+ 2z-2) = 4z + 2 + 5z-1 + 4z-2 + 8z-3 + 0z-4 + ..... We can write this in terms of R2 ring ∞-tuples in this manner 221.6 / 34.2 = 42.5480.... The ∞-tuple product here is not the real number 42.5488...., it is the ∞-tuple which represents the polynomial shown above in R2. From the Maple output we in fact have 22.16 / 3.42 = 42.5 480860620240 480860620240 480860620240 480 .... and we see that the sequence 480860620240 repeats forever. We conclude then by comparing the R1 and R2 ∞-tuple division notations: R1 22.16 / 3.42 = 6.479532163742690058 479532163742690058 479532163742690058 .... R2 22.16 / 3.42 = 42.5 480860620240 480860620240 480860620240 .... 3. Division Example 2 What happens now if we shuffle a pair of coefficients in the previous division example? Suppose we have this polynomial division of interest, where the 4 and 3 have been swapped, (2z + 2 + 1z-1 + 6z-2) / (4 + 3z-1 + 2z-2) = ??? As before multiply top and bottom by z2 to get (2z3 + 2z2 + 1z + 6) / (4z2 + 3z + 2) ≡ I(z) / H(z) . In the ∞-tuple world of the real number ring R1 we can write 22.16/4.32 = 2216/432 = 5.1 296 296 296 ..... with no complications. But something new appears in our R2 ring polynomial division. The numerator is unchanged, and the output sequence oj still begins with o-1 . The recursion relation is the same but with these new parameters on+2 = a in - bon - con+1 a ≡ (1/h2) b ≡ (h0/h2) c ≡ (h1/h2) in our example: a ≡ (1/4) b ≡ (2/4) c ≡ (3/4) Maple can do the polynomial division in terms of real polynomial coefficients, where in the last line we again verify the truncated quotient so obtained. The problem is that in our R2 ∞-tuple ring world we need a quotient polynomial which has coefficients in the ring Mod(10). It is easy to show that, for general Mod(2n), no even element has an inverse. For example, 4 does not have an inverse in Mod(10) since 4*0 = 0 4*1 = 4 4*2 = 8 4*3 = 12 = 2 4*4 = 16 = 6 4*5 = 20 = 0 4*6 = 24 = 4 4*7 = 28 = 8 4*8 = 32 = 2 4*9 = 36 = 6 Notice that 1 is missing from the list. One reason it is missing is that all the numbers in the right column must be even! Therefore, there is no way to write our quotient, (2z3 + 2z2 + 1z + 6) / (4z2 + 3z + 2) = (1/2)z +(1/8) - (3/32)z-1 + ..... such that the quotient has coefficients in Mod(10). What this says is this: in the ring R2, the quotient of the two polynomials does not exist. Thus we end up with the following conclusions for Example 2 R1 22.16 / 3.42 = 2216 / 342 = 6.479532163742690058 479532163742690058 .... R2 22.16 / 3.42 = 2216 / 342 = does not exist If instead of Mod(10) we were to use symbols from Mod(p) where p is a prime number, then all elements have inverses and this problem cannot arise. An example would be Mod(7) with digits 0,1,2,3,4,5,6. Of course in this case, the ratios for R1 would be written in base-7 math. ****************************** not what I want to say ***************** (2) In the polynomial world the notion of division is first described by n(z)/d(z) = q(z) + r(z)/d(z) where n d q and r stand for numerator denominator quotient and remainder. The ring R2 of polynomials however has no division operation called "/" it only knows about and +. We can rewrite the above equation in the following form where only these two operations appear n(z) = q(z)d(z) + r(z) So our same example requires us to do the following polynomial division (2z + 2 + 1z-1+ 6z-2) / (3 + 4z-1+ 2z-2) = q(z) + r(z)/ (3 + 4z-1+ 2z-2) which we write then as (2z + 2 + 1z-1+ 6z-2) = q(z) (3 + 4z-1+ 2z-2) + r(z) If we want Maple to compute the result we have to adjust so that both n(x) and q(x) are proper polynomials. Multiplying top and bottom by of z2 (twice) our division becomes (2z3 + 2z2 + 1z + 6) / (3z2 + 4z + 2) = q(z) + z2r(z)/ (3z2 + 4z + 2) Here is the Maple code to do the division The result is this: q(z) = 4z + 2 r(z) = 5z-1 + 2z-2 and the last Maple line verifies the result. We can do this verification as well by hand (remember that everything is Mod(10) math: (2z + 2 + 1z-1+ 6z-2) = q(z) (3 + 4z-1+ 2z-2) + r(z) ? (2z + 2 + 1z-1+ 6z-2) = (4z+2) (3 + 4z-1+ 2z-2) + 5z-1 + 2z-2 ? The right side may be evaluated as (2z + 6 + 8z-1) + (6 + 8z-1 + 4z-2) + 5z-1 + 2z-2 = 2z + 2 + 1z-1 + 6z-2 which agrees with the left side. The result of our example can then be written in terms of ∞-tuples in our ring R2 : 22.16/3.42 = 42.000 + 0.52/3.42 which is certainly a bizarre looking result. On the other hand we can represent a polynomial f(z) as a an ∞-tuple of elements each in Z10 = Mod(10). For example 22.16 = the ∞-tuple for polynomial f(z) = 2z1 + 2z0 + 1z-1 + 6z-2 Such m-tuples form a ring we shall call R2. We have a rule for multiplying these m-tuples; it is what we do when we do multiplication of polynomials whose coefficients lie in Mod(10). The result can also be represented as an ∞-tuple. For example (notice that 12z-4 is replaced by 2z-4 ) n(z)/d(z) = q(z) + r(z)/d(z) n(z) = q(z)d(z) + r(z) (2z + 2 + 1z-1+ 6z-2) (3 + 4z-1+ 2z-2) = (6z + 4 + 5z-1 + 6z-2 + 6z-3 + 2 z-4) so 22.16 3.42 = 64.5 662 **********************old original text from the appendix*********** (3) What we have pointed out above in our A B counterexample is that the two rings Z and Polys(zZ) are not the same. Once again Z-base-10: {38}•{59} = {2242} Polys(zZ): {38}•{59} = {156772} Well the reader might say it is pretty obvious that these two rings are different. For example we cannot represent 15 or 67 as a single base-10 digit. Also we would be in trouble if we tried to deal with a polynomial with a negative coefficient: (3z2 - 7z + 2) = ?= 3[-7]2 The thing on the right does not look much like a base-10 integer. This leads to a refinement of our previous question: Question 2: Can we make a correspondence between multiplying polynomials defined over the field Z10 = Mod(10) and multiplying base-10 integers? Now consider the same product of polynomials above but coefficients are in Z10: (3z+8)(5z+9) = (15z2 + 67 z + 72) = (5z2 +7z +2) Now we have eliminated the abovementioned objections namely we no longer have negative coefficients nor do we have coefficients that are larger than one digit. However we still have no correspondence between the above polynomial product and this integer product 38•59 = 2242. So we now have: Z-base-10: {38}•{59} = {2242} Polys(zZ10): {38}•{59} = {572} Why are these rings not the same? At the point (15z2 + 67 z + 72) we at least stood a chance but then when we map each coefficient into Z10 to get (5z2 +7z +2) we throw out information. There is no way to connect this polynomial with the integer 2242. This leads to the following observation: Fact: Doing polynomial multiplication in the ring Polys(zZ10) is the same as multiplying the corresponding base-10 integers if you ignore all carries. For example 59 38 02 57 . 572 This is exactly what one does when multiplying (3z+8)(5z+9) with coefficients in Z10. So we can now generalize the above to say: Fact: Multiplying polynomials with coefficients in the ring Zn corresponds to multiplying integers base-n provided that all carries are thrown out. Corollary: Multiplying polynomials with coefficients in the field GF(2) = Z2 corresponds to multiplying binary numbers provided all carries are thrown out. We are now ready for Question 3: Is there some corresponding statement we can make about dividing polynomials? Our first observation is one that we probably should have made earlier. Looking back at our long hand division of polynomials in Figure 5 or at the circuits of Figure 1.1 or 2 we realize that the coefficient hk of H(z) must have an inverse or we are dead in the water. For example the very first quotient symbol is (i0/hk) = i0 • (hk)-1. This leaves us with two options if we want to be thinking about integers: (1) Make sure polynomial coefficients are in a field not just a ring. In a field all elements have inverses. (2) Restrict to H(z) which have hk = 1. Such polynomials are called monic. Now assuming we do (1) or (2) we move to the analog for division of Question 2 above namely: Question 4: Can we make a correspondence between dividing polynomials defined over the field Z10 = Mod(10) and dividing base-10 integers? Here is an example: (5z2 + 3z + 1) / (z+2) = (5z + 3) + 5/(z+2) where we give both the quotient and remainder polynomials. Note that coefficients are not in Z they are restricted to Z10. Now consider the division of two corresponding base-10 integers: 531/12 = 44.25 = 44 + 25/100 It is hopefully clear that there is not much connection between (5z+3) and "44" and (5) and ".25". To make this very clear we write: 531/12 = 44.25 (5z2 + 3z + 1) / (z+2) = (4z + 4) + (2z+5)/(z+2) = (4z + 6) + 1/(z+2) This is no doubt quite obvious to the reader. However the next fact may be less obvious: Fact: Doing polynomial division in the ring Polys(zZ10) is the same as dividing the corresponding base-10 integers if you ignore all carries and borrows. First we review the above example: (5z2 + 3z + 1) / (z+2) = (5z + 3) + 5/(z+2) Now we do it with no-carry no-borrow long division: . 53 . 12 | 531 50. / 5*12 = 50 if no carry 31 36 5 / 31-36 = 5 if no borrow [ 1 - 6 = 1 + (-6) = 1 + 4 = 5 ] With multiplication of polynomials in Polys(zZ10) we never encountered borrows because there were never any subtractions. Multiplication consists of only additions. In contrast the process of long division involves both multiplications (involving possible carries) and subtractions (involving possible carries). We now generalize Fact: Doing polynomial division in the ring Polys(zZn) is the same as dividing the corresponding base-n integers if you ignore all carries and borrows. Corollary: Doing polynomial division in the ring Polys[zGF(2)] is the same as dividing the corresponding binary numbers if you ignore all carries and borrows. Summary: When dealing with multiplication and division of integers there is an interaction between the digit positions. This interaction is known as borrow and carry. For example when the coefficient in a base-10 digit becomes "too large" part of the information is transferred to the next digit on the left via a "carry". One can think of an integer base-z as a polynomial in powers of z but there is always this interaction implied by the arithmetic rules + - • /. In contrast in the multiplication and division of polynomials in z everything is carefully aligned with powers of the variable z. Information is never transferred between two unequal powers. We close this section with one final question: Question 5: How do we know that in polynomial division over some field F it is possible that the quotient may never terminate? Back in Section 1.3 we made this claim and appealed to an analogy with integer division by observing that 514.000000... /37 = 13.891891891891... gives a remainder which never terminates. The analogy is that dividing polynomials is "like" dividing integers and we might compare a non-terminating remainder polynomial with this situation involving integer division: 514/37 = 13 Remainder = 33 5140/37 = 138 Remainder = 34 51400/37 = 1389 Remainder = 7 514000/37 = 13891 Remainder = 33 5140000/37 = 138918 Remainder = 34 51400000/37 = 1389189 Remainder = 7 514000000/37 = 13891891 Remainder = 33 In retrospect we must now admit that dividing integers is really quite different from dividing polynomials so our analogy is not very convincing. A true answer to Question 5 will have to await the next chapter.