Zahlen

Transcript

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 f¨ ur Ziffer in Bin¨ arcode umgewandlet. Anschließend teilt man diese Zahl von rechts nach links in Teile der Gr¨ oße k, sodass B = 2k gilt. Diese Paktete“ entsprechen dann der Bin¨arcodierung der Ziffern im B-adischen System. ” Ganze Zahlen Ganze Zahlen k¨ onnen 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), f¨ ur das Vorzeichen; die restlichen Bits stehen f¨ ur 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 Standardm¨aßig ein bestimmter Betrag, der Exzess, von der Zahl subtrahiert. Der Exzess einer n-Bit Zahl betr¨ agt 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 Bin¨ardarstellung umwandeln F¨ uhrende Null anf¨ ugen 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. Ublicherweise 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 ben¨ otigt 32 Bit. Das erste Bit gibt das Vorzeichen an, die n¨ achsten 8 Bit stehen f¨ ur den Exponenten in -127er Exzess-Darstellung, die restlichen 23 Bit stehen f¨ ur 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 Bin¨arzahl nach IEEE 754-Standard geht man wie folgt vor: • Umwandlung des Integer- und Fraktionsteils in Bin¨ardarstellung. • 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. F¨ ur jede Verschiebung nach rechts wird der Exponent um eins erh¨oht und f¨ ur 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 gr¨ oß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 f¨ ur die beide Zahlen. • Addition/Subtraktion der beiden Mantissen 2 • Normalisierung des Ergebnisses • Underflow-/ Overflowtest. Die Teilergebnisse werden danach gepr¨ uft, ob sie in die daf¨ ur 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 bin¨ar 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. Sp¨ ater kam Unicode mit 16bit, kann 65536 Zeichen. BCD-Code Der BCD-Code ist ein Code der verwendet wird um Dezimalzahlen abzubilden. F¨ ur die Ziffern 0-9 ben¨otigt man 4 Bit, aber 24 = 16 → 6 redundande Codierungen. Ungepackte BCD-Codes verwenden pro Ziffer ein 8-Bit-Wort (Byte), wobei die f¨ uhrenden 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 Ubertragung von kodierten Informationen k¨ onnen Fehler (Crosstalk, Strahlung, defekter Speicher) auftreten. Zum Erkennen werden zus¨ atzliche Informationen in den Code reincodiert. Meist u atsbit. ¨ber ein Parit¨ Eine gerade Parit¨ at ist 1, wenn die Anzahl von Einsen im Codewort gerade ist, sonst Null. Eine ungerade Parit¨ at 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 f¨ ur alle Codew¨orter, so l¨asst sich ein 1-Bit-Fehler korrigieren, ein 2-Bit-Fehler feststellen. Blocksicherung Anordnung von Codes in einem Block, anf¨ ugen von Zeilen-Parit¨ats-Bits“ und Spalten-Parit¨ats-Bits“. Ein einzelner 1-Bit” ” Fehler kann dann genau lokalisiert und korrigiert werden. Optimale Codes ¨ Bei der Ubertragung spielt nicht nur Fehlertoleranz eine Rolle, auch die Geschwindigkeit (und damit die L¨ange eines Codeworts) ist wichtig. Ein Optimaler Code versucht die durchschnittliche Codewortl¨ange zu minimieren. Idee: h¨ aufig 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 m¨oglichst gleich groß sind • Die erste Teilmenge erh¨ alt das Codierungszeichen 0, die zweite erh¨alt die 1. • Fahre rekursiv mit den Teilmengen fort, bis alle Mengen nur noch 1 Zeichen enthalten. Informationsgehalt, mittlere Codewortl¨ ange: 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 Codewortl¨ ange eines Worts x1 x2 . . . xn ist m ¯ = n X p(xi ) · l(xi ), i=1 wobei l(xi ) die Anzahl der Bits bezeichnet, die f¨ ur die Codierung dieses Symbols n¨otig 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 gleichm¨ achtig. 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 -Verkn¨ upfung von Literalen: a ∧ b ∧ c = a · b · c = abc. Ein Summenterm ist eine oder -Verkn¨ upfung 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 -Verkn¨ upfung von Produkttermen, analog ist eine Konjunktive Normalform die Und -Verkn¨ upfung von Summentermen. Die DNF wird aus der Tabelle ausgelesen, in dem jede Zeile mit dem Ausgabewert Eins“ rausgeschrieben wird. Die Eingangs” variablen f¨ ur die eine Null steht, werden in negierter Form genommen. Alle Terme f¨ ur die Zeilen werden durch ∨ verbunden. F¨ ur die KNF werden alle Zeilen mit dem Ausgabewert Null“ rausgeschrieben, wobei Eingangsvariablen f¨ ur die eine Eins“ ” ” steht, in negierter Form genommen werden. Alle Terme f¨ ur die Zeilen (im vorliegenden Beispiel 10 Zeilen) werden durch ∧ verbunden, die Literale selber werden durch ∨ verbunden. Ein Implikant einer Funktion ist ein Produktterm f¨ ur den der Wert der Funktion 1 ist. Ein Primimplikant ist ein minimaler Implikant, einer der nicht mehr verk¨ urzbar ist. Beispiel: Sei f (a, b, c) = ab + bc + a¯bc. Es gibt Implikanten ab, bc, a¯bc, aber auch a ¯bc, ab¯ c, 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 M¨ oglichkeit zu minimieren. • Aufschreiben der Minterme, in Gruppen geordnet sodass immer gleichviele Einsen in den Mintermen vorkommen ¨ • Uberpr¨ ufen 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 Uberdeckungstabelle 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 k¨ onnen aus der Uberdeckungstabelle gestrichen werden. Sequentielle Logik, Speicher Ein DEA (Deterministischer endlicher Automat) ist ein 5-Tupel (Q, Σ, δ : Q × Σ → Q, q0 , F ) ¨ mit Q = Zustandsmenge, Σ = Alphabet, δ = Uberf¨ uhrungsfunktion, q0 = Startzustand, F = Menge der Endzust¨ ande. Mealy- und Mooreautomaten arbeiten ¨ aquivalent zu DEA’s, haben aber zus¨atzlich ein Ausgabealphabet ∆ und eine Ausgabefunktion λ. Beim Mealyautomat h¨ angt die Ausgabe vom aktuellen Zustand und Eingabe ab (quasi wie δ): λ : Q × Σ → ∆. Beim Mooreautomaten h¨ angt 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 Aquivalenzklassen erzeugt. ¨ • Fasse alle Zust¨ ande die bei gleicher Eingabe die gleiche Ausgabe haben zu einer Aquivalenzklasse zusammen. ¨ • Partitioniere diese Aquivalenzklassen weiter, fasse alle Zust¨ande zusammen, die bei gleicher Eingabe den gleichen Folgezustand haben. ¨ • Terminiere wenn keine Aquivalenzklasse 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 Dateneing¨ ange, k Adresseing¨ange und einen Datenausgang. Er w¨ahlt 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 Ausg¨angen 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 bin¨ ar codiert. Ein Decoder hat analog die Bin¨arcodierung des gew¨ unschten Ausgangs am Eingang anliegen. 7