TU Dresden, Fakultat Mathematik und Naturwissenschaften, Institut furAlgebra.

Informationstheorie

Ausarbeitung zum SeminarSchreiben mathematischer Texte

Bearbeiter:Sandra Winzer Matrikel-Nr: 3396656

Dominic Hanel Matrikel-Nr: 3343358

Franziska Boitz Matrikel-Nr: 3351850

Alexander Muller Matrikel-Nr: 3265725

Betreuer:Prof. Dr. Stefan E. Schmidt

Eingereicht am 16.06.2010

Inhaltsverzeichnis

1 Historischer Einstieg 31.1 Etymologie des Informationsbegriffs . . . . . . . . . . . . . . . 31.2 Informationstheorie und Computertechnik im 20. Jahrhundert 31.3 Historische Entwicklung der Informationstheorie (SHANNON) 4

1.3.1 Biographie Claude Elwood Shannon . . . . . . . . . . . 41.3.2 SHANNONs Errungenschaften in der Informationstheo-

rie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Informationstheorie 82.1 Gegenstand der Informationstheorie und Codierungstheorie . . 82.2 Der Begriff Information und Informationsmaß . . . . . . . . . 92.3 Aufgaben und Ziele . . . . . . . . . . . . . . . . . . . . . . . . 10

3 Algebraische Grundlagen 103.1 Definitionen wichtiger Grundbegriffe . . . . . . . . . . . . . . 103.2 Vektorraume . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.3 Polynome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4 Grundlagen aus der Wahrscheinlichkeitsrechnung 17

5 Codierungstheorie 215.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

6 Code - Ein- und Abgrenzung 216.1 Definition Code . . . . . . . . . . . . . . . . . . . . . . . . . . 216.2 Redundanz . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226.3 Wichtige Codes . . . . . . . . . . . . . . . . . . . . . . . . . . 22

7 Effizienz eines Codierers 23

8 Vorstellung einiger Codes 258.1 Einordnung der Kanalcodes . . . . . . . . . . . . . . . . . . . 258.2 Fehlerkorrektur mit Hilfe des Hamming-Abstandes . . . . . . . 26

8.2.1 Der Hamming-Abstand . . . . . . . . . . . . . . . . . . 278.3 Lineare Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

8.3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . 298.3.2 Die Generatormatrix . . . . . . . . . . . . . . . . . . . 30

1

8.3.3 Die Kontrollmatrix . . . . . . . . . . . . . . . . . . . . 318.4 Zyklische Codes . . . . . . . . . . . . . . . . . . . . . . . . . . 32

8.4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . 328.4.2 Darstellung als Polynome . . . . . . . . . . . . . . . . 328.4.3 Das Generatorpolynom . . . . . . . . . . . . . . . . . . 338.4.4 Codierung . . . . . . . . . . . . . . . . . . . . . . . . . 34

8.5 Anmerkung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

9 Entropie 379.1 Einfuhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

10 Verwendung von Entropie in Fachrichtungen 3710.1 Physikalisch-chemischer Entropiebegriff . . . . . . . . . . . . . 3710.2 Entropie von Wahrscheinlichkeitsraumen . . . . . . . . . . . . 40

10.2.1 Eigenschaften der Entropie eines endlichen Wahrschein-lichkeitsraumes . . . . . . . . . . . . . . . . . . . . . . 41

10.2.2 Eindeutigkeitssatz fur die Entropie . . . . . . . . . . . 4310.3 Der Entropiebegriff in der Informationstheorie . . . . . . . . . 48

10.3.1 Entropie, Unsicherheit und Informationsgehalt einerNachricht . . . . . . . . . . . . . . . . . . . . . . . . . 49

10.3.2 Mathematische Definition der Entropie nach SHANNON 50

11 Die Satze von SHANNON 5111.1 Der erste Satz von SHANNON . . . . . . . . . . . . . . . . . . 5211.2 Der zweite Satz von SHANNON . . . . . . . . . . . . . . . . . 52

12 Anwendungen der Informationstheorie 5412.1 Kryptologie - Einmalverschlusselung . . . . . . . . . . . . . . 55

12.1.1 Sicherheit . . . . . . . . . . . . . . . . . . . . . . . . . 5512.1.2 Funktionsweise . . . . . . . . . . . . . . . . . . . . . . 5612.1.3 Vor- und Nachteile . . . . . . . . . . . . . . . . . . . . 58

12.2 Informationstheorie in den Kognitionswissenschaften . . . . . 6012.2.1 Symbolismus . . . . . . . . . . . . . . . . . . . . . . . 6112.2.2 Konnektionismus . . . . . . . . . . . . . . . . . . . . . 6212.2.3 Beispiel: Assoziativspeichermodell . . . . . . . . . . . . 6312.2.4 Vergleich der Paradigmen . . . . . . . . . . . . . . . . 6512.2.5 Extraterrestrische Radioubertragungen . . . . . . . . . 66

2

1 Historischer Einstieg

1.1 Etymologie des Informationsbegriffs

Der Begriff Information wird gegenwartig haufig benutzt, jedoch lasst die-ser Gebrauch oft den klassischen Ursprung außer Acht. Somit soll sich dererste Abschnitt kurz mit der Herkunftsgeschichte des Informationsbegriffsbeschaftigen.Im Rahmen dieser Arbeit wird die Etymologie auf wesentliche Punkte be-schrankt. Fur eine detailliertere Ausfuhrung kann bei RAFAEL CAPURRO(1978) nachgelesen werden. [9]Der Informationsbegriff basiert auf einem Schlusselbegriff der griechischenPhilosophie. Dabei wird ein Formbegriff gepragt. PLATON greift diesenFormbegriff, der die Gestalt oder das Aussehen einer Sache beschreibt, aufund stellt sie ins Zentrum seiner Philosophie. Das heißt er betrachtet dieForm als Urbild oder Idee, wobei die Form als der Materie aufgesetzt an-gesehen wird. ARISTOTELES nimmt dies auf und bezeichnet empirischeGegenstande als aus Materie und Form zusammengesetzt. Unser heutigerFormbegriff stammt aus der Ubersetzung des griechischen Formbegriffs indas Lateinische forma. Information nutzt der Lateiner, um die Handlung desFormens und Gestaltens auszudrucken. Dies geschieht auch im Zusammen-hang von Belehrung und Unterweisung als einer Formung des Intellekts. Demfolgt eine abstraktere Bedeutung als Vorstellung oder Begriff. Das deutscheWort informieren stammt aus dem lateinischen Verb informare. Dabei stelltsich eine ausschlaggebende Bedeutungsubertragung von unterrichten zu be-nachrichtigen heraus. Erst wurde im deutschen das Wort Bildung gegenuberdem Wort Information vorgezogen. Somit blieb Information als neuzeitlicheBedeutung von Information als Wissensmittlung oder Nachricht. [9]

1.2 Informationstheorie und Computertechnik im 20.Jahrhundert

In den 30er Jahren des 20. Jahrhunderts entwickeln sich die Nachrichten-und die Informationstheorie, womit die neuzeitlich-moderne Bedeutung vonInformation als Nachricht verfestigt ist. Die mathematisierte Theorie der In-formation geht auf Arbeiten von SHANNON, HARTLEY, WEAVER undWIENER zuruck.

3

In der Mitte des 20. Jahrhunderts setzte eine rasante Computerentwicklungein, welche die nachrichtentechnische Informationstheorie stark begunstigte.Die Entwicklung der Computertechnik ist so grundlegend, dass hier wichtigeAbschnitte kurz genannt werden. In den 1940er Jahren entwickelte sich dieAutomatentheorie und in den 1950er Jahren wurden Rechenmaschinenmo-delle erforscht. In den sechziger und siebziger Jahren wurde ein Programmder kunstlichen Intelligenz eingesetzt, welches menschliches Denken und Ko-gnitionsleistungen auf einer reinen Symbolverarbeitung reduzierte. Mit derEntwicklung von der Computersprache LISP versuchte man allgemeine Pro-blemlosungsverfahren zu entwickeln. Heute wird das Prinzip zum Teil mitneuronalen Netzen verbunden.

Eine Studie zum Informationsbegriff entstand bereits bei ERHARD OESER(1976). Zweifellos hat der technische Erfolg in der Informationstheorie un-sere Gegenwart beeinflusst, womit sich der charakteristische Begriff des In-formationszeitalter pragte. Wobei man heute auch von einer Wissens- oderBildungsgesellschaft sprechen kann. Somit sind die Begriffswurzeln des latei-nischen Wortes information als Information bzw. Bildung in gewissem Sinnezusammenfuhrbar. [9]

1.3 Historische Entwicklung der Informationstheorie(SHANNON)

Die moderne Informationstheorie hat sich aus den Arbeiten mehrerer Wis-senschaftler entwickelt, wobei hier HARTLEY, GABOR, KOTELNIKOW,KUPFMULLER und SHANNON genannt seien. Im Folgenden werden dieErrungenschaften von SHANNON naher beleuchtet, wobei vorangehend einekurze Biographie SHANNONs erfolgt.

1.3.1 Biographie Claude Elwood Shannon

Claude Elwood Shannon wurde am 30. April 1916 in Petoskey, Michigan ge-boren und verstarb am 24. Februar 2001 in Medford, Massachusetts. Shan-non gilt als Begrunder der Informationstheorie. Er arbeitete wahrend er dieHigh-School besuchte als Bote fur die Western Union (Unternehmen vonweltweitem Geldtransfer). 1932 ging er an die University of Michigan, woseine Schwester Catherine bereits war und im gleichen Jahr ihr Mathema-tikstudium abschloss. Shannon begann ein Elektrotechnik- und Mathematik-

4

studium. Mit einem Abschluss in Mathematik und Elektrotechnik wechselter im Jahr 1936 an das Massachusetts Institute of Technology (MIT). SeineAbschlussarbeit zum Master in Elektrotechnik schrieb er 1937 mit dem TitelA Symbolic Analysis of Relay and Switching Circuits. Dabei benutzte er zurKonstruktion von digitalen Schaltkreisen die Boolesche Algebra. 1940 folgtesein Doktortitel in Mathematik mit einer Arbeit uber theoretische Genetik(An Algebra for Theoretical Genetics). Daraufhin arbeitete er als Forscheram Institute for Advanced Study in Princeton, wobei er bald als Mathema-tiker zu AT+T (nordamerikanischer Telekommunikationskonzern) Bell Labs(Teil der Forschungs- und Entwicklungsabteilung von Alcatel-Lucent) wech-selte. [20]1958 ging er an das MIT, wobei er bereits seit 1956 dort eine Gastprofessuraufgenommen hat. 1978 wurde er vom MIT emeritiert. Als Berater bei denBell Labs fungierte er bis 1972. Des Weiteren veroffentlichte er einen Artikelzum Thema Communication in the presence of noise, wo er die Darstel-lung frequenzbeschrankter Funktionen betrachtet. Den Artikel uber formaleGrundlagen der Kryptographie Communication Theory of Secrecy Systemsveroffentlichte er 1949. [20]Shannon war kreativ und vielseitig interessiert. Dies zeigte sich in der Ent-wicklung der folgenden Produkte: eine Jonglier-Maschine, raketengetriebe-ne Frisbees, motorisierte Pogostocke, eine Maschine zum Gedankenlesen, ei-ne mechanische Maus, die sich in Labyrinthen orientieren konnte und einenSchachcomputer (1960). [20] Die Einheit des Informationsgehaltes einer Nach-richt (Shannon) wurde nach ihm benannt. Des Weiteren wurde das For-schungslabor der AT+T in Florham Park ihm zu Ehren AT+T ShannonLaboratory benannt. [20]Im Bereich der Booleschen Algebra hat er folgende Ergebnisse erarbeitet:Inversionssatz sowie der Entwicklungssatz von SHANNON. [20]

1.3.2 SHANNONs Errungenschaften in der Informationstheorie

SHANNON hat die Arbeiten seiner Vorganger mathematisch untermauertund erweitert, wobei er seine Veroffentlichungen in drei Arbeiten publizierthat. Seine erste Arbeit war eine Erweiterung des modifizierten Hartley-Gesetzes,die auf einer geometrischen Vorstellung basierte und Folgerungen ergab. DieseArbeit blieb unveroffentlicht. SHANNON zweite Arbeit war eine Darstellungseiner ersten und brachte die Einfuhrung der Entropie als Maß fur die In-formation. Die endgultige Arbeit stellt die ganze Theorie zusammen. Diese

5

Arbeit zur Informationstheorie war die Betrachtung des Problems, unter wel-chen Bedingungen eine Datei, die von einem Sender kodiert wurde und diedurch einen gestorten Kommunikationskanal ubermittelt wurde, am Zielortohne Informationsverluste wiederhergestellt werden kann. Dabei nahm er be-zug auf das Konzept der Entropie, welches aus der Physik bekannt ist. Derdamit gelegte Beitrag war auf dem Gebiet der Nachrichtenubertragung we-sentlich. [11] [20]SHANNON ging in seinen ersten beiden Arbeiten anders vor, als seine Vorlaufer.Dabei kann man folgendes Prinzipschema einer Nachrichtenkette betrachten.

[Informationsquelle]→ [Sender]→ [verrauschterKanal]→ [Empfaenger]→ [Bestimmung]

In einer Informationsquelle entsteht eine Information. Beispiele fur einesolche Informationsquelle sind Fernsehbildaufnahmerohren, Mikrofone odereine singende oder sprechende Person. Die Nachricht setzt sich aus einer Fol-ge von Symbolen zusammen, welche unterschiedlichen Spannungsamplitudensein konnen. Eine chronologische Abfolge ist nicht zwingend vorausgesetzt,sondern kann erst durch die Technik der Informationsquelle aus einer ande-ren als zeitlicher Reihenfolge erzeugt werden. Die ubertragenen Informatio-nen konnen auf zwei Arten entstehen. Zum einen konnen die ubertragenenInformationen auf einer Sammlung einer endlichen Zahl diskreter Symboleherstammen oder zum anderen aus sich fortdauernd andernden Informati-onselementen bestehen. [11]Die zu ubertragende Nachricht wird von der Informationsquelle zu einemSender geleitet. Dabei ist es wichtig die Existenz einer festgelegten Bezie-hung zwischen der Nachricht und dem vom Sender ausgehenden Signal zubedenken. Dies ist immer eine Zeitfunktion. Vom Sender aus wird ein ver-rauschter Ubertragungskanal, der mehr oder weniger gestort ist, passiert.Auf dessen Empfangerseite wird das Empfangssignal gebildet. Das Emp-fangssignal kommt zum Empfanger, in dem die Dekodierung der Nachrichtaus dem gestorten Signal ausgefuhrt wird. Der sich am Ausgang befindlicheEmpfanger kann ein Gerat oder eine Person sein, fur die die Nachricht be-stimmt ist. Der Empfanger muss charakterisiert sein, da nur Nachrichten,die auch vom Empfanger gelesen werden konnen, auch sinnvoll zu versendensind. Beispielsweise muss ein Bild nicht besser ubermittelt werden, wennder Empfanger es qualitativ nicht besser darstellen kann. Diesem Faktorschenkte SHANNON weniger Betrachtung, stattdessen sah er das Problemder Nachrichtenubertragung eher als Aufgabe, die Nachricht von der Quelle

6

zum Empfanger zu bringen. [11]SHANNON konnte auch zeigen, dass ein vom Sender gesendetes Signal derZeitdauer T und der Bandbreite W genau durch eine Anordnung von zweiTW-Ziffern mit einem gegenseitigen Abstand von 0,5 W Sekunden ubertragenwerden kann. Somit ist es moglich das Signal als einen Punkt in einen 2-TW-dimensionalen Raum aufzufassen. Die TW-Ziffern bzw. Koordinaten definie-ren genau einen Punkt. SHANNON fuhrt hier eine Betrachtungsweise ein, diees ermoglicht, geometrische Vorstellungen bei der Betrachtung von Signaleneinzusetzen und damit ubersichtliche Ergebnisse darzustellen. Da zwei TWfur Signale mit normalem Schwierigkeitsgrad eine sehr große Ziffer ist, be-deutet die geometrische Darstellung, dass ein einfacher Begriff in einer man-nigfaltigen Umgebung genutzt wird, um einen komplizierten Begriff in einereinfachen Umgebung darzustellen. Der Signalpunkt im mehrdimensionalenRaum ist der einfache Begriff der mannigfaltigen Umgebung. Dagegen istder komplizierte Begriff in einer einfachen Umgebung das ursprungliche Si-gnal als Zeitfunktion. [11]Eine Nachricht lasst sich immer durch eine endliche Zahl von Ziffern darstel-len, somit ist es moglich diese Zahlen als Punkte in einem mehrdimensiona-len Raum vorzustellen. Ein Sender stellt somit die Beziehung zwischen denPunkten des Nachrichtenraumes und denen des Signalraumes her. Shannonzeigte außerdem, dass dem Empfanger die Aufgabe zugeschrieben wird, denNachrichtenpunkt auszuwahlen, der dem empfangenen Signalpunkt koordi-niert ist. [11]Um die Arbeit von Shannon von einer weiteren Seite zu beleuchten, sindim nachstehenden 3 Fragen genannt, die von dieser Arbeit beantwortet wer-den [11]:

1. Wie kann man das Geschwindigkeitsmaß definieren, mit dem Informa-tionen durch eine Nachrichtenquelle erzeugt werden? Eine Grundanfor-derung an das Maß ist die Realisierung von diskreten Symbolen undkontinuierlich veranderlichen Symbolen. Des Weiteren muss die Wahr-scheinlichkeitsstruktur berucksichtigt werden.

2. Wie viel aquivalente Zweierschritte der Nachrichtenubertragung je nachZeiteinheit lassen sich durch einen Nachrichtenkanal ubertragen, wenneine bestimmte Signalleistung, eine definierte Art und ein bestimmterStorungspegel vorliegen?

3. Welche Codierungsmethoden lassen sich benutzen, um eine Nachricht

7

gegebenen Informationsinhalts durch einen Ubertragungskanal gegebe-ner Kapazitat mit der großtmoglichen Geschwindigkeit zu ubertragen,besonders, wenn die Nachricht in ihrer ursprunglichen Form von einergegenuber dem Kanal verschiedenen Bandbreite ist?

2 Informationstheorie

2.1 Gegenstand der Informationstheorie und Codie-rungstheorie

Die Informations- und Codierungstheorie unterstutzt die Beschreibung, Ana-lyse und Bewertung informationeller Prozesse, wie zum Beispiel der Erzeu-gung, Ubertragung und Speicherung von Informationen. Dabei erscheint dieInformation in kodierter Form, was den Zusammenhang zwischen Informations-und Codierungstheorie zeigt. Die Informationstheorie widmet sich nur derspezifischen Seite der Information, namlich dem statistischen Aspekt. Somitgelangt es an seine Grenzen, da es sich auf die wahrscheinlichkeitstheoretischeVerteilung der informationstragenden Elemente (z.B. Zeichen) bezieht. Dahernennt man das Gebiet auch Statistische Informationstheorie oder SHANN-ONsche Informationstheorie. Fur die Einbeziehung des semantischen Aspekts(Bedeutung der Information) und des pragmatischen Aspekts (Nutzen furden Informationsempfanger) ist bisher noch keine allseitige Losung gefunden.Jedoch kann aufgrund der Einschrankung auf den statistischen Aspekt einemathematische Modellierung erfolgen. Somit kann die SHANNONsche Infor-mationstheorie beispielsweise bei der Ubertragung und Speicherung von Da-teien eingesetzt werden (siehe auch Nachrichtenmodell im Abschnitt SHAN-NON). [7]Die Effektivitat bei der Informationsubertragung hangt erheblich von derKodierung der Information ab. Hierbei sind die folgenden zwei Aspekte zubetrachten. Zum einen muss die Quellinformation eindeutig und rationellin einer ubertragungsfahigen Form vorhanden sein (Quellencodierung) undzum anderen soll sie gegen Storungen auf dem Uberragungskanal geschutztwerden (Kanalcodierung). Methoden dazu liefert die Codierungstheorie. DieInformationstheorie liefert die Moglichkeiten und Grenzen der Informati-onsubertragung bei einer geeigneten Codierung. [7]

8

2.2 Der Begriff Information und Informationsmaß

Wie bereits im Abschnitt Etymologie stellen wir fest, dass es keine einheitli-che Definition des Begriffes Information gibt. Beispielsweise ist es subjektiv,ob jemand eine Vorlesung informativ oder nicht informativ fand. Also ver-bindet man Information mit der Gewinnung von neuen Feststellungen auseiner Quelle. Da man aus der Quelle etwas neues Erfahren mochte, liegteine gewisse Unbestimmtheit vor. Beispielsweise besteht die Unbestimmt-heit beim lateinischen Alphabet (Informationsquelle) aus den verschiedenenAuswahlmoglichkeiten der N = 27 Zeichen. Nun bestimmt der Inhalt derNachricht die Anordnung der Zeichen. Dies wirkt auf einen außenstehen-den Betrachter wie ein Zufallsprozess. Mit einer konkreten Wahl beseitigtman diese Ungewissheit uber der Angelegenheit. Daher stammt die vertrau-te Ausfuhrung: Information ist beseitigte Unbestimmtheit. [7]Um einen Ansatz zur quantitativen Beschreibung von Informationsprozessenzu gewinnen, muss man das Maß dieser Unbestimmtheit als entsprechendenAusdruck der Informationsmenge ermitteln. [7]Im Folgenden wird ein Ansatz, der auf HARTLAY zuruckgeht und vonSHANNON ausgebaut wurde, erwahnt. In einer Menge X = x1, x2, . . . , xNsoll das Ereignis xi mit der Wahrscheinlichkeit p(xi) fur i = (1, 2, . . . , N)auftreten. Beispielsweise kann das Ereignis die Wahl eines Buchstabens deslateinischen Alphabets sein. Das Maß Hi fur die Unbestimmtheit uber dasEreignis xi ist der reziproke Wert von p(xi). Daraus folgt, dass je großer p(xi)ist, Hi umso kleiner wird (und umgekehrt). Damit ist auch gegeben, dass dassicherer Ereignis p(xi) = 1 keine Unbestimmtheit enthalt, wenn man denLogarithmus bildet. Man erhalt [7]:

Hi = log1

p(xi)= −log p(xi) (1)

Da Informationen als beseitigte Unbestimmtheit verstanden werden soll,gelten fur den Ausdruck Hi folgende zwei Gegebenheiten. Einerseits be-schreibt Hi das Maß der Unbestimmtheit, welche vor dem Auftreten vonxi vorhanden war und andererseits gilt der Ausdruck Hi fur das Maß derInformation, die nach dem Auftreten von xi gewonnen wurde. Dieses Infor-mationsmaß zeigt jedoch nur den statistischen Aspekt der Information auf.

9

2.3 Aufgaben und Ziele

Hauptsachliche Aufgaben und Ziele der Informations- und Codierungstheorienach [7] sind:

• Modellmaßige Beschreibung informationstheoretischer Probleme in rea-len Informationssystemen,

• Darstellung gesetzmaßiger Zusammenhange und Berechnung speziellerKenngroßen, um die Leistungsfahigkeit von Informationssystemen zuerkennen sowie bestimmte Parameter optimal abzustimmen,

• Entwurf und Bewertung von Codes bezuglich vorgegebener Kriterien,z.B. minimale Codewortlangen (Quellencodierung) oder hohe Storsicherheit(Kanalcodierung). Ziel ist eine nahezu fehlerfreie Dekodierung bei op-timalen Codeparametern.

3 Algebraische Grundlagen

Im Abschnitt der Algebraischen Grundlagen werden einige Begriffe, welchein der algebraischen Codierungstheorie genutzt werden, aufgezeigt. Dies solleinen kurzen Einblick geben und ist somit nicht vollstandig.

3.1 Definitionen wichtiger Grundbegriffe

G, heißt Gruppe, falls folgende Axiome gelten [23]:

1. (Assoziativgesetz)Fur alle x, y, z ∈ G gilt: (x y) z = x (y z).

2. (Neutrales Element)Es gibt genau ein Element 0 ∈ G mit 0 x = x 0 = x fur alle x ∈ G.

3. (Inverse Elemente)Zu jedem x ∈ G gibt es genau ein inverses Element y ∈ G mit x y =y x = 0.

Die Gruppe G heißt kommutativ bzw. abelsch, wenn zusatzlich gilt:Fur alle x, y ∈ G gilt: x y = y x (Kommutativgesetz)

(R,+, ·) heißt Ring, falls folgende Axiome gelten [23]:

10

1. (R,+) ist eine kommutative Gruppe.

2. (Assoziativgesetz fur ·)Fur alle x, y, z ∈ R gilt: (xy)z = x(yz)

3. (Distributivgesetze)Fur alle x, y, z ∈ R gilt: x(y + z) = xy + xz, (x+ y)z = xz + yz

Existiert bezuglich · ein neutrales Element, heißt er Ring mit Einsele-ment.Ist · kommutativ, heißt der Ring kommutativ.

Ein kommutativer Ring mit Einselement , indem extra fur jedes Elementx ∈ R \ 0 ein inverses Element bezuglich der Operation · existiert, heißtKorper.

K = (K,+, ·) heißt Korper, falls gilt [23]:

1. (K,+) ist eine abelsche Gruppe.

2. (K \ 0 , ·,+) ist eine abelsche Gruppe.

3. Fur alle x, y, z ∈ K gilt: x(y + z) = xy + xz.

3.2 Vektorraume

Im Folgenden ist ein Ring stets assoziativ mit Einselement und ein Korperist stets kommutativ.

Ein Vektorraum (V,+, ·) wird definiert: Es seien V eine kommutative,addidive Gruppe mit neutralem Element 0. Deren Elemente heißen V ektoren.Des Weiteren sei F ein Korper, dessen Elemente Skalare heißen. Außerdemsei eine Multiplikation F × V → V ; (λ, x) 7−→ λ · x gegeben, die somit jedemSkalar λ ∈ F und jedem Vektor x ∈ V einen Vektor λ · x ∈ V zuordnet.Die Gruppe V wird Vektorraum uber F (oder F-Vektorraum) genannt, wennfur alle Skalare λ, µ ∈ F und allen Vektoren x, y ∈ V die folgenden Gesetzegelten [3]:

1. λ · (x+ y) = λ · x+ λ · y,

11

2. λ · (µ · x) = (λ · µ) · x,

3. (λ+ µ) · x = λ · x+ µ · x,

4. 1 · x = x.

Eine Teilmenge U eines Vektorraumes V uber F heißt Untervektorraumvon V , falls gilt [3]

1. 0 ∈ U ,

2. Aus x, y ∈ U folgt x+ y ∈ U ,

3. Aus λ ∈ F und x ∈ U folgt λ · x ∈ U .

Der Nullraum 0 und der ganze Vektrraum V sind trivialerweise Unter-vektorraume von V. Des Weiteren ist der mengentheoretische Durchschnittuber ein nichtleeres System von Untervektorraumen von V immer wieder einUntervektorraum von V . Mit U(V ) wird das System aller Untervektorraumevon V bezeichnet.Der von einer Teilmenge S ⊆ V erzeugte Untervektorraum 〈S〉 von V wirdals Durchschnitt

〈S〉 := ∩S⊆U∈U(V )U (2)

uber alle Untervektorraume U von V, die die Menge S beinhalten, defi-niert.Sei S ⊆ U eine Teilmenge eines Untervektorraumes U ∈ U(V ). Diese Teil-menge heißt Erzeugendensystem von U , wenn 〈S〉 = U gilt. Somit bestehtder von einer Teilmenge S ⊆ V erzeugte Untervektorraum 〈S〉 aus allen Li-nearkonbinationen von Vektoren aus S:

〈S〉 =

n∑i=1

λi · si;n ∈ N0, λ1, λ2, . . . , λn ∈ F, s1, s2, . . . , sn ∈ S

(3)

Eine Teilmenge S ⊆ V heißt linear abhangig, falls es eine echte Teil-menge R ⊂6= S mit 〈R〉 = 〈S〉 gibt. Ansonsten wird S linear abhangiggenannt. Die leere Menge ∅ ist linear unabhangig. Betrachtet man eine ein-elementige Teilmenge x ⊆ V , ist diese genau dann linear unabhangig, falls

12

x 6= 0 gilt. Eine zweielementige Menge x, y ⊆ V ist somit genau dann linearabhangig, falls x 6= 0 oder falls ein Skalar λ ∈ F mit y = λx existiert.Allgemein gilt: Eine Teilmenge S ⊆ V ist genau dann linear abhangig, fallses eine endliche Anzahl n ≥ 1 verschiedener Vektoren s1, s2, . . . , sn ∈ S undn Skalare λ1, λ2, . . . , λn ∈ F (λ 6= 0) gibt, mit

n∑i=1

λi · si = 0 (4)

Es sei U ∈ U(V ) ein Untervektorraum eines F -Vektorraumes V . Eine Ba-sis von U ist ein linear unabhangiges Erzeugendensystem B ⊆ U . Die Basenvon U sind somit die minimalen Erzeugendensysteme von U . Um zu zeigen,dass die Basen von U genau die maximalen linear unabhangigen Teilmengenvon U sind, nutzt man den Austauschsatz von STEINITZ.Des Weiteren lasst sich jede Basis von U zu einer Basis von V erganzen. Umdiesen Basiserganzungssatz zu beweisen nutzt man das Lemma von ZORN.Damit besitzt jeder Vektorraum eine Basis.

Die Definition der Dimension ist sinnvoll, da alle Basen von U aus gleichvielen Elementen bestehen, das heißt, sie sind gleichmachtig. Dabei beschreibtdie Kardinalzahl einer Basis des F -Vektorraumes V die Dimension von V .Diese wird mit dimV bezeichnet.

Seien V und W zwei Vektorraume uber demselben Korper F . Wir be-trachten eine Abbildung ϕ : V −→ W . Diese Abbildung heißt linear, wennsie ein Homomorphismus der additiven Gruppe von V ist. Somit muss gelten:

ϕ(x+ y) = ϕ(x) + ϕ(y) (5)

ϕ(λ · x) = λ · ϕ(x) (6)

(∀x, y ∈ V und λ ∈ F )

Als Kern von ϕ wird der folgende Untervektorraum von V bezeichnet:

Ker(ϕ) := x ∈ V ;ϕ(x) = 0 (7)

13

Das Bild von ϕ wird der folgende Untervektorraum von W bezeichnet:

ϕ(V ) := ϕ(x);x ∈ V (8)

Es gilt der Dimensionssatz:

dimV = dimKer(ϕ) + dimϕ(V ) (9)

Betrachtet man zwei F -Vektorraume der gleichen Dimension, sind diesestets isomorph. Falls wir einen n-dimensionalen Vektorraum V betrachten,so konnen wir diesen mit dem Vektorraum Vn(F ) = F n aller n-Tupel x =x1, x2, . . . , xn) identifizieren. Als Grundlage kann man die Standard-BasisEn := (en1 , e

nn, . . . , e

nn) nehmen. Diese Standard-Einheitsvektoren eni werden

fur i = 1, 2, . . . , nmit Hilfe des KRONECKER-Symbols eni := (δi,1, δi,2, . . . , δi,n)definiert.

Nun mochten wir die Begriffe Monomorphismus, Epimorphismus (Isomor-phismus), Endomorphismus und Automorphismus naher beleuchten. Vorhersei gesagt, dass der Homomorphismus eine strukturerhaltende Abbildung ist.Nun betrachten wir eine lineare Abbildung ϕ : V −→ W . Diese ist genaudann ein Monomorphismus ( eine injektive lineare Abbildung), wenn derKern von ϕ nur aus dem Nullvektor V besteht. Dual dazu betrachten wirden Epimorphismus, d. h. einen surjektiven Homomorphismus. Eine linea-re Abbildung eines Vektorraumes in sich heißt Endomorphismus. Und einbijektiver Endomorphis wird Automorphismus genannt.

Bei der Betrachtung von Determinanten wird der Umgang von Deter-minanten quadratischer Matrizen als vertraut angenommen. Die Determi-nantenabbildung hat die Form:

det : Mn×n(F ) −→ F ; Φ 7−→ detΦ (10)

Die Abbildung ist multiplikativ, d.h.: fur alle Φ,Ψ ∈Mn×n(F ) gilt det(Φ ·Ψ) = detΦ ·detΨ. In diesem Sinne kann man die Determantenabbildung auchals Abbildung von End(Vn(F )) auf F interpretieren. Somit definieren wir furϕ ∈ End(Vn(F )) die Determinante von ϕ unabhangig ihrer Basis von Vn(F ),

14

als die Determinante einer ihrer Abbildungsmatrizen Φ : detϕ := detΦ. VonNull verschieden ist die Determinante detϕ, falls es eine lineare Bijektion ist.

Die folgenden Determinanteneigenschaften sind nutzlich bei der Berechnung[3]:

1. Das Vertauschen zweier Zeilen der zweier Spalten der Matrix bewirkteinen Vorzeichenwechsel der Determinante.

2. Nach Multiplikation einer Zeile oder einer Spalte mit einem Skalar λ ∈F ver-λ-facht sich der Wert der Determinante.

3. Die Addition eines skalaren Vielfachen einer Zeile bzw. einer Spalte zuzeiner anderen Zeile bzw. Spalte andert die Determinante nicht.

3.3 Polynome

Sei F ein Korper und sei F [N0] der F -Vektorraum aller Folgen (ai; i ∈ N0).Zunachst definierten wir das Monom

zi := (ϕi,0, ϕi,1, ϕi,2. . . .). (11)

Das beschreibt diejenige Folge aus F [z], die an der Positionsnummeri ∈ No die Komponente ϕi,i = 1 und an allen anderen Positionen die 0 be-sitzt. Die Menge zi; i ∈ N0 all dieser Monome ist die Standard-Basis desVektorraumes F [z]. Des Weiteren heißt fur jede von der Nullfolge verschie-dene Folge a = (ai; i ∈ N0) ∈ F [z] derjenige Index n ∈ N0, fur den an 6= 0und ai = 0 ∀i > n gilt, der Grad von dega := n. [3]

Somit ist es moglich jede Folge von a = (ai; i ∈ N0) ∈ F [z]vom Graddega = n eindeutig als Linearkombination

a =n∑i=0

ai · zi (12)

der Monome der Standard-Basis von F [z] zu schreiben.

15

Polynome werden als Liniearkombinationen der Monome der Standard-Basis geschrieben und bestehen aus Vektoren aus F [z]. Bei konstanten Poly-nomen a·z0 = (a, 0, 0, . . .) schreibt man a := a·z0 und setzt das Korperelementa ∈ F ein. Polynome vom Grad 1 nennt man lineare Polynome undschreibt statt z1 verkurzt z.

Monome lassen sich multiplizieren, indem man fur zwei ganze Zahleni, j ≥ 0 das Produkt der Monome zi und zj wiefolgt bildet:

zi · zj := zi+j. (13)

Die Multiplikation von zwei Polynomen a(z) =∑n

i=0 ai · zi und b(z) =∑mj=0 bj · zj ist ihr Produkt

a(z) · b(z) :=n∑i=o

m∑j=0

ai · bj · zi+j. (14)

Bezuglich der Addition und der Multiplikation von Polynomen bildetF [z] einen Ring (Polynomring uber F). Des weiteren ist F [z] bezuglich derVektorraum- und Ringstruktur eine F-Algebra. Betrachtet man je zwei Po-lynome a(z), b(z) ∈ F [z] gilt fur den Grad die folgende Formel:

dega(z) · b(z) = dega(z) + degb(z). (15)

Somit gilt fur je zwei Polynome a(z), b(z), die vom Nullpolynom 0 ver-schieden sind immer a(z) · b(z) 6= 0.

Sei x ein Ringelement, welches wir in das Polynom einsetzen. Fur jedesx ∈ R ist die Abbildung definiert:

Φx : F [z] −→ R; a(z) =n∑i=0

ai · zi 7→ [a(z)]z=x :=n∑i=0

ai · xi (16)

Diese Abbildung ordnet jedem Polynom den Wert der PolynomfunktionR −→ R;x 7→ a(x) an der Stelle x ∈ R zu. Genannt wird dieser Ring-Homomorphismus Einsetzungshomomorphismus. x ∈ R wird Nullstelle vona(z) genannt, falls die zu a(z) gehorige Polynomfunktion an der Stelle x denWert 0 annimmt (verschwindet): a [z]z=x = 0.

16

4 Grundlagen aus der Wahrscheinlichkeitsrech-

nung

Im Folgenden werden die Begriffe des Ereignisses und der Ereignisalgebraeingefuhrt. Daraus wird auf die Mengenalgebra ubergeleitet und das Kol-mogoroffsche Axiomensystem der Wahrscheinlichkeitsrechnung aufgefuhrt.[Henze, S.5]

Es sei ein Versuch gegeben, dessen moglichen Ausgange vom Zufall abhangen.Dabei werden nur einfache mit endlichen, abzahlbar undendlichen oder uberabzahlbarvielen Versuchsausgangen betrachtet. Solche Elementarereignissen ordnet manein Element ω einer (Elementar-)Ereignismenge Ω zu. Jede Teilmenge A die-ser Ereignismenge Ω(A ⊂ Ω) heißt Ereignis. Somit besteht A aus der Ge-samtheit der Elementarereignissen Ω, die in A liegen [4]:

A = ω | ω ∈ A (17)

Aus den Ereignissen A1, A2, . . . , Ai, . . .wird ein Ereignissystem E gebil-det. Dies ist eine Teilmenge der Potenzmenge von Ω. [4]

Im nachstehenden werden Vereinigung, Durchschnitt und Differenz von Er-eignissen aufgezeigt.

1. Die Vereinigung Ai ∪ Akist das Ereignis, welches aus allen Elementarereignissen, die in Ai und/ oder Ak vorkommen, besteht.

2. Der Durchschnitt Ai ∩ Ak = AiAkist das Ereignis, welches aus allen Elementarereignissen, die in Ai undAk vorkommen, besteht.

3. Die Differenz Ai - Akist das Ereignis, welches aus allen Elementarereignissen, die zu Ai, abernicht zu Ak vorkommen, besteht.

Das sogennante leere Ereignis oder unmogliche Ereignis enthalt keinElementarereignis und wird mit ∅ bezeichnet.

17

Die Ereignismenge Ω wird als sicheres Ereignis bezeichnet.Im Folgenden werden die Begriffe Ereignis und Menge als synonym ange-sehen, da der Satz von STONE (Jede Ereignisalgebra lasst sich einer Men-genalgebra isomorph zuordnen) gilt. [4]Gegeben sei nun ein System B von Teilmengen der Menge (Basismenge) Ω.B = BΩ heißt eine σ - Algebra uber Ω, wenn

1. Ω ∈ B,

2. A ∈ B⇒ Ω− A = A ∈ B,

3. Ai∞1 , Ai ∈ B ∀i⇒ ∪∞i=1Ai ∈ B.

Jetzt fuhren wir den Begriff der Wahrscheinlichkeit mit Hilfe des Kol-mogoroffschen Axiomensystem ein.B sei eine σ - Algebra uber Ω. Des Weiteren sei fur alle A∈B eine reelle ZahlP(A) erklart. Dies ist die Wahrtscheinlichkeit des Ereignisses A (oder dasWahrscheinlichkeitsmaß von A), welches die folgenden Bedingungen erfullt:

1. P (A) ≥ 0

2. P (Ω) = 1

3. Ai ∈ B ∀i;AiAk = ∅, i 6= k;A = ∪iAi ⇒ P (A) =∑

i P (Ai)(σ− Additi-vitat von P)

Somit konnen wir einen Wahrscheinlichkeitsraum als Tripel (Ω,B, P ) be-schreiben, wobei Ω die Basismenge, B die σ - Algebra und P das Wahr-scheinlichkeitsmaß ist. Ein endlicher Wahrscheinlichkeitsraum liegt vor, fallsdie Anzahl der Ereignisse von B endlich sind.Des Weiteren wird eine abzahlbare Menge von Ereignissen Ai | Ai ∈ B einvollstandiges Ereignissystem genannt, falls

AiAk = ∅, i 6= k (18)

Somit schließen sich die Ereignisse voneinander aus und fur das EreignisA = ∪iAi =

∑iAi gilt

18

P (A) = 1. (19)

Bei praktischen Aufgaben treten primar bedingte Wahrscheinlichkeitenauf. Die bedingte Wahrscheinlichkeit fur das Ereignis A ∈ B unter der Bedi-nung, dass das Ereignis B ∈ B (mit P(B) ¿ 0) eintritt, wird wiefolgt definiert:

P (A|B) = P (AB)/P (B). (20)

Nun betrachten wir die vollstandige Wahrscheinlichkeit. Sei ein vollstandigesEreignissystem Ai mit

AiAk = ∅(i 6= k);∪iAi = Ω;P (Ai) > 0∀i (21)

gegeben, so gilt fur jedes Ereignis B ∈ B

B = BΩ = ∪iBAi. (22)

Somit tritt B immer mit einem der untereinander unvereinbaren Ereig-nisse Ai ein und damit gilt der Satz der vollstandigen Wahrscheinlichkeit:

P (B) =∑i

P (BAi) =∑i

P (B|Ai)P (Ai). (23)

Nun werden die Begriffe Zufallsvariable, Verteilungs- und Dichtefunktioneingefuhrt.Sei Ω eine Ereignismenge und ω ihre Elementarereignisse. Weiter sei B eineσ - Algebra uber Ω. Eine reelle Funktion ξ = ϕ(ω) der Elementarereignisseheißt Zufallsvariable, falls fur jede Borel-meßbare Menge Aξ die Menge derUrbildereignisse Aω = ω|ϕ(ω) ∈ Aξ zu B gehort. Wobei Aξ eine Mengevon Werten ξ ist. Somit wird definiert:

P (ξ ∈ Aξ) = P (Aω). (24)

Bei der Durchfuhrung eines Experiments mit einem bestimmten Ausgangω erhalt man die Realisierung

19

x = ϕ(ω) (25)

der Zufallsvariable ξ.Damit lasst sich die Verteilungsfunktion wiefolgt definieren: Sei ξ =

ϕ(ω) eine Zufallsvariable auf (Ω,B, P ); dann heißt die Funktion

F (x) = P (ξ < x) = P (ω|ϕ(ω) < x) (26)

die Verteilungsfunktion der Zufallsvariablen ξ. Die Funktion ist mono-ton, nichtfallend und von links stetig. Sie besitzt hochstens abzahlbar vieleSprungstellen. Es gelten

F (−∞) = 0, F (∞) = 1. (27)

Falls die Verteilungsfunktion F(x) einer Zufallsvariablen ξ differenzierbarist, so ist die Ableitung

f(x) =d

dxF (x) (28)

die Wahrscheinlichkeitsdichte der Zufallsvariablen ξ. Die Ableitung kannals Wahrscheinlichkeit interpretiert werden, dass die Zufallsvariable ξ im in-finitesimalen Intervall [x, x+dx) liegt.

Man definiert den Erwartungswert der Zufallsvariablen ξ durch

E(ξ) =

∫ −∞∞

xdF (x) =

∫ −∞∞

xf(x)dx (29)

Der Erwartungswert existiert genau dann, wenn gilt:

∫ −∞∞|x|dF (x) <∞ (30)

Die Varianz (bzw. Streuung) wird definiert durch

D2(ξ) = E(ξ − E(ξ))2 =

∫ −∞∞

(x− E(ξ))2dF (x) = E(ξ2)− (E(ξ))2. (31)

20

5 Codierungstheorie

5.1 Einleitung

Nicht nur heute, sondern auch fruher wurden Informationen codiert. Schondie alten Agypter codierten 3000 v. Chr. Texte, um sie vor anderen geheimzu halten. Die Caesar-Verschlusselungsmethode codierte ihre Texte durchWeiterrucken des Alphabetes fur den gewunschten Text. Ab 1949 endete diePhase der Geheimhaltung der Verschlusselungstechniken durch Claude Shan-nons veroffentlichen Artikel Communication Theory of Secrecy Systems. Abdiesem Zeitpunkt wurde die Verschlusselungstechnik oder Kryptographie furdie Wissenschaft geoffnet und erhielt eine mathematische Pragung. Die Co-dierung einer Information in der Technik lauft nach ahnlichen Schemata ab,wie die Verschlusselung von Informationen. Man kann sagen, die Codierungs-theorie ging zu großen Teilen aus der Kryptographie hervor, denn diese machtauch nichts anderes, als eine gegebene Information in eine andere umzuwan-deln, mit dem Unterschied, dass in der Elektronik vor allem die Codes aus 0und 1 oder Spannung oder nicht Spannung bestehen. Die Codierungstheorieberuht darauf, dass Texte, Zeichen oder andere Informationen in ein elektro-nisches oder anderes Datentransfernetz, dem so genannten Kanal ubersetztwerden mussen, um von einem Empfanger wieder ruckubersetzt werden zukonnen.

Quelle −→ Kanal −→ Empfanger

Die Ubertragung einer Information in einen Kanal erfolgt mit Hilfe einesCodierers. Jeder Codierer benotigt einen zugrunde liegenden Code, um dieInformation zu codieren. Doch was bedeutet ein Code im mathematischenSinne? Wie kann ein Text effizient codiert werden und wie funktioniereneinfache Kanalcodierer? Mit diesen Themen beschaftigen sich die nachstenSeiten.

6 Code - Ein- und Abgrenzung

6.1 Definition Code

Ein Code uber den Alphabeten A und B ist eine eindeutige Abbildungf : A → B. Sie ordnet eindeutig Worter aus dem Alphabet A Worter aus

21

dem Alphabet B zu. Ein Code ist entzifferbar, wenn es eine Umkehrabbil-dung f−1 : B → A gibt, die jedem Codewort aus dem Alphabet B ein Wortaus dem Alphabet A zuordnet.[21]

6.2 Redundanz

Redundanz bezeichnet einen Zustand von Uberschneidung oder Uberfluss.Ein Code kann so funktionieren, dass er Informationen in uberflussige Sym-bole codiert. Außerdem fuhrt jede vorhersagbare Stelle in einem Code zuRedundanz. Uberflussige oder vorhersagbare Zeichen sollen moglichst nichtoder mit geringen Aufwand codiert werden, um moglichst effizient zu arbei-ten. Zum Beispiel kommt im Deutschen der Buchstabe q nicht gefolgt voneinem u aus. D.h. man konnte diesen Buchstaben ohne weiteres entfernenund konnte trotzdem das Wort eindeutig identifizieren. Redundanz hilft vorDatenverlust und hilft bei der Fehlererkennung. Oft werden aber bei derCodierung weitere Zeichen, so genannte redundante Stellen hinzugefugt, umFehler bei der Ubertragung festzustellen und zu berichtigen. Codes, die Feh-ler erkennen, werden error detecting codes und Codes, die Fehler berichtigenkonnen, werden error correcting codes genannt. Diese Codes liefern dement-sprechend eine Sicherung gegen Fehler in der Ubertragung und damit aucheiner Sicherung gegen Informationsverfalschung.

6.3 Wichtige Codes

Die wichtigsten Codes, die in der Technik genutzt werden, sind zum einender ASCII, der alle Buchstaben, Satzzeichen und weitere Symbole des engli-schen Alphabetes darstellen kann. Dieser wird jeweils aus 7Bit (Zeichen) proSymbol aufgestellt. Heute ist dieser durch den Uni-Code erweitert worden,welcher alle Zeichensysteme auf dem Computer darstellen kann. Zunachstwurde dafur ein 17Bit-Code eingefuhrt, welcher spater durch weitere Ein-teilung in 17 Bereiche erweitert wurde. In der Speicherung von Buchcodeskommt der ISBN-Code zur Anwendung. Der ISSN-Code dient der eindeutigenIdentifizierung von Zeitschriften und Magazinen. In der Luftfahrt kommenaußerdem noch die IATA-Codes zum Einsatz. Es gibt noch eine große Anzahlweiterer Codes, die fur verschiedene Anwendungen genutzt werden.

22

7 Effizienz eines Codierers

Die Schnelligkeit einer Ubertragung einer Information beruht zu einem großenTeil auf der Schnelligkeit der Signalubertragung im Kanal. Damit dieser sowenig wie moglich Informationen zu ubermitteln hat, muss des Codierer eineInformation auf kurzeste Weise codieren. Der Codierer ist eine deterministi-sche Vorrichtung, die eine Nachricht in eine andere Nachricht umwandelt.Die neue Nachricht wird meistens in anderen Symbolen dargestellt. Die Um-formungen sind reversibel( [13, S.29f]).Ein reversibler Codierer formt Nachrichten in eineindeutiger Weise in ver-schlusselte Nachrichten um. Die verschlusselte Nachricht enthalt den gleichenInformationswert, wie die Ausgangsnachricht.Wenn ein Symbol ubertragen wird, so muss die Ubertragungsgeschwindigkeitnicht fur jedes Symbol gleich schnell sein, denn nicht jedes Symbol wird gleichoft benutzt. Wir denken dabei an das Q im Deutschen im Vergleich zum N.Wurde man jedes Symbol einzeln ubertragen, so ware die Signalubertragungviel zu langsam. Der Codierer hat die Aufgabe, den Text so umzuformen, dasser weniger Symbole fur die eineindeutige Umwandlung benotigt. Es stellt sichdie Frage, wie das erreicht werden kann.Die Uberlegungen sollen an einem Beispiel erlautert werden:

Beispiel:Folgender Text soll gunstig codiert werden:ABAAABAAAAAAAA

Fur einen Text tritt der Buchstabe A mit einer Wahrscheinlichkeit von 0,9und der Buchstabe B mit einer Wahrscheinlichkeit von 0,1 auf. Der Codie-rer ubertragt 60 Zeichen in einer Minute. Ziel der Uberlegung ist es, mitso wenig wie moglich Symbolen den Text zu codieren, so dass eine schnelleUbertragung gewahrleistet werden kann.

Der einfachste Codierer ubertragt jeden einzelnen Buchstaben in eine Zif-fer:

Buchstaben Wahrscheinlichkeit Ziffern Gewichtete Anzahlder Ziffern

A 0,9 0 0,9B 0,1 1 0,1

23

Die Summe der gewichteten Anzahlbetragt 1 Ziffer pro Buchstabe und 60Ziffern pro Minute. Der Text wird folgendermaßen codiert:A B A A A B A A A A A A A A0 1 0 0 0 1 0 0 0 0 0 0 0 0

Fur die Ubertragung werden 14 Ziffern benotigt.Eine Verbesserung der Ubertragung kann dadurch erhalten werden, indemman jeweils zwei Buchstaben zusammenfugt und fur diese die Wahrschein-lichkeit bestimmt:

Buchstaben Wahrscheinlichkeit Ziffern Gewichtete Anzahlder Ziffern

AA 0,81 0 0,81AB 0,09 10 0,18BA 0,09 110 0,27BB 0,01 111 0,03

Die Summe der gewichteten Anzahl betragt 1,29. D.h. die mittlere Langeeines Ziffernblockes betragt 1,29. Der Codierer sendet 0,645 Ziffern pro Buch-stabe. Fur den Text ergibt sich:

AB AA AB AA AA AA AA10 0 10 0 0 0 0

Fur die Ubertragung werden 9 Ziffern benotig. Nach dieser Methode kannsolange fortgefahren werden, bis ein Quellcodierer einen Text so mit Ziffernreduziert hat, dass er in einer bestimmten Zeiteinheit gleich oder wenigerSymbole erzeugt, wie der Kanal in der gleichen Zeit versenden kann. DasCodierungstheorem erklart diesen Zusammenhang wie folgt:

CodierungstheoremGegeben sind ein Kanal und eine Nachrichtenquelle, die mit einer kleinerenGeschwindigkeit als die Kanalkapazitat Informationen erzeugt. Man kannimmer einen Codierer finden, der die Nachrichtenquelle in geeigneter Weisecodiert, so dass er durch den Kanal ubertragen werden kann.Man findet also immer einen Codierer, mit denen man einen Quelltext durcheinen Kanal versenden kann.Zusammengefasst bedeutet dies, dass je haufiger ein Zeichen versendet wird,desto geringer sollte der Aufwand sein dieses zu verarbeiten und je seltener

24

ein Zeichen auftritt, desto großer kann der Aufwand sein dieses zu verar-beiten, dadurch wird erreicht, dass der Kanal effizient mit einer geringenAnzahl von Symbolen, aber gleichem Informationsgehalt effektiv die Infor-mation ubertragen kann.

8 Vorstellung einiger Codes

Wie man aus der Definition fur einen Code erkennt, handelt es sich bei derCodierung um eine Abbildung f : A → B.Wie wir im letzten Kapitel ge-sehen haben, wird bei der Codierung einer Information in der Quelle einemoglichst redundanzarme Darstellung angestrebt. Fur die Kanalcodierungwerden jedoch fur viele Codes redundante Stellen hinzugefugt, um die imzweiten Shannonschen Codierungstheorem besagte Restfehlerwahrscheinlich-keit klein zu halten. Das zweite Shannonsche Codierungstheorem besagt, dass

”bei der Ubertragung uber einen gestorten Kanal [...] die zu ubertragende In-

formation mit einer bestimmten Wahrscheinlichkeit verfalscht [wird]. Durchdie storungsgeschutzte [C]odierung konnen die dabei entstandenen Fehlernicht restlos beseitigt werden, so dass die Information nach verlassen derDe[c]odierungseinrichtung noch mit einer gewissen Restfehlerwahrscheinlich-keit [...] behaftet ist.” [7, Seite 125f]In diesem Kapitel sollen einige Kanalcodierungen vorgestellt werden. Speziellsoll es darum gehen, wie Quellcodes in Kanalcodes codiert werden und wiederen Fehlerkorrektur ablauft.

8.1 Einordnung der Kanalcodes

Ein Ausschnitt aus der Vielfalt:

Algebraische Codes besitzen verschiedene algebraische Strukturen und ermoglichen,wie wir kurz in Kapitel 2 gesehen haben, die Moglichkeit des verkurzten Ab-speicherns von Daten. Eingeteilt werden die algebraischen Kanalcodes in diebinaren oder nichtbinaren Blockcodes und in die binaren, blockfreien Codes.Ein Code ist binar, wenn er durch zwei Symbole, z.B. 0 und 1 dargestelltwerden kann. Blockcodes bestehen aus Kanalcodewortern eines AlphabetesA mit fester Lange. Diese Codes werden in die linearen und nichtlinearenCodes unterteilt. Wichtiger sind die linearen Codes in der Informationstheo-

25

rie. Besonders wichtig sind in diesem Fall die Hamming-Codes und die zy-klischen Codes. Hamming-Codes werden vor allem fur die Einfachfehlerkor-rektur durch Rekonstruktion verwendet. Zyklische Codes werden auch zurEinfachfehlerkorrektur genutzt, sie eignen sich aber auch zur Erkennung undKorrektur von Bundelfehlern. Sie sind besonders einfach aufgebaut und ar-beiten effizient. Die blockfreien Codes spielen vor allem fur den Faltungscodeeine große Rolle. Durch Einbau einer zusatzlichen Redundanz bieten Fal-tungscodes einen hoheren Schutz gegen Ubertragungs- und Speicherfehlern,außerdem wird der Informationsgehalt der einzelnen Nutzdatenstellen ubermehrere Stellen des Codewortes verteilt, wodurch noch großere Sicherheitgarantiert werden kann. Die Einordnung der Codes ist nicht vollstandig, be-dingt durch die große Vielfalt der Codes.

8.2 Fehlerkorrektur mit Hilfe des Hamming-Abstandes

Mochte man einen fehlerhaften Code korrigieren, so muss zunachst eine Feh-lererkennung durchgefuhrt werden. Die Fehlerkorrektur wird mit zwei Metho-den angewendet. Zum einen durch Wiederholung (ARQ) und anschließenderEntscheidungsruckmeldung und zum weiteren durch Rekonstruktion(FEC).Die Rekonstruktion eines Codes kann nach drei Methoden durchgefuhrt wer-den. Zum einen mit der Maximum-Likelihood-Methode, mit Prufvektor odermit begrenzter Mindestdistanz.Bei der Fehlerkorrektur mit Wiederholung schickt der Empfanger eines Si-gnals das Ergebnis an den Sender zuruck. Dieser pruft das Ergebnis undschickt es bei Fehlern noch einmal.

26

[7, Seite 127]Bei der Fehlerkorrektur durch Rekonstruktion werden die Fehler vom Empfangererkannt, sowie beseitigt.Bei der Decodierung mit Hilfe der Maximum-Likelihood-Methode (Ahnlich-keitsdekodierung) wird zu einem empfangenen Vektor x zu einem Vektor c’decodiert, der mit der großten Wahrscheinlichkeit zum tatsachlich versand-ten Codevektor c identisch ist ( [22]) Der Vektor, bei dem die wenigsten Stel-len korrigiert werden mussen, werden als Wahrscheinlichste angenommen,d.h. der kleinste Hamming-Abstand besteht zwischen empfangenem und de-codiertem Vektor. Dieser Fall wird auch als des nachstgelegenen Nachbarn(englisch: nearest neighbor decoding) bezeichnet.

Bei der Methode mit Prufvektor wird ein empfangenes Signal gepruft, obdiese ein Codewort sind oder nicht. Eine richtige oder falsche Rekonstruk-tion erfolgt uber den Prufvektor. Damit das Verfahren funktioniert, mussenalle moglichen Prufvektoren bekannt sein.Bei der Rekonstruktion mit begrenzter Mindestdistanz wird ein Signal nurkorrigiert, wenn sich die empfangene Folge innerhalb einer Korrekturkugelbefindet.

8.2.1 Der Hamming-Abstand

Der Hamming-Abstand wurde nach dem Mathematiker Richard Wesley Ham-ming (1915-1998) benannt. Der Abstand zweier binarer Daten mit festerLange kann dadurch ermittelt werden, indem man beide fur jedes Bit ver-gleicht und jeweils die Stelle ermittelt, die ungleich ist. Kurz ausgedrucktbedeutet dies:Sei Σ ein endliches Alphabet x = (x1, ..., xn) und y = (y1, ..., yn) aus Σn

gleichlange Worter uber diesem Alphabet. Der Hamming-Abstand zwischenx und y ist definiert als∆(x, y) :=

∑xi 6=yi

1 mit i = 1, ..., n

Das folgende Beispiel soll zeigen, wie der Hamming-Abstand genutzt wird.

Beispiel 1:Ein Kanalcode A besteht aus 4 Wortern a1 = (0011), a2 = (1010), (a3 =(1100), a4 = (1101) der Lange n = 4. Zu diesen gehort ein Quellencode Bmit b1 = (010), b2 = (101), (b3 = (100) und b4 = (011) der Lange l = 3. Der

27

Kanalcodierer transformiert dabei jeweils die Quellecodeworter in ein Kanal-codewort.Alphabet A = (0011), (1010), (1100), (1101)Alphabet B = (010), (101), (100), (011)Empfangt der Kanalcodierer das Signal a = (1010), so kann eindeutig dasElement b = (101) aus dem Alphabet B zugeordnet werden. Empfangt esdagegen das Signal a∗ = (0001), so kann kein Wort aus dem Alphabet Bzugeordnet werden. Es leitet eine Korrekturmaßnahme ein mit Hilfe desHamming-Abstands:∆(a1, a

∗) = 1∆(a2, a

∗) = 3∆(a3, a

∗) = 3∆(a4, a

∗) = 2Der Kanalcodierer sucht das Wort mit den kleinsten Hamming-Abstand undordnet dem fehlerhaften Wort a∗ das Wort a1 zu und codiert es in das Wortb1 um.

Beispiel Ende

Das heißt, es interessiert bezuglich der Fehlererkennbarkeit und der -korrekturvor allem die minimale Hamming-Distanz ∆min. Mochte man erreichen, dassein Wort ax immer durch ein verfalschtes Wort ex erkennt wird, so darf derHamming-Abstand niemals großer als ∆min werden, da sonst ex nicht erkanntwird oder sogar in ein weiteres Wort des Alphabetes A transformiert wird.Soll der Code alle Verfalschungen erkennen konnen, so muss fur ∆min gelten:∆min = fe + 1 mit fe...Anzahl der von Null verschiedenen Fehlerstellen

Soll außerdem der Code rekonstruiert werden konnen, so muss fur ∆min gel-ten:∆min = 2fk + 1 mit fk...Anzahl der verfalschten Stellen

Ist ∆min geradzahlig, so gibt es eine Folge, die sich genau in der Mitte zweierKanalworter ax und aj befindet. Es gilt dann fur eine korrekte Rekonstruk-tion fur ∆min > 2fk + 1.

28

8.3 Lineare Codes

8.3.1 Definition

Eine besonders wichtige Rolle fur die Kanalcodes stellen die linearen Codesdar. Betrachtet wird dabei das Schema der Ubertragung eines Quellcodewor-tes der Lange l aus dem Alphabet A∗ in eine Kanalcodewort der Lange n desAlphabetes A und der weiteren Ubertragung in ein Empfangsfolge der Langel des Alphabetes A∗:

Quellecode(Lange l) → Kanalcode(Lange n) → Empfangsfolge(Lange l)

Die linearen Blockcodes werden als”endlichdimensionale Vektorraume uber

einen endlichen Korper V”betrachtet. Ein Code ist genau dann ein linearerCode, falls er ein Untervektorraum C von V ist. Das heißt, die Summe zweierCodeworter aus C bildet wieder ein Codewort aus C, d.h. es gilt:∀x, y ∈ C : x+ y ∈ CFur die linearen Codes werden nur Operationen verwendet, deren algebrai-sche Struktur eine Gruppe bildet.Die Worter des Quellcodes sind Elemente aus der Gruppe (A,+)l und dieKanalcodeworter sind Elemente aus der Gruppe (A,+)l+k. Das heißt, dieWorter des Kanalcodes haben die Lange n = l + k. Erfullen die Codes dieGruppenaxiome, dann bezeichnet man die Linearcodes als Gruppencodes.Zur vollstandigen Beschreibung des Untervektorraumes C genugt es die Ba-sisvektoren zu kennen, um diesen vollstandig zu beschreiben. Die Basis kannzum Beispiel durch die Einheitsvektoren ei mit i = 1 − n angegeben wer-den oder durch andere linear unabhangige Vektoren.

”Alle in A enthaltenen

Vektoren werden durch die [...] Basisvektoren und samtliche Linearkombina-tionen aus diesen gebildet.” [7, Seite 144]Fur die weitere Betrachtung wird fur die Vektorverknupfungsoperation diemodulo-2-Addition verwendet.

Beispiel 1:Gegeben ist ein 7stelliges Codealphabet A mit den Kanalcodewortern:a1 = (1000111) a2 = (0100110) a3 = (0010011) a4 = (0001101)Weitere Kanalcodeworter lassen sich durch Linearkombination aus den Ba-sisvektoren bilden: a4 = a1 + a2 = (1100001) a5 = a1 + a3 = (1010100)a6 = a1 + a4 = (1001010)

29

Beispiel Ende

8.3.2 Die Generatormatrix

Mochte man effektiver sein, so stellt man die Linearcodes als Matrizen dar.Man fasst die gebildeten Basisvektoren in einer Matrix zusammen und erhaltdie so genannte Erzeugermatrix oder Generatormatrix G:

G =

g11 · · · g1n...

. . ....

gl1 · · · gln

Eine einfache Methode die Zeilen linear unabhangig anzugeben ist, in dieersten l Spalten die Einheitsmatrix Elxl-Matrix zu schreiben. Dann folgt dar-aus, dass die Zeilen linear unabhangig sind.

G =

1 0 0 · · · 0 g1,l+1 g1,l+2 · · · g1,n

0 1 0 · · · 0 g2,l+1 g2,l+2 · · · g2,n

· · · · · · · · · · · · · · · · · · · · · · · · · · ·0 0 0 · · · 1 gl,l+1 gl,l+2 · · · gl,n

Der Rang der Matrix G ist l. Diese Schreibweise gewahrleistet, dass der er-haltene Code systematisch ist, das heißt, dass die ersten Stellen des Ka-nalcodewortes identisch zum Quellcode sind und diese durch Kontrollstellenerweitert sind.

Beispiel 2:Setzt man die Vektoren aus Beispiel 1 zeilenweise zu der Generatormatrix Gzusammen, so erhalt man:

G =

1 0 0 0 1 1 10 1 0 0 1 1 00 0 1 0 0 1 10 0 0 1 1 0 1

mit C =

1 1 11 1 00 1 11 0 1

Beispiel Ende

Es bleibt die Frage offen, wie man mit Hilfe der Generatormatrix G undden Quellcodewortern a∗j die Kanalcodeworter ai erzeugt. Man erhalt dieKanalcodeworter ai mit:

ai = a∗i ·G oder ausfuhrlich geschrieben(ui1, ui2, ..., uin) = (u∗i1, u

∗i2, ..., u

∗in) ·G

30

8.3.3 Die Kontrollmatrix

Genauso wichtig wie die Generatormatrix G ist die Kontrollmatrix H, dennmit großer Lange von l wird der Aufwand der Anwendung von G immergroßer. Man bestimmt aus diesem Grund aus G die Kontrollmatrix H. H bil-det zu G einen Orthogonalraum, d.h. jeder Vektor in H ist zu jedem Vektorin G orthogonal.H = (−)CTE(n−l)×(n−l)

Fur binare Linearcodes entfallt das Minuszeichen. Der Rang der Matrix Hist n-l.Außerdem gilt wegen der Orthogonalitatsbedingung: G ·HT = 0Die Matrix H liefert eine Vorschrift zur Bildung der Kontrollstellen der Ka-nalcodeworter. Fur die Berechnung der Kontrollelemente gilt:ui,l+j = u∗i,l · g1,j ⊕ u∗i,2 · g2,j ⊕ ...⊕ u∗i,l · gl,j mit j = 1, 2, ...kDaraus ergibt sich fur systematische Codes fur das Kanalcodewort eine Schreib-weise: ai = (u∗i,1u

∗i,2...u

∗i,lui,l+1ui,l+2...ui,l+k)

Fur binare Linearcodes ergibt sich ui,l+j aus der”Summe der bitweisen

Modulo-2-Addition aus denjenigen Stellen in dem zu [c]odierenden Quel-len[c]odewort a∗i , an deren Position in der j-ten Zeile der Kontrollmatrix Heine 1 steht.” [7, Seite 149]

Beispiel 3:Erzeugung der Kontrollmatrix H aus G:

H =

1 1 0 1 1 0 01 1 1 0 0 1 01 0 1 1 0 0 1

Die Kontrollmatrix H wird nicht nur zur Fehlererkennung von der Ubertragungvom Quellcode zum Kanalcodewort genutzt, sondern auch fur die Uber-tragungskontrolle vom Kanal zum Empfanger. Gilt fur die Gleichung s =H · bT = 0 mit bT als Kanalcodewort, so ist b eine Kanalcodewort. s wird alsSyndrom von bT bezeichnet.

Beispiel 4:b1 = (1110001) b2 = (1100001) so ergibt sich fur die Syndrome:s1 = (011) s2 = (000)

Beispiel Ende

31

Mit diesen erhaltenen Vektoren s kann nun noch Fehlerkorrektur betriebenwerden. Lineare Codes werden zum Beispiel fur die ISBN-Codes verwendet,sie spielen außerdem in der Codierungstheorie fur weitere Anwendungen zumBeispiel den Hamming-Codes oder den zyklischen Codes eine weitere wesent-liche Rolle.

8.4 Zyklische Codes

Eine weitere wichtige Gruppe der linearen Blockcodes stellen die zyklischenCodes dar. Sie werden vor allem in der digitalen Signalverarbeitung undin der Nachrichtentechnik eingesetzt. Durch die einfache Handhabung derFehlererkennung und -korrektur haben diese vor allem fur die BCH- undRS-Codes eine große Bedeutung erlangt.

8.4.1 Definition

Zyklisch bedeutet fur diese Art von Code, dass fur jedes Kanalcodewortai = (ui,n−1ui,n−2...ui,1ui,0) die zyklische Verschiebung der Elemente einesCodewortes wieder ein gultiges Codewort aj = (ui,n−2ui,n−1...ui,1ui,0ui,n−1)ergibt.

Beispiel 1:ai = (01100101)aj = (11001010) ist auch ein Codewort fur einen zyklischen Code

Beispiel Ende

Außerdem gelten fur die zyklischen Codes die Korperaxiome.

8.4.2 Darstellung als Polynome

Zyklische Codes werden zweckmaßig mit dem Kanalcodewort a = (un−1un−2...u1u0)als Koeffizienten eines Polynoms mit hochstmoglichen Grad n-1 dargestellt:a(x) = un−1x

n−1 + un−2xn−2 + ...+ u0x

0

Die zyklische Verschiebung wird dadurch realisiert, dass das Polynom a(x)mit x multipliziert wird und anschließend mit x · a(x)mod(xn − 1)der Restbestimmt wird. Der Rest der Division ergibt das verschobene Kanalcodewort:x · ai(x) = un−1x

n + un−2xn−1 + ...+ u0x

1

x · ai(x)mod(xn − 1) = un−1 Rest un−2xn−1 + ...+ u0x

1un−1x0 das wiederum

entspricht aj(x)

32

8.4.3 Das Generatorpolynom

Fur alle zyklischen Codes ist das Generatorpolynom von großer Bedeutung.Das Generatorpolynom besteht aus dem Produkt irreduzibler Minimalpoly-nome, die den zyklischen Code vollstandig beschreiben [7, Seite 162]). Grundlage fur die Bildung des Generatorpolynoms sind die so genanntenModularpolynome. Eigenschaften der Modularpolynome sind:(1) Sie sind irreduzibel, das heißt, sie sind nicht in ein Produkt von Polyno-men zerlegbar.(2) Das Polynom ist primitiv, das heißt, der Zyklus der Polynomreste istmaximal.Der Grad der Modularpolynome M(x) bestimmt somit die Kanalcodewortlangemit k1 = gradM(x) Der Codeparameter n bestimmt sich aus ximodM(x) miti=0,1,2,...n. Fur einen gewissen Wert p wiederholen sich die Polynomreste,d.h.xi = xi+pmodM(x).Gilt fur den Codeparameter n = 2k1 − 1, so ist das Polynom primitiv. Indiesem Fall ist p = n. Ist n < 2k1−1, so kann keine maximale Codewortlangeerreicht werden. In diesem Fall ist p < 2k1 − 1.Besonders wichtig fur die zyklischen Codes sind die uber dem Galois FeldGF(2). GF(2) besteht aus der Menge 0, 1 und auf ihr ist die modulo-2-Addition definiert.

Beispiel 2:M1(x) = x3 + x+ 1und M2(x) = x3 + 1Fur beide Polynome betragt k1 = gradM1(x) = gradM2(x) = 3Daraus folgt, dass n ≤ 23 − 1 = 7 ist.Interessanter ist die Betrachtung de Zyklen der Polynomenreste fur beidePolynome:

xi ximod(x3 + x+ 1) ximod(x3 + 1)x0 1 1x1 x xx2 x2 x2

x3 x+ 1 1x4 x2 + x xx5 x2 + x+ 1 x2

x6 x2 + 1 1x7 1 x

33

Fur M1(x) gilt damit, dass n = 7 ist und damit ist M1(x) primitiv. DieSchleifenlange betragt in diesem Fall auch 7. M2(x) dagegen ist nicht pri-mitiv. Fur M2(x) betragt die Schleifenlange n = 3. Das Codewort bestehtdemnach nur aus 3 Zeichen.

Beispiel Ende

Ist der Grad des Polynoms hoch, so ist die Bestimmung der Codewortlangeaufwendiger. Eine weitere Moglichkeit bietet die Zerlegung von p in Prim-faktoren. Ist xpmodM(x) = 1, so ist n durch den Wert des Exponentenbestimmt.

8.4.4 Codierung

MultiplikationsverfahrenZur Codierung eines Quellcodewortes a∗(x) wird das GeneratorpolynomM(x)der Lange n mit a∗(x) multipliziert und es entsteht das Kanalcodewort a(x):a(x) = a∗(x) ·M(x)Der Grad von M(x) mit k = gradM(x) legt dabei fur primitive Polynomedie Codelange von a(x) durch n = 2k−1 fest. Der Grad fur a∗(x) ergibt sichdamit durch grada∗(x) = l − 1 = n − k − 1. Der Grad von a∗(x) kann aberauch kleiner l-1 sein.

Beispiel 3:Es sei ein primitives Generatorpolynom M(x) = x3 + x + 1 gegeben (sieheBeispiel 2). Der Grad von M(x) ist k = 3 und damit, da M(x) primitiv istn = 23 − 1 = 7. D.h. die Lange der Kanalcodeworter betragt 7. Der Graddes Polynoms fur die Quellcodeworter ist somit 7 − 3 − 1 = 3, daraus folgtwiederum, dass die Quellcodeworter die Lange 4 haben.Gegeben ist das Quellcodewort a∗ = (1110). Es ist das Kanalcodewort adurch Multiplikation von a∗(x) mit M(x) zu bilden:a(x) = a∗(x) ·M(x) = (x3 +x2 +x) ·(x3 +x+1) = x6 +x5 +2x4 +2x3 +2x2 +xDa wir uns im Korper GF(2) befinden, erhalt man fur a(x):a(x) = x6 + x5 + x und damit ist a = (1100010)Nach gleichem Schema konnen weitere Kanalcodeworter aus Quellcodeworterna* bestimmt werden.

34

a∗ a0000 00000000001 00010110010 00101100011 00111011000 10110001001 10100111110 11000101111 1101001

Wie man erkennt, ist dieser Code nicht systematisch. Das Divisionsverfahrenbietet eine Moglichkeit, den Code zu systematisieren.

Beispiel Ende

Divisionsverfahren Das Divisionsverfahren wird verwendet, um einen sy-stematischen Code aus einem Quellcode mit Hilfe der zyklischen Codes zuerzeugen. Dafur wird die Eigenschaft genutzt, dass man einen erzeugten Codeum k redundante Stellen nach links verschiebt, um das gewunscht Codewortzu erhalten.Zur Codierung eines Quellcodewortes a∗ ist ein Generatorpolynom M(x) derLange n vom Grad k gegeben. Ein Kanalcodewort a entsteht durch Multipli-kation von a∗(x) mit xk und der anschließenden Subtraktion eines Restpoly-noms r(x):a(x) = a∗(x) · xk − r(x)Dabei ist r(x) = [a∗(x) · xk]modM(x).Das Restpolynom stellt die Belegung der Kontrollstellen in Kanalpolynoma(x) dar. Am folgenden Beispiel soll gezeigt werden, wie sich a aus a∗ be-stimmen lasst:

Beispiel 4:Es ist das primitive Generatorpolynom M(x) = x3 + x + 1 gegeben. Es istdas Quellcodewort a∗ = (1110) nach dem Divisionsverfahren zu codieren:a∗(x) · x3 = (x3 + x2 + x) ∗ x3 = x6 + x5 + x4

r(x) = [a∗(x) · x3]mod(x3 + x+ 1) = (x6 + x5 + x4)mod(x3 + x+ 1) = x2

Daraus folgt fur a(x):a(x) = a∗(x)·xk−r(x) = x6+x5+x4+x2 daraus ergibt sich fur a = (1110100).Nach gleichem Schema lassen sich auch alle weiteren Quellcodeworter codie-ren und man erhalt:

35

a∗ a0000 00000000001 00010110010 00101100011 00111011000 10001011001 10011101110 11101001111 1111111

Dieser Code ist systematisch, denn die ersten l Stellen des Kanalcodewortessind identisch zu den Quellcodewortern.

Beispiel Ende

FehlererkennungDas Mittel zur Feststellung eines Fehlers beruht auf der Untersuchung desKanalcodewortes b auf eine minimale Hamming-Distanz ∆min. Entsteht durchdie Storung ein Kanalcodewort, so kann man den Fehler nicht mehr erkennen.Fur ein Kanalcodewort kann ein Fehler gefunden werden, wenn das Kanalco-dewort b(x) kein Vielfaches von M(x) ist, dass heißt, wenn b(x)modM(x) 6= 0ist.

Beispiel 5:Es wurde das Kanalcodewort b = (1101000) empfangen. Das Generatorpoly-nom ist M(x) = x3 + x+ 1. Daraus ergibt sich furb(x)modM(x) = (x6 +x5 +x3)mod(x3 +x+ 1) = 1 Das Ergebnis ist ungleich0 und damit gehort b nicht zum Codealphabet A.

Beispiel Ende

36

8.5 Anmerkung

Die Codierung stellt ein weitgehendes Thema in der Informationstheorie dar.Die letzten Seiten sollten einen kleinen Einblick in die Vielfalt der Codie-rungstheorie gewahren. Heute wendet man die einzelnen Codes nicht einzelnan, sondern man versucht vielmehr verschiedene Codes zu verketten, um lei-stungsfahigere und weniger fehleranfallige Codierungen zu realisieren.

9 Entropie

9.1 Einfuhrung

Das Wort Entropie setzt sich zusammen aus dem griechischen Wortern en -innen und trope - Umkehr und hat laut Fremdworterbuch verschiedene Be-deutungen:

1. Die Entropie ist ein Maß fur den Grad der Ungewissheit des Ausgangseines Versuchs und damit eine Große der Wahrscheinlichkeitsrechnung.

2. Die Entropie ist eine Zustandsgroße zur Kennzeichnung des Ordnungs-zustandes thermodynamischer Systeme, mit deren Hilfe die Richtungdes Ablaufs von Warmeprozessen angegeben werden kann [19].

3. Die Entropie ist ein Maß fur den Informationsgehalt einer Nachricht [5].

Bereits anhand dieses Eintrages kann man sehr gut erkennen, dass dasWort Entropie in verschiedenen Fachgebieten verwendet wird. Wir werdensehen, dass dies durchaus sinnvoll ist, da zwar die wortlichen Definitionenunterschiedlich sind, die mathematischen Definitionen aber durchaus inein-ander uberfuhrbar.

10 Verwendung von Entropie in Fachrichtun-

gen

10.1 Physikalisch-chemischer Entropiebegriff

In der Disziplin der Thermodynamik, welche meines Erachtens eine Disziplinzwischen Physik und Chemie darstellt, wird Entropie als Maß fur den Grad

37

der Unordnung eines Systems verwendet. Um dies besser greifen zu konnen,folgt hier ein kleiner Exkurs zu abgeschlossenen Systemen, welcher sich vorallem auf [?, 28ff] stutzt.

Stellen wir uns dafur zunachst ein abgeschlossenes thermodynamischesSystem, zum Beispiel einen mit Gas gefullten Quader mit festem Volumen,vor. Die Gasteilchen seien kugelformige Punktmassen, welche in keinerleiWechselwirkung zueinander treten. Sie bewegen sich mit konstanter Ge-schwindigkeit durch den Hohlraum und rotieren dabei nicht um die eigeneAchse. Treffen sie auf die Gefaßwand, so prallen sie von dieser ab und flie-gen mit derselben Geschwindigkeit weiter. Dieses System aus Gasteilchenstrebt einen statistischen Gleichgewichtszustand an, das heißt die Teilchensollen moglichst gleich im Raum verteilt sein und den großtmoglichen Ab-stand zueinander haben. Dem Beobachter ist nun die makroskopische Ebeneder Erscheinungen dieses Prozesses zuganglich, welche er mikroskopisch in-terpretiert:

38

1. Die Masse der Gasportion setzt sich zusammen aus allen Einzelmassender enthaltenen Gasteilchen.

2. Das Gesamtvolumen entspricht der Summe der Volumina der Teilchenund des Raumes, den sie durch ihre Bewegung in Anspruch nehmen.

3. Durch das Auftreffen auf die Gefaßwand findet eine Impulsubertragungpro Flacheneineit und Zeiteinheit statt, welche als Druck messbar wird.

4. Die messbare Temperatur resultiert aus der mittleren kinetischen Ener-gie eines Teilchens pro Freiheitsgrad.

Um aus der kinetischen Energie eines Teilchens die Temperatur zu be-rechnen, benotigt man den Umrechnungsfaktor 0,5k mit der BOLTZMANN-Konstante

k = 1, 38 · 10−38Joule/Kelvin. (32)

Daraus folgt, dass die Warme eines Systems durch Einfuhrung der Anzahlder Freiheitsgrade z ausgedruckt werden kann mit

z

2kT, (33)

wobei der Faktor z/2 k makroskopisch als spezifische Warme bezeichnetwird. Durch Zufuhr von Warme zu einem abgeschlossenen System erhohtsich aufgrund der erhohten Geschwindigkeit der Teilchen und der damit ein-hergehenden Stoßfrequenz der Druck. In diesem Zusammenhang wurde derBegriff Entropie im Jahr 1850 von CLAUSIUS eingefuhrt. Er stellte fest, dasssich die Entropie eines Systems bei Uberfuhrung eines Zustandes (1) in denZustand (2) die Entropie vermehrt. Das Differential der dabei in das Systemhineinfließenden Warme bezeichnete er mit dQ un definierte die Entropiezu-nahme mit:

∆S =

∫ 2

1

dQ

T(34)

BOLTZMANN entwickelte diese Formel weiter, wobei er nach [?, 30]zunachst folgendes festlegte: In einem abgeschlossenem Gasvolumen gibt esm voneinander wohlunterschiedene Mikrozustande, welche mit

39

x1, ..., xi, ..., xm (35)

bezeichnet werden. Diesen Zustanden sind die Wahrscheinlichkeitszahlen

p((x1)), ..., p((xi)), ..., p((xm)) (36)

eindeutig zugeordnet. BOLTZMANN wendete dies auf die Definition derEntropiezunahme nach CLAUSIUS an und entwickelte diese (unter Umbe-nennung zu H) weiter zu

H = −km∑i=1

p(xi)ln p(xi). (37)

Bei Gleichverteilung der Wahrscheinlichkeiten ergibt sich daraus

H = −km∑i=1

1

mln

1

m= −k ln m (38)

10.2 Entropie von Wahrscheinlichkeitsraumen

Dieser Abschnitt befasst sich mit der Definition und der Verwendung desBegriffs Entropie in der Wahrscheinlichkeitsrechnung. Da im Vorangegange-nen der Wahrscheinlichkeitsraum bereits behandelt wurde, wird darauf nichtweiter eingegangen. Vielmehr sollen die mathematischen Grundlagen fur deninformationstheoretischen Informationsbegriff gelegt werden.

Sei ein Wahrscheinlichkeitsraum A=(Ω,B, P ) mit der Ereignismenge Ωwie bereits im ersten Teil definiert. Zu den Elementarereignissen

ω1, ..., ωi, ..., ωn (39)

seien die Wahrscheinlichkeiten

40

P (ωi) = pi (40)

mit

pi ≥ 0,n∑i=1

pi = 1 (41)

eindeutig zugeordnet [4, 10].

Jeder Zufallsversuch, der diesem Wahrscheinlichkeitsraum zuzuordnen ist,enthalt eine gewisse Unbestimmtheit, da sein Resultat - offenbar in Abhangigkeitvon den Eintrittswahrscheinlichkeiten der einzelnen Elementarereignisse - un-klar ist. Als Maß fur diese Unbestimmtheit fuhrt man nun die Entropie H ein.Diese Unbestimmtheit ist beseitigt, sobald der Versuch durchgefuhrt wurdeund ein bestimmtes Ereignis eingetreten ist. Definiert man nun zusatzlicheine Zufallsvariable X mit

Xi = ld pi, (42)

wobei ld der Logarithmus zur Basis 2 ist, so kann man die EntropieH des Wahrscheinlichkeitsraumes als Erwartungswert dieser Zufallsvariableeinfuhren:

H = −n∑i=1

pi ld pi. (43)

Der Logarithmus zur Basis 2 wird verwendet, weil das heutige Codie-rungssystem in der Informationstheorie und -technik auf dem Binarcode ba-siert [4, 10].

10.2.1 Eigenschaften der Entropie eines endlichen Wahrschein-lichkeitsraumes

Die untenstehenden Eigenschaften sind [4, S.11ff] entnommen und werdenhier nicht hergeleitet oder bewiesen. Herleitung und Beweise konnen der an-gegebenen Quelle entnommen werden.

41

1. Offensichtlich ist die Entropie eines sicheren Ereignisses, also eines Er-eignisses mit der Eintrittswahrscheinlichkeit 1, gleich Null, da hier keineUnsicherheit uber den Versuchsausgang besteht.

2. Ebenso leuchtet ein, dass durch Hinzufugen unmoglicher Ereignisse zueinem gegebenen Wahrscheinlichkeitsraum die Entropie unverandertbleibt, da uber das Nichteintreten dieser Ereignisse Sicherheit besteht.

3. Die Entropie erreicht ihr Maximum, wenn die Wahrscheinlichkeitengleichverteilt sind. Zugrunde liegt die Uberlegung, dass uber das Ein-treten jedes Ereignisses aus der Ereignismenge dieselbe Unsicherheitbesteht.

4. Betrachten wir zwei stochastisch unabhangige WahrscheinlichkeitsraumeA und B, so gilt fur die Entropie ihres kartesischen Produktes:

H(A×B) = H(A) +H(B). (44)

5. Sind die Wahrscheinlichkeitsraume A und B dagegen stochastisch abhangig,ist die Entropie ihres kartesichen Produktes definiert als:

H(A×B) = H(A) +H(B|A) = H(B) +H(A|B). (45)

Diese Entropie nennt man auch bedingte Entropie.

Zum besseren Verstandnis der letztgenannten Eigenschaft sei an dieserStelle aus [4, 14] zitiert:

Die Menge an Information, die aus der Realisierung zweier endlicherWahrscheinlichkeitsraume hervorgeht - aus der Durchfuhrung zweier Versu-che auf zwei endlichen Ereignismengen - ist gleich der Information, die ausder Kenntnis des Versuchsausganges auf einem Raum allein folgt, vermehrt

42

um die Information, die bei Kenntnis des Versuchsausganges auf dem ande-ren Raum folgt, unter der Bedingung, dass ein beliebiges Ereignis des zuerstbetrachteten Raumes eingetreten ist.

Zusammenfassend lasst sich also sagen, dass sich bei der Betrachtungzweier abhangiger Wahrscheinlichkeitsraume A,B die Information aus derRealisierung von B sich unter der Bedingung der Realisierung von A nur ver-kleinern kann, da die Unsicherheit uber das Eintreten bestimmter Ereignisseaus B sinkt. Sind die Wahrscheinlichkeitsraume A und B dagegen unabhangig,so ist der Informationsgehalt, der aus der Realisierung von B gewonnen wird,immer gleich, egal ob im Vorfeld A realisiert wurde oder nicht.

10.2.2 Eindeutigkeitssatz fur die Entropie

Die Entropie H kann als Funktion von Wahrscheinlichkeiten p1, p2, ..., pneines endlichen Wahrscheinlichkeitsraumes A=Ω,B, P interpretiert werden.Man schreibt dann

H = H(p1, p2, ..., pn). (46)

Der Eindeutigkeitssatz fur die Entropie lautet wie folgt.

Sei H(p1, p2, ..., pn) eine Funktion, die fur alle naturlichen Zahlen nundalle

pi ≥ 0mit i = 1, 2, ..., n undn∑i=1

pi = 1 (47)

definiert ist.

43

Besitzt diese Funktion die Eigenschaften

1. Die Funktion H(p1, p2, ..., pn) ist bezuglich aller Argumente stetig.

2. Die Funktion H(p1, p2, ..., pn) nimmt bei festem n unter der Bedingung

n∑i=1

pi = 1 (48)

ihr Maximum fur die Gleichverteilung pi = 1/n, i = 1, 2, ..., n an.

3. Es ist

H(A×B) = H(A) +H(B|A) = H(B) +H(A|B). (49)

4. Es gilt

H(p1, p2, ..., pn, 0) = H(p1, p2, ..., pn). (50)

dann gilt mit einer positiven Konstanten λ

H(p1, p2, ..., pn) = −λn∑i=1

pi ldpi. (51)

(vgl. [4, 16f])

Beweis: (zitiert nach [4, 17ff]) Wir setzen

H(1

n,

1

n, ...,

1

n) = h(n) (52)

und erhalten mit den Eigenschaften 2 und 4

h(n) = H(1

n,

1

n, ...,

1

n, 0) ≤ H(

1

n+ 1,

1

n+ 1, ...,

1

n+ 1) = h(n+ 1), (53)

also ist h(n) nicht monoton fallend in n. Seien nun k, l naturliche Zahlen.Wir betrachten k voneinander unabhangige Wahrscheinlichkeitsraume S1,

44

S2, ..., Sk, von denen jeder l Ereignisse gleicher Wahrscheinlichkeit besitzt,schreiben Si auch fur die Ereignismengen und erhalten so

Si = sr; r = 1, 2, ..., l , P (sr) =1

l(54)

und

H(Si) = H(1

l,1

l, ...,

1

l) = h(l). (55)

Mit Eigenschaft 3 folgt

H(S1 × S2 × S3 × ...× Sk) =k∑i=1

H(Si) = k h(l). (56)

Das kartesische Produkt besteht aus l hoch k Ereignissen gleicher Wahr-scheinlichkeit, also ist die Entropie dieses Produktes gleich h(l hoch k). Wirerhalten

h(lk) = k h(l) (57)

und analog fur jedes andere Paar naturlicher Zahlen m,n

h(mn) = n h(m). (58)

Wir bestimmen nun ein k so, dass fur l,m,n

lk ≤ mn < lk+1. (59)

Dann gilt:

k ld l ≤ n ld m < (k + 1) ld l, (60)

k

n≤ ld m

ld l<

k

n+

1

n. (61)

45

Mit der gezeigten Monotonie folgt sofort

h(lk) ≤ h(mn) ≤ h(lk+1), (62)

k h(l) ≤ n h(m) ≤ (k + 1) h(l) oder (63)

k

n≤ h(m)

h(l)≤ k

n+

1

n(64)

und daraus durch Subtraktion fur beliebige n

h(m)

h(l)− ld m

ld l≤ 1

n. (65)

Da n beliebig groß sein darf und die linke Seite gar nicht von n abhangt,folgt

h(m)

ld m=

h(l)

ld l, (66)

das heißt, da m und l beliebig sind

h(n) = λ ld n. (67)

Wegen der oben gezeigten Monotonie ist λ kleinergleich 0, womit fur pi= 1/n die Behauptung bewiesen ist.Wir betrachten nun den Fall, dass die pi beliebige positive, rationale Zahlensind. Sei also

pi =gig, g = 1, 2, ..., n mit gi, g ∈ N und

n∑i=1

gi = g. (68)

A sei ein endlicher Wahrscheinlichkeitsraum mit den Elementarereignis-sen ωi1 und den Wahrscheinlichkeiten P(ωi1) = pi. B sei ein von A abhangigerzweiter Wahrscheinlichkeitsraum, welcher g Ereignisse ω12, ..., ωg2 enthalt,die wir in n Gruppen zu jeweils g1, g2, ..., gn Ereignissen zusammenfassen.Tritt nun in A das Ereignis ωk1 ein, so geben wir in B allen gk Ereignis-sen der k-ten Gruppe die Wahrscheinlichkeit1/gk, wahrend alle Ereignisse

46

der anderen Gruppen die Wahrscheinlichkeit 0 erhalten. Damit ist fur je-des Resultat ωk1 ∈ Ω1 der Wahrscheinlichkeitsraum B ein System von gkgleichwahrscheinlichen Ereignissen. Daher ist die bedingte Entropie

H(B|ω1k) = H(

1

gk, ...,

1

gk) = h(gk) = λ ld gk, (69)

das heißt bei Bildung des Erwartungswertes bezuglich des Raumes A:

H(B|A) =n∑i=1

piH(B|ω1i ) = λ

n∑i=1

pi ld gi und (70)

(71)

H(A|B) = λn∑i=1

pi ld pi + λ ld g. (72)

Wir betrachten nun das kartesische Produkt A × B, welches aus allenEreignissen ωi1,ωk2) mit i = 1, 2, ..., n, k = 1, 2, ..., g besteht. Ein solchesEreignis ist nach Definition von B nur moglich, wenn ωk2 der i-ten Gruppeangehort. Damit ist die Anzahl der

47

moglichen Ereignisse (ωi1,ωk2) bei festem i gleich gi. Die Anzahl allerEreignisse von A× B ist also

∑i gi = g. Die Wahrscheinlichkeit der Ereignisse

(ωi1,ωk2) ist offensichtlich gleich pi · 1gi

= 1g, also gleichverteilt. Damit gilt

wieder

H(A×B) = h(g) = λ ld g. (73)

Unter Ausnutzung der Eigenschaft 3 ergibt sich

H(A×B) = H(B|A) +H(A), (74)

(75)

λ ld g =n∑i=1

pi ld pi + λ ld g +H(A) (76)

und damit

H(A) = −λn∑i=1

pi ld pi = H(p1, p2, ..., pn). (77)

Dies gilt aufgrund der Stetigkeit von H(p1, p2, ..., pn) fur beliebige, nicht-negative pi. Damit ist der Eindeutigkeitssatz fur die Entropie vollstandig be-wiesen.

10.3 Der Entropiebegriff in der Informationstheorie

SHANNON fuhrte in seiner Arbeit A mathematical theory of communicationden Entropiebegriff in die Informationstheorie ein. Dabei nutzte er deswe-gen denselben Begriff wie in der Thermodynamik, weil die mathematischeDefinition in beiden Disziplinen bis auf den Faktor k, die BOLTZMANN-Konstante, dieselbe ist. Auch die sprachliche Interpretation dieser Defini-tionen liegen wie wir sehen werden eng beieinander. In diesem Abschnittsoll daher zunachst ein Beschreibung des informationstheoretischen Entro-piebegriffs erfolgen. Darauf aufbauend wird die mathematische Beschreibunggeliefert und als Fazit die Parallelen zum physikalischen Entropiebegriff auf-gezeigt.

48

10.3.1 Entropie, Unsicherheit und Informationsgehalt einer Nach-richt

Basis jeder Nachrichtenubertragung ist eine beschrankte Menge von Sym-bolen, welche sowohl dem Sender als auch dem Empfanger einer Nachrichtbekannt ist. Aus dieser Zeichenmenge werden bei der Informationsbildungeinzelne Elemente mit einer bestimmten Wahrscheinlichkeit ausgewahlt undin Form einer Zeichenkette an einen Codierer ubergeben. Nach Codierung,Sendung und Empfang dieser Zeichenkette erfolgt die Bestimmung der Nach-richt. Dabei versucht der Empfanger, die ursprungliche Nachricht auf Grund-lage der vereinbarten Symbolmenge zu rekonstruieren [?, 50]. Die Komple-xitat der Zeichenkette steigt mit der Anzahl der zugrundeliegenden Symbole,was zur Folge hat, dass sich sowohl der Informationsinhalt solch einer Ket-te erhoht, als auch die statistische Unsicherheit fur das Auftreten einzelnerSymbole. An dieser Stelle fuhrte SHANNON die Entropie ein. Er nahm alsZeichenmenge ein Alphabet mit den Buchstaben

a1, ..., ai, ..., an (78)

an, aus dem jeder Buchstabe von der Informationsquelle mit der eindeutigzugeordneten Wahrscheinlichkeit

P (ai) = pi (79)

zur Erzeugung einer Zeichenkette - eines Wortes - ausgewahlt wird. DieInformation, die dabei pro Zeichen ubertragen wird, definierte er als dennegativen dualen Logarithmus der Auftrittswahrscheinlichkeit eines Buch-stabens:

I(ai) = −ld pi (80)

Es erscheint folgerichtig, dass der Erwartungswert des Informationsge-haltes pro Buchstabe ein Maß fur den Informationsinhalt einer Kette solcherBuchstaben darstellt. Gleichzeitig stellte SHANNON fest, dass sich darinauch eine gewisse Freiheit des Alphabets wiederspiegelte, ahnlich wie auchdie Entropie eines abgeschlossenen thermodynamischen Systems. Deswegen

49

und auch aufgrund der Tatsache, dass sich die mathematischen Definitio-nen lediglich durch einen Faktor unterscheiden, nannte SHANNON den vonihm definierten Erwartungswert fur den Informationsgehalt eines Buchsta-bens Entropie [?, S.32].

Im Sinne der Nachrichtenkette wird zwischen der Quellenentropie und derEmfangerentropie unterschieden. Die Quellenentropie bezieht sich auf denmittleren Informationsgehalt der Quelle und spiegelt auch ihre Unbestimmt-heit wieder. Dies korrespondiert mit der Anzahl der Binarentscheidungen,die im Mittel notwendig sind, um einen bestimmten Buchstaben aus dem Al-phabet auszuwahlen. In diesem Zusammenhang wird der Maximalwert derQuellenentropie auch als Entscheidungsgehalt der Quelle bezeichnet [7, 16].

Bei der Ubertragung der Nachricht durch den verrauschten Kanal kann eszu Informationsverlust kommen, weil einzelne Buchstaben fehlerhaft ubertragenwerden. Um den Informationsgehalt der beim Empfanger eingehenden Nach-richt greifbar zu machen, fuhrt SHANNON den Begriff der Empfangerentropieein. Wurde eine Nachricht fehlerfrei ubermittelt, weisen Quellen- und Empfangerentropiekeine Differenz auf. Dieser Zustand wird in der Datenverarbeitung ange-strebt. Auch dafur hat SHANNON einen Losungsansatz gefunden, wie wirspater noch sehen werden.

10.3.2 Mathematische Definition der Entropie nach SHANNON

Wie bereits erwahnt, legte SHANNON jeder Nachrichtenubertragung ein Al-phabet mit n Buchstaben

ai, i = 1, 2, ..., n (81)

und den zugeordneten Wahrscheinlichkeiten

P (ai) = pi, i = 1, 2, ..., n (82)

zugrunde. Den Informationsgehalt pro Buchstabe bestimmt man mit

I(ai) = −ld pi (83)

50

und die Entropie durch den Erwartungswert dieser Zufallsgroße:

H =n∑i=1

pi I(ai) = −n∑i=1

pi ld pi. (84)

Vergleicht man diese Formel mit der Formel fur die thermodynamischenEntropie nach BOLTZMANN

H = −kn∑i=1

p(xi)ln p(xi). (85)

sieht man, dass die Benutzung der Bezeichnung Entropie durch SHAN-NON durchaus berechtigt ist, da lediglich der Umrechnungsfaktor k ln 2 zurUberfuhrung der informationstheoretischen in die thermodynamische Entro-pie notwendig ist [?, 33].

Den Abschluss dieses Abschnitts soll ein Zitat liefern, weches die Aquivalenzder physikalischen und der informationstheoretischen Entropie in meinen Au-gen sehr anschaulich macht [3, 126]:

So wie es nicht moglich ist, ein Kommunikationssystem herzustellen, des-sen Empfanger mehr nutzbare Information erhalt, als die Nachrichtenquelleliefert, so unmoglich ist es, ein perpetuum mobile der zweiten Art zu konstru-ieren, das heißt eine Maschine, die aus der Abkuhlung eines Warmereservoirsmechanische Energie gewinnt.

11 Die Satze von SHANNON

SHANNON fand und bewies zur Entropie einer Nachrichtenubertragung, wel-che in diesem Abschnitte vorgestellt werden sollen.

Die Durchlasskapazitat C eines Kanals ist definiert als das kartesischeProdukt aus dem Alphabet A der Quelle und dem Alphabet B des Empfangers,also

51

C = A×B. (86)

11.1 Der erste Satz von SHANNON

Gegeben seia) ein stationaer Kanal mit der Durchlasskapazitat C und mit endlichem

Gedachtnis der Lange m,b) eine Quelle A mit der Entropie H kleiner C.Dann kann bei hinreichend großem n die von der Quelle ausgesendeten

Nachrichten in das Alphabet A so codieren, dass jedes Wort α aus n Buch-staben des Alphabets A in ein Wort u aus n+m Buchstaben des AlphabetsA ubergeht, und dass bei der Ubertragung des Wortes u uber den Kanalaus dem Kanalausgang erhaltenen Wort β (mit Buchstaben des AlphabetsB) sich das gesendete Wort u - und damit α - mit einer Wahrscheinlichkeitgroßer als 1-ε, ε großer 0, beliebig klein, bestimmen lasst [4, 70]

Oder, anders formuliert: Bei gegebener Quellenentropie H kleiner C kannman immer einen Code finden, mit dessen Hilfe das von der Quelle gesendeteWort mit einer beliebig kleinen Fehlerwahrscheinlichkeit schatzen kann.

Beweis: siehe [4, 70ff].

11.2 Der zweite Satz von SHANNON

Gegeben seia) ein stationarer Kanal [A, p, B] mit endlichen Gedachtnis der Lange m

und der Durchlasskapazitat C,b) eine Quelle A mit der Entropie H kleiner C.Dann kann ein Code von A nach A so gewahlt werden, dass die Ubertragungsgeschwindigkeit

der Nachricht der Große H beliebig nahe kommt [4, 74].

Anders ausgedruckt: Die Ubertragungsgeschwindigkeit einer Informationliegt beliebig nahe an der Entstehungsgeschwindigkeit der Information. Da-

52

mit ist der Informationsgehalt beliebig klein und jedes empfangene Zeichenb enthalt mit einer Wahrscheinlichkeit 1-ε, 0 kleiner ε kleiner 1, denselbenInformationsgehalt wie das entsprechende gesendete Zeichen a.

Beweis: siehe [4, 74ff].

53

12 Anwendungen der Informationstheorie

Die Informationstheorie ist eine breite und tiefgreifende Theorie, daher sindihre Anwendungsmoglichkeiten ebenso tiefgreifend und weit gefachert. Be-vor wir zu konkreten Anwendungsmoglichkeiten kommen, soll zunachst einUberblick gegeben werden (der naturlich keinen Anspruch auf Vollstandigkeiterhebt).

Der Begriff Information im landlaufigen Sinne als”Nachricht“ oder

”Wis-

sen“ wird zum Beispiel in den Kommunikations- und Medienwissenschaftenangewendet, beispielsweise fur das Fernmeldewesen. Die Okonomie sieht In-formation in drei Formen: als Ware, als Ausdruck von Infrastruktur oder alsWettbewerbsvorteil [9].

Im Bereich der Mathematik eng mit der Informationstheorie verwandtist die Kodierungstheorie mit ihren zahlreichen Anwendungen, einige davonwurden bereits in Kapitel vorgestellt. Eine wissenschaftliche Disziplin, derenHauptschwerpunkt auf der Verarbeitung von Information liegt, ist naturlichdie Informatik. Deren Teilgebiete sind daher ebenso eng mit dem Informa-tionsbegriff verwoben, hier seien exemplarisch die Kryptologie, Logik undDatenkompression genannt.

Die Nahe des Informationsbegriffs zu anderen strukturtheoretischen Kon-zepten wie System, Organisation, Struktur und Funktion erklart die Verbin-dung zur Systemtheorie, deren Pionier Ludwig von Bertalanffy etwazeitgleich mit den Pionieren der Informationstheorie arbeitete [12]. Hierbeisei insbesondere auf den Zusammenhang mit Theorien offener Systeme hin-gewiesen, welcher auf die Verwandtschaft der Begriffe Entropie und potenti-elle Information zuruckgeht. Weitere Anwendungsbereiche der Informations-theorie sind vor allem empirische Wissenschaften wie Physik, Biologie und(Kognitions-)Psychologie.

Shannons Informationstheorie konzentriert sich ausdrucklich nur auf dieDimension Syntax, also das Auftreten einzelner Informationseinheiten undihre Beziehungen untereinander. Sie macht keine Aussagen zu Semantik (Be-deutung von Informationseinheiten und ihrer Beziehungen) oder Pragma-tik (Wirkung von Informationseinheiten und ihrer Beziehungen) [9]. EinigeWissenschaften beziehen semantische und pragmatische Gesichtspunkte sehrwohl ein, dazu gehoren unter anderem die Sprachwissenschaften. Als Beispie-le seien die generative Grammatik von Noam Chomsky [1] und die Semiotikvon Umberto Eco [2] genannt.

In diesem Kapitel wird exemplarisch auf Kryptographie, die Kognitions-

54

wissenschaften und extraterrestrische Radioubertragung eingegangen wer-den.

12.1 Kryptologie - Einmalverschlusselung

Die Einmalverschlusselung oder One-Time Pad (OTP) Methode ist ein einfa-ches Verschlusselungsverfahren, das unter bestimmten Bedingungen informa-tionstheoretisch 100% sicher ist. Dies wurde 1949 von Claude Shannon ge-zeigt [16]. Die OTP Methode kann nicht, wie andere Verschlusselungsverfahren,durch computergestutztes Probieren (d.h. Brute-Force) innerhalb endlicherZeit geknackt werden. Sie ist das einzige Verschlusselungsverfahren, dass die-se perfekte Sicherheit bietet [15].

Das Verfahren wurde 1917 von Gilbert Vernam (USA) erfunden undvon Joseph O. Mauborgne fur die Verwendung mit Telex-Geraten wei-terentwickelt. Aufgrund der perfekten Sicherheit wurde und wird es fur sen-sible Kommunikation genutzt, unter anderem von den USA, Russland, Ka-nada und der ehemaligen DDR. Beispielsweise ist die bis heute bestehen-de, hochsichere direkte Fernschreibverbindung zwischen dem amerikanischenPrasidenten und dem sowjetischen Generalsekretar durch ein Einmalschlussel-Verfahren geschutzt. Anbieter von Sicherheitsprodukten fuhren das Systembis heute in ihrem Sortiment, z.B. die osterreichische Mils Electronic [10].

12.1.1 Sicherheit

Vorraussetzung fur die 100%ige Sicherheit des Einmalschlussel-Verfahrenssind:

• Der Einmalschlussel ist so lang wie der Klartext,

• der Einmalschlussel ist geheim (d.h. ist nur dem Sender und dem Empfangerbekannt),

• der Einmalschlussel muss unvorhersagbar zufallig (also nicht mit einemPseudozufallsgenerator erzeugt) sein,

• der Einmalschlussel darf nur einmal verwendet werden (und muss da-nach zerstort werden).

Sobald eine dieser Bedingungen nicht mehr gegeben ist, bietet die Ein-malverschlusselung keine perfekte Sicherheit mehr. Wird der Einmalschlussel

55

etwa nicht personlich ubergeben, sondern verschlusselt per E-Mail zugestellt,ist das gesamte Verfahren nur noch so sicher wie das Verschlusselungsverfahrenfur die Email. Die letztendliche Sicherheit eines Systems ist nur so hoch wiedie des schwachsten Glieds. Um perfekte Sicherheit zu erreichen, muss dasVerfahren selbst aber nicht geheimgehalten werden. Diese Eigenschaft stellteinen Grundsatz der moderenen Kryptographie dar und wurde 1883 vonAuguste Kerckhoffs aufgestellt – somit bezeichnet man es als Kerck-hoffs’ Prinzip [15].

12.1.2 Funktionsweise

Die Einmalverschlusselung ist ein symmetrisches Verfahren, d.h. fur das Ver-schlusseln und Entschlusseln wird der gleiche Schlussel verwendet. Dahermuss der Schlussel vor der Kommunikation sowohl Sender als auch Empfangerbekannt sein. Außerdem mussen die oben genannten Vorraussetzungen gege-ben sein. Im folgenden soll nun das Verfahren an einem einfachen Beispielerklart werden.

Die zu ubertragende geheime Nachricht im Klartext K lautet:

K = ANGRIFFIMMORGENGRAUEN

Der Schlussel S, der beiden Kommunikationspartnern zur Verfugung steht,lautet:

S = WZSLXWMFQUDMPJLYQOXXB

Nun muss der Klartext mit dem Schlussel kombiniert werden. Dazu ordnetman jedem Buchstaben eine Zahl zu:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Mithilfe dieser Zuordnung werden Klartext und Schlussel in eine Reihe vonZahlen umgewandelt. Danach addiert man die Werte stellenweise Modulo 26.

0 13 6 17 8 5 5 8 12 12 14 17 6 4 13 6 17 0 20 4 13 (K)

+22 25 18 11 23 22 12 5 16 20 3 12 15 9 11 24 16 14 23 23 1 (S)

---------------------------------------------------------------

22 12 24 2 5 1 17 13 2 6 17 3 21 13 24 4 7 14 17 1 14

Wenn man dieses Ergebnis jetzt wieder zuruck in Buchstaben ubersetzt,erhalt man den Geheimtext G, der nun ubertragen werden kann.

56

G = WMYCFBRNCGRDVNYEHORBO

Dieser Geheimtext erlaubt keinerlei Ruckschlusse auf den Klartext. Eine sta-tistische Auswertung der Buchstabenhaufigkeiten hat keine Aussicht auf Er-folg, denn es handelt sich nicht um eine monoalphabetische Substitution: Ein

”A“ im Klartext wird im Geheimtext nicht immer durch den selben Buch-

staben dargestellt, im Beispiel einmal als”W“ und einmal als

”O“. Der po-

tentielle Angreifer weiß nur, dass der Klartext im Beispiel aus 21 Buchstabenbesteht – es gibt also eine Unmenge an Moglichkeiten fur Zeichenkombina-tion, die auch noch in verschiedenen Sprachen interpretiert werden konnen.Es gibt keine weiteren Hinweise, welche der moglichen Kombinationen dieRichtige ist – das ist mit perfekter Sicherheit gemeint.

Man kann sich den Schlussel als Rauschen vorstellen, mit dem der Senderseinen Klartext unlesbar macht. Da der Empfanger uber dasselbe Rauschenverfugt, kann er die Nachricht wieder entstoren und somit lesbar machen.Eine abgefangene Nachricht ist fur Abhorer nutzlos, da sie nur Rauschenenthalt.

Zur Erleichterung des Verfahrens kann man die Addition der Buchstabenmodulo 26 in der folgenden Form darstellen (Abb. 1) [14]. Um eine Nach-richt zu kodieren, sucht man den Klartextbuchstaben im Tabellenkopf, suchtdann den Schlusselbuchstaben in der darunterliegenden Spalte (Großbuch-stabe) und erhalt daneben den Geheimtextbuchstaben (Kleinbuchstabe). Dain den Spalten Buchstabenpaare stehen, nennt man diese Darstellungsformauch Bigramm-Tabelle. Um eine Nachricht zu dekodieren, benutzt man dieBigramm Tabelle in Abb. 2. Man sucht den Geheimtextbuchstaben im Tabel-lenkopf, sucht dann den Schlusselbuchstaben in der darunterliegenden Spalte(Großbuchstabe) und erhalt daneben den Klartextbuchstaben (Kleinbuchsta-be).

In der Praxis gebrauchlicher als das gerade dargestellte Beispiel ist eineMethode, bei der die Nachricht zuerst in Zahlen ubersetzt wird und dann miteinem Zahlen-Einmalschlussel kombiniert wird. Dabei werden neben Zah-len fur einzelne Buchstaben auch Zahlenkombinationen fur haufig verwen-dete Worter und Phrasen genutzt, um die Nachricht zu verkurzen. Diesesind darauf optimiert, fehlerresistent gegenuber Zahlendrehern und ahnlichenFluchtigkeitsfehlern zu sein (siehe Abb. 3). Man kann das Einmalschlussel-Verfahren auch fur Dateien auf dem Computer verwenden. Dabei verbindetman jedes Bit der Originaldatei und jedes Bit des Einmalschlussels durcheine XOR-Verknupfung (exklusives Oder).

57

Abbildung 1: Bigramm-Tabelle zum Enkodieren

1⊕ 1 = 0

1⊕ 0 = 1

0⊕ 1 = 1

0⊕ 0 = 0

visuellausfuhren?

12.1.3 Vor- und Nachteile

Der herausragende Vorteil des Einmalschlussel-Verfahrens ist naturlich sei-ne 100%ige Sicherheit. Dabei ist hervorzuheben, dass mit diesem Verfah-ren verschlusselte Informationen auch in der Zukunft geheim bleiben wer-den – im Gegensatz zu anderen gangigen Verschlusselungsverfahren wie AESoder RSA. Deren Sicherheit basiert einzig auf der Tatsache, dass deren Ent-schlusselung durch Ausprobieren sehr vieler Moglichkeiten (sog. Brute-Force-Methode) zur Zeit sehr rechenaufwendig istbrute und somit mehrere Jahr-zehnte dauern wurde. Diese Algorithmen konnten in Zukunft aber nutzlos

58

Abbildung 2: Bigramm-Tabelle zum Enkodieren

werden, wenn sich die Hardware entscheidend verbessert (z.B. der Quanten-computer anwendungsreif wird, und somit Brute-Force-Attacken lohnenswertwerden. Falls in der Mathematik enscheidende Durchbruche erreicht werden,z.B. ein schnelleres Verfahren zur Faktorisierung von Primzahlen entdecktwird, werden die klassischen Verschlusselungsverfahren ebenfalls nutzlos.

Ein weiterer Vorteil des Einmalschlussel-Verfahrens ist seine Einfachheit,es kann mit Bleistift und Papier umgesetzt werden. Man ist also nicht aufeinen Computer angewiesen – ein klarer Vorteil, denn es muss ein erhebli-cher Aufwand betrieben werden, um Computer fur sensible Daten nutzen zukonnen: Beispielsweise muss der Zugang dazu streng kontrolliert werden under darf er nie an ein Netzwerk angeschlossen werden. Ein Agent, der das Ein-malschlussel-Verfahren nutzt, tragt nur einen Einmalschlusselblock mit sich,der leicht versteckt oder zerstort werden kann. Daruber hinaus benotigt erkeine kompromittierenden Empfangssender oder Ahnliches, die Ubertragungwird in der Regel uber Kurzwellensender realisiert, die mit handelsublichenWeltempfangern gehort werden konnen. Ubertragung-

mehr?Zahlen-senderetc.

Doch die Seite der Nachteile des Verfahrens wiegt schwer: Erstens ge-staltet es sich schwierig, große Zufallstexte zu generieren. Dazu ist spezielle

59

Abbildung 3: Code-Tabelle

Hardware notig, die beispielsweise die kosmische Hintergrundstrahlung alsQuelle fur Zufall nutzt. Zweitens ist das Schlusselmanagement uberaus un-praktisch: Aus bereits genannten Grunden konnen die Schlussel nicht miteiner anderen Verschlusselungstechnik elektronisch ubertragen werden, siemussen sowohl Sender als auch Empfanger physisch und vertraulich zuge-stellt werden – ein erheblicher Aufwand. Drittens ist es anfallig gegenuberunvorsichtigem Vorgehen: Falls eine der oben beschriebenen Bedingungennicht oder nur teilweise eingehalten wird, ist der Geheimtext sehr leicht zuentschlusseln. Viertens ist das Verfahren durch aktive Angreifer gefahrdet:Wenn ein Angreifer den Inhalt der geheimen Nachricht kennt und die ver-schlusselte Nachricht abfangt, kann er den Schlussel rekonstruieren und stattdes Originals eine eigene Nachricht senden. Diese muss zwar genauso lang seinwie der Originalklartext, kann aber trotzdem einen verhangnisvollen Inhalthaben.

Im Ergebnis wird das Einmalschlussel-Verfahren vor allem dann einge-setzt, wenn Sicherheit oberste Prioritat hat und damit praktische Maßstabein den Hintergrund treten. Zur Wahrung der Privatsphare in der taglichenKommunikation ist es jedoch ungeeignet.

12.2 Informationstheorie in den Kognitionswissenschaf-ten

Viele Naturwissenschaften bestanden schon lange vor der Entwicklung derInformationstheorie und wurden im Nachhinein von ihr beeinflusst und be-

60

Abbildung 4: Einmalschlusselblock

reichert. Im Gegensatz dazu entwickelten sich die Kognitionswissenschaftenetwa zeitgleich mit der Informationstheorie in den 1940er und 1950er Jah-ren. Informationsverarbeitung spielt keine Nebenrolle, sondern ist das zen-trale Forschungsfeld der Kognitionswissenschaften: Sie untersuchen, wie In-formationen uber die Umwelt von Individuen aufgenommen werden, wie sieverarbeitet werden und in Reaktionen munden. Es gibt dabei zwei zentra-le Herangehensweisen bzw. Paradigmen, die im folgenden erlautert werdensollen: Der Symbolismus und der Konnektionismus [9].

12.2.1 Symbolismus

Wie bereits gesagt wurde, waren die Anfange der Automaten- und Infor-mationstheorie zugleich die Anfange der Kognitionswissenschaften. Durchdie parallele Entwicklung erwuchs in den vierziger Jahren die Vorstellung,menschliches Denken sei eine rechnerische (

”komputationale“) Fahigkeit und

damit von Maschinen nachahmbar. Dies ist das Ziel von Forschungen zurkunstlichen Intelligenz (KI), bei denen man versucht, Problemloseverfahrenzu programmieren (z.B. mit der speziell dafur entwickelten Programmier-sprache LISP) und andere kognitive Simulationsverfahren zu implementie-

61

ren. Laut Alan Turing ist eine Maschine dann im Stande zu”denken“,

wenn sie sich in einem Frage-Antwort-Spiel mit menschlichem Fragestellernicht von einem Menschen unterscheiden lasst. [18] Das KI-Paradigma lau-tet: Menschliches Denken ist ein algorithmischer Prozess, in dem Symbolfol-gen abgearbeitet werden. Die Ein- und Ausgabe folgt syntaktischen Regeln,wahrend die semantische Ebene in der Programmierung nicht beruhrt wird(bzw. durch festgelegte Variablen bereits vorgegeben ist).

Zwar konnten einige gute Frage-Antwort-Maschinen programmiert wer-den (z.B. der kunstliche Psychiater ELIZA von Joseph Weizenbaum), je-doch scheiterte man an

”einfachen“ Fahigkeiten wie Mustererkennung oder

Navigation in einer naturlichen Umwelt. Deswegen konzentrierte man sichzunehmend darauf, das menschliche Gehirn zu untersuchen und kunstlichumzusetzen – dies soll im folgende Abschnitt erlautert werden.

12.2.2 Konnektionismus

Wenn menschliches Denken ein Algorithmus ist, der programmiert werdenkann (das Paradigma der KI), heißt das auch, dass Denken unabhangig vonder Rechenarchitektur ist, es also nur auf das Programm, nicht auf Art undStruktur der Hardware ankommt. Die Neuroinformatik hat einen gegenteili-gen Ansatz: Das Paradigma des Konnektionismus versucht, die Architekturund Funktionsweise eines menschlichen Gehirns nachzuahmen. Fur ein besse-res Verstandnis des Konnektionismus soll im folgenden ein kurzer Uberblickuber die neuronalen Grundlagen gegeben werden.

Das Gehirn ist ein komplexes Netzwerk, dass aus Nervenzellen (Neuro-nen) und Verbindungen (Synapsen) besteht. Die Anzahl der Neuronen wirdauf 1012 und die der Synapsen auf 1015 geschatzt, es ist also ein uberauskomplexes und gleichzeitig sehr dichtes System (jedes Neuron ist im Schnittuber 4 Glieder mit jedem anderen verbunden). Eine Nervenzelle erhalt uberihre Synapsen Signale von anderen Nervenzellen, und wenn die Summe die-ser eingehenden Aktivitaten groß genug ist, sendet sie selbst Signale aus. Siefunktioniert also als eine Art Schwellschalter, ein Effekt den man als syn-aptische Plastizitat bezeichnet. Diese Signale sind kurzzeitige Anderungen(wenige Millisekunden) des elektrischen Potentials von ca. 50-80 Millivolt.Im Wahrnehmungsprozess sind verschiedene großere Neuronenverbande in-volviert, welche einzelne Merkmale aus der Menge der gegebenen Sinnes-daten kodieren. Bei der visuellen Wahrnehmung entsteht beispielsweise derGesamteindruck

”Ich sehe einen Baum“ nur aus dem Zusammenspiel unter-

62

schiedlicher neuronaler Bereiche, die jeweils auf Beurteilung von Form, Ober-flachenstruktur , Farbe usw. spezialisiert sind. Das Symbol

”Baum“ wird also

nicht durch einzelne Neuronen reprasentiert, sondern wird subsymbolisch ge-speichert. Weiterhin ist zu bemerken, dass dieses komplexe System durch ak-tivitatsabhangige Selbstorganisation entsteht. Die Verbindungen und Funk-tionen der einzelnen Neuronen sind nicht a priori festgelegt, sondern entste-hen erst im Laufe der Entwicklung durch aktive Auseinandersetzung mit derUmwelt.

Damit unterscheidet sich das Gehirn erheblich von der Struktur eineshandelsublichen PCs, denn die Informationsverarbeitung findet nicht zentralin einem Prozessor, sondern in einem Netzwerk aus Berechnungsknoten undVerbindungen statt. Informationen werden verteilt gespeichert und parallelverarbeitet. Man hat versucht, solche Architekturen zunachst theoretisch zumodellieren. Ein Beispiel dafur ist der Assoziativspeicher von Steibuch,welcher nun auszugsweise vorgestellt werden soll.

12.2.3 Beispiel: Assoziativspeichermodell

Die Lernmatrix von Steinbuch [17] ist geeignet, das Arbeitsprinzip neuro-naler Netze zu verdeutlichen. Betrachten wir ein einfaches Beispiel, in demzwei Muster in Form von Binarvektoren A und B gegeben sind:

e−→A =

11001

, e−→B =

10101

,

Diese Muster sollen in einer 5×5 Lernmatrix ω gespeichert werden, derenEintrage wir mit ωi,j bezeichnen. Sie berechnen sich gemaß der Lernregel

ωi,j → ωi,j + eiej

Dies kann mann als Netzwerkarchitektur interpretieren: Je funf Eingangs-und Ausgangsneuronen sind untereinander uber Synapsengewichte verbun-den, die in der Matrix reprasentiert sind. Der Anfangszustand ist ω = 0 undnun wird das Muster A gespeichert (

”gelernt”). Die Eintrage berechnen sich

gemaß der bereits genannten Lernregel wij = eAi eAj so dass sich folgende Form

ergibt:

63

ω =

1 1 0 0 11 1 0 0 10 0 0 0 00 0 0 0 01 1 0 0 1

Jetzt soll das zweite Muster gespeichert werden, gemaß der Lernregel

ωi,j → ωi,j + eBi eBj bekommt man

ω =

2 1 0 0 21 1 0 0 11 0 1 0 10 0 0 0 02 1 1 0 2

Nun wollen wir aus der Lernmatrix etwas abrufen. Dazu geben wir einen

Input-Vektor −→x und erhalten den Output-Vektor −→y = ω · −→x . Wir geben alserstes das bereits gespeicherte Muster A ein:

ω · e−→A =

53205

Um diese Ausgabe als binaren Mustervektor interpretieren zu konnen,

definieren wir die Schwellwertfunktion:

σ(x) =

1 falls x ≥ σo

0 sonstmit σo =

1

5

∑i

yi

Der Output-Vektor berechnet sich damit als −→y = σ(ω · −→x ). In unseremBeispiel ist σ0 = 3, wir erhalten also unser gelerntes Muster A in der Ausgabezuruck:

−→y = σ(ω · e−→A ) =

σ(5)σ(3)σ(2)σ(0)σ(5)

=

11001

= e−→A

64

Interessanterweise gibt die Matrix sogar dann das gelernte Muster Azuruck, wenn die Eingabe ahnlich dem Muster A ist:

e−→A∗

=

11000

≈ e−→A =⇒ −→y = σ(ω · e

−→A∗

) =

11001

≡ e−→A

Genau das versteht man unter einem Assoziativspeicher: UnvollstandigeEingaben werden aufgrund von bereits gespeicherten Daten vervollstandigt.Naturlich ist diese Vervollstandigungskapazitat begrenzt. Geben wir etwa einMuster ein, dass eine Uberlagerung von Muster A und Muster B darstellt,so bekommen wir auch eine Uberlagerung der Muster als Ausgabe:

−→x =

11100

=⇒ −→y = σ(ω · −→x ) =

10001

Die Lernmatrix von Steinbuch ist fur den praktischen Einsatz offen-

sichtlich ungeeignet, denn das Verhaltnis zwischen Dimension der Matrixund in ihr speicherbare Muster ist denkbar ungunstig. Allerdings dient es alsanschauliches Modell eines assoziativen Gedachtnisses [9]: Die Speicherungerfolgt verteilt auf alle

”Synapsen“ und wahrend der Verarbeitung arbeiten

alle”Synapsen“ parallel.

12.2.4 Vergleich der Paradigmen

Die Paradigmen des Symbolismus und des Konnektionismus bieten offen-sichtlich unterschiedliche Herangehensweisen. Die praktischen Unterschiedeliegen in der Informationsverarbeitung (sequentiell vs. Parallel), der Speiche-rung (lokalisiert vs. distributiv) und in der Plastizitat, also der Veranderbarkeitdes Systems. Wahrend sich unser Gehirn uberhaupt erst durch Veranderungund Anpassung entwickeln kann, sind klassische KI-Programme starr imHinblick auf ihre Anwendungsbereiche und ihr Potential. Allerdings ist einestrukturelle Anpassung auch in traditioneller KI moglich, wenn man das Pro-gramm selbst als Teil der Eingabe versteht und somit eine Anpassung durchneue Programmebenen moglich macht (universelle Turing-Maschine).

65

Weiterhin gibt es einen konzeptionellen Unterschied, der weiter oben be-reits erlautert wurde: Die Art der Kodierung der Information geschieht inKI-Systemen symbolisch, in neuronalen Netzen jedoch subsymbolisch (d.h.merkmalskodierend). Sehen wir vor uns eine Tasse, so wird sie in unseremGehirn verteilt gespeichert bzw. reprasentiert: Eine Region kodiert die Kan-ten, eine andere die Oberflachenbeschaffenheit und wieder eine andere dieFarbe der Tasse. Im Gegensatz dazu wurde in einem KI-Programm die Tassedurch eine einzige Variable reprasentiert sein.

Die zentrale Frage ist allerdings, ob sich die Paradigmen des Symbolis-mus und des Konnektionismus auch prinzipiell unterscheiden. Holger Lyresieht keinen prinzipiellen Untersched, denn es seien beides Berechenbarkeit-sparadigmen, d.h. sie gehen davon aus, dass unsere physikalische Welt al-gorithmisch beschreibbar und jede Interaktion mit der Umwelt theoretischberechenbar ist. Es sei aber unklar, ob unser Gehirn wirklich

”rechnet“, d.h.

algorithmisch arbeitet [9].

12.2.5 Extraterrestrische Radioubertragungen

Astronomen suchen etwa seit den 1960er Jahren mit Radioteleskopen nach Si-gnalen außerirdischer Lebewesen (SETI engl. Search for Extra-Terrestrial In-telligence). Das Vorhaben erfreut sich großer Bekanntheit, wozu vor allem dasverteilte Rechenprojekt SETI@home Universitat Berkley (USA) beigetragenhat. Tausende Privatanwender stellen dabei ihre ungenutzte Rechenleistungfur die Auswertung der Radiosignale zur Verfugung. Bei der Auswertung wirvor allem nach auffalligen, nicht-zufalligen Signalen gesucht. Dies konnte einunnutzes Unterfangen sein, wie Rainer Kayser von der Universitat Hamburgherausstellt [6]. Falls es extraterrestrische Zivilisationen gibt, dann waren siesicher in der Lage, ihre Radiobotschaften mit optimaler Informationsdichtezu kodieren. Diese enthielten dann aber keine auffalligen Regelmaßigkeitenund ware nicht von der normalen Warmestrahlung eines Sterns zu unterschei-den, stellte Michael Lachmann vom Max-Planck-Institut fur evolutionareAnthropologie in Leipzig fest [8]. Die Uberlegungen von Lachmann undseinen amerikanischen Kollegen Newman und Moore sollen im folgendenausfuhrlich dargestellt werden.

Die Informationstheorie von Shannon betrachtet die Menge xi allermoglichen Nachrichten xi die uber einen Nachrichtenkanal ubertragen werdenkonnen. Im einfachsten Fall ist dieser Kanal rauschfrei, d.h. jede Nachrichtwird genau so empfangen, wie sie gesendet wurde. Nach Shannon bestimmt

66

Abbildung 5: Das Arecibo-Observatorium in Puerto Rico wird fur das SE-TI@home Projekt genutzt. Es ist mit einem Durchmesser von 304,8 m daszweitgroßte Radioteleskop der Welt.

sich der durchschnittliche Informationsgehalt pro Nachricht so

S = −∑i

pi log pi (87)

wobei pi die Wahrscheinlichkeit der Ubertragung der Nachricht xi ist.Ublicherweise steht

”log“ fur den naturlichen Logarithmus. Gibt es keine wei-

teren Beschrankungen, dann wird der Informationsgehalt S maximal, wennalle Nachrichten mit gleicher Wahrscheinlichkeit ubertragen werden. Wennman also viele Nachrichten hintereinander sendet, die mit je gleicher Wahr-scheinlichkeit aus der Menge xi entnommen sind, wird der Datenfluss volligzufallig erscheinen – es sei denn, der Empfanger kennt die Kodierung derNachrichten.

Wir ubertragen die Situation nun auf eine Nachrichtenubermittlung mit-hilfe elektromagnetischer Strahlung. Die These lautet wie folgt: Wir gehendavon aus, dass dem Sender der Nachricht ein begrenzter Vorrat an Ener-gie zur Verfugung steht. Die Frage ist, wie groß die maximale Menge anInformation ist, die mit diesem Energievorrat gesendet werden kann. Im All-

67

gemeinen lauft das auf die Maximierung der Gleichung (87) fur Photonenen-sembles hinaus. Die Losung ist bereits aus der statistischen Physik bekannt,da die Formel der Shannon-Information mit der Formel fur thermodyna-mische Entropie identisch ist. Im Fall von elektromagnetischer Strahlungfuhrt es zu Schwarzkorperstrahlung. Wir werden nun zeigen, dass die in-formationsdichteste elektromagnetische Ubertragung dasselbe Spektrum wieSchwarzkorperstrahlung hat.

Damit wir Shannons Theorie auf elektromagnetische Strahlung anwen-den konnen, mussen wir das Problem als Ubertragung von Information ubereinen Kanal modellieren. Dafur betrachten wir folgendes Gedankenexperi-ment: Stellen wir uns einen Zylinder mit Grundflache At und Lange l mitperfekt reflektierenden Wanden vor, in dessen Inneren wir jeden beliebi-gen elektromagnetischen Mikrozustand erzeugen konnen. Jeder moglichenNachricht wird ein bestimmter Mikrozustand zugeordnet, und der Mikrozu-stand wird an den Empfanger ubertragen. Der Informationsgehalt wird durch wie?Shannons Formel (87) bestimmt, dabei ist pi die Wahrscheinlichkeit, dasssich der Zylinderholraum im Mikrozustand i befindet. Diese Art der Nach-richtenubertragung ist nicht das gleiche wie eine Radioubertragung, aber wirwerden zeigen, dass sie den selben Informationsgehalt hat.

Wir wollen nun einen stetigen Nachrichtenstrom erzeugen, indem wir eineReihe von Mikrozustanden ubertragen, fur die Ubertragung jeder Nachrichtsteht eine begrenzte Energiemenge 〈E〉 zur Verfugung. Was ist dann derhochstmogliche Informationsgehalt pro Nachricht? Dafur mussen wir Glei-chung (87) maximieren, wobei jede Anzahl von Photonen im Zylinder erlaubtist. Das Ergebnis ist das großkanonische Enseble mit

pi =exp [−β(Ei − µNi)]

Z(88)

wobei Ei die Energie in Mikrozustand i ist, Ni die Anzahl der Photonen,Z die großkanonische Zustandssumme, β das Temperaturpotential und µ daschemische Potential. Wenn wir nun die Mikrozustande mit der Anzahl derPhotonen nk im jeweiligen Einzelpartikelzustand k bezeichnen, kann manzeigen, dass der Durchschnitt der nk der Bose-Einstein-Verteilung folgt

〈nk〉 =1

eβεk − 1(89)

Wir haben µ = 0 gesetzt weil es fur Photonen im Vakuum kein chemischesPotential gibt, εk steht fur die Energie eines Photons im Zustand k.

68

Wir erweitern das Gedankenexperiment und stellen uns vor, dass wir,statt den gesamten Zylinderinhalt zu ubertragen, eine Deckflache des Zylin-ders offnen und so die Photonen in Form einer Radioubertragung entweichenkonnen. Der Empfanger befindet sich im Abstand d vom Zylinder und hatdie Flache Ar (Abb. 6). Nur die Photonen, die einen Impuls innerhalb ei-

Abbildung 6: Der Versuchsaufbau des Gedankenexperiments: Links der Zy-linderhohlraum mit dem

”Sender“ (Offnung des Zylinders) und rechts der

”Empfanger“.

nes bestimmten Winkels haben, werden den Empfanger erreichen (eventuellnachdem sie mehrmals an der Innenwand reflektiert wurden). Das Volumenunseres Hohlraumes betragt V = lAt und die Dichte des Einzelpartikelzu-stands ist ρ(ε) = 2lAtArε2

d2h3c3, hierbei ist h das Plancksche Wirkungsquantum

und c die Lichtgeschwindigkeit. Damit ist die spektrale Leistungsdichte un-serer Nachricht

I(ε) =2lAtArd2h3c3

ε2

eβε − 1(90)

Dies bezeichnet man ublicherweise als Schwarzkorperspektrum, welchesvon einer idealen thermischen Strahlungsquelle bei der Temperatur T =β−1 ausgesendet wird. Die meisten astronomischen Korper senden ein sehrahnliches Spektrum aus. Die Ubertragung enthalt alle notwendigen Informa-tionen, um den ursprunglichen Mikrozustand im Zylinder zu rekonstruierenund hat daher denselben Informationsgehalt.

Wir wollen nun einen Nachrichtenstrom erzeugen, wobei jede Nachrichtdurch einen Mikrozustand des Zylinderhohlraums reprasentiert wird. DieUbertragungsdauer betragt dann l

cund die durchschnittliche Ubertragungsintensitat

ist konstant. Die Temperatur wird von der zur Verfugung stehenden Energiebestimmt. Wir berechnen die durchschnittliche Energie 〈E〉 pro Nachrichtindem wir Gleichung (90) uber die Energie ε integrieren und durch l

cteilen.

69

Fur eine Ubertragung mit einem Energiebudget P pro Zeiteinheit berechnetsich die Temperatur T = β−1 uber

T 4 =15h3c2

2π4

d2

AtArP (91)

Der Informationsgehalt pro Zeiteinheit dSdt

kann berechnet werden mit

S = logZ − β δ logZδβ

und δ logZδβ

= 〈E〉 so dass

dS

dt=

8π4

45h3c2

AtArd2

T 3 =

[512π4

1215h3c2

AtArd2

P 3

] 14

(92)

[] Diese Gleichung beschreibt die hochstmogliche Ubertragungsrate fur elek-tromagnetische Ubertragungen fur eine gegebene Durchschnittsleistung P .Sie hangt nur von den Flacheninhalten von Sender und Empfanger, von derenAbstand und von der druchschnittlichen Sendeleistung bzw. der Temperaturab.

Wir konnten zeigen, dass die Optimierung der Informationsdichte fur elek-tromagnetische Strahlung mit einem festen Energiebudget pro Zeiteinheit einSpektrum erzeugt, dass nicht vom Schwarzkorperspektrum zu unterscheidenist. Ein Empfanger, der nicht im Besitz der Kodierung ist, wird eine Nach-richt nicht von naturlich auftretender Schwarzkorperstrahlung im Universumtrennen konnen. Falls also extraterrestrische Wesen diese informationsmaßigeffizienteste Art der Nachrichtenubertragung nutzen, werden wir davon nieerfahren konnen.

Literatur

[1] Noam Chomsky. Aspects of the Theory of Syntax. The MIT press,Cambridge, Massachusetts, 1965.

[2] Umberto Eco. Einfuhrung in die Semiotik. Wilhelm Fink, Munchen,1972.

[3] W. Heise and P. Quattrocchi. Informations-und Codierungstheorie: ma-thematische Grundlagen der Daten-Kompression und-Sicherung in dis-kreten Kommunikationssystemen. Springer, 1995.

70

[4] E. Henze and H.H. Homuth. Einfuhrung in die Codierungstheorie: Stu-dienbuch fur Mathematiker, Informatiker, Naturwissenschaftler und In-genieure ab 3. Semester. Vieweg, 1974.

[5] Hans H. Hermann. Lechners Fremdworterbuch. Lechern Verlag, 1994.

[6] Rainer Kayser. Seti: Geht die botschaft im rauschen unter? http://

www.astronews.com/news/artikel/2004/12/0412-005.shtml, April2010.

[7] H. Klimant, R. Piotraschke, and D. Schoonfeld. Informations-und Kodierungstheorie. Vieweg+ Teubner Verlag,2006.

[8] M. Lachmann, MEJ Newman, and C. Moore. The physical limits ofcommunication. American Journal of Physics, 72:1290, 2004.

[9] Holger Lyre. Informationstheorie. Eine philosophisch-naturwissenschaftliche Einfuhrung. Wilhelm Fink, Munchen, February2002.

[10] Mils. One time key encryption. http://www.mils.com/pages/en/

technology/unbreakable/onetimekey, April 2010.

[11] P. Neidhardt. Einfuhrung in die Informationstheorie. Verlag Technik,1957.

[12] E. Oeser. Wissenschaft und Information: Wissenschaftstheorie und em-pirische Wissenschaftsforschung. Oldenbourg, Wien, 1976.

[13] G. Raisbeck. Informationstheorie, Eine Einfuhrung fur Naturwissen-schaftler und Ingenieure. Akademie-Verlag Berlin.

[14] Dirk Rijmenants. Bigram table. http://users.telenet.be/d.

rijmenants/bigram.txt, April 2010.

[15] Dirk Rijmenants. Cipher machines and cryptology: Onetimepad. http://users.telenet.be/d.rijmenants/en/onetimepad.htm, April 2010.

[16] Claude Elwood Shannon. Communication theory of secrecy systems.Bell Systems Technical Journal, 28:682, 1949.

71

[17] Karl Steinbuch. Die Lernmatrix. Biological Cybernetics, 1(1):36–45,1961.

[18] Alan Mathison Turing. Computing machinery and intelligence. Mind,59(236):433–460, 1950.

[19] Ruth Kufner u.a. Groses Fremdworterbuch. VEB BibliographischesInstitut, 1979.

[20] Wikipedia. Claude elwood shannon, December 2009.

[21] Wikipedia. Code. http://de.wikipedia.org/wiki/Code, February2010.

[22] Wikipedia. Linearer code. http://de.wikipedia.org/wiki/

Linearer_Code, February 2010.

[23] D. Wille and M. Holz. Repetitorium der Linearen Algebra. 1. Binomi,1991.

72