Mikael Olofsson

Arithmetic operations in finite fields and rings

List of Researchers

• Mikael Olofsson , associate professor, Communication Systems, ISY.
• Occational Master students.

Description

The theory of finite fields and rings has several telecommunication applications. These applications include digital mobile telephony, digital radio and television, internet and space applications. Error correcting codes are used in all those applications to ensure correct transmission of information. These codes are normally defined over finite fields, and sometimes over finite rings. That means that decoding of these codes demands arithmetic calculations in these fields or rings. Finite fields and rings are also important for certain crypto systems. It is therefore af great importance for the information technology of today and of the future to be able to perform calculations efficiently in finite fields and rings.

Finite fields and rings can be represented in many ways. The chosen representation determines how the arithmetic operations can be performed. Some representations results in high complexity of the calculations, while other representations results in low complexity. Most of the research done in the area has given efficient algorithms and architectures based on a few representations. It is, however, not shown that those representations are better than other representations, in terms of computational complexity. In fact, on the contrary, a study performed here (see Nils-Hassan Quttineh below) suggests that certain non-conventional representations give lower computational complexity than conventional ones. However, those non-conventional representations are closely related to certain conventional representations.

In this project, we study non-standard representations of finite fields and rings in order to determine if there are yet not considered representations that are better than those considered so far. We also intend to develop new algorithms and architectures for computations in finite fields and rings, based on those new representations. One example of such an architecture is given in the picture to the right.

Finite fields and rings are closely related to error correcting codes, and such codes are used in almost every digital communication system. The trend in digital communication is towards increasing data rates. This trend will increase the demands on fast circuits for encoding and decoding of error correcting codes. Therefore, we need faster calculations in finite fields and rings. On top of that, error correcting codes have found more and more applications. For example, the last 10 to 20 years memory manufacturers have begun tu use error correcting codes to combat errors due to radiation. In these applications, the demands on speed are extreme, and therefore there have only been very simple codes used in memories. If more powerful codes are to be used there, they will need to use arithmetic in finite fields and rings, and the same extreme demands on speed will apply on these calculations.

Publications

• Mikael Olofsson, On Matrix Representations of Finite Extension Fields, Proceedings of Seventh Joint Swedish-Russian International Workshop on Information Theory, S:t Petersburg, Russia, 1995, Institute for Information Transmission Problems, Moscow.
• Mikael Olofsson, VLSI Aspects on Inversion in Finite Fields, PhD thesis, February 2002.
• Ivar Tångring, A Design Study of an Arithmetic Unit for Finite Fields MSc thesis, June 2003.
• Nils-Hassan Quttineh, Computational Complexity of Finite Field Multiplication MSc thesis, August 2003.
• Björn Abrahamsson, Architectures for Multiplication in Galois Rings MSc thesis, June 2004.
• Adam Engström, Computations in Prime Fields using Gaussian Integers MSc thesis, June 2006.
• Oscar Gustafsson & Mikael Olofsson, Complexity Reduction of Constant Matrix Computations over the Binary Field, Proceedings of International Workshop on the Arithmetic of Finite Fields 2007, WAIFI 2007, Madrid, Lecture Notes in Computer Science, LNCS 4547, Springer Verlag.