Kao primjer, upravo smo razmotrili najjednostavnije korektivne kodove - kod s jednostavnom provjerom pariteta koji vam omogućava da otkrijete jednu grešku u primljenoj sekvenci, kao i blok iterativni kod i "oblak" kod koji ispravlja jednu grešku. koristeći skup provjera pariteta. U svim kodovima, u procesu kodiranja za ispravljanje grešaka, formirani su dodatni bitovi koji su dodani originalnoj kombinaciji koda.
Postavimo formalna (generirajuća) pravila prema kojima se vrši kodiranje, tj. transformacija informacijskog niza u kodnu riječ.
Najjednostavniji način da se opiše ili specificira korektivni kodovi je tabelarni način, u kojem se svakoj informacijskoj sekvenci jednostavno dodjeljuje kodna riječ iz tablice kodova. Na primjer, za najjednostavniji kod s provjerom parnosti, tablica korespondencije između kombinacija izvora i koda bit će sljedeća:
Ovaj način opisivanja kodova primjenjiv je na sve, a ne samo na linearne kodove. Međutim, na slobodi To veličina tablica kodova ispostavilo se da je prevelika da bi se mogla koristiti u praksi.
Drugi način definiranja linearnih blok kodova je korištenje tzv sistemi generisanja jednačina, definiranje pravila u koje se pretvaraju simboli informacijskog niza kodni simboli. Za isti primjer, sistem generiranja jednačina će izgledati ovako:
Međutim, najprikladniji i najilustrativniji način za opisivanje linearnih blok kodova je definiranje pomoću njih generirajuća matrica,što je kompaktan oblik reprezentacije sistema verifikacionih jednačina.
Linearni blok(n, /c)-kod je u potpunosti određen matricom veličine G To X P sa binarnim matričnim elementima. U ovom slučaju, svaka kodna riječ je linearna kombinacija redova matrice G, a svaka linearna kombinacija redova G je kodna riječ.
Biće pozvani linearni blok kodovi definisani generisanjem matrica matrični kodovi. Uobičajena (kanonska) reprezentacija generirajuće matrice izgleda ovako: 
Na primjer, za najjednostavniji (4, 3)-kod s provjerom parnosti, generirajuća matrica će izgledati ovako: 
Neka T -(t 1; t 2 , ..., t k)će biti blok poruke koji će se kodirati korištenjem datog koda.
Zatim odgovarajuću kodnu riječ Uće
Uzimajući u obzir strukturu matrice G simboli kodne riječi i bit će ovako:
Drugim riječima, To krajnji lijevi simboli kodne riječi poklapaju se sa simbolima kodiranog informacijskog niza, a ostali (n - do) simboli su linearne kombinacije simbola informacijskog niza.
Na primjer, ako je koder ulazni niz t == (10 1), tada će se pomoću generirajuće matrice kod konstruirati na sljedeći način:
8 Komandant je prvim putem poslao tri izviđača, tri - drugim, dva - trećim, četvrtim je išao sam. Sastavite generirajuću matricu takvog koda.
odgovor: Prema zapletu misije, poruka koju je primio komandant lično ne može se iskriviti. Stoga se ograničavamo na proučavanje informacija koje su prenijeli borci. U grupi koja je krenula jednim od puteva, svaki borac mora izvestiti komandanta ili o pronalasku predmeta (takvu prijavu označavamo sa "1"), ili o odsustvu predmeta ("0") . U nedostatku distorzije, izvještaji svakog borca iz iste grupe moraju se podudarati. dakle:
Matrica se može svesti na kanonski oblik prenumeracijom boraca, tj. na prvi put je poslao prvog, četvrtog i petog, na drugi put - drugog, šestog i sedmog, na treći put - trećeg i osmog borca. Dobijamo sljedeću generirajuću matricu:
Tako definiran kod se zove linearni blok sistematski(P,/cj kod sa generalizovanim provjerama parnosti.
U komunikacijskim sistemima moguće je nekoliko strategija za postupanje s greškama:
- otkrivanje grešaka u blokovima podataka i zahtjev za automatskim ponovnim prijenosom oštećeni blokovi - ovaj pristup se uglavnom koristi na slojevima veza i transporta;
- otkrivanje grešaka u blokovima podataka i odbacivanje loših blokova - ovaj pristup se ponekad koristi u sistemima za streaming medija gdje je kašnjenje prijenosa važno i nema vremena za ponovni prijenos;
- ispravljanje grešaka(engleski) naprijed ispravljanje grešaka) se nanosi na fizički sloj.
Kodovi za otkrivanje i ispravljanje grešaka
Korekcioni kodovi - kodovi koji se koriste za otkrivanje ili ispravljanje grešaka koje nastaju tokom prenosa informacija pod uticajem smetnji, kao i tokom njihovog skladištenja.
Da biste to učinili, prilikom pisanja (prijenosa), dodajte podatke o korisnom učitavanju na poseban način strukturirano višak informacija, a prilikom čitanja (prijema) se koristi u cilju otkrivanja ili ispravljanja grešaka. Naravno, broj grešaka koje se mogu ispraviti je ograničen i zavisi od specifičnog koda koji se koristi.
WITH kodovi za ispravljanje grešaka, blisko povezana kodovi za otkrivanje grešaka. Za razliku od prvog, ovaj drugi može samo utvrditi prisustvo greške u prenesenim podacima, ali ne i ispraviti je.
U stvari, korišteni kodovi za otkrivanje grešaka pripadaju istim klasama kodova kao i kodovi za ispravljanje grešaka. U stvari, bilo koji kod za ispravljanje grešaka također se može koristiti za otkrivanje grešaka (pritom će moći otkriti više greške nego što je mogao da ispravi).
Prema načinu na koji rade s podacima, kodovi za ispravljanje grešaka se dijele na blok, dijeljenje informacija na fragmente konstantne dužine i obradu svakog od njih posebno, i konvolucijski, rad s podacima kao kontinuirani tok.
blok kodovi
Neka se kodirana informacija podijeli na fragmente dužine k bitove koji se konvertuju u kodne riječi dugo n bit. Tada se obično označava odgovarajući blok kod ( n,k) . Broj je pozvan brzina koda.
Ako original k bitni kod ostavlja nepromijenjen i dodaje n − k verifikacija, takav kod se zove sistematično, inače nesistematično.
Blok kod možete postaviti na različite načine, uključujući tabelu u kojoj je svaki skup k mapirani informacijski bitovi n bit kodne riječi. ali, dobar kod mora ispunjavati najmanje sljedeće kriterije:
- mogućnost ispravljanja što većeg broja grešaka,
- što manje zaliha,
- jednostavnost kodiranja i dekodiranja.
Lako je uočiti da su ovi zahtjevi u suprotnosti jedni s drugima. Zato postoji veliki broj kodove, od kojih je svaki prikladan za svoj niz zadataka.
Gotovo svi korišteni kodovi su linearni. To je zbog činjenice da je nelinearne kodove mnogo teže proučavati i da im je teško pružiti prihvatljivu lakoću kodiranja i dekodiranja.
Linearni prostori
Generativna matrica
Ova relacija uspostavlja vezu između vektora koeficijenata 
i vektori. Navođenjem svih vektora koeficijenata možete dobiti sve vektore. Drugim riječima, matrica G generiše linearni prostor.
Checking Matrix
To znači da operacija kodiranja odgovara umnožavanju originala k-bitni vektor na nesingularnu matricu G pozvao generirajuća matrica.
Neka je ortogonalni podprostor u odnosu na C, a H je matrica koja definira osnovu ovog podprostora. Tada je za bilo koji vektor tačno:
.
Svojstva i važne teoreme
Minimalna udaljenost i sposobnost korekcije
Hamingovi vezani i savršeni kodovi
Neka postoji binarni blok ( n,k) korektivni kod t. Zatim nejednakost (tzv Hamingova granica):
.
Kodovi koji zadovoljavaju ovu granicu jednakosti nazivaju se počinio. Savršeni kodovi uključuju, na primjer, Hamingove kodove. Kodovi sa velikom korektivnom snagom koji se često koriste u praksi (kao što su Reed-Solomon kodovi) nisu savršeni.
Dobitak energije
Prilikom prenosa informacija preko komunikacionog kanala, vjerovatnoća greške zavisi od odnosa signal-šum na ulazu demodulatora, tako da je pri konstantnom nivou šuma snaga predajnika od odlučujućeg značaja. U satelitskim i mobilnim sistemima, kao i drugim vrstama komunikacija, pitanje uštede energije je akutno. Osim toga, u određene sisteme komunikacija (na primjer, telefon) za neograničeno povećanje snage signala nije dozvoljena tehničkim ograničenjima.
Budući da kodiranje za ispravljanje grešaka omogućava ispravljanje grešaka, njegova primjena može smanjiti snagu predajnika, ostavljajući brzinu informacija nepromijenjenom. Dobitak energije se definira kao razlika između s/n odnosa u prisustvu i odsustvu kodiranja.
Aplikacija provjerite matricu- - [L.G. Sumenko. Engleski ruski rječnik informacionih tehnologija. M.: GP TsNIIS, 2003.] Teme informacione tehnologije uopšteno EN matrica provere ... Priručnik tehničkog prevodioca
U polju matematike i teorije informacija, linijski kod je važan tip blok koda koji se koristi u krugovima za otkrivanje i ispravljanje grešaka. Linearni kodovi, u poređenju sa drugim kodovima, omogućavaju implementaciju efikasnijih algoritama ... ... Wikipedia
Želite li poboljšati ovaj članak?: Pronađite i navedite fusnote za reference na autoritativne izvore koji potvrđuju ono što je napisano. Ciklični kod ... Wikipedia
Ciklični kod je linearni kod koji ima svojstvo cikličnosti, odnosno svaka ciklička permutacija kodne riječi je ujedno i kodna riječ. Koristi se za transformaciju informacija radi zaštite od grešaka (pogledajte Detekcija i ... ... Wikipedia
- (LDPC kod od engleskog. Low density parity check code, LDPC code, low density code) kod koji se koristi u prijenosu informacija, poseban slučaj blok linearnog koda sa provjerom parnosti. Karakteristika je niska gustina značajnih ... ... Wikipedia
Kod s malom gustinom provjera parnosti (LDPC kod sa engleskog. Low density parity check code, LDPC code, low-density code) kod koji se koristi u prijenosu informacija, poseban slučaj blok linearnog koda sa provjerom parnosti. Značajka ... ... Wikipedia
Reed-Solomon kodovi su nebinarni ciklički kodovi koji vam omogućavaju da ispravite greške u blokovima podataka. Elementi kodnog vektora nisu bitovi, već grupe bitova (blokova). Reed Solomon kodovi su vrlo česti, ... ... Wikipedia
Uvod
Opis procesa digitalne komunikacije
Izvor emituje poruku koja predstavlja opšti slučaj neki električni signal. Ovaj signal se pretvara u digitalni oblik, što je pogodno za dalju obradu.
Zatim se informacije komprimiraju (izvorno kodiranje), minimizirajući redundantnost poruka. Izvorno kodiranje smanjuje troškove prijenosa i skladištenja informacija. Nakon toga, poruka se mora prenijeti preko šumnog kanala. Da bi poruka stigla do potrošača u neiskrivljenom obliku, koristi se kodiranje informacija otporno na buku (kanalno kodiranje). Na strani potrošača, informacije se dekodiraju. Kanalski dekoder ispravlja greške u primljenoj riječi, a izvorni dekoder pretvara ispravljenu riječ u oblik pogodan za potrošača.
Govoreći o kodovima koji kontrolišu greške, treba razlikovati dve strategije za njihovu upotrebu.
- Direktna korekcija greške zbog redundance (Forward Error Correction - FEC).
- Detekcija greške sa naknadnim zahtjevima za ponovni prijenos pogrešno primljenih informacija (Automatic Repeat Request - ARQ).
Prilikom odabira metoda kodiranja i dekodiranja, vodi se mnogo faktora, čiji je odnos prikazan na slici.
Ukupna složenost uključuje hardverske i softverske troškove za implementaciju kodera i dekodera, troškove pohranjivanja i prenošenja informacija itd. Intenzitet protoka podataka uključuje prijenos korisnih informacija, bitova za provjeru, kao i zahtjeve i ponavljanja pojedinačni blokovi informacija o ovim zahtjevima.
Kodiranje za korekciju šuma
Opće informacije
Pravi sistemi za prenos podataka nisu savršeni. Primjenjujući informatičku tehnologiju, moramo voditi računa o mogućnostima grešaka u prijenosu i skladištenju informacija. Ovo se prvenstveno odnosi na
- pohranjivanje informacija na medijima visoke gustine snimanja (magnetni mediji, CD-ROM, DVD);
- prijenos podataka s ograničenom jačinom signala (satelit i mobilnu vezu);
- prijenos informacija preko vrlo bučnih kanala (mobilne komunikacije, velike brzine žičane linije komunikacije);
- komunikacioni kanali sa povećanim zahtevima za pouzdanost informacija ( kompjuterske mreže, dalekovodi sa kompresijom podataka).
U svim gore navedenim slučajevima koriste se kontrolni kodovi grešaka.
Razmislite najjednostavniji model prijenos podataka korištenjem kodiranja za ispravljanje grešaka.
Neka izvorni koder sekvencijalno emituje informacijske riječi fiksne dužine. Kanalski koder zamjenjuje svaku informacijsku riječ u sa kodnom riječju v. Predajnik generiše signale koji odgovaraju kodnoj riječi v i šalje ih kanalu. prijemnik proizvodi inverzna transformacija, kao rezultat čega binarno primljena riječ r stiže u dekoder. Dekoder uspoređuje primljenu riječ r sa svim mogućim kodnim riječima koda koji se koristi. Ako se riječ r poklapa s jednom od kodnih riječi, tada se odgovarajuća informacijska riječ daje potrošaču. Ako se r razlikuje od svih kodnih riječi, tada se u kanalu dogodila greška koja se može otkriti. Svrha kanalnog kodiranja je da se uskladi sa odašiljanim informativna riječ u i primljena informacijska riječ u ′.
Od ovaj opis mogu se izvući 2 zaključka:
- Ako se tokom prijenosa preko kanala sa smetnjama, kodna riječ mapira u drugu kodnu riječ koja se ne poklapa sa prenesenom, tada se javlja greška koja se ne može otkriti. Nazovimo to zaostalom greškom dekodiranja.
- Potrebno je konstruisati kodove koji imaju određenu matematičku strukturu koja omogućava da se efikasno prepoznaju i, u nekim slučajevima, isprave greške koje nastaju kada se informacija prenosi putem komunikacionog kanala.
Linearni blok kodovi
Važnu porodicu kodova čine linearni binarni blok kodovi. Ovi kodovi su izvanredni po tome što, predstavljanjem informacija i kodnih riječi u obliku binarnih vektora, možemo opisati procese kodiranja i dekodiranja pomoću aparata linearne algebre. U ovom slučaju, komponente ulaznih vektora i matrica su simboli 0 i 1. Operacije nad binarnim komponentama se izvode prema pravilima aritmetika po modulu 2.
Najpoznatiji linearni kod je blok Hammingov kod. Nadalje, opis linearnih blok kodova će biti napravljen na primjeru ovog koda. Posebno će se uzeti u obzir (7,4)-Hammingov kod.
Koder binarnog bloka (n, k) preslikava skup od 2 k mogućih binarnih informacijskih riječi u skup od 2 k n -dimenzionalne kodne riječi. U teoriji kodiranja, uvijek postoji korespondencija jedan-na-jedan između ovih skupova.
Umjesto k bitova informacionog vektora, n bitova kodnog vektora se prenosi na kanal. U ovom slučaju se govori o redundantnom kodiranju brzinom: R = n ⁄ k .
Što je manja brzina, veća je redundancija koda i veća je mogućnost zaštite od grešaka. Međutim, treba imati na umu da se s povećanjem redundancije povećavaju i troškovi prijenosa informacija.
Opis procesa kodiranja i dekodiranja
Izvorni materijal za konstrukciju kodnih struktura je n-dimenzionalni binarni vektorski prostor, u kojem su specificirane aritmetičke operacije po modulu 2. K-dimenzionalni linearni prostor, koji sadrži 2 k kodnih riječi. Kod C se formira korišćenjem 2 k kombinacija od k linearno nezavisnih baznih vektora ( g 1 ,…, g k ).
Ovi vektori formiraju redove generirajuće matrice C koda.
Za kod C, postoji dualni kod C d takav da je skalarni proizvod bilo kog para vektora, od kojih jedan pripada prostoru C, a drugi prostoru C d, uvijek jednak nuli. To znači da su kodni vektori C d ortogonalni kodnim vektorima C. S druge strane, ako je neki vektor ortogonalan svim kodnim vektorima C, onda pripada kodu C d i obrnuto. Dualni vektorski podprostor je “presvučen” sa n − k linearno nezavisnih baznih vektora ( h 1 ,…, h n − k ). Ovi vektori formiraju redove kontrolne matrice.
Razmotrimo primjer generiranja i provjere matrica (7,4) Hamming koda:
 |
 |
Treba napomenuti važnu osobinu: i u generatoru i u matrici za provjeru postoji matrica identiteta. Ovo svojstvo se koristi u procesima kodiranja i dekodiranja.
Kodiranje
Kodna riječ v i informacijska riječ u povezane su:
gdje je G generirajuća matrica čija je struktura gore opisana.
Na primjer, informacioni vektor u = (1010) će biti preslikan na vektor koda na sljedeći način:
Lako je vidjeti da se posljednja četiri bita kodnog vektora poklapaju sa informacijskim vektorom. Ovo svojstvo se naziva sistematičnost koda.
Kodovi u kojima se informacijska riječ može direktno izdvojiti iz odgovarajućeg kodnog vektora nazivaju se sistematičnim. Generirajuća matrica bilo kojeg sistematskog koda uvijek se može dovesti u formu preuređivanjem stupaca:
G k × n = (P k ×(n − k) I k),
gdje je I k k × k matrica identiteta.
Tako se u vektoru koda sistematskog koda uvijek mogu razlikovati simboli informacija i provjere.
Uloga kontrolnih znakova i njihova upotreba biće detaljno objašnjeni u nastavku.
Dekodiranje
Zadatak dekodera je da povrati vektor prenesene informacije koristeći strukturu koda, koristeći primljenu riječ r. Za (7, 4) Hamingov kod razmatran gore, može se predložiti sljedeći algoritam detekcije greške. Pošto je kod koji se razmatra sistematičan, izražavamo svaki od tri simbola provjere u terminima simbola informacionog vektora:
V 0 = v 3 ⊕ v 5 ⊕ v 6
v 1 = v 3 ⊕ v 4 ⊕ v 5
v 2 = v 4 ⊕ v 5 ⊕ v 6
Ako je došlo do greške u kanalu, tada u primljenom vektoru r barem jedna od jednakosti neće biti zadovoljena. Zapišimo dobijene test relacije kao sistem jednadžbi za komponente vektora r:
R 0 ⊕ r 3 ⊕ r 5 ⊕ r 6 = s 0
r 1 ⊕ r 3 ⊕ r 4 ⊕ r 5 = s 1
r 2 ⊕ r 4 ⊕ r 5 ⊕ r 6 = s 2
Dakle, iz prve tri kolone generirajuće matrice G, dobili smo sistem od tri verifikacione jednačine. Ako u rezultirajućem sistemu jednačina barem jedna od komponenti (s 0 , s 1 , s 2 ) nije jednaka nuli, onda je došlo do greške u kanalu.
Zapišimo sistem jednadžbi verifikacije opšti pogled. Za bilo koji sistematski kod sa generatorskom matricom G, matrica provjere je definirana na sljedeći način:
H (n − k) × n = (I n − k P T k ×(n − k)).
Tada se sistem verifikacionih jednačina može zapisati kao
Vektor s se obično naziva sindrom. Dakle, greška će biti otkrivena ako barem jedna od komponenti s nije jednaka nuli.
Kao primjer, razmotrite sindromsko dekodiranje (7, 4) Hamingovog koda. Prilikom prijenosa informacijske riječi u = (1010) preko bešumnog kanala, r = v = (0011010) . Možemo potvrditi da je u ovom slučaju sindrom 0.
Ako, na primjer, u kodna riječ došlo je do jedne greške na četvrtoj poziciji (r = (0010010)), tada je četvrti red transponirane kontrolne matrice sindrom.
Nakon prolaska kroz sve moguće pozicije jedne greške, dobijamo kompletna tabela sindromi pojedinačnih grešaka - tabela korespondencije između broja pogrešnog pražnjenja i nastalog sindroma.
| Pogrešno pražnjenje | r0 | r1 | r2 | r3 | r4 | r 5 | r6 |
|---|---|---|---|---|---|---|---|
| Sindrom s | 100 | 010 | 001 | 110 | 011 | 111 | 101 |
Može se vidjeti da greška na i-toj poziciji kodne riječi odgovara sindromu koji formira i-ti stupac matrice H. Pošto su svi stupci matrice različiti, možemo ispraviti jednu uvedenu grešku kanalom koristeći tabelu sindroma.
Vrste grešaka
Linearni blok kodovi imaju 3 vrste grešaka:
- Prepoznatljiva i ispravljiva greška
- Sindrom je prisutan u tabeli sindroma
- Dekoder prepoznaje i ispravlja grešku, a zatim šalje ispravnu riječ prijemniku
- Prepoznatljiva greška
- Primljena riječ ne odgovara nijednoj kodnoj riječi.
- Sindrom nije prisutan u tabeli sindroma
- Dekoder prepoznaje grešku i šalje zahtjev za ponovnim prijenosom informacijske riječi.
- Neprepoznata greška
- Primljena riječ odgovara jednoj od kodnih riječi (ne odgovara originalnoj kodnoj riječi)
- Sindrom je 0
- Dekoder ne prepoznaje grešku i daje potrošaču pogrešnu informacijsku poruku
Zaključak
Treba napomenuti da učinkovitost određenog koda ovisi o području njegove primjene, a posebno o komunikacijskom kanalu. Ako je omjer signal-šum u kanalu dovoljno visok, tada je vjerovatnoća pojedinačne greške višestruko veća od vjerovatnoće greške veće multiplicitnosti, stoga je upotreba Hammingovog koda s ispravkom jedne greške u takvom kanalu može biti vrlo efikasna. S druge strane, u kanalima gdje dominiraju višestruke greške (npr. fading kanali), ispravljanje pojedinačne greške je besmisleno. At praktičan izbor specifičan kod za ispravljanje grešaka, potrebno je uzeti u obzir i brzinu njegovog dekodiranja i složenost tehničke implementacije.
Književnost
- Werner M. Osnove kodiranja. — M.: Tehnosfera, 2004.
- Blahut R. Teorija i praksa kodova za kontrolu grešaka. — M.: Mir, 1986.
Oleg Rybak
Zaista, teško je naći adekvatno objašnjenje. Autori najčešće pretpostavljaju da čitalac zna mnogo unapred i ne nastoje da objasne naizgled jednostavne tačke koje sadrže suštinu. Drago mi je što sam naleteo dati materijal, pojasnio sam nešto.
Linijski kodovi imaju sljedeće svojstvo:
Od svih mnogih 2 k dozvoljene kodne riječi koje formiraju linearnu grupu, iz kojih se može odabrati podskup k riječi koje imaju svojstvo linearne nezavisnosti.
Linearna nezavisnost znači da se nijedna od riječi uključenih u podskup linearno nezavisnih kodnih riječi ne može dobiti zbrajanjem (koristeći linearni izraz) bilo koje druge riječi uključene u ovaj podskup.
Istovremeno, bilo koja od dozvoljenih kodnih riječi može se dobiti zbrajanjem određenih linearno nezavisnih riječi.
Stoga je konstrukcija kodnih kombinacija linearnog koda povezana s linearnim operacijama. Za izvođenje takvih operacija prikladno je koristiti dobro razvijen aparat za matrične proračune.
Za obrazovanje n-bitne kodne riječi iz k-bitnih kodiranih riječi (kodiranje) koriste matricu koja se zove generator.
Generirajuća matrica se dobija upisivanjem k linearno nezavisnih reči u kolonu.
Označite sekvencu kodiranih informacija X i zapisaćemo ga kao matricu reda ||X|| dimenzija 1* k, Na primjer:
||X||=||11001||, gdje k=5.
Jedan od načina da se konstruiše generirajuća (generirajuća) matrica je kako slijedi: Ona se gradi iz matrice identiteta ||Ja|| dimenzija k*k i matrica dodatnih (suvišnih) cifara koje su joj dodijeljene na desnoj strani ||WDM|| dimenzije k*r.
u kojima je k=4
Takva OM struktura daje sistematski kod.
Procedura za konstruisanje MDS matrice biće razmotrena u nastavku.
7.4 Red kodiranja
Kodna riječ CS se dobija množenjem matrice informacijskog niza ||X|| na generirajuću matricu ||OM||:
Množenje se vrši prema pravilima množenja matrice: (SO po SO)
Potrebno je samo zapamtiti da se zbrajanje ovdje vrši po modulu 2.
recimo generirajuća matrica
||OM||= 0010 011
i vektor reda informacijskog niza
Pošto matrica koja se množi ima samo jedan red, množenje je pojednostavljeno. U ovom slučaju, trebali biste staviti u korespondenciju sa redovima generirajuće (generirajuće) matrice ||OM|| matrični bitovi informacijskog niza ||X|| i dodajte one redove generirajuće (generirajuće) matrice koji odgovaraju brojkama jedinice matrice ||X||.
primeti, to ||KC|| = ||X, DR||,
gdje ||X||- niz informacija (jer se množi sa matricom identiteta ||Ja||),
a ||DR||- dodatne cifre u zavisnosti od matrice dodatnih cifara ||WDM||:
|| DR ||= || X || * || MDR||
7.5 Redoslijed dekodiranja
Kao rezultat prijenosa kodne riječi kroz kanal, ona može biti izobličena smetnjama. Ovo će rezultirati primljenom kodnom riječi ||PKS|| možda neće odgovarati originalu. ||CS||.
Distorzija se može opisati sljedećom formulom:
|| PCS || = ||CS || + ||BO ||,
gdje ||IN||- vektor greške - red matrice sa dimenzijom 1* n, With 1 u onim pozicijama u kojima je došlo do izobličenja.
Dekodiranje se zasniva na pronalaženju takozvanog identiteta ili sindroma greške-matrica-red ||OP|| dugo r cifre ( r- broj dodatnih ili redundantnih bitova u kodnoj riječi).
Identifikator se koristi za pronalaženje procijenjenog vektora greške.
Identifikator se nalazi po sljedećoj formuli:
||OP|| = ||PKS||* ||TPM||,
gdje ||PKS||- primljena i eventualno oštećena kodna riječ;
||TPM||,- transponovana kontrolna matrica, koja se dobija iz matrice dodatnih cifara ||WDM|| dodjeljivanjem matrice identiteta odozdo:
Primjer ||TPM||:
Ukoliko ||PKS|| = ||CS|| + ||BO||, Posljednja formula se može napisati kao:
||OP|| = ||CS|| * ||TPM||+||VO|| * ||TPM||.
Razmotrimo prvi termin.
||KC||- matrica-red, i prvi k ispuštanja - informativna.
Dokažimo sada da je proizvod kodne riječi ||CS|| na ||TPM|| vodi do nulte matrice ||0||.
Ukoliko ||CS||- matrica-red, moguć je pojednostavljeni postupak za množenje matrica o kojima je bilo riječi.
Dakle, prvi mandat u
||OP|| = ||CS|| * ||TPM|| + ||VO|| * ||TPM||
je uvijek nula i identitet u potpunosti ovisi o vektoru greške ||IN||.
Ako sada odaberemo takvu matricu provjere TPM, što znači MDR, tako da različiti identiteti odgovaraju različitim vektorima greške OP, tada će po ovim identifikatorima biti moguće pronaći vektor greške IN, i na taj način ispraviti ove greške.
Korespondencija identiteta sa vektorima grešaka nalazi se unapred množenjem vektora grešaka koje se mogu ispraviti sa TPM;
Dakle, sposobnost koda da ispravi greške je u potpunosti određena ||WDM||. Za gradnju MDR za kodove koji ispravljaju pojedinačne greške, trebate u svakom redu MDR imaju najmanje 2 jedinice. U ovom slučaju, također je potrebno imati barem jednu razliku između bilo koje dvije linije MDR.
Kod koji smo dobili je nezgodan po tome što identifikator, iako je jedinstveno povezan sa brojem iskrivljene cifre, nije jednak njemu kao broju. Da biste tražili izobličeni bit, trebate koristiti dodatnu tablicu korespondencije između identifikatora i ovog broja. Pronađeni su i imenovani kodovi u kojima identifikator kao broj određuje poziciju izobličenog bita Hamingovi kodovi.
Zgrada MDR jer slučaj ispravljanja više grešaka postaje mnogo komplikovaniji. Različiti autori su pronašli različite algoritme za konstruisanje ||WDM || za ovaj slučaj, a odgovarajući kodovi se nazivaju po imenima njihovih autora.
Neka x1, x2, ..., xk označava riječ od k informacijskih bitova na ulazu kodera, kodiranih u n-bitnu kodnu riječ C:
unos kodera: X=[x 1, x 2, ...,xk]
izlaz kodera: C=[c 1, c 2, ..., cn]
Neka je data posebna generirajuća matrica G n , k,
postavljanje blok kod (n,k).
Matrični redovi G n , k mora biti linearno nezavisna.
Zatim dozvoljena kombinacija kodova C odgovara kodiranoj riječi X:
C=x 1 g 1 + x 2 g 2 + ... + x k g k.
Sistematski (kanonski) oblik generirajuće matrice G veličina k x n :
Generatorska matrica sistematskog koda stvara linearni blok kod u kojem je prvi k bitovi bilo koje kodne riječi su identični informacijskim bitovima, a ostali r=n-k bitovi bilo koje kodne riječi su linearne kombinacije k informacioni bitovi.
Checking Matrix H n , k Ima r x n elemenata, a istina je:
C x H T = 0.
Ovaj izraz se koristi za provjeru primljene kombinacije koda. Ako jednakost sa nulom nije zadovoljena, onda dobijamo red matrice || c 1 , c 2 , ..., r||, koji se zove sindrom greške.
Hamingov kod. Korektivne i detektivske sposobnosti. Pravila za izbor omjera između dužine kodne riječi i broja bitova informacija. Formiranje generirajućih i kontrolnih matrica Hamingovog koda. Tumačenje sindroma greške
Razmotrimo Hamingov kod sa rastojanjem koda d=3, što vam omogućava da ispravite pojedinačne greške ( d=2q max+1).
Broj dozvoljenih kombinacija kodova za kod sa d=3, za Hamingov kod striktno jednak 2 n/(n+1). Prvo k bitovi kodnih kombinacija koda se koriste kao informacija i njihov broj je jednak
k= log 2 (2 n/(n+1)] = n- dnevnik 2 ( n+1).
Ova jednačina ima cjelobrojna rješenja k= 0, 1, 4, 11, 26, koji određuju odgovarajuće Hamingove kodove: (3,1)-kod, (7,4)-kod, (15,11)-kod, itd. (uvijek n=2w‑1).
Checking Matrix H Hamingov kod ( r=n-k linije i n kolone): za binarni (n,k) kod, n=2 w -1 stupaca se sastoji od svih mogućih binarnih vektora sa r=n-k elemenata, isključujući vektor sa svim nula elementima.
Lako je to provjeriti G x H T= 0 (nula matrica veličine k x r elementi).
Primjer. Provjerimo rad koda prilikom slanja poruke X=1011. Prenesena kombinacija kodova će se formirati u obrascu linearna kombinacija(sabitak po modulu 2) redova br. 1, 3, 4 matrice G 7,4:
Pretpostavljamo da za prenesenu kodnu riječ C greška 0000100 je pogođena, što je rezultiralo a strana koja prima riječi C"=10111 10.
Zatim kada množite C" sa kontrolnom matricom H T dobijamo red matrice sindroma greške koji odgovara tom stupcu matrice provjere H sa brojem bita koji sadrži grešku.
Poređenje rezultirajućeg sindroma sa žicama H T, shvatili smo da je bit #5 na lijevoj strani pogrešan.
Haming dekoder može raditi u dva međusobno se isključuju načini rada:
Režim ispravljanja (ispravka) grešaka (jer d min =3, tada vam omogućava da ispravite pojedinačne greške);
Način otkrivanja greške (jer d min =3, tada detektuje greške višestrukosti q£2). Ako sindrom nije jednak 0, tada dekoder izdaje signal greške.
Ako postoje 2 greške u primljenoj kodnoj riječi, a dekoder radi u modu korekcije, tada neće moći po sindromu odrediti da li je došlo do jedne ili dvije greške, te će izvršiti netačnu korekciju kodne riječi.
Prošireni Hamingov kod. Načini rada dekodera, korektivne i detekcijske sposobnosti. Formiranje kodne riječi. Formiranje kontrolne matrice proširenog Hamingovog koda. Tumačenje sindroma greške
Proširenje Hammingovog koda je da dopuni kodne vektore dodatnim bitom tako da je broj onih sadržanih u svakoj kodnoj riječi paran. Zbog toga imaju Hamming kodovi sa provjerom parnosti sledeće pogodnosti:
Dužina koda se povećava sa 2 w-1 do 2 w, što je pogodno u smislu prenosa i skladištenja informacija;
Minimalna udaljenost d min proširenih Hamming kodova je 4, što omogućava detekciju (!) trostrukih grešaka.
Dodatni bit parnosti omogućava da se dekoder koristi u novom hibridni način rada– otkrivanje i ispravljanje grešaka.
Razmotrite proširenje (7,4,3) Hamingovog koda.
Svaki kodni vektor C a se dobija iz kodnog vektora c dodavanjem dodatnog bita parnosti C a = ( c 1 , ..., c 7, c 8), gdje .
Checking Matrix H(8,4)-kod se dobija iz kontrolne matrice (7,4)-koda u dva koraka:
Nulta kolona se dodaje u matricu (7,4)-koda;
Rezultirajuća matrica je dopunjena redom koji se u potpunosti sastoji od jedinica.
Dobijamo:
Sa sindromskim dekodiranjem
s" = C"Ä H T ,
i sve komponente s" moraju biti jednake 0.
Sa jednom greškom, s "(4) = 1. Po vrijednosti sindroma (niža 3 bita) nalazimo i ispravljamo (invertujemo) pogrešan bit.
At dupla greška komponenta s"(4) = 0, a sindrom je različit od nule. Za razliku od standardni kod Hamming takvu situaciju već otkriveno, ali se ne ispravlja (šalje se zahtjev za ponovnim prijenosom riječi, itd.).
Stoga se prošireni Hamming dekoder može koristiti u jednom od dva međusobno isključiva načina:
Za ispravljanje pojedinačnih i otkrivanje dvostrukih grešaka;
Za otkrivanje trostrukih grešaka.
