Quelles techniques pouvez-vous utiliser pour coder des données sur un canal unidirectionnel avec perte?

Question

Imaginez que vous disposiez d'un canal de communication intrinsèquement avec perte et à sens unique. Autrement dit, il existe un bruit inhérent qu'il est impossible d'éliminer et qui provoque, par exemple, le basculement de bits aléatoires. Imaginez également que ce soit une solution: vous ne pouvez pas demander de retransmission.

Mais vous devez quand même envoyer des données par dessus. Quelles techniques pouvez-vous utiliser pour envoyer des chiffres et du texte sur ce canal?

1. Est-il possible de coder des nombres de manière à ce qu'ils puissent toujours être interprétés comme des valeurs proches de l'original (même dans le cas d'une torsion aléatoire) (transmission avec perte )?

2. Existe-t-il un moyen d'envoyer une chaîne de caractères (ASCII, par exemple) de manière sans perte ?

Ceci est juste pour le plaisir. Je sais que vous pouvez utiliser du code morse ou toute autre communication binaire à très basse fréquence. Je connais les bits de parité et les sommes de contrôle pour détecter les erreurs et réessayer. Je sais que vous pourriez aussi bien utiliser un signal analogique. Je suis simplement curieux de savoir s’il existe des techniques d’économie informatique intéressantes pour envoyer ce genre de choses par un canal avec pertes.

Answer 1

En fonction de certains détails que vous ne fournissez pas à propos de votre canal avec perte, je vous recommande, tout d'abord, d'utiliser un Code gris pour vous assurer que les erreurs sur un bit entraînent de légères différences (pour répondre à votre souhait de limiter les pertes dans une transmission avec pertes), puis éventuellement aussi coder le flux résultant avec certains "sans perte". (== essaie d’encoder sans perte ;-).

Reed-Solomon et ses variantes sont particulièrement utiles si votre les épisodes de bruit sont susceptibles de se produire par petites rafales (plusieurs erreurs de bits dans un seul octet, par exemple), ce qui devrait bien interagir avec le codage de Gray (car les erreurs multibits sont la cause principale de l'aspect "atténuation des pertes" de Gray, conçu se dégrader gracieusement pour les erreurs mono-bit sur le fil). C’est parce que R-S est intrinsèquement un schéma de bloc, et que plusieurs erreurs d’un bloc sont fondamentalement les mêmes qu’une seule erreur, du point de vue de R-S; -).

RS est particulièrement intéressant si de nombreuses erreurs sont des effacements - pour le dire simplement , un effacement est un symbole qui a très probablement été endommagé lors de la transmission, MAIS pour lequel vous savez le fait crucial qu’il a été mutilé. La couche physique, en fonction de sa conception, peut souvent avoir des indices sur ce fait, et si elle a le moyen d'informer les couches supérieures, cela peut être d'une aide cruciale. Laissez-moi vous expliquer un peu les effacements ...:

Disons, pour un exemple simplifié, qu'un 0 est envoyé avec un niveau de -1 volt et un 1 avec un niveau de +1 volt (par rapport à une onde de référence), mais qu'il y ait du bruit (le bruit physique peut souvent être bien modélisé, demandez à n'importe quel ingénieur en communication compétent ;-); En fonction du modèle de bruit, le décodage peut consister en ce que tout ce qui est -0,7 V et moins est considéré comme un bit 0, tout ce qui est +0,7 V et plus est considéré comme un bit, tout ce qui est entre-deux est considéré comme un effacement, c'est-à-dire que la couche supérieure est dite. que le bit en question a probablement été mutilé lors de la transmission et doit donc être ignoré. (Je cite parfois cela à titre d'exemple de ma thèse selon laquelle des abstractions DEVRAIENT parfois "fuir" - d'une manière contrôlée et structurée: le corollaire de Martelli au Loi des abstractions qui fuient ! -).

Un code RS avec un taux de redondance donné peut être environ deux fois plus efficace pour corriger les effacements (erreurs sur lesquelles le décodeur est raconté) que pour corriger des erreurs sinon inconnues - il est également possible de mélanger les deux aspects, en corrigeant les deux. des effacements ET des erreurs inconnues.

En tant que cerise sur le gâteau, les codes R-S personnalisés peuvent être (raisonnablement facilement) conçus et adaptés de manière à réduire la probabilité d'erreur non corrigée à un niveau inférieur à tout seuil requis & # 952; à partir d'un modèle précis des caractéristiques du canal physique, à la fois en termes d'effacement et d'erreurs non détectées (y compris probabilité et éclatement).

Je n'appellerais pas cette région un "ordinateur-science". un, en fait: lorsque j’ai obtenu mon diplôme (MSEE, il ya 30 ans), j’essayais surtout d’éviter "CS". Des trucs en faveur de la conception des puces, des systèmes, des systèmes de radio avancés, etc. - Pourtant, on m'a appris ce truc (enfin, le sous-ensemble qui était déjà du domaine de l'utilisation pratique de l'ingénierie ;-) plutôt bien.

Et juste pour confirmer que les choses n'ont pas tellement changé en une génération: ma fille vient d'obtenir son MS en ingénierie télécom (elle se concentre strictement sur les systèmes radio avancés). Elle ne peut concevoir aucun programme sérieux. , algorithme ou structure de données (bien qu'elle se soit très bien comportée dans les cours obligatoires sur C et Java, il y

Answer 2

Cette question fait l'objet de la théorie du codage .

Answer 3

L’une des méthodes les plus connues consiste probablement à utiliser le code Hamming . Ce n'est peut-être pas la meilleure façon de corriger les erreurs à grande échelle, mais c'est incroyablement simple à comprendre.

Answer 4

• Le codage redondant utilisé dans les supports optiques peut être utilisé. récupérer bit-perte.
  • Le CCE est également utilisé dans les disques durs et la RAM
• Le protocole TCP peut gérer beaucoup de choses perte de données avec retransmissions.

Answer 5

Turbo Codes ou Codes de vérification de parité basse densité pour les données générales, car ils se rapprochent le plus de la limite de Shannon - voir wikipedia.

Answer 6

Vous pouvez utiliser les codes Reed-Solomon .

Answer 7

Voir aussi le protocole de fenêtre coulissante (utilisé par TCP).

Bien que cela inclue le traitement des paquets réorganisés ou perdus, cela ne faisait pas partie de la définition de votre problème.

Answer 8

Comme le dit Alex Martelli, il existe de nombreuses théories de codage dans le monde, mais les codes de Reed-Solomon sont sans aucun doute un bon compromis. Si vous souhaitez réellement créer quelque chose, Jim Plank a écrit un beau tutoriel sur le codage de Reed-Solomon . Plank a un intérêt professionnel pour le codage et dispose de nombreuses compétences pratiques pour le sauvegarder.

Answer 9

Je choisirais certaines de ces suggestions, suivies de plusieurs envois des mêmes données. De cette façon, vous pouvez espérer que différentes erreurs seront introduites à différents endroits du flux et que vous pourrez déduire le nombre souhaité beaucoup plus facilement.