Provjerite matricu. Generiranje matrica blok kodova

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), što minimizira redundantnost poruke. 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.

1. Direktna korekcija greške zbog redundance (Forward Error Correction - FEC).
2. 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 preko 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 konstruisanje kodnih struktura je n-dimenzionalni binarni vektorski prostor, u kojem su specificirane aritmetičke operacije po modulu 2. Sadrži 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 kojeg 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 koristi strukturu koda, prema primljenoj riječi r, za vraćanje vektora prenesene informacije. 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 verifikacionih jednačina u opštem obliku. 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 se, na primjer, dogodila jedna greška u kodnoj riječi 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.

Možete vidjeti da je greška na i-toj poziciji kodna riječ odgovara sindromu formiranom od i-te kolone matrice H. Pošto su svi stupci matrice različiti, možemo ispraviti jednu grešku koju je uveo kanal koristeći tabelu sindroma.

Vrste grešaka

Linearni blok kodovi imaju 3 vrste grešaka:

1. Prepoznatljiva i ispravljiva greška
   • Sindrom je prisutan u tabeli sindroma
   • Dekoder prepoznaje i ispravlja grešku, a zatim šalje ispravnu riječ prijemniku
2. 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.
3. 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 korekcijom 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

1. Werner M. Osnove kodiranja. — M.: Tehnosfera, 2004.
2. 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, sa 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|| dužina 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.

Kao primjer, upravo smo razmotrili najjednostavnije korektivne kodove - kod s jednostavnom provjerom pariteta koji vam omogućava da otkrijete jednu grešku u primljenom nizu, 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. Osim toga, 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 bude 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 znakova 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.

Generativna matrica Linearni kod se naziva matrica veličine, čiji su redovi njeni bazni vektori.

Na primjer,

je generatorska matrica koda od dvije riječi (000, 011).

generira kod B iz primjera 6.3.

Znamo da su kodne riječi linearne kombinacije baznih vektora, tj. matrični redovi. To znači da se riječi mogu dobiti množenjem vektora matricom. Dakle, poruka je napisana kao vektor a kodna riječ koja odgovara poruci se izračunava po formuli

Tako se vektor bitova pretvara u niz binarni znakovi prenosi se preko kanala ili snima u memoriju uređaja za skladištenje.

Okrenimo se problemu dekodiranja.

Pretpostavimo da su za neki binarni vektor sve kodne riječi -koda , zadovoljiti identitet

gdje označava skalarni proizvod vektora i .

Za takav vektor kažemo da je ortogonan. Nakon što smo pronašli takav vektor, mogli bismo uz pomoć identiteta (6.2) provjeriti da li je sekvenca primljena iz kanala kodna riječ.

Imajte na umu da (6.2) vrijedi za sve kodne riječi ako vrijedi za bazne vektore, tj. ako

gdje superscript T označava transponiranje.

Što više takvih “provjera” pronađemo, to ćemo, po svemu sudeći, moći otkriti i ispraviti više grešaka.

Vježba 6.4. Dokažite da provjere formiraju linearni prostor.

Ovaj prostor nazivamo prostorom ortogonalnim linearnom kodu ili prostor za testiranje.

Vježba 6.5. Pronađite dimenziju linearni prostor provjere.

Da biste dovršili posljednju vježbu, morate primijetiti da matrica ima točno linearno nezavisne stupce. Ni više (zašto?) ni manje (zašto?). Popravljamo listu brojeva ovih kolona i zovemo ovaj skup brojeva set informacija. Nešto kasnije, značenje ovog imena će postati jasnije. Vrijednosti vektora biramo proizvoljno na pozicijama koje nisu uključene set informacija. Koje bi trebale biti vrijednosti na pozicijama skupa informacija da bi se (6.3) održao? Da bismo odgovorili na ovo pitanje, moraćemo da rešimo sistem linearnih jednačina, a sistem ima jedina odluka.

Posljedica ovih razmatranja je teorema

Teorema. Dimenzija kontrolnog prostora linearnog koda je jednaka .

Osnovu testnog prostora zapisujemo kao matricu

pozvao provjerite matricu kod.

Matrice provjere i generatora povezane su relacijom

Iz ove relacije vidimo da za bilo koju kodnu riječ imamo

Ovaj identitet se može koristiti kao kriterijum da proizvoljni niz pripada kodu, tj. za otkrivanje grešaka.

Znajući da možete pronaći. Da bismo razumjeli kako to učiniti, napominjemo da se isti kod može dati različitim matricama generatora odabirom baze prostora na različite načine. Štaviše, zamjenom bilo kojeg reda bilo kojom linearnom kombinacijom ovog reda s drugim redovima, dobijamo novu generirajuću matricu istog koda.

Permutiranje stupaca matrice, općenito govoreći, dovodi do drugog koda, ali se ovaj drugi kod po svojim karakteristikama ne razlikuje od originalnog. Pozivaju se kodovi koji se razlikuju samo u numeraciji pozicija ekvivalentan.

Jasno je da za svaki kod postoji ekvivalentan kod kojeg prve pozicije čine informacijski skup, tj. prvi stupci formiraju nesingularnu matricu veličine . Zamjenom redova linearnim kombinacijama redova (Gaussova metoda), rezultirajuća matrica se može svesti na oblik

gdje je matrica identiteta reda, i neka matrica veličine.

Matrica oblika (6.6) naziva se generirajuća matrica svedena na sistematski pogled, i poziva se odgovarajući kod sistematično. Kodiranje za sistematski kod je nešto lakše nego za kod opšti pogled:

, (6.7)

one. u kodnoj riječi, prve pozicije su samo kopija informacijskog niza, a preostale (testne) pozicije se dobijaju množenjem informacijskog vektora matricom veličine, koja je ponekad znatno manja od . Shodno tome, značajna je i informacija o sistematskom kodu manje memorije nego informacije o generalnom linearnom kodu.

Za sistematski kod sa generatorskom matricom u obliku (6.6), matrica provere se može izračunati po formuli

Vježba 6.6. Provjerite (6.7). Savjet: da biste to učinili, zamijenite (6.8) i (6.6) u (6.4).

Kako pronaći provjerite matricu za nesistematski kod?

Veoma jednostavno. Neophodno je matricu dovesti u sistematski oblik i koristiti (6.7). Ako prvi stupci generirajuće matrice formiraju nesingularnu podmatricu (prve pozicije čine skup informacija), tada su takve operacije kao što su permutacija redova i zamjena redova linearnim kombinacijama redova dovoljne da se svedu na sistematski oblik. Ako ne, prvo ćete morati pronaći skup informacija i prenumerisati pozicije tako da prve pozicije postanu informativne.

Pošto je, prema definiciji, linearni (n, /s)-kod dužine P iznad GF(q) je podprostor GFk(q) vektorski prostor GF n (q), tada mora postojati ortogonalni komplement podprostora GFk(q) kod linije (vidi pododjeljak 1.7.1).

Neka je H matrica čiji redovi odgovaraju baznim vektorima ortogonalnog komplementa g-arnog linearnog koda C dužine P. Zatim za bilo koji vektor sa, pripada kodu, fer:

Uslov (2.10) omogućava da se proveri da li proizvoljan n-niz elemenata GF(q) na određeni g-arni linearni kod.

Ako vektor linijskog koda ima Hamingovu težinu sho, to znači da u kodnoj riječi postoje sho simboli različiti od nule (prema definiciji Hammingove težine, vidi pododjeljak 2.1.4). Zatim, prema pravilima množenja matrice, proizvod vektora c s vrijednošću Hammingove težine sho i matrice H t odgovara linearnoj kombinaciji stupaca sho matrice N.Štaviše, jednakost (2.10) očito vrijedi ako i samo ako nema stupaca matrice H linearno zavisna.

Dakle, uslov za postojanje u skupu kodnih reči nekog linearnog koda kodne reči sa Hamingovom težinom w0 je prisustvo u matrici H linearno zavisne kolone u broju sho. Iz ovoga također slijedi da linearni kod ima minimalnu težinu (vidi pododjeljak 2.1.4) od barem neke vrijednosti w0 ako i samo ako je bilo koji w0 - 1 stupac matrice H linearno nezavisan. Prema tome, prema nejednakosti (2.6), da bi se pronašao linearni kod sa minimalnom težinom w0 koji ispravlja t greške, dovoljno je pronaći matricu H, koji ima najmanje sho - 1 = 2 -t bilo koje kolone su bile linearno nezavisne.

Pogledajmo bliže matricu N. Kao što je gore spomenuto, redovi matrice H su bazni vektori ortogonalnog komplementa linearnog koda. Ako skup od n nizova formira podprostor dimenzija da, tada će ortogonalni komplement ovog podprostora imati dimenziju PC(vidi podstavke 1.7.1 i 1.7.2). Dimenzioni podprostor P- to bilo koji oblik PC baznih vektora. Dakle, matrica H treba da sadrži PC linearno nezavisnim redovima.

Pošto su matrice G i H pripadaju istom prostoru n-niza, zatim broj stupaca matrice H jednak je broju stupaca matrice G. Dakle, matrica H ima veličinu (l - do) x l. Svi matrični stupci H, kao što je već pomenuto, formiraju linearnu nezavisne grupe on 2t kolone.

Prema relaciji (2.2), svaka kodna riječ linearnog koda je linearna kombinacija redova generirajuće matrice G koda. U ovom slučaju, očigledno, svaki red matrice G odgovara nekoj kodnoj riječi. Stoga se relacija (2.10) može prepisati na sljedeći način:

Rezultat proizvoda matrica G veličine za* da li H t veličina l x (PC) je matrica veličine to x (l - do), koji se sastoji od nula elemenata.

Matrix H veličina ( p-k) x n, čiji su redovi bazni vektori ortogonalnog komplementa podprostora linearnog koda, naziva se provjerite matricu linijski kod.

Prema relaciji (2.4), generirajuća matrica sistematskog linearnog koda sastoji se od matrice identiteta reda to i matrice čekovnih simbola veličine to x (l - do),što je, pak, produžetak matrice identiteta. Kao što je prikazano u Dodatku 1, množenje dvije matrice može se obaviti dijeljenjem pomnoženih matrica na matrice manji(blokovi) sa naknadnim množenjem pojedinačnih blokova pomnoženih matrica. Zatim za matrice G i H može se napisati:

Broj kolona u blokovima A i B matrice H 7 treba odgovarati broju linija u blokovima Ek i R matrice G (prema pravilima množenja matrica). Rezultirajuća matrica treba imati veličinu / s * (l - do). Očigledno, ako stavimo ALI = -R i AT= El_/s, zatim matrica Hće zadovoljiti jednačinu (2.11).

Dakle, matrica H t je produžetak matrice -R i pored matrice - R matrica H sadrži matricu identiteta reda P - to. Matrix H t je rezultat transpozicije matrice N.

Rezultat ponovljene transpozicije matrice je originalna matrica. Dakle, matrica H može se dobiti transponovanjem matrice N t. Budući da za bilo koji element a polja GF[ 2) a = - a je tačno, tada je za binarni linearni kod tačno R--R.

Matrix H binarni linearni kod će izgledati ovako:

Matrix R, koji je dio matrice G i sadrži simbole za provjeru, može se dobiti transponiranjem matrice R t, uključeno u matricu N.

Dakle, konstrukcija linearnog koda se svodi na pronalaženje matrice N. Prema datoj matrici H lako je pronaći matricu G.

Primjer 2.1.4. Razmotrite konstrukciju binarnog linearnog koda - koda preko GF(2) koji ispravlja jednu grešku kodne riječi s informacijskim nizom veličine to= 3 bita.

Prema relaciji (2.9), za kod sa maksimalna udaljenost r=2-t== 2. Tada je n = /c + r = 3 + 2 = 5. Međutim, kao što će biti pokazano u sljedećem pododjeljku, linearni binarni (5,3) kod nije sposoban ispraviti jednu grešku kodne riječi. U ovom slučaju, minimalni broj suvišnih znakova za ovaj slučaj G= 3, a razmatrani kod je binarni linearni (6,3)-kod.

Dakle, u ovaj slučaj matrica H sadrži kontrolnu matricu veličine /cx(l-/s) = 3 * 3 i matricu identiteta reda n-k \u003d 3.

Svi matrični stupci H moraju formirati linearno nezavisne grupe od dva stupca i linearno zavisnu grupu od tri kolone. Ovaj uslov je ispunjen, na primjer, sekvencama 101, 110 i 011 preko GF(2). Ovi nizovi formiraju stupce matrice R t, uključeno u matricu N. Ostali elementi matrice H odgovaraju matrici identiteta reda 3:

Dodavanje matrici identiteta reda 3 matrice P dobijene transponovanjem matrice R t, dobijamo matricu G:

Razmotrimo sada proces formiranja i strukturu kodne riječi binarnog linearnog (6, 3)-koda sa generirajućom matricom oblika (2.12):

Prva tri simbola kodne riječi (ci - Sz) sadrže informacijske simbole (/ 1 - g "z) nastale kao rezultat množenja matrice informacijskog niza i na matrici identiteta reda 3, koja je dio matrice G. Preostali simboli kodne riječi (C4 - C6) sadrže simbole za provjeru (t^ - tz), dobijen kao rezultat množenja matrice informacijskog niza sa matricom kontrolnih simbola R, takođe uključen u matricu G.

Lako je provjeriti da je u slučaju (6, 3)-koda iz primjera 2.1.4 minimalni broj simbola koji nisu nula među svim kodnim riječima tri (kodne riječi 001101, 010011, 100110 i 111000) . dakle, d*= 3 i, prema relaciji (2.5), kod mora ispraviti jednu grešku kodne riječi. Kao što će biti pokazano u sljedećem pododjeljku, to je zaista slučaj.