Čísla a logika
Číselné vyjádření hodnoty
Au
Kolik váží hrouda zlata ?
Dekadické vážení Když přidám osmé závaží 100g, váha se převáží => závaží zase odeberu a začnu přidávat závaží 10x menší
7 závaží 100g
2 závaží 10g 9 závaží 1g
729g
Binární vážení 1 závaží 512g
0 závaží 256g 1 závaží 128g 1 závaží 64g 0 závaží 32g 1 závaží 16g 1 závaží 8g 0 závaží 4g 0 závaží 2g 1 závaží 1g
Přidám nejtěžší závaží. Pokud je příliš těžké, odeberu ho zpět a zkusím poloviční
1011011001g
Číselné soustavy symbolický zápis hodnoty primitivní: 13 piv = římský zápis čísla 1844 = MDCCCXLIV
1000+500+100+100+100+(50-10)+(5-1)
umožňuje vyjádřit běžné hodnoty složitá pravidla zápisu zcela nevhodný pro matematiku (zkuste vynásobit MDCLXVI x XLIV)
...AB... IF A >= B THEN A + B CI = 100+1 IF A < B THEN A - B IX = -1 + 10
arabský zápis čísla umožňuje vyjádřit libovolně velké hodnoty jednoduchá pravidla zápisu vhodný pro matematické výpočty (zná pojem nuly!)
Polyadické číselné soustavy úplný zápis čísla 729 ve tvaru polynomu:
7*102 + 2*101 + 9*100 počet závaží
obecně polynom:
poměr vah většího a menšího závaží
Z1=Z
Z0=1
An*Zn + An-1*Zn-1 + …. + A2*Z2 + A1*Z1 + A0*Z0 = n=0An*Zn kde A = řádová číslice, Z = základ číselné soustavy vždy platí 0 A Z-1, protože Z*Zn =1*Zn+1
binární soustava oktalová soustava dekadická soustava hexadecimální soustava
Z=2 Z = 23 = 8 Z = 10 Z = 24 = 16
0A 1 0A 7 0A 9 0 A 15
Převod z BIN do DEC Váha bitu:
512 256 128 64 32 16
8
4
2
1
1 0 1 1 0 1 1 0 0 1 1 +8 +16 +64 +128 +512 729
sečteme váhy jedničkových bitů
Převod z DEC do BIN Váha bitu:
729 -512=217 -2 5 6 = - 3 9 -128= 89 -64= 25 -32= -7 -16= 9 Od čísla se postupně odečítají váhy jednotlivých bitů (počínaje nejvyšší vahou, která se ještě vejde do čísla). Jestliže je výsledek odčítání záporný, do výsledku se zapíše 0 a odčítání se anuluje. Jestliže je výsledek odčítání nezáporný, do výsledku se zapíše 1 a v dalším kroku se odečítá od zbytku.
-8= 1
-4=-3 -2=-1 -1= 0
1 0 1 1 0 1 1 0 0 1
1024 512 256 128 64 32 16 8 4 2 1
Hexadecimální soustava Převodní tabulka: zleva doplnit nulami na 4 bity váha bitu: 8
4
2
1
0 0 1 0 1 1 0 1 1 0 0 1
2
D
9
převod HEXBIN a BIN HEX: vždy 4 číslice binárního čísla (bity) odpovídají jedné hexadecimální číslici jako číslice s hodnotou větší než 9 se používají písmena A až F
bin
dec
hex
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 2 3 4 5 6 7 8 9 A B C D E F
Logika výroková logika lze ji chápat intuitivně všechny kovy se teplem roztahují měď je kov ----------------------------------------- dedukce: měď se teplem roztahuje
matematická logika přirozený jazyk je nejednoznačný formalizace, symboly ...
Booleova algebra obdoba numerické algebry zavedena pro výrokovou logiku jsou definovány operace ¬ ... unární operace negace (NOT) ... binární operace sjednocení (OR) ... binární operace průnik (AND)
– negace + součet * součin
je definována binární relace ... relace ekvivalence
operace booleovy algebry lze realizovat technickými prvky
Logická funkce NOT
negace (inverze)
A
vše ostatní =
not A
Logická funkce AND
logický součin (průnik)
A A and B
B
Logická funkce OR
logický součet (sjednocení)
A
B A or B
Tabulka logických funkcí
A B not A A or B A and B A xor B
0 1 0 1
0 0 1 1
1 0 1 0
0 1 1 1
0 0 0 1
0 1 1 0
mohou nastat 4 různé kombinace stavů A,B XOR zkratka z eXclusive OR. Výstup je logická 1 tehdy a jen tehdy pokud se hodnoty vstupů liší.
Funkce NOT (inverze)
relé v klidovém stavu PROPOJÍ okruh žárovky
vybuzené relé ROZPOJÍ okruh žárovky
Funkce AND (logický součin)
k propojení okruhu žárovky je potřebné, aby byly oba kontakty A, B sepnuty současně
Funkce OR (logický součet)
k propojení okruhu žárovky postačí, aby byl sepnut jeden z kontaktů A, B
Elektronické logické obvody aktivní (elektronka, tranzistor) pasivní (odpory, diody) Dnes se téměř výhradně používají logické obvody s tranzistory – HRADLA schematická značka = abstraktní symbol, nezávislý na technické realizaci
hradlo AND
hradlo NAND
symbol inverze
Přenosová charakteristika Nejjednodušším prvkem je INVERTOR U2
pracuje analogově (spojitě) !!
U1
log.
1
U2
charakteristika udává závislost výstupního napětí U2 na vstupním napětí U1
nedefinovaný stav
log.
0 logická
0
logická
1
U1
Přehled kombinačních logických funkcí
Logické schéma
grafické zobrazení propojení hradel schéma lze popsat soustavou logických rovnic požadovanou funkci lze vyjádřit logickými rovnicemi … … z logických rovnic lze odvodit schéma
C A
F
D
B C
D
F = not ( A and B ) or not (not A and B)
Zpoždění hradla ideální hradlo přenáší změny vstupních signálů na výstup bez zpoždění reálná hradla mají zpoždění ! Důsledek: hazardní
stavy
tohle podle rovnic
neexistuje!
B = not A A F = not (A and B) = 1
ideální B
vždy 0
ideální F
F A
B
reálné B reálné F
Synchronní logika výstup kombinačního obvodu se zapisuje do klopného obvodu hodinovými impulsy stav kombinačních obvodů se do příštího hodinového impulsu musí ustálit
CLK
A
D Q
F
B
Q D Q
A B
C
C
C
CLK hazardní stav byl odstraněn
C F
Q
čím menší zpoždění, tím vyšší může být hodinový kmitočet !
Funkční bloky složitější logické obvody, složené z hradel registr, multiplexor, sčítačka, ALU,…
nejdříve to byly konstrukční bloky … … pak výměnné desky … … pak integrované obvody MSI … dnes typické celky vyšší úrovně, umožňující zjednodušit popis procesoru či počítače
Klopný obvod základní prvek statické paměti základní prvek registrů mechanický model:
stabilní stav udržuje zpětná vazba
A
B
OR
NOR
0
0
0
1
0
1
1
0
1
0
1
0
1
1
1
0
2 hradla NOR
Registr bit 0
bit 1
bit 2
D0
D1
D2
….
D R C D R C
D R C
reset
strobe
nulování
zápis
Q
Q0 Data
Q
Q1
Hodiny Set Reset
Q
Q2 klopný obvod typu D
D C S R
Q Výstup
Q
Multiplexor
Podle adresy aktivuje jeden vstup a předá ho na výstup. A0 B0 S0 C0 D0 A1 B1 S1 C1 D1 A2 B2 S2 C2 D2 A
B
C
D
select = C
Příklad použití multiplexoru výběr zdroje adresy pro operační paměť registr A
registr B
registr C
multiplexor ADRESA
operační paměť DATA
registr D
Aritmetický součet čísel COx CIx
0
1 0
v binární soustavě podobně:
0
2 7 Ax 5 + 1 3 Bx 4 4 0 Sx 9
když je součet řádových číslic větší než 1, zapíše se do výsledku hodnota součtu zmenšená o 2 (základ) a do vyššího řádu se přičte přenos 1
v dekadické soustavě:
když je součet řádových číslic větší než 9, zapíše se do výsledku hodnota součtu zmenšená o 10 (základ) a do vyššího řádu se přičte přenos 1
Binární součet čísel COn CIn
0
A B Sn
Sn a COn lze definovat pravdivostní tabulkou jako logické funkce An, Bn a CIn
Funkční tabulka 1-bitové sčítačky C(n-1) A B C0
0 0 0 0 1 1 1 1
0 1 0 1 0 1 0 1
0 0 1 1 0 0 1 1
C(n) Součet 0 0 0 1 0 1 1 1
0 1 1 0 1 0 0 1
Cn = přenos
když C(n-1) = 0
když C(n-1) = 1
DeMorganova pravidla pro převody A + B = A B a AB = A + B
NOR je ekvivalentní inverzím následovaným součinem
NAND je ekvivalentní inverzím následovanými součtem
Logické schéma sčítačky
generátor přenosu
polo-sčítačka realizující A+ B
polo-sčítačka realizující CI + (A + B)
Zobrazení záporných čísel pro vyjádření polarity stačí 1 bit 0000001011011001 = 729 1000001011011001 = -729 toto zobrazení je jednoduché, ale není vhodné pro sčítání sčítačkou 0000001011011001 = 729 +1000001011011001 = -729 1000010110110010 = -1458 výsledek má být nula !!!
Dvojkový doplněk jednoduché odvození záporné hodnoty:
000001011011001 = 729 111110100100110 negace 111110100100111 přičtení 1 111110100100111 = -729 0111111111111111 = max. kladné číslo (32767) ... 0000000000000001 = 1 0000000000000000 = 0 1111111111111111 = -1 1111111111111110 = -2 ... 1000000000000000 = max. záporné číslo (-32768)
Sčítání ve dvojkovém doplňku při sčítání čísel vyjádřených ve dvojkovém doplňku dává sčítačka správný výsledek 0000001011011001 = 729 +1111110100100111 = -729 1 0000000000000000 = 0 výstup Cout sčítačky
výstup S sčítačky
Aritmetická a logická jednotka sčítačka rozšířená o další funkce jedná se vlastně o funkční generátor řídícími signály lze nastavit funkci R = f(A,B) více bitů paralelně
operand A
více bitů paralelně
R = f(A,B)
výsledek R
více bitů paralelně
operand B
stav
několik bitů paralelně
kód požadované funkce f
ADD, SUB, ADC, SBC, AND, OR, XOR, .…
Konec přednášky