Quel algorithme pour des erreurs non rafales extrêmement élevées?

Question

J'ai un flux binaire qui a un taux d'erreur très élevé. Le taux d'erreur est de 50%, ce qui signifie que chaque bit a 50% de chances d'être inversé. L'erreur ne se produit pas en rafales et est complètement aléatoire, donc les codes de Reed & Solomon ne fonctionneraient pas bien.

Quel schéma ou algorithme dois-je appliquer au flux? Je ne me soucie pas du tout des frais généraux.

Tout cela est théorique, il est donc inutile de demander si je pouvais simplement réduire l'erreur du flux.

MODIFIER

Ne dites pas que ce n'est pas possible, la toute première réponse indiquant que c'est possible avec chaîne noisy théorème de codage.

Answer 1

Le théorème de codage de canal bruyant indique que vous pouvez réellement atteindre la capacité de Shannon pour le canal. Il ne dit pas que le canal a une capacité non nulle!

Si vous placez au hasard dans 100% des bits du canal, 50% d'entre eux resteront inchangés. Par conséquent, vous n'inversez que 50% des bits de manière aléatoire. Il devrait être évident que vous ne pouvez pas envoyer de données sur un tel canal - sa capacité Shannon est nulle.

Answer 2

Si le taux d'erreur est de 50%, alors c'est du bruit aléatoire, n'est-ce pas? Je veux dire, songez simplement à essayer de transmettre un seul bit. Si vous envoyez un flux infini du bit de droite, avec un taux d'erreur de 50%, vous obtiendrez des moitiés de 1 et de 0 si le bit de droite est à 1 ou à 0.

S'il s'agit en fait de moins de 50% (par exemple, 50% des bits seront "aléatoires" plutôt que "retournés"), vous pouvez simplement répéter les données - transmettez chaque bit 128 fois et déterminez lequel vous obtenez le plus. de pour chaque 100 bits reçus. C'est la solution simple à coder, extrêmement inefficace, pas mathématique:)

Answer 3

Eh bien, l’intérêt de la correction d’erreur Reed-Solomon est que la plupart des erreurs du monde réel se produisent lors de rafales, vous devez donc entrelacer et désentrelacer les données. Si vos erreurs sont complètement aléatoires, c'est-à-dire distribuées par Poisson, il vous suffira d'ajouter une redondance au flux de manière simple et efficace sur le plan mathématique. Vous pouvez notamment rechercher un modèle de Markov caché, tel que le code en treillis. est fondamentalement juste un moyen mathématiquement efficace d’ajouter de la redondance.

Consultez également le théorème de codage de canal bruyant. Ne s'applique pas aux données numériques, mais si votre source de ces bits est un processus analogique, ou si vous pouviez modéliser vos bits comme si ils étaient le résultat d'un processus analogique, cela pourrait vous donner un aperçu dans ce que vous pourriez faire de mieux. Cela vous évitera de perdre du temps à essayer de faire mieux que ce qui est mathématiquement possible.

Answer 4

Lorsque le canal approche le taux de bruit réel de 50%, il n’est plus possible de transmettre aucune information. Pour répondre à Jon Skeet, si le taux d'erreur est inférieur à 50% de bruit, vous pouvez obtenir des données en effectuant des rafales plus longues des données prévues de manière redondante et statistique, en regardant le résultat avec un certain niveau de confiance dans la valeur d'origine. La longueur de rafale nécessaire et les niveaux de confiance pour une longueur donnée seraient ensuite dérivés sur la base d'une caractérisation du bruit. Sachez toutefois que vous réduisez effectivement le débit de données pour améliorer le rapport signal sur bruit du flux transmis.

Dans votre question, vous avez peut-être exclu cette option, mais un meilleur schéma de codage pourrait être basé sur l'existence relative (ou non) du flux de données lui-même. En d'autres termes, pour transmettre un fichier binaire, envoyez un flux alternatif de 1/0. Pour envoyer un zéro, rien envoyer ou peut-être envoyer un niveau constant. L'idée est qu'émettre (et recevoir) n'importe quoi représente un état et envoyer (et recevoir) rien ne représente l'autre état. Cela ressemblerait effectivement à un type de codage bipolaire des données.

Answer 5

Si votre taux d'erreur est de 50%, le flux de bits EST aléatoire et ne porte AUCUNE CORRÉLATION au flux de bits d'origine. C'est comme si vous analysiez le flux avec un flux de bits complètement aléatoire, et le résultat est complètement aléatoire. Et vous ne pouvez rien y faire.

Le taux de bascule doit être inférieur à 50% pour que tout système fonctionne. Bien sûr, il pourrait être supérieur à 50%, mais vous pouvez d’abord inverser le flux, puis le traiter comme si le taux d’erreur était inférieur à 50%.

Si les erreurs sont complètement aléatoires et très fréquentes (par exemple, 25% des bits sont retournés), il est très difficile de concevoir un mécanisme de détection d’erreur robuste. Vous devez ajouter une quantité importante de redondance.

Answer 6

Avez-vous examiné les codes turbo?

- MarkusQ

Doh! J'ai mal compris que 50% étaient randomisés et non 50% inversés.

Answer 7

Si exactement 50% des bits sont inversés dans une transmission donnée au lieu que chaque bit soit inversé avec une probabilité de 50%, vous pouvez envoyer un bit d'information en envoyant une transmission de deux bits - - envoyez un 0 en tant que 00 et un 1 en tant que 01. Si le premier bit du mot de code reçu est 1, l'autre bit est annulé.