In Vorletzter Artikel habe ich das "Holebo-Limit" aufgegriffen und das Limit des Quantenkommunikationskanals erklärt. Die damalige Annahme war die Geschichte eines Kommunikationspfades namens "klassisch-quantenklassisch", in dem klassische Informationen mit Quantenbits codiert und übertragen werden und klassische Informationen durch POVM-Messung auf der Empfangsseite decodiert werden. Dieses Mal möchte ich stattdessen über die Übertragung des Quantenzustands selbst als "Information" sprechen. In der klassischen Informationstheorie von Shannon gibt es einen berühmten Satz, dass, wenn die Natur (Wahrscheinlichkeitsverteilung) einer Informationsquelle bekannt ist, die minimal erforderliche Kommunikationskapazität bestimmt wird und die Quantenversion dieses Satzes von Schumacher bewiesen wurde. Ich möchte es schaffen, das zu verstehen. Es wird ein bisschen lang, also werde ich es in zwei Teile teilen. Dieses Mal wird zum ersten Mal als Voraussetzung für das Wissen "Shannons Codierungssatz in einem rauschfreien Kanal" in der klassischen Informationstheorie erklärt, und zum zweiten Mal wird das Hauptthema "Schumachers Code in einem rauschfreien Quantenkanal" erklärt. Ich werde den chemischen Satz erklären. Sobald ich es verstanden habe, werde ich jedes Mal versuchen, sein Codierungsverhalten mit einem Python-Programm zu simulieren [^ 1].
[^ 1]: Übrigens habe ich jetzt das Wort "Codierung" verwendet, aber Sie können es als Synonym für "Datenkomprimierung" betrachten. "Codierung" ist die Umwandlung von Informationen in eine Bitfolge. Zu diesem Zeitpunkt möchten wir so effizient wie möglich "kommunizieren" und "speichern", dh mit weniger Ressourcen. Dies schuf die Motivation, Informationen so weit wie möglich zu "komprimieren", und seit Shannon wird seit vielen Jahren geforscht. Um es etwas laut auszudrücken, ich denke, dass "Datenkomprimierung" einer der Zwecke der "Codierung" ist, aber da es sich um einen sehr großen Zweck handelt, wird es in verschiedenen Kontexten in fast derselben Bedeutung verwendet. Ich denke, dass es die aktuelle Situation ist. Auch dieses Mal haben wir es auf "kein Rauschen" beschränkt, aber natürlich kann es "laut" sein. Ich habe noch nicht studiert. Wenn ich es verstehen kann, möchte ich es noch einmal vorstellen (der Zeitplan ist unentschlossen).
Die folgenden Dokumente wurden als Referenz verwendet.
Kurz gesagt, ich möchte die Antwort auf die Frage betrachten, wie viele Daten im Prinzip komprimiert werden können, wenn die Art der Informationsquelle dies ist. Daher ist es notwendig, schwer fassbare Informationen zu abstrahieren, zu modellieren und mathematisch zu verarbeiten. Die Vereinfachung der Erfassung der Essenz kann geringfügig von den tatsächlichen Informationen abweichen, aber wenn sie praktisch nützliche Ergebnisse liefert, ist dies auch gut. Basierend auf dieser Idee abstrahieren und modellieren wir zunächst die Informationsquelle.
Stellen Sie sich beispielsweise Textinformationen in Englisch vor, die aus alphabetischen Zeichenfolgen bestehen. Als es einen englischen Satz "Ich habe einen Traum" gab, waren die alphabetischen Zeichen "I", "$ \ space $", "h", "a", "v", "e" ... Es ist ersichtlich, dass es in chronologischer Reihenfolge auftritt. Es gibt viele andere englische Sätze auf der Welt, und wenn man sie betrachtet, gibt es Buchstaben, die leicht vorkommen (wie "e" und "a") und Buchstaben, die selten generiert werden (wie "q" und "z"). Da es [^ 2] gibt, besteht eine Idee der Abstraktion / Modellierung darin, die alphabetischen Zeichen, die zu jedem Zeitpunkt auftreten, als Wahrscheinlichkeitsvariablen [^ 3] zu betrachten. Es scheint eine natürliche Annahme zu sein, dass die Wahrscheinlichkeiten für diese alphabetischen Zeichen jederzeit gleich sind, und sogar mit der Annahme, dass alphabetische Zeichen, die zu unterschiedlichen Zeiten auftreten, unabhängig voneinander auftreten. Sieht gut aus [^ 4]. Auf diese Weise wird die Informationsquelle, die davon ausgeht, dass die von der Informationsquelle getrennt erzeugten Werte unabhängig voneinander sind und derselben Verteilung folgen (identisch verteilt), als "iid-Informationsquelle (unabhängige und identisch verteilte Informationsquelle)" bezeichnet. Wird genannt. Auf dieser Grundlage werden wir mit den folgenden Diskussionen fortfahren.
[^ 2]: Referenz: Zeichenhäufigkeitstabelle
[^ 3]: "Ich habe einen Traum." Ist eine Passage aus der berühmten Rede von Martin Luther King Jr., und ich denke, viele Leute haben sie im Englischunterricht gelesen oder gehört. Egal wie oft ich es höre, die Rede ist berührend und es gibt etwas, das vermittelt werden kann, wenn man sich nur diese Passage ansieht: „Ich habe einen Traum.“ Was er zu sagen versuchte. Von nun an werde ich erklären, dass wir alle diese Implikationen wegwerfen, abstrahieren und Informationen als mathematisches Objekt erfassen sollten. Das ist die Informationstheorie, mit der Shannon begonnen hat. Es ist eine sehr coole Position, aber sie hat die Welt sehr verändert. Ich werde auf das Video der Rede verlinken. Es sind ungefähr 11 Minuten und 40 Sekunden, in denen "Ich habe einen Traum". [Japanische Untertitel] Rev. Kings Rede "Ich habe einen Traum" - Martin Luther King "Ich habe einen Traum"
[^ 4]: Wenn Sie sich Englisch vorstellen, ist es nicht genau. Zum Beispiel ist die Wahrscheinlichkeit, dass "h" nach "t" kommt, höher als in anderen Fällen. In vielen Quellen scheint es jedoch nicht so falsch zu sein, selbst wenn Sie eine so grobe Annahme machen. Es ist auch üblich, mit den einfachsten Annahmen zu beginnen und schrittweise über komplexere nachzudenken, um eine Theorie zu erstellen. Beginnen wir also mit einer so einfachen Annahme.
Vor Shannons Codierungssatz müssen die Konzepte "typischer Reihen" und "atypischer Reihen" erläutert werden. Angenommen, die i.i.d.-Quelle erstellt die stochastischen Variablen $ X_1, X_2, X_3, \ cdots $. Sie können sich beispielsweise das Phänomen des Werfens einer Münze und die Frage, ob sie vorne oder hinten herauskommt, als stochastische Variable vorstellen und sich vorstellen, sie immer wieder zu wiederholen, um eine Reihe von Vorder- und Rückseite zu erstellen. Wenn Sie die Nummern "0" für die Vorderseite und "1" für die Rückseite zuweisen, ist die Serie eine binäre Serie. Wenn es sich um eine gewöhnliche Münze handelt, treten sowohl die Vorder- als auch die Rückseite mit einer Wahrscheinlichkeit von 1/2 auf, aber ich möchte sie so allgemein wie möglich diskutieren, vorausgesetzt, die Münze wird so hergestellt, dass die Wahrscheinlichkeit, dass die Vorderseite erscheint, $ p $ beträgt Stellen. Trotzdem ist es eine natürliche Annahme, dass sie "identisch verteilt" sind, weil sie jedes Mal die gleichen Münzen werfen. Welches herauskommt, hängt auch nicht von den Ergebnissen der Vergangenheit ab (da es beispielsweise das letzte Mal die "Tabelle" war, bedeutet dies nicht, dass die "Tabelle" dieses Mal leicht herauskommt), so dass "unabhängig" auch seltsam ist. Keine Annahme. Daher können die durch das Werfen von Münzen erhaltenen Informationen als i. D. Informationsquelle angesehen werden.
Wenn Sie $ n $ Wahrscheinlichkeitsvariablen $ X_1, X_2, \ cdots, X_n $ aus dieser unendlichen Reihe von iid-Quellen herausnehmen, sind die tatsächlichen Werte $ x_1, x_2, \ cdots, x_n $ Es gibt viele Möglichkeiten, aber es kann in Serienmuster, die wahrscheinlich auftreten, und Serienmuster, die selten auftreten, unterteilt werden. Eine Sequenz, die wahrscheinlich auftritt, wird als "typische Sequenz" bezeichnet, und eine Sequenz, die selten auftritt, wird als "atypische Sequenz" bezeichnet. Die Wahrscheinlichkeit, 0 zu erhalten, sei $ p = 1/4 $, und die Anzahl der abzurufenden Serien sei $ n = 100 $. Dann können Sie sich vorstellen, dass die Ausgabe von 0 ungefähr 25 Mal beträgt. Selbst wenn Sie diese 100 Proben mehrmals wiederholen, wird es wahrscheinlich zu Schütteln kommen, und die Anzahl der Nullen sollte etwa 25 Mal konzentriert werden. Im Gegenteil, wenn es nur 5 oder 85 Mal gibt, ist dies entweder ein sehr ungewöhnliches Phänomen oder die Person, die die Münze wirft, ist ein Tintenfischmeister. In diesem Beispiel wird eine Reihe, in der 0 etwa 25 Mal vorkommt, als "typische Reihe" bezeichnet.
Ich sagte, dass die typische Reihe eine Reihe ist, die leicht vorkommt, aber wie kann die Wahrscheinlichkeit quantifiziert werden? Wenn die Wahrscheinlichkeit, die Reihe $ x_1, x_2, \ cdots, x_n $ durch Abtasten von n Stücken aus der stochastischen Variablenserie zu erhalten, $ p (x_1, x_2, \ cdots, x_n) $ beträgt, handelt es sich um eine iid-Informationsquelle. ,
p(x_1,x_2,\cdots,x_n) = p(x_1)p(x_2) \cdots p(x_n) \approx p^{np} (1-p)^{n(1-p)} \tag{1}
Es wird sein. Wenn Sie den Logarithmus beider Seiten nehmen,
-\log p(x_1,x_2,\cdots,x_n) \approx -np \log p - n(1-p) \log (1-p) = n H(X) \tag{2}
Damit
p(x_1,x_2,\cdots,x_n) \approx 2^{-nH(X)} \tag{3}
Sie kann mit Entropie angenähert werden. Hier wurde Gleichung (3) abgeleitet, indem zwei Werte vorgestellt wurden, bei denen die Wahrscheinlichkeitsvariablen nur die Werte "0" und "1" annehmen, aber sie gelten auch dann, wenn es mehrere Werte gibt. Ich werde es beweisen.
[Beweis]
Probabilistische Variable
p(x_1,x_2,\cdots,x_n) = p(x_1)p(x_2) \cdots p(x_n) \tag{4}
Auch die funktionale Form von $ p (x_i) $ ist dieselbe. Die Wahrscheinlichkeit $ p (a_ {\ mu}) $, wenn $ x_i = a_ {\ mu} $ ist, ist $ N (a_), wie oft $ a_ {\ mu} $ in der $ n $ -Serie erscheint. Wenn Sie {\ mu}) $ schreiben,
p(a_{\mu}) \approx \frac{N(a_{\mu})}{n} \tag{5}
Kann angenähert werden an. Dann
p(x_1,x_2,\cdots,x_n) \approx \prod_{\mu=1}^{|A|} p(a_{\mu})^{N(a_{\mu})} = \prod_{\mu=1}^{|A|} p(a_{\mu})^{np(a_{\mu})} \tag{6}
Es wird sein. Wenn Sie den Logarithmus beider Seiten nehmen,
- \log p(x_1,x_2,\cdots,x_n) \approx \sum_{\mu=1}^{|A|} np(a_\mu) \log p(a_{\mu}) = nH(X) \tag{7}
Damit
p(x_1,x_2,\cdots,x_n) \approx 2^{-nH(X)} \tag{8}
Dann könnte Gleichung (3) auf die gleiche Weise bewiesen werden. (Ende der Zertifizierung)
Da die Umkehrung der Wahrscheinlichkeit die Zahl ist, wenn sie auftritt, können Sie denken, dass die Anzahl der typischen Reihen ungefähr $ 2 ^ {nH (X)} $ beträgt. Dies bedeutet, dass die meisten Informationen ohne Fehler übertragen werden können, wenn der Code von $ nH (X) $ Bits vorbereitet wird, wenn man bedenkt, dass die Informationsquelle in n Blöcke unterteilt und codiert ist. .. Natürlich können atypische Serien auftreten. Geben Sie in diesem Fall auf und weisen Sie einen geeigneten Code zu. Dann tritt ein Übertragungsfehler mit einer bestimmten Rate auf, aber wenn n groß genug gemacht wird, kann die Rate klein genug gemacht werden, und am Ende kann eine zuverlässige Kommunikation realisiert werden. Genau das hat Shannon bewiesen. Bevor wir auf diesen Beweis eingehen, brauchen wir ein etwas tieferes Verständnis der typischen Serien, also lassen Sie uns darüber sprechen.
Wenn $ \ epsilon> 0 $ angegeben ist,
2^{-n(H(X)+\epsilon)} \leq p(x_1,x_2,\cdots,x_n) \leq 2^{-n(H(X)-\epsilon)} \tag{9}
Die Reihe, die $ x_1, x_2, \ cdots, x_n $ erfüllt, wird als "$ \ epsilon $ typische Reihe" bezeichnet. Die Menge aller solcher $ \ epsilon $ typischen Reihen der Länge $ n $ wird als $ T (n, \ epsilon) $ dargestellt. Gleichung (9)
| \frac{1}{n} \log \frac{1}{p(x_1,x_2,\cdots,x_n)} - H(X) | \leq \epsilon \tag{10}
Es kann umgeschrieben werden als. Damit konnten wir die vage definierten typischen Reihen quantifizieren, so dass sie mathematisch gehandhabt werden können. Als nächstes werde ich drei Sätze über typische Reihen der Reihe nach erklären.
Die Beschreibung von Neilsen, Chan wird so wie sie ist zitiert.
"Fix $ \ epsilon> 0 $. Für jedes $ \ delta> 0 $, ein ausreichend großes $ n $, beträgt die Wahrscheinlichkeit, dass der String $ \ epsilon $ ist, mindestens $ 1- \ delta $. ""
Nun, ich denke, es gibt viele Leute, die überhaupt nicht verstehen, was sie sagen, also werde ich ein wenig kauen. $ \ Epsilon $ ist $ \ epsilon $, das den Bereich typischer Serien bestimmt. Angenommen, Sie beheben dieses $ \ epsilon $. Denken Sie an eine geeignete positive Zahl in Ihrem Kopf (z. B. 0,1). Dann erscheint ein weiteres $ \ delta $. Dies kann als beliebiger positiver Wert eingestellt werden. Dieser Satz besagt, dass unabhängig davon, für welches $ \ delta> 0 $ Sie sich entscheiden, wenn Sie $ n $ groß genug nehmen, eine Reihe von $ n $ Länge zu einer typischen Reihe von $ \ epsilon $ wird. Die Wahrscheinlichkeit beträgt mindestens $ 1- \ Delta $. Wenn beispielsweise $ \ delta $ auf einen relativ großen Wert gesetzt wird (z. B. 0,999), erscheint die Behauptung dieses Theorems ganz offensichtlich. Da die Wahrscheinlichkeit, ein typisches $ \ epsilon $ zu werden, sehr gering ist = ein sehr lockerer Zustand, denke ich, dass es zu gelten scheint, auch wenn es kein so großes $ n $ ist. Was ist andererseits, wenn der Wert von $ \ delta $ sehr klein ist (z. B. 0,000001)? Der Anspruch dieses Satzes ist sehr streng. Weil es heißt, dass die Wahrscheinlichkeit, typisch für $ \ epsilon $ zu werden, fast 1 beträgt. Der Wert von $ n $ kann jedoch groß genug sein. Wenn Sie $ n $ groß genug nehmen, können Sie die Wahrscheinlichkeit, typisch für $ \ epsilon $ zu werden, größer oder gleich $ 1- \ delta $ machen (dh nahe genug an 1). Das sagt dieser Satz. Kurz gesagt, es ist eine sehr einfache Geschichte: Wenn Sie $ n $ groß genug nehmen, ist jede Serie eine typische $ \ epsilon $ -Serie. Stellen Sie sich ein Experiment vor, bei dem Sie würfeln und die Augen aufzeichnen, die herauskommen. Auch wenn es sich nach 10 Umdrehungen nicht um eine typische Serie handelt, muss es sich um eine typische Serie handeln, wenn sie 100-mal oder 1000-mal gewalzt wird. Sie sagen das nur mathematisch genau. Lass es uns beweisen.
[Beweis]
$ X_1, X_2, \ cdots $ ist eine Reihe von stochastischen Variablen, die aus der i.i.d.-Quelle erhalten wurden. Da $ p (X_i) $ unabhängig ist und dieselbe Verteilung hat, ist $ - \ log p (X_i) $ ebenfalls unabhängig und hat dieselbe Verteilung. Dies bedeutet, dass der erwartete Wert von $ - \ log p (X) $ $ E (-log p (X)) $ ist, wenn $ n $ $ - \ log p (X_i) $ herausgenommen werden. Sie kann dem Durchschnittswert angenähert werden. Das heißt, für jedes $ \ epsilon> 0, \ delta> 0 $
p(| \sum_{i=1}^{n} \frac{- \log p(X_i)}{n} - E(- \log p(X)) | \leq \epsilon) \geq 1-\delta \tag{11}
Es gibt immer $ n> 0 $, das gilt. Ist das okay? Egal wie klein $ \ epsilon $ oder $ \ delta $ Sie nehmen, wenn Sie $ n $ groß genug nehmen, können Sie die obige Gleichung erfüllen. Mit anderen Worten, wenn Sie $ n $ groß genug nehmen, können Sie $ E (- \ log p (X)) = \ sum_ {i = 1} ^ {n} \ frac {- \ log p (X_i)} {n} $ machen Dies ist also nur eine Umschreibung des sogenannten "Mehrheitsgesetzes".
Hier,
\begin{align}
& E(- \log p(X)) = H(X) \\
& \sum_{i=1}^{n} \log p(X_i) = \log(p(X_1,X_2,\cdots,X_n)) \tag{12}
\end{align}
Gleichung (11) lautet also
p(| - \frac{\log(p(X_1,X_2,\cdots,X_n))}{n} - H(X) | \leq \epsilon) \geq 1-\delta \tag{13}
Es wird sein. Da der Inhalt von $ p $ auf der linken Seite die Definition der typischen $ \ epsilon $ -Serie selbst ist, drückt Gleichung (13) aus, dass die Wahrscheinlichkeit, eine $ \ epsilon $ typische Serie zu sein, mindestens $ 1- \ delta $ beträgt. Also konnte ich es beweisen. (Ende der Zertifizierung)
Die Beschreibung von Neilsen, Chan wird zitiert.
"Irgendwelche behoben
(1-\delta) 2^{n(H(X)-\epsilon)} \leq |T(n,\epsilon)| \leq 2^{n(H(X)+\epsilon)} \tag{14}
」
Mit anderen Worten,
[Beweis]
Gleichung (9) für die Wahrscheinlichkeit, dass die Reihe $ x = (x_1, x_2, \ cdots, x_n) $ auftritt und die Wahrscheinlichkeit 1 nicht überschreitet.
1 \geq \sum_{x \in T(n,\epsilon)} p(x) \geq \sum_{x \in T(n,\epsilon)} 2^{-n(H(X)+\epsilon)} = |T(n,\epsilon)| 2^{-n(H(X)+\epsilon)} \tag{15}
Damit
|T(n,\epsilon)| \leq 2^{n(H(X)+\epsilon)} \tag{16}
Ist festgelegt. Dies beweist die Ungleichung auf der rechten Seite von Gleichung (14). Als nächstes kommt die Ungleichung auf der linken Seite.
Aus dem typischen Reihensatz (1) und Gleichung (9)
1-\delta \leq \sum_{x \in T(n,\epsilon)} p(x) \leq \sum_{x \in T(n,\epsilon)} 2^{-n(H(X)-\epsilon)} = |T(n,\epsilon)| 2^{-n(H(X)-\epsilon)} \tag{17}
Damit
(1-\delta) 2^{n(H(X)-\epsilon)} \leq |T(n,\epsilon)| \tag{18}
Ist festgelegt. Die Kombination der Gleichungen (16) und (18) ergibt die Gleichung (14). (Ende der Zertifizierung)
Die Beschreibung von Neilsen, Chan wird zitiert.
"$ S (n) $ ist eine Sammlung von Zeichenfolgen mit der Länge $ n $ aus der Quelle, und ihre Größe beträgt höchstens $ 2 ^ {nR} $. Wobei $ R \ <H (X) $ Ist fest. Zu diesem Zeitpunkt gilt die folgende Gleichung für jedes $ \ delta > 0 $ und ausreichend große $ n $.
\sum_{x \in S(n)} p(x) \leq \delta \tag{19}
」
Die Anzahl der typischen Serien beträgt ungefähr $ 2 ^ {nH (X)} $, aber bei Verwendung von $ R $, das kleiner als $ H (X) $ ist, gibt es nur ungefähr $ 2 ^ {nR} $ Teilmengen. Denken Sie an $ S (n) $. Es wird behauptet, dass, wenn $ n $ groß genug gemacht wird, der Anteil von $ S (n) $, der in der Reihe von Längen $ n $ enthalten ist, ausreichend klein sein wird. Bei der Grenze von $ n \ bis \ infty $ konvergiert der Anteil gegen 0. ist das wahr? Vielleicht möchten Sie das sagen, aber es ist wahr. Ich werde es unten beweisen. Bitte genießen Sie die Kraft der Kraft von 2.
[Beweis]
Betrachten Sie die Zeichenfolge $ S (n) $ getrennt für typische und atypische Reihen. Nach dem kanonischen Reihensatz (1) ist, wenn $ n $ ausreichend groß ist, die Anzahl der atypischen Reihen, die in der Reihenmenge der Länge $ n $ enthalten sind, ausreichend klein, so dass ihre Teilmenge $ S (n) Die Anzahl der in) $ enthaltenen atypischen Reihen ist ebenfalls klein genug. Es ist 0 im Limit von $ n \ bis \ infty $.
Andererseits ist die Anzahl der in $ S (n) $ enthaltenen typischen Serien kleiner oder gleich der Anzahl der in $ S (n) $ enthaltenen Serien. Mit anderen Worten, es ist nur $ 2 ^ {nR} $. Da die Auftrittswahrscheinlichkeit der typischen Reihe $ 2 ^ {-nH (X)} $ betrug, beträgt die Wahrscheinlichkeit des Auftretens von $ S (n) $ höchstens $ 2 ^ {n (R-H (X))} $. Das heißt, für ein ausreichend großes $ n $
\sum_{x \in S(n)} p(x) \leq 2^{n(R-H(X))} \tag{20}
ist. Nun, da $ R <H (X) $, für jedes $ \ delta> 0 $
\sum_{x \in S(n)} p(x) \leq \delta \tag{21}
Es gibt $ n> 0 $, das erfüllt. Mit anderen Worten, an der Grenze von $ n \ bis \ infty $,
\sum_{x \in S(n)} p(x) \to 0 \tag{22}
Ist festgelegt. (Ende der Zertifizierung)
Jetzt sind wir bereit, Shannons Theorem zu beweisen, das das heutige Hauptereignis ist. Wieder zitiere ich die Beschreibung von Neilsen, Chan.
"$ \ {X_i \} $ ist die iid-Entropiequelle $ H (X) $. $ R> H (X) $. Zu diesem Zeitpunkt ist die Rate $ R $ für diese Quelle. Es gibt eine zuverlässige Komprimierungsmethode für. Wenn umgekehrt $ R <H (X) $ ist, ist keine Komprimierungsmethode zuverlässig. "
Kurz gesagt, Sie können eine Komprimierungsmethode erstellen, die diese Informationen genau überträgt, sofern Sie eine Übertragungsrate haben, die geringfügig höher ist als die Entropie der Quelle. Lass es uns beweisen.
[Beweis]
Erstens, wenn $ R> H (X) $.
Wählen Sie $ \ epsilon $ aus, das $ H (X) + \ epsilon \ leq R $ erfüllt, und betrachten Sie $ T (n, \ epsilon) $, eine Menge von $ \ epsilon $ typischen Reihen mit diesem $ \ epsilon $. Aus den Annahmen der typischen Reihensätze (1) und (2) und $ R> H (X) $ für jedes $ \ delta> 0 $ und $ n $, das groß genug ist
|T(n,\epsilon)| \leq 2^{n(H(X)+\epsilon)} \leq 2^{nR} \tag{23}
Ist festgelegt. Mit anderen Worten, die Anzahl typischer Reihen beträgt höchstens $ 2 ^ {nR} $, und die Wahrscheinlichkeit, solche Reihen zu erzeugen, beträgt mindestens $ 1- \ delta $. Um es ein bisschen mehr auszudrücken: Wenn Sie ein ausreichend großes $ n $ nehmen, wird die Serie zu einer typischen Serie mit einer Wahrscheinlichkeit von $ 1 $, und die Zahl ist $ 2 ^ {nR} $ [^ 5]. Wenn daher eine aus $ n $ bestehende Reihe mit $ nR $ -Bits codiert wird, kann sie genau genug übertragen werden. Dies wird als "es gibt ein zuverlässiges Komprimierungsverfahren für die Rate R" bezeichnet.
[^ 5]: Der mathematische Wortlaut von $ \ epsilon $ oder $ \ delta $ ist einzigartig und ich denke, es ist zunächst ärgerlich, aber wenn ich versuche, es genau auszudrücken, passiert es einfach. Wenn Sie jedoch genau hinschauen, sagen Sie oft etwas, das überraschend einfach ist. Wenn Sie in diesem Fall die Würfel mehrmals genug würfeln, wird dies zu einer typischen Serie, und die Anzahl der typischen Serien beträgt höchstens $ 2 ^ {nR} $ (jedoch ist $ R $ eine Umdrehung der Würfel). Es ist ein Wert, der etwas größer ist als die Entropie des Falls.
Als nächstes ist der Fall von $ R <H (X) $.
Gemäß dem typischen Reihensatz (3) beträgt die Wahrscheinlichkeit, dass die von der Informationsquelle ausgegebene Reihe in der Reihenmenge $ S (n) $ von $ 2 ^ {nR} $ enthalten ist, wenn $ R <H (X) $ ist Es ist $ 0 $ für ein ausreichend großes $ n $. Daher gibt es keine Komprimierungsmethode, die genau übertragen werden kann. (Ende der Zertifizierung)
Verschiedene Verfahren wie "Huffman-Code" und "arithmetischer Code" wurden als Verfahren zum reversiblen Komprimieren von Daten nahe der Übertragungsrate vorgeschlagen, die der Entropie der Informationsquelle entspricht, aber hier wollen wir Shannons Theorem erfahren. Wir werden eine sehr primitive Codierung für den alleinigen Zweck implementieren. Mit anderen Worten, wenn Sie ein ausreichend großes $ n $ verwenden, können Sie eine zuverlässige Datenkomprimierung erzielen. Bestätigen Sie also durch Simulation, dass der Übertragungsfehler durch Ändern von $ n $ ordnungsgemäß reduziert wird. Masu [^ 6].
[^ 6]: Die hier implementierte Codierung ist also nicht irreversibel, und selbst wenn sie irreversibel ist, haben wir keine Anstrengungen unternommen, um die Effizienz zu verbessern. Betrachten Sie sie daher als eine fast unpraktische Methode.
Diesmal ist die angenommene Informationsquelle eine binäre Reihe, die aus $ \ {0,1 \} $ besteht. Die Komprimierungsmethode ist sehr einfach. Teilen Sie die gesamte Binärsequenz, die Sie übertragen möchten, in Blöcke mit $ n $ Symbolen. Legt fest, ob die in jedem Block enthaltene Binärreihe eine typische Reihe ist, und weist den Code von $ nR $ Bits so zu, dass er für die typische Reihe eindeutig ist, wenn es sich um eine typische Reihe handelt. Wenn nicht, geben Sie auf und weisen Sie einen Code zu, der "unbekannt" darstellt.
Hier ist der gesamte Python-Code.
import random
import numpy as np
from collections import Counter
def generator(prob, N):
return [0 if random.random() < prob else 1 for i in range(N)]
def entropy_exp(s):
prb_0 = list(s).count('0') / len(s)
prb_1 = 1.0 - prb_0
if prb_0 == 1.0 or prb_1 == 1.0:
ent_exp = 0.0
else:
ent_exp = - prb_0*np.log2(prb_0)- prb_1*np.log2(prb_1)
return ent_exp
def coder(data, blk, ent, eps, rat):
# binary data to symbols (= message)
# ex) [0,1,1,0,1,0,0,1,...] -> ['0110','1001',...](for blk = 4)
message = [''.join(map(str,data[i:i+blk])) for i in range(0,len(data),blk)]
# histogram
syms = list(Counter(message).keys())
frqs = list(Counter(message).values())
prbs = [frqs[i]/len(message) for i in range(len(frqs))]
hist = dict(zip(syms, prbs))
# codebook
index = 0
digits = int(rat*blk) # number of digits for each code
codebook = {}
for s,p in hist.items():
ent_exp = entropy_exp(s)
if abs(ent_exp - ent) <= eps and index < 2**digits-1:
codebook[s] = '{:0{digits}b}'.format(index, digits=digits)
index += 1
codebook[False] = '{:0{digits}b}'.format(index, digits=digits)
# coding (message -> codes)
codes = [codebook[s] if s in codebook else codebook[False]
for s in message]
# decodebook
decodebook = {}
for k,v in codebook.items():
decodebook[v] = k
return (codes, decodebook)
def decoder(codes, decodebook, block):
message = [decodebook[c] for c in codes]
blocks = [list(s) if s != False else generator(0.5,block) for s in message]
data_str = sum(blocks, [])
return [int(d) for d in data_str]
def error_rate(data_in, data_out):
N = len(data_in)
count = 0
for i in range(N):
if data_in[i] != data_out[i]:
count += 1
return count / N
if __name__ == "__main__":
# settings
BLK = 10 # block size
NUM = BLK * 1000 # number of binary data sequence
PRB = 0.8 # probability to generate '0'
ENT = - PRB * np.log2(PRB) - (1-PRB) * np.log2(1-PRB) # entropy (= 0.7219..)
RAT = 0.9 # transmission rate (RAT > ENT)
EPS = 0.15 # eplsilon for typical sequence
print("NUM = ", NUM)
print("BLK = ", BLK)
print("ENT = ", ENT)
print("RAT = ", RAT)
# generate data sequence
data_in = generator(PRB, NUM)
# code the data
(codes, decodebook) = coder(data_in, BLK, ENT, EPS, RAT)
# decode the data
data_out = decoder(codes, decodebook, BLK)
# evaluate error rate
err_rate = error_rate(data_in, data_out)
print("error rate = ", err_rate)
Ich werde erklären, was Sie tun. Schauen Sie sich den Hauptverarbeitungsabschnitt an.
# settings
BLK = 10 # block size
NUM = BLK * 1000 # number of binary data sequence
PRB = 0.8 # probability to generate '0'
ENT = - PRB * np.log2(PRB) - (1-PRB) * np.log2(1-PRB) # entropy (= 0.7219..)
RAT = 0.9 # transmission rate (RAT > ENT)
EPS = 0.15 # eplsilon for typical sequence
Dies ist der Teil zum Einstellen verschiedener Parameter. BLK ist die Größe des Blocks, dh die Anzahl der in einem Block enthaltenen Binärwerte. NUM ist die Gesamtzahl der Binärwerte, die Sie übertragen möchten (vorausgesetzt, Sie möchten 1000 Blöcke von Binärwerten übertragen). PRB ist die Wahrscheinlichkeit, dass "0" auftritt (auf 0,8 gesetzt). HNO ist die Entropie pro Symbol (berechnet mit einem PRB-Wert von 0,8, 0,7219 ..). RAT ist die Übertragungsrate. Die Datenkomprimierung erfolgt nur, wenn sie größer als 0,7219 und kleiner als 1,0 ist. Daher habe ich einen geeigneten Wert von 0,9 festgelegt. EPS ist der Wert des Schwellenwerts $ \ epsilon $ zur Bestimmung der typischen Reihe. Ich muss es zu einem mäßig kleinen Wert machen [^ 7], aber wenn ich es zu klein mache, wird der Fehler nicht klein sein, es sei denn, ich setze ein sehr großes $ n $, also habe ich 0,15 als geeigneten Wert gewählt.
[^ 7]: Muss $ \ epsilon $ sein, das $ H (X) + \ epsilon \ leq R $ erfüllt.
# generate data sequence
data_in = generator(PRB, NUM)
Zunächst erstellt der Funktionsgenerator eine Reihe von zu übertragenden Binärwerten. Generieren Sie zufällig einen ganzzahligen Wert von "0" oder "1" gemäß der in PRB festgelegten Wahrscheinlichkeit und geben Sie eine Liste mit der Länge NUM aus. Einzelheiten finden Sie in der Funktionsdefinition.
# code the data
(codes, decodebook) = coder(data_in, BLK, ENT, EPS, RAT)
Der Funktionscodierer codiert data_in und gibt die Codesequenzcodes und das Wörterbuchdecodierungsbuch zum Decodieren aus. Werfen wir einen Blick auf den Inhalt der Funktion.
# binary data to symbols (= message)
# ex) [0,1,1,0,1,0,0,1,...] -> ['0110','1001',...](for blk = 4)
message = [''.join(map(str,data[i:i+blk])) for i in range(0,len(data),blk)]
Da es sich bei den zu übertragenden Daten um eine Liste mit ganzzahligen Werten "0" und "1" handelt, machen Sie sie zu einer Zeichenfolge für jeden Block und zu einer Liste mit dem Namen "message". Ein Beispiel für Blockgröße 4 finden Sie in den Kommentaren.
# histogram
syms = list(Counter(message).keys())
frqs = list(Counter(message).values())
prbs = [frqs[i]/len(message) for i in range(len(frqs))]
hist = dict(zip(syms, prbs))
Erstellen Sie ein Histogramm aus den in der Nachricht enthaltenen Elementen und speichern Sie es in einem Wörterbuch namens hist.
# codebook
index = 0
digits = int(rat*blk) # number of digits for each code
codebook = {}
for s,p in hist.items():
ent_exp = entropy_exp(s)
if abs(ent_exp - ent) <= eps and index < 2**digits-1:
codebook[s] = '{:0{digits}b}'.format(index, digits=digits)
index += 1
codebook[False] = '{:0{digits}b}'.format(index, digits=digits)
Nachdem wir nun die Elemente der Nachricht kennen, die erscheinen, dh die aus n Symbolen bestehende Reihe, entscheiden wir, welchen Code wir jedem zuweisen möchten, und speichern ihn in den Wörterbuchdaten, die als Codebuch bezeichnet werden. Um festzustellen, ob die im Histogramm der obigen for-Schleife enthaltenen Symbolreihen eine typische Reihe sind, berechnet die Funktion entropy_exp die Entropie für diese Reihe. Wenn der Unterschied zwischen der Entropie und der wahren Entropie kleiner oder gleich $ \ epsilon $ ist, wird dies als typische Reihe betrachtet und der 0,9 * n-Bit-Vorzeichenindex wird in der Reihenfolge von 0 zugewiesen. Bei atypischen Reihen wird False als "unbekannt" festgelegt, und der Maximalwert des Index wird als Code dafür zugewiesen.
# coding (message -> codes)
codes = [codebook[s] if s in codebook else codebook[False]
for s in message]
Konvertieren Sie dann unter Verwendung des erhaltenen Codebuchs die Nachricht in eine Liste von Codewortcodes.
# decodebook
decodebook = {}
for k,v in codebook.items():
decodebook[v] = k
Erstellen Sie ein Wörterbuchdecodbuch, das der inversen Konvertierung des Codebuchs entspricht, damit es zur Entschlüsselung verwendet werden kann.
return (codes, decodebook)
Gibt die Codes und das Decodebuch zurück.
Kehren Sie zum Hauptverarbeitungsabschnitt zurück.
# decode the data
data_out = decoder(codes, decodebook, BLK)
Dekodieren Sie die Codes mit der Decoderfunktion. Verwenden Sie zu diesem Zeitpunkt das Dekodierungsbuch. Wie Sie der Funktionsdefinition entnehmen können, wird sie unter Bezugnahme auf das Dekodierungsbuch dekodiert. Wenn das Ergebnis der Dekodierung jedoch Falsch ist, wird eine Zufallsreihe mit einer Fehlerbereitschaft generiert.
Sobald die Entschlüsselung abgeschlossen ist
# evaluate error rate
err_rate = error_rate(data_in, data_out)
print("error rate = ", err_rate)
Verwenden Sie die Funktion error_rate, um die Fehlerrate zu berechnen und anzuzeigen.
Versuchen wir nun, die Blockgröße (Wert von $ n $) zu ändern, um die Fehlerrate zu ermitteln. Erstens, wenn $ n = 10 $.
NUM = 10000
BLK = 10
ENT = 0.7219280948873623
RAT = 0.9
error rate = 0.3499
Die Fehlerrate ist sehr hoch. Etwa 35% sind Fehler. Als nächstes ist der Fall von $ n = 100 $.
NUM = 100000
BLK = 100
ENT = 0.7219280948873623
RAT = 0.9
error rate = 0.03194
Im Vergleich zum Vorjahr verringerte sie sich um eine Ziffer auf etwa 3,2%. Schließlich, wenn $ n = 200 $.
NUM = 200000
BLK = 200
ENT = 0.7219280948873623
RAT = 0.9
error rate = 0.00454
Sie verringerte sich um eine Ziffer auf etwa 0,45%.
Ich habe also festgestellt, dass die Fehlerrate stetig abnimmt, wenn Sie den Wert von $ \ epsilon $ festlegen und den Wert von $ n $ erhöhen. Shannons Theorem argumentiert, dass in dieser Grenze die Fehlerrate Null ist.
Dieses Mal habe ich über die klassische Informationstheorie gesprochen, daher habe ich den Quantenberechnungssimulator qlazy nicht verwendet. Wenn Sie den Code kopieren und einfügen, funktioniert er in Ihrer Python-Umgebung. Wenn Sie also interessiert sind, spielen Sie bitte damit.
Wie in der "Einführung" erwähnt, werde ich das nächste Mal die Quantenversion von Shannons Theorem "Schumachers Codierungssatz in rauschfreien Quantenkanälen" erklären. "Typischer Unterraum" kommt als ein Konzept heraus, das der typischen Reihe ähnlich ist, aber der Satz wird im gleichen Ablauf wie diese Diskussion abgeleitet. Es ist interessant, dass Quanteninformationen auf die gleiche Weise wie Klassiker komprimiert werden können und ihre Grenzleistung auch die Quantenentropie ist.
das ist alles
Recommended Posts