Sisteme de numeratie, coduri - teoremele si axiomele algebrei binare

LABORATOR 1

I. PARTEA TEORETICA.TEOREMELE SI AXIOMELE ALGEBREI BINARE:

I.1. Notiuni fundamentale de algebra booleana.

Bazele acestei algebre au fost puse de G. Boole in a doua jumatate a secolului al XIX lea si fundamentate de C. Shanon in anul 1938. In Romania studii importante in acest domeniu sau facut de catre matematicianul George Moisil.

I.1.1. Axiomele si proprietatiile algebrei boolene.

Fie M o multime nevida dar finita si doua operatii definite prin " " -reuniune si " "-intersectie sau echivalentele lor logice " "(SAU)- disjunctie si " definim o functie binara (logica).

Fie K o submultime a multimii B^N₂ si I B^N₂ si avem sadisfacute relatile:

  si

Se cauta numarul de functii pentru un domeniu de "n" variabile binare

Concluzie: Deoarece pentru fiecare XI B^N₂ functia poate lua numai valorile 0 si 1 rezulta ca numarul functilor boolene distincte este finit si egal cu .

1.3. Operatii logice.

Pe baza postulatelor algebrei booleene sa se demonstreze urmatoarele identitati:

Sa se demonstreze urmatoarele identitati:

II. OPERATII SI TRANSFORMARI

2.1.Sistemul de numeratie zecimal

Sistemul de numeratie utilizat cel mai frecvent este sistemul de numeratie pozitional. Intr-un asfel de sistem, un numar se reprezinta printr-un sir de cifre in care fiecare din pozitile cifrelor are o anumita pondere. Valoarea unui numar este suma ponderata a cifrelor sale, de exemplu:

1734=1x1000+7x100+3x10+4x1

Virgula zecimala face posibila utilizarea unor puteri ale lui 10 atat pozitive cat si negative:

5185,68=5x1000+1x100+8x10+5x1+6x0,1+8x0,01

In general: un numar N de forma n₁n₀n_-1n_-2 are valoarea: N=n₁10¹+n₀10⁰+n_-110^-1+n_-210^-2

adica :  

Cifra cea mai din stanga este este cifra de cel mai mare ordin sau cifra cea mai semnificativa (MSB) iar cifra cea mai din dreapta este cifra de cel mai mic ordin sau cifra cea mai putin semnificativa (LSB).

2.2 Sistemul de numeratie binar

Baza de numeratie este 2 iar valoarea numarului este:

Exemple de echivalente zecimale ale numerelor binare:

10011₂=1x2⁴+0x2³+0x2²+1x2¹+1x2⁰=19₁₀

100010₂=1x2⁵+0x2⁴+0x2³+1x2²+1x2¹+0x2⁰=34₁₀

101,001₂=1x2²+0x2¹+1x2⁰+0x2^-1+0x2^-2+1x2^-3=5,125₁₀

Exemplu de transformare binar- zecimal:

179:2=89 rest 1 (LSB)

:2= 44 rest 1

:2= 22 rest 0

:2= 11 rest 0 deci: 179₁₀=1011001₂

:2= 5 rest 1

:2= 2 rest 1

:2= 1 rest 0

:2=0 rest 1 (MSB)

2.3 Sistemul de numeratie octal.

Are baza 8. Exemple:

Conversie zecimal-octal

- se fac impartiri repetate la 8 si se pastreaza restul. Rezultatul se citeste de la ultimul rest spre primul (MSB).

467:8=58 rest 3 (LSB)

:8= 7 rest 2 deci: 467₁₀=723₈

:2= 0 rest 7 (MSB)

Conversie octal - zecimal

- pornind de la relatia de reprezentare a numerelor intr-o baza data (8) numarul zecimal de obtine prin adunarea coeficientilor puterilor lui 8.

1234₈=1x8³+2x8²+3x8¹+4x8⁰=668₁₀

Conversie binar-octal

de la dreapta spre stanga se imparte cuvantul binar in grupe de trei biti, pentru fiecare scriindu-se cifra zecimala de la 0 la 7 corespunzatoare

100011001110₂=100 011 001 110₂ =4316₈

Conversie octal-binar

- fiecarei cifre din cuvantul octal ii corespunde o grupare de trei biti in binar.

1234₈=001 010 011 100₂

2.4 Sistemul de numeratie hexazecimal.

Are baza 8. Exemple:

Conversie zecimal-hexazecimal

- se fac impartiri repetate la 16 si se pastreaza restul. Rezultatul se citeste de la ultimul

rest spre primul (MSB).

3417:16=213 rest 9 (LSB)

:16= 13 rest 5 deci: 3417₁₀=D59₁₆

:16= 0 rest 13 (MSB)

Conversie hexazecimal - zecimal

- pornind de la relatia de reprezentare a numerelor intr-o baza data (16) numarul zecimal

de obtine prin adunarea coeficientilor puterilor lui 16.

C0DE₁₆=12x16³+0x16²+13x16¹+14x16⁰=49374₁₀

Conversie binar-hexazecimal

- de la dreapta spre stanga se imparte cuvantul binar in grupe de patru biti, pentru

fiecare scriindu-se cifra zecimala de la 0 la F in hexa corespunzatoare.

100011001110₂= 1000 1100 1110 = 8CE₁₆

Conversie hexazecimal-binar

- fiecarei cifre din cuvantul hexazecimal ii corespunde o grupare de patru biti in binar.

C0DE₁₆= 1100 0000 1101 1110₂

2.5 Exemple de conversii de cod.

10111011001₂=2731₈=5D9₁₆=1497₁₀

00101001110₂=1234₈=29C₁₆=668₁₀

10,1011001011₂=010,101 100 101 100₂=2,5454₈

9F,46C_H=1001 1111, 0100 0110 1100₂

Lucrare: Determinarea energiei de activare Arrhenius - reactia tiosulfatul de sodiu cu acidul sulfuric Eseu: Coroziunea materialelor polimerice

2.6 Adunarea si scaderea numerelor nezecimale.

1.6.1. Adunarea numerelor binare.

pentru a realiza adunarea a doua numere binare, X si Y, se aduna biti cei mai putin semnificativi cu transportul initial. Se aplica acelasi procedeu tuturor bitilor pe rand pornind de la dreapta si adaugand transportul provenit de pe fiecare coloana la suma coloanei urmatoare.

X 190+ 1 0 1 1 1 1 1 0 + X 170+ 1 0 1 0 1 0 1 0 +

Y 141 1 0 0 0 1 1 0 1 Y 85 0 1 0 1 0 1 0 1

S 331 1 0 1 0 0 1 0 1 1 S 255 1 1 1 1 1 1 1 1

2.6.2. Scaderea numerelor binare.

pentru a realiza scaderea a doua numere binare, X si Y, se scad biti cei mai putin semnificativi cu imprumutul initial. Se aplica acelasi procedeu tuturor bitilor pe rand pornind de la dreapta si scazand imprumutul provenit de pe fiecare coloana la diferenta coloanei urmatoare.

I 0 1 1 0 1 1 0 1 0 I 0 0 0 0 0 0 0 0 0 cuvant de imprumut

X 210- 1 1 0 1 0 0 1 0 - X 221- 1 1 0 1 1 1 0 1 -

Y 109 0 1 1 0 1 1 0 1 Y 76 0 1 0 0 1 1 0 0

D 101 0 1 1 0 0 1 0 1 D 145 1 0 0 1 0 0 0 1

2.6.3. Adunarea numerelor hexazecimale.

X 1 9 B 9_H + X 1 9 11 9 +

Y C 7 E 6_H Y 12 7 14 6

S E 1 9 F_H S 14 17 25 15

14 16+1 16+9 15

E 1 9 F_H

2.6.4. Tabla adunarii si scaderii in sistemul binar.

Unde: C_in - transport de la rangul inferior

C_out - transport spre rangul superior

B_in - imprumut de la rangul superior

B_out - imprumut spre rangul inferior

2.7 Reprezentarea numerelor negative.

2.7.1. Reprezentarea prin bit de semn

numarul apare sub forma unei valori precedate de un semn care arata daca acea valoare este negativa sau pozitiva. Bitul de semn 1 reprezinta un numar negativ iar bitul de semn 0 un numar pozitiv.

01010101₂=+85₁₀ 11010101₂= - 85₁₀

01111111₂=+127₁₀ 11111111₂= - 127₁₀

2.7.2. Reprezentarea prin complement fata de 2

se complementeaza bit cu bit numarul pozitiv corespunzator adunandu-se la cel mai putin semnificativ bit valoarea 1.

17₁₀= 00010001₂ 11101110 + 119₁₀= 01110111₂ 10001000 +

1 1

1110111 1₂= - 17₁₀ 10001001₂= - 119₁₀

2.7.3. Reprezentarea prin complement fata de 1

se complementeaza bit cu bit numarul pozitiv corespunzator .

17₁₀= 00010001₂ 1110111 0₂= - 17₁₀ 119₁₀= 01110111₂ 10001000₂= - 119₁₀

2.7.4. Adunarea si scaderea complementelor fata de 2

scaderea se realizeaza prin adunarea unui numar negativ in complement fata de 2.

3+ 0011 - 2+ 1110 6+ 0110 4+ 0100

0100 - 6 1010 - 3 1101 - 7 1001

7 0111 - 8 11000 3 10011 - 3 1101

2.8 Inmultirea si impartirea in binar.

procedura asemanatoare cu sistemul zecimal

1.8.1. Inmultirea

11x 1011x

13 1101

33+ 1011+

11 0000

1011

143 1011

10001111 = 143₁₀

3. PROBLEME_[1]

Problema 4.1: Enuntati teoremele si postulatele algebrei booleene.

Problema 4.2: Sa se scrie in baza 2 urmatoarele numere: 37, 89, 133, 513, 1032, 1535, 2048

Problema 4.3: Sa se scrie in baza 10 urmatoarele numere binare:

11101₂, 110100101010₂, 01111011₂, 1000110111101100₂

Problema 4.4: Sa se scrie in hexazecimal urmatoarele numere:

1453, 277, 233, 433, 1128, 1024, 512

Problema 4.5: Sa se scrie in binar numerele:

5AD_H, FA_H, 1FD_H, 72D_H, 11F_H, FFA_H,

Problema 4.6: Sa se scrie in cod Gray primele opt cifre zecimale.

Problema 4.7: Pe baza teoremelor algebrei boolene sa se demonstreze:

Problema 4.8: Sa se exprime cu ajutorul functiei SI-NU functia:

Problema 4.9: Sa se exprime cu ajutorul functiei SAU-NU functia:

Problema 4.10: Pe baza tabelelor de adevar sa se demonstreze urmatoarele inegalitati:

Problema 4.11: Sa se efectueze urmatoarele operatii:

a) in binar: 110101+11001, 101110+100101, 11001101+1100011;

b) in hexazecimal: 1372+4631, 4F1A5+0B8D5, 0F35B+27E6

Problema 4.12: Sa se exprime pe opt biti numerele zecimale:

18, 23, 115, 79, -49, -6, -100

a) complement fata de 2

b) complement fata de 1

c) Cod semn-amplitudine

e) Cod Gray

Problema 4.13 Fiecare dintre urmatoarele operatii aritmetice este corecta in cel putin un sistem de numeratie. Determinati care este baza de numeratie in fiecare caz.

a)     

b)     

c)     

d)     

e)     

f)

Problema 4.14: Sa se demonstreze urmatoarele identitati:

Problema 4.15. Efectuati urmatoarele conversii intre sistemele de numeratie:

a)      1101011₂=?_H

b)      10110111₂=?_H

c)     

d)     

e)     

f)      

g)      AB3D_H=?₂=?₁₀=?₈

h)      9E36,7A_H=?₂=?₁₀=?₈

i)        7158₈=?₂=?₁₀=?_H

j)        3511₁₀=?₂=?₈=?_H

k)      4321₁₀=?₂=?₈=?_H

Problema 4.16 Efectuati urmatoarele operatii:

a)     

b)     

c)     

d)     

e)     

f)      

g)     

h)     

i)       

j)        AD59_H+FE25_H=?_H

k)      BC35_H - AE45_H=?_H

l)        123₁₀x12₁₀=?₂=?_H

m)   473₁₀x14₁₀=?₂=?_H

n)      473₁₀:14₁₀=?₂=?_H

o) 123₁₀:12₁₀=?₂=?_H