Uvod u teoriju informacija i kodovanje
Ivaniš Predrag
Dušan Drajić
ISBN: 978-86-7466-344-8
| izdavač: Akademska Misao |
| godina izdanja: 2009. |
| izdanje: 3. |
| format: B5 |
| povez: Tvrdi |
| pismo: Latinica |
| jezik: srpski |
| broj strana: 513 |
Komentar izdavača
Materija sadržana u ovom udžbeniku izlaže se na Elektrotehničkom fakultetu u Beogradu najvećim delom u okviru redovnih predmeta Statistička teorija telekomunikacija i Računarske telekomunikacije i pokriva tematiku: izvori informacija, statističko kodovanje, kanali za prenos informacija, uvod u zaštitno kodovanje, zaštitno kodovanje u savremenim sistemima, prenos infrmacija uz dopušteno oštećenje, teorija informacija i kriptologija, pregled nekih osnovnih pojmova diskretne matematike i kola za implementaciju cikličnih kodova.
Sadržaj
1. Uvod 1
Nastanak Teorije informacija 1
1.1 Model komunikacionog sistema 2
Literatura 5
2. Izvori informacija 7
2.1 Uvod 7
2.2 Definicija količine informacija 7
2.2.1 Neke druge definicije količine informacija 10
2.3 Diskretni izvori bez memorije 11
2.3.1 Aksiomatski pristup definisanju entropije 12
2.3.2 Osobine entropije 13
2.3.3 Entropija binarnog izvora informacija 15
2.3.4 Primena pojma entropije na rešavanje nekih logičkih zadataka 15
2.3.5 Tipične sekvence 17
2.3.6 Proširenje diskretnog izvora 18
2.4 Diskretni izvori s memorijom 19
2.4.1 Izvor pridružen Markovljevom izvoru 22
2.4.2 Proširenje Markovljevog izvora 22
2.4.3 Markovljevi izvori prvog reda 23
2.4.4 Dijagram stanja i trelis 26
2.4.5 Entropija izvora s memorijom 28
2.4.6 Diferencijalno kodovanje 29
2.4.7 Analiza nekih klasičnih modemskih signala 30
2.4.8 Govor i štampani tekst 34
2.5 Kontinualni izvori 39
2.5.1 Maksimiranje entropije za kontinualne izvore 41
2.5.2 Protok informacija iz kontinualnih izvora 43
Literatura 44
3. Statističko kodovanje 47
3.1 Uvod 47
3.2 Definicija koda 47
3.2.1 Kodno stablo 50
3.2.2 Kraftova nejednakost 51
3.2.3 Makmilanova nejednakost 53
3.2.4 Srednja dužina kodne reči 54
3.3 Prva Šenonova teorema 56
3.3.1 Efikasnost i suvišnost 58
3.3.2 Kodovanje bez proširenja izvora 59
3.3.3 Šenon-Fanoov postupak 59
3.3.4 Hafmenov postupak 63
3.3.5 Adaptivni Hafmenov postupak 67
3.4 Lempel-Zivovi (LZ) kodovi 72
Literatura 77
4. Kanali za prenos informacija 79
4.1 Uvod 79
4.2 Diskretni kanali bez memorije 80
4.2.1 Odnosi verovatnoća u kanalu 86
4.2.2 Apriorna i aposteriorna entropija 88
4.2.3 Prenesena (uzajamna, međusobna) informacija 89
4.2.4 Relativna entropija 95
4.2.5 Entropija više slučajnih promenljivih 95
4.2.6 Teorema o obradi podataka 96
4.2.7 Fanoova nejednakost 96
4.2.8 Kapacitet kanala 97
4.2.9 Kapaciteti nekih kanala 98
4.3 Diskretni kanali s memorijom 104
4.3.1 Kanal sa impulsnim šumom 104
4.3.2 Kanal sa interferencijom simbola 107
4.4 Modeli kanala zasnovani na Markovljevim nizovima 108
4.4.1 Kodni kanal 108
4.4.2 Neke osobine sekvence grešaka 110
4.4.3 Generisanje sekvence grešaka binarnog simetričnog kanala 111
4.4.4 Generisanje sekvence grešaka za modele kanala zasnovane na Markovljevim
nizovima 113
4.4.5. Markovljevi modeli za vremenski sporopromenljive kanale 120
4.4.6 Deskriptivni modeli 125
4.5 Kontinualni kanali 125
4.5.1 Međusobna informacija kod kontinualnih kanala 125
4.5.2 Kapacitet kontinualnog kanala (kanala sa šumovima) 128
4.5.3 Kapacitet kanala sa šumom u slučaju prenosa s diskretnim konstelacijama 130
4.5.4 Kapacitet kanala s proizvoljnom transfer funkcijom 135
4.5.5 Kapaciteti nekih kanala 137
4.6 Čovek s gledišta Teorije informacija 138
4.7 Ostali tipovi kanala 140
4.8. Kapacitet MIMO sistema 141
Literatura 145
5. Uvod u zaštitno kodovanje 149
5.1 Uvod 149
5.2 Elementi za dokazivanje Druge Šenonove teoreme 149
5.2.1 Verovatnoća greške 149
5.2.2 Zaštitno kodovanje ponavljanjem poruke 153
5.2.3 Formulacija II Šenonove teoreme 157
5.2.4 Hemingovo rastojanje 158
5.2.5 Broj tačaka (vektora) u okolini kodne reči 160
5.2.6 “Okoravanje sfera” 161
5.3 Druga Šenonova teorema za binarni simetrični kanal 163
5.3.1 Dopunski komentari II Šenonove teoreme 167
5.4 Veza Hemingovog rastojanja i sposobnosti koda da otkriva i ispravlja
greške 170
5.5 Blok kodovi 172
5.5.1 Kodovi s jednostavnim proverama na parnost 174
5.5.2 Hemingovi kodovi 175
5.5.3 Neke granice 181
5.5.4 Golejev kod 183
5.5.5 Perfektni kodovi 183
5.5.6 Tvrdo i meko odlučivanje na osnovu pravila maksimalnih izgleda 183
5.5.7 Kodovi s težinskim proverama 187
5.5.8 Kodovanje za kanale s paketima grešaka 189
5.6 Konvolucioni kodovi 196
5.6.1. Uvod 196
5.6.2 Način opisa konvolucionih kodova 198
5.6.3. Dekodovanje na osnovu majoritetne logike 207
5.6.4. Sekvencijalno dekodovanje 211
5.6.5. Viterbijev algoritam 216
Literatura 227
6. Linearni blok kodovi 231
6.1 Performanse komunikacionih sistema 231
6.2 Uvod u linearne blok kodove 235
6.2.1 Matrični opis 238
6.2.2 Sindrom i standardni raspored 242
6.2.3 Raspodela težina i Makvilijamsovi identiteti 244
6.2.4 Produktni kodovi 245
6.2.5 Kodovi na bazi matrica Adamara 246
6.2.6 Rid-Malerovi kodovi 246
6.2.7 Kodovi s malom gustinom provera na parnost 249
6.3 Ciklični kodovi 249
6.3.1 Megitova teorema i Megitov dekoder 261
6.3.2 Provera ciklične redundanse (CRC postupak) 263
6.3.3 Fajerovi kodovi 268
6.4 BCH i Rid-Solomonovi kodovi 269
6.4.1 Osnovne operacije u polju Galoa oblika GF(rm) 269
6.4.2 Binarni BCH kodovi 273
6.4.3 Spektri BCH kodova 277
6.4.4 Rid-Solomonovi (RS) kodovi 280
6.4.5. Spektri Rid-Solomonovih kodova 283
6.4.6. Performanse i primena Rid-Solomonovih kodova 284
6.4.7 Dekodovanje BCH i RS kodova 287
6.5 Procena performansi sistema Monte Karlo simulacijom 293
6.5.1 Osnove Monte Karlo simulacionog postupka 293
6.5.2. Određivanje strukture sekvence grešaka 297
6.5.3 Određivanje performansi linearnih blok kodova 299
Literatura 301
7. Zaštitno kodovanje u savremenim sistemima 303
7.1 Dekodovanje linearnih blok kodova pomoću trelisa 304
7.1.1 Formiranje trelisa za linearne blok kodove 304
7.1.2 Dekodovanje linearnih blok kodova Viterbijevim algoritmom 308
7.1.3 Generalizovani Viterbijev algoritam 310
7.1.4 BCJR algoritam 313
7.1.5 SOVA algoritam 319
7.2. Analitički opis strukture konvolucionih kodova 321
7.2.1 Rekurzivni sistematski konvolucioni kodovi – opis i dekodovanje 321
7.2.2 Performanse konvolucionih kodova 328
7.2.3 Bušeni (punktirani) konvolucioni kodovi 337
7.2.4 Bušeni kodovi s kompatibilnim kodnim količnikom (RCPC kodovi) 341
7.3 Hibridne ARQ procedure 346
7.4 Adaptivna modulacija i kodovanje 351
7.5 Uvod u trelis kodovanu modulaciju (TCM) 354
7.6 Kaskadni kodovi 365
7.7 Iterativno dekodovanje 368
7.7.1 Elementarni uvod u turbo kodove 371
7.7.2 Dekodovanje rekurzivnih konvolucionih kodova MAP algoritmom 375
7.7.3 Dekodovanje turbo kodova 378
7.7.4 Performanse turbo kodova 380
7.7.5 Elementarni uvod u kodove s malom gustinom provera na parnost 383
7.7.6 Predstavljanje LDPC kodova grafovima 387
7.7.7 Iterativno dekodovanje LDPC kodova s tvrdim odlukama 390
7.7.8 Iterativno dekodovanje LDPC kodova s mekim odlukama 392
7.7.9 Performanse LDPC kodova 395
7.8 Elementarni uvod u prostorno-vremensko (ST) kodovanje 397
Literatura 401
8. Prenos informacija uz dopušteno oštećenje . 407
8.1 Uvod 407
8.2 Kriterijum vernosti reprodukcije 409
8.3 Definicija funkcije R(D) 410
8.3.1 Osobine funkcije R(D) 411
8.3.2 Binarni izvor bez memorije 412
8.3.3 Kvantovanje amplituda koje se generišu prema normalnoj raspodeli 413
8.4 Kvantovanje i teorija oštećenja informacija 415
Literatura 416
9. Teorija informacija i kriptologija 417
9.1 Uvod 417
9.2 Osnovni pojmovi 418
9.2.1 Blok-šema sistema 418
9.2.2 Tajnost i autentičnost, simetrični i asimetrični kriptosistemi 419
9.3 Neki elementarni postupci šifrovanja 421
9.4 Osnovni doprinosi Teorije informacija kriptologiji 425
9.4.1 Perfektna tajnost 425
9.4.2 Potrebna dužina kriptograma za određivanje ključa 425
9.4.3 Dodatni komentari o šifrovanju 428
9.5 Neki praktični sistemi šifrovanja 429
9.5.1 DES (Digital Encryption Standard) 430
9.5.2 AES (Advanced Encryption Standard) 436
9.5.3 Elementi sistema javnih ključeva 440
9.5.4 RSA algoritam 441
9.5.5 Poređenje sistema sa simetričnim i sistema sa asimetričnim ključevima 444
9.5.6 Heš funkcija i digitalni potpis 445
Literatura 447
A. Pregled nekih osnovnih pojmova diskretne matematike 449
A.1 Grupa 449
A.1.1 Podgrupa 452
A.2 Prsten 452
A.3 Polje 454
A.4 Klase ekvivalencije (dekompozicije) i faktor grupa 455
A.5 Vektorski prostor i linearna algebra 457
A.6 Matrice 459
A.7 Aritmetika u poljima Galoa 460
A.7.1 Ideali, klase ostataka i prsten klasa ostataka 460
A.7.2 Ideali i klase ostataka celih brojeva 461
A.7.3 Ideali i klase ostataka polinoma 463
A.7.4 Algebra klasa ostataka polinoma 464
A.7.5 Vektori i polinomi 465
A.7.6 Polja Galoa 467
A.7.7 Multiplikativna grupa polja Galoa 468
Literatura 472
B. Kola za implementaciju cikličnih kodova (množenje i deljenje
polinoma) 473
B.1 Elementi kola za množenje i deljenje 473
B.2 Množenje polinoma 474
B.3 Deljenje polinoma 476
B.4 Mnioženje i deljenje polinoma na nivou koeficijenata 479
B.5 Rešavanje rekurentnih relacija 481
Literatura 482
C. Berlekamp-Mejsijev (BM) algoritam i njegove primene 483
C.1 Primena BM algoritma na sintezu LSFR 483
C.2 Primena BM algoritma na sintezu kodera 488
C.2..1 Određivanje osnovnih parametara linearnih blok kodova 489
C.2.2 Rekonstrukcija strukture binarnog konvolucionog kodera 492
C.2.3 Rekonstrukcija strukture konvolucionog kodera BM algoritmom 496
C.2.4 Rekonstrukcija struktur turbo kodera 501
Literatura 504
Indeks 507
Nastanak Teorije informacija 1
1.1 Model komunikacionog sistema 2
Literatura 5
2. Izvori informacija 7
2.1 Uvod 7
2.2 Definicija količine informacija 7
2.2.1 Neke druge definicije količine informacija 10
2.3 Diskretni izvori bez memorije 11
2.3.1 Aksiomatski pristup definisanju entropije 12
2.3.2 Osobine entropije 13
2.3.3 Entropija binarnog izvora informacija 15
2.3.4 Primena pojma entropije na rešavanje nekih logičkih zadataka 15
2.3.5 Tipične sekvence 17
2.3.6 Proširenje diskretnog izvora 18
2.4 Diskretni izvori s memorijom 19
2.4.1 Izvor pridružen Markovljevom izvoru 22
2.4.2 Proširenje Markovljevog izvora 22
2.4.3 Markovljevi izvori prvog reda 23
2.4.4 Dijagram stanja i trelis 26
2.4.5 Entropija izvora s memorijom 28
2.4.6 Diferencijalno kodovanje 29
2.4.7 Analiza nekih klasičnih modemskih signala 30
2.4.8 Govor i štampani tekst 34
2.5 Kontinualni izvori 39
2.5.1 Maksimiranje entropije za kontinualne izvore 41
2.5.2 Protok informacija iz kontinualnih izvora 43
Literatura 44
3. Statističko kodovanje 47
3.1 Uvod 47
3.2 Definicija koda 47
3.2.1 Kodno stablo 50
3.2.2 Kraftova nejednakost 51
3.2.3 Makmilanova nejednakost 53
3.2.4 Srednja dužina kodne reči 54
3.3 Prva Šenonova teorema 56
3.3.1 Efikasnost i suvišnost 58
3.3.2 Kodovanje bez proširenja izvora 59
3.3.3 Šenon-Fanoov postupak 59
3.3.4 Hafmenov postupak 63
3.3.5 Adaptivni Hafmenov postupak 67
3.4 Lempel-Zivovi (LZ) kodovi 72
Literatura 77
4. Kanali za prenos informacija 79
4.1 Uvod 79
4.2 Diskretni kanali bez memorije 80
4.2.1 Odnosi verovatnoća u kanalu 86
4.2.2 Apriorna i aposteriorna entropija 88
4.2.3 Prenesena (uzajamna, međusobna) informacija 89
4.2.4 Relativna entropija 95
4.2.5 Entropija više slučajnih promenljivih 95
4.2.6 Teorema o obradi podataka 96
4.2.7 Fanoova nejednakost 96
4.2.8 Kapacitet kanala 97
4.2.9 Kapaciteti nekih kanala 98
4.3 Diskretni kanali s memorijom 104
4.3.1 Kanal sa impulsnim šumom 104
4.3.2 Kanal sa interferencijom simbola 107
4.4 Modeli kanala zasnovani na Markovljevim nizovima 108
4.4.1 Kodni kanal 108
4.4.2 Neke osobine sekvence grešaka 110
4.4.3 Generisanje sekvence grešaka binarnog simetričnog kanala 111
4.4.4 Generisanje sekvence grešaka za modele kanala zasnovane na Markovljevim
nizovima 113
4.4.5. Markovljevi modeli za vremenski sporopromenljive kanale 120
4.4.6 Deskriptivni modeli 125
4.5 Kontinualni kanali 125
4.5.1 Međusobna informacija kod kontinualnih kanala 125
4.5.2 Kapacitet kontinualnog kanala (kanala sa šumovima) 128
4.5.3 Kapacitet kanala sa šumom u slučaju prenosa s diskretnim konstelacijama 130
4.5.4 Kapacitet kanala s proizvoljnom transfer funkcijom 135
4.5.5 Kapaciteti nekih kanala 137
4.6 Čovek s gledišta Teorije informacija 138
4.7 Ostali tipovi kanala 140
4.8. Kapacitet MIMO sistema 141
Literatura 145
5. Uvod u zaštitno kodovanje 149
5.1 Uvod 149
5.2 Elementi za dokazivanje Druge Šenonove teoreme 149
5.2.1 Verovatnoća greške 149
5.2.2 Zaštitno kodovanje ponavljanjem poruke 153
5.2.3 Formulacija II Šenonove teoreme 157
5.2.4 Hemingovo rastojanje 158
5.2.5 Broj tačaka (vektora) u okolini kodne reči 160
5.2.6 “Okoravanje sfera” 161
5.3 Druga Šenonova teorema za binarni simetrični kanal 163
5.3.1 Dopunski komentari II Šenonove teoreme 167
5.4 Veza Hemingovog rastojanja i sposobnosti koda da otkriva i ispravlja
greške 170
5.5 Blok kodovi 172
5.5.1 Kodovi s jednostavnim proverama na parnost 174
5.5.2 Hemingovi kodovi 175
5.5.3 Neke granice 181
5.5.4 Golejev kod 183
5.5.5 Perfektni kodovi 183
5.5.6 Tvrdo i meko odlučivanje na osnovu pravila maksimalnih izgleda 183
5.5.7 Kodovi s težinskim proverama 187
5.5.8 Kodovanje za kanale s paketima grešaka 189
5.6 Konvolucioni kodovi 196
5.6.1. Uvod 196
5.6.2 Način opisa konvolucionih kodova 198
5.6.3. Dekodovanje na osnovu majoritetne logike 207
5.6.4. Sekvencijalno dekodovanje 211
5.6.5. Viterbijev algoritam 216
Literatura 227
6. Linearni blok kodovi 231
6.1 Performanse komunikacionih sistema 231
6.2 Uvod u linearne blok kodove 235
6.2.1 Matrični opis 238
6.2.2 Sindrom i standardni raspored 242
6.2.3 Raspodela težina i Makvilijamsovi identiteti 244
6.2.4 Produktni kodovi 245
6.2.5 Kodovi na bazi matrica Adamara 246
6.2.6 Rid-Malerovi kodovi 246
6.2.7 Kodovi s malom gustinom provera na parnost 249
6.3 Ciklični kodovi 249
6.3.1 Megitova teorema i Megitov dekoder 261
6.3.2 Provera ciklične redundanse (CRC postupak) 263
6.3.3 Fajerovi kodovi 268
6.4 BCH i Rid-Solomonovi kodovi 269
6.4.1 Osnovne operacije u polju Galoa oblika GF(rm) 269
6.4.2 Binarni BCH kodovi 273
6.4.3 Spektri BCH kodova 277
6.4.4 Rid-Solomonovi (RS) kodovi 280
6.4.5. Spektri Rid-Solomonovih kodova 283
6.4.6. Performanse i primena Rid-Solomonovih kodova 284
6.4.7 Dekodovanje BCH i RS kodova 287
6.5 Procena performansi sistema Monte Karlo simulacijom 293
6.5.1 Osnove Monte Karlo simulacionog postupka 293
6.5.2. Određivanje strukture sekvence grešaka 297
6.5.3 Određivanje performansi linearnih blok kodova 299
Literatura 301
7. Zaštitno kodovanje u savremenim sistemima 303
7.1 Dekodovanje linearnih blok kodova pomoću trelisa 304
7.1.1 Formiranje trelisa za linearne blok kodove 304
7.1.2 Dekodovanje linearnih blok kodova Viterbijevim algoritmom 308
7.1.3 Generalizovani Viterbijev algoritam 310
7.1.4 BCJR algoritam 313
7.1.5 SOVA algoritam 319
7.2. Analitički opis strukture konvolucionih kodova 321
7.2.1 Rekurzivni sistematski konvolucioni kodovi – opis i dekodovanje 321
7.2.2 Performanse konvolucionih kodova 328
7.2.3 Bušeni (punktirani) konvolucioni kodovi 337
7.2.4 Bušeni kodovi s kompatibilnim kodnim količnikom (RCPC kodovi) 341
7.3 Hibridne ARQ procedure 346
7.4 Adaptivna modulacija i kodovanje 351
7.5 Uvod u trelis kodovanu modulaciju (TCM) 354
7.6 Kaskadni kodovi 365
7.7 Iterativno dekodovanje 368
7.7.1 Elementarni uvod u turbo kodove 371
7.7.2 Dekodovanje rekurzivnih konvolucionih kodova MAP algoritmom 375
7.7.3 Dekodovanje turbo kodova 378
7.7.4 Performanse turbo kodova 380
7.7.5 Elementarni uvod u kodove s malom gustinom provera na parnost 383
7.7.6 Predstavljanje LDPC kodova grafovima 387
7.7.7 Iterativno dekodovanje LDPC kodova s tvrdim odlukama 390
7.7.8 Iterativno dekodovanje LDPC kodova s mekim odlukama 392
7.7.9 Performanse LDPC kodova 395
7.8 Elementarni uvod u prostorno-vremensko (ST) kodovanje 397
Literatura 401
8. Prenos informacija uz dopušteno oštećenje . 407
8.1 Uvod 407
8.2 Kriterijum vernosti reprodukcije 409
8.3 Definicija funkcije R(D) 410
8.3.1 Osobine funkcije R(D) 411
8.3.2 Binarni izvor bez memorije 412
8.3.3 Kvantovanje amplituda koje se generišu prema normalnoj raspodeli 413
8.4 Kvantovanje i teorija oštećenja informacija 415
Literatura 416
9. Teorija informacija i kriptologija 417
9.1 Uvod 417
9.2 Osnovni pojmovi 418
9.2.1 Blok-šema sistema 418
9.2.2 Tajnost i autentičnost, simetrični i asimetrični kriptosistemi 419
9.3 Neki elementarni postupci šifrovanja 421
9.4 Osnovni doprinosi Teorije informacija kriptologiji 425
9.4.1 Perfektna tajnost 425
9.4.2 Potrebna dužina kriptograma za određivanje ključa 425
9.4.3 Dodatni komentari o šifrovanju 428
9.5 Neki praktični sistemi šifrovanja 429
9.5.1 DES (Digital Encryption Standard) 430
9.5.2 AES (Advanced Encryption Standard) 436
9.5.3 Elementi sistema javnih ključeva 440
9.5.4 RSA algoritam 441
9.5.5 Poređenje sistema sa simetričnim i sistema sa asimetričnim ključevima 444
9.5.6 Heš funkcija i digitalni potpis 445
Literatura 447
A. Pregled nekih osnovnih pojmova diskretne matematike 449
A.1 Grupa 449
A.1.1 Podgrupa 452
A.2 Prsten 452
A.3 Polje 454
A.4 Klase ekvivalencije (dekompozicije) i faktor grupa 455
A.5 Vektorski prostor i linearna algebra 457
A.6 Matrice 459
A.7 Aritmetika u poljima Galoa 460
A.7.1 Ideali, klase ostataka i prsten klasa ostataka 460
A.7.2 Ideali i klase ostataka celih brojeva 461
A.7.3 Ideali i klase ostataka polinoma 463
A.7.4 Algebra klasa ostataka polinoma 464
A.7.5 Vektori i polinomi 465
A.7.6 Polja Galoa 467
A.7.7 Multiplikativna grupa polja Galoa 468
Literatura 472
B. Kola za implementaciju cikličnih kodova (množenje i deljenje
polinoma) 473
B.1 Elementi kola za množenje i deljenje 473
B.2 Množenje polinoma 474
B.3 Deljenje polinoma 476
B.4 Mnioženje i deljenje polinoma na nivou koeficijenata 479
B.5 Rešavanje rekurentnih relacija 481
Literatura 482
C. Berlekamp-Mejsijev (BM) algoritam i njegove primene 483
C.1 Primena BM algoritma na sintezu LSFR 483
C.2 Primena BM algoritma na sintezu kodera 488
C.2..1 Određivanje osnovnih parametara linearnih blok kodova 489
C.2.2 Rekonstrukcija strukture binarnog konvolucionog kodera 492
C.2.3 Rekonstrukcija strukture konvolucionog kodera BM algoritmom 496
C.2.4 Rekonstrukcija struktur turbo kodera 501
Literatura 504
Indeks 507
info.telit.etf
