Princípy počítačov I.

Doc. RNDr. Daniel Olejár, CSc.

Študijný odbor Informatika, školský rok 1999/2000

 

  1. Kódovanie informácie (základné pojmy z teórie formálnych jazykov, teórie informácie a teórie kódovania)

Abeceda, znaky abecedy, slová nad abecedou, zreťazovanie slov, podslovo, dĺžka slova, prázdne slovo, jazyk nad abecedou. Iterácia slov. Zdroj informácie, prenosový kanál. Abeceda zdroja, kódová abeceda. Kódovanie symbolov zdroja, dekódovanie. Kódové slová, kód. Jednoznačnosť dekódovania. Tri prístupy ku kódovaniu:

Základné princípy nerovnomerných kódov: rozličné matematické modely zdroja. Pravdepodobnosti výskytu jednotlivých zdrojových symbolov. Nerovnomerné kódy (Fanov kód). Jednoznačnosť dekódovania. Prefixové kódy.

Základné princípy samoopravných kódov: redundancia prirodzeného jazyka. Kontrola parity. Geometrická interpretácia samoopravného kódu. Hammingova váha vektora. Vzdialenosť dvoch vektorov - kódových slov. Minimálna vzdialenosť a samoopravná schopnosť kódu. Obdĺžnikový kód. Hammingov (7,4)-binárny kód.

 
  1. Kódovanie informácie v počítači.

    2. Numerická informácia. Reprezentácia celých čísel (so znamienkom, bez znamienka, priamy kód, binárny doplnkový kód, excess-kód, Grayov zrkadlový kód). BCD-kód, hexadecimálny kód. Reprezentácia reálnych čísel vo formáte s pevnou rádovou čiarkou. Pohyblivá rádová čiarka (mantisa, exponent, normalizovaný tvar, hidden bit technique). Počet, rozsah a presnosť zobrazovaných čísel. Aritmetické operácie s číslami zapísanými v rozličných formátoch.

    Textová informácia. ASCII. Zobrazovanie textovej informácie. Kódové stránky, fonty.

    Riadiaca informácia. Inštrukcia, formát inštrukcie, operačný kód, adresová časť. Kódovanie adries. Riadiace bity.

     

  2. Spracovanie informácie. (Booleovská funkcia ako matematický model transformácie informácie)

    3. Transformácie binárne zapísanej informácie. Popis transformácií pomocou Booleovských funkcií a Booleovských operátorov. Elementárne Booleovské funkcie. Formuly. Realizácia Booleovských funkcií formulami. Úplná disjunktívna normálna forma (ÚDNF) a disjunktívna normálna forma (DNF). Zložitosť formuly. Minimalizácia DNF. Geometrická a algebraická interpretácia minimalizácie DNF. n-rozmerná Booleovská kocka a graf Booleovskej funkcie. Pokrytie grafu Booleovskej funkcie.Karnaughove mapy. Minimalizácia DNF pomocou Karnaughových máp. Quine-McCluskey-ov algoritmus minimalizácie.

     

  3. Realizácia Booleovských funkcií logickými obvodmi

    4. Logický obvod. Reprezentácia logických hodnôt pomocou fyzikálnych veličín. Realizácia základných Booleovských funkcií (konjunkcia, disjunkcia, negácia, Shefferova, Pierceova funkcia, XOR) pomocou hradiel. Konštrukcia obvodov realizujúcich zložitejšie Booleovské funkcie. Fyzikálne ohraničenia. Časová a priestorová zložitosť logického obvodu. VLSI.

     

  4. Základné kombinačné obvody.

    5. Zjednotenie, prienik, doplnok binárnych veličín. Testovanie nulovosti binárnej veličiny. Výhybka. Dekóder. Prioritný kóder. Multiplexor a demultiplexor. Použitie multiplexora (prepojenie registrov na ALU, realizácia Booleovských funkcií). Porovnávací obvod. Test parity. Jednobitová polosčítačka. Sčítačka. Sčítačka vo funkcii odčítačky. Ošetrenie pretečenia. Sčítanie a odčítanie čísel v binárnom doplnkovom kóde. Aritmetická a logická jednotka (ALU).

     

  5. Sekvenčné obvody I.

    6. Základné pojmy z teórie automatov. Vstup, výstup, stav automatu, prechodová a výstupná funkcia. Stavový diagram a tabuľka prechodov. Príklady konečných automatov. Výpočtová sila konečných automatov. Turingov stroj a jeho výpočtová sila. Mooreov a Mealyho automat.

    Základné pamäťové členy. SR, JK, T, D. Statická a dynamická analýza SR člena. Problémy synchonizácie a ich riešenie. Zapojenie master-slave.

    Návrh sekvenčného obvodu. Automat, tabuľka prechodov. Y-Z matica. Excitačná matica. Realizácia excitačných funkcií a výstupnej funkcie.

     

  6. Sekvenčné obvody II.

    7. Registre (sériový, paralelný, posuvný) a ich použitie. LFSR a ich použitie v teórii kódovania a kryptografii. Pamäť (jednorozmerná, dvojrozmerná). Zložitosť pamäte. Organizácia pamäte v počítači. Register adries pamäte a vyrovnávací register. Asociatívna pamäť.

     

  7. Digitálne systémy.

Register transfer language, RTL (vstupné, výstupné premenné, priraďovanie hodnôt registrom, aritmetické, logické operácie s obsahom registra, operácie posunu, prístup k jednotlivým bitom registra, riadenie výpočtu: rozhodovací príkaz a príkaz skoku.) Riadiace jednotky: jednoduchá, stavovo závislá a programovateľná. Realizácia násobenia a delenia. Princíp činnosti počítača von Neumannovského typu.

 

Literatúra

[1] Adámek J. : Kódovaní, SNTL, Praha 1989

[] Jablonskij S.V.: Úvod do diskrétnej matematiky, Alfa, Bratislava, 1982

[] Pollard L.H.: Computer Design and Architecture, Prentice Hall, 1990

[] Tannenbaum A.: Structured Computer Organisation

 

 

Poznámky. Prednáška je určená pre prvý ročník odboru Informatika. Má rozsah 2/2 Z a prednáša sa v zimnom semestri. Cvičenia voľne dopĺňajú prednášku; ich obsah určuje Katedra rádiofyziky MFF UK. Kurzívou sú uvedené nepovinné témy, ktoré dopĺňajú základný kurz. Niektoré z nich sú predmetom samostaných prednášok (diskrétna matematika, teória kódovania a kryptológia.) Obsahom predmetu Princípy počítačov sú zväčša klasické témy, ktoré sú relatívne nezávislé na použitých technológiách. Na Princípy počítačov I. nadväzuje v letnom semestri 1. ročníka prednáška Princípy počítačov II.

 

Related Page 1 | Related Page 2 | Related Page 3