Construirea de matrice generatoare și de verificare a parității de coduri ciclice. Construirea unei matrice de verificare

Matricea generativă codul liniar se numește o matrice de dimensiune, ale cărei rânduri sunt vectorii de bază.

De exemplu,

este matricea generatoare a codului de două cuvinte (000, 011).

este generatorul pentru codul B din exemplul 6.3.

Știm că cuvintele de cod sunt combinații liniare de vectori de bază, adică. rânduri ale matricei. Aceasta înseamnă că cuvintele pot fi obținute prin înmulțirea unui vector cu o matrice. Deci, mesajul este scris ca un vector iar cuvântul cod corespunzător mesajului se calculează prin formulă

Astfel, vectorul de biți este convertit într-o secvență de simboluri binare transmise pe canal sau scrise în memoria dispozitivului de stocare.

Să trecem la problema decodării.

Să presupunem că pentru un vector binar toate cuvintele de cod ale codului , satisface identitatea

în care denotă produsul scalar al vectorilor și.

Spunem despre un astfel de vector că este ortogonal. După ce am găsit un astfel de vector, am putut verifica, folosind identitatea (6.2), dacă secvența primită de la canal este un cuvânt de cod.

Rețineți că (6.2) este valabilă pentru toate cuvintele de cod dacă este valabilă pentru vectorii de bază, de exemplu. dacă

unde superscriptul T indică transpunerea.

Cu cât găsim mai multe astfel de „verificări”, cu atât mai multe erori vom putea detecta și corecta.

Exercițiul 6.4... Demonstrați că verificările formează un spațiu liniar.

Acest spațiu va fi numit spațiu ortogonal unui cod liniar sau spatiu de verificare.

Exercițiul 6.5... Aflați dimensiunea spațiului liniar al cecurilor.

Pentru a finaliza ultimul exercițiu, trebuie să observați că matricea are coloane exact liniar independente. Nici mai mult (de ce?) Și nici mai puțin (de ce?). Să reparăm lista de numere a acestor coloane și să numim acest set de numere set de informații... Puțin mai târziu, semnificația acestui nume va deveni mai clară. Să alegem în mod arbitrar valorile vectorului în poziții care nu sunt incluse în setul de informații. Care ar trebui să fie valorile la pozițiile setului de informații pentru (6.3) să fie îndeplinite? Pentru a răspunde la această întrebare, este necesar să se rezolve un sistem de ecuații liniare, iar sistemul are o soluție unică.

O consecință a acestui raționament este teorema

Teorema. Dimensiunea spațiului de verificare a unui cod liniar este egală cu.

Scriem baza spațiului de testare sub forma unei matrice

numit matricea de verificare cod.

Matricele de verificare și generatoare sunt legate prin relație

Din această relație vedem că pentru orice cuvânt de cod există

Această identitate poate fi folosită ca criteriu pentru ca o secvență arbitrară să aparțină unui cod, adică. pentru a detecta erorile.

Știind, se poate găsi. Pentru a înțelege cum se face acest lucru, rețineți că același cod poate fi specificat prin diferite matrice generatoare, alegând baza spațiului în moduri diferite. Mai mult, înlocuind în orice șir cu orice combinație liniară a acestui șir cu alte șiruri, obținem o nouă matrice generatoare a aceluiași cod.

Permutarea coloanelor matriceale, în general, duce la un cod diferit, dar acest alt cod nu diferă în caracteristicile sale de cel original. Se apelează coduri care diferă doar prin numerotarea pozițiilor echivalent.

Este clar că pentru fiecare cod există unul echivalent pentru care primele poziții formează un set de informații, adică. primele coloane formează o matrice de dimensiuni nedegenerate. Înlocuind rândurile cu combinații liniare de rânduri (metoda Gauss), matricea rezultată poate fi redusă la forma

unde este matricea de ordine unitară și este o matrice de dimensiune.

O matrice de forma (6.6) se numește matrice generatoare redusă la mod sistematicși se numește codul corespunzător sistematic... Codarea pentru codul sistematic este puțin mai ușoară decât pentru codul general:

, (6.7)

acestea. în cuvântul de cod, primele poziții sunt doar o copie a secvenței de informații, iar pozițiile rămase (de verificare) sunt obținute prin înmulțirea vectorului de informații cu o matrice de dimensiune, care este uneori semnificativ mai mică decât. În consecință, informațiile despre codul sistematic ocupă mult mai puțină memorie decât informațiile despre codul liniar general.

Pentru un cod sistematic cu o matrice generatoare în forma (6.6), matricea de verificare a parității poate fi calculată prin formula

Exercițiul 6.6... Verificați (6.7). Sugestie: pentru aceasta trebuie să înlocuiți (6.8) și (6.6) în (6.4).

Cum găsesc o matrice de verificare pentru un cod nesistematic?

Foarte simplu. Este necesară aducerea matricei într-o formă sistematică și utilizarea (6.7). Dacă primele coloane ale matricei generatoare formează o submatrice nedegenerată (primele poziții formează un set de informații), atunci operațiuni precum permutarea rândurilor și înlocuirea rândurilor cu combinații liniare de rânduri sunt suficiente pentru a o aduce la o formă sistematică. Dacă nu, mai întâi va trebui să găsiți setul de informații și să renumerotați pozițiile astfel încât primele poziții să devină informaționale.

Î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 (transfer), o structura specială 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 (și va putea detecta mai multe erori decât a putut să le repare).

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. Cu toate acestea, un 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 număr 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 de comunicații (de exemplu, telefon), restricțiile tehnice nu dau o creștere nelimitată a puterii semnalului.

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 limba 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

Să reducem matricea H la formă triunghiulară:

Sistem de ecuații:

Simboluri informative:

Simboluri de protecție:

Matricea generativă

Simboluri de informare și simbolurile lor de protecție corespunzătoare:

N	x 1 x 2 x 3 x 4	x 5 x 6 x 7	Greutatea

Există o cutie neagră. L este un set de transformări în el. L a actionat asupra lui X.

X 1 și x 2 nu interacționează unul cu celălalt, deci este un sistem liniar.

Linearitatea codurilor- suma a două cuvinte de cod permise este egală cu cuvântul permis.

Biletul 5.
a) Relația dintre valoarea informației și entropie
b) Principii de construire a codurilor liniare. Decodificarea sindromului

Presupunerea că setul de secvențe de ieșire a canalului este un spațiu vectorial -dimensional peste un câmp GF (q),și mulțimea Y (n, R) secvențele de intrare (codul) este un subspațiu al dimensiunii nR. face decodarea mult mai ușoară. În acest caz Y (n, R) este un subgrup al grupului de aditivi , prin urmare , pot fi descompuse în clase de subgrup . Lasa - toate elementele (cuvinte de cod), apoi toate elementele setului vor fi reprezentate folosind aranjamentul standard

(1)

(aici 0 denotă elementul unitar al grupului) .

Fiecare rând din (1) este generatorul claselor corespunzătoare. Dacă elementele cu greutate minimă din setul lor sunt luate ca generatoare 0, е 1, е 2, ..., е s, atunci orice succesiune din coloana a I-a diferă de laîn mai puține cifre decât. din orice alt cuvânt i¹K. Dacă într-un set care conține x există mai multe elemente de greutate minimă, atunci există același număr de cuvinte de cod care diferă de x în același număr minim de biți.

Pentru demonstrație, să presupunem că x = y i + e, unde e este elementul de greutate minimă în setul său. Evident, d (y i. x) = w (e) și d (y k, x) = w (y k -y i -e). Dacă e- este singurul element de greutate minimă, apoi d (y i, x) K¹ i. Dacă există mai multe astfel de elemente (de exemplu, w ( y j + e) = w (e)), atunci d (y i, x) = d (y k, x) atunci cu condiția ca y k = y j – Da i. Prin urmare, pentru fiecare element y j + e greutate minimă în setul care conține e, există un cuvânt y k = y j – Da eu, care este din la pe distanta d (y k, i) = w (e).

Astfel, pentru toate secvențele x incluse în prima coloană a aranjamentului standard, probabilitatea condiționată R( X \ y i) maxim. Dacă x este într-un grup cu mai multe elemente de pondere minimă, atunci probabilitatea condiționată R( X \ y i) = P ( X \ y k)și rămâne maximă pentru toată lumea la k, situat la aceeași distanță de x

Regula de decodare poate fi formulat astfel: găsiți secvența de ieșire a canalului xÎ în (1) și presupuneți că a fost transmisă șirul y i ÎY (n.R), care se află în aceeași coloană cu x.

Evident, această regulă coincide cu decodarea cu probabilitate maximă și, prin urmare, este optimă.

Regula de decodare a codului de linie poate fi formulat astfel: după aceea. ca secvență de ieșire x; găsit în (1), se determină cel mai probabil vector de eroare e, căutând generatoarea clasei care conține x; găsiți șirul transmis din relația y = x-e.

Puteți construi o procedură de decodare similară dacă profitați de corespondența unu-la-unu dintre clasele și sindroamele elementelor constitutive. Regula de decodare este următoarea: calculaţi sindromul secvenţei acceptate S = X H T = eH T,

unde e este generatorul setului care conține X ... Găsiți e după sindromul S găsit; determinați y din relația y = X -e.

O astfel de decodare coincide, de asemenea, cu decodarea cu probabilitate maximă și, prin urmare, rămâne optimă. Primele coduri cu o procedură similară de decodare au fost codurile Hamming, care corectează erori individuale.

Totuși, găsirea unei secvențe de erori, atunci când numărul de erori admisibile este mai mare de unul, devine rapid complicată, iar cu coduri suficient de lungi și un număr mare de erori de corectat, devine aproape imposibil.

Biletul 6.
a) Entropia și proprietățile ei

Problemă de transmisie continuă mesaj în primire. copii ale acestuia la punctul de colectare. Nu există nicio modalitate de a obține o copie exactă a mesajului anterior, pok. aceasta necesită o precizie infinită în reproducerea acestuia. Poet. setați acuratețea reproducerii mesajului anterior.

e-entropie- aceasta este cantitatea minimă de informații, cat. necesar transmite pe canal, joi. restabili mesaj cu o precizie dată pentru o distribuție dată p (x) a sursei.

Transfer model cont. mesaj:

d 2 = e 2 - eroare la restaurarea mesajului y (t). Este necesar să se stabilească o conexiune între m \ d x (t) și x ’(t), astfel încât x’ să poarte cât mai puține informații despre x, dar să asigure precizia specificată.

H e= min I (x, x ')

Fiecărui interval i se atribuie un număr corespunzător. x = (b-a) / 2 n.

decât> n, intervalele> și> precizie.

I (x, x ’) = H (x’) - H (x ’/ x) -infa reciprocă prin definiție.

H (x ’/ x) = 0 deoarece valoarea unei variabile aleatoare X determină valoarea unei variabile aleatoare X '.

(„Pentru un fix X”)

I (x, x ’) = H (x’) - cantitatea de informații reciproce dintre mulțimi Xși X ' egal cu entropia X '.

(pe baza capacităţii informaţionale a registrului).

Fie x distribuit uniform. pe un interval atunci toate x 'sunt echiprobabile.

log [(b-a) / x] = n valoarea entropiei ~ lungimea registrului

Este necesar să se asigure acuratețea d 2 (eroare pătratică medie):

La numărul minim de informații reciproce. Legătura m \ b x și x ’ este determinată de numărul și lungimea intervalelor x. Trebuie să le alegem astfel încât joi. x 'a fost distribuit uniform.

Fie x și x continui.

(1) x = x ’- n, unde n este o eroare. pisică. se obţine ca urmare a aproximării x x'th.

n = 0, n 2 = d 2 e = e 2 - eroare specificată

El= H (x) -max (H (n)), H (n) va fi max pentru o distribuție gaussiană. n

H (n) = / 2

Sursa este cel mai adesea numită după. Răspândirea gaussiană cu d 2, atunci: H (n) = / 2 = log (d 2 x / d 2 n) / 2 = log (d 2 x / e 2) / 2 [bit / număr]

Dacă pentru 1s. înainte de probe 2F, apoi He t = 2F El= F * log (d 2 x / e 2) [bit / s]

Potrivit tovarășului Shannon pentru gauss. canal: Нe t< F log(1+q 2) [бит/c]

b) Discretizarea mesajelor continue. teorema lui Kotelnikov. Spațiul semnalelor.

Biletul 7.
a) Informații reciproce și proprietățile acesteia

Cantitatea de informații, cat. Yj poartă aproximativ Xi = cantitatea de informații, cat. Xi poartă despre Yj. Și această informație se numește informații reciproce ale m-y Yj și Xi:... Și ea ar putea. > 0,<0,=0, в зависимости от средней информации.

Pentru fiecare pereche ( Xi, Yj) corespunde propriei sale cantități de informații, iar din moment ce Xi și Yj- variabile aleatoare, atunci această cantitate de informații este aleatorie. Prin urmare, putem introduce conceptul de informație medie prin m-y mulțimi:

O stare separată este o pereche de numere.

I (X, Y) - informații reciproce complete (întotdeauna ≥0 când sistemele sunt independente).

Să facem transformări identice:

Apoi, informațiile reciproce pot fi scrise:

, (*)

Din punctul de vedere al descrierii informaționale a sistemului de comunicații, nu are nicio diferență care dintre subsisteme este considerat ca emițător și care ca receptor.

Prin urmare, entropia N(NS) și H(Y) pot fi interpretate ca informații care intră în canalul de comunicare, iar entropiile condiționate H(X Y), H(Y/X) ca informații care sunt împrăștiate în canal.

Conform teoremei eu(NS,Y) ≥0 obținem de la (*):

Când X și Y sunt independenți, i.e. reciproc info-i = 0

b) Discretizarea adaptativă a mesajelor continue

O funcție continuă arbitrară pe bucăți care reprezintă un mesaj sau un semnal poate fi extinsă într-o serie Fourier generalizată în ceea ce privește sistemul complet de funcții ortonormale

dacă energia funcției este finită.

Un sistem infinit de funcții reale se numește ortogonal pe segmentul [a, b] dacă at, iar o funcție separată se numește normalizat dacă.

Un sistem de funcții normalizate în care fiecare două funcții distincte sunt reciproc ortogonale se numește sistem ortonormal. La aproximare, funcțiile sunt limitate, de regulă, de un număr finit de membri ai seriei. Pentru un sistem dat de funcții și pentru un număr fix de termeni ai seriei n, valorile coeficienților pot fi alese astfel încât eroarea pătratică medie de aproximare

atinge un minim. Minimul erorii pătratice medii este atins atunci când coeficienții seriei sunt determinați prin formulă. Seria cu coeficienții determinați în acest fel se numește serie Fourier generalizată.

Un sistem ortogonal se numește complet dacă, prin creșterea numărului de termeni dintr-o serie, eroarea pătratică medie poate fi redusă în mod arbitrar.

Astfel, pentru un set numărabil de coeficienți, este posibil cu un anumit

acuratețea restabilirii funcției corespunzătoare poate fi înlocuită cu transmiterea unei secvențe de coeficienți. Secvența specificată poate fi interpretată ca un vector în spațiu euclidian n-dimensional cu coordonatele pătrat ale lungimii.

Ultima egalitate este o generalizare a teoremei lui Pitagora la cazul spațiului n-dimensional. Este ușor de stabilit prin calcule directe că energia semnalului .

Astfel, discretizarea este înlocuirea unei funcții continue cu o succesiune de coeficienți ... (vector).

Alegerea unui sistem de funcții ortogonale este determinată de scopul și de esența fizică a problemei care se rezolvă, și nu de inferențe pur matematice.

Pentru a transmite un semnal printr-un canal de comunicație, extinderea funcției în seria Kotelnikov este utilizată pe scară largă, ceea ce face posibilă simplificarea semnificativă a determinării coeficienților. Conform teoremei lui Kotelnikov, o funcție arbitrară cu un spectru mărginit poate fi reprezentată identic printr-un număr numărabil al valorilor sale luate la intervale de timp în care F este frecvența de tăiere superioară a spectrului de semnal. În acest caz, funcțiile ,

formarea unui sistem de funcții ortogonale diferă între ele doar printr-o deplasare de-a lungul axei timpului t cu un multiplu și fiecare dintre ele atinge valoarea maximă în acele momente în care valorile tuturor celorlalte funcții sunt egale cu zero. Coeficienții de expansiune sunt determinați prin formulă

care, ca urmare a unor transformări identice, se poate reduce la forma:, adică coeficientul este egal cu valoarea funcției în momentul în care funcția atinge valoarea maximă.

Dacă urmează a fi discretizat un proces aleatoriu normal (gaussian), al cărui spectru energetic are formă dreptunghiulară, atunci coeficienții vor fi variabile aleatoare independente statistic, care coincid cu valorile funcției aleatoare luate cu un pas Dt [9] ].

Astfel, mesajele continue pot fi transmise în formă digitală, adică sub forma unei secvențe de numere, în timp ce fiecare număr exprimă aproximativ valoarea coeficientului corespunzător.

Biletul 8.
a) Surse ergodice. Performanță sursă cu simboluri independente

b) Entropia relativă a variabilelor aleatoare continue

Relativ(diferenţial) entropia unei variabile aleatoare NS numită valoare

În special, dacă intervalul d = 1, atunci

Să aflăm semnificația fizică a entropiei relative H (X) .

Lăsați sursa mesajului să genereze o secvență de valori ale unei variabile aleatorii NS ... După cuantizare, obținem o succesiune de valori ale variabilei aleatoare X ' :

X i 1, X i 2… ..X ik… ..X in.

Cu o creștere nelimitată a lungimii secvenței cu o probabilitate egală cu unu, numai secvențe tipice, al cărui număr

unde este numărul de elementare n -cub dimensional. Sfârșitul unui vector care reprezintă o secvență tipică este punct interior acest cub. Produsul este egal cu volumul unei anumite zone în n -spaţiu dimensional, ale cărui puncte interioare reprezintă capetele vectorilor tipici(secvențe). Când tinde spre zero, numărul de secvențe tipice tinde spre infinit, și volumul fiecărui cub elementar tinde spre zero... În acest caz, volumul V T ocupat de secvențe tipice rămâne constantă, egală.

Entropia în cazul discret ar putea fi determinată prin numărul de secvențe tipice:

În mod similar, entropia relativă poate fi determinată prin volum V T ocupat de secvențe tipice:

Spre deosebire de cazul discret entropia relativă poate fi nu numai pozitivă, ci și negativă și, de asemenea, egală cu zero... Cu cât volumul este mai mare V T ocupat de secvențe tipice, cu atât mai mare este incertitudinea despre care va apărea. Volumul unității ( V T = 1) corespunde entropiei (incertitudinii) egală cu zero ( H (X) = 0). Această valoare este acceptată pentru punctul de referință al entropiei relative.

În special, entropia relativă a unei variabile aleatoare cu uniformă pe un interval unitar ( d = 1 ) distribuția este egală cu zero:

În acest caz, zona n -spațiul dimensional, ocupat de secvențe tipice, coincide aproximativ cu domeniul de definire al tuturor secvențelor și are forma unui cub de unitate de volum ( V T = d n =1 ).

Biletul 9.
a) Performanța sursei Markov. Redundanţă

Î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

Blocați coduri

Dacă originalul k bit codul lasă neschimbat și adaugă n − k verificare, acest cod este numit sistematic, in caz contrar nesistematic.

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 număr mare de coduri, fiecare dintre acestea fiind potrivit pentru propria sa gamă de sarcini.

Spații liniare

Matricea generativă

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

Codurile Reed-Solomon

Avantajele și dezavantajele codurilor liniare

În timp ce codurile liniare tind să se descurce bine cu rare, mari mănunchiuri de erori, eficiența lor cu erori frecvente, dar mici (de exemplu, într-un canal cu AWGN) este mai puțin ridicată. Datorită liniarității, pentru memorarea sau enumerarea tuturor cuvintelor cod este suficientă stocarea în memoria codificatorului sau decodorului a unei părți substanțial mai mici din acestea, și anume doar acele cuvinte care formează baza spațiului liniar corespunzător. Acest lucru simplifică foarte mult implementarea dispozitivelor de codificare și decodare și face ca codurile liniare să fie foarte atractive din punct de vedere al aplicațiilor practice.

Marca de eficiență

Eficiența codurilor este determinată de numărul de erori pe care le poate corecta, de cantitatea de informații redundante, a căror adăugare este necesară, precum și de complexitatea implementării codificării și decodării (atât hardware, cât și sub formă de un program de calculator).

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):

Câștig de energie

Wikimedia Foundation 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

Î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

- (Cod LDPC din limba 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

structura- (cadru): Un cadru logic pentru clasificarea și organizarea informațiilor complexe.

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,

specificarea codului 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 ca o combinație liniară (adăugare modul 2) a rândurilor 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 de pe partea de primire a cuvântului 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. Drept urmare, codurile Hamming verificate prin paritate au următoarele 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 mod hibrid - detectarea și 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.

Cu o eroare dublă, componenta este „(4) = 0, iar sindromul este diferit de zero. Spre deosebire de codul Hamming standard, această situație este 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.