Kombinatoriske kretser

En kombinatorisk krets har utgang som er en ren funksjon av de nåværende inngangene – det finnes ingen tilstand, ingen hukommelse. Designprosessen er: (1) Definer problem, (2) Bygg sannhetstabell, (3) Utled boolsk uttrykk (SOP eller POS), (4) Forenkle (Karnaugh-kart eller algebra), (5) Implementer med porter.

Sum-of-Products (SOP) og Product-of-Sums (POS)

SOP (kanonisk mintermsform): For hver rad i sannhetstabellen der utgangen er 1, skriv et AND-produkt av alle inngangsvariabler (negert hvis 0, ikke-negert hvis 1). Summer alle produktene med OR.
POS (kanonisk maxtermsform): For hver rad der utgangen er 0, skriv et OR-uttrykk (negert hvis 1, ikke-negert hvis 0). Multipliser alle summene med AND.

Karnaugh-kart (K-kart)

Karnaugh-kartet er et visuelt verktøy for systematisk forenkling. Radene og kolonnene følger Gray code (bare én bit endrer seg mellom nabofelter). Sirkl inn grupper av 1-er:

Grupper må ha størrelse $2^k$ (1, 2, 4, 8, 16 …)
Grupper skal være så store som mulig – større grupper gir færre variabler i produkttermen.
Felter i kantene «wrapper» (kartet er sylinder): venstre kant er nabo med høyre kant.
En variabel elimineres fra en gruppe hvis den veksler innen gruppen.
Dekk alle 1-ere minst én gang med færrest mulig grupper.

Don't-care ($\times$): Kombinasjoner som aldri vil opptre kan markeres som don't-care og brukes fritt til å førstørre grupper.

Multipleksere (MUX) og demultipleksere

En $2^n$-til-1 MUX velger én av $2^n$ datalinjer basert på $n$ valgbiter (select). En 4-til-1 MUX med select $S_1 S_0$ og innganger $D_0$–$D_3$: $Y = \overline{S_1}\overline{S_0}D_0 + \overline{S_1}S_0 D_1 + S_1\overline{S_0}D_2 + S_1 S_0 D_3$. MUX kan brukes til å implementere vilkårlige logiske funksjoner ved å koble sannhetstabellenhetene til datainngangene.

Dekodere og enkodere

En $n$-til-$2^n$ dekoder aktiverer én av $2^n$ utgangslinjer basert på $n$ inngangsbiter. Brukes blant annet til adressedekoding i minne. En enkoder gjør det omvendte: $2^n$ innganger → $n$ utgangsbiter.

Ripple-carry adder og carry-lookahead

En full adder (FA) legger til tre biter ($A$, $B$, $C_{in}$) og gir sum $S$ og carry-ut $C_{out}$: $S = A \oplus B \oplus C_{in}$, $C_{out} = AB + C_{in}(A \oplus B)$. En ripple-carry adder kjeder FA-er i serie – enkel, men treg fordi carry-signalet forplanter seg gjennom alle ledd. En carry-lookahead adder beregner alle carry-signaler parallelt ved hjelp av generate ($G_i = A_i B_i$) og propagate ($P_i = A_i \oplus B_i$).

Eksempel: 3-variabels K-kart

Sannhetstabell for $F(A,B,C)$ med mintermer $\{1,3,5,7\}$ (alle odde). K-kart med Gray code-rekkefølge (BC: 00, 01, 11, 10):

     BC
A  | 00 01 11 10
0  |  0  1  1  0
1  |  0  1  1  0

Gruppe: de fire 1-ene i kolonnene 01 og 11 – $A$ varierer (0 og 1), $B$ varierer (0 og 1), $C = 1$ alltid. Resulterende term: $C$. Forenkling: $F = C$.

Eksempel: Maksimal forenkling (flervalg-stil)

To faste eksamenstyper: (1) avlese funksjonsuttrykk fra et portdiagram, og (2) forenkle et uttrykk maksimalt. Begge er flervalg verdt 2–3 poeng hver, hver eksamen.

Forenkle $F = (A+B)(A+\overline{B})(\overline{A}+C)$.
Distribuér de to første: $(A+B)(A+\overline{B}) = A + B\overline{B} = A + 0 = A$.
Da: $F = A(\overline{A}+C) = A\overline{A} + AC = 0 + AC = AC$.
Svar: $F = AC$.

Forenkle $F = AB + \overline{A}C + BC$ (konsensusteorem). Termen $BC$ er en konsensus av $AB$ og $\overline{A}C$ og kan strykes: $F = AB + \overline{A}C$.

Studieguide: Kombinatorisk logikk

Studieguide: Kombinatorisk logikk