Dit zijn de
opdrachten voor III voor vrijdagmiddag van de eerste week.
Achtergrond
Logische
schakelingen voor ‘EN’, ‘OF’ en ‘NIET’ zijn de uiteindelijke bouwstenen van
computers.
|
|------| |------| |------|
in1 --->| | in1 --->| | | | |
EN |---> uit | OF
|----> uit in --->| NIET
|--> uit
in2 --->| | in2 --->| | | | |------| |------| |------| |
Dat deze schakelingen
in computers met elektronica gerealiseerd zijn, is (voor ons) niet van belang.
Je kunt logische schakelingen ook mechanisch of hydraulisch
realiseren.
Ons gaat het
vooral om de logische begrippen die een rol spelen. Dezelfde begrippen die een
rol spelen op dit allerlaagste niveau kom je namelijk overal in de informatica
en informatiekunde (en zelfs daarbuiten) tegen.
Verder maak je met
deze opdrachten in een hele concrete context kennis met activiteiten die
volgende week aan bod zullen komen, zoals
·
het
beschrijven en begrijpen wat een systeem moet doen,
·
het
ontwerpen en realiseren van een systeem (en de standaard verdeel-en-heersstrategie),
·
het
nagaan (voor jezelf) of het werkt, en
·
het
uitleggen (aan een ander) dat het werkt.
Leerdoel
Na het maken van
de opdrachten kun je
·
zelf
een simpele schakeling bouwen,
·
uitleggen
hoe een gegeven ingewikkeldere schakeling, bijvoorbeeld voor optellen van
binaire getallen, werkt,
·
uitleggen
hoe je een ingewikkeldere schakeling, zoals een aritmetische eenheid (ALU), zou
kunnen bouwen,
·
op
verschillende manieren beschrijven (specificeren) wat een schakeling doet,
bijvoorbeeld als tabel, als informele beschrijving in het Nederlands, of als
logische formule met ‘en’, ‘of’ et cetera.
Als je een
computer ter beschikking hebt dan kun je bij deze opdrachten gebruik maken van
deze simulator
van digitale circuits, maar dat hoeft niet.
Opdracht 1
a.
Bouw
een schakeling met twee inputs en één output die kijkt of de twee inputs gelijk
zijn, dat wil zeggen die precies dan een 1 als uitvoer geeft als de twee inputs
gelijk zijn.
Hint: Hoe doe je nou zoiets? Smaken verschillen hier.
·
Eén
aanpak is om de inputs en output een (suggestieve) naam te geven en dan na te
denken over specificaties in natuurlijke taal met behulp van de woorden ‘en’, ‘niet’
en ‘of’, bijvoorbeeld ‘zijn_gelijk als a en b allebei waar, of...’ (zie ook opdracht 1b).
|
|-----------| a
--------------> | | b
--------------> | EQUAL |
-------> zijn_gelijk |-----------| |
·
Je
kunt ook gewoon wat proberen, vervolgens de waarheidstabel voor je probeersel maken om te kijken welke gevallen misgaan en dan die
gevallen repareren door je probeersel uit te breiden of te veranderen.
·
Een
andere aanpak is om eerst de waarheidstabel te maken voor de component die je
wilt maken. Je kunt dan kijken of deze tabel lijkt op een tabel die je al hebt.
Je kunt ook kijken voor welke combinaties van inputs je een 1 moet produceren
als output.
b.
Schrijf
je oplossing voor 1a op in woorden, gebruik makend van de voegwoorden ‘en’,
‘of’ en ‘niet’. Dat wil zeggen label de ingangen van de
schakeling (bijvoorbeeld a, b, c...) en beschrijf daarna de uitvoer in termen
van deze labels en de voegwoorden ‘en’, ‘of’ en ‘niet’; deze beschrijving wordt
dus iets in de trant van ‘(a en b) of (a en (niet b))’.
c.
Bouw
een schakeling met twee inputs en één output die 1 oplevert als precies één van
de inputs 1 is (oftewel de ‘XOR’). Geef ook weer een
beschrijving in woorden.
d.
Bouw
een schakeling met drie inputs en één output die 1 oplevert als precies één van
de inputs 1 is. (Pas op: als je denkt dat je deze kunt maken met twee ‘XOR’
doosjes heb je het waarschijnlijk fout!) Geef ook weer een beschrijving in
woorden.
Opdracht 2
a.
Maak
een schakeling ‘A2’ die een selectie-invoerkanaal a0 gebruikt om één van de twee data-invoerkanalen in0 en in1 uit te kiezen om door
te geven naar het uitvoerkanaal out.
Met andere woorden, als a0 1 is
moet out de waarde van in0 hebben en als a0 0 is moet out de waarde van in1
hebben.
|
|-----------| in0
--------------> | | in1 -------------->
| A2 | -------> out
|-----------|
|
|
a0
|
b.
Maak
met alleen DRIE ‘A2’ doosjes en niets anders een schakeling ‘A4’ die twee selectie-invoerkanalen a0 en a1
gebruikt om één van de vier data-invoerkanalen in0, ..., in3 uit te kiezen om door te geven naar uitvoerkanaal
out:
|
|--------------| in0
--------------> | | in1
--------------> | | in2
--------------> | A4 | -------> out in3
--------------> | |
|--------------|
| |
| | a0 a1 |
Nb. Dus geen ‘EN’, ‘OF’ of ‘NIET’ poorten gebruiken, maar enkel ‘A2’
doosjes. Je hoeft natuurlijk niet uit te tekenen hoe deze ‘A2’ doosjes er van
binnen uit zien.
c.
Maak
een schakeling ‘B4’ die het tegenovergestelde doet, dat wil zeggen die selectie-invoerkanalen a0 en a1
gebruikt om één van de uitvoerkanalen out0, ..., out3 te kiezen om hier
het data-invoerkanaal aan door te geven.
d. Bedenk hoe je schakelingen als ‘A4’ en ‘B4’
zou kunnen gebruiken als onderdelen van een geheugen.
e. Noem zoveel mogelijk plekken waar je bij
het bouwen van een Little Man Computer
schakelingen als ‘A4’ of ‘B4’ zou kunnen gebruiken.
Opdracht 3
Stel we hebben
een 2-bits opteller ‘+’ (met twee keer twee ingaande draadjes voor de twee
2-bits getallen en drie uitgaande draadjes voor het resultaat) en een 2-bits vermenigvuldiger
‘*’ (met twee keer twee ingaande draadjes en vier
uitgaande draadjes voor het resultaat):
|
|-------|
a0 --------------> | |
b0 --------------> | | -------> c0 | + | -------> c1
a1 --------------> | | -------> c2
b1 --------------> | | |-------| |-------|
a0 --------------> | |
b0 --------------> | | -------> c0 | * | -------> c1 | | -------> c2
a1 --------------> | | -------> c3
b1 --------------> | | |-------| |
Maak hiermee een
simpele aritmetische eenheid ‘ALU’, met twee keer twee ingaande draadjes voor
de twee getallen, plus nog een extra ingaand draadje om te kiezen of je wilt
optellen of vermenigvuldigen en vier uitgaande draadjes voor het resultaat.
Nb. Je hoeft hier
dus niet de schakelingen ‘+’ en ‘*’ te maken! Je mag
aannemen dat je deze al hebt.
Opdracht 4
a.
Maak
een 2-bits opteller, die twee gegeven 2-bits getallen a en b
optelt en de som als een 3-bits getal c als uitvoer geeft. (Dus de ‘+’ uit de vorige opdracht.)
|
|-------|
a0 --------------> | |
b0 --------------> | | -------> c0 | + | -------> c1
a1 --------------> | | -------> c2
b1 --------------> | | |-------| |
Nb. Probeer een handige bouwsteen te vinden om dit op een systematische
manier te doen, anders lukt het je nooit om de volgende opgave te maken.
b.
Maak
een 8-bits opteller.
Opdracht 5 (extra)
Kunnen we alle
mogelijke schakelingen wel maken? Geef een overtuigende uitleg die aantoont dat
je voor elke input-output tabel, met n inputs en k outputs, voor willekeurige n
en k, een schakeling kunt maken die deze schakeling realiseert.
Dit kun je doen
door een methode te beschrijven om bij een willekeurige tabel een schakeling te
bouwen. Maak hiervoor de volgende deelopdrachten
a.
Kun
je op een systematische manier een schakeling maken die 1 oplevert dan en
slechts dan als de combinatie van inputs precies overeenkomt met een gegeven
combinatie van nullen en enen? (Bijvoorbeeld kun je een schakeling met drie
inputs en één output maken die 1 oplevert dan en slechts dan als de inputs respectievelijk
1, 0, 1 zijn? Of 1, 0, 0? etc. )
b.
Kun
je op een systematische manier een schakeling maken die 0 oplevert dan en
slechts dan als de combinatie van inputs precies overeenkomt met een gegeven
rij nullen en enen?
c.
Kun
je hiermee op een systematische manier voor een willekeurige gegeven
input-output tabel, met n inputs en 1 output, een bijbehorende schakeling
maken?
d.
Kun
je hiermee nu ook hetzelfde voor een willekeurige input-output tabel, met n
inputs en k outputs?
Product
In beginsel mag
je alleen ‘EN’, ‘OF’ en ‘NIET’ poorten gebruiken, maar daarnaast mag je de gemaakte
poorten wel hergebruiken. Dus als je een ‘XOR’ hebt gemaakt, mag je die
gebruiken bij volgende opdrachten.
Het product is
een serie van tekeningen van schakelingen, met een zin toelichting over welk
diagram wat doet, en voor Opdracht 1 óók de beschrijving van de diagrammen in
woorden.
Je hoeft niet
alle opdrachten in te leveren. Op het antwoordformulier staat precies welke van
de opdrachten ingeleverd moeten worden. Opdracht 5 is in elk geval niet
verplicht.
Als het je niet
lukt voor onderdelen van Opdracht 2 een schakeling te bedenken, schrijf dan in
elk geval de tabel (met nullen en enen) op die het gedrag van de schakeling
beschrijft.
Reflectie
·
Welke
verschillende manieren om een schakeling te beschrijven ben je tegengekomen?
·
Hoe
heb je jezelf of een medestudent ervan overtuigd dat je oplossing goed was?
·
Hoe pak
je zo'n opdracht nou eigenlijk aan? Kun je hier enige
systematiek in ontdekken of in aanbrengen?
·
Hoe
kan een schakeling als in Opdracht 2 gebruikt worden om de CPU waarden uit het
geheugen te laten lezen? Wat voor soort schakeling zou je nodig hebben om de
CPU waarden naar het geheugen te laten schrijven?
·
Zowel
de schakelingen die we vandaag hebben bekeken als de Little Man Computer (of Turing machines) van gisteren zijn
apparaten die iets kunnen berekenen. Wat zijn de essentiële verschillen tussen
de schakelingen van vandaag en de Little
Man Computer?