Mathematics‎ > ‎

Finite Fields with 4-bit Elements

Finite Fields with 16 4-bit elements are large enough to handle up to 15 parallel components in 2D-RS storage systems.




Three equivalent Finite Fields exist with 4-bit elements. The elements are listed below - binary on the left and hex on the right...


0000 = 0

0001 = 1

0010 = 2

0011 = 3

0100 = 4

0101 = 5

0110 = 6

0111 = 7

1000 = 8

1001 = 9

1010 = A

1011 = B

1100 = C

1101 = D

1110 = E

1111 = F


Operations on the elements are defined as operations on binary polynomials (coefficients are 0 or 1) modulo p(x) where p(x) is an irreducible binary polynomial of degree 4. Three p(x)s of degree 4 exist so there are three Finite Fields with 4-bit elements, but these three are equivalent.  (The mathematical terminology used to say they are equivalent is to say they are isomorphic.)

The elements shown above are the coefficients of polynomials of degree 3 or less. For example 1011= x3+x+1.


All three Finite Fields have the same addition table as shown below. Addition is bit-for-bit XOR.






Finite Field 1 uses p(x) = x4+x+1 and has the following multiplication table.




The 8 primitive elements are 2, 3, 4, 5, 9, B, D and E.





Finite Field 2 uses p(x) = x4+x3+x2+x+1 and has the following multiplication table.




The 8 primitive elements are 3, 5, 6, 7, 9, A, B and E.





Finite Field 3 uses p(x)=x4+x3+1 and has the following multiplication table...




The 8 primitive elements are 2, 4, 6, 7, 9, C, D, and E.





Larger Finite Fields with more bits per element follow the same pattern as this example except there are a much larger number of them.


To create an m-bit finite field, all you need is an irreducible binary (coefficients are 0 or 1) polynomial of degree m, and there are tables of irreducible binary polynomials of any degree in multiple places.  Just Google "irreducible binary polynomials".  There is also a table of irreducible binary polynomials in the second edition of Peterson and Weldon's book on error-correcting codes.