Doar ca exemplu, am luat în considerare cele mai simple coduri de corecție - un cod simplu de verificare a parității care detectează o singură eroare într-o secvență primită și un cod iterativ bloc și un cod cloud care corectează o singură eroare folosind un set de verificări de paritate. În toate codurile, în procesul de codificare de corectare a erorilor, s-au format biți suplimentari, adăugați la combinația de cod inițială.
Să stabilim regulile formale (de generare) conform cărora se realizează codificarea, adică. conversia secvenței de informații într-un cuvânt cod.
Cel mai simplu mod de a descrie sau de a atribui coduri de corecție este mod tabelar,în care fiecărei secvențe de informații i se atribuie pur și simplu un cuvânt de cod din tabelul de coduri. De exemplu, pentru cel mai simplu cod cu verificarea parității, tabelul de corespondență dintre combinațiile sursă și cod va fi următorul:
Acest mod de a descrie codurile este aplicabil pentru orice cod, nu doar pentru coduri liniare. Cu toate acestea, pentru mari La marimea tabelul de coduri se dovedește a fi prea mare pentru a fi folosit în practică.
O altă modalitate de a defini codurile de bloc liniare este utilizarea așa-numitelor sisteme de generare a ecuațiilor, definirea regulii după care sunt convertite caracterele secvenței informaționale caractere de cod... Pentru același exemplu, sistemul de generare a ecuațiilor va arăta astfel:
Cu toate acestea, cel mai convenabil și intuitiv mod de a descrie codurile bloc liniare este să le definiți folosind matrice generatoare, care este o formă compactă de reprezentare a sistemului de ecuații de testare.
Bloc liniar(l, / s) -codul este determinat complet de matricea G cu dimensiune La X P cu elemente matrice binare. Mai mult, fiecare cuvânt de cod este o combinație liniară a rândurilor matricei G și fiecare combinație liniară a rândurilor lui G este un cuvânt de cod.
Vor fi apelate coduri de bloc liniare definite prin generarea de matrici codurile matriceale. Reprezentarea obișnuită (canonică) a matricei generatoare arată astfel: 
De exemplu, pentru cel mai simplu (4, 3) cod de verificare a parității, matricea generatoare va arăta astfel: 
Lăsa T -(t 1; t 2, ..., t la) va fi blocul de mesaje care trebuie codificat folosind acest cod.
Apoi cuvântul de cod corespunzător U voi
Ținând cont de structura matricei G caractere de cuvinte de cod și va fi asa:
Cu alte cuvinte, La simbolurile cele mai din stânga ale cuvântului cod coincid cu simbolurile secvenței de informații codificate, iar restul (n - La) caracterele sunt combinații liniare de caractere secvențe de informații.
De exemplu, dacă secvența de intrare a codificatorului t == (10 1), apoi folosind matricea generatoare codul va fi construit după cum urmează:
8 Căpetenia a trimis trei cercetători pe primul drum, trei pe al doilea, doi pe al treilea și a mers el însuși pe al patrulea. Creați o matrice generatoare pentru un astfel de cod.
Răspuns: Potrivit complotului sarcinii, mesajul primit de comandant personal nu poate fi distorsionat. Prin urmare, ne vom restrânge la studiul informațiilor transmise de luptători. Într-un grup care pornește de-a lungul unuia dintre drumuri, fiecare soldat trebuie să raporteze comandantului fie despre detectarea unui obiect (vom desemna un astfel de raport drept „1”), fie despre absența unui obiect („0” ). În absența distorsiunii, rapoartele fiecărui luptător din aceeași grupă trebuie să fie aceleași. Prin urmare:
Matricea poate fi adusă la forma canonică prin renumerotarea luptătorilor, adică. pe primul drum, trimițând primul, al patrulea și al cincilea, pe al doilea drum - al doilea, al șaselea și al șaptelea, pe al treilea drum - al treilea și al optulea luptători. Obținem următoarea matrice generatoare:
Codul definit în acest fel este numit bloc liniar sistematic(P,/ cod cj cu verificări de paritate generalizate.
În sistemele de comunicații, sunt posibile mai multe strategii de tratare a erorilor:
- detectarea erorilor în blocurile de date și cerere de retransmisie automată blocuri deteriorate - această abordare este utilizată în principal la nivel de legătură și transport;
- detectarea erorilor în blocurile de date și eliminarea blocurilor proaste - această abordare este uneori folosită în sistemele media de streaming unde întârzierea transmisiei este importantă și nu există timp pentru retransmisie;
- corectarea erorii(ing. corectarea erorilor înainte) se aplică la nivel fizic.
Codurile de detectare și corectare a erorilor
Codurile de corectare sunt coduri folosite pentru detectarea sau corectarea erorilor care apar în timpul transmiterii informațiilor sub influența interferenței, precum și în timpul stocării acesteia.
Pentru a face acest lucru, atunci când scrieți (transferați), adăugați la sarcina utilă într-un mod special structurat exces informații, iar la citire (recepție) acestea sunt utilizate pentru a detecta sau corecta erori. Desigur, numărul de erori care pot fi corectate este limitat și depinde de codul specific utilizat.
CU coduri de corectare a erorilor, strâns legate coduri de detectare a erorilor... Spre deosebire de prima, cea din urmă poate stabili doar faptul că există o eroare în datele transmise, dar să nu o corecteze.
De fapt, codurile de detectare a erorilor utilizate aparțin acelorași clase de coduri ca și codurile de corectare a erorilor. De fapt, orice cod de corectare a erorilor poate fi folosit și pentru a detecta erori (făcând astfel, va putea detecta Mai mult erori decât le-a putut remedia).
Prin modul de lucru cu datele, codurile care corectează erorile sunt împărțite în blocîmpărțirea informațiilor în fragmente de lungime constantă și procesarea fiecăruia separat și convoluțională care tratează datele ca pe un flux continuu.
Blocați coduri
Lasă informațiile codificate să fie împărțite în fragmente de lungime k biți care sunt convertiți în cuvinte de cod lungimea n pic. Apoi, codul de bloc corespunzător este de obicei notat ( n,k). În acest caz, numărul este apelat viteza codului.
Dacă originalul k bit codul lasă neschimbat și adaugă n − k verificare, acest cod este numit sistematic, in caz contrar nesistematic.
Puteți seta codul de bloc în diferite moduri, inclusiv un tabel, unde fiecare set de k biții de informații sunt mapați n fragment din cuvântul cod. Dar, cod bun trebuie să îndeplinească cel puțin următoarele criterii:
- capacitatea de a corecta cât mai multe erori posibil,
- cât mai puțină redundanță,
- ușurință de codare și decodare.
Este ușor de observat că cerințele date se contrazic. De aceea există un numar mare de coduri, fiecare dintre acestea fiind potrivit pentru propria sa gamă de sarcini.
Aproape toate codurile folosite sunt liniare. Acest lucru se datorează faptului că codurile neliniare sunt mult mai dificil de studiat și este dificil pentru ele să ofere o ușurință acceptabilă de codare și decodare.
Spații liniare
Matricea generativă
Această relație stabilește o relație între vectorii de coeficienți 
și vectori. Enumerând toți vectorii coeficienților, puteți obține toți vectorii. Cu alte cuvinte, matricea G generează spațiu liniar.
Verificați matricea
Aceasta înseamnă că operația de codificare corespunde înmulțirii originalului k-bit vector la o matrice nedegenerată G numit matrice generatoare.
Fie un subspațiu ortogonal în raport cu C, A H este matricea care definește baza acestui subspațiu. Atunci pentru orice vector este adevărat:
.
Proprietăți și teoreme importante
Distanta minima si capacitate de corectare
Hamming frontieră și coduri perfecte
Să existe un bloc binar ( n,k) cod cu capacitate de corectare t... Apoi inegalitatea (numită granița lui Hamming):
.
Se numesc coduri care satisfac această limită cu egalitate perfect... Codurile perfecte includ, de exemplu, codurile Hamming. Codurile cu o putere corectivă mare (cum ar fi codurile Reed-Solomon), care sunt adesea folosite în practică, nu sunt perfecte.
Câștig de energie
La transmiterea informaţiei pe un canal de comunicaţie, probabilitatea de eroare depinde de raportul semnal-zgomot la intrarea demodulatorului, astfel, la un nivel de zgomot constant, puterea emiţătorului este de o importanţă decisivă. În sistemele de satelit și mobil, precum și în alte tipuri de comunicații, problema economisirii energiei este acută. În plus, în anumite sisteme comunicațiile (de exemplu, telefon) pentru a crește puterea semnalului fără limită nu sunt date de restricții tehnice.
Deoarece codarea de corectare a erorilor permite corectarea erorilor, atunci când este utilizată, puterea emițătorului poate fi redusă, lăsând rata de transmitere a informațiilor neschimbată. Câștigul de energie este definit ca diferența dintre SNR în prezența și absența codării.
Aplicație matricea de verificare a parității- - [L.G. Sumenko. Dicționarul englez rus al tehnologiei informației. M .: GP TsNIIS, 2003.] Subiecte tehnologii informaționale în general EN matrice de verificare ... Ghidul tehnic al traducătorului
În domeniul matematicii și al teoriei informației, codul de linie este un tip important de cod bloc utilizat în schemele de detectare și corectare a erorilor. Codurile liniare, în comparație cu alte coduri, permit implementarea unor algoritmi mai eficienți ... ... Wikipedia
Pentru a îmbunătăți acest articol, este de dorit?: Găsiți și aranjați sub formă de note de subsol linkuri către surse autorizate care confirmă ceea ce a fost scris. Cod ciclic... Wikipedia
Codul ciclic este un cod liniar cu proprietatea ciclicității, adică fiecare permutare ciclică a unui cuvânt de cod este, de asemenea, un cuvânt de cod. Folosit pentru a transforma informațiile pentru a le proteja de erori (vezi Detectare și ... ... Wikipedia
- (Cod LDPC din engleză Cod de verificare a parității de densitate scăzută, cod LDPC, cod de densitate scăzută) cod utilizat în transmiterea informațiilor, un caz special al unui cod liniar bloc cu verificare de paritate. O caracteristică este densitatea scăzută a semnificative ... ... Wikipedia
Cod de verificare a parității de densitate scăzută (cod LDPC, cod LDPC) cod utilizat în transmiterea informațiilor, un caz special al unui cod de linie bloc cu verificarea parității. Caracteristică ...... Wikipedia
Codurile Reed-Solomon sunt coduri ciclice non-binare care vă permit să corectați erorile din blocurile de date. Elementele vectorului de cod nu sunt biți, ci grupuri de biți (blocuri). Codurile Reed Solomon sunt foarte comune, ... ... Wikipedia
Introducere
Descrierea procesului de comunicare digitală
Sursa emite un mesaj reprezentând în caz general niste semnal electric... Acest semnal este convertit în formă digitală, care este convenabil pentru prelucrare ulterioară.
Apoi, informația este comprimată (codare sursă), ceea ce reduce la minimum redundanța mesajului. Codarea sursă reduce costurile de transmitere și stocare a informațiilor. După aceea, mesajul ar trebui transmis pe un canal zgomotos. Pentru ca mesajul să ajungă la consumator într-o formă nedistorsionată, se utilizează codificarea informațiilor imună la zgomot (codarea canalului). Pe partea de consumator, informațiile sunt decodificate. Decodorul de canal corectează erorile din cuvântul primit, iar decodorul sursă convertește cuvântul corectat într-o formă convenabilă pentru consumator.
Când vorbim despre coduri care controlează erorile, ar trebui să se distingă două strategii de utilizare a acestora.
- Corectarea directă a erorilor din cauza redundanței (Forward Error Correction - FEC).
- Detectarea erorilor cu cereri ulterioare de retransmitere a informațiilor primite eronat (Automatic Repeat Request - ARQ).
Atunci când alegeți metode de codificare și decodare, acestea sunt ghidate de mulți factori, a căror relație este prezentată în figură.
Complexitatea totală include costurile hardware și software pentru implementarea codificatorului și decodorului, costul stocării și transmiterii informațiilor etc. Debitul de date include transmiterea de informații utile, biți de verificare, precum și solicitări și repetiții pentru acestea. solicitările blocurilor de informații individuale.
Codare anti-interferență
Informatii generale
Sistemele reale de transmisie a datelor nu sunt perfecte. Aplicând tehnologia informației, trebuie să ținem cont de posibilitatea unor erori în transmiterea și stocarea informațiilor. Acest lucru se aplică în primul rând
- stocarea informațiilor pe medii de înaltă densitate (medii magnetice, CD-ROM, DVD);
- transmisie de date cu putere limitată a semnalului (satelit și conexiune mobilă);
- transmiterea de informații prin canale foarte zgomotoase (comunicații mobile, de mare viteză linii de sârmă comunicare);
- canale de comunicare cu cerințe crescute pentru fiabilitatea informațiilor ( retele de calculatoare, linii de transmisie cu compresie de date).
În toate cazurile de mai sus, sunt utilizate coduri de control al erorilor.
Considera cel mai simplu model transmiterea datelor folosind codificarea corectoare a erorilor.
Lăsați codificatorul sursă să scoată secvențial cuvinte de informații cu lungime fixă. Codificatorul de canal înlocuiește fiecare cuvânt de informare u cu un cuvânt de cod v. Emițătorul generează semnale corespunzătoare cuvântului de cod v și le trimite către canal. Receptorul produce transformare inversă, în urma căruia cuvântul binar primit r este trimis către decodor. Decodorul compară cuvântul primit r cu toate cuvintele de cod posibile ale codului utilizat. Dacă cuvântul r coincide cu unul dintre cuvintele cod, atunci cuvântul de informare corespunzător este livrat consumatorului. Dacă r diferă de toate cuvintele de cod, atunci a apărut o eroare detectabilă pe canal. Scopul utilizării codării canalelor este de a obține o potrivire a transmisiei cuvânt de informare u și cuvântul informațional primit u ′.
Din a acestei descrieri Se pot trage 2 concluzii:
- Dacă, în timpul transmisiei pe un canal zgomotos, un cuvânt de cod este mapat într-un alt cuvânt de cod care nu se potrivește cu cel transmis, apare o eroare nedetectabilă. Să o numim eroare reziduală de decodare.
- Este necesar să construiți coduri cu o anumită structură matematică care vă permite să recunoașteți eficient și, în unele cazuri, să corectați erorile care apar atunci când informațiile sunt transmise printr-un canal de comunicare.
Coduri de bloc liniare
Codurile bloc binare liniare formează o familie importantă de coduri. Aceste coduri sunt remarcabile prin faptul că, reprezentând informații și cuvinte de cod sub formă de vectori binari, putem descrie procesele de codificare și decodificare folosind aparatul algebrei liniare. În acest caz, componentele vectorilor și matricelor introduse sunt simbolurile 0 și 1. Operațiile pe componente binare se efectuează conform regulilor aritmetică modulo 2.
Cel mai faimos cod de linie este codul Hamming bloc. Mai mult, descrierea codurilor de bloc liniare se va face folosind acest cod ca exemplu. În special, va fi luat în considerare codul Hamming (7,4).
Codificatorul de cod de bloc binar (n, k) mapează un set de 2 k cuvinte de informații binare posibile într-un set de 2 k cuvinte de cod n-dimensionale. În teoria codificării, există întotdeauna o corespondență unu-la-unu între aceste mulțimi.
În loc de k biți ai vectorului de informații, n biți ai vectorului de cod sunt transmiși către canal. În acest caz, se vorbește de codificare redundantă la o rată: R = n ⁄ k.
Cu cât viteza este mai mică, cu atât este mai mare redundanța codului și cu atât posibilitățile de protecție împotriva erorilor sunt mai mari. Cu toate acestea, trebuie avut în vedere că odată cu creșterea redundanței crește și costul transferului de informații.
Descrierea proceselor de codificare și decodare
Materialul inițial pentru construirea construcțiilor de cod este un spațiu vectorial binar n-dimensional, în care operațiile aritmetice sunt date modulo 2. Acesta conține un k-dimensional. spațiu liniar conţinând 2 k cuvinte de cod. Codul C este format folosind 2 k combinații de k vectori de bază liniar independenți (g 1, ..., g k).
Acești vectori formează rândurile matricei generatoare a codului C.
Pentru un cod C, există un cod dual C d, astfel încât produsul scalar al oricărei perechi de vectori, dintre care unul aparține spațiului C și celălalt spațiului C d, este întotdeauna zero. Aceasta înseamnă că vectorii codului C d sunt ortogonali cu vectorii codului C. Pe de altă parte, dacă un vector este ortogonal cu toți vectorii codului C, atunci aparține codului C d și invers. . Subspațiul vectorial dual este „întins” de n - k vectori de bază liniar independenți (h 1,..., h n - k). Acești vectori formează rândurile matricei de verificare a parității.
Luați în considerare un exemplu de matrice de generare și verificare a parității pentru un cod Hamming (7,4):
 |
 |
O proprietate importantă trebuie remarcată: atât matricea generatoare, cât și matricea de paritate conțin matricea de identitate. Această proprietate este utilizată în procesele de codificare și decodare.
Codificarea
Cuvântul cod v și cuvântul informațional u sunt legate prin raportul:
unde G este matricea generatoare, a cărei structură a fost descrisă mai sus.
De exemplu, vectorul de informații u = (1010) se mapează la vectorul de cod după cum urmează:
Este ușor de observat că ultimii patru biți ai vectorului de cod coincid cu vectorul de informații. Această proprietate se numește consistența codului.
Codurile în care un cuvânt de informare poate fi extras direct din vectorul de cod corespunzător se numesc sistematice. Matricea generatoare a oricărui cod sistematic poate fi întotdeauna redusă la următoarea formă prin rearanjarea coloanelor:
G k × n = (P k × (n - k) I k),
unde I k este matricea de identitate k × k.
Astfel, este întotdeauna posibilă identificarea informațiilor și verificarea simbolurilor în vectorul de cod al codului sistematic.
Rolul caracterelor de verificare și utilizarea lor vor fi explicate în detaliu mai jos.
Decodare
Sarcina decodorului este de a restaura vectorul de informații transmis folosind structura codului, bazată pe cuvântul primit r. Pentru codul Hamming (7, 4) considerat mai sus, se poate propune următorul algoritm de detectare a erorilor. Deoarece codul considerat este sistematic, exprimăm fiecare dintre cele trei simboluri de paritate în termeni de simboluri vectoriale de informații:
V 0 = v 3 ⊕ v 5 ⊕ v 6
v 1 = v 3 ⊕ v 4 ⊕ v 5
v 2 = v 4 ⊕ v 5 ⊕ v 6
Dacă apare o eroare în canal, atunci în vectorul r primit cel puțin una dintre egalități nu va fi îndeplinită. Să scriem relațiile de test obținute sub forma unui sistem de ecuații pentru componentele vectorului 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
Astfel, din primele trei coloane ale matricei generatoare G, am obținut un sistem de trei ecuații de verificare. Dacă în sistemul de ecuații obținut cel puțin una dintre componente (s 0, s 1, s 2) nu este egală cu zero, atunci a apărut o eroare în canal.
Scriem sistemul de ecuații de verificare în vedere generala... Pentru orice cod sistematic cu o matrice generatoare G, matricea de verificare a parității este definită după cum urmează:
H (n - k) × n = (I n - k P T k × (n - k)).
Apoi sistemul de ecuații de testare poate fi scris sub forma
Vectorul s este denumit în mod obișnuit sindrom. Astfel, o eroare va fi detectată dacă cel puțin una dintre componentele lui nu este zero.
Ca exemplu, luați în considerare decodificarea sindromică a codului Hamming (7, 4). Când se transmite un cuvânt de informare u = (1010) pe un canal fără zgomot, r = v = (0011010). Ne putem asigura că în acest caz sindromul este egal cu 0.
Dacă, de exemplu, în cuvânt cod a existat o singură eroare la a patra poziție (r = (0010010)), apoi al patrulea rând al matricei de verificare transpusă este sindromul.
După ce parcurgem toate pozițiile posibile ale unei singure erori, obținem tabel complet sindroame de eroare unică - un tabel de corespondențe ale numărului cifrei eronate cu sindromul rezultat.
| Descărcare eronată | r 0 | r 1 | r 2 | r 3 | r 4 | r 5 | r 6 |
|---|---|---|---|---|---|---|---|
| Sindromul s | 100 | 010 | 001 | 110 | 011 | 111 | 101 |
Se poate observa că o eroare în poziția i-a a cuvântului de cod corespunde sindromului format de coloana i-a a matricei H. Deoarece toate coloanele matricei sunt diferite, putem folosi tabelul de sindrom pentru a corectează o singură eroare introdusă de canal.
Varietăți de erori
Codurile de bloc liniare au 3 tipuri de erori:
- Eroare recunoscută și corectabilă
- Sindromul este prezent în tabelul sindroamelor
- Decodorul recunoaște și corectează eroarea și apoi transmite cuvântul corect către receptor
- Eroare recunoscută
- Cuvântul primit nu se potrivește cu niciunul dintre cuvintele de cod
- Sindromul nu este prezent în tabelul sindroamelor
- Decodorul recunoaște eroarea și trimite o solicitare de retransmitere a cuvântului de date.
- Eroare de nerecunoscut
- Cuvântul primit se potrivește cu unul dintre cuvintele de cod (nu se potrivește cu cuvântul de cod original)
- Sindromul este 0
- Decodorul nu recunoaște eroarea și emite un mesaj de informare eronat către consumator
Concluzie
Trebuie remarcat faptul că eficacitatea unui anumit cod depinde de zona de aplicare a acestuia și, în special, de canalul de comunicare. Dacă raportul semnal-zgomot în canal este suficient de mare, atunci probabilitatea unei singure erori este de multe ori mai mare decât probabilitatea unor erori de ordin superior, prin urmare, utilizarea codului Hamming cu corectarea unei singure erori într-un astfel de canal poate fi foarte eficient. Pe de altă parte, în canalele în care predomină erorile multiple (de exemplu, canalele cu estompare), corectarea erorilor individuale este lipsită de sens. La alegere practică a unui cod specific de corectare a erorilor, este de asemenea necesar să se țină cont de viteza decodării acestuia și de complexitatea implementării sale tehnice.
Literatură
- Werner M. Fundamentele codificării. - M .: Technosphere, 2004.
- Bleihut R. Teoria și practica codurilor de control al erorilor. - M .: Mir, 1986.
Oleg Rybak
Într-adevăr, este dificil să găsești o explicație adecvată. Cel mai adesea, autorii presupun că cititorul știe multe dinainte și nu caută să explice puncte aparent simple care conțin esența. Foarte bucuros că am dat peste acest material, am clarificat ceva pentru mine.
Codurile liniare au următoarea proprietate:
Dintre toată mulţimea 2 k dintre cuvintele de cod permise care formează un grup liniar, se pot distinge subseturile k cuvinte care au proprietatea de independență liniară.
Independența liniară înseamnă că niciunul dintre cuvintele incluse în subsetul de cuvinte de cod independente liniar nu poate fi obținut prin însumarea (folosind o expresie liniară) oricăror alte cuvinte incluse în acest subset.
În același timp, oricare dintre cuvintele de cod permise poate fi obținut prin însumarea anumitor cuvinte liniar independente.
Astfel, construcția combinațiilor de cod ale unui cod liniar este asociată cu operații liniare. Pentru a efectua astfel de operațiuni, este convenabil să utilizați un aparat de calcul matriceal bine dezvoltat.
Pentru educatie n Cuvintele de cod de biți din cuvintele codificate de k biți (codificare) folosesc o matrice, care se numește generare (generare).
Matricea generatoare se obține prin scrierea k cuvinte liniar independente într-o coloană.
Să notăm secvența de informații codificate Xși o vom scrie sub forma unei matrice de rând || X || dimensiune 1* k, de exemplu:
|| X || = || 11001 ||, Unde k = 5.
Una dintre modalitățile de a construi o matrice generatoare (generatoare) este următoarea: Este construită din matricea de identitate || I || dimensiune k * kși matricea de cifre suplimentare (redundante) alocate acestuia din dreapta || MDR || dimensiuni k * r.
unde la k=4
Această structură a OM oferă un cod sistematic.
Procedura de construire a matricei MDS va fi discutată mai jos.
7.4 Ordinea de codificare
Cuvântul de cod KS se obține prin înmulțirea matricei secvenței informaționale || X || pe matricea generatoare || ОМ ||:
Înmulțirea se realizează după regulile înmulțirii matriceale: (SO pe SO)
Trebuie doar să rețineți că adăugarea aici este modulo 2.
de exemplu, matricea generatoare
|| ОМ || = 0010 011
și vectorul rând al secvenței de informații
Deoarece matricea de înmulțit are un singur rând, înmulțirea este simplificată. În acest caz, ar trebui să atribuiți rândurile matricei generatoare (generatoare). || OM || biți ai matricei secvenței informaționale || X ||și adăugați acele rânduri ale matricei generatoare (generatoare) care corespund cifrelor unității ale matricei || X ||.
observa asta || KC || = || X, ДР ||,
Unde || X || - secvență de informații (deoarece înmulțită cu matricea de identitate || I ||),
A || DR ||- cifre suplimentare, în funcție de matricea de cifre suplimentare || MDR ||:
|| DR || = || X || * || MDR ||
7.5 Ordinea de decodare
Ca rezultat al transmiterii cuvântului de cod prin canal, acesta poate fi distorsionat de interferență. Acest lucru va cauza cuvântul de cod acceptat || PKS || este posibil să nu se potrivească cu originalul || COP ||.
Distorsiunea poate fi descrisă folosind următoarea formulă:
|| PKS || = || KS || + || ÎN ||,
Unde || ÎN ||- vector de eroare - matrice-rând cu dimensiunea 1* n, Cu 1 în acele poziții în care s-a produs distorsiunea.
Decodificarea se bazează pe găsirea așa-numitului sindrom de identificare sau matrice de eroare-rând || OP || lungimea r cifre ( r- numărul de biți suplimentari sau redundanți din cuvântul de cod).
Identificatorul este utilizat pentru a găsi vectorul de eroare estimat.
Identificatorul se găsește prin următoarea formulă:
|| OP || = || PCS || * || TPM ||,
Unde || buc || - cuvânt de cod primit și posibil corupt;
|| TPM ||, - matricea de paritate transpusă care se obține din matricea de umplutură || MDR || atribuindu-i matricea de unitati de mai jos:
Exemplu || TPM ||:
În măsura în care || PKS || = || KS || + || BO ||, ultima formula poate fi scrisa ca:
|| OP || = || KS || * || TPM || + || VO || * || TPM ||.
Luați în considerare primul termen.
|| KC || este o matrice de rând, iar prima k cifre – informative.
Să demonstrăm acum că produsul cuvântului de cod || COP || pe || TPM || rezultă o matrice zero ||0||.
În măsura în care || COP ||- matrice-rând, este posibilă o ordine simplificată de înmulțire a matricelor considerate mai sus.
Prin urmare, primul termen în
|| OP || = || KS || * || TPM || + || ÎN || * || TPM ||
întotdeauna egal cu zero și identificatorul este complet dependent de vectorul de eroare || ÎN ||.
Dacă alegem acum o astfel de matrice de verificare a parității TPMși, prin urmare MDR astfel încât diferiți vectori de eroare să corespundă unor identificatori diferiți OP, apoi din acești identificatori se va putea găsi vectorul de eroare ÎN,și, prin urmare, corectați aceste erori.
Corespondența identificatorilor cu vectorii de eroare se găsește în prealabil prin înmulțirea vectorilor erorilor corectabile cu TPM;
Astfel, capacitatea unui cod de a corecta erori este în întregime determinată de || MDR ||. Pentru constructie MDR pentru codurile care corectează erori individuale, aveți nevoie în fiecare linie MDR au cel putin 2 unitati. În acest caz, este, de asemenea, necesar să existe cel puțin o diferență între oricare două linii MDR.
Codul pe care l-am primit este incomod prin faptul că identificatorul, deși este asociat fără ambiguitate cu numărul bitului distorsionat, deoarece un număr nu este egal cu acesta. Pentru a căuta un bit distorsionat, trebuie să utilizați un tabel de corespondență suplimentar între identificator și acest număr. Au fost găsite codurile în care identificatorul ca număr determină poziția cifrei distorsionate și au primit numele Codurile de hamming.
Clădire MDR căci cazul corectării mai multor erori devine mult mai complicat. Diferiți autori au găsit diferiți algoritmi de construcție || MDR || pentru acest caz, iar codurile corespunzătoare sunt denumite după numele autorilor lor.
Fie x1, x2, ..., xk să desemneze un cuvânt de k biți de informație la intrarea codificatorului, codificat într-un cuvânt de cod C de dimensiunea n biți:
intrare codificator: X=[X 1, X 2, ...,xk]
ieșire codificator: C=[c 1, c 2, ..., cn]
Să fie dată o matrice generatoare specială G n, k,
setare cod de bloc (n,k).
Rânduri de matrice G n, k trebuie să fie liniar independent.
Atunci combinația de cod permisă este C corespunzătoare cuvântului codificat X:
C=X 1 g 1 + X 2 g 2 + ... + x k g k.
Forma sistematică (canonică) a matricei generatoare G marimea k X n :
Matricea generativă a unui cod sistematic creează un cod bloc liniar în care primul k biții oricărui cuvânt de cod sunt identici cu biții de informație, iar restul r=n-k biții oricărui cuvânt de cod sunt combinații liniare k biți de informații.
Verificați matricea H n, k Are r X n elemente și este adevărat:
C X H T = 0.
Această expresie este folosită pentru a verifica cuvântul de cod primit. Dacă egalitatea cu zero nu este satisfăcută, atunci obținem matricea rândurilor || c 1 , c 2 , ..., c r|| numit sindrom de eroare.
Cod Hamming. Abilități corective și de detectare. Reguli pentru alegerea relației dintre lungimea cuvântului de cod și numărul de biți de informație. Formarea matricelor generatoare și de paritate ale codului Hamming. Interpretarea sindromului de eroare
Luați în considerare un cod Hamming cu distanța de cod d= 3, permițându-vă să corectați erori individuale ( d=2q max+1).
Numărul de combinații de coduri permise pentru un cod cu d= 3, pentru că codul Hamming este strict egal cu 2 n/(n+1). Primul k biți de combinații de cod ale codului sunt utilizați ca informații și numărul lor este egal cu
k= log 2 (2 n/(n+1)] = n- jurnalul 2 ( n+1).
Această ecuație are soluții întregi k= 0, 1, 4, 11, 26, care determină codurile Hamming corespunzătoare: (3,1) -cod, (7,4) -cod, (15,11) -cod etc. (mereu n=2w‑1).
Verificați matricea H Cod Hamming ( r=n-k linii şi n coloane): pentru un cod binar (n, k) n = 2 w -1 coloanele constau din toți vectorii binari posibili cu r = n-k elemente, excluzând un vector cu toate elementele zero.
Este ușor să verifici asta G X H T= 0 (matrice zero de dimensiune k X r elemente).
Exemplu. Să verificăm funcționarea codului atunci când trimitem un mesaj X= 1011. Cuvântul de cod transmis va fi format sub forma combinație liniară(adăugare modulo 2) rândurile nr. 1, 3, 4 ale matricei G 7,4:
Să presupunem că cuvântul de cod transmis C eroarea 0000100 a fost afectată, ceea ce a dus la primirea partea de primire cuvintele C"=10111 10.
Apoi, înmulțind C „cu matricea de verificare a parității H T obținem matricea de rând a sindromului de eroare, care corespunde acelei coloane a matricei de verificare H cu numărul bitului care conține eroarea.
Comparând sindromul rezultat cu șiruri H T, obținem că bitul # 5 din stânga este greșit.
Decodorul Hamming poate funcționa în două se exclud reciproc moduri:
Modul de corectare (corecție) a erorilor (de când d min = 3, atunci vă permite să remediați erori individuale);
Modul de detectare a erorilor (din moment ce d min = 3, apoi detectează erori de multiplicitate q 2 lire sterline). Dacă sindromul nu este egal cu 0, atunci decodorul emite un semnal de eroare.
Dacă există 2 erori în cuvântul de cod primit și decodorul funcționează în modul de corecție, atunci acesta nu va putea determina prin sindrom dacă au apărut una sau două erori și va efectua o corecție incorectă a cuvântului de cod.
Cod Hamming extins. Moduri de funcționare a decodorului, capabilități de corectare și detectare. Formarea unui cuvânt cod. Formarea matricei de verificare a parității a codului Hamming extins. Interpretarea sindromului de eroare
Extinderea codului Hamming constă în completarea vectorilor de cod cu un bit binar complementar astfel încât numărul de uni conținut în fiecare cuvânt de cod să fie par. Din acest motiv, codurile Hamming verificate de paritate au urmatoarele avantaje:
Lungimile codurilor cresc de la 2 w-1 la 2 w, ceea ce este convenabil din punctul de vedere al transferului și stocării informațiilor;
Distanta minima d min. de coduri Hamming extinse este de 4, ceea ce face posibilă detectarea (!) erorilor de trei ori.
Un bit de paritate suplimentar permite decodorului să fie utilizat într-un nou modul hibrid- detectarea si corectarea erorilor.
Luați în considerare o extensie a codului Hamming (7,4,3).
Fiecare cod vector C a se obține dintr-un vector de cod c prin adăugarea unui bit de paritate suplimentar C a = ( c 1 , ..., c 7, c 8), unde.
Verificați matricea H Codul (8,4) este obținut din matricea de verificare a parității a codului (7,4) în doi pași:
Coloana zero este atașată la matricea codului (7,4);
Matricea rezultată este completată de un rând format în întregime dintr-o unitate.
Primim:
Cu decodare sindromică
s" = C"Ä H T,
în plus, toate componentele lui s „trebuie să fie egale cu 0.
Cu o singură eroare s „(4) = 1. După valoarea sindromului (cel mai puțin semnificativ 3 biți), găsim și corectăm (inversăm) bitul eronat.
La dubla eroare componenta s „(4) = 0, iar sindromul este diferit de zero. Spre deosebire de cod standard Situația lui Hamming este deja descoperit, dar nu este corectată (se trimite o solicitare de retransmitere a unui cuvânt etc.).
Astfel, decodorul Hamming extins poate fi utilizat în unul dintre cele două moduri care se exclud reciproc:
Pentru a corecta erori simple și duble;
Pentru a detecta erori triple.
