Algorithme: Encodage minimal, correction d'erreur, aide s'il vous plaît?

Question

dire qu'il ya un tableau de 1024 bits qui sont tous des zéros:

exemple: [0,0,0,0,0,0,0, ...]

Je 20 zéros avec écraser les à des positions complètement au hasard:

exemple: [0,1,0,0,0,0,0, ...]

Quel est le nombre minimum théorique de bits nécessaires pour coder l'emplacement de ces 20 bits placés au hasard, en supposant que j'avais un codeur parfait? Je sais qu'il y a des équations de théorie de la communication qui me le diront, mais je veux vérifier mes calculs.

Question bonus plus difficile: Montrez-moi le code pour un algorithme qui implémente un encodage qui approche cette limite minimum.

Bonus bonus: Que se passe-t-il si le bit retourne le niveau d'octet au lieu du niveau de bit? par exemple. octets entiers retournés. Même résultat?

Answer 1

Si vous traitez une chaîne de 200 bits comme un tableau de vingt nombres de 10 bits, chacun listant la position de l'un des bits, vous économiserez 824 bits.

Mais je ne pense pas que ce soit le minimum. Par exemple, si vous traitez chacun des nombres par rapport à l'élément précédent au lieu d'une position absolue, une analyse peut montrer qu'en moyenne, vous n'avez besoin que de 8 bits pour encoder la distance jusqu'au bit suivant. Alors ajoutez un peu à l'avant: quand 0, alors 200 bits suivent avec des positions absolues. Quand 1, alors 160 bits suivent avec des positions relatives. Cela devrait donner un nombre moyen de bits inférieur pour encoder la valeur complète. Généraliser, c'est simplement la compression de données.

Il y a probablement beaucoup d'algorithmes de compression qui pourraient réduire le nombre moyen de bits requis pour encoder vos "vingt-et-un bits en 1024" à un très petit nombre. Calculer un arbre binaire approprié, en stocker une représentation, puis stocker les bits nécessaires pour traverser l'arbre donnerait probablement un algorithme très efficace (c'est en fait la base de la compression de données moderne).

Answer 2

Si vous utilisez un encodage basé sur un dictionnaire où le décodeur a également le dictionnaire, il n'y a pas de minimum absolu. Pour un codage en fonction de la fréquence, cependant, ce que vous devez est de calculer l'entropie:

E = -(P(0) * log_2(P(0)) + P(1) * log_2(P(1))) 
E = -(1004/1024 * log_2(1004/1024) + 20/1024 * log_2(20/1024)) 
E = 0.1388005 

Donc, chaque bit de l'entrée devrait exiger 0.1388005 bits de la sortie en moyenne. Au total:

0.1388005 * 1024 = 142.1317 bits. 

Cela signifie qu'en théorie, en utilisant un algorithme optimal, vous pouvez encoder une chaîne avec des zéros 1004 et 20 ceux (ou l'inverse) en utilisant 143 BITS.

Answer 3

plafond (log2 (1024 choisir 20)) = 139 bits de

(calculation on Wolfram Alpha)

Les autres réponses en disant 143 morceaux sortent que nous savons qu'il ya exactement 20 autres. Voici un codage concret pour montrer une façon d'utiliser cette connaissance: en utilisant arithmetic coding, envoyez successivement chacun des 1024 symboles '0' ou '1'. Le premier symbole est pondéré à 20/1024 probabilité d'être '1'; mais chaque symbole plus tard est pondéré différemment.Si le premier symbole était '0', utilisez 20/1023 sur le suivant; mais si c'était "1", utilisez 19/1023. Continuez de la même manière jusqu'à la fin. Le codage arithmétique fait tout le dur travail pour s'adapter à environ 139 bits, tant que nous lui disons les bonnes probabilités.

Sur le "bonus bonus": la correction d'erreur ne figurait pas dans la question initiale. Vous pouvez superposer un code de correction d'erreur à la première recherche d'un encodage optimal en supposant qu'il n'y a pas d'erreur, comme ci-dessus (et c'est normalement un bon moyen de décomposer le problème). Vous ne perdez aucune efficacité de codage de cette façon, même si je pense que vous pouvez perdre de la robustesse - comme si vous aviez plus d'erreurs que votre ECC peut corriger, le message apparaîtra-t-il comme une saleté totale ou se dégradera-t-il plus gracieusement?