Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada
| |
|
|
EE4253 Digital Communications
Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada |
| |
Manipulation of long binary values requires some special techniques. The polynomials notation lends itself to computation in hardware using only shift registers and exclusive-OR (XOR) gates. Once the mathematics of polynomials has been defined, the concept of prime polynomials can be introduced.
1. Single bit binary values are defined on a set {0,1} which constititutes a finite field or Galois field labeled GF(2). For this field the addition operation is defined as being modulo 2 addition:
0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0
Significantly, this is equivalent to the exclusive-OR operation. The set satisfies the definition of an additive group: the properties of closure, identity, inverse, and associative can be confirmed for
addition in this set. The operation is also commutative.
For this field the multiplication operation is defined as:
0 * 0 = 0 0 * 1 = 0 1 * 0 = 0 1 * 1 = 1
While this is like normal multiplication, it is also equivalent to a logical AND operation.
The set satisfies the definition of a multiplicative group: the properties of closure, identity, inverse, and associative can be confirmed for multiplication in this set (excluding the zero which has no inverse). The operation is also commutative.
In summary the set {0,1} is both an additive group and multiplicative group and the operation of multiplication is distributive over addition (e.g. a * [b+c] = a*b + b*c ) both operations are commutative and the set defines a field named GF(2). This field forms the basis for larger fields of the form GF(2m).
These mathematical definitions constitute the theoretical underpinnings for all the manipulations to follow. The rules of everyday math work on real numbers because the real numbers form a field. The same familiar operations work with the Galois field GF(2) with the major difference being that modulo 2 addition is used.
2. Multi-bit binary values can be represented as polynomials with coefficents from GF(2) or the set {0,1}.
For example, the 6-bit binary value 110011 can be written as
and simplified as:
or as polynomial terms in brackets as:
The degree of a polynomial is the power of the highest non-zero coefficient. The above example shows a polynomial of "degree 5".
3. Polynomials can be manipulated using the usual arithmetic rules, in particular, the polynomial powers add under multiplication, as expected.
Example 1: (110011) x (10) = (1100110) can be written as:
4. Polynomials always use modulo 2 addition as described above.
Example 2: (11) x (11) can be computed as:
11
x 11
----
11
+ 110
----
101 Note modulo 2 addition
and as a polynomial: Do not make the mistake of thinking "3 x 3 = 9". This is not your usual binary math!
5. The rules for subtraction follow from addition (if 1+1=0, then 0-1=1 !!), and are also equivalent to the exclusive-OR operation, as:
0 - 0 = 0 0 - 1 = 1 1 - 0 = 1 1 - 1 = 0
6. With these rules in mind, the division (x2 + 1) / (x + 1) can be accomplished:
1 1 = x + 1
________
1 1 ) 1 0 1
1 1
----
1 1
1 1
----
0 no remainder
Therefore: x2 + 1 = (x + 1)(x + 1).
We say that (x + 1) is a factor of x2 + 1. If a polynomial has no factors other than 1 and itself, it is a prime polynomial.
Note that (101) is not the decimal value 5, and (101) is not prime! [ Table of Factors ]
Since prime polynomials are of some importance, it is worthwhile to review some concepts of prime numbers in the familiar decimal world..
The prime numbers {2,3,5,7,11,13,17,19,23,29,31,37...} have no factors other than 1 and themselves.
To determine if a number such as 37 is prime, it can be tested against all possible factors from 2 to 37. In practice, we would immediately recognize EVEN numbers (is 100034 prime?) and proceed by testing for only ODD factors. Finally, we note that testing can stop when the square root of the number is reached.
To test if 37 is prime, we need only try {2,3,5} stopping after the square root of 37.
Similarly, to test if 137 is prime, we need only try {2,3,5,7,9,11}
(Although we would probably not bother trying 9 after eliminating 3 as a factor.)
By recalling these rules, much unnecessary division can be avoided even when testing relatively large numbers. Further optimization of prime number testing is unnecessary at this level.
Following the logic outlined above, polynomials can readily be tested for possible factors:
If the lowest term in a polynomial is not 1, then x is a factor. This is equivalent to checking EVEN integers.
Example 3:
Consider the polynomial: (1100110) = x6 + x5 + x2 + x
By inspection, this cannot be prime since (10) = x is a factor.
Example 4:
Check if the following polynomial is prime:
1. Since the smallest term is 1, then x is not a factor.
2. The highest term is x7, terms up to x3 must be tested (corresponding to the square root).
We would need to test, at most, the following 'ODD' polynomials:
a. 11 : x + 1
b. 101 : x2 + 1 = (x+1)(x+1)
c. 111 : x2 + x + 1
d. 1001 : x3 + 1 = (x+1)(x2+x+1)
e. 1011 : x3 + x + 1
f. 1101 : x3 + x2 + 1
g. 1111 : x3 + x2 + x + 1 = (x+1)(x2+1)
Where some test divisions could be avoided if the obvious factorable terms are skipped, as shown above.
3. Proceed with test divisions. The first test division by (x+1) yields a zero remainder, and a factor is found. This polynomial is not prime.
1 0 1 1 1 1 1 = x6 + x4 + x3 + x2 + x + 1
-----------------
1 1 ) 1 1 1 0 0 0 0 1
1 1 modulo 2 subtraction!
---
0 1 0
0 1 1 subtract when the msb = 1
-----
1 0
1 1
---
1 0
1 1
---
1 0
1 1
---
1 1
1 1
---
0 remainder = 0
Therefore:
x7 + x6 + x5 + 1
= (x+1) (x6+x4+x3+x2+x+1)
Question: Can (x6 + x4 + x3 + x2 + x + 1) be further factored? Answer
The application of polynomials to the manipulation of binary numbers has a practical significance in the way in which the operations are actually performed in a digital circuit. Normally, it would be painstaking and slow to perform long division on large integers. The above example could be performed in hardware with simple XOR-gates and shift registers.
Observe the value 11 (highlighted) as the division proceeds below. This value is essentially being shifted across P(x). It has already been noted that subtraction is equivalent to XOR. Consequently, the division reduces to shifting 11 across P(x) and performing the XOR operation if the msb of both values equals 1.
1 0 1 1 1 1 1 = x6 + x 4 + x3 + x2 + x + 1
-----------------
1 1 ) 1 1 1 0 0 0 0 1
1 1 XOR
---
0 1
1 1 no!
---
0 1 0
1 1 XOR
-----
1 0
1 1 XOR
---
1 0
1 1 XOR
---
1 0
1 1 XOR
---
1 1
1 1 XOR
---
0 remainder = 0
| ||
|
Sat May 25 02:29:57 ADT 2013
Last Updated: 15 JAN 2012 |
Richard Tervo [ tervo@unb.ca ] | Back to the course homepage... |
| ||