CRC

Codieren:
Decodieren:

Wie genau die Division geht findet ihr hier sehr schön erklärt.

Konvertieren

Das B steht für die Basis in der gerechnet wird. Die Wertigkeit der Stellen nimmt von rechts (0) nach links (B^n-1) zu, wobei n die Länge des Tupels ist.
Tricks fürs das Konvertieren:

• Umwandeln einer Dezimalzahl d in eine beliebige Zahl zur Basis b:
  d : b = a Rest c
  a : b = a' Rest c'
  ...
  a'' : b = 0 Rest c'''
  Lösung <[c''',...,c',c]>b
  
• Umwandeln einer Zahl a zur Basis b in eine Zahl a' zur Basis b', Voraussetzung für b', b' = b^n. Bsp.:
  

Rechnen

Mit Radix-B Zahlen lässt sich genauso rechnen wie man es in der Grundschule gelernt hat, nur zu einer anderen Basis.

Konvertieren

Bis auf die erste Stelle werden die Zahlen so betrachtet wie die Radix-B Zahlen. Der Wert an der ersten Stelle x berechnet sich wie folgt, wobei B die Basis ist (in der Vorlesung werden nur gerade Basen betrachtet^^):

von Dezimal nach B-Complement:
von B-Complement in Dezimal:
Kleiner Tipp:
Man kann die Zahlen auch negieren, wenn man x-1 rechenet und dann versucht die Ziffern auf B-1 aufzufüllen.
Bsp.: <[1,2]>4 = 6 -> <[1,1]> -> <[2,2]>4 = -6

Addition und Subtraktion

Die Addition und die Subtraktion werden wie bei den Radix-B Zahlen gerechent. Bei der ersten Stelle (höchswertiges Bit) sollte man jedoch beachten, dass bei Werten größer B/2 die Werte negativ sind.
Bsp:
B=10; y = 7+7 = 94
α(7) = 7-10 = -3
α(9) = 9-10 = -1
94 = -1*10 + 4*1 = -6

Multiplikation

1.Fall, zwei negative Zahlen:
2.Fall, zwei positive Zahlen:
3.Fall, je eine Zahl:

Division

x/y = q R r
Zuerst einmal zu dem generellen Vorgehen, welches egal bei welchem Fall immer gemacht werden muss:

1. x mit "Länge von y" vielen Stellen erweitern, dass heißt, wenn x positiv ist Nullen, wenn sie negativ ist, (B-1)en vorranstellen
2. Der erste Schritt wird immer mit einem negativen y ausgeführt, was um eine Stelle erweitert wurde.(Kann man bei positivem x auch ignorieren, da es eh nullmal rein passt, aber so kann man es sich besser merken^^)

Die Schritte 2-n werden wie bei den Radix-B Zahlen gerechnet mit den folgeneden Unterscheidungen.

x,y	-	+
-	Statt y wird mit -y, also dem positiven Wert gerechnet. Das Ergebnis wird negiert.	Nichts
+	Statt y wird mit -y, also dem positiven Wert gerechnet. Das Ergebnis wird negiert.	Nichts

Fixpunkt-Zahlen

Neber der Basis wird hier nun auch die Anzahl der Nachkommastellen angegeben. Man zeichnet sich am besten das Komma in die kodierte Zahl und berechnet die Zahlen vor dem Komma wie gewohnt. Für die Nachkommastellen wird das Schema 2ⁱ weiter geführt, die erste Stelle hinter dem Komma wird also mit 2⁻¹ gewichtet, die nächste mit 2⁻² usw.. Beispiel:
<[1,1,1,1]>2,2
=> 1*2¹ + 1*2⁰ + 1*2⁻¹ + 1*2⁻² = 3,75

Für die Rückrichtung kann man zuerst die Zahl vor dem Komma, dann die nach dem Komma kodieren.

Rechnen mit Fixpunkt-Zahlen

Das Rechnen mit den Fixpunkt-Zahlen ist genauso wie mit den B-Complement Zahlen. Wichtig ist, bei Addition und Subtraktion die Zahlen so untereinander zu schreiben, dass das Komma übereinander ist. Bei der Multiplikation muss man darauf achten wo das Komma nach der Rechnung hin muss.

Gleitkomma-Zahlen

Diese Zahlen berechnen sich aus drei Teilen, den Sign S, dem Exponenten E und der Mantisse M, die sich auch in dieser Reihenfolge in der kodierten Zahl wieder finden. Beispiel:
<[0,0,1,1,1,1,1,0]>2,4,3
Bedeutet also Basis B = 2, Vorzeichen S = 0 (positiv), Länge e (des Exponente E) = 3, Länge m (der Mantisse M) = 4

Umrechnen in eine "normale" Kommazahl:

Bias berechnen:
ß = (B^e - 1) div 2
= (2³ - 1) div 2 = 7 div 2 = 3

(-1)^S * (M * B^1-m) * B^E-ß
(-1)⁰ * (<[1,1,1,0]> * B^1-4) * B^3-3
1 * <[1.110]> * 1 = 1.75 (verschieben den Kommas um drei Stellen nach links)

Umrechnen in eine Gleitkomma-Zahl:

1,75 umwandeln in die Form <[1,1,1,1,1,1,1,1]>2,4,3

1. Vorhandene Informationen aufschreiben; B = 2, e = 3, m = 4, S = 0
2. E = log_B (|x|) (Ergebnis muss Abgrundet werden)
   E = ld(1,75) = 0
3. M = |x| * B^-E
   M = 1,75
4. M` = M * B<sup>m-1</sup>
   M` = 1,75 * 2³ = 14
5. M` als Radix-B Zahl darstellen:
   <[1,1,1,0]>
6. E` = E + ß
   E` = 0 + 3 = 3
7. E` als Fixpunkt-Zahl darstellen und dabei runden:
   I_m = <[0,1,1]>
8. Bedingung prüfen und E, M anpassen:
   
9. Einzelne Teile in der richtigen Reihenfolge zusammen fassen:
   <[0,0,1,1,1,1,1,0]>2,4,3

Rechnen mit Gleitkomma-Zahlen

Beim Rechnen mit den Gleitkomma-Zahlen sind die Rechenregeln für Potenzen zu beachten. Bei der Addition/Subtraktion muss der kleiner Exponent angeglichen werden, nach der Rechnung kann es passieren, dass nun zwei Ziffern vor dem Komma stehen, dann muss auch hier der Exponent angeglichen werden. Bei der Muliplikation werden die Mantissen multipliziert, die Exponenten Addiert (hier muss einmal der Bias abgezogen werden, da er sonst doppelt vorhanden ist).

Operatoren

Gesetze und Äquivalenzen

KNF und DNF

KNF: In den Klammern stehen ODER, die Klammern werden mit UND verbunden.
DNF: In den Klammern stehen UND, die Klammern werden mit ODER verbunden.

Shannon Normalform

Form: if a then 1 else 0
Bsp:
a & b
1. Schritt: if a then b else 0
2. Schritt: if a then (if b then 1 else 0) else 0
Bsp:
!(d&b^a<->c)
1. Schritt: (a?(!(!(d&b)<->c)):(!(d&b<->c))
2. Schritt: (a?(b?(!(!d<->c):(!(1<->c)))):(b?(!(d<->c)):(!(0<->c))))
3. Schritt: (a?(b?(c?(!(!d<->1):!(!d<->0))):(c?(0:1))):(b?(c?(!(d<->1):!(d<->0))):(c?(1:0))))
4. Schritt: (a?(b?(c?(d?(1:0)):(d?(0:1))):(c?(0:1))):(b?(c?(d?(0:1)):(d?(1:0))):(c?(1:0))))

Averest

Zuerst solltet ihr euch die zip-Datei herunter laden und in einem Ordner entpacken, diese braucht ihr um eure Programme zu testen. Dann ladet ihr euch die Dateien in der entsprechenden Aufgabe runter und entpackt auch diese. In diese Vorlagen (.qrz) sollt ihr eure Lösungen schreiben. Zum Testen müsst ihr folgende Schritte ausführen:

1. averest.exe öffnen, dann geht ein kleines Fenster auf
2. Die .qrz Datei in dieses Fenster ziehen
3. Komplieren, danach müsste eine .aifs Datei in eurem Ornder erscheinen
4. Die aif2trc.exe öffnen
5. Die .aifs Datei in das Fenster ziehen und Simulation auswählen (.trace)
6. Die .txt Datei enthält jetzt die Lösungen zu den Testfällen, hier könnt ihr schauen ob euer Programm das richtige tut.

Weiter kann ich euch die Reference Card empfehlen, hier findet ihr eine Übersicht der Syntax. Hier ein Beispiel wie euer Programm aussehen soll.

/* ************************************************************************** */
/*                                                                            */
/*    eses                   eses                                             */
/*   eses                     eses                                            */
/*  eses    eseses  esesese    eses   Embedded Systems Group                  */
/*  ese    ese  ese ese         ese                                           */
/*  ese    eseseses eseseses    ese   Department of Computer Science          */
/*  eses   eses          ese   eses                                           */
/*   eses   eseses  eseseses  eses    University of Kaiserslautern            */
/*    eses                   eses                                             */
/*                                                                            */
/* ************************************************************************** */

module NOT (bool ?y, !z) {
    
if (y == true)
	z = false;
if (y == false)
	z = true;

      nothing;   
}

// test cases for all possible inputs

drivenby T0 {
    nothing;
}

drivenby T1 {
    y = true;
}

KV-Diagramm

Hier ein Beispiel für ein KV-Diagramm, man beachte das Z-Schema nach dem die Tabelle in das Diagramm eingetragen wird.

Hier ein Beispiel wie man die DNF und die KNF ablesen kann.

Quine/McCluskey

Ersetze die * in der gegebenen Wahrheitstafel durch 0 oder 1.
φ₀ = φ ∧ ß (* by 0)
φ₁ = φ ∧ ß (* by 1)

1. Alle Belegungen die bei φ₁ eine Eins stehen werden in eine neue Tabelle geschrieben, wobei die Belegungen geordnet werden, nach Anzahl der Einsen. Dies ist die erste Spalte der neuen Tabelle.
2. Belegungen in der ersten Zeile zusammenfassen und in die zweite Spalte schreiben. Unterschiede durch * ersetzten. Alle verwendeten Belegungen werden makiert.
3. Wiederhole solange noch Paare gefunden werden können.
4. Eine Matix aufstellen, bei der links die nicht markierten Paare aus der Tabelle vorher eingetragen werden. Oben werden die Belegungen die Eins ergeben von φ₀ eingetragen.
5. Kreuze in der Matik werden eingezeichnet, wenn die Belegung in der nicht verwendeten Paaren vorkommen.
6. Schauen ob Dinge wegfallen können.
7. Ergebnis ablesen (1=a, 0=!a, *=nix)

Ashenhurst Dekomposition

1. Im KV-Diagramm gleiche Spalten suchen und neu kodieren -> neues KV-Diagramm mit w₀, !w₀
2. DNF ablesen -> h(x₁, y₁, w₀)
3. Den Rest mit dem neuen w₀ aufschreiben.
4. DNF ablesen -> g₁(x₀, y₀, c₀)

Rabin-Scott

Hiermit kann aus einem nicht deterministischen Automaten, ein deterministischer Automat machen. Dazu werden Mengen von Zuständen gebildet, in dem man vom Startzustand beginnend die möglichen Zustände für eine Eingabe zusammenfasst. Bsp.(Hier doppelter Kreis = akzeptierender Zustand):

Die Kanten von s0' z.B. würde dann zu den Zuständen {s0,s1} für a und {s0,s2} für b gehen. s0' = {s0}
s1' = {s0,s1}
s2' = {s0,s2}
s3' = {s0,s1,s3}

wikipedia

Automaten Äquivalenz

1. Tabelle aufstellen, bei der die Zustände der Automaten oben und links eingetragen werden.
2. Kreuze nach folgendem Schema machen:
   1. Δ₀: x₀ an alle Stellen, an dennen sich die Akzeptanz der Zustände unterscheiden.
   2. Δ₁: x₁ an alle Stellen, an dennen sich die Akzeptanz der Folgezstände (bei Eingabe eines Zeichens) unterscheidet.
   3. Δ₂: x₂ an alle Stellen, wo sich beim Ziel einer Eingabe auch ein x befindet.
3. Automaten sind gleich, wenn das erste Kästchen leer ist.

Automaten Minimierung

1. Gleiches Schema wie bei der Äquivalenz.
2. Gleiche Zeilen werde zusammengefasst zu einem neuen Zustand.
3. Kanten zwischen den neuen Zuständen zeichnen.

Letzte Aufgabe

Hier eine mögliche Lösung für die letzte Aufgabe: