ECE4253 Digital Communications | |

Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada | |

000 + 000 = 000 011 + 010 = 001 111 + 111 = 000As with GF(2), this is equivalent to the exclusive-OR operation. The set satisfies the definition of an

000 * 000 = 000 011 * 010 = 110 111 * 111 = 10101 = 011 mod P(x)While this is like GF(2) multiplication, the introduction of a primitive polynomial modulus P(x) of degree 3 is important to ensure that this set of eight elements is closed under multiplication. In the example above, the simple product 111 * 111 gives 10101 which must be taken modulus P(x) to give a 3-bit result. The set satisfies the definition of a

In summary the set {0,1,2...2^{m}-1} is both an additive group and a
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 ^{m})**.

The choice of a different P(x) as a modulus leads to different multiplication answers that still belong to the same field. In a practical sense, the results are not fundamentally different and two finite fields with the same number of
elements (order) are called *isomorphic*.

2. Multi-bit binary values can be represented as polynomials with coefficients from **GF(2 ^{m})**.

For example, with m=3, the 9-bit binary value **100110011** can be broken into 3-bit parts as **100 110 011** and written as

and simplified as:

or as polynomial terms in brackets:

The *degree* of a polynomial is the power of the highest non-zero
coefficient. The above example shows a polynomial of "degree 2".

3. Polynomials can be manipulated using the usual arithmetic rules, in particular, the polynomial powers add under multiplication, as expected.

Example 1: (4 6 3) x (1 0) = (4 6 3 0) can be written as:

4. Polynomials always use modulo 2 addition as described above.

Example 2: (1 2) x (1 2) can be computed as:

1 2 x 1 2 ----- 2 4 + 1 2 0 ----- 1 0 4 Note modulo 2 additionand as a polynomial:

This example illustrates the more general property that (a + b)^{2} = a^{2} + b^{2}
which shows that squaring is a linear operation in GF(2^{N}).

5. The rules for **subtraction** follow from addition and are also equivalent to the bitwise exclusive-OR operation, as:

000 - 000 = 000 011 - 010 = 001 111 - 111 = 000

6. With these rules in mind, hand calculation is made easier with addition and multiplication tables for these operations. The choice of P(x) affects only the multiplication table.

See addition and multiplication tables.

In particular, the multiplicative inverse of a value can be found from the multiplication table by identifying the entry in a given row or column that gives the result 1.Longer calculations will benefit from the use a calculator. The P(x) must be specified in each case.

Online GF(2^m) Calculator Tool

7. The non-zero elements of GF(2^{m}} defined on P(x) are found in the terms {a^{n}} provided that the element *a* is a *root* of P(x), meaning that P(a) = 0.

For example, using the above P(x) = x^{3} + x + 1 having m=3, then a=2 is a root because P(2) = 2^3 + 2 + 1 = 3 + 2 + 1 = 0. In this case, the term 2^3 = 2x2x2 = 3 may be found from the multiplication table and the 3-bit additions proceed as 011 + 010 + 001 = 000.

Subsequently, successive powers of 2^{n} describe all the non-zero field elements {1,2,4,3,6,7,5} for n= 0 to 6. For
example, 2^{5} = 7.

It follows that logarithms in GF(2^{3}) are defined such that, for example, if a^{5} = 7 then log(7) = 5. In general, the
computation of such logarithms is not straightforward and the use of a lookup table is one possible approach.

>> a = gf(2,3,11); % Let a=2 in GF(2^3) with P(x) >> y = a.^(0:6) % find successive powers of 2^n y = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal) Array elements = 1 2 4 3 6 7 5 >> log(y) % find the discrete logarithm of these values ans = 0 1 2 3 4 5 6

Mon Mar 4 13:02:07 AST 2024
Last Updated: 07 FEB 2016 |
Richard Tervo [ tervo@unb.ca ] | Back to the course homepage... |