Realizace základních matematických operací v počítači

Realizace základních matematických operací v počítači Nedílnou součástí výuky HW a SW vybavení počítačů na naší škole je znalost práce aritmetické jednotky. Jak známo, počítače realizují aritmetické operace v binární soustavě. Aby HW realizace byla co nejjednodušší, prakticky veškeré výpočty se převádějí na provádění součtu. Rozdíl dvou čísel se převádí na přičítání doplňku (1. resp. 2. doplněk), násobení na přičítání, dělení na odčítání příslušného doplňku, Mocninu a odmocninu lze převést na sčítání resp. odčítání. V první části toho textu se zabýváme HW realizací aritmetických operací, druhá řeší tuto problematiku programově v jazyku Python.

Aplikace logických kombinačních obvodů 1. Sčítání ai

bi

ci

si

c i +1

0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

0 1 1 0 1 0 0 1

0 0 0 1 0 1 1 1

Tabulka 3.1

Základní logický kombinační obvod, který realizuje sčítání, se nazývá úplná binární sčítačka. Jeho pravdivostní tabulka je dána tab.3.1. Z Karnaughových map pro funkce Si a ci+1 pak odvodíme vztahy (3.1) a (3.2). Logické funkce pro Si a ci+1 lze realizovat obvodem z obr.3.1. Sčítačku pro N-bitová čísla můžeme vytvořit kaskádním propojením N stupňů - úplných binárních sčítaček. Na obr.3.2 je příklad pro N = 4, který se vyrábí v integrované podobě ve standardní řadě jako obvod 7483.

S i = ci .(ai .bi + ai .bi ) + ci .(ai .bi + ai .bi )

( 3.1 )

ci +1 = ai .bi + ci .(ai + bi ) = ai .bi + ci .(ai .bi + ai .bi )

( 3.2 )

Nevýhoda kaskádního řazení spočívá v postupném vytváření platných přenosových bitů ci+1 a proto doba potřebná k vytvoření součtu lineárně vzrůstá se vzrůstajícím počtem bitů sčítaných čísel podle vztahu

(

t omax = ( N − 1). tcmax + Max tcmax , tsmax

)

( 3.3 )

Proto se začaly vyrábět sčítačky se současným kanálem přenosu (zrychleným kanálem přenosu), který vytváří všechny potřebné přenosy najednou. Ze vztahu (3.2) snadno odvodíme tyto vztahy pro přenosy čtyřbitové sčítačky. 1

© Střední průmyslová škola elektrotechnická, V Úžlabině 320 Praha 10

c1 = a0 .b0 + c0 .(a0 + b0 )

( 3.4 )

c2 = a1.b1 + a0 .b0 .(a1 + b1 ) + c0 . (a0 + b0 ).( a1 + b1 )

( 3.5 )

c3 = a2 .b2 + a1.b1. (a2 + b2 ) + a0 . b0 . (a1 + b1 ). (a2 + b2 ) +

( 3.6 )

+ c0 . (a0 + b0 ).(a1 + b1 ).( a2 + b2 ) c4 = a3 .b3 + a2 .b2 .( a3 + b3 ) + a0 .b0 . (a1 + b1 ).(a2 + b2 ). (a3 + b3 )

( 3.7 )

+ a1.b1.( a2 + b2 ). (a3 + b3 ) + c0 .(a0 + b0 ). (a1 + b1 ).(a2 + b2 ). (a3 + b3 ) U1B

ci

4 6 5

U1A

ai bi ai bi

bi ci

A3 B3

ai bi ci

c i+1 Si

A2 B2

ai bi ci

c i+1 Si

A1 B1

ai bi ci

c i+1 Si

S1

A0 B0 c0

ai bi ci

c i+1 Si

S0

74ALS86

1

c4 S3

3 2 74ALS86 U2A 1 3

S2

2 74ALS00 U2B

ai ci

Si

U?A

4 6 5

1 2 13

12

c i+1

74ALS10

74ALS00 U2C 9 8 10 74ALS00

Obr.3.1

Obr.3.2 c4

c4

a3 b3

a3 b3

a2 b2

Obvod

c3

popsaný

a2 b2

rovnicemi (1.11) až (1.11)

a1 b 1

s3

s2

c2 a1 b1

s1

c1 a0 b0

a0 b0

c0

c0 Zrychlený kanál přenosu

2

s0

74LS83A

Výrazy c0, c1, c2 a c3 popisují zrychlený kanál přenosu, který je vhodné realizovat dvoustupňovým obvodem jako je tomu u sčítaček 74LS83A, 74LS283 nebo aritmetickologické jednotky (ALU) 74181. Na obr.3.3 je symbolicky znázorněna realizace 4-bitové sčítačky se zrychleným kanálem přenosu. Jak vyplývá z rovnic (3.4) až (3.7)

Obr.3.3 © Střední průmyslová škola elektrotechnická, V Úžlabině 320 Praha 10

složitost dvoustupňové realizace zrychleného kanálu přenosu s narůstajícím počtem sčítaných bitů rychle roste. Jako mezní hodnota bývá označována hodnota n ≤ 16 . K realizaci většinou použijeme kaskádní zapojení 4-bitových sčítaček se zrychleným kanálem přenosu. V tomto zapojení je přenos mezi jednotlivými sčítačkami realizován postupně, uvnitř sčítaček je zrychlený. Pro smíšený způsob vytváření přenosu je označováno jako hybridní sčítačka. Přenosy mezi čtyřbitovými sčítačkami můžeme realizovat i dvou a více stupňovými kanály rychlého přenosu. Z rovnic (3.4) až (3.7) zjistíme, že pouze poslední člen v každé rovnici je závislý na hodnotě počátečního přenosu. Označíme-li gk=ak.bk a pk=ak+bk můžeme rovnice (3.4) až (3.7) přepsat:

c1 = g0 + c0 . p0

( 3. 8 )

c2 = g1 + g0 . p1 + c0 . p0 . p1

( 3.9 )

c3 = g2 + g1 . p2 + g0 . p1 . p2 + c0 . p0 . p1 . p2

( 3.10 )

c4 = g3 + g2 . p3 + g1. p2 . p3 + g0 . p1. p2 . p3 + c0 . p0 . p1. p2 . p3 =

( 3.11 )

= G0 + c0 . P0 kde vyrazy G0 a P0 jsou funkcemi pouze sčítaných bitů ak a bk a k = 0,1,2 a 3. Obdobně můžeme pro přenos c8 psát

c8 =g7 +g6. p7 +g5. p6. p7 +g4.p5.p6. p7 +g3. p4. p5. p6.p7

( 3.12 )

+g2. p3. p4. p5. p6. p7 + g1. p2. p3. p4. p5. p6. p7 + +g0 . p1. p2 . p3. p4 . p5. p6 . p7 + c0 . p0 . p1. p2 . p3. p4 . p5. p6 . p7 = = G1 + p4 . p5 . p6 . p7 . (G0 + c0 . P0 ) = G1 + G0 . P1 + c0 . P0 . P1

kde G1 = g7+g6.p7 + g5.p6.p7 + g4.p5.p6.p7 a P1 = p4.p5.p6.p7. Analogicky můžeme odvodit vztahy pro c12 a c16, z kterých zjistíme, že jsou stejné jako rovnice (3.8) až (3.11) s tím, že nahradíme gk hodnotou Gk a pk hodnotou Pk. K realizaci druhého stupně zrychleného kanálu přenosu potřebujeme obvod realizující rovnice (3.8) až (3.11) a n-bitové sčítačky, které kromě obvyklých vstupů a výstupů ai, bi, Si, c0 a c4, budou vybaveny výstupy funkcí G a P. Takovými obvody jsou 74LS181, 74LS281, 74F381, 74AS681, 74AS881 a 74AS181. Zrychlené kanály přenosu se vyrábí jako obvody 74S182 a 74AS282, (realizují rovnice (3.8) až (3.10)) a místo rovnice (3.11) realizují funkce G a P pro dané připojení třetího stupně zrychleného kanálu přerušení, a 74AS882, který realizuje přenosy cn+8, cn+16, cn+24 a cn+32 pro 32-bitovou sčítačku. Na obr.3.4 je zobrazena 16-bitová sčítačka s dvoustupňovým kanálem 3


zrychleného přenosu realizovaná pomocí čtyřbitových sčítaček se zrychleným kanálem přenosu 74ACT881 a zrychleným kanálem přenosu 74ACT882 . c0 U1

a1 a a2

2 23 21 19

b 1b0 b b2

1 22 20 18

a0

3

3

7 6 5 4 3 8

A0 A1 A2 A3

F0 F1 F2 F3

B0 B1 B2 B3 CN S0 S1 S2 S3 M

A=B CN+4 P G

9 10 11 13

14 16 17 15

s0 s s2 1 s3

U5

P0 G0 P1 G1 P2 G2 P3 G3

P0 G0

17 16 4 3 2 1 19 18 6 5 7 8

CNA CNB P0 G0 P1 G1 P2 G2 P3 G3

CN' CN+X CN+Y CN+Z

P G

13

CN'

15 14 11

CN+X CN+Y CN+Z

9 12

S0 S1 74ACT882

74ACT881

CN'

U2

a4

2 23 21 19

b 5b4 b b6

1 22 20 18

a5 a 7a 6

7

7 6 5 4 3 8

A0 A1 A2 A3

F0 F1 F2 F3

S0 S1 S2 S3 M

s4 s s6 5 s7

ACT881

A=B CN+4 P G

14 16 17 15

P1 G1

B

b9 b8 b b11 10

1 22 20 18 7 6 5 4 3 8

F0 F1 F2 F3

9 10 11 13

s8 s s10 9 s11

A=B CN+4 P G

14 16 17 15

b13 b12 b b15 14

1 22 20 18 7 6 5 4 3 8

R1 3k3

6ns cn

S cn+y

P2 G2

B

P1 G1

6ns cn

S c n+x

ACT881 CN+Y

F0 F1 F2 F3

B0 B1 B2 B3

S0 S1 S2 S3 M

P2 G2

P0 G0

A

A0 A1 A2 A3

CN

B

A

U4 2 23 21 19

6ns

ACT881

74ACT881

a a13 12 a a15 14

S c n+z

6ns

B0 B1 B2 B3

S0 S1 S2 S3 M

cn

A

A0 A1 A2 A3

CN

6ns

CN+X

U3 2 23 21 19

P G

P3 G3

A

ACT881

74ACT881

a9 a 8 a a11 10

ACT882

c16

B0 B1 B2 B3 CN

9 10 11 13

A=B CN+4 P G

74ACT881

9 10 11 13

14 16 17 15

s12 s14

s13

B

s15

c0

6ns cn

S

c0

Obr.3.5 P3 G3

CN+Z

Obr.3.4

VCC

4


2. Odčítání Analogicky jako jsme postupovali při realizaci sčítání, mohli bychom odvodit tabulku pro úplnou binární odčítačku jako obvodu realizujícího operaci odčítání v jednom binárním řádu popsanou vztahem ai . 2 i − bi . 2i − ci . 2 i = ri . 2i − ci +1 . 2 i +1

( 3.13 )

Tato cesta by vedla k vytvoření dalších integrovaných obvodů - odčítaček. Jak bylo ukázáno, není nutné takový obvod vytvářet, protože odčítání můžeme realizovat jako součet dvojkového čísla s jednotkovým nebo dvojkovým doplňkem odčítaného čísla. Pro realizaci jednotkového doplňku potřebujeme invertovat všechny bity odčítaného čísla, k realizaci dvojkového doplňku musíme ještě k invertovanému číslu přičíst jedničku. Vytvoření dvojkového doplňku je možné provést kombinačním obvodem realizujícím funkcionální transformaci čísla na jeho dvojkový doplněk. Daleko častěji se vytváří z jednotkového doplňku, ke kterému je přičtena jednička pomocí sčítačky. Budeme-li dvojkový doplněk využívat k operaci sčítání, můžeme přičtení jedničky k jednotkovému doplňku realizovat při vlastním sčítání tím, že zavedeme nenulový (jednotkový) počáteční přenos c0 = 1. Příklad 1 Navrhněte sčítačku a odčítačku pracující s 8-bitovými čísly X a Y (8.bit představuje znaménko) ve vyjádření dvojkovým doplňkem s pevnou desetinnou čárkou. Sčítání nebo odčítání je řízeno signálem S/O, který je roven 0 pro sčítání a 1 pro odčítání.

V reprezentaci pomocí dvojkového doplňku zpracováváme znaménkový bit stejně jako bity významové. Tím se zjednodušuje obvodové řešení, při kterém není třeba porovnávat obě čísla pro vytvoření znaménka. Je však třeba generovat signál přeplnění pro případy, kdy výsledek přesahuje rozsah hodnot (-128,+127). Mohou nastat tyto případy:

a) Sčítání dvou kladných čísel Sčítačka má na vstupu operandy ve tvaru zv, y a zx, x, kde zv a zx představují znaménko (osmý bit) a x a y představují sedm významových bitů čísel X a Y. Výsledek součtu 0,x a 0,y může být 1) 2)

0, x + 0, y = 0, s , kde S=X+Y a x + y ≤ 2n−1 −1 0 , x + 0 , y = 1 , s , kde s je n-1 nižších řádů součtu x+y a x + y ≥ 2 n −1

5


V druhém případě dochází k přeplnění (přetečení), protože výsledkem součtu dvou kladných čísel je číslo záporné. To je chyba, kterou je třeba indikovat.

b) Sčítání kladného a záporného čísla Sčítačka má na vstupech operandy ve tvaru 0,x a 1,y a realizovanou operaci můžeme zapsat

0, x + 1, y = 0, x + (0, y ) + 1 1

1) pro x > y tj. x =y + r (r - rozdíl) platí 1 0, x + 1, y = 0, y + 0, r + (0, y ) + 1 = 0, r + 2 n = 0, r

( 3.14 )

( 3.15 )

Výsledkem je kladné číslo rovné rozdílu. 2) pro x < y tj. y = x+r platí 1 1 1 0, x + 1, y = 0, x + (0, x + 0, r ) + 1 = 0, x + (0, x )+ (0, r ) + 1 + 1 =

( 3.16 )

= (0, r ) + 1 1

Výsledek odpovídá zápornému vyjádření Y-X. Nedošlo k přeplnění.

c) Sčítání dvou záporných čísel Sčítačka zpracovává operandy ve tvaru 1,x a 1,y , pro které můžeme psát

1, x + 1, y = (0, x ) + 1+ (0, y ) + 1= (0, x + 0, y ) + 1 1

1

1

( 3.17 )

Výsledek je záporná reprezentace součtu dvou kladných čísel. Pro hodnotu 0,x + 0,y přichází v úvahu tři možné případy: 1) Pro 0,x + 0,y = 0,s kde s≤ ≤2n-1-1, platí 1 1, x + 1, y = (0, s ) + 1

( 3.18 )

Výsledek je záporná reprezentace součtu absolutních hodnot X a Y. 2) Pro 0,x + 0,y = 1,00 ... 0 platí 1 1, x + 1, y = (1,00...0) + 1 = 0,11...1 + 1 = 1,00...0

( 3.19 )

Limitní případ - součet X a Y se rovná hodnotě 2n-1. 3) Pro 0,x + 0,y = 1,s , kde s je nižších n-1 řádů součtu X + Y, platí 1, x + 1, y = (1, s ) + 1 1

( 3.20 )

1

Pokud (1,s) ≠ 0,11...1 , pak číslo 1,s patří k záporným číslům a jeho doplněk je číslo kladné. Při přeplnění (podtečení) je výsledek součtu dvou záporných čísel číslo kladné, což je chyba. 6


Z rozboru všech možností vyplývá, že k přetečení nebo podtečení dochází tehdy, když při součtu dvou čísel se stejným znaménkem získáme výsledek se znaménkem opačným. Pro funkci indukující chybu operace můžeme psát

Ch = z x .z y .z s + z x .z y .z s

( 3.21 )

kde zx, zv a zs představují znaménka X,Y a součtu (nebo rozdílu). Zbývá zvolit vhodný obvod zajišťující vytvoření jednotkového doplňku v závislosti na vstupním signálu S/O. Návrh takového obvodu je velmi jednoduchý a vede na obvod EX-OR (neekvivalence) nebo EX-NOR (ekvivalence) podle polarity signálu S/O. Dvojkový doplněk vytvoříme až přímo na sčítačce zavedením nenulového počátečního přenosu pro operaci odčítání. Na obr.1.71 je výsledné zapojení sčítačky a odčítačky pracující s čísly ve vyjádření dvojkovým doplňkem. V závislosti na signálu S/0 se na výstupech osmi obvodů EX-OR objeví číslo Y (případ sčítání) nebo jeho jednotkový doplněk (případ odčítání). Y

8 8 U1 U3A Y0

U4A

1

Y4 3

1 3

K0

2

2 74ALS86 U3B

Y1

74ALS86 U4B

4

Y5 6

4 6

K1

5

9

Y6

K5

K6

YZ 12 11

K3

13

KZ

13 74ALS86

S4 S5 S6 SZ

C0

C4

9

U2 8

74ALS86 U4D 11

4 1 13 10

74ALS283

10

12

S0 S1 S2 S3

B0 B1 B2 B3

9

74ALS86 U3D

X

6 2 15 11 7

K2

10

S/O

K4 K5 K6 KZ

A0 A1 A2 A3

74ALS86 U4C 8

Y3

5 3 14 12

5 74ALS86 U3C

Y2

K4

X4 X5 X6 XZ

S

X0 X1 X2 X3

5 3 14 12

K0 K1 K2 K3

6 2 15 11

A0 A1 A2 A3

8

4 1 13 10

SO S1 S2 S3

B0 B1 B2 B3

7

74ALS86

S0 S1 S2 S3

C0

C4

9

74ALS283 U5B U6A XZ

3

4

1 2 13

U5C 74ALS04

5

6

9

Obr.3.6

7

510 U7A

3 4 5 8

U5A

1

U6B

U5D

VCC

74ALS10

YZ 74ALS04

R1

12

3

1

2

D1 LED

2 6 74ALS00

74ALS04

74ALS10

74ALS04


3. Násobení Paralelní násobičku lze realizovat kombinačním obvodem, který modeluje operaci násobení A a 3 a 2 a1 a 0 stejně, jako se provádí násobení tužkou na xB b 2 b1 b0 papíře. Aritmetický součin dvou bitů je nahrazen 1 p 3 p2 p1 p0 součinem logickým, který má v tomto případě 2 c4 q 3 q 2 q 1 q 0 stejné vlastnosti, součty jednotlivých c4 h 3 h 2 h1 h 0 mezivýsledků provedeme binárními sčítačkami. n 6 n 5 n4 n 3 n 2 n 1 n 0 Řešení takového obvodu si ukážeme na příkladu Obr.3.7 součinu čtyřbitového čísla A a tříbitového čísla B obr.3.7. Součiny pi, qi a hi jsou realizovány logickými členy AND a součty ve shodě s obr.3.7 jsou realizovány sčítačkami 74LS283A.

b0 U1A

U1B

1

U1C

4 3 p3

12

6 p2

2

8 p1

5

74LS08

U1D

9

11 p0

10 74LS08

13

74LS08

74LS08

b1 U2A

U2B

1

U2C

4 3 g3

12

6 q2

2

8 q1

5

74LS08

U2D

9

11 q0

10

74LS08

13

74LS08

74LS08

b2 U3A

U3B

1

12

6 h2

8 h1

5

74LS08

11 h0

10 74LS08

13 74LS08

a2

a3

U3D

9

3 h3 2

B

U3C

4

74LS08

a1

a0

A n n01

p0 U4 p1 p2 p3

5 3 14 12

q0 q1 q2 q3

6 2 15 11 7

A0 A1 A2 A3

S0 S1 S2 S3

5 3 14 12

c4

B0 B1 B2 B3 C0

U5

4 1 13 10 h0 h1 h2 h3

C4

6 2 15 11

9 7

A0 A1 A2 A3

S0 S1 S2 S3

4 1 13 10

n2 n3 n4 n5

9

n6

B0 B1 B2 B3 C0

C4

74LS283 74LS283

Obr.3.8

Na obr.3.8 je zobrazena výsledná realizace násobičky.

8


Uvedeným způsobem lze realizovat násobičku pro dvojková čísla s neomezeným počtem platných míst, složitost obvodu však rychle vzrůstá. Poněkud příznivější situace nastává při použití pamětí ROM a sčítaček. Násobená čísla A a B (např. čtyřbitová) vyjadříme takto 3

( 3.22 )

A = ∑ ai .2i = (a3 a2 a1a0 ) = (a3 a2 00) + (00a1a0 ) i =0

3

( 3.23 )

B = ∑ bi .2 i = (b3b2 b1b0 ) = (b3b2 00) + (00b1b0 ) i =0

kde + nyní značí algebraický součet. Výsledný součin N čísel A a B je dán vztahem

a0 a1 b0 b1

a0 a1 b2 b3

N = (n7 n6 n5 n4 n3 n2 n1n0 ) = ( p3 p2 p1 p0 ) + ( g 3 g 2 g1 g 0 00) +

( 3.24 )

+ (h3 h2 h1 h0 00 ) + (r3 r2 r1r0 0000 )

( 3.25 )

ROM Y0 Y1 Y2 Y3

A3 A2 A1 A0

ROM A3 A2 A1 A0

Y0 Y1 Y2 Y3

p0 p1 p2 p3

g0 g1 g2 g3

6 2 15 11 7

a2 a3 b0 b1

A3 A2 A1 A0

A0 A1 A2 A3

S0 S1 S2 S3

Y0 Y1 Y2 Y3

h0 h1 h2 h3

4 1 13 10

B0 B1 B2 B3 C0

Adresa 0000 0004 0008 000C

C4

9

5 3 14 12 6 2 15 11 7

a2 a3 b2 b3

A3 A2 A1 A0

A0 A1 A2 A3

S0 S1 S2 S3

Y0 Y1 Y2 Y3

00 01 02 03

00 02 04 06

C0

n2 n3

U3 C4

9

5 3 14 12 6 2 15 11

r0 r1 r2 r3

7

Obr.3.9

kde

p 3p 2 p1p 0 = (a 1a 0 ) x( b1b 0 ) ,

00 03 06 09

4 1 13 10

B0 B1 B2 B3

74LS283

ROM

00 00 00 00

U2

74LS283

ROM

Obsah ROM

U1 5 3 14 12

n0 n1

A0 A1 A2 A3

S0 S1 S2 S3

4 1 13 10

B0 B1 B2 B3 C0

C4

9

74LS283

g 3g 2g1g 0 = (a 1a 0 )x( b 3b 2 ) ,

h 3h 2 h1h 0 = (a 3a 2 ) x( b1b0 ) ,

r3r2 r1r0 = ( a 3a 2 ) x( b 3b 2 ) . Dílčí mezivýsledky ( součiny ) p3p2p1p0, g3g2g1g0, h3h2h1h0,

r3r2r1r0 budou uloženy v pamětech ROM, které budou adresovány vstupními proměnnými (a1a 0 ) nebo (a 3a 2 ) a (b1b 0 ) nebo ( b3b 2 ) . Součet čtyř nebo více 9


n4 n5 n6 n7

mezivýsledků vůči sobě vzájemně posunutých provádíme pomocí sčítaček. K tomuto řešení je třeba poznamenat, že stejným způsobem můžeme postupovat při programování násobení čísel v jazyce symbolických adres jejichž délka přesahuje rozsah operandů násobičky integrované v procesorové jednotce.

4. Porovnání čísel Porovnání čísel je velmi častou operací v číslicové technice a tomu odpovídá i množství vyráběných integrovaných obvodů v různých variantách. Tyto obvody se používají v synchronizačních (spouštěcích) obvodech logických analyzátorů, kde zjišťují shodu mezi předem nastavenou hodnotou a vstupními signály. Často se používají místo adresových dekodérů v mikroprocesorových systémech, zvláště potřebujeme-li vytvořit jenom jeden aktivační signál, atd. Porovnávací obvody můžeme rozdělit na obvody určující rovnost nebo nerovnost vstupních proměnných (logické porovnání) nebo dvojkových čísel (aritmetické porovnání), kdy jeden bit porovnávaných čísel má funkci znaménka. Při realizaci obvodu logického porovnání můžeme vycházet přímo z pravdivostní tabulky.

Příklad 2 Navrhněte logický kombinační obvod realizující všechny funkce f1 až f6 pro porovnání dvou dvoubitových čísel pomocí logických členů NAND. a1 a0 b1 b0

0 0 0 0 0 0 0 0

0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

f 3 f 4 f5 f6

0 0 0 0 1 0 0 0

1 0 0 0 1 1 0 0

0 1 1 1 0 0 1 1

1 1 1 1 0 1 1 1

a1 a0 b1 b0

1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1

Tabulka 3.2

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

f 3 f 4 f5 f6

1 1 0 0 1 1 1 0

1 1 1 0 1 1 1 1

0 0 0 1 0 0 0 0

0 0 1 1 0 0 0 1

Nejprve vytvoříme pravdivostní tabulku pro funkce f3, f4, f5, a f6 tab.3.2. Z Karnaughových map, které si pro funkce f3, f4, f5, a f6 napíšeme zjistíme, že pro realizaci logickými členy NAND jsou jednodušší funkce f3 a f5. Pro

dané funkce odvodíme tyto výrazy

10


f 3 = a1 .b1 + a0 .b0 .b1 + a1 .a0 .b0 = a1 .b1 + a0 .b0 .(a1 + b1 )

( 3.25 )

f 5 = a1 .b1 + a0 .b0 .b1 + a1 .a0 .b0 = a1 .b1 + a0 .b0 .(a1 + b1 )

( 3.26 )

Na obr.3.10 je zobrazeno konkrétní zapojení porovnávacího obvodu pro dvě dvoubitová čísla A a B. Pro funkce f3 a f5 můžeme psát f 3 = ( A > B ) = (a1 > b1 ) ∪ (a0 = b0 )( . a0 > b0 )

( 3.27 )

f 5 = ( A < B ) = (a1 < b1 ) ∪ (a0 = b0 )( . a0 < b0 )

( 3.28 )

Logické výrazy v rovnicích (3.27) a (3.28) můžeme nyní nahradit boolovskými výrazy které vyjadřují ptatnost zapsaných podmínek

(a

k

> bk ) = ak .bk ,

(a k

(a

k

= bk ) = ak ⊕ bk

( 3.29 )

≥ bk ) = ak + bk

Dosadíme-li výrazy ze vztahu (3.29) do rovnic (3.27) a (3.28 ), potom s pomocí minimalizační metody konsensu získáme tyto závěrečné vztahy f 3 = a1 .b1 + (a1 .b1 + a1 .b1 ).a0 .b0 = a1 .b1 + a0 .b0 .(a1 + b1 )

( 3.30 )

f 5 = a1 .b1 + (a1 .b1 + a1 .b1 ).a0 .b0 = a1 .b1 + a0 .b0 .(a1 + b1 )

( 3.31 )

Porovnáním rovnic (3.25), (3.30) a (3.26) a (3.31) vidíme, že jsou stejné. V současné době již při realizaci porovnávacího obvodu použijeme některý z vyráběných integrovaných obvodů. Některé obvody jsou vybaveny vstupy (P=Q, PQ) pro kaskádní řazení obvodů. Kaskádní řazení však bude vykazovat stejné nevýhody, s kterými jsme se již seznámili při sčítání čísel. Potřebujeme-li porovnání vyhodnotit v kratší době než umožňuje kaskádní řazení, můžeme přistoupit k dvoustupňové realizaci porovnávacího obvodu.

11


U3A U1A

b1

1

a1

2

U1C 3

8 10 U2A

74ALS00

3 4 5

a0 b0

74ALS04

74ALS00

f5

U4A

6

1 3

f2

4

f1

6

f6

2 74ALS10 U2B 1 2 12 13

b0 a0 U1B

b1 a1

f4

2

1

9

3 U1D

74ALS10

4

74ALS00 U3B

74ALS04 U3C

12

6

11

5

13

5

74ALS00

74ALS00

74ALS04

Obr.3.10

f3

U1

a 20 a 21 a 22 a 23 b20 b21 b22 b23 b19 a 19

10 12 13 15 9 11 14 1 2 3 4

A0 A1 A2 A3 B0 B1 B2 B3 AB

U4 . .

AB

7 6 5

74ACT85 . . . U2

a5 a6 a7 a8 b5 b6 b7 b8 b4 a4

10 12 13 15 9 11 14 1 2 3 4

A0 A1 A2 A3 B0 B1 B2 B3 AB

. .

10 12 13 15 9 11 14 1 2 3 4

A0 A1 A2 A3 B0 B1 B2 B3 AB

AB

7 6 5

AB

74ACT85

AB

7 6 5

74ACT85 U3

a0 a1 a2 a3 b0 b1 b2 b3

10 12 13 15 9 11 14 1 2 3 4

A0 A1 A2 A3 B0 B1 B2 B3 AB 74ACT85

VCC

AB

7 6 5

R1 4k7

Obr.3.11

Ve druhém stupni obvodu budeme porovnávat dílčí části obou čísel např. v jednom obvodu nejnižší čtyři bity ( a 3 a 2 a1a 0 ) a ( b 3 b 2 b1 b 0 ), v druhém obvodu další čtyři bity ( a7 a6a 5a 4 ) a ( b 7 b 6 b 5 b 4 ), atd. V prvém stupni obvodu potom vyhodnotíme porovnání dílčích výsledků ze stupně druhého. Na obr. 3.11 je zobrazena ukázka dvoustupňové realizace 24-bitového porovnávacího obvodu. V případě aritmetického porovnávání čísel musíme do výstupních funkcí zabudovat vliv znamének obou vstupních čísel. Jedná-li se o čísla vyjádřená v dvojkovém doplňku, můžeme použít porovnávací obvody AS885 nebo

AS866, které realizují aritmerické i logické porovnání.

12


Obvod OK LS85 ALS518 ALS522 LS683 ALS519

ALS520 LS682 ALS521 LS684 LS686 ALS688 AS885 AS866

LS685 LS687 ALS689

P=Q Ano Ano Ne Ne Ano Ne Ne Ne Ne Ne Ano

Výstupy P=Q P>Q P>Q Ne Ano Ne Ne Ne Ne Ano Ne Ne Ano Ne Ano Ne Ne Ne Ano Ne Ne Ano Ne Ano Ano Ne Ano Ano Ne Ne Ne Ano Ne Ne Ano Ne

P
Aktivace výstupu

Poznámka

Ne Ano Ano Ne Ano Ano Ne Ano Ano Ano

Logic Logic Logic Logic Logic Logic Logic Logic Logic Reg. P Reg.P i Q

Tabulka 3

Příklad 3 Navrhníte obvod realizující funkci AB pro devítibitová čísla se znaménkem ve formátu ±A a8 0

b8 0

0 1 1

1 0 1

A≥B

A ≥ B 1 0 A ≤ B

Pro výslednou funkci AB můžeme psát pravdivostní tabulku 3.4, kde A aB jsou absolutní hodnoty čísel A a B vyjádřené bity 0 až 7. Funkce A ≥ B a A ≤ B můžeme vyjádřit vztahy

Tabulka 3.4

A ≥ B = ( A > B )∪ ( A = B )

( 3.32 )

A ≤ B = ( A < B )∪ ( A = B )

( 3.33 )

Pro výslednou funkci můžeme za pomoci rovnic (3.22) a (3.33) psát tento logický výraz A ≥ B = a8 .b8 .[( A > B ) + ( A = B )] +

( 3.34 )

+ a8 .b8 .[( A < B ) + ( A = B )] + a8 .b8 =

= a8 .b8 .( A > B )( . A = B ) + a8 .b8 .( A > B ) + a8 .b8 , který realizuje obvod z obr.3.12.

13


Mimo aplikací v kterých se obě porovnávaná čísla mohou měnit (synchronizační obvody), existují aplikace porovnávající vstupní data s pevnou neměnnou hodnotou, jako jsou komparátory nebo adresové dekodéry. V těchto případech můžeme vyjma popsaných obvodů a již zmíU1 U2A 2 19 1 a0 P0 P=Q něných adresových 4 3 a1 P1 a2 2 6 1 P2 P>Q dekodérů AS138, 8 a3 P3 11 a4 74ACT00 P4 AS139, atd. použít spe13 a5 P5 15 a6 P6 U3 cializované obvody 17 a7 P7 6 7 A>B I10 Y1 určené k tomuto účelu. 3 5 b0 Q0 I11 5 4 b1 Q1 I12 7 3 Jednu skupinu tvoří b2 Q2 I13 9 b3 Q3 R1 12 10 9 b4 programovatelné komQ4 I20 Y2 14 11 b5 4k7 Q5 I21 16 12 b6 parátory tab.3.5, Q6 I22 18 13 b7 Q7 I23 VCC u nichž je hodnota Q 14 74ACT682 A 2 b8 před použitím obvodu B 1 G1 15 a8 naprogramována na G2 zvolenou hodnotu. 74ACT153 Obr.3.12 Druhou skupinu tvoří adresové komparátory ALS677, ALS678 (16 adres) a ALS679, ALS680 (12 adres), jejichž vstupy P3, P2, P1 a P0 Obvod Výstup Bitů Vstupy určují binární Programovatelné Normální počet ALS526 16 Č ísla Q Č ísla P nulových P=Q ALS528 12 Čísla Q Čísla P spodních P=Q adresovacích ALS527 8 Čísla Q Čísla P P=Q vodičů. 4 Čísla P i Q P=Q Budou-li Tabulka 3.5 zároveň zbývající adresové vodiče v log.1 a bude platný aktivační signál, bude výstup v aktivní úrovni log.0.

Příklad 4

Navrhněte adresový dekodér pro aktivaci vstupních portů s adresami C00CH, C00DH, C00EH a C00FH v adresovém prostoru datové paměti procesoru 8051.

Přímo adresovatelný prostor procesoru 8051 je 64kB a tudíž adresová sběrnice má 16 adresovacích vodičů A0 až A15. Datová paměť je ovládána řídícími signály RD (pro čtení) a WR (pro zápis). Z požadovaných adres vstupních portů vyplývá, že adresové vodiče musí nabývat hodnot 14


A15 A14 A13 A12 A11 A10 A9 A8 A7A6 A5 A4 A3 A2 A1 A0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 X X

U2A A0 A1

2 3

A B

1

G

Y0 Y1 Y2 Y3

4 5 6 7

74ALS139 U1

A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A2 A3 A14 A15

1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17

RD

18 19 20 21 23

A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 A16 P0 P1 P2 P3 G

Y

22

74LS677

C00CH C00DH C00EH C00FH

kde X značí log.1 nebo log.0. Neměnné hodnoty pro všechny porty jsou na adresových vodičích A2 až A15 a proto je budeme dekódovat adresovým komparátorem. K 10 nulovým adresovým vodičům přidáme ještě 2 nevyužité vstupy adresového komparátoru a připojíme je na jeho spodní adresové vodiče. Protože předpokládáme 12 nulových vstupních hodnot, připojíme na vstupy P3,P2,P1,P0 hodnotu 1100 (12). K vytvoření 4 aktivačních signálů od sebe odlišených adresovými vodiči A1 a A0 provedeme pomocí dekodéru 1 ze 4 typu 74ALS139 obr.3.13.

R1 VCC 4k7

Obr.3.13

5. Převodníky BIN-BCD a BCD-BIN Často používanou operací v číslicové technice je převod BCD-BIN čísla v BCD kódu na číslo binární (číslo ve dvojkové soustavě) a převod BIN-BCD čísla binárního na číslo v BCD kódu. Převod BCD-BIN, který se realizuje jednodušeji než převod BIN-BCD, je možné provádět výše popsanými metodami. Tyto metody však nejsou vhodné pro obvodové řešení ani programové řešení na úrovni jazyka symbolických adres, lze je bez obtíží realizovat ve vyšších programovacích jazycích. Postupy, které jsou vhodnější k obvodovému i programovému řešení budeme ilustrovat na dvou příkladech.

15


Příklad 5 Navrhněte převodník čísla 0 až 99 vyjádřeného v BCD kódu na číslo binární. Číslo v kódu BCD můžeme vyjádřit vztahem

(

)

(

N = a13 .2 3 + a12 .2 2 + a11.21 + a10 .10 + a03 .23 + a02 .2 2 + a01.21 + a00

)

( 3.34 )

kde hodnoty (a 13 a 12 a 11a 10 ) a (a 03 a 02 a 01a 00 ) představují desítky a jednotky čísla v BCD kódu a znaménko + představuje aritmetický součet. Nejprve vyjádříme hodnotu 10 jako 23 + 2 a roznásobíme rovnici (3.34). Srovnáním jednotlivých výrazů podle mocnin 2n získáme tento výraz N = a13 .26 + a12 .25 + (a11 + a13 ).2 4 + (a03 + a12 + a10 ).23 +

( 3.35 )

+(a11 + a02 ).22 + (a10 + a01 ).21 + a00

Na obr.3.14 je nakresleno výsledné zapojení obvodu, za použití čtyřbitových sčítaček typu 74LS283. Jednou z často používaných operací v číslicové technice je převod binárního čísla na číslo v desítkové soustavě, ve které bude každá cifra vyjádřena v BCD kódu. S takovým převodem se setkáváme všude, kde naměřenou a zpracovanou hodnotu bude potřeba zobrazit na displeji přístroje. Převod binárního čísla do desítkové soustavy je možné provádět třemi metodami: a00

n0 U1

a01 a02 a03 a11 a10 a12 a13

5 3 14 12 6 2 15 11 7

A0 A1 A2 A3

S0 S1 S2 S3

74LS283

C4

U2 5 3 14 12

B0 B1 B2 B3 C0

n1 n2

4 1 13 10

9

6 2 15 11 7

Obr.3.14

A0 A1 A2 A3

S0 S1 S2 S3

4 1 13 10

n3 n4 n5 n6

B0 B1 B2 B3 C0

C4

9

74LS283

a) postupným odečítáním mocnin základu, která je vhodná pro programové řešení b) postupného dělení základem, která je vhodná pro programové řešení, při kterém máme k dispozici operaci dělení 16


c) metodou využívající princip dekadické korekce

Poslední jmenovaná metoda je vhodná pro programové i obvodové řešení, které je možné realizovat jak sekvenčním tak i kombinačním obvodem. Každé binární číslo N můžeme vyjádřit vztahem N = an .2 n + a n −1 .2 n −1 + a n − 2 .2 n − 2 + ... + a1 .21 + a0

( 3.36 )

který snadno upravíme do tvaru N = (...((a n .2 + a n −1 ).2 + a n − 2 ).2 + ... + a1 ).2 + a0

( 3.37 )

Z rovnice (3.37) vyplývá, že číslo N můžeme vytvořit postupnou sekvencí skládající se z násobení dvěma a přičtení dalšího koeficientu, který je roven 0 nebo 1. Jak vyplývá z vlastností dekadické korekce je jasné, že bude-li mezivýsledek násobený dvě ma dekadické číslo, pak po jeho vynásobení a přičtení dalšího koeficientu je možné realizovat dekadickou korekci, která výsledek opět převede na dekadické číslo. Situace je analogická s realizací součtu dvou stejných BCD čísel s přenosem.

Příklad 6 Převeďte číslo 00110100 na číslo dekadické v BCD kódu.

a6

0

0

0

0

0

0

0

0

Počáteční stav

a5

0 0

0 0

0 0

0 0

0 0

0 0

0 0

1 1

1.krok a 6 .2 + a 5 dekadická korekce

a4

0 0

0 0

0 0

0 0

0 0

0 0

1 1

1 1

2.krok (a 6 .2 + a 5 ).2 + a 4 dekadická korekce

a3

0 0

0 0

0 0

0 0

0 0

1 1

1 1

0 0

3.krok (........).2 + a 3 dekadická korekce

a2

0 0

0 0

0 0

0 1

1 0

1 0

0 1

1 1

4.krok (............).2 + a 2 dekadická korekce

a1

17


0 0

1 1

0 0

0 0

0 0

1 1

1 1

0 0

5.krok (............).2 + a 1 dekadická korekce

a0

0 0

1 1

0 0 5

0 1

1 0

1 0

0 1 2

0 0

6.krok (............).2 + a 0 dekadická korekce Výsledek

Tabulka 3.6

Algoritmus popsaný tabulkou 3.6 lze nejsnáze realizovat pomocí programu v jazyce symbolických adres pro příslušný mikroprocesor nebo pomocí kaskády sekvenčních obvodů, které modelují operace prováděné v jedné dekádě (dekadickou korekci + násobení dvěma). Obvod lze realizovat i paralelní strukturou vytvořenou z obvodů realizujících operaci v jedné dekádě a trojúhelníkově se rozšiřující v závislosti na počtu nutných kroků a délce převedeného čísla viz. tab.3.6. V následující části textu shrnujeme možnosti programové realizace bitových operací prostřednictvím programů v jazyce Python. Jednotlivé aritmetické operace realizujeme pomocí řetězců, kde každá pozice odpovídá jednomu bitu. Tím každý prvek řetězce nabývá hodnoty jedna či nula. Předtím, než probereme jednotlivé operace, vytvoříme některé pomocné programy. Tě mi jsou programy pro převod mezi dekadickou a binární soustavou a opačný převod mezi těmito soustavami. Program pro převod mezi dvěma soustavami print "program pro prevod dekadickeho cisla na binarni " vysl=" " cislo =int(raw_input("zadej cislo pro prevod:")) pom =cislo while pom <>1: x="0" pom=cislo/2 zbytek =cislo-pom*2 if zbytek==1 : x="1" vysl=x+vysl cislo =pom vysl= "1" +vysl print vysl print "program pro prevod binarniho cisla na dekadicke " a="00010111" suma =0 k=1 for i in range(7,-1,-1): if a[i]=="1":suma =suma +k k=k*2 print suma

18


Program pro součet dvou binárních čísel print "program pro vypocet souctu dvou binarnich cisel " x="10100110" y="01110101" v="" p=0 for i in range (7,-1,-1): if x[i]=="1" and y[i]=="1" and not p: z= "0" p=1 elif x[i]=="1" and y[i]=="0" and not p: z= "1" p=0 elif x[i]=="0" and y[i]=="1" and not p: z= "1" p=0 elif x[i]=="1" and y[i]=="1" and p: z= "1" p=1 elif x[i]=="1" and y[i]=="0" and p: z= "0" p=1 elif x[i]=="0" and y[i]=="1" and p: z= "0" p=1 elif x[i]=="0" and y[i]=="0" and p: z= "1" p=0 elif x[i]=="0" and y[i]=="0" and not p: z="0" p=0 v=z+v print x print y print v

součet v binární soustavě

0+0=0 přenos do vyššího řádu 0 1+0=1 přenos do vyššího řádu 0 1+1=0 přenos do vyššího řádu 1 Rozšíření předchozího případu o přenos z nižšího řádu : 0+0+0=0 0+0+1=1 0+1+1=0 1+1+1=1

19

přenos 0 přenos 1 přenos 1 přenos 1


Poznámka: platí zde zákony komutativní a asociativní. V následující tabulce jsou všechny možnosti. Tabulka má celkem 2**3 řádků : Tabulka – sčítání ve dvojkové soustavě

Vstupní hodnoty

Vysledek součtu

Přenos

0

0

0

0

0

0

0

1

1

0

0

1

0

1

0

0

1

1

0

1

1

0

0

1

0

1

0

1

0

1

1

1

0

0

1

1

1

1

1

1

Popis problému:

Při psaní programu s výhodou použiji možnosti logických operací v podmínce operátor and . a not.( and logický součin a not negace podmínky) Pro hodnotu přenosu zavedu proměnou tytu boolean, která má hodnotu true, pokud je nenulová. Ve všech ostatních případech má hodnotu false V dalším textu uvádím postup pro realizaci prvních dvou řádků výše uvedené tabulky. Řetězec x obsahuje jednu vstupní proměnou, řetězec y obsahuje druhou vstupní proměnnou a p obsahuje číselnou hodnou přenosu z nižšího řádu. Vždy musíme řetězce zpracovávat po jednotlivých bitech. Operace se musí provádět od nejnižších bitů. Abychom vybrali určitou pozici ( i - tou) používáme v cyklu zápis řetězce x[i] a y[i]. Hodnota z obsahuje příslušný bit výstupního řetězce. Zápis:

if x [i] == “0” and y[i] and not p: z =“0“ p=0 elif x[i]==“0“ and y[i] and p: 20


z =“1“ p=1 Veškeré bity výstupního řetězce z se načítají do řetězce v pomocí skládání řetězců (operátor +) směrem zleva po každém průchodu cyklem.. v je na počátku deklarováno jako prázdný řetězec. Příkazem v =““ v=v+z

Dalším možným problémem je úprava obou operandů na řetězec stejné délky. Aritmetiku budeme demonstrovat na délce 8: To provedeme následujícím způsobem: 1. pomocí funkce len zjistíme délku vstupního řetězce znaků 2. spustíme cyklus s parametrem range (8-len(a) 3. v tomto cyklu přidávám zprava znaky nula. Program: print "program pro doplnění řetězce bin. čísel na délku 8" a=raw_input("retezec:") x="0" for i in range (8-len(a)): a=x+a print a

Program pro výpočet rozdílu dvou binárních čísel.

Postupujeme naprosto obdobně. print "program pro vypocet rozdilu binarnich cisel " b=raw_input("zadej cslo ve tvaru retezec ") a=raw_input("zadej druhe cilo ve tvaru retezec ") v="" p=0 for i in range (7,-1,-1): if a[i]=="0" and b[i]=="0" and not p : p=0 x="0" elif a[i]=="1" and b[i]=="0" and not p: p=1 x="1" elif a[i]=="0" and b[i]=="1" and not p: p=0 x="1" elif a[i]=="1" and b[i]=="1" and not p: p=0 x="0" elif a[i]=="1" and b[i]=="1" and p: p=1 x="1" elif a[i]=="0" and b[i]=="1" and p: p=0 x="0"

21


elif a[i]=="1" and b[i]=="0" and p: p=1 x="0" elif a[i]=="0" and b[i]=="0" and p: p=1 x="1" v=x+v print print print print

"rozdil cisel: " b a v

Poznámka: Vstupní řetězce musíme zadávat v délce 8 znaků.

Existuje i druhá možnost jak postupovat: Rozdíl převedeme na přičítání dvojkového doplňku. V tomto případě nejprve napíšeme program pro výpočet 1.doplňku (prostá negace). Program: print "program pro vypocet negace cisel " a="10101000" b="" for i in range (8): if a[i]=="1":pom="0" if a[i]=="0":pom="1" b=b+pom print a print b

Poznámka: řetězec a obsahuje vstupní řetězec. Řetězec b obsahuje výstupní řetězec.

Jako další krok přičteme aritmeticky 1 k takto získanému řetězci (tj. vytvoříme druhý doplněk). Pak provedeme výpočet rozdílu jako přičtení dvojkového doplňku. Doporučujeme program realizovat pomocí funkce, kterou můžeme v programu volat dvakrát: Poprvé pro přičtení 1 (pro vytvoření 2. doplňku z negovaného menšitele) a podruhé pro přičtení takto vytvořeného doplňku k menšenci. Funkční program pro součet dvou dekackých čísel pomocí převodu do binární soustavy, aritmetického součtu v binární soustavě a převedení výsledku do dekadické soustavy. print "program pro prevod dekadickeho cisla na binarni " vysl="" cislo =int(raw_input("zadej 1.cislo pro soucet:")) pom =cislo while pom <>1: x="0" pom=cislo/2

22


zbytek =cislo-pom*2 if zbytek==1 : x="1" vysl=x+vysl cislo =pom vysl= "1" +vysl print "program pro prevod dekadickeho cisla na binarni " vysl1="" cislo =int(raw_input("zadej 2.cislo pro soucet:")) pom =cislo while pom <>1: x="0" pom=cislo/2 zbytek =cislo-pom*2 if zbytek==1 : x="1" vysl1=x+vysl1 cislo =pom vysl1= "1" +vysl1 print "program pro doplnění řetězce bin. čísel na délku 8" a=vysl x="0" for i in range (8-len(a)): a=x+a print "program pro doplnění řetězce bin. čísel na délku 8" b=vysl1 x="0" for i in range (8-len(b)): b=x+b def secti (u,w): x=u y=w v="" p=0 for i in range (7,-1,-1): if x[i]=="1" and y[i]=="1" and z= "0" p=1 elif x[i]=="1" and z= "1" p=0 elif

not p:

y[i]=="0" and not p:

x[i]=="0" and y[i]=="1" and not p: z= "1" p=0

elif x[i]=="1" and y[i]=="1" and p: z= "1" p=1 elif x[i]=="1" and z= "0" p=1 elif

23

y[i]=="0" and p:

x[i]=="0" and y[i]=="1" and p: z= "0" p=1


elif

x[i]=="0" and z= "1" p=0

y[i]=="0" and p:

elif

x[i]=="0" and z="0" p=0


v=z+v return(v) print " vstupni binarni cisla : ",a,b c=secti(a,b) print" vysledek binarniho souctu : " ,c print "program pro prevod binarniho cisla na dekadicke " a=c suma =0 k=1 for i in range(7,-1,-1): if a[i]=="1":suma =suma +k k=k*2 print " vysledek v dekadicke soustave ",suma

Výsledek běhu programu: Python 2.5.2 (r252:60911, Feb 21 2008, 13:11:45) [MSC v.1310 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. **************************************************************** Personal firewall software may warn about the connection IDLE makes to its subprocess using this computer's internal loopback interface. This connection is not visible on any external interface and no data is sent to or received from the Internet. **************************************************************** IDLE 1.2.2 >>> ============================== RESTART ================================ program pro prevod dekadickeho cisla na binarni zadej 1.cislo pro soucet:12 program pro prevod dekadickeho cisla na binarni zadej 2.cislo pro soucet:5 program pro doplnění řetězce bin. čísel na délku 8 program pro doplnění řetězce bin. čísel na délku 8 vstupni binarni cisla : 00001100 00000101 vysledek binarniho souctu : 00010001 program pro prevod binarniho cisla na dekadicke vysledek v dekadicke soustave 17 >>>

24


Funkční program pro rozdíl dvou dekadických čísel (opět převod dekadického čísla do binární soustavy, výpočet druhého doplňku menšitele, přičtení druhého doplňku k menšenci a výsledek převést do dekadické soustavy): print "program pro prevod dekadickeho cisla na binarni " vysl="" cislo =int(raw_input("zadej 1.cislo pro rozdil:")) pom =cislo while pom <>1: x="0" pom=cislo/2 zbytek =cislo-pom*2 if zbytek==1 : x="1" vysl=x+vysl cislo =pom vysl= "1" +vysl print "program pro prevod dekadickeho cisla na binarni " vysl1="" cislo =int(raw_input("zadej 2.cislo pro rozdil:")) pom =cislo while pom <>1: x="0" pom=cislo/2 zbytek =cislo-pom*2 if zbytek==1 : x="1" vysl1=x+vysl1 cislo =pom vysl1= "1" +vysl1 print "program pro doplnění řetězce bin. čísel na délku 8" a=vysl x="0" for i in range (8-len(a)): a=x+a vysl=a print "program pro doplnění řetězce bin. čísel na délku 8" b=vysl1 x="0" for i in range (8-len(b)): b=x+b print "program pro vypocet negace cisel " a=b b="" for i in range (8): if a[i]=="1":pom="0" if a[i]=="0":pom="1" b=b+pom vysl1=b print " kontrola = vypocet negace " print a print vysl1 print def secti (u,w): x=u y=w

25


v="" p=0 for i in range (7,-1,-1): if x[i]=="1" and y[i]=="1" and z= "0" p=1 elif x[i]=="1" and z= "1" p=0 elif

not p:



elif x[i]=="1" and y[i]=="1" and p: z= "1" p=1 elif x[i]=="1" and z= "0" p=1

y[i]=="0" and p:

elif

x[i]=="0" and y[i]=="1" and p: z= "0" p=1

elif

x[i]=="0" and z= "1" p=0

y[i]=="0" and p:

elif

x[i]=="0" and z="0" p=0


v=z+v return(v) c=secti(vysl1,"00000001") print " kontrola souctu - vytvoření 2. doplnku" print vysl1 print "00000001" print c print d=secti(vysl,c) print " kontrola souctu - provedeni rozdilu dvou binarnich cisel" print vysl1 print c print d print" vysledek binarniho rozdilu : " ,d print print "program pro prevod binarniho cisla na dekadicke " a=d suma =0 k=1 for i in range(7,-1,-1): if a[i]=="1":suma =suma +k k=k*2 print " vysledek v dekadicke soustave ",suma

26


Výsledek běhu programu: Python 2.5.2 (r252:60911, Feb 21 2008, 13:11:45) [MSC v.1310 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. **************************************************************** Personal firewall software may warn about the connection IDLE makes to its subprocess using this computer's internal loopback interface. This connection is not visible on any external interface and no data is sent to or received from the Internet. **************************************************************** IDLE 1.2.2 >>> ============================== RESTART ================================ >>> program pro prevod dekadickeho cisla na binarni zadej 1.cislo pro rozdil:12 program pro prevod dekadickeho cisla na binarni zadej 2.cislo pro rozdil:5 program pro doplnění řetězce bin. čísel na délku 8 program pro doplnění řetězce bin. čísel na délku 8 program pro vypocet negace cisel kontrola = vypocet negace 00000101 11111010 kontrola souctu - vytvoření 2. doplnku 11111010 00000001 11111011 kontrola souctu - provedeni rozdilu dvou binarnich cisel 11111010 11111011 00000111 vysledek binarniho rozdilu : 00000111 program pro prevod binarniho cisla na dekadicke vysledek v dekadicke soustave 7 >>>

Práce s inverzním kódem

Inverzní kód pracuje na bázi tzv. prvního doplňku (záporná čísla se vytváří pouze inverzí všech bitů a následně, pokud vznikl kruhový přenos tj. stav, kdy je přenos z nejvyššího významového bitu, se provede znovu výpočet s aritmetickým přičtením jednotky do nejnižšího bitu. Příklad: 5-3

5 = 00000101 3= 00000011 27


1. doplněk 3 = 11111100 soucet: 00000101 11111100 00000001 Poznámka: vznikl kruhový přenos to znamená nové sčítání: 00000001 00000001 00000010 Poznámka: kruhový přenos již nevznikl a tak toto je výsledek Abychom mohli výpočet provést, musíme nejprve modifikovat vlastní součet. Zde budeme předávat 2 hodnoty – výsledek jako řetězec a přenos jako řetězec (Příkaz str(p) vytvoří z proměné typu číslo proměnnou typu string) Výpis modifikované funkce pro soucet (soubor soucet.py) def secti (u,w): x=u y=w v="" p=0 for i in range (7,-1,-1): if x[i]=="1" and y[i]=="1" and z= "0" p=1 elif x[i]=="1" and z= "1" p=0 elif

not p:




28

y[i]=="0" and p:

elif

x[i]=="0" and y[i]=="1" and p: z= "0" p=1

elif

x[i]=="0" and z= "1" p=0

y[i]=="0" and p:


elif

x[i]=="0" and z="0" p=0


v=z+v return(v,str(p))

Vyvolání a práce s touto funkcí (soucet dvou kladných čísel): import soucet u="00000101" v="11111100" x=soucet.secti(u,v) print "vysledek ",x[0],"prenos ",x[1] if x[1]=="1": x=soucet.secti(x[0],"00000001") print " celkovy vysledek ",x[0]

Celý program pro odčítání: import soucet u="00001111" v="00000011" print "program pro vypocet negace cisel " a=v b="" for i in range (8): if a[i]=="1":pom="0" if a[i]=="0":pom="1" b=b+pom w=b x=soucet.secti(u,w) print "vysledek ",x[0],"prenos ",x[1] if x[1]=="1": x=soucet.secti(x[0],"00000001") print " celkovy vysledek ",x[0]

Zde je výsledek běhu programu: Python 2.5.2 (r252:60911, Feb 21 2008, 13:11:45) [MSC v.1310 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. **************************************************************** Personal firewall software may warn about the connection IDLE makes to its subprocess using this computer's internal loopback interface. This connection is not visible on any external interface and no data is sent to or received from the Internet. ****************************************************************

29


IDLE 1.2.2 >>> ============================= RESTART ================================ >>> program pro vypocet negace cisel vysledek 00001011 prenos 1 celkovy vysledek 00001100 >>>

Zde je celý program (převedení z dekadické soustavy do binární, výpočet binární operace a zpětné převedení do dekadické soustavy) : print "program pro prevod dekadickeho cisla na binarni " vysl="" cislo =int(raw_input("zadej 1.cislo pro rozdil:")) pom =cislo while pom <>1: x="0" pom=cislo/2 zbytek =cislo-pom*2 if zbytek==1 : x="1" vysl=x+vysl cislo =pom vysl= "1" +vysl print "program pro prevod dekadickeho cisla na binarni " vysl1="" cislo =int(raw_input("zadej 2.cislo pro rozdil:")) pom =cislo while pom <>1: x="0" pom=cislo/2 zbytek =cislo-pom*2 if zbytek==1 : x="1" vysl1=x+vysl1 cislo =pom vysl1= "1" +vysl1 print "program pro doplnění řetězce bin. čísel na délku 8" a=vysl x="0" for i in range (8-len(a)): a=x+a vysl=a print "program pro doplnění řetězce bin. čísel na délku 8" b=vysl1 x="0" for i in range (8-len(b)): b=x+b print "program pro vypocet negace cisel " a=b b="" for i in range (8): if a[i]=="1":pom="0" if a[i]=="0":pom="1" b=b+pom vysl1=b print " kontrola = vypocet negace " print a

30


print vysl1 print import soucet u=vysl v=vysl1 x=soucet.secti(u,v) print "vysledek ",x[0],"prenos ",x[1] if x[1]=="1": x=soucet.secti(x[0],"00000001") print " celkovy vysledek v binarni soustave ",x[0] print d=x[0] print "kontrola vysledku binarnich operaci" print vysl print vysl1 print d print" vysledek binarniho rozdilu : " ,d print print "program pro prevod binarniho cisla na dekadicke " a=d suma =0 k=1 for i in range(7,-1,-1): if a[i]=="1":suma =suma +k k=k*2 print " vysledek v dekadicke soustave ",suma

Zde je výsledek běhu celého programu: Python 2.5.2 (r252:60911, Feb 21 2008, 13:11:45) [MSC v.1310 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. **************************************************************** Personal firewall software may warn about the connection IDLE makes to its subprocess using this computer's internal loopback interface. This connection is not visible on any external interface and no data is sent to or received from the Internet. **************************************************************** IDLE 1.2.2 >>> ============================== RESTART ================================ >>> program pro prevod dekadickeho cisla na binarni zadej 1.cislo pro rozdil:15 program pro prevod dekadickeho cisla na binarni zadej 2.cislo pro rozdil:8 program pro doplnění řetězce bin. čísel na délku 8 program pro doplnění řetězce bin. čísel na délku 8 program pro vypocet negace cisel kontrola = vypocet negace 00001000 11110111 vysledek 00000110 prenos 1 celkovy vysledek v binarni soustave

31

00000111


kontrola vysledku binarnich operaci 00001111 11110111 00000111 vysledek binarniho rozdilu : 00000111 program pro prevod binarniho cisla na dekadicke vysledek v dekadicke soustave 7 >>>

Aritmetické operace:

Základní aritmetickou operací je v počítačích sčítání. Odčítání lze převést na přičítání dvojkového doplňku. Násobení lze převést na přičítání, dělení na odčítání. To pak pomocí přičítání dvojkového doplňku zpět na sčítání. Realizace násobení pomocí sčítání: print "program pro nasobeni pomoci scitani" a=int(raw_input("zadej 1.operand : ")) b=int(raw_input("zadej 2.operand : ")) i=b x=0 while i > 0: x=x+a i=i-1 print "vysledek nasobeni je ",x

Zde je výsledek: Python 2.3.4 (#53, May 25 2004, 21:17:02) [MSC v.1200 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. **************************************************************** Personal firewall software may warn about the connection IDLE makes to its subprocess using this computer's internal loopback interface. This connection is not visible on any external interface and no data is sent to or received from the Internet. **************************************************************** IDLE 1.0.3 >>> ============================== RESTART ================================ >>> program pro nasobeni pomoci sacitani zadej 1.operand : 6 zadej 2.operand : 8 vysledek nasobeni je 48 >>>

Realizace děleni pomoci odčítání: print "program ptro delení pomocí odečítání" a=int(raw_input("zadej delenec : ")) b=int(raw_input("zadej delitel : ")) x=a-((a/b)*b) i=0

32


while a >= x: a=a-b i=i+1 print "vysledek deleni je ",i-1

Zde je výsledek: Python 2.3.4 (#53, May 25 2004, 21:17:02) [MSC v.1200 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. **************************************************************** Personal firewall software may warn about the connection IDLE makes to its subprocess using this computer's internal loopback interface. This connection is not visible on any external interface and no data is sent to or received from the Internet. **************************************************************** IDLE 1.0.3 >>> ============================== RESTART ================================ >>> program ptro delení pomocí odeèítání zadej delenec : 50 zadej delitel : 10 vysledek deleni je 5 >>>

Druha odmocnina print " druha odmocnina " a=int(raw_input(" zadej cislo :")) b=0.0 while ((b**2) < a ): b=b+0.00001 c=round (b,4) print " vysledek .",c

Zde využíváme vlasnosti, že postupně zvyšujeme hodnotu proměnné b od hodnoty nula a vždy testujeme, zda druhá mocnina tohoto čísla je menší. V opačném případě jsme nalezli správné řešení. Samozřejmě, rychlejšího výsledku bychom mohli dosáhnout s použitím Newtonovy metody. Výhoda výše uvedeno algoritmu je však v tom, že lze realizovat s minimálními úpravami i vyšší odmocniny než dvě. Zde je výsledek běhu programu: Python 2.3.4 (#53, May 25 2004, 21:17:02) [MSC v.1200 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. **************************************************************** Personal firewall software may warn about the connection IDLE makes to its subprocess using this computer's internal loopback interface. This connection is not visible on any external interface and no data is sent to or received from the Internet. ****************************************************************

33


IDLE 1.0.3 >>> ============================== RESTART ================================ >>> druha odmocnina zadej cislo :12 vysledek . 3.4641 >>>

Násobení a dělení

Vytvořte programy, které funkci násobení a dělení nahradí funkcemi sčítání resp. odčítání. Sčítání a odčítání realizujte v binární soustavě včetně příslušných převodů mezi dekadickou a binární soustavou. Program pro násobení print "program pro nasobeni " a=int(raw_input("zadej a ")) b=int(raw_input("zadej b ")) zbytek =b vysledek=0 while zbytek >0: zbytek=zbytek-1 vysledek=vysledek+a print vysledek

Zde je výsledek běhu programu: Python 2.5.2 (r252:60911, Feb 21 2008, 13:11:45) [MSC v.1310 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. **************************************************************** Personal firewall software may warn about the connection IDLE makes to its subprocess using this computer's internal loopback interface. This connection is not visible on any external interface and no data is sent to or received from the Internet. **************************************************************** IDLE 1.2.2 >>> ============================== RESTART ================================ >>> program pro nasobeni zadej a 12 zadej b 5 60 >>>

Nyní převedeme již známé části programů na funkce: soubor scitani1.py obsahuje sčítáni v binární soustavě: def secti (u,w): x=u y=w v="" p=0

34


for i in range (7,-1,-1): if x[i]=="1" and y[i]=="1" and z= "0" p=1 elif x[i]=="1" and z= "1" p=0 elif

not p:




y[i]=="0" and p:

elif

x[i]=="0" and y[i]=="1" and p: z= "0" p=1

elif

x[i]=="0" and z= "1" p=0

elif

x[i]=="0" and z="0" p=0 v=z+v return(v)

soubor neg.py obsahuje

negaci

y[i]=="0" and p:


:

def negace(a): b="" for i in range (8): if a[i]=="1":pom="0" if a[i]=="0":pom="1" b=b+pom return(b)

Soubor prevodbin. py převádí do binární soustavy: def prevodbin (cislo): vysl="" pom =cislo c=1 if not pom: c=0 vysl="0" while pom <>1 and c : x="0" pom=cislo/2 zbytek =cislo-pom*2 if zbytek==1 : x="1" vysl=x+vysl

35


cislo =pom if c: vysl= "1" +vysl a=vysl x="0" for i in range (8-len(a)): a=x+a return(a)

Soubor prevoddekadicky obsahuje prevod do dekadicke soustavy ze soustavy binární: def prevoddec(a): suma =0 k=1 for i in range(7,-1,-1): if a[i]=="1":suma =suma +k k=k*2 return(suma)

Soubor odc. py obsahuje odcitani v binární soustave: import scitani1,neg def odcitani(a,b): c=neg.negace(b) d=scitani1.secti(c,"00000001") e=scitani1.secti(d,a) return(e)

Na základě těchto funkcí bylo vytvořeno sčítání dekadických čísel – soubor scitani.dec: import scitani1,neg,prevodbin,prevoddekadicky def scitani(a,b): c=prevodbin.prevodbin(a) d=prevodbin.prevodbin(b) e=scitani1.secti(c,d) f=prevoddekadicky.prevoddec(e) return (f)

pak odčítání soubor odcitani.py: import odc,prevodbin,prevoddekadicky def odcitani (a,b): c=prevodbin.prevodbin(a) d=prevodbin.prevodbin(b) e=odc.odcitani(c,d) f=prevoddekadicky.prevoddec(e) return(f)

36


Na základě těcho funkcí bylo modifikováno a) násobení: print "program pro nasobeni " import scitanidec,odcitanidec a=int(raw_input("zadej a")) b=int(raw_input("zadej b")) pocet=0 zbytek =b vysledek=0 while zbytek >0: pocet=scitanidec.scitani(pocet,1) zbytek=odcitanidec.odcitani(zbytek,1) vysledek=scitanidec.scitani(vysledek,a) print vysledek

Zde je výsledek běhu programu: Python 2.5.2 (r252:60911, Feb 21 2008, 13:11:45) [MSC v.1310 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. **************************************************************** Personal firewall software may warn about the connection IDLE makes to its subprocess using this computer's internal loopback interface. This connection is not visible on any external interface and no data is sent to or received from the Internet. **************************************************************** IDLE 1.2.2 >>> ============================== RESTART ================================ >>> program pro nasobeni zadej a15 zadej b6 90 >>>

a) dělení print "program pro deleni“ a=int(raw_input("zadej a ")) b=int(raw_input("zadej b ")) pocet=0 vysledek=a while vysledek>=b: pocet=pocet+1 vysledek=vysledek-b print pocet

Zde je výsledek běhu programu: Python 2.5.2 (r252:60911, Feb 21 2008, 13:11:45) [MSC v.1310 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information.

37


**************************************************************** Personal firewall software may warn about the connection IDLE makes to its subprocess using this computer's internal loopback interface. This connection is not visible on any external interface and no data is sent to or received from the Internet. **************************************************************** IDLE 1.2.2 >>> ============================== RESTART ================================ >>> program pro deleni zadej a 15 zadej b 4 3 >>>

Modifikovaný program pro práci v binární soustavě: print "program pro deleni " import scitanidec,odcitanidec a=int(raw_input("zadej a ")) b=int(raw_input("zadej b ")) pocet=0 vysledek=a while vysledek>=b: pocet=scitanidec.scitani(pocet,1) vysledek=odcitanidec.odcitani(vysledek,b) print pocet

Výsledek běhu programu: Python 2.5.2 (r252:60911, Feb 21 2008, 13:11:45) [MSC v.1310 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. **************************************************************** Personal firewall software may warn about the connection IDLE makes to its subprocess using this computer's internal loopback interface. This connection is not visible on any external interface and no data is sent to or received from the Internet. **************************************************************** IDLE 1.2.2 >>> ============================== RESTART ================================ >>> program pro deleni zadej a 12 zadej b 6 2 >>>

Závěr: Výše uvedené programy demonstrují možnosti práce v binární soustavě, v doplňkovém a inverzním kódu. Tyto znalosti jsou důležité pro pochopní práce počítače a především pro programování procesorů typu RISC, kde téměř vždy chybí v instrukčním souboru instrukce pro násobení a dělení. 38


Realizace základních matematických operací v počítači

Recommend Documents