note curs1

Click here to load reader

Post on 24-Dec-2015

251 views

Category:

Documents

0 download

Embed Size (px)

DESCRIPTION

curs

TRANSCRIPT

  • 1

    1 BAZELE MATEMATICE ALE CALCULATOARELOR

    1.1 Reprezentarea informaiei

    Informaiile prelucrate prin sistemele de calcul sunt de diverse tipuri dar

    ele sunt reprezentate la nivel elementar sub form binar. O informaie

    elementar corespunde deci unei cifre binare (0 sau 1) numit bit. O

    informaie mai complex (un caracter, un numr etc.) se exprim printr-o

    mulime de bii.

    Codificarea unei informaii const n a stabili o coresponden ntre

    reprezentarea extern a informaiei (caracterul A sau numrul 33, de

    exemplu) i reprezentarea sa intern, care este o secven de bii.

    Avantajele reprezentrii binare se refer n special la facilitatea de

    realizare tehnic cu ajutorul elementelor bistabile (sisteme cu 2 stri de

    echilibru) precum i la simplitatea efecturii operaiilor fundamentale sub

    forma unor circuite logice, utiliznd logica simbolic cu dou stri (0, 1).

    Informaiile prelucrate n sistemele de calcul sunt de dou tipuri:

    instruciuni i date.

    Instruciunile, scrise n limbaj main, reprezint operaiile efectuate n

    sistemul de calcul i ele sunt compuse din mai multe cmpuri:

    codul operaiei de efectuat;

    operanzii implicai n operaie. Codul operaiei trebuie s suporte o operaie de decodificare

    (transformare invers codificrii) pentru a se putea efectiv executa.

    Datele sunt operanzii asupra crora acioneaz operaiile (prelucrrile),

    sau sunt produse de ctre acestea. O adunare, de exemplu, se aplic la doi

    operanzi, furniznd un rezultat care este suma acestora.

    Se pot distinge datele numerice, rezultat al unei operaii aritmetice, sau

    date nenumerice, de exemplu simbolurile care constituie un text.

    Date nenumerice

    Datele nenumerice corespund caracterelor alfanumerice: A, B, ..., Z, a,

    b, ..., z, 0, 1, 2, ..., 9 i caracterelor speciale: ?, !, , $, ;, ...

    Codificarea se realizeaz pe baza unei tabele de coresponden specific

    fiecrui cod utilizat. Printre cele mai cunoscute coduri putem enumera:

    BCD Binary Coded Decimal prin care un caracter este codificat pe 6 bii;

    ASCII American Standard Code for Information Interchange (7 bii);

    EBCDIC Extended Binary Coded Decimal Internal Code (8 bii). Figura urmtoare prezint corespondena dintre diferite coduri.

  • 2

    Figura 1.1 Tabela de coresponden ntre coduri

    caracter BCD ASCII EBCDIC

    0 000000 0110000 11110000

    1 000001 0110001 11110001

    2 000010 0110010 11110010

    ... ... ...

    ...

    9 001001 0111001 11111001

    A 010001 1000001 11000001

    B 010010 1000010 11000010

    C 010011 1000011 11000011

    (6 bii) (7 bii) (8 bii)

    Datele numerice

    Datele numerice sunt de urmtoarele tipuri:

    a) numere ntregi pozitive sau nule: 0; 1; 315... b) numere intregi negative: -1; -155... c) numere fracionare: 3.1415; -0.5...

    d) numere n notaie tiinific: 4.9 107 ; 1023 ...

    Codificarea se realizeaz cu ajutorul unui algoritm de

    conversie asociat tipului de dat corespunztor. Operaiile

    aritmetice (adunare, scdere, nmulire, mprire) care se pot

    aplica asupra acestor date se efectueaz de regul n aritmetica

    binar. Figura de mai jos arat regulile operaiilor binare.

    0 + 0 = 0 0 0 = 0

    0 + 1 = 1 0 1 = 0

    1 + 0 = 1 1 0 = 0

    1 + 1 = 10 1 1 = 1

    Numerele ntregi pozitive sau nule cuprind: 0, 1, 2, ...,N, N + 1...

    Sisteme de numeraie

    Un sistem de numeraie face s-i corespund unui numr N, un anumit

    simbolism scris i oral. ntr-un sistem de numeraie cu baza p > 1, numerele

    0, 1, 2, ..., p 1 sunt numite cifre.

    Orice numr ntreg pozitiv poate fi reprezentat astfel:

    N = anpn + an-1pn-1 + ... + a1p + a0

  • 3

    cu ai 0, 1, 2, p-1 i an 0.

    Se utilizeaz de asemenea notaia echivalent N = anan-1...a1a0.

    Numerele scrise n sistenul de numeraie cu baza 2 (binar) sunt adesea

    compuse dintr-un mare numr de bii, i de aceea se prefer exprimarea

    acestora n sistemele octal (p = 8) i hexazecimal (p = 16), deoarece

    conversia cu sistemul binar este foarte simpl.

    Schimbri de baz

    a) binar zecimal

    Conversia se realizeaz prin nsumarea puterilor lui 2 corespunztoare

    biilor egali cu 1;

    Exemplu: 101012= 24 + 2

    2 + 2

    0 = 16 + 4 + 1 = 2110

    b) zecimal binar Conversia se efectueaz prin mpriri ntregi succesive cu 2. Testul de

    oprire corespunde situaiei ctului nul. Numrul binar este obinut

    considernd resturile n ordinea invers.

    Exemplu: Conversia lui 26:

    26 : 2 = 13 rest 0

    13 : 2 = 6 rest 1

    6 : 2 = 3 rest 0

    3 : 2 = 1 rest 1

    1 : 2 = 0 rest 1

    Se obine (de jos n sus): 2610 = 110102.

    c) octal (hexazecimal) zecimal

    Conversia se reduce la nsumarea puterilor lui 8 (16).

    d) zecimal octal (hexazecimal) Conversia se efectueaz prin mpriri ntregi succesive prin 8 (16).

    Testul de oprire corespunde situaiei ctului nul. Numrul octal

    (hexazecimal) este obinut considernd resturile obinute de la ultimul ctre

    primul.

    e) octal (hexazecimal) binar Conversia corespunde dezvoltrii fiecrei cifre octale (hexazecimale) n

    echivalentul ei binar pe 3 (4) bii.

    Exemplu:

    278 = 0101112 deoarece 28 = 0102 i 78 = 1112.

    3A16 = 001110102 deoarece 316= 00112 i A16=10102.

    f) binar octal (hexazecimal) Conversia se realizeaz nlocuind de la dreapta la stnga, grupele de 3

    (4) bii prin cifra octal (hexazecimal) corespunztoare. Dac numrul de

  • 4

    bii nu este multiplu de 3 (4) se completeaz configuraia binar la stnga cu

    zerouri.

    Exemplu: 1010112= 538 = 2B16 .

    Numere ntregi negative

    Numerele ntregi negative pot fi codificate prin trei metode:

    semn i valoare absolut (SVA);

    complement logic sau restrns sau fa de 1 (C1);

    complement aritmetic sau adevrat sau fa de 2 (C2); Prin metoda semn i valoare absolut, numerele se codific sub

    forma: valoare absolut. Prin aceast reprezentare se sacrific un bit pentru semn. n mod normal,

    0 este codul semnului +, iar 1 este codul semnului -. n aceste condiii, pe un

    cuvnt de k bii se pot reprezenta numere ntregi pozitive i negative N,

    astfel nct: - (2k-1

    - 1) N (2k-1

    - 1).

    Aceast metod de reprezentare prezint unele inconveniente:

    numrul zero are dou reprezentri distincte: 000...0 i 100...0, adic +0 i - 0;

    tabelele de adunare i nmulire sunt complicate din cauza bitului de semn care trebuie tratat separat.

    Complement logic i aritmetic

    Complementul logic (complement fa de 1) se calculeaz nlocuind,

    pentru valorile negative, fiecare bit 0 cu 1 i 1 cu 0.

    Complementul aritmetic (complement fa de 2) este obinut adunnd o

    unitate la valoarea complementului logic.

    Exemplu: Reprezentarea numrului (-6) pe 4 bii: +6 = 0110

    Semn i valoare absolut: - 6 = 1110

    Complement fa de 1: - 6 = 1001

    Complement fa de 2: - 6 = 1010

    Se poate uor constata c intervalul numerelor ntregi N care se pot

    reprezenta n complement fa de 1 este acelai ca i pentru reprezentarea

    semn i valoare absolut.

    Pentru reprezentarea n complement fa de 2 exist o valoare n plus,

    deci pentru k bii vom avea: -2k-1

    N (2k-1

    -1).

    Se poate remarca faptul c bitul cel mai din stnga (bitul de semn) este

    ntotdeauna 0 pentru numere pozitive i 1 pentru cele negative i aceasta

    pentru fiecare din cele trei reprezentri, conform tabelului urmtor.

  • 5

    (16 bii 2

    16 = 65536 = 2 32768 valori posibile)

    zecimal semn i valoare complement complement

    absolut fa de 2 fa de 1

    +32767 0111...1...1111 0111...1...1111 0111...1...1111

    +32766 0111...1...1110 0111...1...1110 0111...1...1110

    ... ... ... ...

    +1 0000...0...0001 0000...0...0001 0000...0...0001

    +0 0000...0...0000 0000...0...0000 0000...0...0000

    -0 1000...0...0000 ------------------ 1111...1...1111

    -1 1000...0...0001 1111...1...1111 1111...1...1111

    ... ... ... ...

    -32766 1111...1...1110 1000...0...0010 1000...0...0001

    -32767 1111...1...1111 1000...0...0001 1000...0...0000

    -32768 ------------------ 1000...0...0000 ------------------

    Reprezentarea n complement fa de 1 recunoate dou zerouri (+0

    i 0), dar este simetric, deoarece aceleai numere pozitive i negative

    sunt reprezentabile, iar aceast situaie se poate uor realiza electronic.

    n complement fa de 1 sau fa de 2, operaiile aritmetice sunt

    avantajoase, deoarece operaia de scdere se realizeaz prin adunarea

    complementului.

    ntr-o adunare n complement fa de 1, o cifr de transport ctre ordinul

    superior generat de bitul de semn trebuie adugat la rezultatul obinut,

    spre deosebire de complementul fa de 2, cnd aceast cifr de transport se

    ignor.

    n complement fa de 1 sau 2 nu se produce depire de capacitate

    dect n cazul n care cifrele de transport generate de bitul de semn i de

    bitul anterior acestuia sunt diferite.

    Numere fracionare

    Numerele fracionare sunt numerele subunitare.

    Schimbri de baz

    a) binar zecimal Conversia se face adunnd puterile corespunztoare ale lui 2.

    Exemplu: 0.012 = 0 2-1

    + 1 2-2

    = 0.2510.

    b) zecimal binar Conversia se efectueaz prin nmuliri succesive cu 2 a numerelor pur

    fracionare. Acest algoritm trebuie s se termine cnd se obine o parte

  • 6

    fracionar nul sau cnd numrul de bii obinui corespunde mrimii

    registrului sau a cuvntului de memorie n care se va stoca valoarea.

    Numrul binar se obine citind prile ntregi n ordinea calculrii lor.

    Exemplu: 0.125 2 = 0.250 = 0 + 0.250

    0.25 2 = 0.50 = 0 + 0.50

    0.50 2 = 1.0 = 1 + 0.0

    Vom considera prile ntregi de sus n jos, deci: 0.2510= 0.0012.

    Pentru numerele fracionare se pot remarca reprezentrile n virgul fix

    i virgul mobil.

    Virgula fix (VF)

    Sistemele de calcul nu posed virgula la nivelul mainii, deci

    reprezentarea numerelor fracionare se face ca i cnd acestea ar fi ntregi,

    cu o virgul virtual a crei poziie este controlat de ctre programator.

    Datorit dificultii de gestionare a virgulei de ctre programator (pot

    apare frecvent situaii de depire a capacitii de memorare), se prefer

    soluia aritmeticii n virgul mobil.

    Virgula mobil (VM) Primele sisteme de calcul utilizau doar virgula fix pentru efectuarea

    operaiilor aritmetice, iar ctre sfritul anilor 50, n urma apariiei logicii

    cablate s-a introdus pe scar larg reprezentarea n virgul mobil a

    numerelor fracionare.

    n majoritatea sistemelor de calcul actuale destinate n special

    aplicaiilor de natur tehnico-tiinific, cele dou metode de reprezentare

    (virgula fix i virgula mobil) coexist i sunt foarte utile.

    Reprezentarea n virgul mobil const n a reprezenta numerele sub

    forma urmtoare:

    N = M BE cu: B = baza (2, 8, 10, 16...)

    M = mantisa

    E = exponentul

    Exponentul este un numr ntreg, mantisa normalizat este un numr

    pur fracionar (fr cifre semnificative la partea ntreag). Cu excepia

    numrului zero (n general reprezentat prin cuvntul 000...0), vom avea

    ntotdeauna: 0.12 M 12 , sau 0.510 M 110.

  • 7

    Exponentul i mantisa trebuie s poat reprezenta att numere pozitive

    ct i negative. Cel mai adesea, mantisa admite o reprezentare sub forma

    semn i valoare absolut, iar exponentul este fr semn, dar decalat.

    Exemplu

    SM ED M

    unde SM este semnul mantisei, ED este exponentul decalat i M mantisa.

    Pentru nu numr de k bii rezervai pentru ED se pot reprezenta fr

    semn 2k valori, de la 0 la 2

    k 1. Decalajul considerat este 2

    k-1, ceea ce

    permite ca valorile de la 0 la 2k-1

    -1 pentru ED s corespund unui exponent

    real (ER) negativ, iar valorile de la 2k-1

    la 2k 1 ale lui ED s corespund

    unui exponent real (ER) pozitiv. Deci domeniul de valori reprezentabile

    pentru exponentul real este de la 2k-1

    la 2k-1

    -1.

    De exemplu, pentru k = 4, pe cei 4 bii putem reprezenta fr semn

    numere de la 0 la 15 pentru ED. Decalajul considerat este 2k-1

    = 23 = 8, deci

    pentru exponentul real (ER) putem considera valori de la - 2k-1

    = -23 = -8 i

    pn la 2 k-1

    1 = 23 1 = 7.

    Relaia existent se poate scrie astfel: ER = ED D.

    Exponentul determin intervalul de numere reprezentabile n sistemul de

    calcul, iar numerele prea mari pentru a putea fi reprezentate corespund unei

    depiri superioare de capacitate de memorare overflow, iar numerele

    prea mici corespund unei depiri inferioare de capacitate de memorare

    underflow.

    Mrimea mantisei exprim precizia de reprezentare a numerelor.

    Avantajul utilizrii virgulei mobile fa de virgula fix const n

    intervalul mult mai extins al valorilor posibile de reprezentat.

    Figura urmtoare prezint schematic tipurile diverse de informaii

    prelucrate n sistemele de calcul.

    Standardul IEEE 754

    Standardul IEEE Institute of Electrical and Electronics Engineers

    definete trei formate de reprezentare a numerelor n virgul mobil:

    a) simpl precizie pe 32 de bii (1 bit pentru SM, 8 bii pentru ED i 23 pentru M);

    b) dubl precizie pe 64 bii (1 bit pentru SM, 11 bii pentru ED i 52 bii pentru M);

    c) dubl precizie extins pe 96 bii (1 bit pentru SM, 15 bii pentru ED i 80 bii pentru M) .

    d) precizie cvadrupl pe 128 bii (1 bit pentru SM, 15 bii pentru ED i 112 bii pentru M)

  • 8

    Exponentul este decalat cu 128 pentru reprezentarea n simpl precizie i

    cu 1024 pentru reprezentarea n dubl precizie. Mantisa fiind normalizat,

    exist sigurana c primul bit al mantisei are valoarea 1, ceea ce permite

    omiterea sa (bit ascuns) pentru creterea preciziei de reprezentare, dar

    complic prelucrarea informaiei.

    INFORMA|II

    INSTRUC|IUNI DATE

    (diferite formate n cod main)

    Cod op. Operanzi

    Numerice Nenumerice

    Codificare prin tabele

    BCD (6 bii)

    ASCII (7 bii)

    EBCDIC (8 bii)

    Numere ntregi pozitive Numere ntregi negative

    (conversie direct

    zecimal binar)

    SVA C1 C2

    Numere fracionare

    VF VM (mantis, baz, exponent)

    Coduri zecimale codificate n binar

    Dac aritmetica sistemelor de calcul este de regul binar, ea poate fi de

    asemenea i zecimal. n cazul calculatoarelor de buzunar i de birou, n

    sistemele de calcul specifice aplicaiilor comerciale, operaiile se efectueaz

    direct asupra reprezentrii zecimale a numerelor.

  • 9

    Un numr zecimal, care cuprinde una sau mai multe cifre (de la 0 la 9),

    este codificat cu ajutorul biilor utiliznd anumite coduri. Tabela de mai jos

    prezint patru exemple de astfel de coduri.

    zecimal BCD excedent-3 2 din 5 bicvintal 0 0000 0011 00011 01 00001 1 0001 0100 00101 01 00010

    2 0010 0101 00110 01 00100

    3 0011 0110 01001 01 01000 4 0100 0111 01010 01 10000

    5 0101 1000 01100 10 00001

    6 0110 1001 10001 10 00010

    7 0111 1010 10010 10 00100 8 1000 1011 10100 10 01000

    9 1001 1100 11000 10 10000

    Exemplu: zecimal :129

    binar :10000001 = 27 +2

    0 = 128 + 1

    BCD :000100101001

    Codul BCD

    Codul BCD Binary Coded Decimal este unul dintre cele mai

    rspndite coduri cu semnificaia zecimal codificat n binar, n care

    fiecare cifr zecimal este codificat n mod individual n echivalentul su

    binar pe patru bii.

    Orice cifr zecimal se poate reprezenta pe patru bii, dar valorile

    reprezentabile pe patru bii sunt n numr de 24 = 16, deci vor rmne 6

    configuraii neutilizate, de care trebuie s se in seama la efectuarea

    operaiilor aritmetice.

    n situaia operaiei de adunare trebuie s se adauge 6 ori de cte ori

    rezultatul este superior lui 9, iar pentru operaia de scdere se va extrage 6

    dac rezultatul este negativ.

    Exemplu: zecimal binar BCD

    15+ 01111+ 00010101+

    18 10010 00011000

    --- ------- ------------- 33 100001 00101101 > 9

    (= 33) 0110 +6

    -------------

    00110011 (=33)

  • 10

    Operaiile aritmetice sunt deci destul de complicate, dar operaiile de

    intrare / ieire sunt uor de realizat deoarece fiecare entitate BCD este direct

    asociat unui caracter. Din aceste motive, codul BCD se gsete n

    sistemele de calcul de gestiune, unde operaiile aritmetice sunt mult mai

    puin numeroase dect operaiile de intrare / ieire.

    Codul BCD este un cod ponderat 8 4 2 1, cei patru bii necesari

    pentru a codifica o cifr au o pondere corespunztoare cu poziia lor,

    respectiv 8 = 23 pentru bitul cu numrul 3, 4 = 2

    2 pentru bitul cu numrul 2,

    2 = 21 pentru bitul cu numrul 1 i 1 = 2

    0 pentru bitul cu numrul 0.

    Codul excedent 3

    Codul excedent - 3 nu este un cod ponderat, fiecare cifr zecimal

    este codificat separat n echivalentul su binar + 3.

    Exemplu: 12910 = 010001011100 excedent - 3

    Avantajul acestui cod fa de codul BCD este acela c operaiile

    aritmetice sunt mai simple.

    De exemplu, complementarea fa de 9 (similar n sistemul zecimal cu

    complementarea fa de 1 n sistemul binar) este imediat: este suficient

    complementarea fiecrui bit.

    Codul 2 din 5

    Codul 2 din 5 este un cod neponderat n care fiecare cifr zecimal

    este codificat pe 5 bii, dintre care numai 2 au valoarea 1.

    Exemplu: 12910 = 001010011011000 cod 2 din 5

    Avantajul acestui cod este acela de detectare (nu i corectare) a unei

    erori sau a unui numr impar de erori.

    Codul bicvintal

    Codul bicvintal este un cod ponderat 5043210 care permite detectarea

    erorilor. O cifr zecimal este codificat printr-un numr binar pe 7 bii,

    avnd un singur bit egal cu 1 pe primele 2 poziii din stnga i un singur bit

    egal cu 1 pe 5 poziii cele mai din dreapta.

    Exemplu: 12910 = 010001001001001010000 bicvintal.

    1.2 Coduri de erori

    Informaiile pot fi modificate involuntar n timpul transmisiei sau

    stocrii lor n memorie. Trebuie deci utilizate anumite coduri care permit

    detectarea sau chiar corectarea erorilor datorate acestor modificri.

  • 11

    Aceste coduri se constituie pe un numr de bii superior celui strict

    necesar pentru a codifica informaia. Astfel, celor m bii de date li se adaug

    k bii de control. Deci, n memorie vor fi stocai n m + k bii. Asemenea configuraii definesc codurile redundante.

    Unele coduri nu permit dect detectarea erorilor (coduri

    autoverificatoare), altele permit detectarea i corectarea uneia sau mai

    multor erori (coduri autocorectoare).

    Controlul de paritate este codul autoverificator cel mai simplu. El se

    compune din m + 1 bii: cei m bii de informaie la care se adaug al

    (m + 1) lea bit numit bit de paritate. Valoarea sa este aleas astfel ca

    numrul total de bii egali cu 1, calculat pe n + 1 bii s fie par (n cazul

    unei pariti pare), sau impar (paritate impar).

    Exemplu: Transmiterea de caractere codificate n ASCII pe 7 bii plus

    un bit de paritate ntre un calculator i un terminal.

    A 1 1000001

    B 1 1000010

    E 0 1000101

    bit de paritate impar

    Dac un bit este schimbat din eroare n timpul transferului, paritatea nu

    mai este verificat i informaia trebuie retransmis, deoarece eroarea nu

    poate fi localizat pentru a putea fi corectat.

    n general, controlul de paritate nu permite dect detectarea unui numr

    impar de erori, n cazul unui numr par efectele se pot anula.

    Controlul de paritate nu poate fi utilizat dect pentru transmisii n care

    posibilitatea apariiei erorilor este sczut (de exemplu, n interiorul unui

    calculator sau ntre calculator i perifericele sale).

    Codul dublei pariti

    Codificare: considerm exemplul unui cod ASCII (7 bii);

    fiecare caracter este codificat pe o linie a unui tablou;

    un cod de paritate este efectuat pe fiecare linie (transversal);

    un cod de paritate este efectuat pe fiecare coloan (longitudinal); Decodificare

    controlul transversal permite detectarea erorilor pe linie;

    controlul longitudinal permite detectarea erorilor pe coloan; Dubla paritate permite corectarea unei erori, sau n anumite cazuri a

    unui numr impar de erori (ca de exemplu un numr impar de bii eronai

    pe aceeai linie, coloan sau repartizai pe linii i coloane diferite).

    Exemplu: Se dorete transmiterea mesajului 1968 cu paritate impar; se

    detecteaz o eroare la intersecia primei linii cu coloana a 4-a.

  • 12

    bit control

    1 2 3 4 5 6 7 paritate longitudinal

    1 0 1 1 1 0 0 1 0 F

    9 0 1 1 1 0 0 1 1 A

    6 0 1 1 0 1 1 0 1 A

    8 0 1 1 1 0 0 0 0 A

    bit paritate 1 1 1 1 0 0 1

    contr. transv. A A A F A A A

    Principiul dublei pariti este adesea utilizat n stocarea pe band

    magnetic a informaiilor. Astfel, pentru o band cu n piste:

    fiecare caracter este stocat transversal pe n 1 piste;

    un bit de paritate transversal este stocat pe a n-a pist;

    un bloc de caractere suport un control longitudinal de paritate.

    Codul lui Hamming

    Codul lui Hamming este un cod autocorector bazat pe teste de paritate.

    Versiunea cea mai simpl permite corectarea unui bit eronat. Celor m bii de

    informaie li se adaug k bii de control al paritii. Vom avea n = m+k bii

    necesari pentru transmiterea informaiei.

    Deoarece trebuie indicate n + 1 posibiliti de eroare (inclusiv absena

    erorii) prin cei k bii de control, trebuie ca 2k n + 1. Cele 2k posibiliti de

    de codificare pe k bii servesc la determinarea poziiei erorii, apoi se poate

    corecta bitul eronat.

    Tabelul urmtor permite determinarea lui k cnd se cunoate n:

    m 0 0 1 1 2 3 4 4 5 6 7 8 9 10 ... 120

    k 1 2 2 3 3 3 3 4 4 4 4 4 4 4 ... 8

    n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ... 128

    De obicei se ia n 2k 1 n loc de n < 2k 1. Dac se numeroteaz biii de la dreapta spre stnga pornind de la 1, biii

    de control (sau de paritate) sunt plasai pe poziia puterilor lui 2 (biii cu

    numrul 1, 2, 4, 8, 16, ...). Fiecare bit de control efectueaz control de

    paritate (par sau impar) asupra unui anumit numr de bii de date. Se

    determin astfel cei n bii de transmis sau de stocat.

    Exemplu: Dac m 4 se poate construi un cod Hamming (CH) pe 7 bii

    (n 7), adugnd 3 bii de control (k 3).

  • 13

    7 6 5 4 3 2 1

    m4 m3 m2 k3 m1 k2 k1

    Cei trei bii de control sunt plasai pe poziia puterilor lui 2:

    k1 1; k2 2; k3 4.

    Vom vedea acum, pentru fiecare bit al mesajului care sunt biii de

    control care permit verificarea paritii sale.

    7 (0111)2 4 + 2 + 1 7 este controlat de k3, k2, k1; 6 (0110)2 4 + 2 6 este controlat de k3, k2; 5 (0101)2 4 + 1 5 este controlat de k3, k1; 4 (0100)2 4 4 este controlat de k3; 3 (0011)2 2 + 1 3 este controlat de k2, k1; 2 (0010)2 2 2 este controlat de k2; 1 (0001)2 1 1 este controlat de k1;

    Problema se pune i invers: care sunt poziiile binare controlate de ctre

    fiecare cod? Rspunsul este urmtorul:

    k1 controleaz biii cu numerele 1, 3, 5, 7;

    k2 controleaz biii cu numerele 2, 3, 6, 7;

    k3 controleaz biii cu numerele 4, 5, 6, 7.

    Cnd se recepioneaz informaia, se efectueaz controlul de paritate.

    Pentru fiecare bit de control se compar valoarea transmis cu cea recalculat.

    Dac cele dou valori sunt identice, se atribuie valoarea 0 unei variabile

    binare Ai asociat bitului de control ki, altfel, Ai primete valoarea 1.

    Valoarea zecimal a configuraiei binare format din variabilele

    Ak, Ak-1, ..., A1 furnizeaz poziia bitului eronat, care se poate corecta.

    Presupunem c: pentru k1, A1 1, pentru k2, A2 1, iar pentru k3,

    A3 0. Eroarea se gsete n poziia (A3A2A1)2 (011)2 3.

    ntr-adevr, k1 poate detecta o eroare n poziiile 1, 3, 5, 7, k2 poate

    detecta o eroare pe poziiile 2, 3, 6, 7, iar k3 pe poziiile 4, 5, 6, 7. O eroare

    detectat de k 1 i k 2 nu i de k3 nu poate proveni dect din bitul 3.

    Exemple:

    (A3A2A1)2 (000)2 indic absena unei erori;

    (A3A2A1)2 (001)2 indic eroare pe bitul 1;

    (A3A2A1)2 (110)2 indic eroare pe bitul 6.

    Exemplu de recepionare a unui mesaj: (1011100)2. Dac s-a utilizat un

    CH cu paritate par, s se reconstituie mesajul iniial (n 7, k 3, m 4).

    numr 7 6 5 4 3 2 1

    tip m4 m3 m2 k3 m1 k2 k1

    valoare 1 0 1 1 1 0 0

    k1 0 controleaz poziiile 1, 3, 5, 7, nu se verific, deci A1 1;

    k2 0 controleaz poziiile 2, 3, 6, 7, se verific, deci A2 0;

  • 14

    k3 0 controleaz poziiile 4, 5, 6, 7, nu se verific, deci A3 1;

    Adresa erorii (A3A2A1)2 (101)2 5. Bitul numrul 5, care este egal cu

    1 este eronat. Mesajul iniial corectat i fr biii de control este: (1001)2.

    Calculul simplificat al codului lui Hamming (CHS)

    Metoda Hamming poate simplifica calculul biilor de control, astfel:

    se transform n binar poziiile din mesaj care conin valoarea 1;

    se nsumeaz modulo 2, astfel:

    pentru paritate par: un numr par de 1 0, un numr impar

    de 11 (sum modulo 2 direct);

    pentru paritate impar: un numr par de 11, un numr

    impar de 10 (sum modulo 2 inversat).

    Exemplu: S codificm mesajul (10101011001)2 cu paritate par:

    m 11, deci k 4 i n 15.

    numr 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

    tip m11 m10 m9 m8 m7 m6 m5 k4 m4 m3 m2 k3 m1 k2 k1

    valoare 1 0 1 0 1 0 1 ? 1 0 0 ? 1 ? ?

    Biii cu valoarea 1 se gsesc pe poziiile 15, 13, 11, 9, 7, 3, deci:

    15 1 1 1 1

    13 1 1 0 1

    11 1 0 1 1

    9 1 0 0 1

    7 0 1 1 1

    3 0 0 1 1

    -----------

    0 1 0 0 bii de paritate

    k4 k3 k2 k1 Mesajul codificat este deci (101010101001100)2.

    Exemplu de recepie a unui mesaj:

    S-a primit mesajul urmtor: (101000101001100)2, codificat cu paritate

    impar. Biii cu valoarea 1 se gsesc pe poziiile 15, 13, 9, 7, 4, 3.

    15 1 1 1 1

    13 1 1 0 1

    9 1 0 0 1

    7 0 1 1 1

    4 0 1 0 0

    3 0 0 1 1

    ---------- adunare modulo 2 inversat.

    0 1 0 0

    A4A3A2A1 eroare pe poziia 4.

  • 15

    Dup corectarea erorii i eliminarea codurilor de control, mesajul iniial

    este: (10100011001)2.

    Codul lui Hamming i erorile grupate

    Metoda lui Hamming poate corecta n general doar un bit eronat, dar se

    poate utiliza pentru detectarea i corectarea erorilor multiple pe o secven

    de bii aranjnd mesajul sub form matricial, codificnd pe linie dup

    metoda HC i transmind mesajul pe coloane.

    De exemplu, pentru transmiterea mesajului Hamming se codific pe o

    linie fiecare caracter n cod ASCII, completnd cu biii de control dup

    metoda CH.

    ASCII Cod Hamming (pentru fiecare liter)

    11 10 9 8 7 6 5 4 3 2 1 (numr)

    H 1001000 1 0 0 1 1 0 0 1 0 0 0

    a 1100001 1 1 0 0 0 0 0 0 1 1 0

    m 1101101 1 1 0 0 1 1 0 0 1 1 1

    m 1101101 1 1 0 0 1 1 0 0 1 1 1

    i 1101001 1 1 0 0 1 0 0 1 1 0 1

    n 1101110 1 1 0 0 1 1 1 1 0 0 1

    g 1100111 1 1 0 0 0 1 1 0 1 0 1

    Dac se produc erori grupate, pentru o secven de bii suficient de

    scurt, ( 7 pentru acest caz) atunci, efectund transmisia pe coloan vom

    avea un singur bit eronat pe linie, pe care-l putem corecta datorit biilor de

    control adugai potrivit metodei lui Hamming.

    n ultimii ani, codurile autocorectoare sunt din ce n ce mai utilizate

    pentru a asigura integritatea informaiilor stocate n memorie.

    Un cod autocorector permite creterea considerabil a timpului mediu

    ntre dou defeciuni care pot s apar: erorile nu apar dect atunci cnd

    numrul lor depete capacitatea de corectare a codului respectiv. Erorile

    care nu sunt corectate, cel puin se pot detecta.

    Detectarea erorilor grupate

    n comunicaiile la distan, erorile sunt mult mai frecvente dect n

    interiorul calculatorului. Erorile consecutive pot fi extinse adesea la un bloc

    ntreg de bii de informaie.

    Se vor utiliza n acest sens coduri care permit detectarea erorilor

    grupate, corectarea acestora fiind adesea prea costisitoare.

    Metoda codurilor polinomiale (CRC)

    CRC Cyclic Redondant Coding este metoda cea mai folosit pentru

    detectarea erorilor grupate. naintea transmiterii, informaiei i se adaug bii

  • 16

    de control, iar pe baza acestora, dac la recepionarea mesajului se

    detecteaz erori, atunci acesta trebuie retransmis.

    O informaie pe n bii poate fi considerat ca lista coeficienilor binari ai

    unui polinom cu n termeni, deci de grad n-1.

    Exemplu: 110001 x5 + x

    4 + 1;

    Pentru a calcula biii de control se va efectua un anumit numr de

    operaii cu aceste polinoame cu coeficieni binari. Operaiile se vor efectua

    modulo 2, adunarea i scderea nu va ine seama de cifra de transport, deci

    toate operaiile de adunare i scdere sunt identice cu operaia logic XOR.

    Pentru generarea i verificarea biilor de control att sursa ct i

    ddestinaia mesajului utilizeaz un polinom generator G (x).

    Dac M (x) este polinomul corespunztor mesajului iniial (de transmis),

    iar r este gradul polinomului generator G (x), atunci algoritmul de construire

    i verificare a codurilor care se incorporeaz n mesajul de transmis este

    urmtorul:

    1) se nmulete M (x) cu xr (se adaug r zerouri la sfritul mesajului iniial);

    2) se efectueaz mprirea modulo 2: M(x)*xr/G(x)Q(x)+R(x)/G(x); Ctul Q (x) se ignor, iar restul R (x) conine r bii. Se efectueaz

    scderea modulo 2: M (x) * xr R (x) T (x), iar T (x) este

    polinomul care reprezint mesajul de transmis. Polinomul ciclic T

    (x) Q (x) * G (x) este un multiplu al polinomului generator.

    4) La recepionarea mesajului se efectueaz mprirea T (x) /G (x):

    a) dac restul 0 nu sunt erori de transmisie; b) altfel, s-au produs erori, deci mesajul trebuie retransmis.

    Exemplu de transmitere a unui mesaj. Se dorete transmiterea mesajului

    101101 (6 bii) M (x) =x5 + x

    3 + x

    2 + 1.

    Polinomul generator este: 1011 G (x) = x3 + x + 1 de grad r = 3.

    1) Efectum nmulirea: M (x) xr = 101101000 (se adaug r = 3 zerouri la M (x).

    2) Realizm mprirea modulo 2: M (x)*xr/G (x):

    1 0 1 1 0 1 0 0 0 1 0 1 1

    1 0 1 1 ---------

    --------

    1 0 0 0 0 1 ctul Q(x)

    0 0 0 0 0 1 0 0 0

    1 0 1 1

    --------

    0 0 1 1 R (x) = 0 1 1

    3) Ctul Q (x) este ignorat. Pentru a realiza diferena modulo 2 M (x) *x

    r R (x) este suficient adugarea celor r bii din R (x) la

  • 17

    sfritul mesajului M (x) mesajul de transmis este

    T (x) = 101101011.

    Exemplu de recepionare a unui mesaj. S-a primit mesajul urmtor:

    11010101. G (x) = 1011 (4 bii) G (x) = x3 + x + 1 de grad r = 3.

    4) Se efectueaz mprirea T (x) / G (x).

    1 1 0 1 0 1 0 1 1 0 1 1

    1 0 1 1 ---------

    --------

    1 1 1 1 0

    0 1 1 0 0

    1 0 1 0

    -------- 0 1 1 1 1

    1 0 1 1

    --------

    0 1 0 0 0

    1 0 1 1

    --------

    0 0 1 1 1 R (x) = 1 1 1

    R (x) 0, s-au detectat erori de transmisie, mesajul se retransmite.

    Cele mai utilizate polinoame generatoare G (x) sunt:

    CRC 12 x12 + x11 + x3 + x2 + x + 1;

    CRC 16 x16+ x15 + x2 + 1;

    CRC CCITT x16 + x12 + x5+ 1.

    1.3 Elemente de logic numeric

    Logica propoziional este o algebr al crei obiectiv iniial este

    modelarea raionamentului.

    Mai recent aceast algebr i-a demonstrat utilitatea ca instrument de

    concepie (concepia circuitelor calculatorului).

    O a treia utilizare a logicii const n a servi ca model de calcul pentru

    limbajele de programare (Prolog).

    Logica propoziional este un model matematic care ne permite s

    raionm asupra naturii adevrate sau false a expresiilor logice.

    O propoziie este un enun care poate lua una din cele dou valori de

    adevr: adevrat sau fals. Simbolurile care pot reprezenta o propoziie se

    numesc variabile propoziionale.

    Expresii logice

    O prim mulime de expresii logice se definete recursiv astfel:

    - sunt operanzi atomici:

  • 18

    variabilele propoziionale;

    constantele logice true i false; - Orice operand atomic este expresie logic; - Dac E i F sunt expresii logice atunci E and F este expresie logic; - Dac E i F sunt expresii logice atunci E or F este expresie logic; - Dac E este expresie logic atunci not E este expresie logic; Prezentm definiia operatorilor logici and, or i not.

    and 0 1 or 0 1 not

    0 0 0 0 0 1 0 1

    1 0 1 1 1 1 1 1

    Funcii booleene

    Semnificaia unei expresii logice poate fi descris formal ca o funcie

    care d o valoare adevrat sau fals pentru expresia ntreag pornind de la

    valoarea argumentelor, numit funcie logic sau boolean.

    Tabele de adevr

    O funcie boolean poate fi reprezentat n practic printr-o tabel de

    adevr ale crei linii corespund tuturor combinaiilor de valori de adevr

    pentru argumente. Exist o coloan pentru fiecare argument i una pentru

    valoarea funciei.

    Figura urmtoare prezint tabelele de adevr pentru operaiile logice

    and, or, not, xor.

    p q p and q p q p or q p not p p q p xor q

    0 0 0 0 0 0 0 1 0 0 1

    0 1 0 0 1 1 1 0 0 1 0

    1 0 0 1 0 1 1 0 0

    1 1 1 1 1 1 1 1 1

    Tabela de adevr a unei funcii cu k argumente posed 2k linii. Fiecare

    linie asigneaz pentru funcie valoarea 0 sau 1, deci exist 22k

    funcii.

    Operatori logici suplimentari

    implicaia dac p este adevrat atunci q este adevrat;

    echivalena dac i numai dac;

    operatorul nonand not (p and q), notat p nand q;

    operatorul nonor not (p or q), notat p nor q.

    Figura urmtoare prezint tabelele de adevr pentru , , nand, nor.

  • 19

    p q p q p q p q p q p nand q p q p nor q

    0 0 1 0 0 1 0 0 1 0 0 1

    0 1 1 0 1 0 0 1 1 0 1 0

    1 0 0 1 0 0 1 0 1 1 0 0

    1 1 1 1 1 1 1 1 0 1 1 0

    Asociativitatea i precedena operatorilor logici

    Operatorii logici and i or sunt asociativi i comutativi i vor fi grupai

    de la stnga la dreapta. Ceilali operatori nu sunt asociativi.

    Precedena operatorilor logici: not, nand, nor, and, or, , .

    Funcii booleene ale expresiilor logice

    Vom construi expresii logice pornind de la tabelele de adevr. Dei se

    pot defini o infinitate de expresii logice, de obicei, se va ncerca pe ct

    posibil s se gseasc cea mai simpl expresie logic.

    Notaii prescurtate

    and se reprezint prin juxtapunerea operanzilor; or se reprezint prin +;

    not se reprezint prin sau prin bararea variabilei.

    Construcia unei expresii logice din tabela de adevr

    Forma normal disjunctiv este o sum logic de mintermi pentru

    care funcia ia valoarea logic adevrat (1). Un minterm este un produs

    logic de literale (variabile propoziionale) ale unei linii, astfel: dac p are

    valoarea 0 n coloana k, se utilizeaz p , altfel se utilizeaz p.

    Forma normal conjunctiv este un produs logic de maxtermi pentru

    care funcia ia valoarea 0. Un maxterm este o sum logic de literale ale

    unei linii, astfel: dac p ia valoarea 0 se utilizeaz p, altfel p .

    Legi algebrice pentru expresii logice

    Legi ale echivalenei

    1. Reflexivitate: pp ; 2. Comutativitate: pqqp ; 3. Tranzitivitate: rprqandqp ; 4. Echivalena negaiilor: qpqp ;

    Legi similare aritmeticii

    5. Comutativitate and: pqqp ;

  • 20

    6. Asociativitate and: rqprqp ; 7. Comutativitate or: pqqp ; 8. Asociativitate or: rqprqp ; 9. Distributivitate and fa de or: rpqprqp ; 10. 1 (true) este identitate pentru and: p1p ;

    11. 0 (false) este identitate pentru or: p0p ; 12. 0 este adsorbant pentru and: 00p ;

    13. Eliminare duble negaii: pp .

    Diferene fa de legile aritmeticii

    14. Distributivitate or fa de and: rpqprqp ; 15. 1 este adsorbant pentru or: 1p1 ;

    16. Idempotena operatorului and: ppp ;

    17. Idempotena operatorului or: ppp ;

    18. Subsumarea:

    a) pqpp ; b) pqpp .

    19. Eliminarea anumitor negaii:

    a) qpqpp ; b) qpqpp .

    20. Legile lui de Morgan:

    a) qp qp ;

    b) qpqp ;

    c) n21 p...pp p 1+ p 2+...+ p n;

    d) n21n21 p...ppp...pp .

    Legi ale implicaiei

    21. qppqandqp ; 22. qpqp ; 23. rprqandqp ; 24. qpqp .

  • 21

    Tautologii i metode de demonstraie

    25. Legea terului exclus: 1pp ; 26. Analiza de caz: qqpandqp ; 27. Contrara reciprocei: pqqp ; 28. Reducere la absurd: p0p ; 29. Demonstraie prin reducere: p1p ;

    Exemple:

    1) Funcii de o variabil a:

    a z0 z1 z2 z3 z0 = 0 constant; 0 0 0 1 1 z1 = a identitate;

    1 0 1 0 1 z2 = a negaie;

    z3 = 1 constant;

    2) Funcii logice de 2 variabile a i b:

    00 01 10 11 ab

    0 0 0 0 F0 = 0

    0 0 0 1 F1 = ba

    0 0 1 0 F2 = ba

    0 0 1 1 F3 = a

    0 1 0 0 F4 = ba

    0 1 0 1 F5 = b

    0 1 1 0 F6 = ba

    0 1 1 1 F7 = ba

    1 0 0 0 F8 = baba

    1 0 0 1 F9 = ba

    1 0 1 0 F10 = b

    1 0 1 1 F11 = ba

    1 1 0 0 F12 =

    1 1 0 1 F13 = ba

    1 1 1 0 F14 = (ab) = a+b

    1 1 1 1 F15 = 1

    a

  • 22

    Tabelele Karnaugh (TK)

    Tabelele sau diagramele lui Karnaugh permit simplificarea funciilor

    logice. Metoda se bazeaz pe inspectarea vizual a tabelelor judicios

    construite (metoda este util cu un numr de variabile 6).

    TK se poate considera ca o transformare a tabelei de adevr.

    TK cu 2 variabile

    Cele 4 csue ale TK corespund celor 4 linii ale tabelei de adevr:

    fiecare variabil logic completeaz o linie sau o coloan;

    un produs de 2 variabile completeaz o csu; Pentru a completa TK pornind de la tabela de adevr se atribuie valoarea

    1 csuelor corespunztoare strilor din intrare n care funcia are valoarea

    1. Metoda de simplificare const din a ncadra csuele ocupate, adiacente

    pe aceeai linie sau coloan (suprapunerile sunt permise). Figura urmtoare

    prezint o TK cu 2 variabile.

    a b z b a

    0 1

    0 0 0 0 1

    0 1 1

    1 0 1 1 1 1

    1 1 1

    n urma reducerii avem vom obine z = a+b.

    TK cu 3 variabile

    Tabela de adevr a funciei logice de 3 variabile se transform ntr-o TK

    cu dou dimensiuni, grupnd dou variabile pe linie sau coloan. Trecerea

    de la o linie (coloan) la alta difer printr-o singur variabil (se consider

    tabela ca nfurtoarea unui cilindru.

    Pentru construirea TK cu 3 variabile:

    fiecare variabil completeaz un bloc de 4 csue;

    un produs logic de dou variabile completeaz un bloc de 2 csue;

    un produs logic de 3 variabile completeaz o csu.

    Exemplu: f (a, b, c) = abc+abc+abc+abc;

    b ac

    00 01 11 10

    0 1 1 1

    1 1

    n urma reducerii se obine z = ac+bc.

  • 23

    TK cu 4 variabile

    Se construiete TK, precum nfurtoarea unui cilindru, att orizontal

    ct i vertical, astfel:

    fiecare variabil completeaz un bloc de 8 csue;

    un produs logic de 2 variabile completeaz un bloc de 4 csue;

    un produs logic de 3 variabile completeaz un bloc de 2 csue;

    un produs logic de 4 variabile completeaz o csu. Exemplu:

    z(a,b,c,d)=abcd+abcd+abcd+abcd+abcd+

    abcd+abcd+abcd+abcd+abcd+abcd.

    cd ab 00 01 11 10

    00 1 1

    01 1 1 1 1

    11 1 1 1 1

    10 1

    Expresia simplificat este z = d+bc+abc.

    n general, metoda de simplificare a unei funcii de 4 variabile prin TK

    este urmtoarea:

    ncadrarea csuelor cu 1 care nu sunt adiacente altora cu 1 i deci nu pot forma blocuri de 2 csue;

    ncadrarea csuelor care pot forma grupe de 2 csue dar nu pot forma blocuri de 4 csue;

    ncadrarea csuelor care pot forma grupe de 4 csue dar nu pot forma blocuri de 8 csue;

    ncadrarea grupelor de 8 csue adiacente; Pentru reducerea funciilor logice cu mai mult de 4 variabile trebuie

    create mai multe tabele Karnaugh.