Digitaltechnik - 20K%94nig/Digtech2_2.pdf · ´0010´ ´1001 ´ Kodierung ... 101 100 011 010 001 000 ¾Stetige, physikalische Größen (Sensoren) ... 4 0100 0100 1 0100 0 3 0011

1

Digitaltechnik

© Andreas König Folie 2-1

Kodierung und Arithmetik

DigitaltechnikAndreas König

Professur Technische InformatikFakultät Informatik

Technische Universität Chemnitz

Wintersemester 2001/2002

Digitaltechnik



Rekapitulierung zu Kapitel 1

Motivation und Einführung zum Gebiet DigitaltechnikAbgrenzung von Analogtechnik und DigitaltechnikEinführung von Signalen der Digitaltechnik und Betrachtung des InformationsgehaltsDarstellung der geschichtlichen Entwicklung der RechentechnikZusammenhang Digitaltechnik und MikroelektronikNotwendigkeit und Methodik des systematischen bzw. automatisierten Entwurfs digitaler Systeme

Vorarbeit für detaillierte Erarbeitung desGebiets in den folgenden Kapiteln und Semesterwochen

Ein Beispiel:

2

Digitaltechnik



Vorlesungsgliederung:1. Einführung2. Kodierung und Arithmetik3. Grundlagen der booleschen Algebra4. Entwurf zweistufiger kombinatorischer Logik5. Zieltechnologien und Technologieanpassung6. Zeitliches Verhalten kombinatorischer Schaltnetze7. Entwurf sequentieller Schaltwerke 8. Funktionsblöcke digitaler Rechner und Systeme9. Entwurf von Systemen der Digitaltechnik10. Ausblick

Digitaltechnik



Kapitelgliederung:

2. Kodierung und Arithmetik2.1 Kodierung2.2 Analog/Digital-Umsetzung2.3 Zeichendarstellung2.4 Kodes für Fehlererkennung und –korrektur2.5 Optimale Kodes2.6 Polyadische Zahlensysteme 2.7 Kodewandlung2.8 Kodeumschaltung

3

Digitaltechnik



Aus der einführenden Darstellung zur historischen Entwicklung von Rechnern ist der Bedarf geeigneter Informationsrepräsentation klar gewordenBeispielsweise müssen Zeichen aus der menschlichen Begriffswelt in eine maschinengeeignete Repräsentation abgebildet werdenEin Kode ist eine Vorschrift für die eindeutige Zuordnung der Zeichen eines Zeichenvorrats (Urmenge) zu denjenigen eines anderen Zeichenvorrats (Bildmenge)

Die Zuordnung muss nicht umkehrbar eindeutig sein !

Kodierung

A

b

a

BC c

Dd

.--...

-.-.-..

Digitaltechnik



Die zwei Zustände L und H binärer Signale der Digitaltechnik werden typisch mit den Symbolen 0 und 1 bezeichnetZeichen sind dann Vektoren aus Binärstellen (Kodewörter):

Kodierung

´0´´1´

´2´´3´

´9´bis

´0000´

´0001´´0011´

´0010´´1001´

Kodierung

Dekodierung

Beschreibung der Kodierungsvorschrift: Tabelle oder Algorithmus

4

Digitaltechnik



Für m Binärstellen lassen sich 2m Kodewörter verwendenDie Zahl der zu nutzenden Kodewörter N muss N <= 2m seinAuswahl und Strukturierung der Kodewörter nach bestimmten Überlegungen und Randbedingungen:

• O/1-Verteilung (Anzahl k der Einsen, Lage der Einsen)• Bestimmte Distanz zwischen aufeinanderfolgenden Kodewörtern

Die Hammingdistanz DH gibt den Unterschied oder die Distanz zwischen zwei gleichlangen Kodewörtern xj und xk als skalaren Wert:

Kodierung

Beispiel Thermometerkodierung:

ki

m

ijiH xxD ⊕=∑

=1

⊕ DH = 3

Digitaltechnik



Bei fester Vorgabe der erlaubten Zahl k von Einsen ohne Einschränkungen der Lage kann bei m-stelligen Kodewörtern eine Zahl von Kodewörtern gebildet werden

Beispiel für m=5 und k=2 und damit N=10 (z.B. für Ziffern ´0´bis ´9´):

Kodierung

)!(!!

kmkm

km

−=

1001001100

1000101010

0100100110

1100000101

1010000011

Minimale Distanz DH = 2 zwischen Kodewörtern dieses (2aus5)-Kodes!

5

Digitaltechnik



Die Kodierung von Information dient dem Zweck, günstige Eigenschaften bezüglich Merkmalen wie• Verarbeitbarkeit• Lesbarkeit (Mensch/Maschine)• Übertragbarkeit• Fehlersicherheit• Speicherbarkeit• Vertraulichkeit, Datensicherheit (Kryptographie)

Je nach vorliegender Priorität dieser Merkmale und Randbedingungen der Aufgabe kommt man zu verschiedenen KodierungenEinige für die Digitaltechnik wichtige Kodes werden im folgenden vorgestellt

Kodierung

Digitaltechnik


Kodierung und ArithmetikAnalog/Digital-Umsetzung

Kodes für die Analog zu Digitalwandlung:

111110101100011010001000

Stetige, physikalische Größen (Sensoren) in Binärwörter umsetzenWandlungsgenauigkeit vom jeweiligen Prinzip abhängigProblem: Wechsel mehrerer Ziffern zwischen Kodewörtern erfolgt nicht gleichzeitig !Abhilfe: Kodes mit DH=1, z.B. Gray-Kode (später)

101

6

Digitaltechnik



Wesentlich für die Datenverarbeitung ist eine Repräsentation, die die Bearbeitung textueller Daten erlaubtEbenso Kodierung für den Austausch von Informationen und Daten zwischen digitalen Teilsystemen (Austauschkodes)Wesentliches Merkmal: Lexikographische Anordnung der Zeichen des zu kodierenden Alphabets wird in eine entsprechende Anordnung in einem Binäralphabet abgebildetAlphabetische Sortierung von Textdaten wird damit durch einfache Vergleichsoperationen möglichEin wesentlicher, weitverbreiteter Vertreter ist der ASCII-KodeEr umfasst Buchstaben, Ziffern und viele international übliche Sonder- und Steuerzeichen

Zeichendarstellung

Digitaltechnik


Kodierung und ArithmetikZeichendarstellung

Tabelle des ASCII-Kodes

DELo_O?/USSI-F/1111

~n^N>.RSSO-E/1110

}m]M=-GSCR-D/1101

|l\L<‘FSFF-C/1100

{k[K;+ESCVT-B/1011

zjZJ:*SUBLF-A/1010

yiYI9)EMHAT-9/1001

xhXH8(CANBS-8/1000

wgWG7´ETBBEL-7/0111

vfVF6&SYNACK-6/0110

ueUE5%NAKENQ-5/0101

tdTD4$DC4EOT-4/0100

scSC3#DC3ETX-3/0011

rbRB2“DC2STX-2/0010

qaQA1!DC1SOH-1/0001

p`P@0SPDLENUL-0/0000

7-111

6-110

5-101

4-100

3-011

2-010

1-001

0-000

HexBinär

MSBLSB

American

Standard

Code

for

Information

Interchange

7

Digitaltechnik



Bedeutung der ASCII-Steuerzeichen:

Zeichendarstellung

DeleteDEL

Unit SeparatorUSShift InSI

Record SeparatorRSShift OutSO

Group SeparatorGSCarriage ReturnCR

File SeparatorFSForm FeedFF

EscapeESCVertical TabVT

Substitute SUBLine FeedLF

End of MediumEMHorizontal TabHT

CancelCANBackspaceBS

End of Transmission BlockETBBellBEL

Synchron. IdleSYNAcknowledgementACK

Not AcknowledgmentNAKEnquiryENQ

Device Control 4DC4End Of TransmissionEOT

Device Control 3DC3End Of TextETX

Device Control 2DC2Start of TextSTX

Device Control 1DC1Start of HeadingSOH

Data Link EscapeDLEAlle Leitungen NULLNUL

Ein Beispiel:

Digitaltechnik



Die 7-stelligen Kodewörter reichen allerdings oft für Sonderzeichen anderer Sprachen (Umlaute) nicht ausErweiterung oder Modifikation des Kodes erforderlichBeispielsweise besitzt UNICODE (Norm ISO 10646 v1.2) 16 Stellen und überdeckt den ASCII-Kode mit seinen ersten 128 ZeichenAustauschkodes im weiteren Sinne zur MMK:• Sieben-Segment-Kode• Punktmatrixanzeige• Kodes zur Verbesserung der Maschinenlesbarkeit (Neue

Nummernschilder nach DIN 66008 in OCR-A-Schrift)• Blindenschrift

Oft auch Kombination von Kodes für maschinelles und menschliches Lesen (Strichkode und Zahlen)

Zeichendarstellung

8

Digitaltechnik



Bei Übertragung und Speicherung digitaler Signale (Binärinformation) kann physikalische Repräsentationsgröße durch Störeinflüsse verfälscht werdenFolge: Übertragungs- bzw. SpeicherfehlerInteresse: Erkennung bzw. Korrektur des/der aufgetretenen Fehler(s)Vorgehensweise: Geeignete Kodierung die durch zusätzlichen minimalen Aufwand (Redundanz) Erkennung/Korrektur ermöglichtKorrektur erfordert mehr Aufwand als Erkennung !Annahme der Zahl gleichzeitig zu berücksichtigender Fehler (1 oder 2)Ergänzung der Binärdarstellung, Fehler führen Kodewörter, die nicht in Kodierung verwendet werden (Fehlererkennung)Verdeutlichung:

Fehlererkennung und –korrektur

0010 0011 01111 Fehler 1 Fehler

gültigesKodewort

gültigesKodewort

unbenutztesKodewort,Fehlerfall

Digitaltechnik



Einsfehlerkennung durch Ergänzung des Kodewortes, so dass Anzahl der Einsen auf eine gerade bzw. ungerade Anzahl gebracht wird (evenoder odd parity)Erforderliche Ergänzung für BCD-Kode:


1001 11001 010019

1000 01000 110008

0111 00111 101117

0110 10110 001106

0101 10101 001015

0100 00100 101004

0011 10011 000113

0010 00010 100102

0001 00001 100011

0000 10000 000000

ungeradegeradeBCDDezimal

BCD-Kode mit Parität

9

Digitaltechnik



Fehlerkennung durch Geradzahligkeitsprüfung


1 0 0 0 1

Geradzahligkeits-prüfung

Z=0

23 22 21 20 E

FehlerFehlerkein

Z

=10

Fehlerkennung durch UngeradzahligkeitsprüfungErweiterung des Konzepts von einzelnen Kodewörtern zur Blocksicherung mit doppelter QuersummenergänzungSpalten und Zeilen eines Blocks ergänzenBei einem Fehler über Zeile/Spalte der fehlerhaften Quersumme Fehlerkorrektur möglich

Ein Beispiel:

Digitaltechnik



Beispiel für Blocksicherung [Lipp 99]:


10100Prüfwort

001106

111107

011003

111001

100104

010105

BCD-Kode mit gerader ParitätZiffer

Spalte mit Fehler(ungerade Parität)

Zeile mit Fehler(ungerade Parität)

Ein Beispiel:

10

Digitaltechnik



Fehlerkorrektur bzw. Erkennung von zwei FehlernDas fehlerhafte Kodewort muss die Information liefern, aus welchem Kodewort es entstanden istGültige Kodeworte müssen für die Erkennung von zwei Fehlern eineentsprechende Distanz aufweisen

Schema erlaubt Ein- bzw. Zweifachfehler erkennen oder Einfachfehler korrigieren


0010 0011 11111. Fehler

1. Fehler

gültigesKodewort

unbenutztesKodewort,Fehlerfall

0111unbenutztesKodewort,Fehlerfall

Korrektur

Korrektur2. Fehler

2. Fehler

Ein Beispiel:

Digitaltechnik



Der Hamming-Kode (hier: (7,4)) ist ein solcher fehlerkorrigierender KodeKodewörter haben den Mindestabstand von DH=3Der Kode besteht aus 7 bit, die in drei Kontrollgruppen strukturiert sindJede Kontrollgruppe des Hamming-Kodes besteht aus drei Informations-bits und einem Kontroll-bit


10011009

00001118

11110007

01100116

10100105

00110014

11000013

01010102

10010111

00000000

202122K223K1K0Wertigkeit

7654321Bit-Nr.

Kontrollgruppen:• K0: K0232220

• K1: K1232120

• K2: K2222120

Allgemeine Bildungsregel:

Bsp.: d=8 bit, p=4 bit

ppd 21≤++

11

Digitaltechnik



Beim Hamming-Kode erfolgt Geradzahligkeitsprüfung für jede KontrollgruppeEin Kodewort (7 bit) ist immer dann fehlerhaft wenn mindestens eine Geradzahligkeitsprüfung Fehler anzeigt


Geradzahligkeits-prüfung K2

1 2 3 4 5 6 7



ZC ZAZB

Digitaltechnik



Tabellarische Zusammenstellungen der Fehlermeldungen der Geradzahligkeitsprüfungen mit den Ausgangswerten

Über die Ausgangswerte der Geradzahligkeitsprüfer wird beim Hamming-Kode die Nummer des fehlerhaften bit angegeben


202122

111K0, K1 und K27

011K1 und K26

101K0 und K25

001K24

110K0 und K13

010K12

100K01

K0

ZA

K1

ZB

K2

ZC

Fehlermeldung derGeradzahligkeitsprüfung

Fehler im bit Nr.:

Ausgangswerte

12

Digitaltechnik


Kodierung und ArithmetikOptimale Kodes

Die Länge der Nachricht bestimmt den Aufwand der ÜbertragungMinimierung des Übertragungsaufwands durch geschickte Kodierung bzw. Kompression der Daten (Kanalkodierung)Verlustfreie und verlustbehaftete Verfahrensvarianten (JPEG, MPEG)Ausnutzung unterschiedlicher Auftrittshäufigkeiten von Zeichen durch Kodierung der Zeichen mit unterschiedlich langen KodewörternBeispiel Morse-Kode: Ausnutzung der statistischen Eigenschaften der englischen Sprache zur kompakten NachrichtendarstellungVerallgemeinerung: Optimale Kodes (Shannon-Fano und Huffman)Ziel: Minimierung der

mittleren Kodewortlänge:

Minimal erreichbarer Idealwert: Durchschnittlicher Informationsgehalt

∑=

•=N

i ipldipH

1 )(1)(

∑=

•=N

iimipm

1)()(

Digitaltechnik



Morse Alphabet:

Optimale Kodes

--..Z--M-.--Y.-..L-..-X-.-K

----.9.--W.---J---..8.--V..I--...7..-U....H-....6-T--.G.....5...S..-.F....-4.-.R.E...--3--.-Q-..D..---2.--.P-.-.C.----1---O-...B-----0-.N.-A

Kodierung der Zeichen mit unterschiedlich langen Kodewörtern

13

Digitaltechnik



Konstruktion des Shannon-Fano-Kodes:• Ausgangsbasis: Zeichenvorrat mit zugehörigen

Auftrittswahrscheinlichkeiten• Nach aufsteigender Wahrscheinlichkeit linear ordnen• In zwei Mengen aufteilen, so dass die Summenwahrscheinlich-

keiten beider Mengen möglichst gleich sind• Die erste Teilmenge erhält als (erstes) Kodierungszeichen für das

entstehende Kodewort eine ´1´, die andere eine ´0´• Rekursiv wird für die beiden entstandenen Teilmengen das

Verfahren wieder angewendet, bis nur noch je ein Zeichen in den resultierenden Teilmengen verbleibt

• Anschaulich wird ein binärer Baum aufgebaut, dessen Blätter die Zeichen des Zeichenvorrats repräsentieren und dessen Äste auf dem Weg zu den Blättern die jeweiligen Kodewörter repräsentieren

Digitaltechnik



Geben sei ein Zeichenvorrat der Zeichen a, b, c, d, e mit den zugeordneten Wahrscheinlichkeiten 0,1; 0,1; 0,2; 0,3; 0,3;

Optimale Kodes

{a,b,c,d,e}

∑ =1p

∑ =1p

{a,b,c} ∑ = 4,0p

{a,b}

{a} {b}

{c}

p=0,1 p=0,1

p=0,2 p=0,3 p=0,3

∑ = 2,0p

∑ = 6,0p{d,e}

1

1

1

1

0

0

0

0

Kodierung:111001001000

edcba

14

Digitaltechnik



Wie gross ist die mittlere Kodewortlänge ?

2,223,023,022,031,031,0

)()(1

=•+•+•+•+•=

•=∑=

mm

imipmN

i

Ein Beispiel:

Digitaltechnik



Unabhängig von der Betrachtungsebene des Anwenders verarbeiten Schaltungen und Systeme der Digitaltechnik numerische und symbolische Informationen in binärer Repräsentation Symbolische Information wird z.B. durch vorgestellte Kodes umgesetztDie Handhabung numerischer Information (Zahlen) ist essentiell Zahlendarstellung, Konversion und Arithmetik sind grundlegend für die Realisierung effizienter digitaler SystemePolyadische Zahlensysteme, z.B. unser Dezimalsystem, haben folgenden Aufbau:

mit N: Zahl im Zahlensystem, R: Basis (Grundzahl, Radix) R>=2Ri: Wertigkeit der Stelle i, di: Ziffer der Stelle i, Z: Menge der Ziffern

Polyadische Zahlensysteme

00

11

0

... RdRdRdRdN nn

n

i

ii +++==∑

=

15

Digitaltechnik



Ergänzend zu der vorgestellten Repräsentation einer natürlichen Zahl wird eine reelle Zahl für p Vorkomma- und n Nachkommastellen dargestellt mit

Gebräuchliche Zahlensysteme sind:• Dualsystem mit R= 2 und ZB = {0,1} • Oktalsystem mit R= 8 und ZO = {0,1,2,3,4,5,6,7} • Dezimalsystem mit R= 10 und ZD = {0,1,2,3,4,5,6,7,8,9}

Beispiel:

• Hexadezimalsystem mit R= 2 und ZH = {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}Beispiel:


∑−≥≥−

±=nip

ii RdD

1

0123 1011001001022001 •+•+•+•=D

0101 1610161101011 DDHHH AA •+•=•+•=

Digitaltechnik



Anmerkung: Begriff Dualzahl oder –darstellung ist für die Repräsentation einer Zahl oder Ziffer mit Hilfe von Binärgrößen in polyadischer Darstellung reserviert.Andere Fälle werden als Binärvektoren oder –darstellung bezeichnet. Zahlendarstellungen in vier Systemen:


1 42 02 41 0 1 0 0

1 31 92 31 0 0 1 1

0 A1 01 20 1 0 0 1

0 90 91 10 1 0 0 1

0 80 81 00 1 0 0 0

0 50 50 50 0 1 0 1

0 40 40 40 0 1 0 0

0 30 30 30 0 0 1 1

0 20 20 20 0 0 1 0

0 10 10 10 0 0 0 1

0 00 00 00 0 0 0 0

Hexadezimalzahlen161 160

Dezimalzahlen101 100

Oktalzahlen81 80

Dualzahlen24 23 22 21 20

16

Digitaltechnik


Kodierung und ArithmetikKonvertierung zwischen Zahlensystemen

Beispielsweise die Ein- und Ausgabe alltäglicher Information in Rechenanlagen, z.B. Preise, Kontostände, etc., erfordert den Wechsel der Basis und damit die Konversion des Wertes vom Quell- ins ZielsystemBei Zahlensystemen, deren Basis eine Potenz der Basis eines anderen Zahlensystems ist, gestaltet sich die Konvertierung günstig:Hexadezimal Dual: 1BE8H = 0001|1011|1110|1000BOktal Dual: 721O = 111|010|001B

Bei Konvertierungen zwischen beliebigen Zahlensystemen stehen allgemeine Konvertierungsalgorithmen zur VerfügungEin einfacher Ansatz ist die Notation der Zahl durch Ziffern undStellengewichten im Zielsystem, gefolgt von Ausrechnung des Zahlenwertes im Zielsystem: 122.13 = 1* 32 + 2* 31 + 2* 30 + 1* 3-1 = 17.3333310

F1AC16 = 15* 163 + 1* 162 + 10* 161 + 12* 160 = 6186810

13410 = (1* 102 + 3* 101 + 4* 100 )10 = (1* 1012 + 10* 1011 + 11)3 !

Digitaltechnik



Für ganze Zahlen bietet der Divisionsalgorithmus eine günstige allgemeine Konversion einer Zahl NR1 im Zahlensystem mit der Basis R1in eine Zahl NR2 im Zahlensystem mit der Basis R2:

Dies kann umgeformt werden zu:

Aus dieser Darstellung lässt sich erkennen, daß durch sukzessive Division beider Seiten der Gleichung durch die Zielbasis im Quellsystemder Divisionsrest (mod) jeweils eine Ziffer der zu konvertierenden Zahl in der Zielbasis von der niederwertigsten zur höchstwertigenStellenwertigkeit (LSD/MSD; LSB/MSB) ergibt. Die niederwertigste Stelle von NR2 ist (NR1 mod R2) = d0

020

121

1211

RdRdRdN nnR •+•++•= −− K

021221 )))((1

dRdRRdN nR +•+•+•= − KK

17

Digitaltechnik



Beispiele: Umwandlung von 13410 in eine Dualzahl:

134 / 2 = 67 R 0 (LSB)/ 2 = 33 R 1

/2 = 16 R 1/2 = 8 R 0

/2 = 4 R 0/2 = 2 R 0

/2 = 1 R 0/2 = 0 R 1 (MSB)

Also ist 13410 = 100001102

Digitaltechnik



Weitere Beispiele: Umwandlung von 46710 in eine Oktalzahl:

467 / 8 = 58 R 3 (LSD)/ 8 = 7 R 2

/8 = 0 R 7 (MSD) Damit ist 46710 = 7238

Umwandlung von 198910 in eine Hexadezimalzahl:

1989 / 16 = 124 R 5 (LSD)/ 16 = 7 R 12

/16 = 0 R 7 (MSD)

Nach Umwandlung der Ziffern ins Zielsystem ist 198910 = 7C516

18

Digitaltechnik



Für gebrochene Zahlen NR1 bietet der Multiplikationsalgorithmus eine entsprechende Konversionsmöglichkeit:

Dies kann umgeformt werden zu:

Sukzessive Multiplikation beider Seiten der Gleichung mit der Zielbasis R2 im Quellsystem ergibt jeweils durch Abschöpfung der entstehenden Vorkommastelle eine Ziffer der zu konvertierenden Zahl in der Zielbasis von der höchstwertigen zur niederwertigsten Stellenwertigkeit (MSD/LSD; MSB/LSB) ergibt. Die höchstwertigste Stelle von NR2 ist (NR1 * R2) = d-1

nn

nnR RdRdRdN −

−+−

+−−

− •+•++•= 21

211

211K

))))((( 121

122

121

121

KK nnR dRdRdRdRN −−

+−−

−−

−− •+•++•+•=

Digitaltechnik



Beispiel: Umwandlung von 0.62510 in eine Dualzahl:

0.625 * 2 = 1.25 (MSB)* 2 = 0.5

*2 = 1.0 (LSB)

Also ist 0.62510 = 0.1012

Anmerkung: Da Rechnung in anderen Zahlensystemen, z.B. Division, ungewohnt ist, wird versucht die notwendigen Rechenschritte im Dezimalsystem durchzuführen. Eine Konversion zwischen beliebigenBasen kann auch durch zwei Konversion über das Dezimalsystem durchgeführt werden.

19

Digitaltechnik



Beispiel: Umwandlung von 1D316 in eine Oktalzahl über Dezimalsystem:Rechnung im Zielsystem:

1D316 = 1* 162 + 13* 161 + 3* 160 = 46710

Rechnung im Quellsystem:467 / 8 = 58 R 3 (LSD)

/ 8 = 7 R 2/8 = 0 R 7 (MSD) Damit ist 1D316 = 7238

Für den Spezialfall der Wandlung von Hexadezimal- nach Oktalsystem ist es günstiger über das Dualsystem und eine Umgruppierung der Bitstellen zu konvertieren:1D316 = 0001|1101|00112

000|111|010|0112 = 07238 = 7238

Digitaltechnik



Der zentralen Bedeutung der dezimalen Darstellung und die Schwierigkeiten bei der Umwandlung führten zu einer speziellen Darstellung Die Binary-Coded-Decimal (BCD)-Kodierung nutzt nur die Bitmuster 0-9Die ungenutzten Kombinationen werden als Pseudotetraden bezeichnet

Damit wird die Umsetzung direkt ermöglicht:

199510 = (0001 1001 1001 0101)BCD

Spätere BCD-Arithmetik wird durch Pseudotetraden und Korrektur erschwert

1 41 1 1 0

1 01 0 1 0

1 11 0 1 1

1 21 1 0 0

1 31 1 0 1

81 0 0 0

70 1 1 1

60 1 1 0

1 51 1 1 1

91 0 0 1

50 1 0 1

40 1 0 0

30 0 1 1

20 0 1 0

10 0 0 1

00 0 0 0

BCD-Zahlen101 100

Dualzahlen23 22 21 20

Ein Beispiel:

20

Digitaltechnik


Kodierung und ArithmetikArithmetik

Rechnung mit BCD-ZahlenBeispiel Konversion: Umwandlung von positiven BCD-Zahlen in eine Dualzahl:181 = 0001 1000 0001BCD

Konvertierung im Dualsystem:(((0001*1010) + 1000) * 1010 + 0001)=10110101

Umwandlung von Dualzahl in positive BCD-Zahlen:181 = 10110101

• Fortgesetzes Dividieren durch 10; Rest ergibt jeweils BCD-Stelle• Addition der Stellenwertigkeiten als BCD-Zahlen, bei Überschreitung des

Darstellungsbereichs einer Vierergruppe Korrekturaddition mit 0110 (6) zur Erzeugung eines Übertrags in die nächste BCD-Stelle(16= 00010000B = 0001 0110BCD ; 32= 00100000B = 0011 0010BCD !)

Digitaltechnik


Kodierung und ArithmetikArithmetikBeispiel Konversion: Umwandlung von Dualzahl in positive BCD-Zahlen:181 = 101101011 00012 0000

00014 0100

01018 0000

0101 < 10; keine Korrekturaddition erforderlich16 0001 0110

0001 1011 > 9; Korrekturaddition erforderlich0001 01100010 0001

32 0011 00100101 0011

64 0000 00000101 0011

128 0001 0010 10000001 0111 1011 > 9; Korrekturaddition erforderlich0000 0001 01100001 1000 0001

21

Digitaltechnik



Addition und Subtraktion vorzeichenloser Zahlen Im folgenden nur Betrachtung der Algorithmen; Schaltungen und Rechenwerke folgen in späteren KapitelnEs gelten die selben (bekannten) Regeln, die für die manuelle Rechnung mit dezimalen Zahlen gelten. Beschränkung der Betrachtung auf Dualzahlen Beispiel Addition:

X 190 10111110Y 141 10001101

C + 101111000X+Y 331 01001011

Zusätzlich zur Summe entsteht ein Übertrag (Carry)N-stellige Operanden führen zu (N+1)-stelligem Ergebnis

Übertrag aus vorhergehender Stufe

Digitaltechnik



Die Subtraktion ist der Addition ähnlich, jedoch wird bei negativem Wert der Subtraktion für zwei Ziffern von der nächsthöheren Stelle geborgt. Vergleichbar zum Carry gibt es ein ein- bzw. ausgehendes BorrowBeispiel Subtraktion:

X 229 11100101Y 46 00101110

C - 001111100X+Y 183 10110111

Zusätzlich zur Summe entsteht ein ausgehendes Borrow-SignalN-stellige Operanden führen zu (N+1)-stelligem ErgebnisAddition und Subtraktion würden unterschiedliche Rechenwerke erfordern. Behandlung vorzeichenbehafteter Zahlen

Borrow aus vorhergehender Stufe

Ein Beispiel:

22

Digitaltechnik



Darstellung vorzeichenbehafteter Zahlen• Vorzeichen-Betrag (VB)-Darstellung• Komplementdarstellung (R-Komplement, (R-1)-Komplement

In VB-Darstellung wird eine Stelle zur Repräsentation des Vorzeichens zu den Betragsstellen hinzugefügt. Im Dezimalsystem wird mit +/-, im Dualsystem mit einer 0/1 notiertKonsequenz: Doppelte Nulldarstellung +0 bzw. –0 !

0000

1100

11110001

1011

1010

10010111

0101

0110

0100

0011

00101101

1110

1000

+0

+3

+4

+5

+6

+7-0

-1

-2

-3

-4

-5

-6

-7+1

+2

BetragVZ

12012 11 −±+− −− nn KK

Digitaltechnik



Addition und Subtraktion in VB-Darstellung erfordern Fallunter-scheidungen Beträge gleichen Vorzeichens können direkt addiert werdenUnterschiedliches Vorzeichen: kleinere von größerer Zahl subtrahieren und Vorzeichen der größeren für das Ergebnis einsetzen

VB-Zahlena,b

Addition a+bSubtraktion a-b

Va=Vb

AdditionB=Ba+BbV=Va=Vb

ja nein

Ba>Bb

SubtraktionB=Ba-BbV=Va

SubtraktionB=Bb-BaV=Vb

ja neinÄnderung desVorzeichens desSubtrahenden b

Überlaufprüfung !

23

Digitaltechnik



VB-Darstellung aufwendig !Komplementdarstellung vorzeichenbehafteter Zahlen ermöglicht Rückführung der Subtraktion auf die AdditionEinsparung im RechenwerkFür Dualzahlen wird das R-Komplement oder die KR-Darstellung und damit die K2-Darstellung gebildet durch:

0000

1100

11110001

1011

1010

10010111

0101

0110

0100

0011

00101101

1110

1000

+0

+3

+4

+5

+6

+7-8

-7

-6

-5

-4

-3

-2

-1+1

+21202 11 −− −− nn KK

DRD n −=

Wertebereich unsymmetrischEinfache Nulldarstellung

Addition von positiven Zahlen

Subtraktion von positiven Zahlen

Überlauf

Digitaltechnik



Alle Rechnungen in K2 durch Addition ohne Fallunterscheidung Bildung der K2–Darstellung für Dualzahlen durch invertieren der einzelnen Bitstellen und Addition eines Eins:

X 229 011100101X 100011010C + 1

K2(X) -229 100011011

Rechenbeispiele:n=4, D= – 1 – (+2) – 1 1111– 2 1110C + 11100– 3 1101

n=4, D= – 1 + (+2) – 1 1111+ 2 0010C + 11100– 3 0001

Übertrag hat nicht mehr die Bedeutung einer Bereichsüberschreitung

24

Digitaltechnik



Eine Überlauf tritt auf, wenn die Vorzeichen der Summanden gleich sind und das Ergebnisvorzeichen davon abweichtWeitere Beispiele (n=4):

Beispiele (n=4) mit Überlauf:

+3 0011+4 0100+_________+7 0111

–2 1110–6 1010+_________–8 11000

+6 0110–3 1101+_________+3 10011

+4 0100–7 1001+_________–3 1101

–3 1101–6 1010+_________–9 10111

=+7

+5 0101+6 0110+_________+11 1011

= –5

–8 1000–8 1000+_________–16 10000

=0

+7 0111+7 0111+_________+14 1110

= –2

Subtraktion durch Komplementbildung für Subtrahenden und Addition

Digitaltechnik



Komplementbildung durch (einfache) Invertierung des Subtrahenden und EinsadditionEinsaddition durch Eingangs-Carry bei Addition:

Eingangs-Carry 1+4 0100 0100+3 0011 1100-_______________+_______+1 10001

Überlaufbedingung: Vorzeichen der Summanden nach Komplementierung des Subtrahenden gleich und unterschiedlich vom Ergebnisvorzeichen

Eingangs-Carry 1+3 0100 0011+4 0011 1011–_______________+_______–1 1111

Eingangs-Carry 1+3 0011 0011–4 1100 0011–_______________+_______+7 0111

25

Digitaltechnik



Alternative Darstellung ist (R-1)-Komplement oder die K(R-1)-Darstellung und damit die K1-Darstellung gebildet durch:

K1-Addition: Für negative Zahl wird K1-Komplement verwendet und Addition durchgeführt. Entsteht ein Carry bei der Addition, so muß dieses noch zur bisherigen Summe addiert werden (End-Around-Carry)

0000

1100

11110001

1011

1010

10010111

0101

0110

0100

0011

00101101

1110

1000

+0

+3

+4

+5

+6

+7-7

-6

-5

-4

-3

-2

-1

-0+1

+212012 11 −±+− −− nn KK

DRD n −−= 1

Wertebereich symmetrischDoppelte Nulldarstellung

Addition von positiven Zahlen

Subtraktion von positiven Zahlen

Überlauf

Digitaltechnik



Beispiele der K1-Addition (n=4):

Beispiele K1-Subtraktion (n=4) ohne bzw. mit Überlauf:

+3 0011+4 0100+_________+7 0111

+4 0100–7 1000+_________–3 1100

–5 1010–2 1101+_________–7 10111

11000

+6 0110–3 1100+_________+3 10010

10011

Subtraktion durch Komplementbildung für Subtrahenden und Addition

+4 0100 0100+3 0011 1100-_______________+_______+1 10000

10001

–5 1010 1010+7 0111 1000-_______________+_______–12 10010

1OV=1; +3 0011

26

Digitaltechnik



Multiplikation erfolgt nach den Regeln, die auch im Dezimalsystem üblich sindZiffernweise Multiplikation des Multiplikanden mit den Stellen des Multiplikators und stellengewichtete Akkumulation der PartialprodukteBeispiel für vorzeichenlose Zahlen:

Ergebnis der Multiplikation für n Stellen erfordert 2n StellenRückführung im wesentlichen auf Addition im Dualsystem (Shift/Logik)Geschwindigkeit und Aufwand durch Schaltungstechnik bestimmt

Dezimal: 11 * 1333 = 11 *3

11 = 11 *1____143

Dual: 1011 * 11011011 = 1 *1011

0000 = 0 *10111011 = 1 *1011

1011 = 1 *1011_________10001111

Digitaltechnik



Multiplikation vorzeichenbehafteter Zahlen:• Vorzeichen von Multiplikand und Multiplikator bestimmen• Von negativen Operanden wird der Betrag (K2-Komplement)

gebildet• Durchführung der Multiplikation der Beträge• Bei Gleicheit der Vorzeichen von Multiplikand und Multiplikator ist

das Ergebnis positiv, sonst negativ: K2-KomplementbildungBeispiel für vorzeichenbehaftete Zahl:

Dezimal: -21 * 17Dual: 101011 * 010001101011 * 010001

Beträge bilden:Beträge bilden:010101 * 010001010101 * 010001

Vorzeichen ungleich !Vorzeichen ungleich !Ergebnis: -357

010101 * 010001010101 * 010001010101010101 = 1 * 010101010101

000000 = 0 *000000 = 0 * 010101010101000000 = 0 *000000 = 0 * 010101010101

000000 000000 = 0 *= 0 * 010101010101010101010101 = 1 * 010101010101__________0101100101

K2: 1010011011 = -357

Ein Beispiel:

27

Digitaltechnik



Division erfolgt im einfachsten Fall nach den Regeln der Vergleichsmethode, wie sie auch im Dezimalsystem üblich istBeginnend von der höchstwertigen Stelle wird überprüft, wie oft der Divisor in den höherwertigen Teil des Dividenden passt.Vom Dividenden wird das Produkt Divisor mal Quotientenstelle subtrahiert und dann sukzessive fortgefahrenDie Division ist beendet, wenn Rest kleiner als der Divisor istBeispiel für vorzeichenlose Zahlen:

Dezimal: 217 / 11 = 19 + 8/11-11107 -99

8Quotient: 19Rest : 8

Dual: 11011001/1011 = 10011 + 1000/1011–1011

10100–101110011–10111000

Digitaltechnik



Division vorzeichenbehafteter Zahlen:• Vorzeichen von Divident und Divisor bestimmen• Von negativen Operanden wird der Betrag (K2-Komplement)

gebildet• Durchführung der Division der Beträge• Bei Gleicheit der Vorzeichen von Divident und Divisor ist das

Ergebnis positiv, sonst negativ: K2-KomplementbildungBeispiel für vorzeichenbehaftete Zahl:

Dezimal: -128 / 17Dual: 10000000 / 10001

Beträge bilden:10000000 / 010001

(+128 eigentlich nicht mehrdarstellbar)

Vorzeichen ungleich !Ergebnis: -(7+9/17)

10000000 * 10001 = 111 + 1001/10001– 10001

11110– 10001

011010– 10001

01001K2: Quotient: 11001 = -7

Rest : 10111 = -9

28

Digitaltechnik



Für Multiplikation und Division wurden hier nur die prinzipiellen Verfahren vorgestelltFür die konkrete Realisierung von Rechenwerken sind eine Reihe von Varianten verfügbar, z.B. zur Rechnung mit K2-Darstellung (Verfahren von Robertson, Algorithmus von Booth, Divisionsmethode mit/ohne Rückstellung des Rests)Behandlung ggf. in Verbindung mit speziellen RealisierungsformenGute Übersicht: [Hoffman 83], Kapitel 3

Digitaltechnik



Zusätzlich zu Grundrechenarten werden einige spezielle Operationen häufig benötigtSpezialfall der Multiplikation und Division für den Fall eines Multiplikators bzw. Divisors der eine Potenz der Basis 2 istVereinfachung zu Schiebe- oder Shift-Operation um n-Stellen für 2n

Multiplikation bedeutet Links-Shift und Division Rechts-Shift

Vergleichsoperation von Dualzahlen:Rückführung auf probeweise Subtraktion der Zahlen Auswertung der Differenz und ihres Vorzeichens:a = b für a-b = 0a = b für a-b = 0a < b für a-b < 0 (negatives Ergebnis)a <= b für a-b <= 0 (negativ oder Null)a > b für a-b > 0

29

Digitaltechnik



Addition und Subtraktion von BCD-ZahlenBeim Rechnen mit BCD-Zahlen ist die Einhaltung des erlaubten Wertebereichs zu beachten. Bei Überschreitung muss Korrektur erfolgenBeispiele:

Bei Subtraktion erfolgt KorrektursubtraktionDie Bildung eines Zehnerkomplements ist möglichBCD-Multiplikation(Division) auf BCD-Addition/Subtraktion rückführbar [Hoffmann 83]

+4 0100+5 0101+_________+9 1001

+5 0101+19 0001 1001+______________

0001 11101 0110

0010 0100+24 0010 0110

+14 0001 0100–9 0000 1001+______________

0000 10110000 01100000 0101

+5 0000 0101

Digitaltechnik



Weitere tetradische Kodes zur Verbesserung gegenüber BCDStibitz- oder Excess-3-Kode entsteht aus BCD-Kode durch Addition von 0011B zu jeder ZifferKodewörter 0...4 und 5...9 werden spiegelbildlich komplementärBeim Aiken oder 2-4-2-1-Kode erfolgt umkehrbar eindeutig die Zuordnung der Ziffern 0...9 zu 4-stelliger Dualzahl mit den Stellengewichten 2-4-2-1.Kodewörter 0...4 und 5...9 werden ebenfalls spiegelbildlich komplementärStibitz- und Aiken-Kodes erleichtern Subtraktion über KomplementAndere Kodierung, Excess-128-Kode, z.B. verwendet in folgendem GleitpunktformatGleichzeitige Änderung mehrerer Ziffern problematisch, z.B. mechanische Abtastung in Meß- und AutomatisierungstechnikKodierung durch Gray-Kode stellt Wechsel vongenau einer Ziffer beim Übergang sicher

0111;0101;0000;1000

30

Digitaltechnik



Darstellung der zusätzlichen tetradischen Kodes

(10) 1 1 1 1

(11) 1 1 1 0

(9) 1 1 0 1

(8) 1 1 0 0

(13) 1 0 1 1

(12) 1 0 1 0

(14) 1 0 0 1

(15) 1 0 0 0

(5) 0 1 1 1

(4) 0 1 1 0

(6) 0 1 0 1

(7) 0 1 0 0

(2) 0 0 1 1

(3) 0 0 1 0

(1) 0 0 0 1

(0) 0 0 0 0

Gray-Kode

1 1 1 1

1 1 1 0

1 1 0 1

(9) 1 1 0 0

(8) 1 0 1 1

(7) 1 0 1 0

(6) 1 0 0 1

(5) 1 0 0 0

(4) 0 1 1 1

(3) 0 1 1 0

(2) 0 1 0 1

(1) 0 1 0 0

(0) 0 0 1 1

0 0 1 0

0 0 0 1

0 0 0 0

Dreiexcess-Kode

(9) 1 1 1 1

(8) 1 1 1 0

(7) 1 1 0 1

(6) 1 1 0 0

(5) 1 0 1 1

1 0 1 0

1 0 0 1

1 0 0 0

0 1 1 1

0 1 1 0

0 1 0 1

(4) 0 1 0 0

(3) 0 0 1 1

(2) 0 0 1 0

(1) 0 0 0 1

(0) 0 0 0 0

Aiken-Kode2-4-2-1

1 1 1 01 1 1 0

1 0 1 01 0 1 0

1 0 1 11 0 1 1

1 1 0 01 1 0 0

1 1 0 11 1 0 1

(8) 1 0 0 01 0 0 0

(7) 0 1 1 10 1 1 1

(6) 0 1 1 00 1 1 0

1 1 1 11 1 1 1

(9) 1 0 0 11 0 0 1

(5) 0 1 0 10 1 0 1

(4) 0 1 0 00 1 0 0

(3) 0 0 1 10 0 1 1

(2) 0 0 1 00 0 1 0

(1) 0 0 0 10 0 0 1

(0) 0 0 0 00 0 0 0

BCD-Kode8-4-2-1

Dualzahlen8-4-2-1

Digitaltechnik



Bisherige Darstellung und Arithmetik für natürliche bzw. reellwertige FestpunktzahlenNachteil: Wertebereich fest, Zahlenbereich und Genauigkeit können nicht bedarfsweise gegeneinander eingetauscht werdenLösung: Darstellung durch eine Gleitpunktzahl mit dynamischem SkalierungsfaktorEine Gleitpunktzahl besteht aus Mantisse M und Exponent E bei gegebener Basis R:

Bei R=2 bedeutet ein Inkrement(Dekrement) des Exponenten ein Rechts(Links)verschieben der MantisseDie Mantisse bestimmt die Genauigkeit der dargestellten ZahlDer (+/-) Exponent skaliert Mantisse von betragsmäßig sehr kleinen bis zu sehr großen Zahlen

ERMD *=

31

Digitaltechnik



Darstellung einer Gleitpunktzahl am Beispiel des IEEE Floating-PointStandard (IEEE 754) in Single-Precision (32 Bit):

Mantisse (23 Bit) zwecks eindeutiger Darstellung normalisiert, VBZusätzliches Hidden Bit (HB) mit Komma rechts vom HBExponent: 8 Bit (Excess-127 kodiert), Werte 0016 und FF16 kodieren Spezialfälle wie Null oder Überlauf (HB ist dann nicht 1)Beispiele:

+3.000 = 0 10000000 1 10000000000000000000000+ +1 1.5

-17.375 = 1 10000011 1 00010110000000000000000- +4 1.0859375

+0.125 = 0 01111100 1 10000000000000000000000+ -3 1.5

0.000 = 0 00000000 0 00000000000000000000000+ -127 0.0

Weitere Standardformate: Double-Precision (64 Bit), Extended Prec.

31 30 23 22 0V Exponent (E) 23 HB Mantisse (M) 0

Digitaltechnik



Beliebte Prüfungsfrage: Für gegebenes Gleitkommaformat (M,E,R)• Kleinste positive darstellbare Zahl: Mmin*REmin

• Größte positive darstellbare Zahl : Mmax*REmax

• Kleinste negative darstellbare Zahl: -Mmax*REmax

• Größte negative darstellbare Zahl: -Mmin*REmin

Zahlendarstellung gemäß IEEE-Standard

-1V *Infty0255

-1V *000-1V * 2-126*(0,M)= 00-1V * 2E-127*(1,M)M0<E<255

Ungültig (NaN)= 0255WertMantisseExponent

32

Digitaltechnik



Wandlung von Festpunkt- in Gleitpunktzahlen:• Konvertieren der Zahl in die Zahlendarstellung der Mantisse (VB!)• Exponent entsprechend der Kommastelle setzen• Normalisieren der Mantisse im gegebenen Format mit Exponentenanpassung• Umwandlung des Exponenten in Zieldarstellung, z.B. Excess-127• Mantisse, Vorzeichen und Exponent ins Gleitpunktformat eintragen

Mögliche Genauigkeitprobleme: 32 Bit Integer nach 32 Bit FP !Rückwandlung von Gleitpunkt- in Festpunktzahlen:

• Exponent bei Verschiebung der Mantisse entsprechend der gewünschten Stellung des Punktes im Festpunktformat anpassen

• Wertebereichsüberschreitung ist hierbei möglich !• Typische Wandlung in Programmiersprache double nach int reduziert auf

Abschneiden des Nachkommaanteils (Vernachlässigung einerWertebereichsüberschreitung)

Digitaltechnik



Behandlung der Addition und Subtraktion für Gleitpunktzahlen:• Überprüfung, ob beide Operanden ungleich Null, sonst ist Ergebnis der Wert

des Operanden ungleich Null bzw. Null • Exponentenvergleich: Bei ungleichen Exponenten Anpassung erforderlich• Verschieben der Mantisse der Zahl mit kleinerem Exponenten nach rechts• Addition der Mantissen nach Exponentenanpassung• Bei Mantissenüberlauf nach Addition Rechtsverschiebung mit Exponenten-

anpassung• Falls Mantisse nicht normalisiert, Linksverschiebung mit Exponenten-

anpassung bis zur Normalisierung• Beispiel:

D = 60 + 0,0125 = 0,6*102 +0,125*10-1= 0,6*102 + 0,000125*102

= 0,600125*102

Eine Normalisierung ist hier nicht erforderlich

Es kann zu Exponentenunterlauf/überlauf und unechter Null kommen

33

Digitaltechnik



Behandlung der Multiplikation für Gleitpunktzahlen:• Überprüfung, ob einer der Operanden gleich Null ist, dann ist Ergebnis

gleich Null• Addition der Exponenten, Multiplikation der Mantissen• Mantisse nicht notwendigerweise normalisiert, Linksverschiebung mit

Exponentenanpassung um eine Stelle zur Normalisierung erforderlich• Ausführung der Multiplikation mit einer Stelle höherer Genauigkeit, um bei

Normalisierung gültige Ziffer nachzuziehen !• Beispiel:

D = 60 * 0,0125 = (0,6*102) * (0,125*10-1) = (0,6* 0,125)* 10(2-1)

= 0,075*101

= 0,75* 100

Eine Normalisierung war hier erforderlich

• Es kann zu Exponentenüberlauf/unterlauf kommen

Digitaltechnik



Behandlung der Division für Gleitpunktzahlen:• Überprüfung, ob Dividend gleich Null ist, dann ist Ergebnis gleich Null bzw.

bei Divisor auch gleich Null undefiniert• Bei Dividend ungleich Null und Divisor gleich Null resultiert unendlich• Falls Dividend und Divisor ungleich Null erfolgt Subtraktion der

Exponenten, und Division der Mantissen• Bei normalisierten Mantissen von Dividend und Divisor kann Mantisse des

Resultats größer Eins werden, Rechtsverschiebung mit Exponentenanpassung um eine Stelle zur Normalisierung erforderlich

• Alternativ: Rechtsverschiebung der Mantisse des Dividenden vor Division um eine Stelle, dann Normalisierung des Resultats durch Linksverschiebung

• Beispiel:

D = 60 / 0,0125 = 0,6*102 /0,125*10-1= 0,6/ 0,125 *(102 / 10-1)= 4,8 *10(2-(-1)) = 4,8*103 = 0,48*104

• Es kann Exponentenüberlauf/unterlauf, undefininiert (0/0) und unendlich (x/0) im Laufe der Division auftreten.

• Häufig Zusammenfassung (0/0) und (x/0) zu Division durch Null

Ein Beispiel:

34

Digitaltechnik


Kodierung und ArithmetikKodewandlung

Beim Austausch zwischen Teilsystemen, die unterschiedliche Kodierungen verwenden ist eine Kodewandlung oder UmkodierungerforderlichASCII-Kode nach BCD-Darstellung für die Zahlen 0 bis 9:

Gray-Kode nach Dualzahl:

01000011001000010000BCD

01101000110011011001001100010110000ASCII

43210Zeichen

10011000011101100101BCD

01110010111000011011101101100110101ASCII

98765Zeichen

111110101100011010001000Dualzahl

100101111110010011001000Gray-Kode

Digitaltechnik


Kodierung und ArithmetikKodewandlung

BCD nach 7-Segment:

111101110019

111111110008

111000001117

101111101106

101101101015

011001101004

111100100113

110110100102

011000000011

111111000000

7-Segment(abcdefg)

BCDZiffera

b

c

d

e

eg

Ein Beispiel:

A-F

35

Digitaltechnik


Kodierung und ArithmetikKodeumschaltung

Eine eineindeutige Kodierung verlangt die Einhaltung der Beziehung

In vielen Fällen kann das benötigte m aus technischen Gründen nicht verfügbar gemacht werden:• Tastaturen mit zu grossem Tastenvorrat geometrisch nicht sinnvoll• Tastaturen nicht beliebig miniaturisierbar (Uhren, Taschenrechner,

PDAs/Organizer)• Limitierungen der Übertragungswege

Ausweg: KodeumschaltungKodewörter werden mehrfach genutzt; Kodierung wird mehrdeutigEindeutigkeit wird durch Kontext von Steuer- oder Umschaltzeichen

mN 2≤

Digitaltechnik


Kodierung und ArithmetikKodeumschaltung

Zahl der je Gruppe darstellbaren Zeichenzahl

Zahl der mit Umschaltung darstellbaren Kodewörter (einschließlich der allen Gruppen gemeinsamen Zeichen)

Beispiele: ASCII: SO/SI, Shift-Taste, ESC+Zusatzzeichen (Escape-Sequenzen)

jiN m −−= 2´

iNjN +•= ´´´

Zahl der insgesamt darstellbaren KodewörterN´´

Zahl der nutzbaren Kodewörter je GruppeN´

Zahl der Gruppen und damit Umschaltzeichenj

Zahl der allen Gruppen gemeinsamen Zeicheni

Stellenzahl der Kodewörter (Binärdarstellung)m

Zahl der zu kodierenden ZeichenN

Ein Beispiel:

Documents

Digitaltechnik - 20K%94nig/Digtech2_2.pdf · ´0010´ ´1001 ´ Kodierung ... 101 100 011 010 001 000 ¾Stetige, physikalische Größen (Sensoren) ... 4 0100 0100 1 0100 0 3 0011