Władysław Mochnacki - Kody korekcyjne i kryptografia, Książki
[ Pobierz całość w formacie PDF ]
⌧ ☯☺ ⌧ ⌧ ⌧ ⌧ ⌧ ☺☺ ☺☺ ⌧ ☯ ⌧ ⌧ ☺☺☺ ☺ ☺ ☺ ☺ ☺⌧ ☺☺☺☺ ☺☺ ☺ ☺ ☺☺☺ ☺ ☺ ☺ KODY KOREKCYJNE I KRYPTOGRAFIA WŁADYSŁAW MOCHNACKI Władysław Mochnacki KODY KOREKCYJNE I 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 4 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 [ Pobierz całość w formacie PDF ] |