Informationstheorie - Information theory

Informationstheorie ist die wissenschaftliche Erforschung der Quantifizierung , Speicherung und Kommunikation von digitalen Informationen . Das Feld wurde in den 1920er Jahren durch die Arbeiten von Harry Nyquist und Ralph Hartley und in den 1940er Jahren von Claude Shannon grundlegend begründet . Das Feld liegt an der Schnittstelle von Wahrscheinlichkeitstheorie , Statistik , Informatik , statistischer Mechanik , Informationstechnik und Elektrotechnik .

Ein Schlüsselmaß in der Informationstheorie ist die Entropie . Die Entropie quantifiziert die Unsicherheit, die mit dem Wert einer Zufallsvariablen oder dem Ergebnis eines Zufallsprozesses verbunden ist . Zum Beispiel liefert die Ermittlung des Ergebnisses eines fairen Münzwurfs (mit zwei gleich wahrscheinlichen Ergebnissen) weniger Informationen (geringere Entropie) als die Angabe des Ergebnisses eines Würfelwurfs (mit sechs gleich wahrscheinlichen Ergebnissen). Einige andere wichtige Maße in der Informationstheorie sind gegenseitige Information , Kanalkapazität, Fehlerexponenten und relative Entropie . Wichtige Teilgebiete der Informationstheorie sind Quellencodierung , algorithmische Komplexitätstheorie , algorithmische Informationstheorie , informationstheoretische Sicherheit und endliche Blocklängen-Informationstheorie .

Anwendungen grundlegender Themen der Informationstheorie sind verlustfreie Datenkompression (zB ZIP-Dateien ), verlustbehaftete Datenkompression (zB MP3s und JPEGs ) und Kanalcodierung (zB für DSL ). Ihr Einfluss war entscheidend für den Erfolg der Voyager- Missionen in den Weltraum, die Erfindung der CD , die Machbarkeit von Mobiltelefonen und die Entwicklung des Internets. Die Theorie hat auch Anwendungen in anderen Bereichen, einschließlich gefunden statistische Inferenz , Kryptographie , Neurobiologie , Wahrnehmung , Linguistik, die Entwicklung und Funktion von molekularen Codes ( Bioinformatik ), thermische Physik , Molekulardynamik , Quantencomputing , schwarze Löcher , Information Retrieval , Informationsbeschaffung , Plagiatserkennung , Mustererkennung , Anomalieerkennung und sogar Kunsterstellung.

Überblick

Die Informationstheorie untersucht die Übertragung, Verarbeitung, Extraktion und Nutzung von Informationen. Abstrakt kann man sich Information als Auflösung von Unsicherheit vorstellen. Im Fall der Informationskommunikation über einen verrauschten Kanal wurde dieses abstrakte Konzept 1948 von Claude Shannon in einem Artikel mit dem Titel A Mathematical Theory of Communication formalisiert , in dem Information als eine Menge möglicher Botschaften gedacht wird und das Ziel darin besteht, diese Nachrichten über einen verrauschten Kanal zu senden und den Empfänger die Nachricht trotz des Kanalrauschens mit geringer Fehlerwahrscheinlichkeit rekonstruieren zu lassen. Das Hauptergebnis von Shannon, das Kodierungstheorem für verrauschte Kanäle, zeigte, dass im Grenzbereich vieler Kanalnutzungen die asymptotisch erreichbare Informationsrate gleich der Kanalkapazität ist, eine Größe, die lediglich von der Statistik des Kanals abhängt, über den die Nachrichten übertragen werden sind gesendet.

Die Codierungstheorie befasst sich mit dem Auffinden expliziter Verfahren, Codes genannt , zum Erhöhen der Effizienz und zum Reduzieren der Fehlerrate der Datenkommunikation über verrauschte Kanäle bis nahe an die Kanalkapazität. Diese Codes können grob in Datenkompressions- (Quellcodierung) und Fehlerkorrektur- (Kanalcodierung) Techniken unterteilt werden. Im letzteren Fall dauerte es viele Jahre, bis die Methoden, die Shannons Arbeit bewies, möglich waren.

Eine dritte Klasse von informationstheoretischen Codes sind kryptographische Algorithmen (sowohl Codes als auch Chiffren ). Konzepte, Methoden und Ergebnisse aus der Codierungstheorie und der Informationstheorie finden in der Kryptographie und Kryptoanalyse breite Anwendung . Eine historische Anwendung finden Sie im Artikel Verbot (Einheit) .

Historischer Hintergrund

Das bahnbrechende Ereignis, das die Disziplin der Informationstheorie begründete und weltweit sofort bekannt machte, war die Veröffentlichung von Claude E. Shannons klassischem Aufsatz "A Mathematical Theory of Communication" im Bell System Technical Journal im Juli und Oktober 1948.

Vor dieser Arbeit waren in den Bell Labs begrenzte informationstheoretische Ideen entwickelt worden , die alle implizit Ereignisse gleicher Wahrscheinlichkeit unterstellten. Harry Nyquists Aufsatz aus dem Jahr 1924, Certain Factors Affecting Telegraph Speed , enthält einen theoretischen Abschnitt zur Quantifizierung von "Intelligenz" und der "Leitungsgeschwindigkeit", mit der sie von einem Kommunikationssystem übertragen werden kann, und gibt die Beziehung W = K log m (in Erinnerung an die Boltzmann-Konstante) ), wobei W die Übertragungsgeschwindigkeit von Informationen ist, m die Anzahl der verschiedenen Spannungspegel ist, aus denen bei jedem Zeitschritt ausgewählt werden kann, und K eine Konstante ist. Ralph Hartleys Veröffentlichung von 1928, Transmission of Information , verwendet das Wort Information als eine messbare Größe, die die Fähigkeit des Empfängers widerspiegelt, eine Folge von Symbolen von jeder anderen zu unterscheiden, und somit die Information als H = log S n = n log S quantifizieren , wobei S war die Anzahl der möglichen Symbole und n die Anzahl der Symbole in einer Übertragung. Die Informationseinheit war daher die Dezimalziffer , die ihm zu Ehren seither manchmal als Hartley als Maßeinheit oder Informationsmaßstab bezeichnet wurde. Alan Turing verwendete 1940 ähnliche Ideen als Teil der statistischen Analyse des Brechens der deutschen Enigma- Chiffren des Zweiten Weltkriegs .

Ein Großteil der Mathematik der Informationstheorie mit Ereignissen unterschiedlicher Wahrscheinlichkeit wurde für das Gebiet der Thermodynamik von Ludwig Boltzmann und J. Willard Gibbs entwickelt . Zusammenhänge zwischen informationstheoretischer Entropie und thermodynamischer Entropie, einschließlich der wichtigen Beiträge von Rolf Landauer in den 1960er Jahren, werden in Entropie in Thermodynamik und Informationstheorie untersucht .

In Shannons revolutionärem und bahnbrechendem Aufsatz, dessen Arbeiten Ende 1944 in den Bell Labs im Wesentlichen abgeschlossen waren, führte Shannon erstmals das qualitative und quantitative Kommunikationsmodell als statistischen Prozess ein, der der Informationstheorie zugrunde liegt, und begann mit der Behauptung:

"Das grundlegende Problem der Kommunikation besteht darin, an einem Punkt eine an einem anderen Punkt ausgewählte Nachricht entweder genau oder ungefähr wiederzugeben."

Dabei kamen die Ideen von

  • die Informationsentropie und Redundanz einer Quelle und ihre Relevanz durch das Quellencodierungstheorem ;
  • die gegenseitige Information und die Kanalkapazität eines verrauschten Kanals, einschließlich des Versprechens einer perfekten verlustfreien Kommunikation, gegeben durch das Codierungstheorem über verrauschte Kanäle;
  • das praktische Ergebnis des Shannon-Hartley-Gesetzes für die Kanalkapazität eines Gaußschen Kanals ; ebenso gut wie
  • das Bit – eine neue Art, die grundlegendste Informationseinheit zu sehen.

Informationsmengen

Die Informationstheorie basiert auf Wahrscheinlichkeitstheorie und Statistik. Die Informationstheorie beschäftigt sich oft mit Informationsmaßen der Verteilungen, die mit Zufallsvariablen verbunden sind. Wichtige Informationsmengen sind Entropie, ein Informationsmaß in einer einzelnen Zufallsvariablen, und gegenseitige Information, ein gemeinsames Informationsmaß zwischen zwei Zufallsvariablen. Die erstgenannte Größe ist eine Eigenschaft der Wahrscheinlichkeitsverteilung einer Zufallsvariablen und gibt eine Grenze für die Rate an, mit der Daten, die von unabhängigen Stichproben mit der gegebenen Verteilung erzeugt wurden, zuverlässig komprimiert werden können. Letzteres ist eine Eigenschaft der gemeinsamen Verteilung von zwei Zufallsvariablen und ist die maximale Rate zuverlässiger Kommunikation über einen verrauschten Kanal im Grenzbereich langer Blocklängen, wenn die Kanalstatistik durch die gemeinsame Verteilung bestimmt wird.

Die Wahl der logarithmischen Basis in den folgenden Formeln bestimmt die Einheit der Informationsentropie, die verwendet wird. Eine gängige Informationseinheit ist das Bit, basierend auf dem binären Logarithmus . Andere Einheiten sind die nat , die auf dem natürlichen Logarithmus basiert , und die Dezimalziffer , die auf dem gewöhnlichen Logarithmus basiert .

Im Folgenden wird ein Ausdruck der Form p log p konventionell als gleich Null betrachtet, wenn p = 0 ist . Dies ist begründet, weil für jede logarithmische Basis.

Entropie einer Informationsquelle

Basierend auf der Wahrscheinlichkeits-Massenfunktion jedes zu kommunizierenden Quellsymbols ist die Shannon- Entropie H in Einheiten von Bits (pro Symbol) gegeben durch

wobei p i die Auftrittswahrscheinlichkeit des i- ten möglichen Wertes des Quellsymbols ist. Diese Gleichung gibt die Entropie in der Einheit "Bits" (pro Symbol) an, weil sie einen Logarithmus der Basis 2 verwendet, und dieses Entropiemaß zur Basis 2 wurde ihm zu Ehren manchmal als Shannon bezeichnet . Die Entropie wird auch häufig unter Verwendung des natürlichen Logarithmus berechnet (Basis e , wobei e die Eulersche Zahl ist), der eine Entropiemessung in nats pro Symbol erzeugt und manchmal die Analyse vereinfacht, indem die Notwendigkeit vermieden wird, zusätzliche Konstanten in die Formeln aufzunehmen. Andere Basen sind ebenfalls möglich, werden jedoch weniger häufig verwendet. Zum Beispiel erzeugt ein Logarithmus der Basis 2 8 = 256 eine Messung in Bytes pro Symbol, und ein Logarithmus der Basis 10 erzeugt eine Messung in Dezimalstellen (oder Hartleys ) pro Symbol.

Intuitiv ist die Entropie H X einer diskreten Zufallsvariablen X ein Maß für die mit dem Wert von X verbundene Unsicherheit, wenn nur ihre Verteilung bekannt ist.

Die Entropie einer Quelle , die eine Sequenz von aussendet N Symbolen, die unabhängig und identisch verteilt (iid) ist NH Bits (pro Nachricht von N Symbolen). Wenn die Quelldatensymbole identisch verteilt sind jedoch nicht unabhängig, die Entropie einer Nachricht mit der Länge N wird kleiner als NH .

Die Entropie einer Bernoulli - Studie als Funktion der Erfolgswahrscheinlichkeit, oft die genannte binäre Entropiefunktion , H b ( p ) . Die Entropie wird bei 1 Bit pro Versuch maximiert, wenn die beiden möglichen Ergebnisse gleich wahrscheinlich sind, wie bei einem unvoreingenommenen Münzwurf.

Wenn man 1000 Bits (0s und 1s) überträgt und der Wert jedes dieser Bits dem Empfänger vor der Übertragung bekannt ist (mit Sicherheit einen bestimmten Wert hat), ist klar, dass keine Informationen übertragen werden. Wenn jedoch jedes Bit unabhängig davon mit gleicher Wahrscheinlichkeit 0 oder 1 ist, wurden 1000 Shannons an Informationen (häufig als Bits bezeichnet) übertragen. Zwischen diesen beiden Extremen können Informationen wie folgt quantifiziert werden. Wenn die Menge aller Nachrichten { x 1 , ..., x n } ist , die X sein könnte, und p ( x ) die Wahrscheinlichkeit von einigen ist , dann ist die Entropie H von X definiert:

(Hier ist I ( x ) die Selbstinformation , also der Entropiebeitrag einer einzelnen Nachricht und der Erwartungswert .) Eine Eigenschaft der Entropie ist, dass sie maximiert ist, wenn alle Nachrichten im Nachrichtenraum gleichwahrscheinlich p . sind ( x ) = 1/ n ; dh am unvorhersehbarsten, in welchem ​​Fall H ( X ) = log n ist .

Der Spezialfall der Informationsentropie für eine Zufallsvariable mit zwei Ausgängen ist die binäre Entropiefunktion, meist zur logarithmischen Basis 2, also mit dem Shannon (Sh) als Einheit:

Gemeinsame Entropie

Die gemeinsame Entropie zweier diskreter Zufallsvariablen X und Y ist lediglich die Entropie ihrer Paarung: ( X , Y ) . Dies bedeutet , dass , wenn X und Y sind unabhängig , dann ist ihre Verbundentropie die Summe ihrer einzelnen Entropien ist.

Wenn zum Beispiel ( X , Y ) die Position einer Schachfigur darstellt – X die Reihe und Y die Spalte, dann ist die gemeinsame Entropie der Reihe der Figur und der Spalte der Figur die Entropie der Position der Stück.

Trotz ähnlicher Schreibweise sollte die gemeinsame Entropie nicht mit der Kreuzentropie verwechselt werden .

Bedingte Entropie (Äquivokation)

Die bedingte Entropie oder bedingte Unsicherheit von X bei gegebener Zufallsvariable Y (auch Äquivokation von X über Y genannt ) ist die durchschnittliche bedingte Entropie über Y :

Da die Entropie davon abhängig gemacht werden kann, ob eine Zufallsvariable oder diese Zufallsvariable ein bestimmter Wert ist, sollte darauf geachtet werden, diese beiden Definitionen der bedingten Entropie nicht zu verwechseln, von denen die erstere häufiger verwendet wird. Eine grundlegende Eigenschaft dieser Form der bedingten Entropie ist:

Gegenseitige Information (Transinformation)

Gegenseitige Information misst die Menge an Informationen, die über eine Zufallsvariable durch die Beobachtung einer anderen gewonnen werden kann. Es ist wichtig in der Kommunikation, wo es verwendet werden kann, um die Informationsmenge zu maximieren, die zwischen gesendeten und empfangenen Signalen geteilt wird. Die gegenseitige Information von X relativ zu Y ist gegeben durch:

wo SI ( S pecific gegenseitig I nformationen) ist die punktuellen gegenseitige Information .

Eine grundlegende Eigenschaft der gegenseitigen Information ist, dass

Das heißt, zu wissen , Y , können wir durchschnittlich speichern I ( X ; Y ) Bits bei der Codierung X im Vergleich zu nicht zu wissen , Y .

Gegenseitige Informationen sind symmetrisch :

Mutual Information kann als die durchschnittliche Kullback-Leibler-Divergenz (Informationsgewinn) zwischen der ausgedrückt wird posterior Wahrscheinlichkeitsverteilung von X gegeben dem Wert von Y und die Vorverteilung auf X :

Mit anderen Worten, dies ist ein Maß dafür, wie stark sich die Wahrscheinlichkeitsverteilung auf X im Durchschnitt ändert, wenn uns der Wert von Y gegeben wird . Dies wird oft als Abweichung vom Produkt der Randverteilungen zur tatsächlichen gemeinsamen Verteilung umgerechnet:

Gegenseitige Informationen stehen in engem Zusammenhang mit dem Log-Likelihood-Ratio-Test im Kontext von Kontingenztafeln und der Multinomialverteilung sowie mit dem Pearson- 2- Test : gegenseitige Informationen können als Statistik zur Bewertung der Unabhängigkeit zwischen einem Variablenpaar betrachtet werden und haben eine gute spezifizierte asymptotische Verteilung.

Kullback-Leibler-Divergenz (Informationsgewinn)

Die Kullback-Leibler-Divergenz (oder Informationsdivergenz , Informationsgewinn oder relative Entropie ) ist eine Möglichkeit, zwei Verteilungen zu vergleichen: eine "echte" Wahrscheinlichkeitsverteilung und eine willkürliche Wahrscheinlichkeitsverteilung . Wenn wir Daten auf eine Weise komprimieren, die davon ausgeht, dass es sich um die Verteilung handelt, die einigen Daten zugrunde liegt, obwohl dies in Wirklichkeit die richtige Verteilung ist, ist die Kullback-Leibler-Divergenz die Anzahl der durchschnittlichen zusätzlichen Bits pro Datum, die für die Komprimierung erforderlich sind. Es ist so definiert

Obwohl sie manchmal als „Entfernungsmetrik“ verwendet wird, ist die KL-Divergenz keine echte Metrik, da sie nicht symmetrisch ist und die Dreiecksungleichung nicht erfüllt (was sie zu einer Semiquasimetrie macht).

Eine andere Interpretation der KL-Divergenz ist die "unnötige Überraschung", die ein Prior von der Wahrheit einführt: Angenommen, eine Zahl X soll zufällig aus einer diskreten Menge mit Wahrscheinlichkeitsverteilung gezogen werden . Wenn Alice die wahre Verteilung kennt , während Bob glaubt (hat einen Vorrang ), dass die Verteilung ist , dann wird Bob im Durchschnitt überraschter sein als Alice, wenn er den Wert von X sieht . Die KL Divergenz ist der (objektive) Erwartungswert von Bob (subjektiven) surprisal minus Alices surprisal, gemessen in Bit , wenn das Protokoll ist in der Basis 2. Auf diese Weise wird das Ausmaß , in dem Bob vor ist „falsch“ kann in Form quantifiziert werden wie "unnötig überrascht" es ihn machen soll.

Andere Mengen

Andere wichtige informationstheoretische Größen sind die Rényi-Entropie (eine Verallgemeinerung der Entropie), die differentielle Entropie (eine Verallgemeinerung von Informationsmengen auf kontinuierliche Verteilungen) und die bedingte gegenseitige Information .

Codierungstheorie

Ein Bild mit Kratzern auf der lesbaren Oberfläche einer CD-R. Musik- und Daten-CDs sind mit Fehlerkorrekturcodes kodiert und können so auch mit kleinen Kratzern durch Fehlererkennung und -korrektur noch gelesen werden .

Die Codierungstheorie ist eine der wichtigsten und direktesten Anwendungen der Informationstheorie. Sie kann in Quellencodierungstheorie und Kanalcodierungstheorie unterteilt werden. Unter Verwendung einer statistischen Beschreibung für Daten quantifiziert die Informationstheorie die Anzahl von Bits, die zum Beschreiben der Daten benötigt werden, was die Informationsentropie der Quelle ist.

  • Datenkomprimierung (Quellcodierung): Für das Komprimierungsproblem gibt es zwei Formulierungen:
  • Fehlerkorrigierende Codes (Kanalcodierung): Während die Datenkompression so viel Redundanz wie möglich entfernt, fügt ein fehlerkorrigierender Code genau die richtige Art von Redundanz (dh Fehlerkorrektur) hinzu, die benötigt wird, um die Daten effizient und zuverlässig über einen verrauschten Kanal zu übertragen.

Diese Aufteilung der Codierungstheorie in Kompression und Übertragung wird durch die Informationsübertragungstheoreme oder Quellen-Kanal-Trennungstheoreme begründet, die die Verwendung von Bits als universelle Währung für Informationen in vielen Kontexten rechtfertigen. Diese Theoreme gelten jedoch nur in der Situation, in der ein sendender Benutzer mit einem empfangenden Benutzer kommunizieren möchte. In Szenarien mit mehr als einem Sender (der Multiple-Access-Kanal), mehr als einem Empfänger (dem Broadcast-Kanal ) oder zwischengeschalteten "Helfern" (der Relay-Kanal ) oder allgemeineren Netzwerken , ist die Kompression gefolgt von der Übertragung möglicherweise nicht mehr optimal. Die Netzwerkinformationstheorie bezieht sich auf diese Multi-Agenten-Kommunikationsmodelle.

Quellentheorie

Jeder Prozess, die aufeinanderfolgende Nachrichten erzeugt , kann eine in Betracht gezogen wird Quelle von Informationen. Eine gedächtnislose Quelle ist eine Quelle, bei der jede Nachricht eine unabhängige, identisch verteilte Zufallsvariable ist , während die Eigenschaften der Ergodizität und Stationarität weniger restriktive Beschränkungen auferlegen. Alle diese Quellen sind stochastisch . Diese Begriffe werden für sich genommen außerhalb der Informationstheorie gut untersucht.

Rate

Informationsrate ist die durchschnittliche Entropie pro Symbol. Bei gedächtnislosen Quellen ist dies lediglich die Entropie jedes Symbols, bei einem stationären stochastischen Prozess ist dies

das heißt, die bedingte Entropie eines Symbols, wenn alle zuvor erzeugten Symbole gegeben sind. Für den allgemeineren Fall eines Prozesses, der nicht notwendigerweise stationär, das ist durchschnittliche Rate ist ,

das heißt, die Grenze der gemeinsamen Entropie pro Symbol. Für stationäre Quellen liefern diese beiden Ausdrücke das gleiche Ergebnis.

Informationsrate ist definiert als

In der Informationstheorie ist es üblich, von der "Rate" oder "Entropie" einer Sprache zu sprechen. Dies ist beispielsweise dann sinnvoll, wenn die Informationsquelle englische Prosa ist. Die Rate einer Informationsquelle hängt mit ihrer Redundanz und ihrer Komprimierbarkeit zusammen, dem Thema der Quellcodierung .

Kanalkapazität

Die Kommunikation über einen Kanal ist die Hauptmotivation der Informationstheorie. Kanäle erzeugen jedoch oft keine genaue Rekonstruktion eines Signals; Rauschen, Stilleperioden und andere Formen der Signalverfälschung verschlechtern oft die Qualität.

Betrachten Sie den Kommunikationsprozess über einen diskreten Kanal. Ein einfaches Modell des Prozesses ist unten dargestellt:

Hier repräsentiert X den Raum der gesendeten Nachrichten und Y den Raum der während einer Zeiteinheit über unseren Kanal empfangenen Nachrichten. Lassen p ( y | x ) , die seine bedingte Wahrscheinlichkeitsverteilungsfunktion von Y angegeben X . Wir betrachten p ( y | x ) als eine inhärente feste Eigenschaft unseres Kommunikationskanals (die die Natur des Rauschens unseres Kanals darstellt). Dann wird die gemeinsame Verteilung von X und Y vollständig durch unseren Kanal und durch unsere Wahl von f ( x ) bestimmt , der marginalen Verteilung von Nachrichten, die wir über den Kanal senden. Unter diesen Einschränkungen möchten wir die Informationsrate oder das Signal maximieren , das wir über den Kanal kommunizieren können. Das geeignete Maß hierfür ist die gegenseitige Information, und diese maximale gegenseitige Information wird Kanalkapazität genannt und ist gegeben durch:

Diese Kapazität hat die folgende Eigenschaft in Bezug auf die Kommunikation mit der Informationsrate R (wobei R normalerweise Bits pro Symbol ist). Für jede Informationsrate R < C und Codierfehler ε > 0 gibt es für genügend große N einen Code der Länge N und der Rate ≥ R und einen Decodieralgorithmus, so dass die maximale Wahrscheinlichkeit eines Blockfehlers ≤ ε ist ; das heißt, es ist immer möglich, mit beliebig kleinem Blockfehler zu senden. Außerdem ist es für jede Rate R > C unmöglich, mit einem beliebig kleinen Blockfehler zu senden.

Die Kanalcodierung beschäftigt sich damit, solche nahezu optimalen Codes zu finden, die verwendet werden können, um Daten über einen verrauschten Kanal mit einem kleinen Codierungsfehler mit einer Rate nahe der Kanalkapazität zu übertragen.

Kapazität bestimmter Kanalmodelle

  • Ein zeitkontinuierlicher analoger Kommunikationskanal, der einem Gaußschen Rauschen unterliegt – siehe das Shannon-Hartley-Theorem .
  • Ein binärer symmetrischer Kanal (BSC) mit einer Überkreuzungswahrscheinlichkeit p ist ein binärer Eingangs- und ein binärer Ausgangskanal, der das Eingangsbit mit der Wahrscheinlichkeit p umkehrt . Die BSC hat eine Kapazität von 1 − H b ( p ) Bits pro Kanalnutzung, wobei H b die binäre Entropiefunktion zum Basis-2-Logarithmus ist:
Binärer symmetrischer Kanal.svg
  • Ein binärer Löschkanal (BEC) mit Löschwahrscheinlichkeit p ist ein binärer Eingangs-, ternärer Ausgangskanal. Die möglichen Kanalausgaben sind 0, 1 und ein drittes Symbol 'e', ​​das als Löschung bezeichnet wird. Das Löschen stellt einen vollständigen Informationsverlust über ein Eingabebit dar. Die Kapazität des BEC beträgt 1 – p Bits pro Kanalnutzung.
Binärer Löschkanal.svg

Kanäle mit Gedächtnis und gezielter Information

In der Praxis haben viele Kanäle Speicher. Der Kanal ist nämlich zur Zeit durch die bedingte Wahrscheinlichkeit gegeben . Es ist oft bequemer, die Notation zu verwenden und den Kanal zu verwenden . In einem solchen Fall wird die Kapazität durch die gegenseitige Informationsrate gegeben , wenn keine Rückkopplung verfügbar ist und die gerichtete Informationsrate für den Fall, dass entweder eine Rückkopplung vorliegt oder nicht (wenn keine Rückkopplung vorhanden ist, ist die gerichtete Information gleich der gegenseitigen Information).

Bewerbungen in anderen Bereichen

Geheimdienstanwendungen und Geheimhaltungsanwendungen

Informationstheoretische Konzepte gelten für Kryptographie und Kryptoanalyse. Turings Informationseinheit, das Verbot , wurde im Ultra- Projekt verwendet, um den deutschen Enigma-Maschinencode zu knacken und das Ende des Zweiten Weltkriegs in Europa zu beschleunigen . Shannon selbst definierte ein wichtiges Konzept, das heute als Einheitsdistanz bezeichnet wird . Basierend auf der Redundanz des Klartextes wird versucht, eine minimale Menge an Geheimtext bereitzustellen, die erforderlich ist, um eine eindeutige Entzifferbarkeit zu gewährleisten.

Die Informationstheorie lässt uns glauben, dass es viel schwieriger ist, Geheimnisse zu bewahren, als es zunächst erscheinen mag. Ein Brute-Force-Angriff kann Systeme zerstören, die auf asymmetrischen Schlüsselalgorithmen oder auf den am häufigsten verwendeten Methoden von symmetrischen Schlüsselalgorithmen (manchmal als geheime Schlüsselalgorithmen bezeichnet) wie Blockchiffren basieren . Die Sicherheit all dieser Methoden beruht derzeit auf der Annahme, dass kein bekannter Angriff sie in praktischer Zeit brechen kann.

Informationstheoretische Sicherheit bezieht sich auf Methoden wie das One-Time-Pad , die nicht anfällig für solche Brute-Force-Angriffe sind. In solchen Fällen kann die positive bedingte gegenseitige Information zwischen Klartext und Geheimtext (konditioniert auf dem Schlüssel ) eine ordnungsgemäße Übertragung gewährleisten, während die unbedingte gegenseitige Information zwischen Klartext und Geheimtext null bleibt, was zu einer absolut sicheren Kommunikation führt. Mit anderen Worten, ein Lauscher wäre nicht in der Lage, seine Schätzung des Klartextes zu verbessern, indem er Kenntnis des Geheimtextes, aber nicht des Schlüssels erlangt. Wie bei jedem anderen kryptographischen System ist jedoch auch bei informationstheoretisch sicheren Verfahren Vorsicht geboten; das Venona-Projekt konnte die einstigen Pads der Sowjetunion durch unsachgemäße Wiederverwendung von Schlüsselmaterial knacken.

Pseudozufallszahlenerzeugung

Generatoren für Pseudozufallszahlen sind in Computersprachenbibliotheken und Anwendungsprogrammen weit verbreitet. Sie sind fast überall für die kryptographische Verwendung ungeeignet, da sie sich der deterministischen Natur moderner Computerausrüstung und Software nicht entziehen. Eine Klasse verbesserter Zufallszahlengeneratoren wird als kryptographisch sichere Pseudozufallszahlengeneratoren bezeichnet , aber selbst sie erfordern Zufalls-Seeds außerhalb der Software, um wie beabsichtigt zu funktionieren. Diese können bei sorgfältiger Ausführung über Extraktoren gewonnen werden. Das Maß für ausreichende Zufälligkeit in Extraktoren ist die Min-Entropie , ein Wert, der sich auf die Shannon-Entropie durch die Rényi-Entropie bezieht ; Die Rényi-Entropie wird auch bei der Bewertung der Zufälligkeit in kryptographischen Systemen verwendet. Obwohl verwandt, bedeuten die Unterschiede zwischen diesen Maßen, dass eine Zufallsvariable mit hoher Shannon-Entropie für die Verwendung in einem Extraktor und damit für Kryptographieanwendungen nicht unbedingt zufriedenstellend ist.

Seismische Erkundung

Eine frühe kommerzielle Anwendung der Informationstheorie lag im Bereich der seismischen Ölexploration. Die Arbeit auf diesem Gebiet ermöglichte es, das unerwünschte Rauschen vom gewünschten seismischen Signal abzutrennen und zu trennen. Informationstheorie und digitale Signalverarbeitung bieten eine wesentliche Verbesserung der Auflösung und Bildschärfe gegenüber früheren analogen Verfahren.

Semiotik

Semiotikern Doede Nauta und Winfried Nöth beide als Charles Sanders Peirce als eine Theorie der Informationen in seinen Werken auf Semiotik geschaffen zu haben. Nauta definierte die semiotische Informationstheorie als das Studium „der internen Prozesse der Codierung, Filterung und Informationsverarbeitung“.

Konzepte der Informationstheorie wie Redundanz und Codekontrolle wurden von Semiotikern wie Umberto Eco und Ferruccio Rossi-Landi verwendet , um Ideologie als eine Form der Nachrichtenübermittlung zu erklären, bei der eine dominante soziale Schicht ihre Botschaft durch die Verwendung von Zeichen aussendet, die ein hohes Maß an Redundanz, so dass nur eine Nachricht unter einer Auswahl konkurrierender Nachrichten decodiert wird.

Sonstige Anwendungen

Die Informationstheorie hat auch Anwendungen im Glücksspiel und in der Informationstheorie , in Schwarzen Löchern und in der Bioinformatik .

Siehe auch

Anwendungen

Geschichte

Theorie

Konzepte

Verweise

Das klassische Werk

Andere Zeitschriftenartikel

  • JL Kelly, Jr., Princeton , "Eine neue Interpretation der Informationsrate" Bell System Technical Journal , Vol. 2, No. 35, Juli 1956, S. 917–26.
  • R. Landauer, IEEE.org , "Information is Physical" Proc. Workshop on Physics and Computation PhysComp'92 (IEEE Comp. Sci.Press, Los Alamitos, 1993) S. 1–4.
  • Landauer, R. (1961). "Irreversibilität und Wärmeentwicklung im Rechenprozess" (PDF) . IBM J. Res. Abw . 5 (3): 183–191. doi : 10.1147/rd.53.0183 .
  • Timme, Nikolaus; Alford, Wesley; Flecker, Benjamin; Beggs, John M. (2012). „Multivariate Informationsmaße: die Perspektive eines Experimentators“. arXiv : 1111.6857 [ cs.IT ].

Lehrbücher zur Informationstheorie

Andere Bücher

MOOC zur Informationstheorie

Externe Links