Operatii cu numere reprezentate in BCD

Operatii cu numere reprezentate in BCD

In codul BCD (denumirea improprie a codului NBCD) fiecare cifra zecimala a unui numar este inlocuita cu tetrada corespunzatoare din codul 8421 (codul NBCD). Reamintim ca acest tip de reprezentare se mai numeste si zecimal codificat binar.

Prezentam in continuare modalitatile in care se pot efectua calcule aritmetice cu numere reprezentate in BCD de catre o unitate aritmetica care lucreaza in binar.

Adunarea in zecimal codificat binar presupune:

exprimarea fiecarei cifre zecimale printr-o tetrada binara;

efectuarea adunarii pozitie cu pozitie, de la dreapta la stanga; pot sa apara urmatoarele situatii:

daca rezultatul apartine sistemului zecimal atunci suma din pozitia respectiva nu necesita corectii;

daca rezultatul sumei pozitiei respective este un numar situat in multimea atunci:

transportul generat se aduna la pozitia urmatoare;

se aduna 6 (0110) la suma din pozitia respectiva, deoarece transportul generat la pozitia urmatoare a insemnat practic transferul numarului 16 (10000) si nu 10 cat era necesar;

daca rezultatul pozitiei respective este situat in intervalul , atunci:

se aduna 6 (0110) la suma din pozitia respectiva, pentru a forta transportul la pozitia urmatoare;

se aduna transportul generat la suma din pozitia urmatoare.

Exemplu: Sa se efectueze in BCD suma 5683 + 2794.

Mai sus transportul aparut din tetrada anterioara este evidentiat prin "".

Exercitii:

a) 567 + 856; b) 4319 + 7214; c) 6915 + 7298; d) 795 + 356; e) 1876 + 9545

Scaderea in zecimal codificat binar se efectueaza astfel:

fiecare cifra zecimala se exprima printr-o tetrada binara;

se efectueaza scaderea pozitie cu pozitie; daca pentru o pozitie nu este necesar imprumutul de la pozitia urmatoare, atunci rezultatul este corect;

daca este necesar un imprumut, acesta va declansa executia urmatoarelor operatiuni:

se scade 1 de la pozitia urmatoare;

se aduna 16 (10000) la descazutul operatiei curente;

se efectueaza scaderea;

se scade 6 (0110) din rezultat pentru corectie, deoarece s-a imprumutat 16 si nu 10 cat era necesar.

Exemplu: Sa se efectueze in cod BCD diferenta 539-175

Imprumutul de la o tetrada din pozitia urmatoare a este evidentiat prin "".

Exercitii:

a) 1234 - 765; b) 352 - 187; c) 4175 - 2497; e) 5432 - 2789; f) 6739 - 4869

Coduri detectoare si corectoare de erori

Determinarea paritatii - paritate para, paritate impara

Daca reprezentarea binara a unei valori contine un numar impar de valori de 1, spunem ca avem paritate impara, iar daca contine un numar par de valori de 1, spune ca avem un numar cu paritate para.

Atunci cand este necesara transmiterea unei informatii de la un dispozitiv la altul, exista posibilitatea modificarii accidentale a valorii unui bit sau a unui grup de biti din reprezentare numarului. Spunem ca a aparut o eroare de transfer. Detectia bitului transmis incorect poate fi detectata in cel mai simplu mod prin introducerea la sfarsitul secventei de biti ce urmeaza a fi transferata si a bitului de paritate. Daca atat dispozitivul care transmite informatia cat si receptorul convin sa foloseasca acelasi mod de calcul asupra bitului de paritate (para sau impara), dispozitivul care emite pozitioneaza ultimul bit astfel incat numarul total de biti de 1 din reprezentarea informatiei transmise (inclusiv bitul de paritate) sa fie par sau impar.

Exemplu :

I. paritate para:

informatia ce trebuie transmisa:   1 0 1 1 0 1 0 1
determinarea bitului de paritate:  
informatia ce va fi transmisa:  1 0 1 1 0 1 0 1

II. paritate impara:

informatia ce trebuie transmisa:   1 0 1 1 0 1 0 1
determinarea bitului de paritate:  
informatia ce va fi transmisa:  1 0 1 1 0 1 0 1

Dispozitivul care va receptiona informatia va contoriza numarul de biti de 1 receptionati. Daca ultimul bit din mesajul receptionat difera de cel calculat de receptor conform paritatii stabilite, atunci se semnaleaza emitatorul despre aparitia unei erori la receptie, cerand ca mesajul sa fie retransmis.

Aceasta metoda este utila pentru transferuri de dimensiuni mici, unde retransmiterea informatiei nu prezinta un inconvenient atat de mare. Principalul neajuns al acestei metode este ca nu poate detecta prezenta a mai mult de un bit eronat in mesajul receptionat. Daca doi biti din mesaj sunt incorecti, bitul de paritate nu mai semnaleaza eroarea.

Coduri polinomiale ciclice

Codurile polinomiale ciclice sunt cele mai utilizate coduri pentru detectarea erorilor dintr-un mesaj transmis. Ele mai sunt cunoscute si sub numele de coduri cu redundanta ciclica sau coduri CRC (Cyclic Redundancy Code). Codurile polinomiale sunt bazate pe tratarea sirurilor de biti ca reprezentari de polinoame cu coeficientii 0 sau 1. O secventa de cod de biti, , este vazuta ca o lista de coeficienti ai unui polinom de grad :

, , .

Codurile polinomiale ciclice au proprietatea: daca este un cuvant cu sens, atunci orice permutare ciclica a simbolurilor sale este un cuvant cu sens .

In cazul utilizarii acestor coduri, mesajului , ce trebuie transmis, i se asociaza polinomul . Apoi, printr-un algoritm de codificare, polinomul se transforma intr-un polinom , astfel incat sa fie multiplu al unui polinom , numit polinom de generare.

Pentru realizarea codificarii se poate utiliza algoritmul de inmultire sau algoritmul de impartire a polinoamelor. Operatiile aritmetice asupra coeficientilor polinoamelor se fac in modulo 2 si deci nu exista transport la adunare sau imprumut la scadere.

Folosind algoritmul de inmultire: nu se obtine o separare a simbolurilor redundante de cele informationale, aceasta fiind principalul motiv pentru care se prefera algoritmul de impartire, desi este mai complicat.

Consideram ca polinomul de generare este de grad :

, , .

Algoritmul de codificare prin impartire este urmatorul:

se inmulteste polinomul cu obtinandu-se ;

se imparte la :

Gradul polinomului va fi cel mult egal cu . Coeficientii polinomului , considerat de grad (eventual completand cu coeficienti nuli), constituie simbolurile de control asociate mesajului informational.

se aduna (modulo 2) cu , obtinandu-se polinomul . Coeficientii polinomului constituie mesajul ce se va transmite: , care contine in pozitiile semnificative cele simboluri informationale, iar in pozitiile mai putin semnificative cele simboluri de control.

Polinomul atasat mesajului transmis este un multiplu al polinomului de generare. Intr-adevar:

se obtine:

.

Polinomul este divizibil cu . Aceasta proprietate este folosita drept criteriu pentru detectia erorilor.

Fie mesajul receptionat , caruia i se asociaza polinomul . Se poate scrie ca , unde este polinomul erorilor. Aplicand criteriul de detectie a erorilor, obtinem:

.

Se observa ca daca este multiplu al lui , mesajul receptionat este validat, desi contine erori. Daca nu este multiplu al lui , atunci eroarea este sesizata.

Prin aceasta metoda sunt determinate toate pachetele de erori de lungime mai mica decat gradul lui . Prin pachet de erori se intelege o succesiune de simboluri, corecte sau eronate, in care primul si ultimul simbol sunt eronate. In transmisia datelor se folosesc trei polinoame generatoare, considerate standarde internationale:

,

,

.

Exemplu 1:

Sa se determine mesajul transmis stiind ca mesajul de transmis este si polinomul de generare este .

Rezolvare:

;

, deoarece gradul lui este 4;

;

se imparte la :

Observatie. Adunarea si scaderea in modulo 2 sunt echivalente.

Rezulta ca .

Polinomul transmis este :

.

Coeficientii acestui polinom reprezinta mesajul ce se va transmite: .

Exercitii:

Care va fi mesajul transferat daca mesajul util este:

a) 10101010; b) 11001101; c) 10010110; d) 10000011

Exemplul 2:

Stiind ca s-a receptionat mesajul , sa se verifice corectitudinea lui.

Rezolvare:

Mesajului receptionat i se asociaza polinomul . Aplicam criteriul de detectie a erorilor si impartind polinomul la obtinem catul si restul . Deoarece rezulta ca mesajul receptionat este eronat.

Exercitii:

Care a fost mesajul util, daca la receptie s-a primit mesajul T, stiind ca polinomul de generare a fost CRC - 12. Verificati daca transmisia a fost afectata de erori.

a) T = 110011001010100111

b) T = 111100001111000011

Codul Hamming

Richard Hamming a propus o metoda inovatoare de alcatuire a mesajului care va fi transmis, prin includerea mai multor biti de paritate, astfel incat receptorul sa poata detecta prezenta unui bit eronat care sa poata fi corectat.

Plasarea bitilor de paritate

Plasarea bitilor de paritate sunt locatiile avand ca indici puteri ale lui 2: . Celelalte pozitii din mesaj sunt reprezentarea binara a informatiei utile.

Vom considera in continuare ca se foloseste codificarea in paritate para.

Pentru un mesaj util reprezentat pe 4 biti sunt necesari inca 3 biti de paritate:

Calcularea bitilor de paritate se face astfel:

; ; .

Daca presupunem ca informatia utila ce trebuie transmisa are reprezentarea 1101, mesajul final va arata astfel:

Exercitii:

Codificati Hamming mesajele: 1011; 1100; 1001; 1010.

Observatie:

In cazul in care doi biti din reprezentare sunt afectati de eroare, se poate detecta prezenta erorii, dar nu se poate specifica care a fost valoarea initiala a celor doi biti.