3. Codes - ostfalia.de€¦ · ASCII-Code. Prof. Dr.-Ing. Thorsten Uelzen Fakultät Elektrotechnik - Wolfenbüttel [email protected] Digitaltechnik Grundlagen Prof. Dr.-Ing. Thorsten

Version 1.0 von 02/2018

Prof. Dr.-Ing. Thorsten UelzenFakultät Elektrotechnik - Wolfenbüttel

[email protected]

Prof. Dr.-Ing. Thorsten Uelzen

Digitaltechnik Grundlagen3. Codes


[email protected]

Prof. Dr.-Ing. Thorsten Uelzen 2Digitaltechnik Grundlagen

Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Grundlagen von Codierungen

- Hat nicht unbedingt nur mit Spionage etc. zu tun - Allgemeine Definition [nach DIN 44300 Teil 2 von 1988]:

- Ein Code ist eine Abbildungsvorschrift, die jedem Zeichen eines Zeichenvorrats (Urbildmenge) eindeutig ein Zeichen oder eine Zeichenfolge aus einem möglicherweise anderen Zeichenvorrat (Bildmenge) zuordnet.

- Beispielsweise stellt der Morsecode eine Beziehung zwischen Buchstaben und einer Abfolge kurzer und langer Tonsignale (und umgekehrt) her.

[Quelle: Wikipedia]


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h


- Ein Code gibt also an wie Informationen dargestellt werden.- Warum? Weil unterschiedliche Systeme unterschiedliche Codes effizienter

verarbeiten und fehlerfreier „verstehen“ können.- Mensch = Sprache - Musikinstrumente = Noten- Biologie = DNA - Computer = binäre Codes

- Wollen diese unterschiedlichen Systeme kommunizieren, wird ein Code benötigt = Übersetzer

[Que

lle:

gesi

nn.it

Gm

bH &

Co.

KG

]


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Grundlagen von Codierungen- Ein Codewort ist eine Folge von Zeichen, die in einem bestimmten

Zusammenhang als Einheit betrachtet wird. Ein Codewort kann auch aus nur einem Zeichen bestehen.

- Existiert eine Anordnung der Codeworte und somit eine Größer-Kleiner-Beziehung zwischen zwei beliebigen verschiedenen Codeworten, so nennt man den Codewortvorrat Codealphabet.

- Bei Binärcodes besteht jedes Codewort der Bildmenge aus einer Folge von Binärzeichen.

- Bei der technischen Verarbeitung von Informationen spielen Binärcodes eine überragende Rolle.

- Ein Gerät, das eine Codierung durchführt, nennt man Codierer, Coder oder Encoder.

- Ein Gerät, das eine Codierung rückgängig macht, nennt man Decodiereroder Decoder.

- Kann ein Gerät sowohl codieren als auch decodieren, so nennt man es Codec (Coder/Decoder).

[Quelle: Harriehausen, T: Arbeitsblätter zu Digitaltechnik Grundlagen]


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h


Zweck einer Codierung ist die Umformung der Darstellung von Informationen, um deren

- Übertragbarkeit (hohe Sicherheit gegen Verfälschung, optimale Nutzung der physikalischen Eigenschaften des Übertragungskanals)

- Speicherbarkeit (kompakte Darstellung zur Minimierung des Speicherplatzes, optimale Nutzung der physikalischen Eigenschaften des Speichermediums)

- Verarbeitbarkeit (einfache und schnelle Durchführung von Operationen)- Lesbarkeit (für Menschen oder Maschinen)

zu verbessern. Um diese verschiedenen Zwecke zu erreichen, wurde eine unübersehbare Zahl von Codes entwickelt, insbesondere zur Darstellung von

- Zahlen (numerische Codes)- beliebigen Schriftzeichen: Buchstaben, Sonderzeichen, Ziffern

(alphanumerische Codes).

[Quelle: Fricke, K.: Digitaltechnik, Springer Vieweg und Harriehausen, T: Arbeitsblätter zu Digitaltechnik Grundlagen]


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Binärcodes

- Informationen werden mit „0“ und „1“ codiert- z.B. Dualcode für Zahlen- Beliebige andere Codes bzw. Code-Tabellen sind denkbar

[Quelle: Wikipedia]

ASCII-Code


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Binärcodes - Ausdrücke

- Ein binärer Code ist einschrittig, wenn sein Zeichenvorrat ein Codealphabet bildet und zwei benachbarte Codeworte sich nur in genau einem Bit unterscheiden. vgl. Hamming-Distanz

- Bei einem stetigen Code ist die Zahl der Bits, in denen sich benachbarte Codeworte unterscheiden, konstant.

- Das Gewicht eines binären Codewortes ist die Anzahl der Einsen in dem Codewort.- Bei gleichgewichteten binären Codes ist die Anzahl der Einsen in allen

Codeworten identisch. - Bei einem balancierten binären Code ist in allen Codeworten die Anzahlen

der Einsen gleich der Anzahl der Nullen. Wird bei einem solchen Code z. B. zur Darstellung einer Eins ein Impuls mit x Volt und zur Darstellung einer Null ein Impuls mit –x Volt verwendet, so enthält das Signal, das die Abfolge der Codeworte darstellt, keinen Gleichanteil.



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Binärcodes - Ausdrücke

- Ein binärer numerischer Code ist bewertbar, wenn jeder Stelle eine (positive) Stellenwertigkeit zugeordnet ist. Diese Stellenwertigkeit gilt üblicherweise für den Fall, dass an der Stelle eine 1 steht (vgl. Dualcode). Bei der verallgemeinerten Definition kann die Wertigkeit auch negativ sein und – ggf. von bit zu bit unterschiedlich – auch für den Fall gelten, dass an einer Stelle eine 0 steht.

- Ein binärer numerischer Code ist selbst-komplementierend(negationssymmetrisch), wenn das Codewort für die Dezimalziffer X bitweisekomplementär zum Codewort für die Ziffer 910-X ist.



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Binärcodes - Hammingdistanz

- Die Hamming-Distanz (HD) zweier binärer Codeworte gleicher Länge gibt an, in wie vielen Stellen (Bits) sich diese beiden Worte unterscheiden.

- Beispiel:- Codewort 1: 110111101000001100

- Codewort 2: 101011000111000110

- Unterschiede: XXX X XXXX X X

- Die beiden Codeworte bestehen jeweils aus 18 bit. Sie unterscheiden sich in 10 Stellen. Also ist ihre Hamming-Distanz HD =10.

- Die minimale Hamming-Distanz HDmin eines Zeichenvorrates (d. h. einer Menge von Codeworten) ist das Minimum der Hamming-Distanzen aller Paare unterschiedlicher Codeworte des Zeichenvorrates.

- Die minimale Hamming-Distanz bezieht sich also auf einen ganzen Zeichenvorrat.

- Der Wert von HDmin kann nur zwischen 1 und der Anzahl der Stellen der Codeworte liegen.



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Binärcodes - Hammingdistanz

- Bei der Ermittlung von HDmin für einen Zeichenvorrat kann man also stets mit dem Vergleich von Codeworten aufhören, sofern man zwei Codeworte findet, die sich nur in einem Bit unterscheiden.

- Bei einem Zeichenvorrat mit HDmin = 2 unterscheiden sich alle Codeworte in mindestens zwei Stellen voneinander.

- Tritt ein Fehler auf, der nur genau ein beliebiges Bit verfälscht, so entsteht eine Bitkombination, die kein gültiges Codewort ist und die somit als fehlerhaft erkannt werden kann.

- Höhere Werte von HDmin ermöglichen die Erkennung von bestimmten Mehrfachfehlern und sogar die Korrektur von bestimmten Fehlern.

Beispiele:00110 und 00100 → Hamming-Abstand=112345 und 13344 → Hamming-Abstand=2Haus und Baum → Hamming-Abstand=2



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Numerische Codes

- Werden ausschließlich zur Darstellung von Zahlenwerten verwendet.- Bilden daher immer ein Codealphabet.- Bereits behandelt: Dual-/Oktal-/Dezimal-/Hexadezimal-Code,

Einerkomplement-/Zweierkomplement-/Vorzeichen-Betrags-Darstellung.- Bei den oben genannten Codes wird der darzustellende Zahlenwert

insgesamt codiert (Wortcodes).

Oft in der Anwendung: BCD-Code und Gray-Code



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Numerische Codes – BCD-Codes

- BCD-Codes (BCD = binary coded decimal) stellen genau eine dezimale Ziffer (0 ... 9) pro Codewort dar.

- 10 dezimale Ziffern min. 4 bit notwendig Sechs 4 bit lange Codeworte (Tetraden) „über“ = Pseudotetraden

- 1010 = 10.000.000.000 verschiedene Möglichkeiten – aber nur sehr wenige spielen eine Rolle:- 8-4-2-1-Code (identisch mit dem Dualcode für die Zahlen 0 bis 9)- Aiken-Code (Stellenwertigkeit 2-4-2-1)- Stibitz-Code, auch Exzess-3-Code genannt

(im Mittel zwei Einsen pro Codewort)- Glixon-Code (einschrittig)

- Ersten drei Codes sind bewertbar- Minimale Hamming-Distanz aller vier Codes ist HDmin = 1- Aiken- und der Stibitz-Code sind negationssymmetrisch, was vorteilhaft bei

der Realisierung von Schaltungen zur Subtraktion ist.


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h


- Sollen Dezimalzahlen mit mehreren Ziffern mittels eines BCD-Code dargestellt werden, so wird jede Ziffer einzeln codiert:- 12310 = 0001 0010 0011BCD-8-4-2-1

- n-stellige Dezimalzahl = 4n bit.- Folge: Multiplikative Vermehrung der Pseudotetraden Codierung ist weitschweifig oder redundant

- Vorteil dieser Redundanz ist die Tatsache, dass ein Fehler, der ein zulässiges Codewort in eine Pseudotetrade umwandelt, erkannt werden kann - Fehlererkennung.


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h




[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h


- BCD-8-4-2-1-Addition:1. binäre Addition2. Korrekturen:

a) Tritt Übertrag in nächste Tetrade durch 1. auf: Addition von 6D = 0110 bei der Tetrade, die den Übertrag erzeugt hat.

b) Tritt Pseudotetrade auf: Addition von 6D = 0110c) Es wird immer nur jede Tetrade einmal korrigiert.

- BCD-8-4-2-1-Subtraktion: (lassen wir weg, da keine neg. BCD-Definition)

- Beispiele: 339D + 662D = 1001D19D + 89D = 108D248D + 515D + 139D = 902D


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h


- Stibitz-Addition:1. binäre Addition2. Korrekturen:

a) Tritt Übertrag in die nächste Tetrade bei 1. auf: Addition von 3D = 0011 bei der Tetrade, die den Übertrag erzeugt hat.

b) sonst immer: Addition von 13D = 1101 c) Übertrag durch Korrekturen streichen.d) bei Übertrag im MSB: alles nochmal mit 0011 (=0D) im MSBs (6D+9D)

- Stibitz-Subtraktion: siehe Beispiele

- Beispiele: 13D + 55D = 68D12D + 27D = 39D6D + 9D = 15D53D - 16D = 37D25D - 12D = 13D9D - 17D = -8D


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Binärcodes – einschrittige Codes

- In der Messtechnik besonders wichtige Codes für zuverlässige Messungen von z.B. Längen oder Winkeln (Absolutlängen und Absolutwinkel)

- Problem: Beim Dualcode ändern sich z.T. drei Bit gleichzeitig = fehleranfällig

- Lösung: Einschrittige Codes:- hier ändert sich immer nur ein Bit- maximale Abtastsicherheit

[Quelle: Fricke, K.: Digitaltechnik, Springer Vieweg und Harriehausen, T: Arbeitsblätter zu Digitaltechnik Grundlagen]


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Binärcodes – einschrittige Codes

- Beispiele:

- Technisch besonders wichtig: GRAY-CODE (beliebig viele Bits möglich)

[Quelle: it-wissen.info]


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Binärcodes – Gray-Code

Problem beim Dualcode:

Theoretische Zahlen (Bit-) Folge:{0000}, {0001}, {0010}, {0011}, {0100}, {0101}, {0110}, {0111} usw.

Tatsächliche Folge:{0000}, {0001}, {0000}, {0010}, {0011}, {0100}, {0101}, {0111}, {0110}, {0111} usw.

[Quelle: Wikipedia]


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Binärcodes – Gray-Code

Problemlösung durch Gray-Code:

Abgesendete Sequenz: {0000}, {0001}, {0011}, {0010}, {0110}, {0111}, {0101}, {0100} usw.

Ankommende Sequenz: {0000}, {0001}, {0011}, {0010}, {0110}, {0111}, {0101}, {0100} usw.

[Quelle: Wikipedia]


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Binärcodes – Gray-Code - Anwendung

Absolutwertgeber:

[Quelle: Wikipedia]

Lichtsensoren


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Binärcodes – Gray-Code - Anwendung

Absolutwertgeber:



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Alphanumerische Codes

- Können meistens darstellen:

– numerische Ziffern („0“ ... „9“)– Schriftzeichen (Alphazeichen) (z. B. „a“ .. „z“, „A“ .. „Z“, „Ä“, „ß“, ...)– meist auch Sonderzeichen („$“, „§“, „&“, „@“, ...)– eventuell kleine Grafiken (z. B. „☺“, „“, „╧“, ...)– und in der Regel auch Steuerzeichen zur Steuerung der

Datenübertragung (CR, LF, BEL, ...)

- Oft in der Anwendung zu finden:- ASCII [gespr. „Aski]- EBCDIC [gespr. „Äbsdick“]- Unicode [gespr. …]



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Alphanumerische Codes - ASCII

- Jedem Zeichen wird ein Bitmuster aus 7 Bit zugeordnet; dies ergibt 27 = 128 verschiedene Bitmuster, die auch als die ganzen Zahlen 0–127 (hexadezimal 00h–7Fh) interpretiert werden können.

- Das ggf. nicht benutzte achte Bit (bei 8 Bit-Codierung) kann für Fehlerkorrekturzwecke (Paritätsbit) auf den Kommunikationsleitungen oder für andere Steuerungsaufgaben verwendet werden. Heute wird es aber fast immer zur Erweiterung von ASCII auf einen 8-Bit-Code verwendet.

- 7-bit-Code = 95 druckbare und 33 Steuerzeichen- 1963 standardisiert, aktuell als ANSI X3.4-1968. - Programme und Daten wurden damals in Lochstreifen oder Lochkarten

gestanzt. Bitmuster 1111111 = DEL, da alle nicht gestanzten Löcher gestanzt wurden

[Quelle: Wikipedia und Harriehausen, T: Arbeitsblätter zu Digitaltechnik Grundlagen]


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h


- ASCII kann alle im US-amerikanischen Schriftverkehr üblichen Zeichen darstellen (aber z.B. keine Ä, Ö, Ü, ß). 8-bit-Varianten des ASCII für verschiedene Sprachen (Codepages). Die IBM-PCs und MS-DOS verwendeten die Codepage 437.

- In der ISO-Norm 8859 sind 15 verschiedene 8-bit-Zeichensätze definiert, die auf dem ASCII aufbauen, z. B. - „Latin-1, Westeuropäisch“ - „Latin-9, Westeuropäisch“.

Letzterer Zeichensatz enthält auch das Euro-Zeichen „€“. Der Zeichensatz Windows-1252 ähnelt ISO 8859-1.



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h


[Quelle: Wikipedia]


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Alphanumerische Codes – ASCII - Steuerzeichen

[Quelle: Wikipedia]


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Alphanumerische Codes – EBCDI und UnicodeEBCDIC (Extended BCD Interchange Code)- IBM-spezifischer 8-bit-Code (IBM Großrechner-Systemen); inkompatibel zu

ASCII; auch verschiedene Codepages mit nationalen Sonderzeichen

Unicode- Unicode-Konsortium (www.unicode.org)

Ziel: Alle Zeichen aller lebenden und toten Sprachen sollen vollständig erfasst werden.

- 32 bit zur Zeichencodierung von 1.114.112 Schriftzeichen (eigentlich 21 bitausreichend)

- Für die Codierung der wichtigsten Zeichen aller lebenden Sprachen (außer Chinesisch) sind 16 bit ausreichend.

- Unicode-Zeichen können durch ein bis vier 8-bit-Zeichen (Oktetts) dargestellt werden Nutzung z. B. in Java und Linux = UTF-8 Codierung (UTF = Unicode Transformation Format)

- ISO Normung des Unicodes als „Universal Character Set“ (UCS) in ISO-Norm-10646


http://www.unicode.org/


[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Binärcode - m-aus-n Codes

- Ein konkreter Code aus dieser Klasse hat - eine definierte Länge = n Stellen- m Stellen sind gleich „1“ (gleichgewichtiger Code) und - die restlichen n-m Stellen sind gleich „0“. - Alle anderen Kombinationen der beiden Symbole sind keine gültigen

Codeworte – hohe Redundanz- Diese Klasse von Codes kann prinzipiell zur Darstellung beliebiger

Informationen verwendet werden.



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Binärcode - 1-aus-10 Codes

- Für die technisch einfache Erfassung der auf einer Zehnertastatur gedrückten Taste.

- Wird eine Taste gedrückt, so wird die dieser Taste zugeordnete Stelle „1“.



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Binärcode - 2-aus-5 Codes

- Verwendung z. B. in verschiedenen Varianten des Strichcodes (engl. barcodes) zur kompakten Darstellung von Dezimalzahlen beliebiger Stellenzahl verwendet.

- Jedes Codewort besteht aus 2 breiten und 3 schmalen Strichen, die durch Lücken fester Breite getrennt werden.

- Neben den Codeworten für die Ziffern 0 bis 9 gibt es spezielle Codeworte, die den Anfang (Start) bzw. das Ende (Stopp) einer Zahl darstellen.

- Komplizierter aufgebaut ist der nach ISO/IEC 16390 (ehemals DIN EN 801) genormte „Interleaved 2 of 5“ Code. Bei ihm werden sowohl breite und schmale Striche als auch breite und schmale Lücken verwendet. Zwei benachbarte Dezimalziffern werden gemeinsam codiert: die eine durch die Striche, die andere durch die Lücken. Dadurch ist der Code nur für Zahlen mit einer geraden Zahl von Ziffern geeignet.



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Gesicherte Codes

- Häufiges Problem: Fehlerhafte Signalübertragung- Speichern von Daten- Mobilfunk- CDs etc.

- Herausforderung: Fehlererkennung- Auf den folgenden Folien Beschränkung auf Codewörter gleicher

definierter Länge.

Lösung: Einführung bzw. Erweiterung von Paritätsbits.



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Gesicherte Codes - Parität

- Parität ist die Eigenschaft der Geradzahligkeit der „1“en in einem Codewort.- Es gibt gerade Parität (even parity) und ungerade Parität (odd parity).- Ein Paritätsbit ergänzt eine Gruppe von Bits auf insgesamt gerade oder

ungerade Parität.

- Beispiel:- Nutz-Codeworte haben 2 bit: 00, 01, 10, 11 (HDmin = 1).- Es wird links ein Paritätsbit angefügt, das zu insgesamt

gerader Parität führt: 000, 101, 110, 011 (HDmin = 2). - Damit ist ein neuer Code mit 3 bit-Codeworten entstanden.- Von den 23 = 8 möglichen Bitkombinationen sind aber nur 50% gültige

Codeworte des neuen Code. Tritt eine der anderen Bitkombinationen auf, muss ein Fehler aufgetreten sein!

- Möglich sind hier 1-bit-, 2-bit- und 3-bit-Fehler.



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Gesicherte Codes – Parität – Beispiel (Fortsetzung)

Darstellung der 8 möglichen Bitkombinationen als Eckpunkte eines Würfels im 3-dimensionalen Codewort-Raum (grün/schwarz = gültig, rot/ = ungültig).

Von einem gültigen Codewort gelangt man über eine beliebige der 3 zugehörigen Kanten immer zu einer ungültigen Bitkombination. Das entspricht dem Auftreten eines 1-bit-Fehlers: erkennbar!



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h


Von einem gültigen Codewort gelangt man über zwei beliebige, verschiedene, aneinander grenzende Kanten immer zu einer gültigen Bitkombination. Das entspricht dem Auftreten eines 2-bit-Fehlers: nicht erkennbar!



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h


Ein beliebiger Weg entlang der Kanten des Würfels führt immerabwechselnd über gültige Codeworte (schwarze Kreise) und ungültige Bitkombinationen ( Kreise). Ein solcher Weg lässt sich auch eindimensional („gerade gezogen“) darstellen:

Die Darstellung in Bild 1 gilt nur für den Fall von 2 Nutzbitsund einem Paritätsbit.

Die Darstellung in Bild 2 gilt für beliebig viele Nutzbitsund ein Paritätsbit.



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h


Ergänzt man einen redundanzfreien Code um 2 sinnvoll gewählte Paritätsbits, ergibt sich ein neuer Code mit HDmin = 3.

Ein beliebiger Weg entlang der Kanten des Hyperwürfels führt immer von einem gültigen Codewort (schwarzer Kreis) über zwei ungültige Bitkombinationen ( Kreise) zu einem anderen gültigen Codewort.

Ein solcher Weg lässt sich auch eindimensional darstellen:

Diese Darstellung lässt sich einfach auf den Fall von beliebig vielen Paritätsbits erweitern.

Ergänzt man einen redundanzfreien Code um n sinnvoll gewählte Paritätsbits, ergibt sich ein neuer Code mit HDmin = n+1.



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Gesicherte Codes - Fehlerkorrektur

- Bei einem Code nach Bild 3 führt eine Verfälschung von 1, 2, 4, 5, 7, 8, ... beliebigen Bits zu ungültigen Codeworten.

- Korrektur möglich bei 1-Bit-Fehler: nächst gelegenes gültige Codewort mit minimalstem Hamming-Abstand (maximum likelihood decoder).

- Treten jedoch Fehler auf, die 2, 4, 5, 7, 8, ... Bits verfälschen, werden die verfälschten Codeworte zwar erkannt, jedoch „falsch korrigiert“.

- Fehler, die 3, 6, 9, ... Bits verfälschen, sind nicht erkennbar und damit auch nicht korrigierbar.



[email protected]


Folie

n si

nd n

ur fü

r den

inte

rnen

Geb

rauc

h

Gesicherte Codes - Fehlerkorrektur

- Bei Analyse oder Synthese eines Codes ist ein Fehlermodell notwendig.- Wichtige Informationen sind z. B.:

- Welche Bit-Kombination entsteht beim Totalausfall?(oft 000 ... 0 oder 111 ... 1)

- Wie groß ist die Wahrscheinlichkeit für m Fehler in n Bit-Folgen( normalerweise : (m-1)-Bit-Fehler häufiger als m-Bit-Fehler)

- Gibt es bestimmte Fehlermuster?(„Bursts“ = fehlerhafte Bits in Folge)

- Es ist absolut unmöglich, einen Code zu konstruieren, der gegen Fehlereinflüsse völlig unempfindlich ist.

- Je höher die Hamming-Distanz zwischen benachbarten Codewarten durch Paritätsbits ist, desto besser lassen sich Fehler bestimmen und korrigieren.

- Es gibt viele Strategien in der Literatur und Anwendung (z.B. wo die Paritätsbits platziert werden …)


Documents

3. Codes - ostfalia.de€¦ · ASCII-Code. Prof. Dr.-Ing. Thorsten Uelzen Fakultät Elektrotechnik - Wolfenbüttel [email protected] Digitaltechnik Grundlagen Prof. Dr.-Ing. Thorsten