I

Seminar zur Quantenmechanik II Elemente der klassischen Informationstheorie

1. EINLEITUNG 1

2. QUELLEN 1

2.1 DISKRETE QUELLEN MIT UNABHÄNGIGEN EREIGNISSEN (QUELLE OHNE GEDÄCHTNIS) 2 2.2 VERBUNDQUELLE 3 2.3 KONTINUIERLICHE QUELLEN 4

3. KODIERUNG DISKRETER QUELLEN 5

3.1 QUELLEN-, KANALKODIERUNG UND REDUNDANZ 5 3.2 DEKODIERUNG 6 3.3 HUFFMAN-VERFAHREN (OPTIMALKODIERUNG) 7 3.4 FEHLERKORRIGIERENDER HAMMING-KODE 8

4. KANALKAPAZITÄT UND ÜBERTRAGUNGSGESCHWINDIGKEIT 10

5. KRYPTOGRAPHIE 11

5.1 ALLGEMEINES SCHEMA EINES VERSCHLÜSSELUNGSSYSTEMS 11 5.2 INFORMATIONSGEHALT UND SICHERHEIT 12 5.3 ONE-TIME-PAD KRYPTOGRAPHIE 13 5.4 PUBLIC-KEY VERSCHLÜSSELUNGSSYSTEM 13 5.4.1 ALLGEMEINES PRINZIP 13 5.4.2 RIVEST-SHAMIR-ADLEMAN SYSTEM 14 5.5 NP-STRENGES PROBLEM ALS KRYPTOSYSTEM 15

1

1. Einleitung Die Informationstheorie gehört zum theoretischen Fundament der Informatik und steht in engen Zu-

sammenhang mit der Kodierungstheorie. Begründet wurde sie 1948 von C.E. Shannon. Die mathema-

tischen Grundlagen für diese Theorie entstammen der Wahrscheinlichkeitstheorie.

Beispiele für Informationstragende Systeme sind Radio- und Fernsehübertragungen, Telefonverbin-

dung oder Bildübertragung von Satelliten. Diese Systeme bestehen alle im Allgemeinen aus einer

Quelle, dem Kodierer und Dekodierer, dem Kanal und der Senke (Abbildung 1). Nachrichten oder eine

Folge von Nachrichten werden von der Quelle produziert. Der Kodierer macht aus der Nachricht ein

übertragbares Signal, welches über den Übertragungskanal übermittelt wird. Der Kanal ist das vermit-

telnde Medium zwischen Sender und Empfänger. Alle Störungen die auf das Signal wirken, passieren

im Kanal. Der Dekodierer kehrt den Prozess des Kodierers um, wonach die Nachricht zum Empfänger

(Senke) gelangt.

Abbildung 1: Allgemeines Modell der Nachrichtenübertragung mit einem gestörten Kanal

In der Informationstheorie werden mathematische Modelle zur Beschreibung der einzelnen Kompo-

nenten eines solchen Nachrichtenübertragenden Systems und das Zusammenwirken dieser Kompo-

nenten entwickelt.

Dabei werden etwa die Quelleninformation und die vom Kanal unter dem Einfluss von Störungen über-

tragene Information berechnet. Die Effektivität der Informationsübertragung ist dabei wesentlich von

der Kodierung der Information abhängig.

Die Kodierungstheorie bietet eine Vielzahl von Methoden einerseits die Quelleninformation in übertra-

gungsfähige Form eindeutig und rationell darzustellen und andererseits gegen Störungen auf dem

Übertragungskanal zu schützen. Die Informationstheorie bestimmt dagegen die Möglichkeiten und

Grenzen der Informationsübertragung bei geeigneter Kodierung

2. Quellen Der Begriff Information wird mit der Gewinnung neuer Erkenntnis aus einer Quelle verbunden. Das

bedeutet es muss eine gewisse Unbestimmtheit über die Quelle vorliegen, sonst kann nichts neues

aus ihr erfahren werden.

Betrachten wir zum Beispiel einen idealen und einen gezinkten Würfel mit jeweils sechs Seiten. Beim

idealen Würfel haben alle sechs Ereignisse die gleiche Wahrscheinlichkeit. Bei einem gezinkten Wür-

fel sollen die hohen Augenzahlen eine größere Wahrscheinlichkeit als die niedrigeren haben. Beim

idealen Würfel haben wir grundsätzlich keine Ahnung, welche Augenzahlen sich ergeben. Beim ge-

zinkten Würfel können wir ehr mit großen Augenzahlen rechnen. Somit besitzt der der ideale Würfel

eine größere Unbestimmtheit.

Nun wollen wir etwas finden, wodurch wir die Unbestimmtheit ausdrücken können. In einer Menge

X={x1,...,xN} soll das Ereignis xi mit der Wahrscheinlichkeit p(xi) für i =1,...,N auftreten. Der reziproke

Wert von p(xi) stellt dann ein Maß der Unbestimmtheit H(xi) über das Ereignis xi dar: Je größer p(xi)

2

desto kleiner wird H(xi) und umgekehrt. Damit auch die Bedingung erfüllt wird, dass ein sicheres Er-

eignis, also p(xi)=1, keine Unbestimmtheit enthält, bildet man den Logarithmus und erhält:

)x(plog)x(p

1log)x(H i

ii −=

=

Weiterhin ist wichtig, je größer die Unbestimmtheit einer Nachricht ist desto größer ist ihr Informati-

onsgehalt.

2.1 Diskrete Quellen mit unabhängigen Ereignissen (Quelle ohne Gedächtnis)

Ein Alphabet ist eine endliche geordnete Menge von Zeichen die für die Darstellung einer Nachricht

verwendet werden.

Beispiele: {A,B,C,…X,Y,Z} gewöhnliches Alphabet

{1,0} binäres Alphabet

Eine Quelle mit dem Alphabet X={x1,...,xN} und der Verteilung der zugehörigen Auftrittswahrschein-

lichkeiten p(xi) mit i=1,...N, wobei

∑=

=N

1i

i 1)x(p

wird als diskrete Quelle X mit unabhängigen Ereignissen bezeichnet. Die Quelle wählt also ein Symbol

xi aus dem Alphabet X mit der Wahrscheinlichkeit p(xi) aus.

Jedes Ereignis liefert einen unterschiedlichen Beitrag zur Unbestimmtheit bzw. zum Informationsge-

halt der Quelle. Selten auftretende Ereignisse besitzen einen großen Informationsgehalt und weniger

selten auftretende einen niedrigen. Da die Ereignisse zufälligen Charakter haben ist auch Hi eine Zu-

fallsgröße, für die folgender Mittelwert berechnet werden kann.

∑−∑ ====

N

1i

ii

N

1i

ii )x(plog)x(p)x(p)x(HH [bit]

H wird auch als Quellenentropie oder mittlere Unbestimmtheit bezeichnet. Sie stellt auch den mittleren

Informationsgehalt dar.

Zur Verdeutlichung betrachten wir zwei Ereignisse mit der Wahrscheinlichkeit p und 1-p, wofür die

Entropie zu H = -(p)log(p) - (1-p)log(1-p) wird. Für diesen Fall ist die Entropie über die Ereigniswahr-

scheinlichkeit in Abbildung 2 aufgetragen.

Abbildung 2: Entropie für zwei Ereignisse mit den Wahrscheinlichkeiten p und 1-p (Binärquelle).

3

Aus der Graphik gehen wichtige Eigenschaften der Entropie hervor. Wie z.B. ist ein Ereignis sicher ist

der Informationsgehalt Null. Das gleiche gilt für p = 0, weil in diesem Fall das andere Ereignis die

Wahrscheinlichkeit 1 hat (es wird definiert 0log0=0). Ein Maximum ist bei p = 0.5 zu sehen. Daraus geht

hervor, sind alle Ereignisse Gleichwahrscheinlich wird die Entropie maximal. Die wichtigsten Eigen-

schaften der Entropie sind nun noch mal aufgelistet.

Eigenschaften der Entropie:

- Die Quellenentropie wird maximal, wenn alle Ereignisse der Quelle gleichwahrscheinlich sind.

- Eine Quelle, deren Alphabet ein sicheres Ereignis enthält, hat keine Unbestimmtheit.

- Die Hinzufügung von unmöglichen Ereignissen zum Alphabet einer Quelle ändert die Entropie nicht.

- Die Auflösung eines Ereignisses in Teilereignisse, für die pi=q1+q2 gilt, führt zur Zunahme der Entro-

pie. H1(p1,...,pi,…pN) < H2(p1,…,q1,q2,...pN)

Aus der letzten Aussage folgt, je größer die Auflösung eines diskreten Systems ist, d.h. je feiner es

strukturiert ist, desto größer ist seine Entropie bzw. sein mittlerer Informationsgehalt.

Hinweis: Diskrete Quelle mit abhängigen Ereignissen heißen MARKOV-Quellen

2.2 Verbundquelle Hier betrachten wir zwei diskrete Quellen X und Y mit den dazugehörigen Verteilungen der Auftritts-

wahrscheinlichkeiten p(xi) der Zeichen xi∈ X und p(yj) der Zeichen yj∈ Y. Dabei sollen die Ereignisse

innerhalb jeder Einzelquelle voneinander unabhängig sein. Allerdings sind die Ereignisse beider Quel-

len voneinander abhängig, d.h., dass ein Ereignis der einen Quelle von einem vorausgegangenen

Ereignis der anderen Quelle bestimmt wird. Wir legen fest, dass immer zuerst in der Quelle X ein Er-

eignis stattfindet, das unmittelbar danach ein bedingtes Ereignis in der Quelle Y mit der bedingten

Wahrscheinlichkeit p(yj|xi) auslöst. Dieses bedingte auftreten von zwei Ereignissen bezeichnet man als

Verbundereignis (xi,yj) mit der Verbundwahrscheinlichkeit p(xi,yj). Für die Verbundwahrscheinlichkeit

ergibt sich folgendes:

p(xi,yj) = p(xi)p(yj|xi)

Für die Entropieberechnung kann hier prinzipiell der gleiche Ansatz gemacht werden wie für die dis-

krete Einzelquelle, da die Verbundquelle allein durch eine Menge diskreter Wahrscheinlichkeiten ein-

deutig beschrieben wird. Damit erhalten wir die Verbundentropie (joint entropy).

)y,x(plog)y,x(p)Y,X(H jiji

N

1i

M

1j∑ ∑−== =

Mit i=1,…,N; j=1,…,M und N≥M. Um weitere Aussagen zur Verbundentropie zu gewinnen, setzten wir

für p(xi,yj), p(xi)p(yjxi) ein. Damit folgt

4

)x|y(p)x(plog)x|y(p)x(p)Y,X(H ijiiji

N

1i

M

1j∑ ∑−== =

Nach einigen Umformungen erhalten wir

∑ ∑∑−−=i i j

ijijiii )x|y(plog)x|y(p)x(p)x(plog)x(p)Y,X(H

Im ersten Term erkennen wir die Quellenentropie H(X), der zweite Term stellt die bedingte Entropie

(conditional entropy) H(Y|X). Für die Verbundentropie erhalten wir schließlich folgende Formel

)X|Y(H)X(H)Y,X(H −=

Für den Fall, dass zuerst in der Quelle Y in Ereignis auftritt, erhält man im Ergebnis

H(X,Y) = H(Y) - H(X|Y) 2.3 Kontinuierliche Quellen Das von einer kontinuierlichen Quelle ausgehende Signal kann in einem vorgegebenen Bereich jeden

beliebigen Wert annehmen, d.h. die Menge der Möglichen Ereignisse dieser Quelle ist unbegrenzt. In

Analogie zu Auftrittswahrscheinlichkeit bei diskreten Ereignissen kann die Wahrscheinlichkeitsdichte

interpretiert werden als die Wahrscheinlichkeit, mit der ein zu einem bestimmten Zeitpunkt auftreten-

der Funktionswert des zufälligen Signals x(t) in ein bestimmtes Intervall ∆x fällt.

Abbildung 3: Wahrscheinlichkeitsdichtefunktion

Zur Berechung der Entropie einer kontinuierlichen Quelle bzw. eines kontinuierlichen Signals wollen

wir von einer diskreten Betrachtung der stetigen Dichtefunktion ausgehen, damit bereits bekannte

Beziehungen von en diskreten Quellen übernommen werden können. Dazu denkt man sich die Fläche

unter der Dichtefunktion (Abbildung 3) in Teile gleicher Breite ∆x zerlegt. Das Integral einer Teilfläche

der Breite ∆x gibt die Wahrscheinlichkeit p(xi) dafür an, dass die zufällige Größe xi im Bereich ∆x liegt.

p(xi)= ∫∆x

dx)x(f ≈ f(xi)∆x

Setzt man dies in die Beziehung für die Entropie diskreter Ereignisse ein erhält man

H(X) = -∑ ∆∆i

ii )x)x(flog(x)x(f

= - ∑ ∆i

ii )x(flogx)x(f - ∑ ∆∆i

i xlogx)x(f

5

Um nun zu Entropie einer kontinuierlichen Quelle zu gelangen, muss der Grenzübergang ∆x�0 durch-

geführt werden. Das gelingt nicht vollständig denn log ∆x würde mit ∆x�0 eine unendlich große Entro-

pie H(X) ergeben, was offensichtlich der Realität widerspricht. Betrachtet man die Stufenbreite ∆x als

Maß für die Auflösung der stetigen Funktion in praktisch unterscheidbare Amplitudenwerte (was der

praktisch möglichen Genauigkeit bei der Informationserfassung entspricht), dann hat ∆x immer einen

Wert, der größer als Null ist und im Gegensatz zur Funktion x(t), nicht zufällig ist.

Nach dem Grenzübergang für die übrigen Ausdrücke in der obigen Gleichung erhalten wir

H(X) = - ∫∞

∞−

dx)x(flog)x(f - log ∆x

Da unter gleichen Bedingungen als konstant angesehen werden kann, lässt man das Glied log ∆x

meistens weg und spricht von der relativen Entropie einer kontinuierlichen Quelle

dx)x(flog)x(fHrel ∫∞

∞−

=

3. Kodierung diskreter Quellen Um Informationen übertragen oder verarbeiten zu können, muss sie in eine dafür geeignete Form

dargestellt werden. Dies erreicht man mit Kodierung. Unter Kodierung wird allgemein ein Vorgang

verstanden, bei dem die Elemente eines Alphabets auf die Elemente eines anderen Alphabets (bzw.

Wörter über diesem Alphabet) abgebildet werden. Für diskrete Quellen bedeutet das, dass jedes Ele-

ment des Quellenalphabets einem Element des Kanalalphabets U eindeutig zugeordnet wird.

Beispiel: Binärkodierung mit U = {1,0}

Ein Wort a ∈ Ul wird als Kodewort der Länge l bezeichnet. Das Alphabet A ∈ Ul (Menge alle Kodewör-

ter) das einem Quellenalphabet eindeutig zugeordnet ist, bildet ein Kode.

Sind alle Kodewörter von der gleichen Länge, heißt der Kode, gleichmäßiger Kode. Als ungleichmäßi-

ger Kode, wird ein Kode mit ungleicher Kodewortlänge bezeichnet.

3.1 Quellen-, Kanalkodierung und Redundanz

In der Regel ist es nötig die Codewörter bezüglich des Aufwandes zu minimieren (z.B. zeitminimale

Übertragung). Dies erfolgt mittels der Quellenkodierung. Hierzu zählt unter anderen die Huffman-

Codierung. Das Signal das an den Kanal übergeben wird, muss für die Übertragung mittels der Kanal-

kodierung so verändert werden, dass es optimal und möglichst fehlerarm über diesen Kanal gelangt.

In Abbildung 4 ist das Modell eines Nachrichtenkanals unter Hervorhebung der Quellen- und der Ka-

nalkodierung dargestellt.

6

Abbildung 4: Koderedundanz im Nachrichtenmodell

Bei der Kanalkodierung wird beabsichtigt Koderedundanz (d.h. der Kode enthält zusätzliche Bits, die

keine Information vermitteln) hinzugefügt, um Schutz gegen Störungen zu erreichen (siehe Abbildung

5). Bei der Quellenkodierung soll die Quelleninformation in eine möglichst redundanzarme Darstellung

gebracht werden.

Abbildung 5: Beispiel für das hinzufügen von Redundanz um die Nachrichten vor der Zerstörung im Ka-nal zu schützen ( BEC steht für binary erasure channel).

Aus praktischen Gründen wie das einsparen von Speicherplatz oder kürzere Übertragungszeiten der

Information, werden möglichst kleine Kodewortlängen angestrebt. Da jedoch die Kodewortlänge den

mittleren Informationsgehalt je Quellenzeichen verkörpert, gilt für einen dekodierbaren Kode die untere

Schranke l ≥ H. Für die Koderedundanz R gilt demnach

R = l – H ≥ 0

Die Forderung nach minimaler Koderedundanz führt zu der Frage, ob auch redundanzfreie Kodierung

(l = H) möglich ist. Shannon hat nachgewiesen, dass es prinzipiell möglich ist, jede diskrete Quelle

völlig redundanzfrei zu kodieren (Shannonsches Kodierungstheorem).

3.2 Dekodierung Die Kodierung erfüllt natürlich nur dann ihren Zweck, wenn die Kodewörter vom Empfänger wider

eindeutig den ursprünglichen Quellenzeichen zugeordnet werden können. Deshalb muss die Zuord-

nung von Quellenzeichen und Kodewörtern eindeutig sein. Ein Kode ist eindeutig dekodierbar, wenn

man die binäre Empfangsfolge eindeutig in Blöcke (Wörter) bestimmter Länge zerlegen und diese den

Quellenzeichen eindeutig zuordnen kann. Weiterhin wird gefordert, dass die Dekodierung unverzögert

7

erfolgen soll, d.h. jedes Wort soll unmittelbar nach Empfang der letzten Stelle eindeutig dekodiert wer-

den können.

Bei gleichmäßigen Kodes ist die Trennung der fortlaufenden Empfangsfolge (Erkennung der Worten-

den), kein Problem, weil alle Wörter gleichlang sind. Beim ungleichmäßigen Kode ist eine zusätzliche

Bedingung, zur Erkennung der Wortenden gefordert. Diese Bedingung ist die so genannte Präfix-

Eigenschaft. Ein ungleichmäßiger Kode, bei dem kein Kodewort den Anfang (Präfix) eines anderen

Kodewortes darstellt, wird als Kode mit Präfix-Eigenschaft bezeichnet.

Die so genannten Kommakodes bilden eine spezielle Klasse der Präfix-Kodes. Jedes Kodewort be-

steht hier nur aus Einsen und wird mit einer Null (als „Komma“) abgeschlossen. Ausnahme bilden nur

Kodewörter maximaler Länge deren letzte Stelle, Null als auch Eins sein kann. Um dies zu verdeutli-

chen betrachten wir den Kodebaum für dieses Beispiel. Dabei wird jedes Kodewort durch einen von

der Baumwurzel ausgehenden Pfad bis hin zu einem Endknoten (schwarzen Punkte) bestimmt.

Abbildung 6: Kodebaum für den Kommakode

Um die Dekodierungsbedingung zu erfüllen, darf es auf jedem Pfad des Kodebaums nur ein Endkno-

ten geben. Die Stufen des Kodebaums bestimmen die verschiedenen Kodewortlängen l = l1, l2,…, lmax.

3.3 Huffman-Verfahren (Optimalkodierung)

Unter einen optimalen Kode versteht man denjenigen Kode, der unter allen dekodierbaren Kodes

einer Quelle, die kleinstmögliche Redundanz aufweist. Die Minimierung der Koderedundanz ist gleich-

bedeutend mit der Maximierung des Anteils der Quelleninformation im Kodewort (Im günstigsten Fall

l = H). Dabei gilt, je höher die Auftrittswahrscheinlichkeit eines Quellenzeichens, umso kleiner ist die

entsprechende Kodewortlänge, und umgekehrt.

Beim Huffman-Verfahren wird zuerst das Wahrscheinlichkeitsfeld nach fallenden Werten geordnet. Die

letzten beiden Wahrscheinlichkeiten (die mit den kleinsten Werten) werden zu einem neuen Wert zu-

sammengefasst. Dieses neue reduzierte Wahrscheinlichkeitsfeld wird erneut nach fallenden Werten

geordnet und die letzten beiden Werte werden wieder zusammengefasst. Das ganze wird wiederholt

bis die Zusammenfassung der letzten beiden Werte eins ergibt. Nun wird ein Kodebaum entsprechend

dem Reduktionsschema aufgestellt indem die Kodesymbole 0 du 1 zugeordnet werden.

Beispiel:

Es sei nun folgendes Wahrscheinlichkeitsfeld gegeben: pj = (0,40 0,18 0,14 0,10 0,08 0,05 0,05)

In der folgenden Abbildung ist dafür das beschriebene Vorgehen beim Huffman-Verfahren dargestellt.

8

Abbildung 7: Huffman-Verfahren

Anhand des Kodebaums können wir die mittlere Kodewortlänge bestimmen.

Diese ist für ungleichmäßige Kodes

∑==

N

1iiim lpl

lm = 0,40⋅1+0,18⋅3+0,14⋅3+0,10⋅3+0,08⋅4+2⋅0,05⋅5 = 2,48 Binärzeichen (BZ) pro Quellenzeichen (QZ).

Damit beträgt die Koderedundanz bei diesem Optimalkode nur noch

R = 2,48 BZ/QZ⋅1bit/BZ – 2,43bit/QZ = 0,05bit/QZ.

3.4 Fehlerkorrigierender Hamming-Kode Die Anzahl der Stellen, in denen sich zwei Kodewörter unterscheiden, bezeichnet man als Hamming-

Distanz d. Betrachtet man z.B. die Kanalkodewörter (010) und (100), dann ist deren Hamming-Distanz

zwei, denn sie unterscheiden sich in der ersten und der zweiten Stelle. Bezüglich der Korrigierbarkeit

von Fehlern interessiert man sich besonders für die minimale Hamming-Distanz dmin eines Kanalko-

des.

Um einen Übertragungsfehler zu erkennen benötigt man einen Kode der die Hamming-Distanz dmin=2

hat. Bei so einem Kode unterscheidet sich jedes Kodewort mindestens um zwei Stellen von den ande-

ren. Betrachtet wir dazu den Kode mit den Kodewörtern 000, 011, 101 und 110. Ein Übertragungsfeh-

ler führt zwangsläufig auf ein Wort, dass nicht im Kode enthalten ist. Somit ist der Fehler erkannt. Zwei

Fehler können nicht erkannt werden, da ein Kodewort bei zwei Fehlern zu einem anderen Kodewort

wird und somit kommt es zu einer Fehlinterpretation. Bei einem Kode mit der Hammig-Distanz dmin = 3

werden zwei Fehler erkannt. Allgemein gilt, dass f = dmin – 1 Fehlerstellen erkannt werden können mit

der Hammingdistanz dmin.

Für die Fehlerkorrektur gilt dagegen, dass (dmin -1)/2 Fehler korrigiert werden bei ungeraden dmin und

(dmin-2)/2 werden für gerade dmin korrigiert. Dies wird verdeutlicht indem man um die benutzten Kode-

wörter so genannte „Korrekturkugeln“ (Hamming-Kugeln) legt (siehe Abbildung 8). Dabei sind so viele

Fehler korrigierbar, wie nicht benutze Kombinationen auf dem Weg zu dem anderen Kodewort inner-

halb dieser Korrekturkugeln liegen.

9

Abbildung 8: Kode mit dmin = 3 sowie die angedeuteten Korrekturkugeln

Bei großen Kodewortlängen ist es z.B. praktikabel Prüfstellen zu verwenden. Man fügt bei jedem Ko-

dewort eine Stelle hinzu so, dass die Anzahl der Einsen gerade (ungerade) ist. Der Fehler wird beim

Empfänger dadurch erkannt, dass die Prüfbedingung „gerade Zahl von Einsen“ nicht erfüllt ist.

Nun sind noch die Begriffe Generatormatrix, Kontrollmatrix und Syndrom zu klären. Vorteile bietet es,

Linearkodes durch Matrizen darzustellen. Der Zeilenraum der Generatormatrix G erzeugt den Linear-

kode. Jede Zeile (sind linear unabhängig) der Matrix entspricht also einem Kanalkodewort. Die Matrix

H wird als Kontrollmatrix des durch die Generatormatrix G erzeugten Linearkodes bezeichnet, denn

sie liefert unmittelbar eine Vorschrift zur Bildung der Kontrollstellen der Kanalkodewörter. Es gilt:

G⋅HT=0. Um festzustellen ob eine empfangene Binärfolge b ein Kanalkodewort ist, d.h. ob eine Verfäl-

schung vorliegt oder nicht, benutzen wir die Beziehung

s = H⋅bT

Wenn der Vektor den Wert Null annimmt, ist die empfangene Binärfolge ein Kanalkodewort. s wir als

Fehlersyndrom oder auch als Prüfvektor bezeichnet. Das Syndrom, kann auch zusätzlich dazu ver-

wendet werden, die Position der Verfälschung festzustellen und damit den Fehler zu beheben. Die

Korrektur erfolgt einfach durch Negation der als fehlerhaft erkannten Elemente.

Kodes die einen Fehler korrigieren können bezeichnet man als Hamming-Kode. Ein Hamming-Kode

hat die Hamming-Distanz dmin =3 und ist also damit geeignet einen Fehler in einer Empfangsfolge zu

korrigieren. Die Kodewortlänge n eines solchen Kodes beträgt n = 2k-1. k ist die Anzahl der Kontroll-

elemente (bestimmen Parität) in der Matrix H. Mit deren Hilfe ist erkennbar ob ein Fehler im Kodewort

vorliegt. Tritt ein Fehler auf ändert sich die Parität des Wortes (gerade Parität = gerade Anzahl von

Einsen)

Die Kontrollmatrix eines (7,4)-Hamming-Kodes hat die Form (n=7, k=3, 4 übrige Elemente neben k=3).

H =

1

1

1

0

1

1

1

0

1

0

0

1

1

1

0

0

1

0

1

0

0

Nehmen wir an das Wort b = 0110001, dann ist das Syndrom s = 110. Damit ist das inkorrekte Bit das

sechste, womit das Kodewort 0110011 ist. Die Kontrollelemente sind die Spalten die nur eine Eins

enthalten.

10

4. Kanalkapazität und Übertragungsgeschwindigkeit Uns interessiert auch, welche Zeit zur Übertragung einer bestimmten Informationsmenge in einen

vorgegebenen Kanal benötigt wird. Dafür ist es nötig Begriffe wie Inforationsfluss, Symbolfrequenz,

Schrittgeschwindigkeit und Übertragungsgeschwindigkeit zu erläutern.

Eine Quelle X liefert in einer bestimmten Folge Quellenzeichen QZ die zur Senke übertragen werden.

Die pro Sekunde abgegebene Anzahl von Quellenzeichen wird als Quellensymbolfrequenz fQ [QZ/s]

bezeichnet. Das Produkt aus der Quellenentropie H(X) und fQ wird Quelleninformationsfluss IQ =

fQ⋅H(X) [bit/s] genannt. Der Quellenkodierer passt die Quelle an ein Kanal an und wandelt Quellenzei-

chen in Kanalzeichen um. Dabei darf keine Information verloren gehen. Die Anzahl der Zeichen, die

zur Darstellung eines Quellenzeichens benötigt wird, soll mit l [Kanalzeichen (KZ) pro QZ] bezeichnet

werden. Kennen HK und H(X) gilt:

l=H(X)/HK

HK ist der maximale Informationsgehalt eins Kanalzeichens. Der Quellenkodeinformationsfluss, also

der Informationsfluss der den Quellenkodierer verlässt, berechet sich zu

IQK= fQ⋅l⋅HK

Da l nur ganzzahlig sein kann, muss gelten

IQK ≥ IQ

IQK= IQ, wenn H(X)/HK ganzzahlig ist, d.h. die Koderedundanz ist Null. IQK > IQ gilt immer dann, wenn

H(X)/HK nicht ganzzahlig ist, d.h. die Koderedundanz ist größer Null.

Der Kanalinformationsfluss IKK (=IK) der den Kanalkodierer verlässt ist größer als IQK, welcher vom

Qellenkodierer zum Kanalkodierer gelangt. Das ist der Fall, weil zusätzliche Kanalzeichen hinzugefügt

werden um eine gesicherte Übertragung zu ermöglichen.

Den Kanalkodierer verlässt der Transinformationsfluss IT, das ist die pro Kanalzeichen übertragene

Information. In Analogie zur Quellensymbolfrequenz können wir von einer Kanalsymbolfrequenz fK in

KZ/s sprechen. Ein Begriff für fK, der aus der Übertragungstechnik stammt, ist die Schrittgeschwindig-

keit vs in Schritt/s. Die maximal mögliche Schrittgeschwindigkeit wird durch die Bandbreite des Kanals

begrenzt. Eine weitere wichtige Kenngröße des Kanals ist die Übertragungsgeschwindigkeit vü in bit/.

Es gilt

vü = IK = vsHK

Die Übertragungsgeschwindigkeit und der Kanalinformationsfluss sind demnach das gleiche. vü ist

also ein Informationsfluss im Gegensatz zu vs, welches eine übertragungstechnische Größe ist. Für

den Transinformationsfluss IT, lässt sich ein ähnlicher Zusammenhang beschreiben:

IT = vsHT

11

Ist ein Kanal nicht gesichert, d.h. es gibt keinen Kanalkodierer, ist der Quelleninformationsfluss IQK

gleich dem Kanalinformationsfluss IK. Für einen gesicherten Kanal soll IT=IQK gelten. Es ist leicht ein-

zusehen, dass der Transinformationsfluss IT auf einen gestörten Kanal immer kleiner als die Übertra-

gungsgeschwindigkeit vü ist.

Auf realen Kanälen ist pro Zeit übertragbare Information begrenzt. An dieser Stelle kommen wir zum

Begriff Kanalkapazität C. Die Kanalkapazität ist der Maximalwert des Transinformationsflusses und ist

proportional zur Bandbreite B:

C = max{IT} ∼ B

5. Kryptographie Die Kryptologie ist ein Anwendungsgebiet der Informationstheorie und beschäftigt sich mit Methoden

Nachrichten zu verschlüsseln und zu entschlüsseln. Ein Anwendungsbeispiel ist das Pay-TV. Die Bil-

der werden in verschlüsselter Form gesendet und können mit Hilfe eines Receivers entschlüsselt wer-

den. Das Elektronik-Banking könnte ohne die Kryptologie nicht existieren. Die Kryptologie wird in zwei

Bereiche unterteilt, die Kryptographie und die Kryptoanalysis. Die Kryptography ist ein Gebiet, welches

sich mit der Entwicklung von Methoden zur Verschlüsselung beschäftigt. Hier wird allgemein gebrauch

von geheimen Schlüsseln gemacht. Nur diejenigen die diesen Schlüssel besitzen können die Nach-

richt entschlüsseln. Für jeden anderen ist der Zugang zu der Information geradezu unmöglich. Die

Kryptoanalysis beschäftigt sich mit der Entschlüsselung von Nachrichten ohne jeglichen Schlüssel

(„hacking“).

5.1 Allgemeines Schema eines Verschlüsselungssystems In Abbildung 9 ist ein allgemeines Verschlüsselungssystems gezeigt. Eine Quelle generiert eine Nach-

richt M, die als Klartext bezeichnet wird und übertragen werden soll.

Abbildung 9: Schema eines Verschlüsselungssystems

Danach wird der Klartext, in ein Chiffretext C umgewandelt. Die Entschlüsslung kann als eine Trans-

formation T angesehen werden, bei welcher M in C umgewandelt wird. Es gibt eine Zahl von Möglich-

keiten für diese Transformation, welche abhängig vom gewählten Schlüssel K ist. Dieser Schlüssel

entstammt einer Menge von möglichen Schlüsseln. Damit haben wir

)M(TC K=

12

Die Entschlüsselung passiert auf der Seite des Empfängers. Dazu wird die inverse Transformation

TK-1 durchgeführt womit folgt

)C(TM 1K

−= 5.2 Informationsgehalt und Sicherheit Der Informationsgehalt im Klartext wird durch die Entropie folgendermaßen ausgedrückt.

∑−==

n

1i

ii )M(plog)M(p)M(H

Dabei sind p(Mi) mit i=1,…, n die Wahrscheinlichkeiten der Ereignisse der Klartext-Nachrichten Mi. Die

Informationsmenge des Chiffretextes wird als H(C) und die Informationsmenge in Bezug auf den Kode

als H(K) bezeichnet. Analog sehen die bedingten Entropien aus. H(K|C) (Schlüssel-Mehrdeutigkeit) ist

ein Maß für die Unsicherheit des Schlüssels, wenn wir Kenntnisse über den verschlüsselten Text C

besitzen. Sei Kh mit h = 1,…, l eine Menge von Schlüsseln und Cj mit j = 1,…, m die möglichen Kryp-

togramme, dann gilt

)C|K(plog)C,K(p)C|K(H jhjh

l

1h

m

1j∑ ∑−== =

Die Schlüssel-Mehrdeutigkeit gibt also die Anzahl von Bits an, die zur Bestimmung eines Schlüssels

bekannt sein müssen, sofern ein Chiffretext gegeben ist. p(Kh|Cj) gibt die Wahrscheinlichkeit dafür an,

dass bei einem empfangenen Chiffretext C der Schlüssel K zur Verschlüsselung verwendet wurde.

H(M|C) ist dementsprechend der Informationsgehalt bezüglich des Klartextes M für einen gegebenen

Chiffretext. Dies wird auch die Nachrichten-Mehrdeutigkeit genannt. H(M|C,K) kann einfach als Infor-

mationsgehalt in Bezug auf den Klartext, wenn Chiffretext und Kode bekannt sind bezeichnet werden.

Ist der Klartext eindeutig in Bezug auf den Chiffretext und den Schlüssel, gilt:

H(M|C,K) = 0

Das bedeutet, wenn wir Zugriff auf den verschlüsselten Text haben und den Schlüssel, dann ist es

auch möglich den Klartext zu finden: Die Unbestimmtheit (Informationsgehalt) von M ist gleich Null.

H(K|M,C) wird die Schlüssel-Auftritts-Mehrdeutigkeit (key appearance equivocation) genannt, welches

der Informationsgehalt im Bezug auf den Schlüssel bei gegebenen Klartext und Chiffretext. Weiter gilt:

H(K|M,C) = H(K|C) - H(M|C)

Die wechselseitige Information I(M,C) zwischen Klartext und Chiffretext ist

)M|C(H)C(H)C|M(H)M(H)C,M(I −=−=

I(M,C) sollte so klein wie möglich sein, denn die wechselseitige Information ist auch ein Maß für die

gegenseitige Abhängigkeit von Klartext und Chiffretext. D.h., wenn der Chiffretext absolut keine Infor-

mation über den Klartext enthält, gilt H(M|C) = H(M) (Kenntnis von C ändert nichts an der Ungewiss-

heit von M) und die wechselseitig Information zwischen Klartext und Chiffretext wird Null I(M,C). Ist

I(M,C) = 0 sprechen wir von einem absolut sicheren Verschlüsselungssystem.

13

5.3 One-Time-Pad Kryptographie

Während des zweiten Weltkrieges wurde die so genante One-Time-Pad Kryptographie von den Deut-

schen und von den Russen verwendet. Diese Verschlüsselungsform ist unknackbar, allerdings auch

sehr unpraktisch.

A und B kennen beide den Schlüssel, wobei der Schlüssel mindestens genauso lang wie die Nach-

richt sein muss. Zuerst muss das Alphabet in eine universell bekannten Art und Weise numerisch

codiert werden. Hierzu kann die folgende Tafel dienen (Alternative ASCII-Code)

Das Alphabet umfasst hier 30 Zeichen (d.h. N = 30). Alice verwendet jetzt z.B. den folgenden Schlüs-

sel: 12 01 18 27 03 23 05 10 21 24. Nun addiert sie den Schlüssel mit der Nachricht modulo N:

Bob, der den Schlüssel kennt, kann jetzt die Nachricht durch Subtraktion des Codes modulo N ent-

schlüsseln. Das Verfahren hat aber mehrere Nachteile, wie sehr lange Schlüssel und das jeder

Schlüssel nur einmal verwendet werden kann. Da die sichere Schlüsselübertragung problematisch ist,

kann auch ein längerer Code verwendet werden, wobei jedes Mal ein neues Teilstück gewählt wird.

Durch Zusatzprotokolle ist es auch möglich, am Anfang der Nachricht eine Position in einer frei und

eindeutig zugänglichen Quelle (z.B. in einem Buch) zu kennzeichnen. Die Positionsangabe (Seite,

Zeile, Spalte) stellt dann den Beginn des Codes dar.

5.4 Public-Key Verschlüsselungssystem

Die Public-Key-Methode wurde erst 1976 vorgestellt und ist heute ein Standardverfahren. Es wird

nicht nur von Banken und anderen Finanzinstitutionen eingesetzt, sondern auch bei normalen E-Mails.

Als Beispiel ist der RSA-Kode im folgendem vorgestellt.

5.4.1 Allgemeines Prinzip Jeder Teilnehmer Ai am System verfügt über ein Schlüsselpaar (ki, li). Daneben ist allen Teilnehmern

der Kodier-Algorithmus C sowie der Dekodieralgorithmus D bekannt. Diese Algorithmen erfüllen für

jedes Schlüsselpaar (ki, li) und jede Nachricht M die Bedingung

M = D(C(M, ki), li)

Der Schlüssel ki wird nun allen anderen Teilnehmern bekannt gegeben (er wird daher öffentlicher

Schlüssel genannt), während der Schlüssel li geheim bleibt.

Will Bj nun eine verschlüsselte Nachricht an Ai senden, läuft folgendes ab:

14

1. Bj ermittelt den öffentlichen Schlüssel ki von Ai.

2. Bj berechnet das Kryptogramm c = C(M, ki).

3. Das Kryptogramm c wird über öffentliche Kanäle an Ai übertragen.

4. Ai gewinnt mittels M = D(c, li) die Nachricht zurück.

Damit ein solches Verfahren sicher und in großem Maßstab praktisch ist, müssen folgende Voraus-

setzungen erfüllt werden:

1. Es muss leicht sein, zufällige Paare (ki, li) zu generieren.

2. Das Kryptogramm c = C(M, ki) muss leicht berechenbar sein.

3. Ohne li muss das Dekodieren von c sehr aufwendig sein.

4. Mit li muss M = D(c, li) leicht berechenbar sein.

5.4.2 Rivest-Shamir-Adleman System

A generiert zwei große Primzahlen p und q. Im folgendem ist n = p⋅q. Als nächstes berechnet A

z = (p − 1)⋅(q − 1)

und wählt zwei natürliche Zahlen e und d, die der Bedingung d⋅e = 1mod z genügen, aus. Wenn d (bzw.

e) relativ Prim zu z ist, d.h. d und z haben keine gemeinsamen Primfaktoren, dann liegt e fest. Die Zah-

len p und q werden im folgendem nicht mehr benötigt und von A sicherheitshalber vernichtet. A hat

jetzt zwei Schlüssel: Den öffentlichen Schlüssel (e, n): Dieser Schlüssel wird möglichst weit verbreitet,

insbesondere erhält B eine Kopie hiervon. Und den privaten Schlüssel d: A sichert den Schlüssel, da

er unbedingt geheim, d.h. nur ihm bekannt sein darf. Damit sind die Vorbereitungen von A abge-

schlossen. Möchte B eine codierte Nachricht an A senden, dann bildet B die Nachricht auf eine Zif-

fernfolge ab, zerlegt diese Folge in Blöcke der Größe k (ggf. füllt er den letzten Block mit Nullen auf)

und berechnet für jeden Block (hier mit x bezeichnet):

C(x) = x

e mod n

Die so kodierte Nachricht sendet B an A. Um die Nachricht zu dekodieren, berechnet A für jeden Zif-

fernblock y = C(x)

D(y) = yd mod n mit D(y) ≡ x

Ein potentieller Lauscher (E) müsste zuerst n faktorisieren, um d zu ermitteln (NP-Problem).

Beispiel:

Erzeugung des Schlüssels: A wählt p = 47 und q = 71 und damit n = 3337 und z = 3220. Als nächstes

wählt A d = 1019 aus und prüft, ob d und z teilerfremd (coprim) sind. Da dies der Fall ist, berechnet A

die Zahl c, die c⋅d = 1mod z, d.h. c⋅1019 = 1mod 3220, erfüllt. Dies wird von c = 79 geleistet. Damit Ist

der öffentliche Schlüssel (c, n) = (79, 3337) und der private Schlüssel d = 1019.

15

Erzeugung und Übertragung der Nachricht: B möchte nun A die Nachricht STRENG GEHEIM? übermit-

teln. Dazu kodiert B diese Nachricht numerisch (unter Verwendung der Übersetzungstabelle aus 8.3)

und gruppiert diese dann in vierziffern-Folge:

Nun wendet B auf jeden Block x die Codierfunktion C(x) = x

cmod n = x79

mod 3337 an:

Das Kryptogramm 3211267519101179041614700384 wird nun über einen öffentlichen Kanal an A

übertragen, der es wieder in vierziffern-Blöcke y zerlegt und D(y) = yd mod n = y1019 mod 3337 berech-

net:

Schließlich kann A nun die Ziffernfolge wieder in Text zurückübersetzen.

5.5 NP-strenges Problem als Kryptosystem

In P (Polynomzeit) liegen Probleme die einen Algorithmus besitzen der das Problem in Polynomialer

Zeit löst (anders: in endlicher Zeit lösbar). In NP liegen Probleme für die bisher noch kein Algorithmus

gefunden wurde der das Problem in Polynomialer Zeit löst. Für viele Probleme ist ein Algorithmus mit

polynomieller Laufzeit bekannt. Für andere, einfache Probleme konnten lediglich Algorithmen mit ex-

ponentieller Laufzeit gefunden werden (NP). Allerdings kann bislang nicht bewiesen werden, dass für

diese Probleme kein polynomieller Algorithmus existiert. Es ist also unklar, ob es zwei Klassen von

Problemen gibt: polynomiell, und nicht-polynomiell lösbare. Andere Schreibweise: Gilt wirklich P ≠

NP? Viele Probleme, für die kein polynomieller Algorithmus bekannt ist, sind polynomiell äquivalent.

Wird also für nur eins dieser Probleme ein polynomieller Algorithmus gefunden, sind die anderen

Probleme auch polynomiell lösbar, und P = NP. Public-Key-Verfahren beruhen meist auf Problemen

aus NP (Auffinden des geheimen Schlüssels ist aus NP). Falls also P =NP gilt, wird ein Großteil der

Public-Key-Kryptographie hinfällig.

Die Sicherheit der momentan gängigen Verfahren beruht auf schwierigen Algorithmen (d.h. nicht in

polynomieller Laufzeit lösbar), und der Annahme P ≠ NP. Mit Quantencomputern sind exponentielle

Laufzeiten kein Problem mehr. Es wird bereits jetzt an sogenannter „quantum-hard cryptography“

gearbeitet.