Informatika alapjai

Kapuáramkörök

A számítógép egy műszakilag megvalósított rendszer,^⇒ amelynek a legfontosabb eleme a számítógép központi egysége, ezen belül a központi feldolgozó egysége (CPU), amely a számítógép programozott működését hardver szinten megvalósítja, ill. vezérli (metaforikusan kifejezve a működés alapvető "logikáját" szolgáltatja).
A CPU működésének elvi szintű megértéséhez az első lépés azoknak az alapáramköröknek, ún. kapuáramköröknek a megismerése, amelyekből komplex logikai hálózatokat tudunk felépíteni. Ezek a hálózatok teszik lehetővé, hogy a CPU képes legyen a számítógép működése szempontjából alapvető feladatok elvégzésére (például az éppen futó program utasításainak beolvasására, az utasítások értelmezésére és végrehajtására, a megfelelő műveletek elvégzésére, szükség esetén a futó programok megszakítására stb.).
Összetett, komplex logikai függvényeket megvalósító rendszereknél (és a számítógépek túlnyomó többsége ilyen), "nem célszerű egyetlen, ugyancsak bonyolult logikai hálózatot tervezni. Előnyösebb, ha ilyenkor a bonyolult logikai feladatot több, de önmagukban viszonylag egyszerű logikai hálózat létrehozásával, azok összehangolt működtetésével oldjuk meg. A logikai hálózatoknak az így kialakuló rendszere alapján bevezethetjük a logikai rendszer fogalmát." (Arató 1996: 18)

Egy logikai rendszerben az egyes részfeladatokat végző funkcionális egységek vezérlését egy ún. vezérlő egységgel kell biztosítanunk. A vezérlő egységet megvalósíthatjuk például egy olyan logikai hálózattal, amely a megfelelő vezérlő jelek kiadásával hangolja össze és ütemezi a funkcionális egységek működését:
(1) A vezérlő jeleket a vezérlő egység meghatározott logikai feltételek teljesülése esetén adja ki; a logikai feltételeket meghatározó logikai értékek származhatnak
    ○ az (egy vagy többfázisú) órajelgenerátor által kiadott órajelekből,
    ○ más funkcionális egységek vagy áramkörök által kiadott vezérlő jelekből (például egy kétállapotú gomb kimenetéből, a megszakításvezérlő egység kimeneteiből stb.),
    ○ a vezérlő egység, ill. a funkcionális egységek belső állapotát tároló regiszterekből (például az állapotregiszterből, a megszakításregiszterből, a fázisregiszterből stb.),
    ○ stb.
(2) A vezérlő egység által kiadott vezérlő jelek végzik a funkcionális egységek vezérlését (például szinkron sorrendi hálózatok esetén az órajelek engedélyezik vagy tiltják azoknak a tároló áramköröknek ("flip-flopoknak") a működését, amelyek a bemeneteket, a belső állapotokat, a kimeneteket stb. tárolják).
Egy logikai hálózat vagy egy logikai rendszer funkcionális egységeinek működését meghatározott vezérlő jelek segítségével vezérelhetjük. (Ilyenek lehetnek például az órajelek, a vezérlő egység kimenetei stb.)

A logikai alapáramkörök vagy kapuáramkörök^⇒ és a logikai hálózatok^⇒ működési elveinek megismerése után még visszatérünk a logikai rendszerek vezérlésének^⇒ kérdésére.

Függetlenül technikai megvalósításuktól, a kapuáramkörök olyan fekete dobozoknak tekinthetőek, amelyekben az inputot és az outputot jelentő feszültségjelek a logikai 0 és 1 állapotoknak felelnek meg. Ebben az értelemben egy kapuáramkör egy adott logikai műveletet reprezentál. A kapuáramkör bemenetét az adott logikai művelet független változóinak lehetséges értékei ("kombinációi") adják, a kapuáramkör kimenete pedig az adott logikai művelet eredménye lesz.
A kapuáramkörök, valamint a bemenetükön, ill. kimenetükön megjelenő bináris jelek szemléltethetőek olyan áramkörök ("kapcsolások") segítségével, amelyek csak telepeket, mechanikus kapcsolókat és izzólámpákat tartalmaznak (vö. pl. Urbán 1987: 14-22). Érdemes megjegyeznünk, hogy ha mechanikus kapcsolók helyett elektromechanikus, kivülről elektromos jelekkel vezérelhető kapcsolókat (jelfogókat vagy reléket) használunk, akkor nemcsak a kapuáramkörök, hanem összetett logikai hálózatok is kialakíthatók (elvileg akár egy programvezérelt számítógép is).
A kapuáramkörök tényleges kialakítása számos módon lehetséges. Korábban például telefonreléket, elektroncsöveket, diódákat ill. tranzisztorokat használtak. Ezek közül a tranzisztorok kiemelt jelentőségűek, mivel ezek képezik az alapját a napjainkban használt integrált áramköröknek. A mai számítógépekben nagy bonyolultságú (ún. VLSI) integrált áramkörökben, "chipekben" hozzák létre a kapuáramköröket és a belőlük kialakított összetett logikai hálózatokat.

Tárgyalásunk szempontjából alapvető, hogy a logikai alapműveletek megvalósíthatók digitális áramkörök, ún. kapuáramkörök segítségével.

A logikai alapműveleteket megvalósító kapuáramköröket például az alábbi szimbólumokkal ábrázolhatjuk:

AND:
vagy

OR:
vagy

NOT:
vagy
vagy vagy

Korábban láttuk, hogy a logikai alapműveletek segítségével minden logikai függvény kifejezhető. Ennek megfelelően a kapuáramkörök megfelelő összekapcsolásával tetszőleges logikai függvény műszakilag megvalósítható.
A kapuáramkörök összekapcsolásával létrehozott logikai hálózatok elvileg bármilyen logikai függvény műszaki megvalósítását lehetővé teszik.

1. példa: egy egyszerű egybites összeadó, ún. félösszeadó áramkör igazságtáblázata és kapuáramkörökkel történő megvalósítása (HA, half adder; vö. Wikipédia, Sulinet Tudásbázis):

A fenti igazságtábla két egybites szám (A és B) összegét adja meg (S), valamint az összeadáskor fellépő maradékot (C). Az igazságtáblázat alapján a félösszeadót megvalósító logikai függvények t.d.n.f.^⇒ alakja a következő:
S = ( ⌝A ∧ B ) ∨ ( A ∧ ⌝B ) = A⨁B és
C = ( A ∧ B )
Figyeljük meg, hogy a félösszeadó kapuáramkörökkel történő megvalósítása során
(1) a ⌝A és ⌝B jeleket egy-egy NOT kapuval állítjuk elő,
(2) a három AND kapu bemeneteit vagy közvetlenül a félösszeadó valamelyik bemenetéről (A és B), vagy valamelyik NOT kapu kimenetéről (⌝A és ⌝B) állítjuk elő,
(3) az összeget (S) egy OR kapu állítja elő, amelynek a bemenetét két AND kapu kimenete szolgáltatja, és
(4) az átvitelt a magasabb helyi értékek felé (C) egy AND kapu állítja elő, amelynek a bemenetét közvetlenül a félösszeadó bemenetei (A és B) szolgáltatják.

A félösszeadó működésének ismeretében felépíthető egy több bites bináris összeadó (ún. teljes összeadó). Ha a félösszeadó igazságtáblázatát egy oszloppal kibővítjük, amely az előző helyi értékről származó átvitelt (C_i vagy c_in) tartalmazza, az ún. egybites teljes összeadó igazságtáblázatát^⇒ kapjuk:

Az egybites teljes összeadó igazságtáblázatában

A és B az összeadandó bitek,
C_i (vagy c_in) az előző helyi értékről átvitt (vagy átvett) bit (i=input),
C_o (vagy c_out) a következő helyi értékre történő átvitel bitje (o=output),
S az A és B megfelelő bitjeinek összege, pontosabban ennek legalacsonyabb helyiértékű bitje.

Feladat:
Valósítsuk meg az igazságtábla alapján az egybites teljes összeadót (FA, Full Adder). Az összeadás megszokott algoritmusát alkalmazva a feladat két félösszeadóval (HA, Half Adder) könnyen megoldható:

Az ábrán szereplő teljes összeadót megvalósító logikai áramkört az alábbi logikai függvények írják le:
S_tmp=(A∧⌝B)∨(⌝A∧B)
C_tmp=A∧B
S=(C∧⌝S_tmp)∨(⌝C∧S_tmp)
C_sec=S_tmp∧C
C_out=C_sec∨C_tmp
Mivel
⌝S_tmp= ⌝(A∧⌝B)∧⌝(⌝A∧B)=
(⌝A∨B)∧(A∨⌝B)= (→ disztributivitás összetett formája^⇒)
(⌝A∧A)∨(⌝A∧⌝B)∨(B∧A)∨(⌝B∧⌝B)=
(⌝A∧⌝B)∨(B∧A)
Ezért
S=(C∧⌝S_tmp)∨(⌝C∧S_tmp)=
S=[C∧((⌝A∧⌝B)∨(B∧A))]∨ [⌝C∧((A∧⌝B)∨(⌝A∧B))]=
S=(C∧⌝A∧⌝B)∨(C∧B∧A)∨ (⌝C∧A∧⌝B)∨(⌝C∧⌝A∧B)=
S=(A∧⌝B∧⌝C)∨(⌝A∧B∧⌝C)∨ (⌝A∧⌝B∧C)∨(A∧B∧C)
Másrészt
C_sec=S_tmp∧C=
[(A∧⌝B)∨(⌝A∧B)]∧C=
(A∧⌝B∧C)∨(⌝A∧B∧C)
Tehát
C_out=C_sec∨C_tmp=
[(A∧⌝B∧C)∨(⌝A∧B∧C)]∨(A∧B)=
(A∧⌝B∧C) ∨ (⌝A∧B∧C) ∨ [(A∧B) ∨ (A∧B∧C)] = (→ abszorpció összetett formája^⇒)
[(A∧⌝B∧C) ∨ (A∧B∧C)] ∨ [(⌝A∧B∧C) ∨ (A∧B∧C)] ∨ (A∧B) =
(A∧C)∨(B∧C)∨(A∧B) =
(A∧B)∨(A∧C)∨(B∧C)
Ellenőrizzük a teljes összeadót megvalósító logikai áramkör működését egy igazságtáblázattal:
egybites teljes összeadó igazságtáblázata
A B C=C_in S_tmp C_tmp S C_sec C_out
0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 0
1 0 0 1 0 1 0 0
1 1 0 0 1 0 0 1
0 0 1 0 0 1 0 0
0 1 1 1 0 0 1 1
1 0 1 1 0 0 1 1
1 1 1 0 1 1 0 1

Ellenőrzésként vessük össze a táblázat első három oszlopának, valamint a pirossal és sárgával kijelölt oszlopoknak az értékeit az egybites teljes összeadó korábban elkészített igazságtáblázatával.^⇒
Az egybites teljes összeadó kimenetének leírása logikai függvényekkel (három logikai változóval, t.d.n.f. alakban^⇒ ):
S(A,B,C) = (⌝A∧B∧⌝C) ∨ (A∧⌝B∧⌝C) ∨ (⌝A∧⌝B∧C) ∨ (A∧B∧C) = A⨁B⨁C
C_out(A,B,C) = (A∧B∧⌝C) ∨ (⌝A∧B∧C) ∨ (A∧⌝B∧C) ∨ (A∧B∧C) = (A∧B) ∨ (A∧C) ∨ (B∧C)

Az egybites teljes összeadó áramkörök összekapcsolásával pedig könnyen megvalósíthatunk egy 'n' bites teljes összeadót. Például az alábbi ábrán egy 4 bites teljes összeadó látható (vö. Wikipédia, Sulinet Tudásbázis).
Vegyük észre, hogy a kép valamilyen oknál fogva nem a szokásos, balról jobbra történő jelterjedési irányt ábrázolja, hanem pont fordítva (azaz az álló helyzetben megjelenített ábra jobbról balra "olvasandó".)

Jegyezzük meg, hogy

a legalacsonyabb helyi értéken nincs "bejövő" átvitel, tehát értelemszerűen C₋₁=0;
a legmagasabb helyi értékű biten pedig az átvitel (C₃=1) ún. túlcsordulást jelez.

A túlcsordulás rendszerint azt jelzi, hogy adott számú bit esetén az összeadás nem végezhető el, mivel a kapott összeg több bitből áll, mint a számok ábrázolására vagy tárolására rendelkezésre álló bitek száma. (Például 1101₂+1000₂=10101₂ esetén az összeadandók 4 bitesek, az összeg viszont 5 bites.)
Emeljük ki, hogy a példákban szereplő logikai hálózatok esetében
(1) a kimenet kizárólag a bemenetre adott jelektől függ, és
(2) ideális esetben feltételezzük, hogy a kimeneti jelek a bemeneti jelek hatására "azonnal" (azaz késleltetés nélkül) megjelennek.

Az ilyen típusú hálózatokat kombinációs hálózatoknak nevezzük.
A kapuáramkörök felhasználásával interaktívan különböző logikai hálózatokat alakíthatunk ki az alábbi internetes címeken:
Logic Gate Simulator | Academo.org – Free, interactive, education.
https://academo.org/demos/logic-gate-simulator/ (2022-11-19)
simulator.io - Build and simulate logic circuits.
https://simulator.io/ (2022-11-19)

2. példa: egy 2-4 dekóder bemenete egy két bites bináris szám két számjegye (bitje). A dekóder 2²=4 kimenettel rendelkezik. A dekóder úgy működik, hogy a bemenet minden lehetséges értékkombinációja esetén a kimenetek közül mindig pontosan egy vesz fel 1 értéket, és különböző bemenetekhez különböző kimenetek tartoznak.
Az áramkör igazságtáblázata, és kapuáramkörökkel történő egy lehetséges megvalósítása a következő (vö. Wikipedia):

A fenti igazságtábla egy kétbites bináris szám számjegyeihez (A₀ és A₁) rendeli hozzá 2 nemnegatív egész kitevős hatványainak direkt kódban ábrázolt értékeit (ahol D₀, D₁, D₃, D₄ a direkt kódban ábrázolt szám számjegyei). Vegyük észre, hogy bármilyen 'A' input esetén a dekóder olyan 'D' outputot szolgáltat, hogy a D₀, D₁, D₃, D₄ számjegyek közül mindig pontosan egynek az értéke lesz 1 (a többi számjegy pedig zérus lesz).

egybites teljes összeadó igazságtáblázata
A	B	C=C_in	S_tmp	C_tmp	S	C_sec	C_out
0	0	0	0	0	0	0	0
0	1	0	1	0	1	0	0
1	0	0	1	0	1	0	0
1	1	0	0	1	0	0	1
0	0	1	0	0	1	0	0
0	1	1	1	0	0	1	1
1	0	1	1	0	0	1	1
1	1	1	0	1	1	0	1

Gyakorló feladatok

Hozzunk létre kombinációs hálózatokat, amelyek az alábbi logikai függvényeket valósítják meg ("realizálják"). Ahol lehet, próbáljuk meg egyszerűsíteni is a függvényeket! (vö. Fodor-Nagy 1982: 82-90):

(a) p(A,B)=(A∧⌝B) ∨ (⌝A∧B)

(b) p(A,B,C)=(A∧B∧⌝C) ∨ (A∧⌝B∧C) ∨ (A∧B∧C)

(c) p(A,B,C)=(A∧B) ∨ (⌝A∧B∧C) ∨ (⌝A∧B∧⌝C)

(d) p(A,B,C)=(A∧B) ∨ (⌝A∧⌝B) ∨ (A∧C)

(e) p(A,B,C)=(A∧B) ∨ (⌝A∧⌝B∧C) ∨ (⌝A∧B∧⌝C)

(f) p(A,B,C,D)=((A∧B∧C) ∨ ⌝B) ∧ ⌝D

Logikai hálózatok

Láttuk, hogy a számítógépet fekete doboznak tekintve a számítógép működését elvi szinten egy megfelelő függvény (ill. függvények^⇒) segítségével adhatjuk meg. Korábban utaltunk rá,^⇒ hogy a függvény értéke a bemenetek mellett függhet a számítógép korábbi működése során előállított és/vagy tárolt adatoktól is.
A továbbiakban azzal a kérdéssel foglalkozunk, hogy hogyan tudunk megvalósítani kapuáramkörök segítségével egy
p(x₁,x₂,...,x_n):{0,1}Χ{0,1}Χ...Χ{0,1}→{0,1}
'n' változós logikai függvényt.
Több logikai függvény használata esetén használhatjuk a korábbi p₁, p₂, ..., p_n jelöléseket. A számítógép elvi működésének leírásához nyilvánvalóan több logikai függvényre van szükségünk, de ennek most nincs különösebb jelentősége, mivel ha egy tetszőleges 'p' logikai függvényt meg tudunk műszakilag valósítani, ezt akárhány logikai függvény esetében ugyanúgy megtehetjük.
A fenti 'p' logikai függvényt műszakilag egy meghatározott alapáramkörökből felépülő logikai hálózattal tudjuk megvalósítani. Attól függően, hogy
– a 'p' logikai függvény értékének meghatározásához elegendők pusztán a függvény független változóinak az értékei, vagy pedig
– a függvény értékének meghatározásához szükség van a független változók értékén kívül további adatokra, "rejtett paraméterekre" is,
a számítógép működésének műszaki alapját képező logikai hálózatok két típusáról beszélhetünk:

kombinációs logikai hálózat: a kimenetet egyértelműen meghatározzák a logikai hálózat bemenetei, azaz a hálózat bemenetét jelentő logikai értékek adott "kombinációi";
sorrendi vagy szekvenciális logikai hálózat: a kimenetet nem határozzák meg egyértelműen a logikai hálózat bemenetei; a kimenet egyértelmű meghatározásához a bemeneti kombinációk mellett szükség van további adatokra (ún. szekunder adatokra vagy "kombinációkra") is.

A szekunder kombinációkat a sorrendi hálózat állapotainak is nevezik (vö. Arató 1996: 140).

Egy sorrendi logikai hálózatot egy olyan kombinációs hálózatnak tekinthetünk, amely visszacsatolást tartalmaz, vagyis a kimenet egyértelmű meghatározásához ismernünk kell a bemeneti kombinációk mellett olyan szekunder értékeket ("kombinációkat") is, amelyeket a hálózat korábbi működése során állított elő (és közvetlenül vagy tárolás után visszacsatolta ezeket az értékeket a hálózat bemenetére).
A sorrendi hálózatok két fajtáját különböztetjük meg:

aszinkron sorrendi hálózatok: a visszacsatolás közvetlenül történik (vagy tárolók közbeiktatásával, vö. Fodor-Nagy 1982: 105); ezek a hálózatok a bemeneti jelek megváltozására azonnal reagálnak (eltekintve az áramkörök késleltetésétől);
szinkron sorrendi hálózatok: a visszacsatolás tárolók közbeiktatásával történik, amelyek tárolják a hálózat belső állapotait; a hálózat működését órajelek vezérlik, amelyek szinkronizálják az egyes áramkörök működését.

Aszinkron hálózatra példa egy két állapotú statikus tárolóáramkör (ún. flip-flop); szinkron hálózatra pedig egy soros bináris összeadó, amely meghatározott ütemezésben kapja meg az összeadandók adott helyi értékű bináris számjegyeit, állítja elő az egyes helyi értékeken képződő átvitelt, és az összeg megfelelő helyi értékű bináris számjegyeit (vö. Arató 1996: 17-18, 139-141 et passim; Könyves Tóth 1982: 105-106 et passim). Jegyezzük meg, hogy a számítógép központi egysége olyan logikai rendszernek tekinthető, amely tartalmaz mind kombinációs hálózatokat, mind aszinkron és szinkron sorrendi hálózatokat.
A továbbiakban lássunk néhány példát aszinkron sorrendi hálózatokat megvalósító áramkörökre.

1. példa: R-S flip-flop (NOR kapukkal megvalósítva)
Az R-S flip-flop egy 1 bites tárolóáramkör, amelyet NOR kapukkal a következőképpen alakíthatunk ki:
⇋
Az ábra jelölései:

S: a flip-flop bemenete; S=1 esetén 1 érték beírása (Set)
R: a flip-flop bemenete; R=1 esetén 0 érték beírása (Reset)
Q': a flip-flop kimenete; a flip-flop által tárolt érték

Q: a flip-flop Q' kimenete visszacsatolva az S bemenetű NOR kapu másik bemenetére (azaz Q←Q'; stabil állapotban Q=Q' teljesül)

Q': a flip-flop második kimenete; a flip-flop kimenetének, azaz a flip-flop által tárolt értéknek (Q') a negáltja (azaz Q'=⌝Q' teljesül)

Q: a flip-flop Q' kimenete visszacsatolva az R bemenetű NOR kapu másik bemenetére (azaz Q←Q'; stabil állapotban Q=Q' teljesül)

Mivel a Q' és Q' kimeneteket visszacsatoljuk (Q←Q', Q←Q'), a visszacsatolt értékek a flip-flop R és S bemenetei mellett szekunder adatokként befolyásolják a flip-flop Q' és Q' kimeneteit.
Ha a Q'=Q' (azaz Q←Q') visszacsatolást nem vesszük figyelembe, az R-S flip-flop működését leíró logikai függvény az alapműveletekkel
    Q'= f(R,S,Q)= S∨(⌝R∧Q)
módon írható fel. A függvényt NAND művelettel megvalósítva^⇒ a
    Q'= (S NAND S) NAND ((R NAND R) NAND Q)= S∨(⌝R∧Q)
függvényt kapjuk. Ha a függvényt NOR művelettel valósítjuk meg^⇒, ez például a
    Q'= R NOR (S NOR Q)= (⌝R∧S)∨(⌝R∧Q)
függvénnyel lehetséges.
Jegyezzük meg, hogy a NOR művelettel kifejezett függvény R=1 és S=1 esetén eltérő eredményt szolgáltat, mint a másik két függvény.
Írassuk ki a fenti logikai függvények igazságtáblázatát egy JavaScript program segítségével:
// R-S flip-flop igazságtáblázatai (visszacsatolás nélkül)

function neg(x) {
 var a=Boolean(x);
 var c=!a;
 return Number(c);
 }

function kon(x,y) {
 var a=Boolean(x), b=Boolean(y);
 var c=a && b;
 return Number(c);
 }

function dis(x,y) {
 var a=Boolean(x), b=Boolean(y);
 var c=a || b;
 return Number(c);
 }

function nand(x,y) {
 var a=Boolean(x), b=Boolean(y);
 var c=!(a && b);
 return Number(c);
 }

function nor(x,y) {
 var a=Boolean(x), b=Boolean(y);
 var c=!(a || b);
 return Number(c);
 }

writeln("R"+" " +"S"+" "+"Q"+"  "+
        "S∨(⌝R∧Q)"+" "+"(R NOR (S NOR Q))"+" "+
        "(⌝S NAND (⌝R NAND Q))");
writeln("------------------------------"+
        "--------------------------");

for(i=0;i<=1;i++) {
 for(j=0;j<=1;j++) {
  for(k=0;k<=1;k++) {
   var m=kon(neg(i),k);
       m=dis(j,m);
   var n=nor(j,k);
       n=nor(i,n);
   var s=nand(j,j);
   var p=nand(i,i);
       p=nand(p,k);
       p=nand(s,p);
   writeln(i+" " +j+" "+k+"      "+m+
           "             "+n+
           "                   "+p);
   }
  }
 }

writeln("------------------------------"+
        "--------------------------");
A program képernyőképe a következő:

A visszacsatolásokat figyelembe véve a NOR műveletekkel megvalósított R-S flip-flop kimeneti értékeit a következő algoritmussal számíthatjuk ki:

Kiindulásként az R S és Q bemenetekhez rendeljünk adott értékeket, azaz kezdetben ne vegyük figyelembe a Q←Q' visszacsatolást; tároljuk Q kezdeti értékét (Q₀=Q); tároljuk a kiszámítási ciklusok számát is (n=0)
Számítsuk ki Q' értékét a
Q' = ⌝(S∨Q)
képlet alapján
vegyük figyelembe a Q ← Q' visszacsatolást, és Q=Q' feltétel mellett számítsuk ki Q' értékét a
Q' = ⌝(R∨Q)
képlet alapján
rögzítsük, hogy egy számítási ciklus véget ért (n=n+1); ezután tároljuk Q kiszámított értékét (Q_n=Q'), vegyük figyelembe a Q ← Q' visszacsatolást, és
folytassuk az algoritmust az alábbiak szerint:

ha Q értéke a számítási ciklus után megegyezik az előző értékével (Q_n=Q_n−1), álljunk meg (stabil állapothoz jutottunk)
ha n=1 és Q értéke az első számítási ciklus után nem egyezik meg az előző értékével (Q₁≠Q₀), folytassuk az algoritmust a 2. lépéstől kezdve (átmeneti állapothoz jutottunk)
ha n=2 és Q értéke a második számítási ciklus után megegyezik a kezdeti értékével (Q₂=Q₀), ne folytassuk tovább az algoritmust, mert Q értéke innentől kezdve állandóan váltakozni fog (instabil állapothoz jutottunk)

Az igazságtáblát ezek után úgy tudjuk megkonstruálni, hogy az S és R bemenetek lehetséges értékei mellett a Q kimenet lehetséges kezdeti értékeit is felvesszük a táblázatba, és ennek megfelelően számítjuk ki az R-S flip-flop kimenetét.
A fenti algoritmus alapján az R-S flip-flop igazságtáblázata a következő lesz:
R-S flip-flop
R S Q=Q_n Q'=Q_n+1
0 0 0 0 (=Q_n) Q értéke változatlan (előzőleg beállított 0 vagy 1 állapot tárolása)
1 1 (=Q_n)
0 1 0 1 SET (1 beállítása, "flip")
1 1 (=Q_n)
1 0 0 0 (=Q_n) RESET (0 beállítása, "flop"; a flip-flop törlése)
1 0
1 1 0 0 (=Q_n) (tiltott állapot, mivel mindkét kimenet 0 értékű lesz)
1 0

Az R-S flip-flop NOR kapukkal megvalósított formájában a flip-flop két kimenetétől elvárjuk, hogy egymás negáltjai legyenek (azaz Q=⌝Q teljesüljön). Az R-S flip-flop NOR kapus megvalósításában ez S=1 és R=1 esetén nem áll fenn (mivel Q=Q teljesül), ezért ezt az állapotot nem engedjük meg.
Az R-S flip-flop NOR kapukkal megvalósított formájában az S=1 és R=1 kombináció tiltott.

Az R-S flip-flop teljes igazságtáblázata a korábban megismert kiszámítási algoritmus alapján a következő lesz, ha NOR kapukkal valósítjuk meg és a visszacsatolásokat is feltüntetjük:

R-S flip-flop (NOR)
S R Q ⌝(S∨Q)=Q'→Q ⌝(Q∨R)=Q'→Q ellenőrzés: Q=Q'?

Jegyezzük meg, hogy mivel R=0 és S=0 bemenetek mellett az R-S flip-flop a korábban beállított logikai értéket tárolja, a bemeneteket egy órajellel kapuzva^⇒ csak akkor változhat meg az R-S flip-flop állapota, ha ezt az órajel engedélyezi.
Ha az R-S flip-flop bemenetét egy órajellel (C) vezéreljük, egy ún. szinkron R-S flip-flop áramkört kapunk:

Ha pedig a szinkron R-S flip-flop 'R' bemenetét egy inverter (azaz NOT kapu) segítségével állítjuk elő, egy ún. D flip-flop áramkört kapunk:

A D flip-flop előnye, hogy megszünteti az R-S flip-flop tiltott állapotát (vagyis nem fordulhat elő az R=1 és S=1 bemenet).

2. példa: R-S flip-flop (NAND kapukkal megvalósítva)
Az R-S flip-flopot megvalósíthatjuk NAND kapukkal is:

Az R-S flip-flop igazságtáblázata a következő:
R-S flip-flop (NAND)
S R y q=⌝(⌝R∧y) Y=⌝(S∧q) (ellenőrzés)

Ha ebben a megvalósításban is két kimenetet szeretnénk (mint a NOR kapukkal megvalósított R-S flip-flop esetén), akkor a tiltott S=1 és R=1 kombinációk elkerülése érdekében célszerű az Y kimenetből egy inverter segítségével közvetlenül előállítani a negált ⌝Y értéket.
Vegyük észre, hogy ha megengedjük az S=1 és R=1 kombinációt, akkor az Y kimenet megegyezik az S=1 és R=0 kombinációnak megfelelő bemenettel, azaz 1 tárolása történik meg. (Ebben az esetben a flip-flopot S-dominánsnak nevezzük, mert ha S=1 teljesül, akkor az R bemenet értékétől függetlenül a flip-flop tárolni fogja az 1 értéket.)

3. példa: Master-Slave J-K flip-flop
A korábban tárgyalt R-S flip-flop áramkörök "hátránya, hogy az órajel ideje alatt a bemeneti vezérlés megváltozása megjelenik a kimeneten. A jelenségre azt szokták mondani, hogy a flip-flop átlátszik. Ez azt jelenti, hogy tárolónk egy óraütemben több állapotváltozást is végrehajthat. Az ebből eredő hátrány összetett hálózatokban jelentkezik, amikor ugyanazon órajellel több, egymást vezérlő tárolót kapuzunk" (Takács 1995: 40).
Ezt a hátrányt küszöböli ki a master-slave (MS) J-K flip-flop, amely egy kétütemű, élvezérelt tároló. A J-K flip-flop úgy működik, hogy
– az órajel megjelenésekor, azaz az órajel "felfutó" élének hatására a bemeneti jelet elhelyezi egy ún. előtárba (master);
– az órajel eltűnésekor, azaz az órajel "lefutó" élének hatására az előtárban tárolt jelet átírja egy ún. főtárba (slave).
A főtárban tárolt információ fog megjelenni a flip-flop kimenetén. (vö. Takács 1995: 40-41)
Az MS J-K flip-flop egy 1 bites tárolóáramkör, amelyben két, egymás után következő R-S flip-flopot egy órajellel vezérlünk. Az MS J-K flip-flop elvi kialakítása a következő:

A J-K flip-flop igazságtáblázata a következő:
J-K flip-flop
J K Q_n+1 Q_n+1
0 0 Q_n Q_n
0 1 0 1
1 0 1 0
1 1 Q_n Q_n

Jegyezzük meg, hogy a J-K flip-flop 'J' bemenete az R-S flip-flop 'S' bemenetének, a J-K flip-flop 'K' bemenete pedig az R-S flip-flop 'R' bemenetének felel meg.
Az MS J-K flip-flop igazságtáblázata nyilvánvalóan függ a flip-flopban levő R-S flip-flopok által tárolt értékektől (azaz az MS J-K flip-flop belső állapotaitól). Az ábrából látszik, hogy az MS J-K flip-flop működése során az órajel hatására a Master R-S flip-flop tartalma mindig átmásolódik a Slave R-S flip-flopba. Az MS J-K flip-flop által tárolt értéket a Slave R-S flip-flop tartalma adja, amely a tárolt információ átírása után megegyezik a Master R-S flip-flop tartalmával. (Jegyezzük meg, hogy ha ez nem állna fenn, azaz a kiinduló állapotban a Slave R-S flip-flop és a Master R-S flip-flop tartalma különböző lenne, az MS J-K flip-flop hibásan működne.)
Az MS J-K flip-flop igazságtáblázatának C=1 és C=0 értékeknek megfelelő értékeit attól függően kaphatjuk meg, hogy milyen értékeket jelentenek a J és K bemenetek, a Master flip-flop által tárolt y2 tartalom, és a Slave flip-flop által tárolt y1 tartalom. A beállított paraméterek különböző értékei mellett egy teljes óraciklus után a J-K flip-flop állapotai egyszerűen kiszámíthatók.
Az alábbi táblázatban a paraméterek értékére kattintva a megfelelő értékek beállíthatók:

a J-K flip-flop paramétereinek beállítása
J K y2 y1=Q_n
0 0 0 0

J K C q←y1 S_(m) R_(m) y2 S_(s) R_(s) y1=Q_n+1

A táblázatban
– az órajel felfutó ágának az órajel C=1 értéke felel meg;
– az órajel lefutó ágának az órajel C=0 értéke felel meg;
– a stabil állapotot az jelenti, amikor a visszacsatolt 'y1' jel kezdeti értéke (Q_n) egy teljes óraciklus után megegyezik az 'y1' jel számított értékével (Q_n+1).
Figyeljük meg, hogy hogyan változnak az MS J-K flip-flop (J-K-y2-y1) állapotai. Az állapotok stabilak, ha a Master FF és Slave FF kezdeti állapotai megegyeznek. Ezt a továbbiakban feltételezzük. (A teljesség kedvéért megadjuk az y2≠y1 eseteket is.)

J=0 és K=0 esetén az előzőekben beállított értéket (y2) tároló állapotot kapunk:

0000→0000
0011→0011
0010→0011→0011 (ez egy teljes óraciklus után egy óracikluson keresztül hibás működést eredményezne)
0001→0000→0000 (ez egy teljes óraciklus után egy óracikluson keresztül hibás működést eredményezne)

J=1 és K=0 esetén 1 értéket beállító állapotot kapunk:

1000→1011→1011
1011→1011
1010→0011→0011
1001→1000→1011→1011 (ez egy teljes óraciklus után egy óracikluson keresztül hibás működést eredményezne)

J=0 és K=1 esetén 0 értéket beállító állapotot kapunk:

0100→0100
0111→0100→0100
0101→0100→0100
1010→0111→0100→0100 (ez egy teljes óraciklus után egy óracikluson keresztül hibás működést eredményezne)

J=1 és K=1 esetén minden teljes óraciklusban az előzőekben beállított értéket (y2) invertáló állapotot kapunk, és a flip-flop sosem kerül stabil állapotba ("oszcillál"):

1100→1111→1100→...
1111→1100→1111→...
1101→1100→1111→...
1110→1111→1100→...

A fenti példák esetében "ideális" áramköröket tételeztünk fel, amelyek késleltetés nélkül működnek. A gyakorlatban azonban számos probléma merülhet fel (például amiatt, mert az órajel véges időtartamú, és az áramkörök véges működési sebességgel rendelkeznek, ennek megfelelően meghatározott időre van szükségük egy művelet elvégzéséhez).

R-S flip-flop
R	S	Q=Q_n	Q'=Q_n+1
0	0	0	0 (=Q_n)	Q értéke változatlan (előzőleg beállított 0 vagy 1 állapot tárolása)
1	1 (=Q_n)
0	1	0	1	SET (1 beállítása, "flip")
1	1 (=Q_n)
1	0	0	0 (=Q_n)	RESET (0 beállítása, "flop"; a flip-flop törlése)
1	0
1	1	0	0 (=Q_n)	(tiltott állapot, mivel mindkét kimenet 0 értékű lesz)
1	0

R-S flip-flop (NOR)
S	R	Q	⌝(S∨Q)=Q'→Q	⌝(Q∨R)=Q'→Q	ellenőrzés: Q=Q'?

R-S flip-flop (NAND)
S	R	y	q=⌝(⌝R∧y)	Y=⌝(S∧q)	(ellenőrzés)

J-K flip-flop
J	K	Q_n+1	Q_n+1
0	0	Q_n	Q_n
0	1	0	1
1	0	1	0
1	1	Q_n	Q_n

Logikai rendszerek vezérlése

Korábban bevezettük a logikai rendszer^⇒ fogalmát, amelyben az egyes részfeladatokat funkcionális egységek végzik, és ezek vezérlését a vezérlő egység biztosítja.
Egy logikai rendszer működését legegyszerűbben úgy képzelhetjük el, hogy az egyes funkcionális egységek, ill. az ezeket megvalósító áramkörök
(1) a bemenetüket meghatározott tároló egységekből olvassák ki (pl. X, Y),
(2) majd végrehajtják a nekik megfelelő műveleteket (például egy kombinációs hálózattal), és
(3) a kimenetüket meghatározott tároló egységekbe írják be (Z←X op Y).
A sorrendi működés például a bemeneteket (ill. a belső állapotokat és/vagy a kimeneteket) tároló flip-flopok vezérlésével valósulhat meg, amelyeknek a működését meghatározott vezérlő jelekkel engedélyezhetjük vagy tilthatjuk.
A fentieket formálisan egy
    /P*Q*.../ Z←X op Y
szerkezetű mikroutasítással írhatjuk le, ahol P, Q, ... a vezérlőjeleknek megfelelő logikai változók (és például a 'P' logikai változó jelenthet egy órajelet, ill ennek egy fázisát), a mikroutasítás /P*Q*.../ feltételrészében (vagy címkéjében) szereplő '*' művelet pedig a P, Q, ... logikai változók közötti konjunkciót (∧) jelöli.
Egy tároló "megnyitását" egy áramkör számára például úgy valósíthatjuk meg, hogy az áramkör minden egyes bemenetét a működést engedélyező vezérlő jellel vagy jelekkel közösen egy AND kapu bemenetére kapcsoljuk ("kapuzzuk").
Ha az áramkör "kapuzott" bemenetén az egyik vezérlő jel egy órajel, akkor egy ún. várakozási ciklust alakíthatunk ki. Ekkor az áramkör minden óraciklusban "megvizsgálja" a bemenetet, amit egy vagy több másik, az áramkörtől függetlenül működő funkcionális egység állíthat be. A várakozási ciklus ezáltal lehetővé teszi az egyes funkcionális egységek (pl. memóriaegység, I/O egységek stb.) aszinkron vezérlését.
A rendszer logikai tervezésekor az egyes funkcionális egységeket tekinthetjük fekete dobozoknak, amelyekhez meghatározott logikai feltételeket (ún. címkéket) rendelünk hozzá. A címkékben szereplő logikai változók adatok, címek és vezérlő jelek egyaránt lehetnek. (Ha a címkékben csak órajelek szerepelnek, szinkron működésről, ha az órajeleken kívül más vezérlő jelek is megjelennek, aszinkron működésről beszélhetünk.) A címkék az egyes funkcionális egységek működését vezérlik.
A címkék olyan logikai feltételek, amelyekben meghatározott logikai változók állnak egymással logikai kapcsolatban. A rendszer működésének "logikáját"
   – a címkékben szereplő logikai változók értékének előállítása, és ezek függvényében
   – a címkéknek megfelelő vezérlő jelek előállítása
határozza meg.

Mivel a címkékben számos logikai változó szerepelhet, ennek megfelelően egy vezérlő egységet egy olyan logikai hálózattal valósíthatunk meg, amely
– több bemenettel rendelkezik (ezek lehetnek például órajelek, a funkcionális egységek állapotát megadó jelek, egyes I/O egységek megszakításkérései stb.) és
– minden kimenete egy adott címkének megfelelő vezérlő jelet állít elő.

A	B	C=C_in	S_tmp	C_tmp	S	C_sec	C_out
0	0	0	0	0	0	0	0
0	1	0	1	0	1	0	0
1	0	0	1	0	1	0	0
1	1	0	0	1	0	0	1
0	0	1	0	0	1	0	0
0	1	1	1	0	0	1	1
1	0	1	1	0	0	1	1
1	1	1	0	1	1	0	1

A	B	C=C_in	S_tmp	C_tmp	S	C_sec	C_out
0	0	0	0	0	0	0	0
0	1	0	1	0	1	0	0
1	0	0	1	0	1	0	0
1	1	0	0	1	0	0	1
0	0	1	0	0	1	0	0
0	1	1	1	0	0	1	1
1	0	1	1	0	0	1	1
1	1	1	0	1	1	0	1

A digitális számítógépek működésének alapjai

A	B	C=C_in	S_tmp	C_tmp	S	C_sec	C_out
0	0	0	0	0	0	0	0
0	1	0	1	0	1	0	0
1	0	0	1	0	1	0	0
1	1	0	0	1	0	0	1
0	0	1	0	0	1	0	0
0	1	1	1	0	0	1	1
1	0	1	1	0	0	1	1
1	1	1	0	1	1	0	1