I denna laboration får du träna på att använda abstrakta klasser, arv, dynamisk bindning, rekursion och generiska containerklasser.
När man konstruerar digitala kretsar utgår man från enkla digitala komponenter, t.ex. logiska grindar (gates) och vippor (flipflops). Komponenternas in- och utsignaler är elektriska spänningar på “låg nivå” eller “hög nivå”. Dessa brukar betecknas som 0 och 1 (false
resp. true
). De enklaste grindarna avbildar på elektronisk väg de logiska funktionerna, t.ex. “icke”, “och”, “eller” och “exklusiv eller”. Vippor kännetecknas av att de har ett inre tillstånd, d.v.s. utsignalernas värden beror inte enbart på insignalernas aktuella värden.
Er uppgift är att skriva några klasser som modellerar och simulerar digitala kretsar och komponenter enligt beskrivningen som följer. I de klasser som beskrivs nedan får ni lägga till instansvariabler och -metoder om det behövs. Dessa ska i så fall vara vara private. Inga klassvariabler eller -metoder ska läggas till. Binära värden ska representeras av boolean
, där false
representerar 0 och true
representerar 1.
CircuitComponent
Ni ska skriva en klass CircuitComponent
, basklassen för komponenter. Tänk på att klasser med abstrakta metoder måste deklarares abstrakta. En komponent har ett visst antal ingångar och utgångar. In- och utgångar adresseras med index från 0 till antalet in-/utgånger - 1. För varje in- och utgång finns ett aktuellt värde (en boolean
). Varje utgång är antingen inte kopplad eller kopplad till en viss ingång på en komponent. En kopplad utgång representeras av en instans av hjälpklassen Wire
, se nedan. Varje ingång är antingen kopplad eller inte, vilket representeras av en boolean
.
De komponenter med internt tillstånd som kan modelleras är tänkta att vara synkront styrda av en klocksignal. För att undvika konstigheter med timing så finns det två metoder. Den ena, updateState
, uppdaterar interna tillståndet baserat på ingångsvärdena men ändrar ej utångsvärdena. Den andra, propagateStateChange
, beräknar nya utgångsvärden baserat på nya interna tillståndet och propagerar dessa till kopplade komponenter.
Klassen ska innehålla åtminstone dessa medlemmar:
En hjälpklass Wire
som ska definieras så här:
private static class Wire {
CircuitComponent receiver;
int receiverInputIndex;
Wire(CircuitComponent receiver, int receiverInputIndex) {
this.receiver = receiver;
this.receiverInputIndex = receiverInputIndex;
}
}
Denna används för att hålla reda på vilken komponents ingång som en viss utgång är kopplad till (receiver
) och vilket index ingången har hos mottagarkomponenten (receiverInputIndex
).
Två heltal som anger antalet ingångar resp. utgångar som komponenten har. Dessa ska vara protected
och final
.
Två arrayer av boolska värden som innehåller aktuella ingångarnas resp. utgångarnas värden. Dessa ska vara private
.
En array av Wire
där varje element representerar motsvarande utgångs koppling. Avsaknad av koppling på en viss utgång representeras av null
. Denna array ska vara private
.
En array av boolska värden där varje element håller reda på om motsvarande ingång är kopplad. Denna array ska vara private
.
En konstruktor som tar antal ingångar och utgångar som argument. Komponenten ska initialt inte har några in- eller utgångar kopplade. Aktuellt värde på ingångar ska sättas till false
. Metoden computeOutputs
(se nedan) ska därefter anropas och värdena läggas in som aktuella värden för utgångarna.
En metod
protected boolean getInput(int inputIndex)
som ger aktuellt värde för ingång med index inputIndex
.
En metod
public void connect(int outputIndex, CircuitComponent receiver, int receiverInputIndex)
som skapar en koppling från utgången med index outputIndex
på aktuell komponent till ingången med index receiverInputIndex
på komponenten receiver
. Om värdet på mottagande komponents ingång inte stämmer överens med värdet på aktuell komponents utgång så ska mottagande komponents ingångsvärde ändras och propagateChange
anropas för mottagande komponent. Om denna utgång eller denna ingång redan är kopplad ska ett RuntimeException
kastas.
En metod
public void disconnect(int outputIndex)
som tar bort kopplingen mellan utgången med index outputIndex
på aktuell komponent och ingången som den var kopplad till. Om denna utgång ej är kopplad ska ett RuntimeException
kastas.
En metod
protected void propagateChange()
som har ansvar för att se till att ändringar i en komponent får effekt i alla kopplade komponenter. Den ska anropa computeOutputs
. Metoden ska inte anropas med arrayen som representerar aktuella utgångsvärden som argument. Istället ska en array för tillfällig lagring av nya utgångsvärden användas. Värdena ska i denna sättas till false
före anropet av computeOutputs
. Efter anropet till computeOutputs
jämför man värdena i den tillfälliga arrayen med dem i arrayen med aktuella värden och uppdaterar där de värden som ändrats. För de utgångar vars värde ändras och är kopplade uppdateras värdet på mottagande komponents ingång och metoden anropas rekursivt för mottagande komponent. Ändringen ska alltså progageras genom hela nätet av kopplade komponenter.
En metod
protected abstract void computeOutputs(boolean[] newOutputValues);
Denna metod är abstrakt. Subklasserna definiera här hur utgångsvärdena för den typ av komponent de representerar beror på ingångsvärdena och eventuellt internt tillstånd. Ingångsvärdena läses i metodens definitioner i subklasserna m.h.a. getInput
. Utgångarnas nya värden läggs på resp. index i newOutputValues
.
Två metoder med definitionerna
protected void updateState() {
}
protected void propagateStateChange() {
}
Dessa metoder överskuggas av subklasser som har ett internt tillstånd. updateState
ska i dessa subklasser läsa av aktuella ingångsvärden och uppdatera det interna tillståndet enligt dessa (och interna tillståndets föregående värde). propagateStateChange
ska i dessa subklasser beräkna nya utångsvärden efter att interna tillståndet uppdaterats. Detta görs helt enkelt genom ett anrop till propagateChange
. De två metoderna har tomma default-implementationer, vilket motsvarar beteendet hos komponenter utan internt tillstånd.
LogicGate
Denna klass ska ärva CircuitComponent
och modellera en logisk grind, d.v.s. en komponent utan internt tillstånd och med en utgång.
Den ska åtminstone dessa medlemmar:
En konstruktor som tar antalet ingångar som argument.
En metod
protected abstract boolean compute();
som ska definieras av subklasser och beskriva den logiska funktionen som komponenten mostsvarar. Den enda utgångens värde returneras av metoden.
Metoden computeOutputs
ska definieras genom att anropa compute
och lägga in retur-värdet från denna i newOutputValues
.
AndGate
, OrGate
, XorGate
och NotGate
Dessa klasser ska vara konkreta, ärva LogicGate
, ha en konstruktor utan argument och definiera compute
på rätt sätt (och, eller, exklusiv eller, icke). NotGate
ska ha en ingång, de andra två ingångar. Använd getInput
för att läsa ingångarnas värden i definitionen av compute
.
Adder
Det ska vara en konkret klass som ärver CircuitComponent
. Den representerar en full-adder, en komponent med tre ingångar och två utgångar som vi kallar s och c. s ska vara utgången med index 0 och c utgången med index 1. Ingångarna tolkas som nollor och ettor och summeras. Resultatet kan beskrivas med ett binärt tal med två bitar. Utgången s (summa) motsvarar minst signifikanta biten i resultatet och c (carry) den mest signifikanta. Klassen ska ha en konstruktor utan argument. Klassen behöver inte implementeras genom att skapa en krets med logiska grindar, utan man kan helt enkelt utföra additionen med Java-kod genom att implementera computeOutputs
på rätt sätt.
Constant
Den modellerar en komponent med bara en utgång vars värde är konstant. Den ska ha följande definition
class Constant extends CircuitComponent {
private final boolean value;
public Constant(boolean value) {
super(0, 1);
this.value = value;
if (value == true) {
propagateChange();
}
}
protected void computeOutputs(boolean[] newOutputValues) {
newOutputValues[0] = value;
}
}
Input
Ska vara en konkret klass och representera en ingång till en krets av komponenter. Den ska ha noll ingångar och en utgång. Klassen ska ärva CircuitComponent
. Den kan definieras ungefär som Constant
, men variabeln ska inte vara final utan kunna ändras efter att komponenten skapats.
Klassen ska ha följande:
En kontruktor lik den i Constant
som tar initiala värdet som argument.
Samma implementering av computeOutputs
som Constant
har.
En metod
public void setValue(boolean value)
som anropas när man vill ändra kretsingångens värde. Denna ska se till att eventuell förändring propageras till kopplad komponent genom att anropa propagateChange
.
Output
Ska vara en konkret klass. Är motsatsen till Input
, en utgång i en krets. Den ska ha en ingång och ingen utgång.
Klassen ska ha:
En konstruktor utan argument.
En definition av computeOutputs
En metod
public boolean getValue()
som returnerar aktuellt värde (hos komponentens enda ingång).
Fork
Klassen ska motsvara en förgrening med valbart antal utgångar. Definitionen ska vara
class Fork extends CircuitComponent {
public Fork(int nOutput) {
super(1, nOutput);
}
protected void computeOutputs(boolean[] newOutputValues) {
boolean val = getInput(0);
for (int i = 0; i < newOutputValues.length; i++) {
newOutputValues[i] = val;
}
}
}
StatefulComponent
Klassen ska vara en abstrakt superklass för komponenter med tillstånd. Definitionen ska vara
abstract class StatefulComponent extends CircuitComponent {
StatefulComponent(int nin, int nout) {
super(nin, nout);
}
final protected void propagateStateChange() {
propagateChange();
}
}
propagateStateChange
överskuggas med en definition där propagateChange
anropas. Dess sub-klasser ska överskugga updateState
.
DFlipFlop
En konkret klass som ska ärva StatefulComponent
och simulera en D-vippa. Den ska ha en ingång, en utgång och en bit som internt tillstånd. Det interna tillståndet ska initialt vara false
. När updateState
anropas ska det interna tillståndet bli lika med ingångsvärdet. När computeOutputs
anropas ska utgångsvärdet sättas till det interna tillståndets värdet. Klassen ska ha en konstruktor utan argument.
JKFlipFlop
En konkret klass som ska ärva StatefulComponent
och simulera en JK-vippa. Den ska ha två ingångar (j på index 0 och k på index 1), två utgångar (q på index 0 och nq på index 1) och en bit som internt tillstånd. Det interna tillståndet ska initialt vara false
. När updateState
anropas ska interna tillståndet
true
om j = true
och k = false
false
om j = false
och k = true
false
och k = false
false
till true
, true
till false
) om j = true
och k = true
När computeOutputs
anropas ska q sättas till det interna tillståndets värdet och nq till icke q. Klassen ska ha en konstruktor utan argument.
Circuit
Klassen ska representera en hel krets med komponenter.
Den ska ha
En privat instansvariabel kallad components
av typen Map<String, CircuitComponent>
En konstruktor utan argument som skapar en tom krets.
En metod
public void addComponent(String name, CircuitComponent component)
som lägger till en komponent i kretsen och binder den till namnet name
. Om det redan finns en komponent med samma namn så ska ett RuntimeException
kastas.
En
public CircuitComponent getComponent(String name)
som returnerar komponenten i kretsen som name
är associerat till. Om name
inte är associerat till en komponent så returneras null
.
En metod med följande definition
public Set<String> componentNames() {
return components.keySet();
}
En metod
public void tick()
som simulerar en klockpuls i kretsen genom att först anropa updateState
för alla komponenter och sedan anropa propagateStateChange
för alla komponenter.
En konstruktor
public Circuit(List<String> lines)
Denna ska skapa en krets som innehåller komponenter och kopplingar enligt listan lines
. Varje sträng i listan motsvarar en komponent och kopplingarna ut från dessa. Ni ska anta att varje sträng är på följande format:
namn typ koppling koppling ...
Varje del avgränsas av mellanslag. Först kommer komponentens namn i kretsen, sedan dess typ. Typen kan vara AND
, OR
, XOR
, NOT
, ADDER
, INPUT
, OUTPUT
, ZERO
, ONE
, FORK
, DFLIPFLOP
eller JKFLIPFLOP
. Vilken komponent detta motsvarar är uppenbart för de flesta. INPUT
ska skapa en Input
med false
som initialt värde. ZERO
ska skapa en Constant
med värdet false
. ONE
ska skapa en Constant
med värdet true
. FORK
ska skapa en Fork
med två utgångar.
Efter typen kommer ett antal kopplingar (0 eller fler). Varje koppling har formatet
utgindex mottagarkomp ingindex
Återigen avgränsas delarna med mellanslag. utgindex
är indexet för utgången som ska kopplas. mottarkomp
är namnet på komponenten som är receiver
i kopplingen. ingindex
är indexet för den ingång på mottagarkomponenten som ska kopplas.
En koppling kan hänvisa till en mottagarkomponent som definieras senare i listan. Man måste därför löpa igenom listan två gånger. Första gången skapar man bara rätt typ av komponent, utan kopplingar. Andra gången lägger man till alla kopplingar.
Här är ett exempel på en krets med en and-grind och kretsingångar och en utgång kopplade till den. Varje rad motsvarar en sträng i listan som skickas till konstruktorn.
i1 INPUT 0 c 0
i2 INPUT 0 c 1
c AND 0 o 0
o OUTPUT
Ni kan testa era komponentklasser innan ni implementerat Circuit
genom att skapa och koppla ihop instanser. Lägg till Input
s och Output
s och påverka och avläs värden via deras metoder setValue
resp. getValue
. Mellan krets-ingångarna och -utgångarna lägger ni in andra komponenter. Se exemplet ovan.
När ni implementerat Circuit
kan ni använda detta program för interaktiv testning. Det låter användaren välja en fil som beskriver en krets enligt formatet ovan. För varje kretsingång skapas en knapp med dess namn och värde. När man trycker på knappen ändras ingångens värde. För varje kretsutgång visas dess namn och värde. När man klickar på ingångsknappar ska detta automatiskt och korrekt återspeglas i utgångarnas värden om allt funkar som det ska (förutom för vipp-komponenterna). Det finns också en knapp “Clock Tick” som anropar tick
i Circuit
, d.v.s. simulerar ett synkront klock-tick hos de komponenter i kretsen som har ett internt tillstånd. För kretsar utan komponenter med tillstånd (vippor) har “Clock Tick” ingen effekt. När man trycker på input-knapparna ska ändringen direkt propageras och synas i utgångarna (om logiken i kretsen innebär att ändring av utgången ska ske).
Det finns några exempel-kretsar att pröva. Många av dem innehåller bara några få olika komponenter, så man kan börja använda detta testprogram tidigt om man implementerar Circuit
innan man implementerar alla komponent-klasser. Börja t.ex. med Input
, Output
och de logiska grindarna.
Slutligen finns ett program för automatisk testning som prövar er implentering med alla typer av komponenter och rapporterar om något fel hittas. Innan ni lämnar in labben bör ni kunna köra detta testprogram utan att fel upptäcks.
Skicka in enbart era .java
-filer. De ska vara lösa, ej packade .zip
eller dylikt. Skicka inte in testprogrammens java-filer, bara de med komponentklasserna och klassen Circuit
. Placera inte era klasser i något paket. (Era filer ska inte innehålla någon rad package ...;
)
Tänk på att följa de allmänna riktlinjerna för programmeringsstil som anges på sidan Laborationer.