Technische Informatik I (SS 2006) Zusammenfassung Halbaddierer / -subtrahierer unterscheiden sich...

transcript

Technische Informatik I (SS 2006)

Zusammenfassung

● Halbaddierer / -subtrahierer unterscheiden sich nur durch ein NICHT-Gatter

● Umschaltbarer HA/HS möglich● Brauchen Volladdierer…

▪ HA+HA

● Brauchen Vollsubtrahierer…▪ HA+HS

● …für parallele Rechenwerke

Weitere wichtige Schaltnetze?

● Eingänge werden auf Ausgänge abgebildet. Wenn E=1 (enable)

Multiplexer (MUX)

● Weist mehreren Eingängen ein Ausgang zu▪ Auswahl von Eingang aX

falls S=X in Binärdarstellung

● Realisierung mit disjunktiver Normalform:▪ y=(¬S0 & ¬S1 & a0) | (S0 & ¬S1 & a2) |

(¬S0 & S1 & a2) | (S0 & S1 & a3)

S0 S1S

yBsp: 1-aus-

S[0-1] zusammen-

gefasst = Bus

Demultiplexer (DEMUX)

● Weist ein Eingang mehreren Ausgängen zu▪ Auswahl von Ausgang yX falls S=X in Binärdarstellung

● Realisierung:▪ y0=a & ¬S0 & ¬S1

▪ y1=a & S0 & ¬S1

▪ y2=a & ¬S0 & S1

▪ y3=a & S0 & S1

S0 S1S

aBsp: 1-zu-4-DEMUX

Kodierer

● EIN Eingang aX auf 1, Ausgänge stellen Eingangsnummer X in Binärdarstellung dar

● Realisierung:▪ y0=a1 | a3

▪ y1=a2 | a3

Bsp: 4-zu-2-Kodierer

Dekodierer

● Ein Ausgang yX wird gemäß Eingang in Binärdarstellung auf 1 gesetzt

● Realisierung:▪ y0= ¬a0 & ¬a1

▪ y1= a0 & ¬a1

▪ y2= ¬a0 & a1

▪ y3= a0 & a1

Bsp: 2-zu-4-

Dekodierer

Einsatzmöglichkeiten

● MUX/DEMUX▪ Übergang serielle/parallele Übertragung

● MUX▪ Auswahl Speicherzelle

● Kodierer▪ Eingangskodierung (z.B. Interrupt)

● Dekodierer▪ Dekodierung eines Maschinenbefehls,

auch Auswahl Speicherzelle

● Elementare Bauteile eines Prozessors

Komplexität

● Gatterverbrauch steigt mit zunehmender Komplexität stark an

kombinatorische Logik

Zustand

Teil 1: Logik1c: Flip-Flops

Grundelement: Flip-Flop (FF)

● Zustand zunächst E1=1E2=0

● Q1=0Q2=1

● Ändere E2=1

● Zustand für Q bleibt!

Wichtig: E1=E2=0 vermeiden

Dann: Q1 = ¬Q2 (Q, Q)

● Nenne Eingänge ▪ S (Set)▪ R (Reset)

● Negierte Logik● Schaltzeichen

Grundelement: Flip-Flop (FF)

Zeitverhalten

● Bei ¬S=¬R=1 Anfangszustand gemäß Bauteiltoleranz

¬S=1 =0

¬R=1 =0

Q=1 =0

¬Q=1 =0

Asynchrone vs. synchrone Schaltungen

● Basis-FF kann jederzeit sein Zustand ändern● Sog. asynchrones Design

▪ Vorteil: Schnell▪ Nachteil: In Kombination mit weiteren

Schaltungselementen Verhalten schwer bestimmbar

● Synchrone Schaltungen▪ Taktgeber▪ Takt bestimmt durch langsamste Bauteilgruppe

● Flip-Flip: Braucht Takteingang

Getaktetes Flip-Flop (FF)

● Falls C=0▪ Ausgänge der NAND-

Gatter =1▪ Keine Änderung,

● Falls C=1▪ Änderung des Basis-FF-

Zustandes▪ Jedoch während

„C=1-Zyklus“ weitere Änderung möglich

Clock-(C)-Verarbeitung und Inverter

Basis-FFS

D-Flip-Flop

● Sonderform des RS-FF● D = delay● Hält Informationen ein Taktzyklus

Master-Slave-Flip-Flop

● Master übernimmt Zustand bei C=1● Slave übernimmt Zustand bei C=(1→0)

Master Slave

Master-Slave-Flip-Flop

● Flip-Flop übernimmt Zustand bei C=(1→0)● Änderungen während Takt =1 können überschrieben

werden● Aber: Umsetzen wird „gelatched“

S=1 =0

R=1 =0

C=1 =0

Q=1 =0

Master-Slave-JK-Flip-Flop

J=1 =0 K=1 =0 C=1 =0 Q=1 =0

Master-Slave-JK-Flip-Flop

● Eigenschaften:● JK-Eingänge entsprechend zu Q

▪ Q bleibt stabil (wie MS-FF)

● JK-Eingänge gegenteilig zu Q▪ Q ändert sich (wie MS-FF)

● J=K=1▪ Q toggelt bei fallender Taktflanke▪ Keine undefinierten Zustände

Master-Slave-JK-FF mit direkten Eingängen

● Zwei weitere Eingänge üblich● R=Reset

▪ Bewirkt asynchrones Löschen (Q=0)

● P=Preset▪ Asynchrones Setzen (Q=1)

1-Bit-Speicher

● Problem des Überschreibens:▪ Brauchen definierten Zeitpunkt, wenn Eingänge stabil▪ Wählen ein Eingang (D=data)▪ Zusätzlich ein Schreibeingang (W=write)▪ Synchroner 1-Bit-Speicher

1-Bit-Speicher

● Schreibvorgang bei fallender Taktflanke und W=1

● Zusätzlich möglich: Leseeingang (R=read)▪ Q=0 falls R=0

● Andere Möglichkeit:▪ Kombinierter RW-Eingang mit CS („Chip Select“)

D=1 =0 W=1 =0 C=1 =0 Q=1 =0

1-Bit-Schreib-Lese-Speicher

● Ziel: Speicherzelle soll ein- bzw. ausgeschaltet werden▪ Ausschalten der Ausgabe mit R (=read)▪ Kombinierter RW-Eingang mit CS („Chip Select“)

Q‘RW

1-Bit-Schreib-Lese-Speicher

● Ziel: Speicherzelle soll ein- bzw. ausgeschaltet werden (mit CS)▪ RW gibt die „Richtung“ an▪ D muss nur zum gewählten Zeitpunkt gültig sein

D =1 =0 RW=1 =0 CS =1 =0 Q =1 =0

Schreibzyklus Lesezyklus

Mehr-Bit-Speicher

● Bsp: 4-Bit-Speicher, ein Bit soll gewählt werden

● RW und D gemeinsamer Eingang

● Adressbus A[0-1] selektiert Bit

Speicherbausteine

● Üblicher Speicher für schnelle Anwendungen● Auswahl der Reihe durch Adressleitung

▪ RAM (=„random access memory“)

● Verliert keine Informationen, solange Gatter arbeiten▪ Statisch (=static)

● SRAM

A[0-1]

D0 D1 D2 D3 D4 D5 D6 D7

D1 D2 D3 D4 D5 D6 D7D0

D[0-7]

Zusammenfassung

● Basis-Flip-Flop (FF) merkt sich Zustand („latch“) zu beliebiger Zeit▪ Nachteile:▪ Nicht synchron▪ Undefinierte Zustände möglich

● Getaktetes RS-FF übernimmt nur bei C=1● Master-Slave-FF übernimmt bei C=1,

▪ Bis C=(1→0) Zustandsänderung möglich▪ Ab C=0 Eingang eingefroren, Slave gibt

übernommenen Zustand an Ausgang

Zusammenfassung

● Master-Slave-JK-FF▪ Keine undefinierten Zustände▪ Weiterentwicklung: Direkte Lösch- (R-) und

Setzeingänge (P)

● 1-Bit-Speicher▪ RW-Eingang für Schreib-/Leserichtung▪ CS definiert Zeitfenster, wenn Daten stabil und gültig

● Mehr-Bit-Speicher mit Adressierung● Parallele Datenein- und Ausgabe (z.B. 8 Bit)

Können Zustände speichernUrsprüngliches Problem:

Vereinfachung von Schaltnetzen

Teil 1: Logik1d: Serielle Rechenwerke

0111 +1011

10 11 10 10=10010

Mensch ist nicht zu parallelem

Arbeiten ausgelegt

Bit-für-Bit-Ausgabe von Binärzahlen

10010 - 1011

11 11 11 10 =00111

Schieberegister (SR)

● Reihenschaltung von FF‘s

● Serielle Eingabe Dser wird parallelisiert (Q-Ausgänge der einzelnen FF‘s)

● Seriell-Parallelumsetzer

Dser C

1 01 0 000 110 0 10 1

Q0 Q1 Qn

Zeitverhalten SR

Zeit T0 T1 T2 T3 T4

Dser 1 0 0 1 0

Q0 0 1 0 0 1

Q1 0 0 1 0 0

Q2 0 0 0 1 0

Q3 0 0 0 0 1

● 4-Stufiges SR: Setzt serielle Information in 4 Taktzyklen in parallele Information um

● Rechendauer vs. Parallelisierung

● Benutzen direkte Setz- und Löscheingänge

● Ersetze jedes FF (x) in SR durch obige Schaltung

Parallele Eingabe

D0 D1 Dn

Q0 Q1 Qn

Links-Rechts-Schieberegister (LR-SR)

● Reihenschaltung von FF‘s● JK-Eingänge werden jeweils mit LR und MUX

umgeschaltet

LR LR LR

Serielles AddierwerkAugend

0 1 1 1

Addend

1 0 1 1

0 0 0 0

Carry-Bit

0 0 1 1

0 1 0 1

0 0 0 0

Takt: 1

0 0 0 1

0 0 1 0

1 0 0 0

0 0 0 0

0 0 0 1

0 1 0 0

0 0 0 0

0 0 1 0

Eigenschaften serielles Addierwerk

● 3 Register ▪ 2 für Operanden

• Paralleleingang wird für Startwerte benutzt• Serieller Eingang wird auf „0“ gelegt

▪ 1 für Ergebnis• Parallelausgang für Ergebnis

● Ergebnis wird um ein Bit erweitert (letzter Übertrag)▪ Carry-Bit (spezielles „Register“)

● N-Bit-Addition benötigt N Takte● Problem: Weitere Takte würden Ergebnis

löschen

Serielles Addierwerk mit AkkumulatorOperand

0 1 1 1

Akkumulator

1 0 1 1

Carry-Bit

0 1 1 1

Takt: 1 2 3 4

0 0 1 0

0 0 0 0

Akkumulator

● Vorteile● Nur 2 Register werden benötigt● Ergebnis steht gleich wieder für neue Operation

zur Verfügung▪ Nach Prüfung des Carry-Bits

• Carry-Bit evt. löschen

▪ Nach Initialisierung des Operanden

● Analog: Subtraktion▪ Umschaltbarer Addierer/Subtrahierer

● Immer noch offen: Erzeugung von N Taktpulsen

Zähler

C=1 =0Q0=1 =0Q1=1 =0

Q2=1 =0

Asynchroner Zähler

● Q0 wirkt als Takt für Q1

● Q1 wirkt als Takt für Q2

● Usw.

● Laufzeit pro Umklappvorgang tD

● Insgesamt (n-1)*tD Zeitversatz zwischen erstem und letztem Bit

● Kombinatorische Logik zum Dekodieren:● Gefährlich! (sog. „ripple counter“)● Brauchen synchrones Design

Synchrone Zähler

● JK-FF mit J=K=1 ist 2er-synchron-Zähler Q0

▪ Toggelt bei jedem Takt

● Für 4er-Zähler muss Takt synchron 2tem FF zugeführt werden.▪ Übergangstabelle aufstellen

Zähler-stand

(Toggeln)

(Setzen)

Zähler-stand

Synchrone Zähler: Aufbau

● 4er-synchron-Zähler▪ J0=K0=1 und J1=K1=Q0

● Analog:● 8er-synchron-Zähler

▪ J0=K0=1 und J1=K1=Q0 und J2=K2=(Q0 & Q1)

Start-Stop-Logik

● Ziel: Brauchen 4 Taktpulse

0…7C

RQ0 Q1 Q2

Inaktiv

Start-Stop als Zustand

● Kombinatorische Logik bestimmt:▪ Wenn Aktiv

• Zähler=Zähler+1

• Cout=Cin

▪ Wenn Inaktiv• Zähler=0

• Cout=0

(Zähler als „Black Box“ angenommen)

● Brauchen Zustandssteuerung für Aktiv/Inaktiv

Inaktiv

Start = 0

Start = 1

Zähler < 4

Zähler ≥ 4

Multiplikationen

● Dezimalzahlen

35 * 12

+ 2*5=10+ 1*5= 5 + 2*3= 6+1*2= 2= 320

● Binärzahlen

101 *101110

+1* 101110+0 +1*101110= 11100110

Parallel-Multiplikation

● 1 Bit

● 2 Bit▪ Aufwendig

● 3 Bit▪ 3*3 UND-Gatter▪ 3 VA + 3 HA▪ Noch aufwendiger!

P0 P1 P2 P3

Serien-Multiplizierer

● Multiplikant 2 Bit● Multiplikator 3 Bit● Akkumulator 4(+1)

Bit● Langsam

(Additionen mit M=0)

Multiplikant

0 0 1 1

Akkumulator (Produkt)

0 0 0 0

Multiplikator

0 1 1 1

0 0 1 1

0 1 1 0

1 0 0 1

0 0 0 1

1 1 0 0

0 1 0 1

Zustände Serienmultiplizierer

Inaktiv 1234

● Bsp: 2Bit * 3Bit▪ Hier nur 1. Zyklus▪ Akkumulierung nicht nötig, falls M=0▪ Übergänge müssen kontrolliert werden▪ Nächstes Kapitel

Start = 0

Start = 1

LR-Shift& M = 1

Start = 1 & M = 0

Teil 1: Logik1e: Zustandsautomaten

Synchroner Zähler als Zustandsautomat

● Betrachte Zählerstand als Zustand

● Übergänge ohne Randbedingungen

Zustandsautomat (1)

● Nur Ausgabe▪ Hier Codierung

möglich

● Keine Eingabe▪ Takt und

asynchroner Reset kein Eingang!

Zustandsspeicher

„0“, „1“, „2“, „3“Flip-Flops

Übergangsregeln

Wenn „0“, dann „1“Wenn „1“, dann „2“Wenn „3“, dann „4“Wenn „4“, dann „0“

KombinatorischeLogik

AusgabeKombinatorischeLogik

Codierung der Zustände

● Natürliche Codierung:▪ „0“ ist 00▪ „1“ ist 01▪ „2“ ist 10▪ „3“ ist 11

● Decodierung nicht nötig

● „One-Hot“ Codierung:▪ „0“ ist 0001▪ „1“ ist 0010▪ „2“ ist 0100▪ „3“ ist 1000

● Decodierung z.B. durch 4-zu-2-Kodierer

Codierung der Zustände

● Bsp: Ampelfarben▪ „Rot“ ist 001▪ „Gelb“ ist 010▪ „Grün“ ist 100▪ „Rot-Gelb“ ist 011▪ Natürliche Codierung,

„verschwendet“ Flip-Flops

● Nur 4 Zustände, 2 FFs reichen aus, „dichte Codierung“▪ „Rot“ ist 10▪ „Gelb“ ist 01▪ „Grün“ ist 00▪ „Rot-Gelb“ ist 11

● Im Prinzip jede Codierung möglich(Schaltungsaufwand, Timing)

Synchroner Zähler als Zustandsautomat

● Betrachte Zählerstand als Zustand

● Möchte Vorwärts- und Rückwärtszählen

● Eingang R

R=1R=1

Zustandsautomat (2)

● Eingänge▪ Beeinflussen

Übergangs- regeln

Zustandsspeicher

„0“, „1“, „2“, „3“Flip-Flops

Übergangsregeln

Eingänge

Definitionen

● (Zustands-)Automat („state machine“): ▪ System, dass verschiedene Zustände annehmen

kann▪ Übergänge hängen von Eingangsvariablen ab

● Endlicher Automat („finite s.m.“)▪ Nur begrenzte Anzahl von N Zuständen

● Deterministischer Automat▪ Eingangsinformation und Vorzustand bestimmen

Verhalten eindeutig

● Endlicher, deterministischer Automat ▪ …Grundlage der Prozesssteuerung

Zustandsautomat (3)

● Eingänge gehen nur in Übergangslogik▪ Moore-Automat

● Eingänge gehen auch in Ausgabelogik▪ Mealy-Automat

Zustandsspeicher

„0“, „1“, „2“, „3“Flip-Flops

Übergangsregeln

Eingänge

Moore vs. Mealy

● Moore Spezialfall von Mealy● Mealy kann sofort reagieren● Weniger FFs● Mehr kombinatorische Logik● Aber: kombinatorische Logik kann kritisch

werden. Hazards, Spikes● Mealy kann in Moore umgewandelt werden (1

Takt Zeitverlust)

Ampelanlage - Aufgabenstellung

● Zwei kreuzende Straßen▪ Hauptstraße (1) soll „Grün“ haben▪ Nebenstraße (2) soll „Rot“ haben, bis Auto wartet

● Berücksichtigung von Fußgängern▪ Beide Straßen „Rot“ für Fußgängerphase

● Eingänge ▪ Auto wartet A=1▪ Fußgänger wartet F=1

Ampelanlage - Zustandsdiagramm

A=0 & F=0

A=1 | F=1

F=1F=0

RotGelbF

Grün2

RotGelbF

Grün2

Wahl der Codierung

● 7 Zustände: Dichte Codierung benötigt 3 FFs▪ „XYZ“

● Ausgänge▪ Bsp: ▪ A1Rot=X|(¬X&Y&¬Z)

● Simulation

RotGelbF

Grün2

Schaltungsentwurf

● Hier nur erste 4 Übergänge(Achtung: 000-Schleife fehlt!)

RotGelbF

Kombinatorische Logik als ROM

● Fasse die 3 FF-Ausgänge + 2 Eingänge als Adresse auf

● Die 3 Übergangs-Ausgänge und 8 Ampellichter als Bitmuster:

● 32 Wörter à 11 Bit● ROM=„Read Only

Memory“

XYZAF X‘Y‘Z‘111222FF

00000 000 001 100 10

00001 001 001 100 10

00010 001 001 100 10

00011 001 001 100 10

00100 010 010 100 10

00101 010 010 100 10

Kombination von Zustandsmaschinen

● Schlecht: Fußgänger drückt kurz, Zustand geht von „Grün“ nach „Gelb“, was macht Maschine?

● „Normale“ Ampel; Fußgänger drückt, Licht geht an

● Brauchen Start-Stop-Logik (War selbst schon Automat)

Start/Stop

Fußgänger

F-Ampel Rot

Zusammenfassung Kapitel 1

● Grundgatter UND, ODER, NICHT als boolsche Funktionen

● Schaltfunktionen und –netze als Funktionstabelle oder kombinatorisch

● Umwandlungen der Implementierung● Paralleladdierer, -subtrahierer, -multiplizierer● Kombinatorische Logik begrenzt● Zustandsspeicher: Flip-Flop● Zähler

Zusammenfassung Kapitel 1

● Schieberegister● Serieller Addierer, Subtrahierer, Multiplizierer● Codierung von Zuständen allgemein● Übergänge von Zuständen● Moore und Mealy-Automaten● Funktions- und serielles Verhalten in ROM

Ausblick: Arbiter

Gerät 1 Gerät 3Gerät 2

Arbiter

Technische Informatik I (SS 2006) Zusammenfassung Halbaddierer / -subtrahierer unterscheiden sich...

Documents