GF(2)
GF(2) (även betecknad , Z /2 Z eller ) är det finita fältet av två element (GF är initialismen av Galois field , ett annat namn för finita fält). Notationerna Z 2 och kan påträffas även om de kan förväxlas med notationen av 2 -adiska heltal .
0 GF(2) är fältet med minsta möjliga antal element, och är unikt om den additiva identiteten och den multiplikativa identiteten betecknas respektive och 1 , som vanligt.
Elementen i GF(2) kan identifieras med de två möjliga värdena på en bit och till de booleska värdena true och false . Härav följer att GF(2) är grundläggande och allestädes närvarande inom datavetenskap och dess logiska grunder.
Definition
0 GF(2) är det unika fältet med två element med dess additiva respektive multiplikativa identiteter betecknade och 1 .
Dess addition definieras som den vanliga additionen av heltal men modulo 2 och motsvarar tabellen nedan:
| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
Om elementen i GF(2) ses som booleska värden, är additionen densamma som den för den logiska XOR- operationen. Eftersom varje element är lika med sin motsats är subtraktion alltså samma operation som addition.
Multiplikationen av GF(2) är återigen den vanliga multiplikationen modulo 2 (se tabellen nedan), och på booleska variabler motsvarar den logiska OCH- operationen.
| × | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
GF(2) kan identifieras med fältet för heltalen modulo 2 , det vill säga kvotringen för ringen av heltal Z med den ideala 2 Z av alla jämna tal : GF(2) = Z /2 Z .
Egenskaper
behålls många av de välbekanta egenskaperna hos talsystem, såsom de rationella talen och reella talen :
- addition har ett identitetselement (0) och en invers för varje element;
- multiplikation har ett identitetselement (1) och en invers för varje element utom 0;
- addition och multiplikation är kommutativa och associativa ;
- multiplikation är distributiv över addition.
Egenskaper som inte är bekanta från de reella siffrorna inkluderar:
- varje element x i GF(2) uppfyller x + x = 0 och därför − x = x ; detta betyder att egenskapen för GF(2) är 2;
- varje element x i GF(2) uppfyller x 2 = x (dvs. är idempotent med avseende på multiplikation); detta är ett exempel på Fermats lilla teorem . GF(2) är det enda fältet med denna egenskap (Bevis: om x 2 = x , då antingen x = 0 eller x ≠ 0 . I det senare fallet måste x ha en multiplikativ invers, i vilket fall båda sidorna divideras med x ger x = 1. Alla större fält innehåller andra element än 0 och 1, och dessa element kan inte uppfylla denna egenskap).
Ansökningar
På grund av de algebraiska egenskaperna ovan fungerar många välbekanta och kraftfulla matematiska verktyg i GF(2) lika bra som andra områden. Till exempel kan matrisoperationer, inklusive matrisinversion , tillämpas på matriser med element i GF(2) ( se matrisring ) .
Varje grupp V med egenskapen v + v = 0 för varje v i V (dvs varje element är en involution ) är nödvändigtvis abelisk och kan omvandlas till ett vektorrum över GF(2) på ett naturligt sätt, genom att definiera 0 v = O och 1 v = v . Detta vektorutrymme kommer att ha en bas , vilket innebär att antalet element i V måste vara en potens av 2 (eller oändlig).
I moderna datorer representeras data med bitsträngar av en fast längd, kallade maskinord . Dessa är utrustade med strukturen av ett vektorrum över GF(2). Tillägget av detta vektorutrymme är den bitvisa operationen som kallas XOR (exklusiv eller). Den bitvisa OCH är en annan operation på denna vektorrymd, vilket gör den till en boolesk algebra , en struktur som ligger till grund för all datavetenskap . Dessa mellanslag kan också utökas med en multiplikationsoperation som gör dem till ett fält GF(2 n ), men multiplikationsoperationen kan inte vara en bitvis operation. När n i sig är en potens av två, kan multiplikationsoperationen vara nim-multiplikation ; alternativt, för vilket n som helst , kan man använda multiplikation av polynom över GF(2) modulo ett irreducerbart polynom (som till exempel för fältet GF(2 8 ) i beskrivningen av Advanced Encryption Standard- chifferet).
Vektorutrymmen och polynomringar över GF(2) används i stor utsträckning inom kodningsteori , och i synnerhet i felkorrigeringskoder och modern kryptografi . Till exempel är många vanliga felkorrigeringskoder (som BCH-koder ) linjära koder över GF(2) (koder definierade från vektorrum över GF(2)), eller polynomkoder (koder definierade som kvoter av polynomringar över GF(2) )).
Se även
- Lidl, Rudolf; Niederreiter, Harald (1997). Finita fält . Encyclopedia of Mathematics och dess tillämpningar. Vol. 20 (andra upplagan). Cambridge University Press . ISBN 0-521-39231-4 . Zbl 0866.11069 .