Coduri binar-zecimale

CODURI BINAR-ZECIMALE

Aceste coduri se utilizeaza pentru codificarea cifrelor zecimale. Pentru codificarea fiecareia din cele 10 cifre, sunt necesari 4 biti; din cele 16 valori posibile, 6 vor fi neutilizate. Prin stabilirea unor corespondente intre multimea cifrelor zecimale si multimea celor 16 cuvinte de 4 biti, se obtin numeroase posibilitati de codificare . Din numeroasele coduri posibile se utilizeaza practic doar o mica parte.

Codurile utilizate se impart in coduri ponderate si neponderate.

In cazul codurilor ponderate, o cifra zecimala este exprimata printr-o combinatie de 4 cifre binare, in care fiecarei cifre i se asociaza o anumita pondere. Ponderile pot fi pozitive sau negative. Valoarea cifrei zecimale se obtine prin suma bitilor din cod, fiecare bit fiind multiplicat cu valoarea ponderii asociate.

Considerand un cod format din bitii , , , , ponderile asociate acestora fiind , , respectiv , valoarea cifrei zecimale codificate este:

(1.1.)

Ponderile fiecarui bit reprezinta valoarea corespunzatoare din denumirea codului. Pentru ponderile de sus, codul are denumirea .

In tabelul 1 se prezinta exemple de coduri ponderate de 4 biti mai des utilizate.

Tabelul 1 - Coduri binar-zecimale ponderate de 4 biti

Exemple

In cazul codului 8421, deoarece fiecare bit are ponderea numararii in binar , iar cuvintele de cod reprezinta numerele succesive in sistemul binar natural, codul se mai numeste cod binar-zecimal natural (NBCD - Natural Binary Coded Decimal). In mod obisnuit, acest cod se numeste, impropriu, cod BCD.

In cazul codului 2421, numit si cod Aiken (dupa numele prof. Howard Aiken), primele 5 cifre zecimale au aceeasi exprimare ca si in codul 8421. Cifra zecimala 5 poate fi exprimata fie prin 0101, fie prin 1011. Deci, reprezentarea unor cifre zecimale nu este unica, aceasta proprietate fiind valabila si pentru alte coduri. Pentru codificare s-a ales reprezentarea 1011, deoarece codul pentru cifra 5 se poate obtine atunci prin complementarea codului pentru cifra 4. Aceeasi regula se poate aplica pentru obtinerea codului cifrei 6 din codul cifrei 3, a codului cifrei 7 din codul cifrei 2 etc.

Codurile care au aceasta proprietate se numesc coduri autocomplementare. Un cod este autocomplementar daca cuvantul de cod al complementului fata de 9 al cifrei N (deci ) se poate obtine din codul cifrei N, prin complementarea fiecaruia din cei 4 biti. De exemplu, codul 8421 nu este autocomplementar, iar codurile 2421, , sunt autocomplementare.

Conditia necesara pentru ca un cod ponderat sa fie autocomplementar este ca suma ponderilor sa fie egala cu 9. Autocomplementaritatea constituie un avantaj in constructia unui dispozitiv aritmetic care lucreaza cu numere zecimale reprezentate in codul respectiv.

Observatie. In forma interna, numerele sunt reprezentate si prelucrate fie sub forma binara, fie codificate printr-un cod binar-zecimal. Trebuie sesizata diferenta dintre conversia unui numar zecimal in echivalentul sau binar si codificarea binar-zecimala a numarului zecimal.

De exemplu:

(4 biti)

(8 biti)

Codurile neponderate pot avea un numar mai mare de 4 biti. Codurile cele mai uzuale sunt prezentate in tabelul 2.

Codul Exces 3 este autocomplementar, si deriva din codul 8421 (BCD) prin adaugarea la fiecare cifra a valorii 3. Utilizand acest cod, se poate face distinctia intre lipsa unei informatii inscrise intr-un registru sau locatie de memorie si inscrierea valorii zero (0000 reprezinta lipsa unei informatii iar zero este codificat prin 0011).

Tabelul 2 - Coduri binar-zecimale neponderate

Codul 2 din 5 se utilizeaza pentru reprezentarea numerelor zecimale printr-un grup de 5 biti. Denumirea deriva din faptul ca fiecare cifra zecimala codificata in binar contine doi biti de 1 din cei 5 biti.

Codul Gray are proprietatea de adiacenta, adica trecerea de la o cifra zecimala la urmatoarea sau precedenta necesita modificarea unui singur bit din cuvantul de cod. Este util pentru marimile care cresc sau descresc succesiv.

Coduri detectoare de erori

Transmiterea informatiilor prin medii influentate de zgomote poate fi insotita de introducerea unor erori. Verificarea transmiterii corecte a informatiilor se poate realiza cu ajutorul unor coduri speciale numite coduri detectoare de erori.

Una din metodele de detectare a unei erori o constituie detectarea combinatiilor interzise. In cazul codurilor binar-zecimale, deoarece se utilizeaza 10 din cele 16 combinatii posibile de 4 biti, celelalte combinatii nu trebuie sa apara. Aceste combinatii interzise se pot utiliza pentru detectarea erorii. Daca, de exemplu, in codul BCD 1000 apare o singura eroare, codul poate fi transformat in 0000, 1100, 1010 sau 1001. Dintre aceste combinatii, a doua si a treia constituie combinatii interzise, astfel incat in aceste cazuri eroarea poate fi detectata. Celelalte combinatii nu sunt interzise, deci in cazurile respective eroarea nu poate fi detectata.

O modalitate de crestere a probabilitatii de detectare a erorilor consta in folosirea mai multor combinatii interzise, care pot fi disponibile daca codurile au mai mult de 4 biti. De exemplu, in codul 2 din 5 apare o eroare ori de cate ori o cifra codificata are mai mult sau mai putin de doi biti de 1. Astfel, se pot detecta erori multiple.

O alta metoda pentru detectarea erorilor consta in folosirea unor biti suplimentari de verificare. De exemplu, un cod de n biti poate fi format din m biti de date si r biti redundanti de verificare . Fiind date doua cuvinte de cod, de exemplu 1000 1001 si 1011 0001, se poate determina numarul bitilor care difera. In acest caz, exista 3 biti care difera. Pentru determinarea numarului de biti care difera, se efectueaza suma modulo 2 intre cele doua cuvinte de cod, si se calculeaza numarul bitilor de 1 ai rezultatului. Numarul pozitiilor in care doua cuvinte de cod difera reprezinta distanta Hamming. Daca intre doua cuvinte de cod se afla o distanta Hamming d, sunt necesare d erori de cate un singur bit pentru trecerea de la un cod la al doilea cod.

Proprietatile de detectare a erorilor ale unui cod depinde de distanta sa Hamming. Pentru detectarea a d erori de cate un singur bit, este necesar un cod cu distanta , deoarece cu un asemenea cod nu exista posibilitatea ca d erori de un singur bit sa modifice un cuvant de cod valid intr-un alt cuvant de cod valid.

Un exemplu simplu de cod detector de erori este un cod care contine un bit suplimentar numit bit de paritate. Acest bit se poate alege astfel incat numarul total al bitilor avand valoarea 1 in exprimarea numarului sa fie par, respectiv impar. Daca se utilizeaza paritatea para, notand cu bitii cifrei zecimale si cu p bitul de paritate, valoarea bitului de paritate determina ca suma modulo 2 a valorii tuturor bitilor sa fie 0:

de unde rezulta:

Daca se alege paritate impara, trebuie ca:

sau:

Un asemenea cod are distanta 2, deoarece o eroare de un singur bit produce un cuvant de cod cu paritatea eronata. La transmisia datelor se adauga bitul de paritate para sau impara, iar la receptie se determina daca paritatea este aceeasi cu cea de la transmisie.

Codurile 8421 cu paritate para ale cifrelor zecimale sunt indicate in tabelul 3.

Tabelul 3 - Codul 8421 cu paritate para

Un asemenea cod are distanta 2, deoarece o eroare de un singur bit produce un cuvant de cod cu paritatea eronata. La transmisia datelor se adauga bitul de paritate para sau impara, iar la receptie se determina daca paritatea este aceeasi cu cea de la transmisie.

Coduri corectoare de erori

Verificarea paritatii nu poate detecta aparitia erorilor duble, deoarece aceste erori nu modifica suma modulo 2 a bitilor. Exista coduri mai complexe, numite coduri corectoare de erori, care permit si corectarea unui bit eronat sau a mai multor biti eronati. Aceste coduri sunt utile atunci cand retransmisia informatiei nu este posibila, sau necesita un timp care nu ar fi acceptabil.

Presupunem un cod cu m biti de date si r biti de verificare, cod care permite corectarea tuturor erorilor de un singur bit. Fiecaruia din cele cuvinte de cod valide ii corespund n cuvinte de cod ilegale cu distanta 1. Acestea se formeaza prin inversarea sistematica a fiecaruia din cei n biti. Fiecare din cele cuvinte valide necesita combinatii de biti dedicate pentru cuvantul respectiv. Deoarece numarul total al combinatiilor de biti este , trebuie ca . Utilizand relatia: , aceasta cerinta devine: . Fiind dat m, aceasta impune o limitare inferioara asupra numarului bitilor de verificare necesari pentru corectarea erorilor de un singur bit. De exemplu, pentru un cuvant de biti, numarul minim al bitilor de verificare este , iar pentru un cuvant de biti, numarul minim al bitilor de verificare este .

Aceste limite teoretice pot fi atinse utilizand o metoda datorata lui Richard Hamming. Metoda poate fi utilizata pentru construirea codurilor corectoare de erori pentru cuvinte de cod de orice dimensiune. Intr-un cod Hamming, se adauga r biti de paritate la un cuvant de m biti, rezultand un nou cuvant cu lungimea de biti. Bitii sunt numerotati incepand cu 1 (si nu cu 0), bitul 1 fiind bitul c.m.s. Toti bitii ai caror numar este o putere a lui 2 sunt biti de paritate, restul bitilor fiind utilizati pentru date. De exemplu, in cazul unui cuvant de 4 biti, bitii 1, 2 si 4 sunt biti de paritate. In total, cuvantul de cod va contine 7 biti (4 de date si 3 de paritate). In exemplul prezentat se va utiliza in mod arbitrar paritatea para.

Fiecare bit de paritate verifica anumite pozitii de biti. Aceste pozitii sunt ilustrate in figura de mai jos, unde prin patrate s-a indicat pozitia bitilor de paritate, iar prin cercuri s-a indicat pozitia bitilor de informatie.

Figura 1 - Constructia codului Hamming pentru valoarea binara 0101 prin adaugarea a trei biti de paritate

Pozitiile de biti verificate de bitii de paritate sunt urmatoarele:

Bitul 1 de paritate verifica bitii 1, 3, 5, 7.

Bitul 2 de paritate verifica bitii 2, 3, 6, 7.

Bitul 4 de paritate verifica bitii 4, 5, 6, 7.

In general, bitul b este verificat de acei biti astfel incat . De exemplu, bitul 5 este verificat de bitii 1 si 4 deoarece . Bitul 6 este verificat de bitii 2 si 4 deoarece .

Se considera exprimarea in cod 8421 a cifrei zecimale 5 . Bitul 1 de paritate va trebui sa determine un numar par de cifre de 1 pentru pozitiile 1, 3, 5 si 7, deci va avea valoarea 0. Similar se determina valoarea bitului 2 de paritate, care va avea valoarea 1, si a bitului 4 de paritate, care va avea valoarea 0.

Daca transmiterea cifrei zecimale se realizeaza corect, toti bitii de paritate verifica in mod corect paritatea. Daca apare o eroare de transmisie, fie la un bit de paritate, fie la un bit de informatie, acest cod poate corecta o singura eroare. De exemplu, presupunand ca a aparut o eroare la transmiterea bitului de informatie din pozitia 6. Codul receptionat va fi 0100111 in loc de 0100101. Se verifica bitii de paritate, cu urmatoarele rezultate:

Bitul 1 de paritate este corect (bitii 1, 3, 5, 7 contin doi biti de 1)

Bitul 2 de paritate este incorect (bitii 2, 3, 6, 7 contin trei biti de 1)

Bitul 4 de paritate este incorect (bitii 4, 5, 6, 7 contin trei biti de 1)

Bitul incorect trebuie sa fie unul din bitii testati de bitul 2 de paritate (2, 3, 6 sau 7). Deoarece bitul 4 de paritate este incorect, unul din bitii 4, 5, 6 sau 7 este incorect. Bitul eronat este unul din cei care se afla in ambele liste, deci poate fi bitul 6 sau 7. Bitul 1 de paritate fiind corect, rezulta ca si bitul 7 este corect. Bitul eronat este deci bitul 6, si valoarea acestui bit trebuie inversata. In acest fel, eroarea poate fi corectata.

O metoda simpla pentru determinarea bitului eronat este urmatoarea: se calculeaza bitii de paritate, si daca toti bitii sunt corecti, inseamna ca nu exista eroare (sau exista mai mult de o eroare). Se atribuie apoi bitilor de paritate ponderile 1, 2, respectiv 4, si se aduna ponderile bitilor de paritate eronati. Suma rezultata reprezinta pozitia bitului eronat. De exemplu, daca bitii de paritate 2 si 4 sunt eronati, bitul eronat este bitul 6.

Coduri alfanumerice

Datele alfanumerice contin cifre, litere si semne speciale, numite, in general, caractere. Codurile care pot reprezenta asemenea caractere se numesc coduri alfanumerice.

Codul ASCII

Un cod alfanumeric foarte des utilizat este codul ASCII (American Standard Code for Information Interchange), care codifica literele mari si mici ale alfabetului englez, cifrele zecimale, semnele de punctuatie si alte caractere speciale. Codul ASCII utilizeaza 7 biti pentru a codifica 128 de caractere. Din cele 128 de caractere, 94 sunt caractere care pot fi tiparite, iar 34 sunt caractere utilizate pentru diferite functii de control.

In tabelul 4 se prezinta codurile ASCII. Cei 7 biti ai codului sunt notati cu pana la , fiind bitul c.m.s. De notat ca cei trei biti mai semnificativi ai codului determina coloana din tabela, iar cei patru biti mai putin semnificativi determina linia din tabela. De exemplu, litera A este reprezentata ASCII prin codul binar 100 0001 (coloana 100, linia 0001).

Tabelul 4 - Codurile ASCII

Cele 34 de caractere de control sunt desemnate in tabelul caracterelor ASCII prin nume abreviate. Caracterele de control se utilizeaza pentru transmisia datelor si pentru aranjarea textului intr-un anumit format. Exista trei tipuri de caractere de control: de formatare, de separare a informatiei si de control al comunicatiei. Dintre caracterele de formatare a textului mentionam cele pentru deplasarea inapoi BS (Backspace), retur de car CR (Carriage Return) si tabulare orizontala HT (Horizontal Tabulation). Separatorii de informatii se utilizeaza pentru separarea datelor in sectiuni, de exemplu in paragrafe si pagini. Acestea cuprind caractere cum sunt separatorul de inregistrare RS (Record Separator) si separatorul de fisier FS (File Separator). Caracterele de control al comunicatiei se utilizeaza la transmisia textului. Exemple de asemenea caractere sunt STX (Start of Text) si EXT (End of Text), care se pot utiliza pentru incadrarea unui mesaj transmis pe liniile de comunicatie.