2.4 Kombinatorisk logikk

Kretser som lever i nuet

Noen elektroniske kretser har hukommelse – de husker hva som skjedde tidligere. Men en stor familie av kretser gjør det ikke. De lever helt i nuet: utgangen bestemmes utelukkende av hvilke verdier som ligger på inngangene akkurat nå. Endrer du inngangene, endrer utgangen seg umiddelbart, uten å bry seg om fortiden. Disse kaller vi kombinatoriske kretser.

Det kan høres begrenset ut, men nettopp disse minneløse kretsene er byggesteinene i alt digitalt utstyr. Av logiske porter satt sammen på smarte måter får vi velgere som plukker ut riktig signal, dekodere som tenner riktig lampe, og – mest imponerende – adderere som faktisk kan legge sammen tall. Det er slik en datamaskin regner.

I dette kapittelet skal vi møte de viktigste kombinatoriske kretsene. Vi starter med multiplekseren og dekoderen, to nyttige velgere. Deretter bygger vi opp halvadderen og heladderen, og ser hvordan de kan kjedes sammen for å legge sammen flersifrede binærtall – fra første prinsipp til et ferdig regnestykke.

Velgere: multiplekser og dekoder

La oss begynne med multiplekseren, ofte forkortet MUX. Den er rett og slett en digital velger: av flere innganger sender den én videre til utgangen, alt etter hva du ber om. Den enkleste er en 2-til-1 MUX, med to datainnganger $D_0$ og $D_1$, en velgerinngang $S$, og en utgang $Y$. Når $S = 0$, slipper den $D_0$ gjennom; når $S = 1$, slipper den $D_1$. Dette fanges i ett boolsk uttrykk: $Y = \bar{S} \cdot D_0 + S \cdot D_1$.

Tenk på et system med to temperatursensorer. Du kobler sensor A til $D_0$, sensor B til $D_1$, og en bryter til $S$. Med bryteren av leses sensor A, med bryteren på leses sensor B – multiplekseren fungerer som en elektronisk omkobler. Vil du velge mellom flere, bruker du en 4-til-1 MUX med to velgerinnganger $S_1 S_0$ som danner et 2-bits tall: 00 velger $D_0$, 01 velger $D_1$, 10 velger $D_2$, og 11 velger $D_3$.

Den motsatte funksjonen har dekoderen. I stedet for å velge én av mange innganger, tar den et binærtall inn og aktiverer én av mange utganger. En 2-til-4 dekoder har innganger $A_1 A_0$ og fire utganger $Y_0$ til $Y_3$, der bare én er høy om gangen – den som svarer til tallet på inngangen. Uttrykkene følger rett av tabellen: $Y_0 = \bar{A_1} \cdot \bar{A_0}$, $Y_1 = \bar{A_1} \cdot A_0$, $Y_2 = A_1 \cdot \bar{A_0}$ og $Y_3 = A_1 \cdot A_0$. Dekodere brukes blant annet til å velge riktig minnecelle, styre et sjusegment-display eller peke ut en bestemt enhet i et datasystem.

Halvadderen – å legge sammen to biter

Nå til kretsene som virkelig regner. Hvordan kan logiske porter legge sammen tall? Vi starter i det små, med å legge sammen to enkeltbiter, A og B. I binær har vi fire muligheter: $0+0=0$, $0+1=1$, $1+0=1$, og $1+1$ – som blir 2, altså $10$ i binær. Det siste tilfellet trenger to siffer, og det er nettopp her det blir interessant.

Kretsen som gjør dette kalles en halvadder. Den har to utganger: en sum-bit $S$ og en mente-bit $C$ (carry). Ser vi på sannhetstabellen, oppdager vi et mønster. Summen $S$ er 1 nøyaktig når A og B er forskjellige – det er XOR-funksjonen, eksklusiv ELLER, skrevet $S = A \oplus B$. Menten $C$ er 1 bare når begge er 1 – det er AND, $C = A \cdot B$.

La oss sjekke med $1 + 1$: $S = 1 \oplus 1 = 0$ og $C = 1 \cdot 1 = 1$. Sammen gir det $C S = 10$, altså 2 i binær. Akkurat riktig. Med to enkle porter, en XOR og en AND, har vi laget en krets som faktisk adderer.

Men hvorfor heter den «halv»-adder? Fordi den mangler noe viktig: den har ikke plass til en mente som kommer inn fra et tidligere siffer. Når du legger sammen flersifrede tall, drar du jo en mente videre fra én kolonne til neste, akkurat som i vanlig addisjon. For å håndtere det trenger vi en mer komplett krets.

Heladderen – og hvordan tall legges sammen

For å legge sammen flersifrede binærtall trenger vi en heladder. Forskjellen fra halvadderen er en ekstra inngang: $C_{in}$, menten som kommer inn fra forrige siffer. Heladderen har altså tre innganger – A, B og $C_{in}$ – og to utganger, sum $S$ og utgående mente $C_{ut}$.

Boolsk blir summen en XOR av alle tre: $S = A \oplus B \oplus C_{in}$. Den utgående menten er litt mer sammensatt: $C_{ut} = A \cdot B + C_{in} \cdot (A \oplus B)$. Med ord: det blir mente enten hvis både A og B er 1, eller hvis det allerede kom en mente inn samtidig som A og B er forskjellige. Praktisk nok kan en heladder bygges av to halvaddere og en OR-port.

Nå har vi alt vi trenger for å legge sammen ekte tall. La oss regne $11_2 + 01_2$, som er $3 + 1 = 4$. Vi begynner med det minst signifikante bitet, posisjon 0, og bruker en halvadder fordi det ikke kommer noen mente inn ennå: $A_0 = 1$, $B_0 = 1$ gir $S_0 = 0$ og en mente $C_0 = 1$. Denne menten drar vi videre. På posisjon 1 bruker vi en heladder med $A_1 = 1$, $B_1 = 0$ og $C_{in} = 1$: summen blir $S_1 = 1 \oplus 0 \oplus 1 = 0$, og menten $C_{ut} = 1 \cdot 0 + 1 \cdot (1 \oplus 0) = 1$. Setter vi resultatet sammen, får vi $C_{ut} S_1 S_0 = 100_2 = 4$ – stemmer. Slik kobler vi én halvadder og flere heladdere i kjede, og kan legge sammen så store tall vi vil, akkurat som regneenheten i en datamaskin.

Oppsummering

Vi har bygd opp de kombinatoriske kretsene – de minneløse kretsene der utgangen bare avhenger av inngangene akkurat nå. Multiplekseren velger én av flere innganger ($Y = \bar{S} \cdot D_0 + S \cdot D_1$ for den enkleste), mens dekoderen gjør det motsatte og aktiverer én av flere utganger ut fra et binærtall.

Deretter så vi hvordan logiske porter kan regne. Halvadderen legger sammen to biter med $S = A \oplus B$ og $C = A \cdot B$, men mangler inngang for innkommende mente. Heladderen løser dette med $S = A \oplus B \oplus C_{in}$ og $C_{ut} = A \cdot B + C_{in} \cdot (A \oplus B)$, slik at vi kan kjede én halvadder og flere heladdere sammen og legge sammen flersifrede binærtall – akkurat slik regneenheten i en datamaskin gjør det.