Mikael Olofsson

Aritmetiska operationer i ändliga kroppar och ringar

Forskare

• Mikael Olofsson, universitetslektor, Kommunikationssystem, ISY.
• Då och då någon examensarbetare.

Beskrivning

Teorin om ändliga kroppar och ringar används i flera telekommunikationstillämpningar. Dessa tillämpningar inkluderar digital mobiltelefoni, digital radio och television, internet och rymdapplikationer. Felrättande koder används i alla dessa tillämpningar för att säkerställa korrekt överföring av information. Dessa koder definieras normalt över ändliga kroppar och ibland över ändliga ringar. Det innebär att avkodning av dessa koder kräver beräkningar i dessa kroppar och ringar. Ändliga kroppar och ringar är också viktiga för vissa kryptosystem. Förmågan att effektivt utföra beräkningar i ändliga kroppar och ringar är alltså mycket viktigt för dagens och framtidens informationsteknologi.

Ändliga kroppar och ringar kan representeras på många sätt. Den valda representationen bestämmer hur beräkningarna kan utföras. Vissa representationer ger hög beräkningskomplexitet, medan andra representationer ger låg beräkningskomplexitet. Den hittillsvarande forskningen inom området har främst gått ut på att hitta effektiva algoritmer och arkitekturer baserat på några få representationer. Det är inte på något sätt visat att dessa representationer skulle vara de bästa, vad gäller beräkningskomplexitet. Tvärt om, en undersökning som gjorts hos oss (se Nils-Hassan Quttineh nedan) antyder att vissa okonventionella representationer ger lägre beräkningskomplexitet än konventionella. Dessa okonventionella representationer är dock nära relaterade till vissa konventionella representationer.

Detta projekt går ut på att betrakta okonventionella representationer av ändliga kroppar och ringar, för att avgöra huruvida det finns bättre representationer än de som hittills betraktats. Vi avser att utveckla ett flertal nya algoritmer och arkitekturer för olika beräkningar i ändliga kroppar och ringar, baserat på dessa nya representationer. Ett exempel på en sådan arkitektur visas i figuren här intill.

Ändliga kroppar och ringar är intimt förknippade med felrättande koder, som i sin tur används i nära nog all digital kommunikation idag. Trenden inom digital kommunikation är allt högre datatakter. Detta kommer att öka kraven på snabba kretsar för kodning och avkodning av felrättande koder. Därmed behövs också snabbare beräkningar i ändliga kroppar och ringar. Därtill kommer att felrättande koder hittar fler och fler tillämpningar. De senaste 10 à 20 åren har t.ex. minnestillverkare experimenterat med att använda felrättande koder för att motverka fel som uppkommer på grund av strålning. Här ställs extrema krav på hastighet, varför man hittills använt mycket enkla koder. Om kraftfullare koder ska kunna användas där, kommer beräkningar i ändliga kroppar och ringar in även där, och samma höga krav på hastigheten kommer att ställas på dessa beräkningar.

Publikationer

• 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, doktorsavhandling, februari 2002.
• Ivar Tångring, A Design Study of an Arithmetic Unit for Finite Fields examensarbete (civ-ing), juni 2003.
• Nils-Hassan Quttineh, Computational Complexity of Finite Field Multiplication examensarbete (civ-ing), augusti 2003.
• Björn Abrahamsson, Architectures for Multiplication in Galois Rings examensarbete (civ-ing), juni 2004.
• Adam Engström, Computations in Prime Fields using Gaussian Integers examensarbete (civ-ing), juni 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.

Sidansvarig: Mikael Olofsson
Senast uppdaterad: 2013 05 18   00:56