Dans Article avant-dernier, j'ai repris "Holebo limit" et expliqué la limite du canal de communication quantique. L'hypothèse à l'époque était l'histoire d'un chemin de communication appelé «classique-quantique-classique» dans lequel l'information classique est codée avec des bits quantiques et transmise, et l'information classique est décodée par mesure POVM du côté récepteur. Cette fois, j'aimerais plutôt parler de la transmission de l'état quantique lui-même comme "information". Dans la théorie de l'information classique de Shannon, il existe un théorème célèbre selon lequel si la nature (distribution de probabilité) d'une source d'information est connue, la capacité de communication minimale requise est déterminée et la version quantique de ce théorème a été prouvée par Schumacher. Je veux réussir à comprendre cela. Ça va être un peu long, alors je vais le diviser en deux parties. Cette fois, la première fois, comme connaissance préalable, j'expliquerai "le théorème de codage de Shannon dans un canal sans bruit" dans la théorie classique de l'information, et dans un second temps, le sujet principal, "le code de Schumacher dans un canal quantique sans bruit" J'expliquerai le théorème chimique. Chaque fois, une fois que je comprendrai, j'essaierai de simuler son comportement de codage avec un programme Python [^ 1].
[^ 1]: Au fait, j'ai utilisé le mot «encodage» maintenant, mais vous pouvez le considérer comme synonyme de «compression de données». «Encodage» est la conversion d'informations en une chaîne de bits. À ce moment-là, nous voulons «communiquer» et «stocker» le plus efficacement possible, c'est-à-dire avec moins de ressources nécessaires. Cela a créé la motivation de «compresser» les informations autant que possible, et des recherches ont été menées depuis de nombreuses années depuis Shannon. Pour le dire un peu bruyant, je pense que la "compression de données" est l'un des objectifs du "codage", mais comme il s'agit d'un objectif très large, il est utilisé à peu près dans le même sens dans divers contextes. Je pense que c'est la situation actuelle. Aussi, cette fois, nous l'avons limité à "pas de bruit", mais bien sûr, il peut être "bruyant". Je n'ai pas encore étudié, donc si je peux le comprendre, je voudrais le présenter à nouveau (le calendrier est indécis).
Les documents suivants ont été utilisés comme références.
En un mot, je voudrais examiner la réponse à la question de savoir combien de données peuvent être compressées en principe lorsque la nature de la source d’information est la suivante. Par conséquent, il est nécessaire d'abstraire, de modéliser et de traiter mathématiquement une sorte d'informations insaisissables. La simplification pour capturer l'essence peut s'écarter légèrement des informations réelles, mais si elle donne des résultats pratiquement utiles, c'est également une bonne chose. Sur la base de cette idée, nous avons d'abord résumé et modélisé la source d'information.
Par exemple, imaginez des informations textuelles en anglais constituées de chaînes de caractères alphabétiques. Quand il y avait une phrase anglaise "I have a dream.", Les caractères alphabétiques étaient "I", "$ \ space $", "h", "a", "v", "e" ... , On peut voir qu'il se produit dans l'ordre chronologique. Il y a beaucoup d'autres phrases anglaises dans le monde, et quand vous les regardez, il y a des lettres qui sont faciles à apparaître (comme "e" et "a") et des lettres qui sont rarement générées (comme "q" et "z"). Puisqu'il y a [^ 2], une idée d'abstraction / modélisation est de considérer les caractères alphabétiques qui apparaissent à chaque instant comme des variables de probabilité [^ 3]. Il semble naturel que les probabilités pour ce caractère alphabétique soient communes à tout moment, et même avec l'hypothèse que les caractères alphabétiques qui apparaissent à des moments différents se produisent indépendamment les uns des autres. Ça a l'air bien [^ 4]. De cette manière, la source d'informations qui suppose que les valeurs générées séparément de la source d'informations sont indépendantes les unes des autres et suivent la même distribution (répartie de manière identique) est appelée «source d'informations iid (source d'informations indépendante et répartie de manière identique)». Est appelé. Sur cette base, nous procéderons aux discussions suivantes.
[^ 2]: Référence: Table de fréquence des caractères
[^ 3]: "J'ai un rêve." Est un passage du célèbre discours de Martin Luther King, Jr., et je pense que beaucoup de gens l'ont lu ou entendu dans les cours d'anglais. Peu importe combien de fois je l'entends, le discours est touchant, et il y a quelque chose qui peut être transmis rien qu'en regardant ce passage «J'ai un rêve». Ce qu'il essayait de dire. À partir de maintenant, j'expliquerai que nous devrions jeter toutes ces implications, les abstraire et capturer l'information comme un objet mathématique. C'est la théorie de l'information que Shannon a lancée. C'est une position très cool, mais cela a beaucoup changé le monde. Je vais faire un lien vers la vidéo du discours. Je commence à appeler "J'ai un rêve." À partir d'environ 11 minutes et 40 secondes. [Sous-titres japonais] Discours du révérend King "J'ai un rêve" --Martin Luther King "J'ai un rêve"
[^ 4]: Si vous imaginez l'anglais, ce n'est pas exactement. Par exemple, la probabilité que "h" vienne après "t" est plus élevée que dans les autres cas. Cependant, dans de nombreuses sources, il semble que même si vous faites une hypothèse aussi approximative, ce n'est pas si faux. De plus, commencer par les hypothèses les plus simples et réfléchir progressivement aux plus complexes est la manière habituelle de construire une théorie. Alors, commençons par une hypothèse aussi simple.
Avant le théorème de codage de Shannon, il est nécessaire d'expliquer les concepts de «série typique» et de «série atypique». Supposons maintenant que la source i.i.d. crée les variables stochastiques $ X_1, X_2, X_3, \ cdots $. Par exemple, vous pouvez penser au phénomène de lancer une pièce et savoir si elle sort à l'avant ou à l'arrière comme une variable stochastique, et imaginez le répéter encore et encore pour créer une série de recto et verso. Si vous attribuez un numéro "0" pour le recto et "1" pour le verso, la série sera une série binaire. S'il s'agit d'une pièce de monnaie ordinaire, le recto et le verso se produiront avec une probabilité de 1/2, mais j'aimerais en discuter de manière aussi générale que possible, en supposant donc que la pièce est faite de sorte que la probabilité d'apparition du recto soit de $ p $ Mettre. Même ainsi, il est naturel de supposer qu'ils sont «répartis de manière identique» parce qu'ils lancent les mêmes pièces à chaque fois. De plus, celui qui sort ne dépend pas des résultats passés (par exemple, puisque c'était la "table" la dernière fois, cela ne veut pas dire que la "table" sortira facilement cette fois), il est donc étrange de dire "indépendant". Pas une hypothèse. Par conséquent, les informations obtenues en jetant des pièces peuvent être considérées comme une source d'information i.i.d.
Si vous retirez les variables de probabilité $ n $ $ X_1, X_2, \ cdots, X_n $ de cette série infinie de sources iid, les valeurs réelles $ x_1, x_2, \ cdots, x_n $ seront Il existe de nombreuses possibilités, mais elles peuvent être divisées en modèles de séries susceptibles de se produire et en modèles de séries qui se produisent rarement. Les séquences susceptibles de se produire sont appelées "séquences typiques", et les séquences qui se produisent rarement sont appelées "séquences atypiques". Soit la probabilité d'obtenir 0 $ p = 1/4 $ et le nombre de séries à récupérer $ n = 100 $. Ensuite, vous pouvez imaginer que le nombre de fois que 0 est sorti est d'environ 25 fois. Même si vous répétez ces 100 échantillonnages plusieurs fois, il y aura probablement des fluctuations, et le nombre de 0 devrait être concentré environ 25 fois. Au contraire, s'il n'y en a que 5 ou 85 fois, c'est soit un phénomène très inhabituel, soit la personne qui lance la pièce est un maître de calmar. Dans cet exemple, une série dans laquelle 0 apparaît environ 25 fois est appelée «série typique».
J'ai dit que la série typique est une série facile à réaliser, mais comment quantifier la probabilité? Si la probabilité d'obtenir la série $ x_1, x_2, \ cdots, x_n $ en échantillonnant n morceaux de la série de variables stochastiques est $ p (x_1, x_2, \ cdots, x_n) $, c'est une source d'information iid. ,
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}
Ce sera. Si vous prenez le logarithme des deux côtés,
-\log p(x_1,x_2,\cdots,x_n) \approx -np \log p - n(1-p) \log (1-p) = n H(X) \tag{2}
Alors
p(x_1,x_2,\cdots,x_n) \approx 2^{-nH(X)} \tag{3}
Il peut être approximé en utilisant l'entropie. Ici, l'équation (3) a été dérivée en imaginant une valeur binaire dans laquelle les variables de probabilité ne prennent que les valeurs «0» et «1», mais elle est valable même s'il y a plusieurs valeurs. Je vais le prouver.
[Preuve]
Variable probabiliste
p(x_1,x_2,\cdots,x_n) = p(x_1)p(x_2) \cdots p(x_n) \tag{4}
De plus, la forme fonctionnelle de $ p (x_i) $ est la même. La probabilité $ p (a_ {\ mu}) $ lorsque $ x_i = a_ {\ mu} $ est $ N (a_) le nombre de fois que $ a_ {\ mu} $ apparaît dans la série $ n $. Si vous écrivez {\ mu}) $,
p(a_{\mu}) \approx \frac{N(a_{\mu})}{n} \tag{5}
Peut être approximé à. Puis
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}
Ce sera. Si vous prenez le logarithme des deux côtés,
- \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}
Alors
p(x_1,x_2,\cdots,x_n) \approx 2^{-nH(X)} \tag{8}
Ensuite, l'équation (3) pourrait être prouvée de la même manière. (Fin de la certification)
Puisque l'inverse de la probabilité est le nombre quand il se produit, vous pouvez penser que le nombre de séries typiques est d'environ 2 $ ^ {nH (X)} $. Cela signifie que la plupart des informations peuvent être transmises sans faute si le code de $ nH (X) $ bits est préparé, en considérant que la source d'informations est divisée en n blocs et codée. .. Bien sûr, des séries atypiques peuvent se produire, alors dans ce cas, abandonnez et attribuez un code approprié. Ensuite, une erreur de transmission se produira à un certain débit, mais si n est rendu suffisamment grand, le débit peut être rendu suffisamment petit et, à la fin, une communication fiable peut être réalisée. C'est exactement ce que Shannon a prouvé. Avant d'entrer dans cette preuve, nous avons besoin d'une compréhension un peu plus approfondie de la série typique, alors parlons-en.
Lorsque $ \ epsilon> 0 $ est donné,
2^{-n(H(X)+\epsilon)} \leq p(x_1,x_2,\cdots,x_n) \leq 2^{-n(H(X)-\epsilon)} \tag{9}
La série $ x_1, x_2, \ cdots, x_n $ qui satisfait la condition est appelée "série typique $ \ epsilon $". L'ensemble de toutes ces séries typiques $ \ epsilon $ de longueur $ n $ est représenté par $ T (n, \ epsilon) $. L'équation (9) est
| \frac{1}{n} \log \frac{1}{p(x_1,x_2,\cdots,x_n)} - H(X) | \leq \epsilon \tag{10}
Il peut être réécrit comme. Avec cela, nous avons pu quantifier la série typique vaguement définie afin qu'elle puisse être manipulée mathématiquement. Donc, ensuite, je vais expliquer trois théorèmes sur les séries typiques dans l'ordre.
La description de Neilsen, Chan est citée telle quelle.
"Fixez $ \ epsilon> 0 $. Pour tout $ \ delta> 0 $, un $ n $ suffisamment grand, la probabilité que la chaîne soit $ \ epsilon $ est d'au moins $ 1- \ delta $. "
Eh bien, je pense qu'il y a beaucoup de gens qui ne comprennent pas du tout ce qu'ils disent, alors je vais mâcher un peu. $ \ Epsilon $ est $ \ epsilon $, qui détermine la plage de séries typiques. Supposons maintenant que vous corrigiez ce $ \ epsilon $. Pensez à un nombre positif approprié dans votre tête (par exemple, 0,1). Ensuite, un autre $ \ delta $ apparaîtra. Cela peut être défini comme n'importe quelle valeur positive. Ce théorème soutient que peu importe ce que $ \ delta> 0 $ vous décidez, si vous prenez $ n $ assez grand, une série de $ n $ de longueur devient une série typique de $ \ epsilon $. La probabilité est d'au moins $ 1- \ delta $. Par exemple, si $ \ delta $ est défini sur une valeur relativement grande (telle que 0,999), la revendication de ce théorème semble tout à fait évidente. Parce que la probabilité de devenir un $ \ epsilon $ typique est très petite = une condition très lâche, je pense donc qu'elle semble tenir même si ce n'est pas un si grand $ n $. D'autre part, que se passe-t-il si la valeur de $ \ delta $ est très petite (par exemple, 0,000001)? La revendication de ce théorème est très stricte. Parce qu'il dit que la probabilité de devenir typique de $ \ epsilon $ est presque de 1. Cependant, la valeur de $ n $ peut être suffisamment grande. Si vous prenez $ n $ assez grand, vous pouvez rendre la probabilité de devenir typique de $ \ epsilon $ supérieure ou égale à $ 1- \ delta $ (c'est-à-dire assez proche de 1). C'est ce que dit ce théorème. En un mot, c'est une histoire très simple: si vous prenez $ n $ assez gros, toute série sera une série $ \ epsilon $ typique. Considérez une expérience dans laquelle vous lancez un dé et enregistrez les yeux qui sortent. Même si elle ne devient pas une série typique après 10 rotations, elle doit être une série typique si elle est roulée 100 fois ou 1000 fois. Vous dites simplement cela mathématiquement exactement. Prouvons-le.
[Preuve]
$ X_1, X_2, \ cdots $ est une série de variables stochastiques obtenues à partir de la source i.i.d. Puisque $ p (X_i) $ est indépendant et a la même distribution, $ - \ log p (X_i) $ est également indépendant et a la même distribution. Cela signifie que la valeur attendue de $ - \ log p (X) $ est $ E (-log p (X)) $ lorsque $ n $ $ - \ log p (X_i) $ sont retirés. Elle peut être approximée à la valeur moyenne. Autrement dit, pour tout $ \ 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}
Il y a toujours $ n> 0 $ qui tient. Est-ce correct? Peu importe la taille de $ \ epsilon $ ou $ \ delta $ que vous prenez, si vous prenez $ n $ assez grand, vous pouvez satisfaire l'équation ci-dessus. En d'autres termes, si vous prenez $ n $ qui est assez grand, vous pouvez faire $ E (- \ log p (X)) = \ sum_ {i = 1} ^ {n} \ frac {- \ log p (X_i)} {n} $ Ce n'est donc qu'une paraphrase de la soi-disant «loi de la majorité».
ici,
\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}
Ainsi, l'équation (11) est
p(| - \frac{\log(p(X_1,X_2,\cdots,X_n))}{n} - H(X) | \leq \epsilon) \geq 1-\delta \tag{13}
Ce sera. Puisque le contenu de $ p $ sur le côté gauche est la définition de la série typique $ \ epsilon $ elle-même, l'équation (13) exprime que la probabilité d'être une série typique $ \ epsilon $ est d'au moins $ 1- \ delta $. J'ai donc pu le prouver. (Fin de la certification)
La description de Neilsen, Chan est citée.
"Tout fixe
(1-\delta) 2^{n(H(X)-\epsilon)} \leq |T(n,\epsilon)| \leq 2^{n(H(X)+\epsilon)} \tag{14}
」
En d'autres termes,
[Preuve]
Équation (9) pour la probabilité que la série $ x = (x_1, x_2, \ cdots, x_n) $ se produise et la probabilité ne dépasse pas 1.
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}
Alors
|T(n,\epsilon)| \leq 2^{n(H(X)+\epsilon)} \tag{16}
Est établi. Cela prouve l'inégalité du côté droit de l'équation (14). Vient ensuite l'inégalité du côté gauche.
À partir du théorème de série typique (1) et de l'équation (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}
Alors
(1-\delta) 2^{n(H(X)-\epsilon)} \leq |T(n,\epsilon)| \tag{18}
Est établi. La combinaison des équations (16) et (18) donne l'équation (14). (Fin de la certification)
La description de Neilsen, Chan est citée.
"$ S (n) $ est une collection de chaînes de longueur $ n $ provenant de la source, et sa taille est au maximum de 2 $ ^ {nR} $. Où $ R \ <H (X) $ Est fixe. À ce stade, l'équation suivante est valable pour tout $ \ delta > 0 $ et suffisamment grand $ n $.
\sum_{x \in S(n)} p(x) \leq \delta \tag{19}
」
Le nombre de séries typiques est d'environ 2 $ ^ {nH (X)} $, mais en utilisant $ R $, qui est plus petit que $ H (X) $, il n'y a qu'environ 2 $ ^ {nR} $ sous-ensembles. Pensez à $ S (n) $. Il prétend que si $ n $ est suffisamment grand, la proportion de $ S (n) $ contenue dans l'ensemble de séries de longueur $ n $ sera suffisamment petite. A la limite de $ n \ à \ infty $, la proportion converge vers 0. Est-ce vrai? Vous voudrez peut-être dire cela, mais c'est vrai. Je vais le prouver ci-dessous. Veuillez profiter de la puissance de 2.
[Preuve]
Considérez la chaîne $ S (n) $ comme une série typique et une série atypique. D'après le théorème des séries canoniques (1), lorsque $ n $ est suffisamment grand, le nombre de séries atypiques contenues dans l'ensemble de séries de longueur $ n $ est suffisamment petit, de sorte que son sous-ensemble $ S (n) Le nombre de séries atypiques contenues dans) $ est également assez petit. Il vaut 0 dans la limite de $ n \ à \ infty $.
En revanche, le nombre de séries typiques contenues dans $ S (n) $ est inférieur ou égal au nombre de séries contenues dans $ S (n) $. En d'autres termes, c'est juste 2 $ ^ {nR} $. Puisque la probabilité d'apparition de la série typique était de 2 $ ^ {-nH (X)} $, la probabilité d'apparition de $ S (n) $ est au plus de 2 $ ^ {n (R-H (X))} $. Autrement dit, pour un $ n $ suffisamment grand
\sum_{x \in S(n)} p(x) \leq 2^{n(R-H(X))} \tag{20}
est. Maintenant que $ R <H (X) $, pour tout $ \ delta> 0 $
\sum_{x \in S(n)} p(x) \leq \delta \tag{21}
Il existe $ n> 0 $ qui satisfait. En d'autres termes, à la limite de $ n \ à \ infty $,
\sum_{x \in S(n)} p(x) \to 0 \tag{22}
Est établi. (Fin de la certification)
Nous sommes maintenant prêts à prouver le théorème de Shannon, qui est l'événement principal d'aujourd'hui. Encore une fois, je cite la description de Neilsen, Chan.
"$ \ {X_i \} $ est la source iid d'entropie $ H (X) $. $ R> H (X) $. À ce stade, le taux $ R $ pour cette source. Il existe une méthode de compression fiable pour. Inversement, si $ R <H (X) $, aucune méthode de compression n'est fiable. "
En un mot, vous pouvez créer une méthode de compression qui transmet précisément ces informations, à condition que vous ayez un taux de transmission légèrement supérieur à l'entropie de la source. Prouvons-le.
[Preuve]
Premièrement, lorsque $ R> H (X) $.
Sélectionnez $ \ epsilon $ qui satisfait $ H (X) + \ epsilon \ leq R $, et considérez $ T (n, \ epsilon) $, qui est un ensemble de séries typiques $ \ epsilon $ avec ce $ \ epsilon $. À partir des hypothèses des théorèmes de série typiques (1) et (2) et $ R> H (X) $, pour tout $ \ delta> 0 $ et $ n $ assez grand
|T(n,\epsilon)| \leq 2^{n(H(X)+\epsilon)} \leq 2^{nR} \tag{23}
Est établi. En d'autres termes, le nombre de séries typiques est au plus de 2 $ ^ {nR} $, et la probabilité de générer une telle série est d'au moins $ 1- \ delta $. Pour le dire un peu plus, si vous prenez un $ n $ suffisamment grand, la série deviendra une série typique avec une probabilité de $ 1 $, et le nombre est $ 2 ^ {nR} $ [^ 5]. Par conséquent, si une série composée de $ n $ est codée en utilisant $ nR $ bits, elle peut être transmise avec suffisamment de précision. C'est ce qu'on appelle "il existe une méthode de compression fiable pour le taux R".
[^ 5]: Le libellé mathématique qui arrive avec $ \ epsilon $ ou $ \ delta $ est unique et je pense que c'est ennuyeux au début, mais quand j'essaye de le dire exactement, ça arrive. Cependant, si vous l'examinez attentivement, vous constaterez souvent que c'est étonnamment facile. Dans ce cas, si vous lancez les dés suffisamment de fois, cela devient une série typique, et le numéro de la série typique est au plus $ 2 ^ {nR} $ (cependant, $ R $ est une rotation des dés). Ce sera une valeur légèrement supérieure à l'entropie du cas).
Vient ensuite le cas de $ R <H (X) $.
Selon le théorème de série typique (3), lorsque $ R <H (X) $, la probabilité que la série sortie de la source d'information soit incluse dans l'ensemble de séries $ S (n) $ de $ 2 ^ {nR} $ est Ce sera 0 $ pour un $ n $ suffisamment grand. Par conséquent, aucune méthode de compression ne peut être transmise avec précision. (Fin de la certification)
Diverses méthodes telles que le "code de Huffman" et le "code arithmétique" ont été proposées comme méthodes pour compresser de manière réversible des données pour se rapprocher du taux de transmission correspondant à l'entropie de la source d'information, mais expérimentons ici le théorème de Shannon. Nous allons implémenter un encodage très primitif dans le seul but. En d'autres termes, si vous prenez un $ n $ suffisamment grand, vous pouvez obtenir une compression de données fiable, confirmons donc par simulation que l'erreur de transmission sera réduite correctement en changeant $ n $. Masu [^ 6].
[^ 6]: Ainsi, le codage mis en œuvre ici n'est pas irréversible, et même s'il est irréversible, nous n'avons conçu aucune mesure pour améliorer l'efficacité, alors pensez-y comme une méthode presque impraticable.
Cette fois, la source d'information supposée est une série binaire constituée de $ \ {0,1 \} $. La méthode de compression est très simple. Divisez toute la séquence binaire que vous souhaitez transmettre en blocs de $ n $ symboles. Détermine si la série binaire contenue dans chaque bloc est une série typique, et s'il s'agit d'une série typique, attribue le code de $ nR $ bits de sorte qu'il soit unique à la série typique. Sinon, abandonnez et attribuez un code qui représente «inconnu».
Voici l'intégralité du code Python.
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)
Je vais vous expliquer ce que vous faites. Regardez la section de traitement principale.
# 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
C'est la partie pour définir divers paramètres. BLK est la taille du bloc, c'est-à-dire le nombre de valeurs binaires contenues dans un bloc. NUM est le nombre total de valeurs binaires que vous souhaitez transmettre (en supposant que vous souhaitiez transmettre 1000 blocs de valeurs binaires). PRB est la probabilité que "0" se produise (fixé à 0,8). ENT est l'entropie par symbole (calculée avec une valeur PRB de 0,8, elle est de 0,7219 ..). RAT est le taux de transmission. La compression des données ne se produira pas à moins qu'elle ne soit supérieure à 0,7219 .. et inférieure à 1,0, je l'ai donc définie sur une valeur appropriée de 0,9. EPS est la valeur du seuil $ \ epsilon $ pour déterminer la série typique. Je dois en faire une valeur modérément petite [^ 7], mais si je la rends trop petite, l'erreur ne sera pas petite à moins que je ne mette un très grand $ n $, donc j'ai choisi 0,15 comme valeur appropriée.
[^ 7]: Doit être $ \ epsilon $ qui satisfait $ H (X) + \ epsilon \ leq R $.
# generate data sequence
data_in = generator(PRB, NUM)
Tout d'abord, le générateur de fonctions crée une série de valeurs binaires à transmettre. Générez aléatoirement une valeur entière de "0" ou "1" selon la probabilité définie dans PRB, et sortez une liste de longueur NUM. Voir la définition de la fonction pour plus de détails.
# code the data
(codes, decodebook) = coder(data_in, BLK, ENT, EPS, RAT)
Le codeur de fonction code data_in et sort les codes de séquence de code et le décodage de dictionnaire pour le décodage. Jetons un coup d'œil au contenu de la fonction.
# 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)]
Puisque les données à transmettre sont une liste composée de valeurs entières "0" et "1", faites-en une chaîne de caractères pour chaque bloc et faites-en une liste appelée message. Un exemple de taille de bloc 4 est fourni dans les commentaires.
# 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))
Créez un histogramme à partir des éléments contenus dans le message et stockez-le dans un dictionnaire appelé 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)
Maintenant que nous connaissons les éléments du message qui apparaissent, c'est-à-dire la série constituée de n symboles, nous décidons quel code attribuer à chacun et le stockons dans le dictionnaire de données appelé livre de codes. Afin de déterminer si la série de symboles incluse dans l'histogramme de la boucle for ci-dessus est une série typique, la fonction entropy_exp calcule l'entropie pour cette série. Si la différence entre l'entropie et l'entropie vraie est inférieure ou égale à $ \ epsilon $, elle est considérée comme une série typique et l'indice de signe 0,9 * n bits est attribué dans l'ordre à partir de 0. Dans le cas de séries atypiques, il est défini sur False pour signifier «inconnu», et la valeur maximale de l'indice lui est assignée comme code.
# coding (message -> codes)
codes = [codebook[s] if s in codebook else codebook[False]
for s in message]
Ensuite, à l'aide du livre de codes obtenu, convertissez le message en une liste de codes de mots de code.
# decodebook
decodebook = {}
for k,v in codebook.items():
decodebook[v] = k
Créez un décodage de dictionnaire qui correspond à la conversion inverse du livre de codes afin qu'il puisse être utilisé pour le décryptage.
return (codes, decodebook)
Renvoie les codes et le décodage.
Revenez à la section de traitement principale.
# decode the data
data_out = decoder(codes, decodebook, BLK)
Décodez les codes avec la fonction décodeur. À ce moment-là, utilisez le livre de décodage. Comme vous pouvez le voir à partir de la définition de la fonction, elle est décodée en se référant au décodage, mais si le résultat du décodage est Faux, une série aléatoire sera générée avec une préparation aux erreurs.
Une fois le décryptage terminé
# evaluate error rate
err_rate = error_rate(data_in, data_out)
print("error rate = ", err_rate)
Utilisez la fonction error_rate pour calculer et afficher le taux d'erreur.
Maintenant, essayons de changer la taille du bloc (valeur de $ n $) pour voir quel sera le taux d'erreur. Premièrement, lorsque $ n = 10 $.
NUM = 10000
BLK = 10
ENT = 0.7219280948873623
RAT = 0.9
error rate = 0.3499
Le taux d'erreur est très élevé. Environ 35% sont des erreurs. Vient ensuite le cas de $ n = 100 $.
NUM = 100000
BLK = 100
ENT = 0.7219280948873623
RAT = 0.9
error rate = 0.03194
Par rapport à la fois précédente, il a diminué d'un chiffre à environ 3,2%. Enfin, si $ n = 200 $.
NUM = 200000
BLK = 200
ENT = 0.7219280948873623
RAT = 0.9
error rate = 0.00454
Il a diminué d'un chiffre à environ 0,45%.
Donc, j'ai trouvé que si vous corrigez la valeur de $ \ epsilon $ et augmentez la valeur de $ n $, le taux d'erreur diminuera régulièrement. Le théorème de Shannon soutient que dans cette limite, le taux d'erreur est nul.
Cette fois, je parlais de théorie de l'information classique, donc je n'ai pas utilisé le simulateur de calcul quantique qlazy. Si vous copiez et collez le code, il fonctionnera dans votre environnement Python, donc si vous êtes intéressé, veuillez jouer avec.
La prochaine fois, comme mentionné dans l '"Introduction", j'expliquerai la version quantique du théorème de Shannon, "le théorème de codage de Schumacher dans les canaux quantiques sans bruit". "Sous-espace typique" apparaît comme un concept similaire à la série typique, mais le théorème est dérivé dans le même flux que cette discussion. Il est intéressant de noter que l'information quantique peut être compressée de la même manière que les classiques, et sa performance marginale est également l'entropie quantique.
c'est tout
Recommended Posts