algoritmi de matematică discretă

Descrierea procesului de comunicare digitala

Sursa emite un mesaj care reprezintă cazul general, un anumit semnal electric. Acest semnal este convertit într-o formă digitală, care este convenabil pentru prelucrare ulterioară.

Următorul este compresia de date (sursă de codificare), minimizând redundanța mesajului. de codificare sursa reduce costurile de transport și stocare a informațiilor. Mesajul care urmează să fie transmis pe un canal zgomotos. Pentru ca mesajul să ajungă la consumator în formă nedistorsionate, utilizând informații de codificare noiseless (canal de codificare). Pe informațiile din partea consumatorilor este decodificat. decodor canal corectează erorile din cuvântul primite și decodor sursa convertește cuvântul corectat într-o formă convenabilă pentru consumator.

Vorbind despre codurile care controlează erorile, trebuie să se facă distincția între două strategii de utilizare a acestora.

1. corectare a erorilor din cauza redundanței (Forward Error Correction - FEC).
2. Detectarea erorilor și cererile ulterioare de retransmisie a informațiilor primite în mod eronat (Repeat Request Automatic - ARQ).

La selectarea codificare și metode de decodificare sunt ghidate de mai mulți factori, relația care este reprezentată în figură.

Complexitatea generală a hardware-ului și software-ul sunt costul de implementare codificator și decodor, stocare și costurile de transport și așa mai departe. D. Fluxul de date de intensitate include transmiterea de informații utile, biții de paritate, și, de asemenea, cererile și solicită repetarea acestor blocuri de informații individuale.

de codificare fără zgomot

Prezentare generală

Sistemul actual de transmitere a datelor nu este perfect. Aplicarea tehnologiei informației, ar trebui să ia în considerare posibilitatea de erori în transmiterea și stocarea informațiilor. Aceasta se referă în primul rând la

• stocarea informațiilor pe un suport de înregistrare de înaltă densitate (suporturi magnetice, CD-ROM, DVD);
• transferul de date la o putere limitată a semnalului (prin satelit și comunicații mobile);
• transmiterea de informații într-un canal extrem de zgomotoase (comunicații mobile, de mare viteză legături cu fir);
• canale de comunicare cu cerințe ridicate privind fiabilitatea informațiilor (rețele, linii de transmisie cu compresie a datelor).

In toate cazurile de mai sus, sunt utilizate codurile, erori de control.

Luați în considerare cele mai simple modelul de date utilizând codificarea de corectare a erorilor.

Să presupunem că o sursă de codoare ieșiri secvențial cuvinte de date de lungime fixă. canal de codificare înlocuiește fiecare cod cuvânt de date cuvânt u v. Transmițătorul generează semnale corespunzătoare v și trimite cuvânt de cod-l la canal. Receptorul efectuează transforma un invers, ca rezultat al căreia decodorului primește primit binar cuvântul r. Decodorul compară r cuvântul primit cu toate codul folosit cuvinte de cod. În cazul în care cuvântul r se potrivește cu unul dintre cuvintele de cod care corespunde cuvântului informație, și a emis consumatorului. Dacă r este diferit de toate cuvintele de cod, atunci când detectează o eroare a avut loc în canal. Scopul aplicării canal de codificare este de a realiza o coincidență a informațiilor transmise cuvântului u și informațiile primite de cuvântul u“.

Din această descriere este posibil să se facă 2 O:

• Dacă în procesul de transfer al unui cuvânt cod de canal de zgomot va apărea într-un cuvânt cod diferit, care nu coincide cu transmise, se intampla ceva eroare nedetectabile. Noi o numim decodificarea de eroare reziduală.
• Necesar pentru a construi coduri care au o structura matematica care poate detecta în mod eficient, iar în unele cazuri și de a corecta erorile în transmiterea informațiilor printr-un canal de comunicare.

Coduri liniare Block

O familie importantă a codurilor forma codurilor liniare bloc binare. Aceste coduri sunt remarcabile în care, prezentarea informației și cod cuvinte sub formă de vectori binari, putem descrie procesele de codare și decodare folosind aparatul de algebra liniara. Astfel, componentele vectorilor de intrare si matrici sunt simboluri 0 și 1. Operațiunile cu componente binare sunt produse în conformitate cu regulile de aritmetică modulo 2.

Cel mai cunoscut cod liniar este un Hamming cod bloc. Descrierea suplimentară a codurilor bloc liniare se va face pe un exemplu de cod. În special, acesta va fi considerat (7,4) -Code Hamming.

codificator bloc binar (n. K) -Code afișează o multitudine de 2 k cuvinte posibile bit de informație într-o multitudine de k bidimensional n codewords. În teoria codurilor între aceste seturi este întotdeauna o corespondență unu-la-unu.

vector de informații În schimb k-bit în canalul n-biți transmis vector de cod. În acest caz vorbim de codare excesivă cu rata: R = n / k.

Este mai scăzută viteza, cu atât mai mare redundanței și mai multe oportunități de eroare, el are. Cu toate acestea, trebuie remarcat faptul că o creștere a costurilor de transmitere a informațiilor redundante crește, de asemenea.

Descrierea proceselor de codare și decodare

Structura spațiului vectorial cod

Materia primă pentru construirea de construcții cod servește ca un spațiu binar n-dimensional vector, în care operațiile aritmetice specificate modulo 2. spațiu vectorial k-dimensional încorporat, care conține 2 k codewords. Codul C se formează prin combinațiile de 2 k k liniar independente vectori bază .

Acești vectori formează un rând al generatorului de cod matrice C.

Există cod dublu C d la codul C astfel încât produsul scalar al oricărei perechi de vectori, dintre care unul aparține C, iar celălalt - spațiul C d. Este întotdeauna zero. Aceasta înseamnă că codul vectorilor C d ortogonale cod vectori C. Pe de altă parte, dacă un vector este perpendiculară pe toți vectorii de cod C care aparține codului C d și vice-versa. subspațiul vectorial dual „tensionate“ în n - k vectori de bază liniar independenți . Acești vectori formează un rând al matricei verificare.

Să considerăm un exemplu de generare a matricei de selectare și (7,4), cod Hamming:

Trebuie remarcat proprietate importantă atât în ​​generarea, iar matricea de verificare este prezent matricea de identitate. Această proprietate este folosită în procesele de codare și decodare.

de codificare

v și cuvântul cuvintelor de cod de informații u sunt legate de:

unde G - matricea de generare. structura care a fost descrisă mai sus.

De exemplu, vectorul u informație = (1010), este afișat într-un vector de cod după cum urmează:

Este ușor de observat că ultimele patru biți ale vectorului de cod coincid cu informațiile vectoriale. Această proprietate este numit un cod sistematic.

Codurile, care cuvânt de date pot fi alocate direct din codevector corespunzătoare a numit sistematic. Generarea matrice oricărui cod sistematic este întotdeauna posibil prin rearanjarea coloanele la forma:

unde am k - matricea identitate de dimensiune k × k.

Astfel, în vectorul de cod de cod sistematic poate evidenția întotdeauna informații și de a verifica simboluri.

v 0 ... v n - k -1

v n - k ... v n -1

n - k paritate

simboluri K

Rolul paritate și utilizarea lor va fi explicată în detaliu mai jos.

decodare

Sarcina Decoder este, folosind o structură de cod al cuvântului primit r. recuperarea vectorului informațiilor transmise. Discutat mai sus pentru (7, 4), cod Hamming poate propune următorul algoritm pentru detectarea erorilor. Deoarece codul considerat este sistematic, exprimă fiecare dintre cele trei simboluri de paritate prin vector de informații:

Dacă o eroare în canal, vectorul primit r cel puțin una din ecuațiile vor fi efectuate. Scriem relațiile primite într-un sistem de verificare de ecuații pentru componentele vectorului r.

Astfel, primele trei coloane ale matricei generatorului G, obținem un sistem de verificare a trei ecuații. Dacă cel puțin una dintre componentele din sistemul de ecuații rezultat nu zero, a apărut o eroare în canal.

Noi scrie ecuațiile paritate de verificare în formă generală. Pentru orice cod sistematic cu matrice generatorul G. matricea de verificare este definit după cum urmează:

H (n - k) x n = (I n - k × P T k (n - k)).

Apoi, sistemul de validare de ecuații poate fi scris ca

Vectorul s este numit un sindrom. Astfel, eroarea va fi detectată dacă cel puțin una dintre componentele s nu este egal cu zero.

Ca un exemplu, ia în considerare sindromul Decoding (7, 4), cod Hamming. La transmiterea unui cuvânt informație u = (1010) printr-un canal fără zgomot r = v = (0011010). Putem vedea că, în acest caz, sindromul este 0.

Dacă, de exemplu, în cuvântul de cod a existat o singură eroare în a patra poziție (r = (0010010)), sindromul este a patra linie a matricei verificare transpuse.

După ce a trecut prin toate pozițiile posibile ale unei singure erori, obținem un tabel complet de sindroame de eroare unice - tabel corespunde numărului descărcării eronate se obține prin acest sindrom.

Este posibil să observați că eroarea în poziția de-al i-lea al cuvântului cod corespunde sindromului format de I -lea coloana a H. matricei Din moment ce toate coloanele sunt diferite, putem folosi tabelul sindroamelor pentru a corecta o singură eroare introdusă de canal.

erori de soiuri

Pentru coduri bloc liniare, există 3 tipuri de erori:

1. Recunoașterea și remedieri de erori
   • Cuvântul primit nu se potrivește cu oricare dintre cuvintele de cod
   • Sindromul este prezent în tabelul de sindrom
   • Decodorul detectează și corectează erorile, și apoi transmite la receptor cuvântul corect
2. eroare de recunoscut
   • Cuvântul primit nu se potrivește cu oricare dintre cuvintele de cod
   • Sindromul este prezent în tabelul de sindrom
   • Decodorul detectează o eroare și trimite o solicitare de retransmisie a cuvântului de date.
3. eroare nerecunoscută
   • Cuvântul primit se potrivește cu unul dintre cuvintele de cod (nu cuvântul de cod original corespunzător)
   • Sindromul este 0
   • Decodorul nu detectează o eroare și emite mesajul de informații eronate de utilizator

concluzie

Trebuie remarcat faptul că eficacitatea unui anumit cod depinde de domeniul de aplicare și, în special, de canalul de comunicare. Dacă raportul S / N canal este suficient de mare, probabilitatea unei singure erori este de multe ori mai mare decât probabilitatea unor erori de ordin superior, prin urmare, utilizarea unui astfel de cod Hamming canal corectarea erorilor unice pot fi foarte eficiente. Pe de altă parte, în canalele dominate de mai multe erori (de exemplu, canale de fading), corectarea singură eroare este lipsită de sens. În practica de selectare a unui anumit cod de corectare a erorilor este de asemenea necesar să se ia în considerare rata de decodare și complexitatea implementării tehnice.

literatură

Singura explicație clară!

Într-adevăr o explicație clară, care poate fi găsit cu greu. mulțumire

Este greu de înțeles cartea, a se vedea baieti