L’objectif principal de la théorie de l’information est de fournir une formulation mathématique pour chacun des blocs de cette figure. Il existe de nombreux ouvrages qui couvrent la théorie de l'information en détail, comme [CT91], [Mac03] ou encore [Gra90].
Éléments de théorie de l’information
- Quantité d’information d’une source
- Codage sans perte de l’information
- Codes uniquement décodable et codes instantanés
- Conditions d’existence des codes
- Théorème de codage sans perte
- Canaux et capacités de canal
- Modèles de canaux usuels et leur capacité
- Canal binaire symétrique et canal à effacement
- Canal à bruit additif blanc gaussien
- Décodeur
- Conclusion
Nous allons maintenant donner quelques résultats de théorie de l’information sur les codes sources en général. Éléments de théorie de l'information 21 En théorie de l'information, la définition d'un code sans perte est la suivante.
Codes à longueur variable
Codes de Huffman
Par conséquent, ces dernières années, de nombreux travaux ont été réalisés sur le codage conjoint source-canal afin de proposer des solutions optimisant conjointement le codage source et le codage canal. Les codes de Huffman sont donc principalement utilisés sur l'alphabet de base de la source.
Représentation d’un CLV sous forme d’arbre binaire
[BK93] montre que leurs performances de compression sont correctes si l'alphabet A est suffisamment grand. Ces codes sont définis pour une source discrète sans mémoire à 5 symboles et sans loi de probabilité.
Codage arithmétique et quasi-arithmétique
Codes arithmétiques
- Encodeur
- Décodeur
Notez que la taille de l'intervalle fini est égale à la probabilité que la séquence soit transmise. Ainsi, lorsque l'un ou l'autre de ces deux cas se produit lors du processus de codage, un bit peut être transmis et la taille de l'intervalle courant est doublée.
Codes quasi-arithmétiques
- Construction d’un code QA
En utilisant l'algorithme décrit ci-dessus pour construire l'automate de codage d'un code QA, le nombre d'états obtenus n'est pas nécessairement fini. L’automate de décodage d’un code QA peut être obtenu à partir de l’automate codeur en suivant la méthode présentée dans [BJWK06].
Décodage robuste et codage conjoint source-canal
Décodage souple des CLV et codes QA
- Treillis bit
- Treillis bit/symbole
- Réduction de complexité
Pour tirer le meilleur parti des informations sur le nombre de symboles transmis, un modèle d'état pour les CLV appelé treillis bit/symbole a été proposé dans [BH00a]. Le nombre d'états du treillis bit/symbole est quadratique avec la longueur de la chaîne.
Ajout de redondance dans les trains binaires codés entropique-
- Codes à longueur variable réversibles
- Codes QA avec symbole interdit
- Marqueurs de synchronisation
Pendant le processus de décodage, lorsque la plage sélectionnée se trouve dans la plage associée au SI, une erreur est détectée. Dans cet article, les auteurs considèrent également le partitionnement de l'intervalle interdit au sein de l'intervalle actuel et montrent que les propriétés de distance des codes QA avec SI dépendent de la configuration de l'intervalle.
Conclusion
- Préliminaires
- Présentation du modèle agrégé
- Analyse de complexité du modèle agrégé
- Résultats de simulation
3.3) Puisque le nombre d'états sur le réseau de bits est égal à L(X)×card(Ωd), nous pouvons écrire la complexité de décodage DT sur le modèle agrégé. Rappelons que cette complexité est quadratique avec la longueur de séquence sur le modèle bit/symbole.
Décodage combiné multi-treillis
- Motivation
- Description de l’algorithme
- Complexité moyenne de l’algorithme de décodage combiné multi-
- Optimisation sous contrainte des paramètres T 1 et T 2
La figure 3.11 illustre la complexité de l'algorithme de décodage multi-treillis combiné pour différents CLV et pour les paramètres T1 = 4 et T2 = 5. Dans ces conditions, la complexité moyenne de l'algorithme de décodage multi-treillis combiné pour les paramètres T1 et T1+ ∆ Test donné par.
Calcul de la marginale postérieure au niveau symbole sur le modèle
Présentation de l’algorithme
- Première étape : correspondance entre M k et T k
- Deuxième étape : obtention de la probabilité marginale
Une estimation de l'horloge des symboles pour chaque valeur de modulomk (et pas seulement pour m∗k) est nécessaire. Les valeurs estimées de l'horloge des symboles pour les états restants sont affichées au-dessus des états.
Analyse de complexité
Les deux étapes de l'algorithme proposé ont été décrites séparément pour plus de clarté. En effet, l'algorithme de Viterbi (étape 1) et la passe avant BCJR (étape 2) peuvent être effectués simultanément.
Résultats de simulation
L'algorithme SOVA est une extension de l'algorithme de Viterbi afin de pouvoir calculer les probabilités a posteriori sur chacun des symboles de la séquence décodée. P(Sk|Y1L(X)), (3.24) où les termes P(Sk|Y1L(X)) correspondent à la probabilité a posteriori résultant de l'algorithme de décodage considéré.
Décodage souple avec information adjacente
Impact de la position d’une contrainte de longueur
La position relative optimale de la contrainte de longueur est fixée à 0,6 pour T = 2 et 0,79 pour T = 8. Il est à noter que pour les CLV, la contrainte de nœud racine est utilisée à la fin.
Utilisation de contraintes de longueur partielles
Supposons que nous plaçons trois contraintes partielles de 1 bit au lieu de la contrainte totale de 3 bits. On obtient donc de meilleures performances en utilisant trois contraintes partielles de 1 bit au lieu d'une contrainte totale de 3 bits, à condition d'utiliser la solution optimale donnée par l'algorithme de recuit simulé.
Décodage robuste avec information adjacente
- Comparaison en termes de performances avec des ap-
3.7 – Positionnement et configurations de 3 contraintes partielles de 1 bit et les taux d'erreur de séquence associés pour le code C5, Eb/N0 = 3dB et T = 8. Donc pour comparer les performances obtenues avec Q7 et QF S7 de manière impartiale, ⌊ (edlF S7 − edl7)×L(S)⌋ bits d'information de contiguïté ont été introduits sous la forme de contraintes de longueur partielle.
Conclusion
Élaboration de l’error state diagram
Ainsi, on considère que le code associé au prochain symbole reçu contient une erreur binaire. Tous les modèles d'erreur possibles dans un mot de code ont été pris en compte, ainsi que la probabilité de transition associée.
Calcul de l’espérance de E s
La fonction de transfert du diagramme entre nl et ns est donc un polynôme G de la variable z dont les coefficients de zk sont égaux aux probabilités que considère le CLV pour resynchroniser les symboles exacts sources après l'erreur de transmission. Le calcul de cette grandeur nécessite donc celui de la fonction de transfert du diagramme.
Méthode matricielle
Si la matrice (I - H), où I est la matrice identité de mêmes dimensions que H, est inversible, alors G (z) est aussi l'élément situé en haut à droite de la matrice (I - H) -1 . La longueur de propagation attendue d'une seule erreur est un critère de performance pour les CLV lorsque le décodage est implémenté dans le décodeur [ZZ02].
Calcul de la ddp de ∆S pour les CLV
Rappelons que ces coefficients représentent le ddp de ∆S dans le cas où une erreur sur un seul bit se produit dans le message. Nous venons donc de voir les méthodes de calcul du MEPL et du ddp de la variable ∆S pour les CLV et dans le cas où une erreur sur un seul bit se produit lors de la transmission.
Propriétés de synchronisation des codes quasi-arithmétique
Error state diagram adapté aux codes QA
La resynchronisation du décodeur variera en fonction de l'état dans lequel se trouve la machine de décodage au moment où l'erreur binaire se produit. Il y a donc autant d’états finaux possibles dans le diagramme qu’il y a d’états dans la machine de décodage du code QA.
Calcul de la d.d.p de ∆S pour les codes QA
La méthode présentée dans la section 4.1 est ensuite utilisée pour calculer la valeur moyenne E. Par conséquent, pour un code QA donné, nous pouvons maintenant calculer la longueur de propagation attendue des erreurs sur les bits ainsi que la densité de probabilité des erreurs sur les bits ∆S.
Estimation de la ddp de ∆S sur un CBS
Pour l'estimation du ddp de L(X), nous supposerons que cette densité de probabilité est une densité gaussienne moyenne l×L(S) et dont la variance est estimée ci-dessous.
Estimation de la ddp de ∆S sur un CBS
Les valeurs ddp estimées et simulées de ∆S pour le code Q7 et un rapport signal sur bruit Eb/N0 = 4dB sont présentés dans la figure 4.5. 4.5 – Valeurs estimées et simulées du ddp de ∆S : CodeQ7,Eb/N0=4 dB le décodage dur est utilisé au décodeur, la valeur moyenne de Es permet de comparer les performances des CLV.
Pseudo-degré et critères de sélection des CLV
Pseudo-degré d’un code
Cet intervalle dépend du code (CLV ou QA) et du rapport signal sur bruit du canal. Les pseudo-grades de CLVC1 à C16 pour un rapport signal sur bruit de 6dB sont donnés dans la deuxième colonne du tableau 4.8.
Critères de sélection des CLV en décodage souple
Le tableau 4.5.2 montre les valeurs de P(∆S = 0) et H(∆S) pour ces trois codes, ainsi que les valeurs de MEPL et VEPL et les performances de décodage de ces codes. Le code C17 est le moins bon selon les critères MEPL et VEPL, mais le meilleur selon les critères P(∆S = 0) et H(∆S), ainsi qu'en termes de performances de décodage.
Analyse de performances du modèle agrégé
Ici, nous pouvons clairement voir la relation entre le comportement de H(∆SmodT) et la performance des codes sur le modèle total. La performance des codes a été obtenue en appliquant l'algorithme de Viterbi au modèle global.
Conclusion
Dans ce chapitre, nous nous concentrerons plus spécifiquement sur le problème asymétrique de Slepian-Wolf. Le théorème de Slepian-Wolf dans le cas asymétrique a été étendu par Wyner et Ziv dans [WZ76] au cas des sources gaussiennes à valeurs continues.
État de l’art en codage de Slepian-Wolf
Techniques basées sur des CLV
Dans cette condition, en utilisant les informations Y adjacentes, l'ambiguïté provoquée par le regroupement de symboles deX peut être supprimée. L'idée de base est cependant la même que pour [ZE01] : si la densité de probabilité P(x, y) de X et des informations adjacentes satisfait certaines conditions, les symboles de l'alphabet source virtuel X′ dont la cardinalité est la plus petite et l'entropie la plus grande faible.
Techniques basées sur des codes de canal
- Utilisation de codes en bloc
- Utilisation de turbo-codes
- Utilisation de codes LDPC
Le décodeur reçoit ces deux bits, et a ainsi le choix entre les deux mots de code possibles dans l'ensemble. Il sélectionnera le mot de code dont la distance de Hamming à Y est la plus faible.
Schéma de codage distribué à l’aide de codes QA
- Codes quasi-arithmétique poinçonnés
- Codes quasi-arithmétique avec recouvrement d’intervalle
- Décodage souple avec information adjacente
- Structures itératives
- Structure en série
- Structure en parallèle
- Résultats de simulation
- Sources binaire sans mémoire
- Sources binaires avec mémoire
Spar codant un code QA classique produit un message binaire X de longueur L(X) très proche de l'entropie source. Pour obtenir un taux de compression Rt (inférieur à l'entropie source), les bits de X sont poinçonnés.
Conclusion
5.12 – Performance de différents schémas de codage de ressources distribuées à un débit de 0,4 bps pour une ressource sans mémoire avec p = 0,9. 5.15 – Performance de différents schémas de codage de ressources distribuées à 0,09 bps pour une ressource mémoire d'ordre 1 avec p = 0,9 et ρm = 0,9.
Algorithme BCJR
Système de communication
Les flash codes ont la propriété suivante : Propriété 1.1 Un flash code est un code qui ne peut être que décodé. Il a montré que la longueur des mots de code d'un code uniquement décodable satisfait également à l'inégalité de Kraft (1,8).
Canal binaire symétrique
Canal à effacement
Canal à bruit additif blanc gaussien
Le chapitre suivant détaille les codes sources courants utilisés dans cet article, ainsi qu'un état de l'art en matière de décodage robuste et de décodage conjoint source/canal de ces codes. Le message issu du codage source contenant très peu de redondance, chaque élément binaire de ce message contient une quantité importante d'informations.
Chaîne de transmission classique
Enfin, le théorème de séparation suggère une solution à l'objectif de transmission avec un taux d'erreur arbitrairement faible, mais ce théorème ne dit pas qu'il est nécessaire d'effectuer séparément le codage source et le codage canal pour y parvenir. Cette approche consiste à utiliser ou ajouter une redondance résiduelle au niveau du codage source pour donner aux codes des propriétés que le décodeur utilise pour améliorer les performances des codes sources.
Construction de l’arbre de Huffman
On obtient alors un nœud appelé « supersymbole » dont la probabilité est égale à la somme des probabilités des deux symboles qui ont permis de le construire. Associez un mot de code à chaque symbole initial en descendant l'arbre obtenu et en concaténant 0 si on suit l'enfant de gauche et 1 si on suit l'enfant de droite.
Arbre binaire associé au code C 0
Automate d’encodage/décodage du code C 0
Le principe de base du codage arithmétique a été discuté pour la première fois par Shannon dans [Sha48]. Contrairement au codage de type Huffman, le codage arithmétique classique réalise une correspondance entre une séquence complète de symboles et un flux binaire.
Exemple d’encodage arithmétique
Exemple de décodage arithmétique
Pour garantir que le nombre d'états d'un automate de codage de code QA est fini, les auteurs de [BJWK06] et [DHS06] ont introduit une valeur limite pour la variable suivante. Cette technique entraîne une très légère réduction des performances de compression des codes QA, mais garantit que le nombre d'états de l'automate d'encodage est fini.
Automates d’encodage et décodage du code QA Q 9
En 1993, un algorithme pour exploiter la redondance résiduelle pour les CLV a été proposé dans [SB91]. Les techniques de décodage doux des codes CLV ou QA reposent principalement sur des algorithmes d'estimation appliqués aux réseaux.
Treillis bit associé au code C 0
Ce modèle intègre les valeurs de l'horloge des symboles au sein des états, permettant tout type d'informations supplémentaires sur le nombre de symboles à exploiter. En effet, à l'instant bitk, l'horloge symbole peut prendre ses valeurs dans tout l'intervalle [k/lM, k/lm].
Treillis bit/symbole associé au code C 0
Ce modèle est constitué uniquement des états internes du décodeur (nœuds internes de l'arbre pour les CLV et états du décodeur pour les codes QA). La figure 3.1 montre les probabilités des états du treillis bit/symbole exécuté par l'algorithme BCJR de manière simplifiée.
Code C 0
L'agrégation des conditions pour un décodage flexible des codes T CLV et QA 57 doit être augmentée pour obtenir des performances optimales. La figure 3.10 montre les performances du code Q7 en fonction du rapport signal sur bruit pour différentes valeurs de T.
Taux d’erreur symbole en fonction du rapport signal à bruit pour le
On peut noter que l'algorithme de décodage multi-réseau combiné permet de réduire la complexité du décodage sur une gamme intéressante de rapports signal sur bruit. 3.11 – Complexité de l'algorithme de décodage multi-réseaux combiné basé sur Eb/N0 pour les codes C5, C7, C9, C11 et C13 et comparaison avec l'approche classique.
Complexité de l’algorithme de décodage combiné multi-treillis en fonc-
Complexité de l’algorithme de décodage combiné multi-treillis en fonc-
Une fois cette estimation réalisée, l'algorithme BCJR permet d'estimer la probabilité marginale au niveau du symbole. La première étape de l'algorithme décrit ci-dessus consiste à associer à chacun des états sélectionnés une estimation de la valeur totale de l'horloge symbolique.
Estimation de l’horloge symbole pour les états sélectionnés par l’algo-
L'estimation de l'horloge symbolique associée aux états restants décrits ci-dessus est présentée pour les mêmes paramètres que dans l'exemple 3.2 de la figure 3.14. Chacune de ces paires se voit attribuer une valeur d'horloge symbolique ϕ(ˆtk, Mk) estimée lors de l'étape 1 décrite ci-dessus.
Estimation de l’horloge symbole associée aux états restants
Dans ce cas il faut stocker deux mesures différentes pour chaque état de la grille à un instant donné bitk : max(P(V1, . .,Vk;Y1k)) pour l'algorithme de Viterbi et la probabilité de (3.19 ) pour l'algorithme de Viterbi. Algorithme BCJR. Les probabilités qui seront surestimées à l'aide de l'algorithme décrit dans cette section seront donc très faibles (en simulation la valeur η = 10−6 est utilisée).
Taux d’erreur symbole pour le code Q 7 en fonction du rapport signal à
3.15 – Taux d'erreur sur les symboles du code Q7 en fonction du rapport signal sur bruit pour différentes techniques de décodage.
Taux d’erreur symbole pour le code C 10 en fonction de T pour diffé-
On peut constater dans ce tableau que l'utilisation de l'algorithme proposé pour calculer les probabilités marginales au niveau symbole n'affecte que très peu la qualité de la probabilité a posteriori par rapport au décodage optimal sur le treillis bit/symbole. On remarque également que l’indice de confiance moyen issu de l’algorithme SOVA est bien inférieur à celui issu de l’algorithme proposé dans cette section.
Taux d’erreur symbole pour le code C 5 en fonction de la position relative
3.17 – Taux d'erreur sur les symboles du code C5 en fonction de la position relative de la contrainte commune. 3.18 – Taux d'erreur de symbole pour le code Q7 en fonction de la position relative de la contrainte commune.
Taux d’erreur symbole pour le code Q 7 en fonction de la position rela-
L'algorithme de recuit simulé permet encore une fois de trouver la configuration optimale, et ainsi d'obtenir un meilleur TES que la solution classique consistant à utiliser une contrainte de terminaison. L'occurrence moyenne des erreurs de symboles en fonction de leur position dans le message est représentée sur la figure 3.19 pour le code Q7 et pour 3 techniques différentes d'utilisation de bits faisant référence à des contraintes de longueur : la contrainte de terminaison classique, une contrainte totale placée dans une position optimale est placée (d'après les résultats de 3.4.1), et la configuration optimale de 3 contraintes partielles.
Occurrence des erreurs symboles en fonction de leurs positions pour le
Les bits d'information adjacents faisant référence aux contraintes partielles sont transmis indépendamment du message binaire et peuvent donc être ou non protégés du bruit provenant du canal. Ainsi, pour des séquences de 100 symboles, 10 bits d'information contigus ont été introduits pour le décodage C10.
Les états du codeur et du décodeur associés à cet exemple sont présentés dans le tableau 4.1. Forte resynchronisation [KN00] : l'encodeur et le décodeur sont de nouveau dans le même état (pas de décalage d'horloge des symboles).
Code à longueur variable proposé dans [MR85]
Ainsi, après décodage du mot de code erroné, le décodeur sera soit dans l'un des états internes de l'arbre CLVnal, nα2. cas 2 ci-dessus), soit en mode resynchronisation (cas 1 ci-dessus). Ces probabilités sont égales à la probabilité du mot de code sur lequel l'erreur se produit, divisée par la longueur moyenne de description du code (ici 2.2).
ESD associé au code C 1
Notez que G(1) = 1, ce qui signifie que la probabilité que codeC1 se resynchronise après une erreur binaire est de 1. Par conséquent, codeC1 a une forte probabilité de forte resynchronisation après une erreur binaire.
ESD associé au code C 1 pour le calcul de la d.d.p de ∆S
Dans cette section, le moteur de décodage des codes QA sera utilisé pour dériver une ESD adaptée à ces codes. Nous notons (NkX, NkY) la paire de variables aléatoires qui représentent l'état du décodeur après décodage des bits les plus temporels de X et Y respectivement.
ESD d’état initial β 0 associé au code Q 7
Les TESQ des codes de la figure 4.6 dans les mêmes conditions de simulation sont présentés sur la figure 4.7. Les codes QARI permettent, comme nous venons de le constater, d'atteindre des taux de compression inférieurs à l'entropie de la source.
Schéma de codage distribué utilisant des codes QA 127 Pour chaque transition(i, j) entre les états αi et αj de l'automate de codage d'un code QA ou d'un code QARI, on appellera bt(i, j) la séquence de bits, est émise par cette transition et bt(i, j) la longueur de cette séquence. Dans le schéma de codage de source distribué présenté sur la figure 5.4, le décodeur dispose du message binaire X, ainsi que des informations adjacentes Y pour effectuer l'estimation de S.
Région des taux admissibles dans le cas symétrique du théorème de
Connaître Y nous permet de coder X avec seulement deux bits, puisqu'il n'y a qu'une ambiguïté de deux bits entre X et Y. Les 8 mots de code deX sont divisés en 4 ensembles de deux mots de code, de sorte que la distance entre les deux mots de code dans chaque ensemble est maximum. Cet exemple correspond au code du bloc de matrice de parité (3,1,3). 5.5) Le syndrome des mots de code dans un ensemble δi est en réalité égal à la représentation binaire dei.
Schéma de codage de source distribué à l’aide de codes QA
Automate d’encodage d’un code QA adapté à une source avec une mé-
Ces codes sont assez similaires aux codes QA classiques, mais ils permettent d'atteindre des taux de compression inférieurs à l'entropie source. Cette procédure conduit à augmenter la taille de l'intervalle réel après chaque codage du symbole et donc à diminuer le taux de compression.
Pour tirer le meilleur parti des informations d'adjacence (sur les symboles deS), nous utiliserons un modèle d'état de type bit/symbole pour effectuer un décodage en treillis. Les états de ce modèle sont définis par les paires de variables aléatoires Vk= (Nk, Mk), où Nk représente l'état de la machine de codage du code QA et Mk les valeurs d'horloge binaire possibles au temps symbole k.
Encodeur d’une structure itérative en série
Décodeur d’une structure itérative en série
Encodeur d’une structure itérative en parallèle
Décodeur d’une structure itérative en parallèle
Nous avons appliqué les schémas proposés à des séquences de L(S) = 100 symboles et avons moyenné le TES à la sortie du décodeur sur 105 réalisations de la source pour un taux de compression global de 0,4 bits par seconde. symbole. Pour atteindre une vitesse de 0,4 bits par symbole, 8 bits ont ainsi été découpés pour chaque réalisation de la source.
Performances de différents schémas de codage de source distribué à un
Performances de différents schémas de codage de source distribué à un
5.14 – Performance de différents schémas de codage de ressources distribuées à un débit de 0,4 bps pour une ressource sans mémoire avec p = 0,8.
Performances de différents schémas de codage de source distribué à un
Performances de différents schémas de codage de source distribué à un
Guillemot - Synchronization Recovery and State Model Reduction for Soft Decoding of Variable Length Codes - IEEE Trans. Common source-channel decoding for variable-length encoded data by exact and approximate MAP sequence detection.