Booleova algebra

• nauka o operacích na množině {0, 1}

Základní operace

• Logický (Booleův) součin AND ∧

• Logický (Booleův) součet OR ∨

• Negace NOT ¬ ˜

• Způsoby popisů

  • Pravdivostní tabulka
  • Graficky v rovině = Vennovy diagramy
  • Matematický aparát

Využití Booleovy algebry

• 1938 = využito pro kontaktní z
• Základní prvek: relé (Relay)
  • Relé rozepnuto. = Cívkou neprotéká proud, pružina kotvičku odtahuje od cívky.
  • Relé sepnuto. = Cívkou protéká proud a vzniklé magnetické pole přitáhne kotvičku k cívce.
  • kontakt ovládaný dvouhodnotovou proměnnou a
    1. spínací kontakt (a)
    2. rozpínací kontakt (¬a)

Zapojení kontaktů

• sériové a . b
• paralelní a + b

Nevýhody použití:

• First real bug (moth) found in 1947.

Obvodové znázornění Booleovy algebry:

Minimalizace počtu operací B-algebry

1. Matematické výrazy: !(xy)z + !(x)yz = !xz(!y + y) = !xz
2. Využitím jednotkové krychle
3. Karnaughova mapa - normalizací Vennova diagramy - B-algebra je nevhodná pro technickou realizaci - příliš velký počet.

Shefferova algebra

• Založena na negace logického součinu NAND
• Lze převést z Booleovy algebry

Peirceova algebra

• Založena na negaci logického součtu NOR

Fyzikální podstata signálů

Průběh signálu

• Změny signálu v praxi nejsou diskrétní, nýbrž spojité.
• Takt =
• Bity přenášíme zvlášť v časovém taktu.
• Nejen, že potřebujeme začátek a konec taktu, ale i prostředek, kdy budeme měřit hodnotu.
• Hodnotu nelze číst (vzorkovat), když se hodnota mění. (Zakázané pásmo = signál se nesmí v takovém stavu nacházet při čtení.)
• Pozitivní logika/Negativní logika

Technologie TTL (transistor-transistor logic)

• Základní stavební prvek je tranzistor NPN.
• Parametry TTL:
  • napájecí napětí +5V
  • L < 0,8V
  • H > 2,0V
• Tři vývody: báze (řídící vývod), kolektor, emitor
• Malou změnu proudu mezi bází a emitorem ovlivňujeme velké změny proudu mezi kolektorem a emitorem.

Invertor v TTL

• Implementace operace negace v Booleově algebře.

NAND pomocí dvou tranzistorů NOR pomocí dvou tranzistorů

Kombinační logické obvody

• Základní logické členy:
  • Invertor
  • AND
  • OR
  • NAND
  • NOR
• Ostatní logické členy
  • XOR ⊕ =1 mod2 = Nonekvivalence
  • XNOR NOXOR = ekvivalence

Logické obvody

• Multiplexor
  • přepínač, datové a adresové vstupy, Z = A.X + !A.Y
• Dekodér
  • n adresových vstupů a 2^n datových vstupů
  • pracuje s pamětí

Sčítačky

Sčítačka MODULO 2

• x + y = z
• přenos neřeší
• z = !x.y + x.!y

Polosčítačka

• Má S součet a P přenos do vyššího řádu.
• S = !x.y + x.!y
• P = x.y

Úplná sčítačka pro jeden binární řád

• vstup xi, yi a přenos z nižšího řádu pi-1
• výstup si a pi

Vícemístná sčítačka

• Používá x-krát sčítačku pro jeden řád.
• Nemůžeme spustit naráz x řádů.
• Nelze ani sestavit sčítačku pro 2×32 vstupů. (2^64 možností vstupů)

Sekvenční logické obvody

• Mají výstup závislý na hodnotě vstupů a na posloupnosti změn, které předcházely.
• Některé výstupy jsou ‘zpětná vazba’.
• Qk = vnitřní paměť (Pamatují si výstup předchozího vyhodnocení.)

Základní paměťový člen - Klopný obvod RS

• R = RESET (nulování)
• S = SET (nastavení)
• R=1 a zároveň S=1 je zakázaný stav
• Obvod řízený jedničkami vs obvod řízený nulami. - Klopný obvod řízený:
  • hladinou
    • horní
    • dolní
  • hranou
    • čelem impulsu (nástupní hrana = z 0 na 1)
    • týlem impulsu (sestupná hrana = z 1 na 0)

Klopný obvod D

• D = Delay (vzorkovací k. o.) 

Klopný obvod JK

• Funguje jako RS k.o., ale nemá zakázaný stav. Při zakázaném stavu pro RS vrací negaci Q.
• U složitějších obvodů nastává problém se resetováním stavu celé sítě, proto se zavádí globální reset, který je u všech připojený k lokálnímu resetu.

Typické sekvenční obvody v počítačích

• Sériová sčítačka = Sumátor (kombinační obvod) + D k.o.
• Paralelní registr = střádač (accumulator); n-bitová paměť, součástí procesoru
• Sériový přenos:
  • Informaci přenášíme po bitech. (Dvoustavová komunikace)
  • Čtyřstavová komunikace (Přenos informace po dvou bitech. 2^2 = 4)
  • Přenosová rychlost:
    • v bitech za sekundu (neznamená počtu taktů)
    • v počtu změn stavu za sekundu (baud rate, Bd)
• Uvnitř počítače přenos paralelně pomocí sběrnice.
  • Do prvního registru zapíše procesor, to se zapíše i do druhého registru a až může op. paměť zapsat data z registru, aktivuje druhý registr a zapíše data.
• Sériový registr (posuvný registr)
  • Jedním taktem signálu CLK se informace posune o jeden D-KO.
  • Sériově poslaná data potřebujeme převést do paralelního tvaru.

Sčítačka v BCD kódu

• Součet dvou čísel:
  • Budeme přičítat 6:
    • Je-li přenos v binárním součtu.
    • Je-li číslo 11xx nebo 101x

Násobičky

• Sekvenční násobení (bez znaménka)
  • Střádač má dvojnásobnou velikost násobence a násobitele.
  • Násobenec přičítáme ke střádači, když i-tý řád násobitele se rovná 1.
  • Po každém řádu posouváme střádač o jeden bit doprava.

Bitové manipulace

Rotace bitů

• Operace nad n-tici bitů. Obsah n-tice se rotuje.
• Bity se neztrácí.
• Doleva = Bity nižšího řádu se posunují směrem k vyššímu řádu. Když by došlo k přetečení, přičte se 1 k uvolněnému řádu (významově nejnižšímu).
• Doprava = Bity nejvyššího řádu k nejnižšímu.

Logický posun

• Podobně jako rotace, ale bit který se uvolňuje se ztrácí.
• Doleva = do nejnižšího bitu se vkládá 0
• Doprava = do nejvyššího bitu se vkládá 0

Aritmetický posun (Arithmetic shift)

• Zachovává znaménko.
• Doleva = násobení 2; Znaménkový bit se nemění! (V procesoru žádný aritmetický posun doleva není, používá se logickým posunem doleva. Když by došlo k ovlivnění znaménka dojde k přeplnění.)
• Doprava = dělení 2; Znaménkový bit se kopíruje do nižšího řádu! (viz doplňkový kód)