N-state Finite Fields GF(n)

© 2011 Peter Lablans, all rights reserved

Please note that at least two USA patents are pending related to the disclosed matter herein.

The Alternate N-state Finite Field

This website provides novel or alternate finite fields that can be characterized by neutral elements that are not 0.

Finite Field or Galois Field GF(n)

A Finite Field or a Galois Field is abbreviated as GF(n).  A finite field has a finite number of elements (n).  A finite field is defined by its elements (n) and by operations that can be performed in or over the finite field.  There are at least 2 operations that have to be performed in the finite field, which are usually called an addition (+) and a multiplication (*).

These operations are dyadic operations that involve two operands.  For instance c = a + b, wherein + is an addition over GF(n); a and b are elements in GF(n) and the result c also has to be an element of GF(n).

An example of an addition over a finite field is for instance a modulo-n addition, wherein n is a prime number.  For instance, with n = 5 and + is + mod-5, (3 + 4) mod-5 is 2. One may provide a similar example for a multiplication modulo-5.

The advantage of arithmetic in a field GF(n) is that all elements are fully determined, including the ones generated by an inverse operation.  Thus, no rounding errors occur, and there is no uncertainty about an outcome of a performed operation.  For instance, a division 5/3 over an infinite field R is 1.666666..., which is not attractive in applications such as error correcting coding or encryption.

The theory of Finite Fields and arithmetic of Finite Fields is quite complex, while its application is actually relatively simple. 

 Representation of GF(n)

Finite Fields that are defined as an extension of a binary field are currently the most popular in use.  They are applied in encryption and in error correcting coding such as Reed Solomon (RS) codes.  These fields can be generated from primitive polynomials that are represented by primitive Linear Feedback Shift Registers (LFSRs) of degree n (or with n shift register elements). 

How to create a finite field GF(8) with a 3-element binary LFSR is well described in an on-line article by Dr. Sklar.

In actual application of a finite field GF(n) it is easier to use the truth tables that define the operations over GF(n).  The following tables define an addition and a multiplication over GF(4).

The above + and * operations have properties of which several may not be readily apparent.  The most commonly known property of an addition over GF(n=2^p) is that its inverse (subtraction) is the same as the original addition.  Another property is of a division, which is the inverse of the multiplication.  An inverse of each multiplication (except for the multiplication with 0) is that the inverse is also an element of the field GF(n).  Division by 1, is multiplication by 1.  Division by 2, is multiplication by 3.  Division by 3, is multiplication by 2. 

Both addition and multiplication over GF(4) are commutative (a * b = b * a) and associative operations (a * b * c = a * c * b).  The addition and multiplication are a distributive pair (a* (b + c)) = a*b + a*c).  The multiplication and addition have a neutral zero element e for which (a + e = a) and (a*e = e).  Furthermore, the multiplication has a neutral identity element g for which (a*g = a) or a*a^-1=g.     

Under common arithmetic rules, we usually apply e = 0 and g = 1.  However, this is not really a stringent requirement.  It conforms with our deeply entrenched sense of what a digit or symbol in arithmetic means.  However, such a limited interpretation of what a neutral element should be is not required in machine arithmetic.

An alternate finite field

In some applications, it would be advantageous to use a definition of a finite field that is completely different from the commonly used definition, while still benefiting from the operational properties of a finite field.  Such a different finite field can be called an alternate finite field.

An alternate finite field GF(4) can be created with the following definition of  the operations + and *, which more appropriately and in accordance with Iain Adamson’s book “Introduction to Field Theory” should be called “laws of composition.”

The zero-neutral element in this alternate field GF(4) is 1 so that 1 + a = a.  Also 1*a = 1.  The identity neutral element is 0 so that 0*a = a. The addition is self-reversing. The division provides results that are in the field.

Alternate finite fields can be applied in most if not all of the known coding and encryption methods that apply arithmetic over a finite field GF(n).

Reduction of Truth Tables in GF(n)

Arithmetic over GF(n) is generally performed over a binary extension field GF(2^p). This facilitates especially a traditional addition over GF(n), which becomes a XOR addition of the binary words representing a symbol in GF(n). A multiplication over the extension field in general is a shift of the bits of the binary word representing the symbol in GF(n) that is being multiplied. A symbol over GF(n) in the literature is often represented as αⁱ, with i being one of (n-1) consecutive integers and a special zero symbol. This avoids assigning a common decimal symbol to a symbol over GF(n) and reflects the representation by binary words. However, this notation also makes it initially difficult to easily follow the specific operations over GF(n).

It is much easier to apply the common truth tables over GF(n) as provided above. In fact, one can avoid common arithmetical binary executions by performing truth table or memory based operations, rather than complicated switching operations on binary words. A commonly used field is field GF(256) wherein each symbol is represented by a byte of 8 bits. A truth table for an addition or multiplication over GF(256) requires 64 kbytes of storage.

The execution speed of an expression over GF(n) such as y = a1*x1 + a2*x2 + ... ak*xk wherein ak is a constant over GF(n) and xk is a variable symbol can be increased by eliminating the multiplication step by reducing the addition truth table in accordance with the multiplication factor ak.

For instance, part of an expression over GF(4) may be a term 3*xk which is added to a partial sum s. The term (s + 3*xk) can be represented by the following reduced truth table.

The truth table is now non-commutative. Arithmetic over GF(n) (such as decoding of Reed Solomon codewords) applies many composite expressions and thus can benefit from these truth table reductions.

Intellectual Property

Aspects of the above described approach are protected by issued patents and at least one pending patent application which can be viewed by clicking here and at least one issued patent which can be viewed by clicking here. All rights are strictly reserved to the inventor and Ternarylogic LLC.

This website is provided for educational purposes only. No license or permission to use an apparatus or method claimed in any patent is provided or implied herewith.

If you use any text or drawing of this site's content you have to acknowledge each page or occurrence with: Source: Ternarylogic LLC, author Peter Lablans. You will have to get permission in writing to include any of the drawings or text of this site in any written, printed, paper or electronic document intended for distribution.

Commercial use of all or any of the content of this site is strictly prohibited. For educational and commercial use please contact admin at ternarylogic dot ignore dot com.

A trial license or a limited license on IP owned by Ternarylogic LLC on a named basis for educational or evaluation purposes may be provided. Such a license will only be provided in response to a written request to Ternarylogic LLC.

Further information on the Ternarylogic LLC IP portfolio can be found at www.ternarylogic.com/portfolio.pdf.

©2011, Peter Lablans. All rights reserved.

[TOP]