Zahlen

Zahlen
Umrechnen einer B-adischen Zahl ins Dezimalsystem:
z10 = zn−1 B n−1 + zn−2 B n−2 + · · · + z0 B 0 =
n−1
X
zi B i
i=0
Beispiel: (3014)5 = (3 ∗ 53 ) + (0 ∗ 52 ) + (1 ∗ 51 ) + (4 ∗ 50 ) = 375 + 0 + 5 + 4 = (384)10
Umrechnen einer Dezimalzahl in ein B-adisches System:
Wiederholte Division mit Rest:
z10 : B = q0 Rest r0
q0 : B = q1 Rest r1
..
.
qn : B = 0 Rest rn .
Liest man nun den Rest von unten nach oben, so ergibt sich die gesuchte Zahl im System zur Basis B
zB = rn rn−1 . . . r0
Umwandlung zwischen beliebigen Basen:
• Zuerst wird ins Dezimalsystem bringen um anschlißend Division mit Rest
• Sind beide Basen A, B Zweierpotenzen, so geht die Umwandlung noch schneller. Zuerst wird die Zahl (a)A Ziffer für
Ziffer in Binärcode umgewandlet. Anschließend teilt man diese Zahl von rechts nach links in Teile der Größe k, sodass
B = 2k gilt. Diese Paktete“ entsprechen dann der Binärcodierung der Ziffern im B-adischen System.
”
Ganze Zahlen
Ganze Zahlen können als Festkommazahl dargestellt werden. Diese bestehen aus 2 Teilen, Integerteil und Fraktionsteil.
zB = zn−1 zn−2 . . . z0 , z−1 . . . z−m
Dabei wird das Komma nicht wirklich angegeben, ist nur eine logische Markierung damit wir sehen wo die Ziffer mit Wertigkeit
0 steht. Der Wert einer solchen Festkommazahl ist:
zB = zn1 B n−1 + zn−2 B n−2 + · · · + z0 B 0 + z−1 B −1 + z−2 B −2 + · · · + z−m B −m =
n−1
X
zi B i .
i=−m
Negative Zahlen
Vorzeichen und Betrag
Bei der Darstellung einer negativen Zahl mittels Vorzeichen und Betrag steht das Most significant bit (MSB, das ganz links),
für das Vorzeichen; die restlichen Bits stehen für den Betrag der Zahl. Ist das MSB = 0 so ist die Zahl positiv, andernfalls
negativ.
Exzess
Bei der Darstellung einer negativen Zahl mittels Exzess wird Standardmäßig ein bestimmter Betrag, der Exzess, von der
Zahl subtrahiert. Der Exzess einer n-Bit Zahl beträgt meist 2n−1 . Beispiel mit n = 3:
Exzess = 2n−1 = 22 = 4. Beispiel: 000 = -4, 001 = -3, 010 = -2, . . . ; 111 = 3.
1
Komplement
positiv
Einerkomplement
negativ
Zweierkomplement
positiv
negativ
Betrag bilden
In Binärdarstellung umwandeln
Führende Null anfügen
Nullen und Einsen vertauschen
Nullen und Einsen vertauschen
1 dazuaddieren
fertig
Gleitkomma, IEEE 754
Gleitkommadarstellung: z = (−1)S × M × B E
Dabei ist S das Vorzeichenbit, M die Mantisse, B die Basis und E der Exponent.
37, 145 = 0, 037145 × 103
Man muss genau festlegen, an welcher Stelle das Komma stehen muss. Üblicherweise steht das Komma hinter der MSB der
Mantisse, welches nicht 0 ist. Man nennt z dann eine normalisierte Zahl.
Standartisiert wurde das ganze unter der IEEE 754 -Norm, die Gleitkommazahlen zur Basis 2 darstellt.
Eine Zahl mit einfacher Genaugikeit benötigt 32 Bit.
Das erste Bit gibt das Vorzeichen an, die nächsten 8 Bit stehen für den Exponenten in -127er Exzess-Darstellung, die restlichen 23 Bit stehen für die Mantisse. Da das Komma immer hinter der MSB der Mantisse 6= 0 steht, muss vorn logischerweise
eine 1 stehen. Da die Mantisse also immer vorn eine 1 hat, kann ich die auch weglassen (sogenanntes hidden-bit).
Umwandlung
Bei der Umwandlung einer Dezimalzahl in eine Binärzahl nach IEEE 754-Standard geht man wie folgt vor:
• Umwandlung des Integer- und Fraktionsteils in Binärdarstellung.
• Zusammensetzen der Zahl zu [ganzer Teil].[gebrochener Teil]
• Normalisierung: Das Komma wird nach rechts oder links verschoben, bis nur noch eine Eins vor dem Komma bleibt.
Für jede Verschiebung nach rechts wird der Exponent um eins erhöht und für jede Verschiebung nach links wird der
Exponent um eins erniedrigt.
• Exponent in Exzessdarstellung bringen: 127 (bzw 1023 bei double precision) auf den Exponenten aufaddieren.
• Zahl zusammenbauen: Vorzeichen, Exponent, Mantisse.
Rechnen mit IEEE 754
Addition und Subtraktion:
• Ermittlung des Operanden mit dem größtem Exponenten e.
• Verschiebung der Mantisse des Operanden mit dem kleineren Exponenten nach rechts, bis beide Exponenten übereinstimmen. Somit ergibt sich ein gleicher Exponent e für die beide Zahlen.
• Addition/Subtraktion der beiden Mantissen
2
• Normalisierung des Ergebnisses
• Underflow-/ Overflowtest. Die Teilergebnisse werden danach geprüft, ob sie in die dafür vorgesehenen Stellen passen.
Multiplikation:
• Bestimmung des Vorzeichens des Ergebnisses als Produkt der Vorzeichen der beiden Operanden
• Bestimmung des Exponenten des Ergebnisses durch Addition der Exponenten der beiden Operanden.
• Bestimmung der Mantisse des Ergbnisses durch Multiplikation der Mantissen der beiden Operanden und gegebenfalls
Normalisierung des Ergenisses
• Zusammensetzung des Ergebnisses und Underflow- / Overflowtest
Rechenoperationen
Codes
Codes sind Vorschriften zum Abbilden eines Alphabets in ein Anderes.
Die Hammingdistanz zweier gleichlanger Codes beschreibt an wieviel Stellen sich die Codes binär unterscheiden.
Gray-Code
Ein Graycode ist eine Codierung, bei der jedes Wort eine Hamming-Distanz von genau 1 hat.
Konstruiert wird er mittels reflektierendem Gray-Code: Sei G1 = {0, 1} Der Reflektierende Code von G1 , Gref
ist die von1
ref
hinten-nach-vorne-Aufschreibung von G1 : Gref
=
{1,
0}.
Jetzt
wird
weiter
konstruiert:
G
=
{0G
,
1G
}
=
{00,
01, 11, 10}
2
1
1
1
ref
Gn = {0G(n−1) , 1G(n−1) }
So konstruiert man einen Gray-Code.
ASCII-Code
7bit, kann 128 Zeichen darstellen. Später kam Unicode mit 16bit, kann 65536 Zeichen.
BCD-Code
Der BCD-Code ist ein Code der verwendet wird um Dezimalzahlen abzubilden. Für die Ziffern 0-9 benötigt man 4 Bit,
aber 24 = 16 → 6 redundande Codierungen. Ungepackte BCD-Codes verwenden pro Ziffer ein 8-Bit-Wort (Byte), wobei die
führenden 4 Stellen auf 0 gesetzt werden (noch redundander), gepackte verwenden nur ein halbes Byte (ein sog. Nibble).
Die Addition in BCD-Code geht Nibbleweise von rechts nach links, ist das Ergebnis mal > 9 muss eine 610 drauf addiert
werden.
Fehlererkennde Codes
Bei Übertragung von kodierten Informationen können Fehler (Crosstalk, Strahlung, defekter Speicher) auftreten. Zum Erkennen werden zusätzliche Informationen in den Code reincodiert. Meist über ein Paritätsbit.
Eine gerade Parität ist 1, wenn die Anzahl von Einsen im Codewort gerade ist, sonst Null.
Eine ungerade Parität ist 1, wenn die Anzahl von Einsen im Codewort ungerade ist, sonst Null.
3
Fehlerkorrigierende Codes
Codiert man seine Codes mit einer Hammingdistanz von 3 für alle Codewörter, so lässt sich ein 1-Bit-Fehler korrigieren, ein
2-Bit-Fehler feststellen.
Blocksicherung
Anordnung von Codes in einem Block, anfügen von Zeilen-Paritäts-Bits“ und Spalten-Paritäts-Bits“. Ein einzelner 1-Bit”
”
Fehler kann dann genau lokalisiert und korrigiert werden.
Optimale Codes
Bei der Übertragung spielt nicht nur Fehlertoleranz eine Rolle, auch die Geschwindigkeit (und damit die Länge eines Codeworts) ist wichtig. Ein Optimaler Code versucht die durchschnittliche Codewortlänge zu minimieren.
Idee: häufig Auftretened Zeichen bekommen kurze Codierung, seltene bekommen lange. (Beispiel Morsecode: e → .; q →
− − .−)
Ein Beispiel ist der Shannon-Fanø-Code:
• Ordne Zeichen nach Auftrittswahrscheinlichkeit
• Bilde daraus 2 Teilmengen, so dass die Summenwahrscheinlichkeiten der Mengen möglichst gleich groß sind
• Die erste Teilmenge erhält das Codierungszeichen 0, die zweite erhält die 1.
• Fahre rekursiv mit den Teilmengen fort, bis alle Mengen nur noch 1 Zeichen enthalten.
Informationsgehalt, mittlere Codewortlänge:
Der Informationsgehalt (Entropie) eines Alphabets {x1 , x2 , . . . , xn } ist
n
X
p(xi ) · log2
i=1
1
,
p(xi )
wobei p(xi ) die Auftrittswahrscheinlichkeit des Zeichens xi bestimmt.
Die mittlere Codewortlänge eines Worts x1 x2 . . . xn ist
m̄ =
n
X
p(xi ) · l(xi ),
i=1
wobei l(xi ) die Anzahl der Bits bezeichnet, die für die Codierung dieses Symbols nötig sind.
Schaltalgebra
4
Die nicht, und, oder -Gatter reichen aus um jede beliebige Funktion zu beschreiben. Verwendet werden aber meist nor und
nand -Gatter. Diese sind gleichmächtig. Der Beweis nutzt die De’Morgan-Gesetze:
A ∨ B = A ∨ B = A ∧ B.
A ∧ B = A ∧ B = A ∨ B.
Logikminimierung
Ein Literal ist eine Boolesche Variable.
Ein Produktterm ist eine und -Verknüpfung von Literalen: a ∧ b ∧ c = a · b · c = abc.
Ein Summenterm ist eine oder -Verknüpfung von Literalen: a ∨ b ∨ c = a + b + c.
Ein Minterm (Vollkonjunktion) einer n-stelligen Booleschen Funktion ist ein Produktterm über alle n Variablen, analog ist
ein Maxterm (Volldisjunktion) der Summenterm über alle n Variablen.
Eine Disjunktive Normalform (SOP) ist die Oder -Verknüpfung von Produkttermen, analog ist eine Konjunktive Normalform
die Und -Verknüpfung von Summentermen.
Die DNF wird aus der Tabelle ausgelesen, in dem jede Zeile mit dem Ausgabewert Eins“ rausgeschrieben wird. Die Eingangs”
variablen für die eine Null steht, werden in negierter Form genommen. Alle Terme für die Zeilen werden durch ∨ verbunden.
Für die KNF werden alle Zeilen mit dem Ausgabewert Null“ rausgeschrieben, wobei Eingangsvariablen für die eine Eins“
”
”
steht, in negierter Form genommen werden. Alle Terme für die Zeilen (im vorliegenden Beispiel 10 Zeilen) werden durch ∧
verbunden, die Literale selber werden durch ∨ verbunden.
Ein Implikant einer Funktion ist ein Produktterm für den der Wert der Funktion 1 ist.
Ein Primimplikant ist ein minimaler Implikant, einer der nicht mehr verkürzbar ist.
Beispiel: Sei f (a, b, c) = ab + bc + ab̄c. Es gibt Implikanten ab, bc, ab̄c, aber auch ābc, abc̄, abc, ac
Primimplikanten sind jedoch nur ab, bc, ac.
Ein Primimplikant der als einziger einen Minterm überdeckt heißt essentieller Primimplikant.
Quine-McCluskey-Verfahren
ist eine weitere Möglichkeit zu minimieren.
• Aufschreiben der Minterme, in Gruppen geordnet sodass immer gleichviele Einsen in den Mintermen vorkommen
• Überprüfen benachbarter Elemente, sollten diese sich in genau 1 Stelle unterscheiden so kann diese weggelassen werden.
Erstelle so eine Neue Liste und markiere die beiden Elemente.
5
• Loop until Neue Liste leer ist
• Alle Unmarkierten Elemente sind Primimplikanten.
• Erstelle Überdeckungstabelle mit Primimplikanten und zuerst gefundenen Mintermen
• Markiere Kreuzpunkte mit einem X wenn der Primimplikant den Minterm überdeckt
• Suche essentielle Primimplikanten (diese haben nur ein X in der Spalte)
Definition Zeilenendominanz Zeile Pi dominiert Zeile Pj , wenn Pi ein X in jeder Spalte hat, in der auch Pj ein X hat.
DefinitionSpaltendominanz Spalte mi dominiert Spalte mj , wenn mi ein X in jeder Zeile hat, in der auch mj ein X hat.
Dominierte Spalten und Zeilen können aus der Überdeckungstabelle gestrichen werden.
Sequentielle Logik, Speicher
Ein DEA (Deterministischer endlicher Automat) ist ein 5-Tupel
(Q, Σ, δ : Q × Σ → Q, q0 , F )
mit Q = Zustandsmenge, Σ = Alphabet, δ = Überführungsfunktion, q0 = Startzustand, F = Menge der Endzustände.
Mealy- und Mooreautomaten arbeiten äquivalent zu DEA’s, haben aber zusätzlich ein Ausgabealphabet ∆ und eine Ausgabefunktion λ. Beim Mealyautomat hängt die Ausgabe vom aktuellen Zustand und Eingabe ab (quasi wie δ): λ : Q × Σ → ∆.
Beim Mooreautomaten hängt die Ausgabe nur vom Zustand ab: λ : Q → ∆. Die Ausgabe erfolgt beim Mealyautomat also
vor dem Zustandswechsel, beim Mooreautomat danach.
Ginsburg-Huffmann
ist ein Verfahren das zur Zustandsminimierung verwendet werden kann. Dabei werden Äquivalenzklassen erzeugt.
• Fasse alle Zustände die bei gleicher Eingabe die gleiche Ausgabe haben zu einer Äquivalenzklasse zusammen.
• Partitioniere diese Äquivalenzklassen weiter, fasse alle Zustände zusammen, die bei gleicher Eingabe den gleichen
Folgezustand haben.
• Terminiere wenn keine Äquivalenzklasse mehr partitionierbar ist.
FlipFlops
VHDL
entity G Automat is
port (clk,reset, E, C,S7, R: in std logic;
GC, G7, M : out std logic);
end G Automat;
architecture Behavioral of G Automat is
Type state type is (I, H);
Signal current state, next state: state type;
Begin
comp:process (E, C, S7, R, current state)
begin
6
case current state is
when I =>
if (E = ’1’) then next state <= H; else next state <= I; end if;
when H =>
if (C= ’1’) then next state <= I; M <= ’0’ ; GC <= ’1’ ; G7 <= ’0’;
elsif (S7 = ’1’) then next state <= I; M <= ’0’ ; G7 <= ’1’ ; G7 <= ’0’;
elsif (R = ’1’) then next state <= I; M <= ’1’ ; G7 <= ’0’; G7 <= ’0’; GC <= ’0’;
elsif (E = ’1’) then next state <= I; M <= ’0’ ; G7 <= ’0’; GC <= ’0’ ;
else next state <= H; M <= ’0’ ; G7 <= ’0’; GC <= ’0’; end if;
end case;
reg: process(clk, next state, reset)
begin
if (reset = ’1’) then current state <= I;
elsif (clk’event and clk = ’1’) then
current state <= next state;
end if;
end process;
end Behavioral;
RTL
Ein Bus ist eine Gruppierung von n ≥ 1 Leitungen.
Ein Wortgatter ist eine Gruppierung von n ≥ 1 Gattern.
Ein Multiplexer (n : 1 MUX) besitzt n Dateneingänge, k Adresseingänge und einen Datenausgang. Er wählt entsprechend
der im k-Bit Adressbus angegebenen Adresse einen Dateneingang aus und legt dessen Wert am Datenausgang an.
Ein Demultiplexer (DEMUX) weist analog einen Dateneingang einem von n Ausgängen zu.
Ein Encoder hat ein n-Bit Wort x als Dateneingang, bei dem nur 1 Bit xi den Wert 1 hat. Er gibt ein k-Bit Wort aus, welches
den Index i binär codiert. Ein Decoder hat analog die Binärcodierung des gewünschten Ausgangs am Eingang anliegen.
7

Download Report