Quelles sont les applications théoriques des codes de correction d'erreur en plus de la correction d'erreur elle-même? Je connais trois applications: le théorème de Goldreich-Levin sur le trépan dur, la construction d’un extracteur par Trevisan et l’ amplification de la dureté de la fonction...
Je recherche des codes correcteurs d'erreurs du type suivant: codes binaires à débit constant, décodable à partir d'une fraction constante d'erreurs, par un décodeur réalisable en tant que circuit booléen de taille , où est la longueur de codage.O(N)O(N)O(N)NNN Quelques antécédents: Spielman, dans...
Le code de Huffman pour une distribution de probabilité est le code de préfixe avec la longueur moyenne pondérée minimale du mot de code , où est la longueur du ème mot de code. C'est un théorème bien connu que la longueur moyenne par symbole du code Huffman est comprise entre et , où est...
L'algorithme DEFLATE populaire utilise le codage Huffman au-dessus de Lempel-Ziv. En général, si nous avons une source aléatoire de données (= entropie 1 bit / bit), aucun encodage, y compris Huffman, n'est susceptible de le compresser en moyenne. Si Lempel-Ziv était "parfait" (ce qu'il approche...
La matrice a la dimension . Nous voulons remplir utilisant des entiers compris entre et , inclus.n × n ( n - 1 ) A 1 nUNEAAn × n ( n - 1 )n×n(n−1)n \times n(n-1)UNEAA111nnn Exigences: Chaque colonne de est une permutation de .1 , … , nUNEAA1 , … , n1,…,n1, \dots, n Toute sous-matrice formée de deux...
Soit une matrice ( ) réelle avec la propriété que toute collection de colonnes est de rang complet.k ≤ n A kk × nk×nk\times nk ≤ nk≤nk\le nUNEUNE{\bf A}kkk Q: Existe - t-il un moyen efficace de trouver de manière déterministe un vecteur tel que la matrice augmentée conserve la même propriété que :...
Je veux commencer à apprendre le codage réseau: http://en.wikipedia.org/wiki/Network_coding Connaissez-vous une bonne enquête (par exemple à partir des enquêtes et des tutoriels IEEE) sur les sujets ci-dessus. J'ai trouvé des cours universitaires sur google mais j'aimerais avoir des recommandations...
Existe-t-il une construction connue d'un code de correction d'erreur linéaire E C C : Fnq→ FmqECC:Fqn→Fqm\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^m (avec des paramètres raisonnables), de sorte que lorsqu'il est donné un vecteur booléen v ∈ { 0 , 1 }nv∈{0,1}nv\in \{0,1\}^n , il renvoie également...
Je voulais savoir quelles sont les applications de SGT dans le domaine de la théorie de l'information et du codage et peut-être des communications. Le plus lié qui me vient à l'esprit est le travail sur les codes d'extension Michael Sipser et Daniel Spielman, "Expander Codes", IEEE Transactions on...