Available internal projects

Arithmetic in prime fields based on Eisenstein integers

Contact:	Mikael Olofsson
Examiner:	Mikael Olofsson

Description

Arithmetic operations in finite fields are often used for encoding and decoding of error control codes. To make those calculations efficient, among other things we need efficieant implementations of those arithmetic operations. Within the division of Communication Systems there is research about efficient arcitectures for VLSI implementation of arithmetic operations in finite extension fields. Exemples of this research are Mastrovito [1], Alfredsson [2] and Olofsson [3].

Traditionally, both engineers and researchers have concentrated on codes over fields of characteristic two, i.e. the field size is a power of two. Lately, a slight increase of interest for codes over other alphabets have emerged. Therefore we find that prime fields can be of interest. For the theory about finite fields, we refer to Lidl & Niederreiter [4] and Herstein [5].

A prime field GF(p) can be created from the ring of integers by reducing all arithmetic calculations modulo p. An alternative way for some primes p is to start with the ring of Eisensteinintegers a+wb, where a and b are integers and w is a third root of 1, i.e. we have w = e^i 2/3. Here the calculations are reduced modulo an irreducible element in that ring. These two representations yield different architectures for calculations in the field.

In this Master thesis work you will study those two representationer of one or a few prime fields with respect to some suitable complexity measure for a few arithmetic operations.

This Master thesis work is suitable for students with interest for algebra and implementations.

References

[1]	Edoardo Mastrovito , VLSI Architectures for Computations in Galois Fields, PhD Thesis, Linköping University, 1991.
[2]	Lasse Alfredsson , VLSI Architectures and Arithmetic Operations with Application to the Fermat Number Transform, PhD Thesis, Linköping University, 1996.
[3]	Mikael Olofsson , VLSI Aspects on Inversion in Finite Fields, PhD Thesis, Linköping University, 2002.
[4]	Rudolf Lidl & Harald Niederreiter, Finite Fields, Cambridge University Press, Cambridge, 1983.
[5]	I. N. Herstein, Topics in Algebra, John Wiley & Sons, New York, second edition, 1975.