Canale discrete de transmisiune cu constrangeri

si coduri de translatie a datelor

1. Obiectivul lucrarii

Aceasta lucrare isi propune sa prezinte caracterizarea canalelor discrete cu constrangeri prin matricea tranzitiilor de stare si metoda de calcul a capacitatii acestui tip de canale. De asemenea, se studiaza o modalitate de constructie a codurilor bloc de translatie a datelor pentru acest tip de canale, ilustrandu-se practic un cod RLL de lungime fixa.

2. Introducere teoretica

2.1. Canalul binar cu constrangeri

Canalul binar cu constrangeri este sistemul de comunicatie care contine in alfabetul de intrare doar doua litere, '0' si '1', si care nu permite ca simbolurile de intrare sa poata fi transmise in ordine arbitrara.

Un caz tipic este dat de canalul binar cu constrangeri RLL (Run Lenth Limited). Un exemplu de constrangere RLL consta in a nu permite existenta sirurilor de simboluri formate numai din '0' sau '1' de lungime mai mare decat o valoare maxima k. Aceasta restrictie asigura ca tranzitiile intre sirurile '0' si '1' sa nu fie prea rare, lucru important pentru pastrarea informatiei de sincronizare a emitatorului cu receptorul. Din aceste tranzitii receptorul are posibilitatea extragerii informatiei de sincronizare pentru semnalul receptionat din canalul discret, reglandu-si baza de timp locala dupa tactul emitatorului.

De asemenea, o alta constrangere RLL limiteaza numarul de simboluri identice succesive la o valoare minima d. Aceasta restrictie asigura existenta unor tranzitii nu prea dese ale semnalului de pe canal, ceea ce inseamna reducerea benzii de frecventa ocupate de semnal si posibilitatea citirii lui cu ajutorul unor interferente intre simboluri avand o rezolutie nu foarte pretentioasa. Canalul discret care respecta ambele restrictii de acest tip se noteaza prin RLL (d,k).

Pentru canalul binar cu constrangeri se poate defini un set al starilor permise:

fiecare stare corespunzand unuia sau mai multor moduri posibile prin care poate trece secventa anterioara de intrare. Din fiecare stare pot fi transmise doar simbolurile din alfabetul de intrare . La urmatorul impuls de ceas al canalului va fi transmis unul din simbolurile permise, in acel moment starea schimbandu-se, starea noua depinzand de starea veche si de simbolul transmis.

Se poate reprezenta grafic succesiunea starilor canalului folosind doua tipuri de diagrame:

diagrame de stare: acestea descriu tranzitiile dintr-o stare in alta cu ajutorul arcelor de cerc pe care se va inscrie simbolul transmis care face trecerea intre stari;

diagrame trellis: acestea descriu tranzitiile dintr-o stare in alta desfasurate pe axa timpului, astfel incat sa se poata observa schimbarea unei stari in oricare alta pe parcursul a mai multor impulsuri de ceas.

Pentru exemplificare s-a ales un canal binar cu constrangerea de tipul urmator: se interzice transmiterea unei secvente ce contine un sir mai mare de trei simboluri identice (k = 3).

Deci setul starilor permise va fi:

S₀ = 111 S₃ = 0

S₁ = 11 S₄ = 00

S₂ = 1 S₅ = 000

Diagrama de stare corespunzatoare este cea din figura 1:

Fig. 1. Diagrama de stare a canalului binar cu constrangerile RLL (0,3).

Fiecare stare exprima cel mai recent sir de simboluri identice, iar tranzitiile se fac respectand constrangerea impusa. Spre exemplificare, se presupune canalul in starea S₄. De aici, prin emiterea unui '0', canalul trece in starea S₅, deci exista trei simboluri de zero emise consecutiv. Din starea S₅ nu se poate emite decat simbolul '1'. Emiterea unui '0' din starea S₅ nu este posibila, acest lucru ducand sistemul intr-o stare nedefinita

Diagrama trellis corespunzatoare are forma din figura 2:

Fig. 2. Diagrama trellis a canalului binar cu constrangerile RLL (0,3).

Se observa din aceasta diagrama ca tranzitiile dintr-o strare in oricare alta stare sunt posibile dupa un anumit numar de impulsuri de ceas. De exemplu, din starea S₀ se ajunge in starea S₂ prin trecerea sistemului prin starea S₃ intermediara, dupa un impuls de ceas.

2.2. Matricea tranzitiilor de stare

Canalul discret cu constrangeri poate fi descris si cu ajutorul matricii tranzitiilor de stare, notata cu B, la care elementele b_ij ale matricii reprezinta numarul de arce care trec din starea S_i in starea S_j de pe diagrama de stare.

In exemplul anterior, matricea tranzitiilor de stare este de tipul:

Se obtine:

Se poate extinde descrierea pentru un numar mai mare de pasi. Astfel, matricea tranzitiilor de stare pentru doi pasi se noteaza B² si are elementele b²_ij date de numarul arcelor distincte care fac trecerea de la starea S_i la starea S_j si care au o lungime de doi pasi (acopera o perioada de timp de doua impulsuri de ceas).

2.3. Capacitatea canalului

Pentru canalul cu constrangeri se defineste capacitatea astfel:

bit/secunda

unde M(T) reprezinta numarul total de secvente permise pe care il poate forma alfabetul canalului in timpul T.

Aceasta expresie este valabila in cazul in care literele alfabetului au durate diferite. In cazul simbolurilor de durate egale, capacitatea canalului binar cu constrangeri se poate exprima si in biti per simbol:

bit/simbol

unde M(n) reprezinta numarul secventelor de aceeasi lungime n.

In acest caz se poate determina valoarea capacitatii cu ajutorul matricii tranzitiilor de stare B, din relatia:

C = log₂l bit/simbol

unde l este cea mai mare valoare proprie pozitiva a matricii B (radacina maxima a polinomului caracteristic corespunzator matricii B). Aceasta metoda de calcul a capacitatii canalului se aplica in cazul simbolurilor de aceeasi durata

Considerand exemplul de canal binar cu constrangeri RLL (0,3), se poate scrie ecuatia:

Va rezulta deci:

Aplicand cateva transformari elementare asupra determinantului, se obtine polinomul caracteristic:

l - l 2l³ - 3l² - 2l - l = 0 .

Radacina cea mai mare a polinomului este l = l_max=1,84. Acestei valori ii corespunde capacitatea canalului:

C = log₂l 0,88 biti/simbol.

2.4. Coduri de translatie

Codul de translatie transforma secventa de date de la intrarea canalului discret intr-o noua secventa care satisface constrangerile impuse de canal. Aceste coduri fac parte din categoria codurilor de adaptare la canal.

Considerand o secventa binara de date, finita sau infinita, aceasta poate fi descompusa intr-un mod unic intr-o inlantuire de cuvinte, fiecare cuvant terminandu-se cu un singur '1' si incepand cu un sir de zerouri sau cu lipsa zerourilor.

De exemplu, fie secventa de date: 01010001011101

Aceasta se poate desface in cuvinte: 01,01,0001,01,1,1,01,

Un bloc (n,r) pentru translatia de date consta in 2^r secvente de simboluri de canal, fiecare secventa avand lungimea de bloc egala cu n, unde

r = numarul bitilor de sursa (lungimea cuvantului de informatie),

n = numarul bitilor de canal (lungimea cuvantului de cod).

Codul are rata R = r/n biti per simbol de canal.

Secventele numite 'cuvinte de cod' trebuie sa satisfaca constrangerile canalului la insiruirea perechilor de simboluri. Deoarece cuvintele de cod vor fi concatenate, perechile alaturate trebuie sa satisfaca si ele aceste constrangeri, deci va trebui sa se elimine din lista blocurilor cateva intrari, astfel ca, dupa concatenare, constrangerile sa ramana respectate.

2.4.1. Constructia unui cod bloc de translatie

Metoda 1

Pentru exemplificare se considera un cod bloc (3,2) la care constrangerea impusa este aceea ca nu sunt admise mai mult de doua zerouri succesive.

Cuvintele de cod cu lungime de 3 biti care respecta aceasta constrangere sunt:

010

011

101

110

111

Acestea pot fi concatenate in orice ordine fara a distruge restrictia impusa. Acum, pentru a forma codul bloc (3,2) se aleg 2² = 4 cuvinte de cod din acest set si se fixeaza un tabel de corespondenta:

Cuvinte de informatie  Cuvinte de cod

010

011

110

111

In general, codorul consta dintr-un tabel de 2^r cuvinte de n biti, iar decodorul dintr-un tabel de 2ⁿ cuvinte de r biti din care doar 2^r cuvinte sunt folosite.

Metoda 2

O metoda matematica de constructie a codului bloc consta in formarea cuvintelor de cod din doua parti:

- un sufix,

- un prefix.

In cazul in care n este par, sufixul si prefixul vor avea lungimi egale, si anume  n/2.

Daca lungimea blocului este impara (n impar), atunci sufixul si prefixul vor avea lungimile dupa cum urmeaza:

- pentru prefix se aloca lungimea (n-1)/2,

- pentru sufix se aloca lungimea (n+1)/2.

Metoda se aplica pentru constructia unui cod bloc (5,3) pentru un canal cu constrangeri care nu permit lungimi mai mari de trei simboluri identice succesive.

Metoda va decurge astfel: pentru inceput se vor alege acele prefixe de lungime doi biti care conduc canalul in stari independente de starea initiala in care s-a gasit anterior canalul.

Prefixe: 00, 01, 10, 11.

Stari canal: S₀ = 000; S₁ = 00; S₃ = 0; S₃ = 1; S₄ = 11; S₅ = 111.

Exemplu.

Se considera canalul in starea S₀ si la intrarea in canal va fi secventa 00. Canalul va fi blocat inca de la primirea primului bit, el trebuind sa treaca intr-o stare nepermisa cu patru zerouri succesive.

Canalul se afla in starea initiala. Primeste la intrare aceeasi secventa prefix 00 luata si anterior in discutie; dupa primul simbol intrat in canal, acesta va trece in starea S₂ si dupa cel  de-al doilea simbol in starea S₁.

Rationand in acelasi mod se poate construi un tabel in care se va reprezenta starea finala pe care o va atinge canalul pornind din fiecare stare initiala, pentru fiecare secventa de doi biti prezenta la intrarea in canal (vezi Tabelul 1).

Zona centrala a tabloului arata ca doar prefixele 01 si 10 conduc canalul catre o stare care este independenta de starea initiala.

Pentru fiecare dintre aceste prefixe (01 si 10) se tabeleaza sufixele permise care pastreaza restrictia canalului in cazul concatenarii lor cu prefixele corespunzatoare.

Tab. 1. Secventele permise la trecerea canalului din starea initiala in starea finala.

Prefixe  01 10

Sufixe 1. 001 001

Sufixe 2. 010 010

Sufixe 3. 011 011

Sufixe 4. 100 100

Sufixe 5. 101 101

Sufixe 6. 110 110

Pentru a obtine codul (5,3) se aleg oricare opt din aceste cuvinte de cod si se fixeaza orice corespondenta prin intermediul unui nou tabel intre cuvintele de cod de 5 biti si cele de informatie de 3 biti.

Exemplu:

INFO  COD

01001

01010

01011

01100

10001

10010

10011

10100

2.4.1. Constructia unui cod bloc de translatie. Codul Franaszek

Tot in aceasta lucrare este descris si codul RLL (2,7) de lungime variabila (cod prefix de translatie) si de rata ½ .

Lungimile datelor variaza corespunzator pentru a pastra rata bit per simbol constanta.

Un exemplu de cod prefix pentru translatia de date este codul Franaszek din tabel, proiectat pentru canalul binar cu constrangeri care admite succesiunea a cel putin doua zerouri si a maximum sapte zerouri. Deci, un cod RLL (2,7).

Cuvinte de sursa Cuvinte de cod

0100

1000

000100

001000

100100

00001000

00100100

Canalul cu constrangerea RLL (2,7) are capacitatea C = 0,517 biti/simbol, iar codul Franasyek corespunzator are rata R = 0,5 biti per simbol. Intotdeauna R < C.

Capacitatea canalului se calculeaza astfel:

a) Se construieste matricea tranzitiilor de stare, corespunzatoare diagramei de stare asociate. Se definesc starile:

S₀ = 1 S₄ = 0000

S₁ = 0 S₅ = 00000

S₂ = 00 S₆ = 000000

S₃ = 000 S₇ = 0000000.

Diagrama de stare va fi:

Fig. 2. Diagrama de stare a canalului cu constrangerea RLL (2,7).

Matricea tranzitiilor de stare va fi:

.

Se determina polinomul caracteristic al matricii tranzitiilor de stare conform relatiei:

det[B - l I] = (-1)ⁿP(l

unde: n = ordinul matricei (aici 8),

P(l lⁿ - C_n-1lⁿ - C_n-2lⁿ - - C₁l - C_0.

Multimea: IC_n-1, C_n-2, , C₁, C₀} reprezinta niste coeficienti care dupa cum se observa sunt chiar elementele coloanei 0 a matricei tranzitiilor de stare.

Aceasta relatie este valabila doar pentru matrice de forma normala Frohenius, caz intalnit la toate matricele de stare B care intra in discutie in cazul canalelor discrete cu constrangeri (d,k). Se obtine:

P l) = (-1)⁸(1xl - 0xl - 0xl - 1xl - 1xl - 1xl - 1xl - 1xl - 1x1).

Deci:

det[B - lI l l l l l l

Cea mai mare radacina a ecuatiei este: l_max = 1,431. Capacitatea canalului va fi:

C = log₂l_max = 0,517 biti/simbol.

Se observa ca rata acestui cod este foarte apropiata de capacitatea canalului, ceea ce arata ca este un cod complex.

Cuvintele de cod Franaszek satisfac conditia de prefix, deci pot fi decodate unic.

3. Descrierea evolutiei programului

Dupa lansarea in executie a programului 'capa.exe' urmeaza a fi selectat tipul codului dorit. Exista doua posibilitati:

cod de lungime fixa,

cod de lungime variabila.

Codul bloc RLL (de lungime fixa)

Vor fi introduse valorile constrangerilor canalului (parametrii RLL: d = numarul minim de simboluri identice succesive admise de canal, k = numarul maxim de simboluri identice succesive admise de canal).

Programul va afisa starile permise de canal si matricea corespunzatoare a tranzitiilor de stare B.

Prin apasarea oricarei taste se trece la afisarea coeficientilor polinomului caracteristic asociat matricii B, in ordinea descrescatoare a gradului, precum si a polinomului caracteristic .

Din nou, apasand oricare tasta, se trece la determinarea valorilor proprii ale matricii B, prin cautarea radacinilor polinomului caracteristic. Metoda utilizata este de tip iterativ, utilizand o contractie, conform teoremei de punct fix.

Vor fi afisate valoarea radacinii gasite si capacitatea canalului binar cu constrangerile date, calculata pe baza radacinii determinate anterior.

Va fi afisat un tabel in care vor fi reprezentate starea finala pe care o atinge canalul pornind din fiecare stare initiala, pentru fiecare secventa de biti prezenta la intrare. Din tabel se identifica zona care conduce canalul catre o stare independenta de starea initiala

In continuare se vor afisa prefixele identificate din tabel, precum si sufixele permise care pastreaza restrictia canalului in cazul concatenarii lor cu prefixele corespunzatoare.

In final se afiseaza codul (n,r) sub forma unui tabel cuvinte sursa - cuvinte canal si se compara capacitatea canalului cu rata codului. 

Codul prefix RLL (de lungime variabila) - codul Franaszek

Aceasta parte de program afiseaza pe rand prin apasarea oricarei taste:

tabelul de cod al cuvintelor sursa si canal

starile canalului

diagrama de stare

matricea tranzitiilor de stare

polinomul caracteristic

capacitatea canalului

4. Desfasurarea lucrarii

4.1. Se studiaza introducerea teoretica

4.2. Se parcurge optiunea 1 (cod RLL de lungime fixa).

4.3. Se introduc constrangerile d si k si se noteaza matricea B obtinuta si polinomul caracteristic. Exemplu:

d si k = 10, in cazul canalului reprezentat de mediul de inregistrare-redare de la Compact Disc;

d si k = 7 sau d = 1 si k = 8, in cazul canalelor reprezentate de mediul de inregistrare-redare pe banda magnetica

4.4. Se noteaza valoarea radacinii maxime a ecuatiei si a capacitatii canalului.

4.5. Se vizualizeaza si se retine codul obtinut, notandu-se rata acestuia.

4.6. Se reia rularea programului pentru alte seturi de date.

4.7. Se parcurge optiunea 2 a programului de simulare (cod Franaszek).

4.8. Se noteaza valorile parametrilor canalului RLL (2,7) si ai codului Franaszek.

5. Intrebari

5.1. Care este explicatia existentei limitarii inferioare si superioare a numarului de simboluri identice succesive admise pe un canal discret?

5.2. Construiti diagramele de stare si trellis ale canalelor pentru seturile de date utilizate in acest program.

5.3. Interpretati valorile din matricile tranzitiilor de stare obtinute prin rularea programului.

5.4. De ce nu se folosesc in practica formulele de calcul pentru capacitatea canalelor discrete cu constrangeri rezultate din definitie?

5.5. Descrieti metoda de calcul a capacitatii canalelor discrete cu constrangeri in cazul in care simbolurile care parcurg canalul nu au aceeasi durata

5.6. Care este valoarea maxima pe care o poate atinge capacitatea canalelor binare cu constrangeri calculata in program?

Se pot construi coduri bloc de translatie care sa permita utilizarea intregii capacitati a canalului?

5.8. De ce la constructia codului RLL de lungime fixa prin metoda 2 se cauta acele combinatii ale simbolurilor de la intrare care duc canalul intr-o stare independenta de starea initiala?

5.9. Metoda 1 de la constructia codului RLL de lungime fixa este eficienta pentru valori mari ale parametrilor codului?

5.10. Dati exemple de aplicatii ale codurilor RLL de lungime fixa si ale codului Franaszek.