Stefan Schäffl er Mathematik der Information Theorie und Anwendungen der Shannon-Wiener Information Springer-Lehrbuch Masterclass Stefan Schäffler Mathematik der Information Theorie und Anwendungen der Shannon-Wiener Information StefanSchäffler Fakultät für Elektro- und Informationstechnik MathematikundOperationsResearch UniversitätderBundeswehrMünchen Neubiberg,Deutschland ISSN1234-5678 ISBN978-3-662-46381-9 ISBN978-3-662-46382-6(eBook) DOI10.1007/978-3-662-46382-6 Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detailliertebibliografischeDatensindimInternetüberhttp://dnb.d-nb.deabrufbar. MathematicsClassificationNumber(2010):62Bxx,94A15,68Q12,81P45,80A05,37Axx SpringerSpektrum ©Springer-VerlagBerlinHeidelberg2015 DasWerkeinschließlichallerseinerTeileisturheberrechtlichgeschützt.JedeVerwertung,dienichtaus- drücklichvomUrheberrechtsgesetzzugelassenist,bedarfdervorherigenZustimmungdesVerlags.Das giltinsbesonderefürVervielfältigungen,Bearbeitungen,Übersetzungen,MikroverfilmungenunddieEin- speicherungundVerarbeitunginelektronischenSystemen. DieWiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesemWerk be- rechtigtauch ohnebesondere Kennzeichnung nicht zuderAnnahme, dasssolcheNamenimSinneder Warenzeichen- undMarkenschutz-Gesetzgebung alsfreizubetrachtenwärenunddahervonjedermann benutztwerdendürften. DerVerlag,dieAutorenunddieHerausgebergehendavonaus,dassdieAngabenundInformationenin diesemWerkzumZeitpunkt derVeröffentlichungvollständigundkorrektsind.WederderVerlagnoch die Autoren oder die Herausgeber übernehmen, ausdrücklich oder implizit,Gewähr für den Inhalt des Werkes,etwaigeFehleroderÄußerungen. GedrucktaufsäurefreiemundchlorfreigebleichtemPapier. Springer-Verlag GmbH Berlin Heidelberg ist Teil der Fachverlagsgruppe Springer Science+Business Media (www.springer.com) Für Antonia,Michael und ? Einleitung Informationtheoryisabranchofthemathematical theoryofprobabilityandmathematical statistics. SolomonKullbackin[Kull97] DerBegriffInformationgehörtzudenSchlüsselbegriffenunsererZeit;Soziologenspre- chen daher unter anderem vom Informationszeitalter, wenn sie die Gegenwart beschrei- ben. Fragt man nach den wissenschaftlichen Disziplinen, die sich mit Information be- schäftigen,sokommtdenmeistenwohldieInformatik,dieNachrichtentechnikundganz allgemein Kommunikationswissenschaften (etwa als Teilgebiete der Elektrotechnik, der Psychologie und der Soziologie) in den Sinn; an die Mathematik denken die wenigs- ten.AusdiesemGrundwirddieInformationstheorieauchnicht(mehr)alsTeilgebietder Mathematikwahrgenommen.Diesistumsoerstaunlicher,wennmanbedenkt,dassesMa- thematikerwaren,diediePionierarbeiteinerwissenschaftlichenTheoriederInformation –eingebettetindieStochastik–geleistethaben. In mathematisch-naturwissenschaftlichem Kontext tritt der Begriff Information wohl erstmalsimJahre1925ineinerArbeitvonRONALD AYLMER FISHER (1890–1962)mit demTitel„Theoryofstatisticalestimation“auf(siehe[Fi25]);dabeiwirdimPrinzipnach derMengeanInformationgefragt,diemanüberunbekannteVerteilungsparameterdurch RealisierungendeszugrundegelegtenZufallsexperimentserhält;aufeineverwandteFra- gestellung werdenwir beider Betrachtungsuffizienter Statistiken zusprechen kommen. In diesem Buch wird ein zur FISHER-Information alternativer Zugang zum Begriff der Informationgewählt.AlsersteVeröffentlichungindiesemZusammenhangkannderArti- kel„AMathematicalTheoryofCommunication“gelten,dessenersterTeilvonCLAUDE ELWOOD SHANNON (1916–2001)im Juli 1948 im Bell Systems Technical Journal ver- öffentlicht wurde (siehe [ShWe63]). Das Ziel dieser Vorgehensweise wird im Titel des besagtenArtikelsklar:DerInformationsbegriffdientalsBausteineinerzuentwickelnden Theorieder Kommunikation.Im gleichen Jahr wählte NORBERT WIENER (1894–1964) unabhängigvonSHANNONeinenanalogenZugangfürstetigeVerteilungendurchEinfüh- rungderdifferentiellenEntropie(siehe[Wie61]),welcheinthermodynamischemKontext bereits von LUDWIG BOLTZMANN (1844–1906) im Jahr 1866 verwendet wurde; aller- dings verwendete WIENER im Gegensatz zu BOLTZMANN und SHANNON in diesem VII VIII Einleitung Zusammenhang explizit den Begriff Information. Das vorliegende Buch hat somit den Shannon-WienerZugangzummathematischenInformationsbegriffzumGegenstand.Wie bereits NORBERT WIENER in seinem Buch über Kybernetik ([Wie61]) feststellte, kann dieserZugangdenInformationsbegriffvonFISHERersetzen(dasentsprechendeHilfsmit- telistdie„deBruijnIdentität“,sieheetwa[Joh04]).ObwohlsowohlSHANNON alsauch WIENER beiihrerKonzeptiondermathematischen„Messung“einerInformationsmenge inerster LiniedieKommunikationstheorieim Blickhatten,zeigtschondieParallelezur Thermodynamik,dassderimFolgendenzuuntersuchendeInformationsbegriffwesentlich breiteranwendbarist. Der erste Teil des vorliegenden Buchesist den Grundlagen gewidmet. Wesentlich ist dabeinacheinergegenseitigenAbgrenzungderbeidenBegriffeNachrichtundInformati- ondieaxiomatischeZuordnungeinerInformationsmengezueinerWahrscheinlichkeit. In Teil II werden abzählbare Systeme, also Wahrscheinlichkeitsräume mit höchstens abzählbar vielen Ergebnissen untersucht. Die mittlere Informationsmenge dieser Syste- me führt auf die fundamentale Definition der Shannon-Entropie und ihre Anwendung als geeignetes Maß für die Güte einer Codierung; mit der Huffman-Codierungwird ei- ne optimale Codierung vorgestellt. Ein sehr wichtiges Beispiel für abzählbare Systeme liefert die statistische Physik – genauer die Thermodynamik.In diesem Zusammenhang ermöglicht die Shannon-Entropie eine informationstheoretische Interpretation der ther- modynamischenEntropieundinsbesonderedeszweitenHauptsatzesderThermodynamik fürabgeschlosseneSysteme(Kap.4).MitderEinführungbedingterWahrscheinlichkeiten inKap.5werdenzweiklassischeAnwendungenderShannon-Entropieindermathema- tischenStatistik(SuffizienzvonSchätzfunktionen)undinderNachrichtentechnik(Trans- information)vorgestellt.EinBuchüberdieMathematikderInformationwäreohneeinen BlickaufQuanteninformationundQuantenalgorithmenunvollständig;dasentsprechende sechsteKapiteldientalsEinführungindieseThematik. Mit Teil III beginnt die Analyse allgemeiner Systeme, also von Wahrscheinlichkeits- räumen mit im Allgemeinen mehr als abzählbar vielen Ergebnissen; dies führt auf den vonNORBERT WIENERimRahmenderInformationstheorieeingeführtenBegriffderdif- ferentiellenEntropie.Dienotwendigenmaß-undintegrationstheoretischenVoraussetzun- genwerdenjeweilsanderStelleentwickelt,wosiebenötigtwerden.NebenAnwendungen ausderNachrichtentechnikunddermathematischenStatistikwirdderInformationsbegriff auchbeiderAnalysedynamischerSystemebetrachtet. Dieses Buch ist für Mathematiker und/oder Informatiker mit Vorkenntnissen auf Bachelor-Niveau geschrieben. Es dient einerseits der Darstellung, wie der Informati- onsbegriff in der Mathematik verankert ist, und soll andererseits eine Auswahl von Anwendungen (gerade auch außerhalb der Kommunikationstechnik) vorstellen; da als Mathematikbuchkonzipiert,wirdnatürlichgroßerWertaufexakteBeweisführunggelegt. Daher wird sich der Inhalt dieses Buches nicht mit den Inhalten decken, die Ingenieure mit dem Begriff Informationstheorie in Verbindung bringen (hierzu gibt es eine nicht mehr zu überschauendeFülle von Literatur;genanntsei als Klassiker [CovTho91]). Zur VermeidungvonMissverständnissen wurdedaherimTiteldiesesBuchesderBegriffIn- Einleitung IX formationstheorievermieden.DennochbleibtbeimAutordieÜberzeugung,dassauchder einoderandereIngenieurdasvorliegendeBuchmitGewinnlesenwird,wennersichauf dieSpracheundDarstellungsartderMathematikeinlässt,wasabergeradeinDeutschland leidernichtselbstverständlichist. AberauchMathematikerwerdenindiesemBuchgewisseThemenvermissen;ichden- ke insbesondere an die Ergodentheorie. Dieses Thema hat sich längst zu einer eigenen Spezialdisziplinentwickelt;indenAbschn.7.3und9.4werdenwirzumindestaufdenBe- griffdesergodischenWahrscheinlichkeitsmaßeszusprechenkommen.EinStandardwerk zumThemaErgodentheorieundInformationistimmernoch[Bill65].Füreinemathema- tischfundierteEinführungindieCodierungstheorie,diehierauchnuramRandebetrachtet wird, sei auf [Ash65] und [HeiQua95] verwiesen. Einen sehr interessanten Zusammen- hanggibteszwischenderShannon-EntropieundderHausdorff-DimensioneinerMenge; hierseiauf[Bill65]und[PötSob80]verwiesen. MeingeschätzterMitarbeiterundKollege,Herr DR. R. VON CHOSSY hatdasManu- skript in den letzten Wochen seiner Dienstzeit kritisch durchgearbeitet, viele Verbesse- rungvorschläge und wertvolle Beweisideen (zum Beispiel zu Theorem 8.1) eingebracht undwar mirsomitwieimmereineunschätzbareHilfe. IhmseiandieserStelle–gerade auchfürseinehervorragendeArbeitindengemeinsamen14Jahren–besondersgedankt. Symbole P.˝/ Potenzmengevon˝ S Entropie P BildmaßvonX X PB bedingteWahrscheinlichkeit T Transinformation C Kanalkapazität R Coderate H Hilbertraum h(cid:2);(cid:2)i SkalarproduktinH H S SphärevonH H H˝n n-fachesTensorproduktvonH (cid:2).X/ vonX erzeugte(cid:2)-Algebra k(cid:2)k Maximum-Norm 1 Z Zylindermenge ˚ binäreAddition .˝;S/ Messraum .˝;S;P/ Wahrscheinlichkeitsraum F Frobenius-PerronOperator E.XjC/ bedingteErwartung XI Inhaltsverzeichnis TeilI Grundlagen 1 NachrichtundInformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1 AusgangspunktSender:Nachricht . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 EndpunktEmpfänger:Information . . . . . . . . . . . . . . . . . . . . . . . 10 2 InformationundZufall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1 WahrscheinlichkeitundInformationsmenge . . . . . . . . . . . . . . . . . . 13 2.2 DiemittlereInformationsmengeeinesZeichens . . . . . . . . . . . . . . . 18 TeilII AbzählbareSysteme 3 DieEntropie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.1 DiskreteWahrscheinlichkeitsräume . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 MittlereInformationsmenge . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3 Huffman-Codierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4 DasMaximumEntropiePrinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.1 MaximalemittlereInformationsmengeunterNebenbedingungen . . . . . 37 4.2 StatistischePhysik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5 BedingteWahrscheinlichkeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.1 Suffizienz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.2 Transinformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 6 Quanteninformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 6.1 Q-Bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 6.2 TensorräumeundMulti-Q-Bits . . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.3 Messungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 6.4 Kopieren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 XIII