Kody korekcyjne i kryptografia.pdf

⌧

☯☺

⌧

☺☺

⌧

☯

⌧

☺☺☺

☺

☺⌧

☺☺☺☺

☺☺

☺

☺☺☺

☺

KODY KOREKCYJNE

KRYPTOGRAFIA

WŁADYSŁAW MOCHNACKI

Władysław Mochnacki

KODY KOREKCYJNE

KRYPTOGRAFIA

Oficyna Wydawnicza Politechniki Wrocławskiej

Wrocław 2000

Wydział Elektroniki Politechniki Wrocławskiej

Opiniodawcy:

Józef DUDEK

Czesław KOŚCIELNY

Opracowanie redakcyjne i korekta

Ewa SOBESTO

Wydanie drugie poprawione

Copyright by Oficyna Wydawnicza Politechniki Wrocławskiej, Wrocław 2000

OFICYNA WYDAWNICZA POLITECHNIKI WROCŁAWSKIEJ

Wybrzeże Wyspiańskiego 27, 50-370 Wrocław

ISBN

Drukarnia Oficyny Wydawniczej Politechniki Wrocławskiej. Zam.

Spis treści

Wstęp.........................................................................................................................7

Część 1. Elementy algebry ciał skończonych .............................................................. 9

1.1. Wprowadzenie....................................................................................................9

1.1.1. Systemy algebraiczne .................................................................................9

1.1.2. Kongruencje i arytmetyka modularna ......................................................10

1.1.3. Funkcja Eulera .........................................................................................12

1.2. Ciała proste.......................................................................................................13

1.2.1. Konstrukcja ciała prostego .......................................................................13

1.2.2. Przykłady ciał prostych ............................................................................13

1.2.3. Rząd multyplikatywny elementów ciała ..................................................14

1.2.4. Charakterystyka ciała ...............................................................................15

1.3. Algebra wielomianów i przestrzeń wektorowa ................................................16

1.3.1. Wielomiany nad ciałami skończonymi ....................................................16

1.3.2. Wielomiany nierozkładalne i pierwotne...................................................17

1.3.3. Tablice wielomianów nierozkłdalnych nad ciałami prostymi..................19

1.3.4. Przestrzeń wektorowa ..............................................................................20

1.4. Sekwencje okresowe nad ciałami prostymi......................................................22

1.4.1. Generowanie sekwencji okresowych .......................................................22

1.4.2. Generatory sekwencji okresowych ..........................................................23

1.4.3. Właściwości binarnych sekwencji pseudolosowych ................................24

1.5. Konstrukcja i struktura ciał rozszerzonych ......................................................28

1.5.1. Ciała rozszerzone .....................................................................................28

1.5.2. Konstrukcja rozszerzonych ciał skończonych..........................................29

1.5.3. Elementy ciała skończonego w postaci macierzy ....................................30

1.5.4. Elementy ciała skończonego w postaci wektorów ...................................31

1.5.5. Elementy ciała skończonego w postaci wielomianów .............................32

1.5.6. Ciała rozszerzone nad niebinarnymi ciałami prostymi ............................33

1.5.7. Wielomiany minimalne elementów ciała .................................................35

1.5.8. Struktura ciał rozszerzonych ....................................................................38

1.6. Sekwencje okresowe i rozszerzenia ciał nad ciałami rozszerzonymi..............41

1.6.1. Wielomiany i sekwencje okresowe nad ciałami rozszerzonymi .............41

1.6.2. Właściwości sekwencji pseudolosowych nad ciałami rozszerzonymi .....42

1.6.3. Rozszerzenia ciał nad ciałami rozszerzonymi ..........................................44

1.7. Realizacja działań w ciałach skończonych.......................................................47

1.7.1. Logarytmy Zecha .....................................................................................47

1.7.2. Programowa realizacja działań w ciałach skończonych..........................50

1.7.3. Układy mnożenia i dzielenia wielomianów .............................................52

1.7.4. Układy realizujące działania arytmetyczne w ciałach rozszerzonych......55

Część 2. Kody korekcyjne .......................................................................................... 59

2.1. Elementy transmisji danych .............................................................................59

Spis treści

2.1.1. System transmisji danych.........................................................................59

2.1.2. Zakłócenia i błędy w kanałach transmisyjnych........................................61

2.1.3. Model binarnego kanału transmisji danych .............................................62

2.2. Charakterystyka kodów....................................................................................64

2.2.1. Typy kodów korekcyjnych.......................................................................64

2.2.2. Struktura kodu blokowego .......................................................................64

2.2.3. Zdolność detekcyjna i korekcyjna kodu...................................................68

2.2.4. Geometryczna interpretacja kodu.............................................................70

2.2.5. Syndrom ...................................................................................................71

2.3. Kody liniowe ....................................................................................................72

2.3.1. Definicja kodu liniowego .........................................................................72

2.3.2. Macierzowy opis kodu liniowego ............................................................74

2.3.3. Kodowanie informacji..............................................................................76

2.3.4. Dekodowanie ciągów odebranych ...........................................................77

2.3.5. Liniowe kody Hamminga.........................................................................79

2.4. Kody cykliczne.................................................................................................83

2.4.1. Charakterystyka kodów cyklicznych .......................................................83

2.4.2. Wielomiany generujące kody cykliczne ..................................................85

2.4.3. Algorytm kodowania................................................................................86

2.4.4. Uproszczony algorytm dekodowania .......................................................88

2.5. Macierzowy opis kodów cyklicznych ..............................................................92

2.5.1. Wyznaczanie macierzy generującej na podstawie wielomianu

generującego kod ..........................................................................................92

2.5.2. Wyznaczenie macierzy kontrolnej na podstawie wielomianu

generującego kod dualny...............................................................................94

2.5.3. Definicja kodu cyklicznego za pomocą pierwiastków wielomianu

generującego kod ..........................................................................................96

2.5.4. Kodowanie i dekodowanie kodów cyklicznych.......................................99

2.6. Realizacja techniczna koderów i dekoderów kodów cyklicznych .................102

2.6.1. Realizacja kodera ...................................................................................102

2.6.2. Realizacja dekodera................................................................................104

2.6.3. Dekodowanie z łowieniem błędów ........................................................107

2.7. Przegląd binarnych kodów cyklicznych.........................................................110

2.7.1. Cykliczne kody Hamminga ....................................................................110

2.7.2. Kody maksymalnej długości ..................................................................111

2.7.3. Kody Bose-Chaudhuri-Hocquenghema .................................................111

2.7.4. Tablica kodów cyklicznych....................................................................116

2.8. Kody cykliczne korygujące błędy grupowe ...................................................118

2.8.1. Błędy grupowe .......................................................................................118

2.8.2. Kody Reeda-Solomona ..........................................................................118

2.8.3. Realizacja techniczna kodów Reeda-Solomona .....................................121

2.8.4. Rozszerzone kody Reeda-Solomona ......................................................122

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: