Publication

Polarization and randomness extraction

Emmanuel Abbé
2011
Conference Papers

Résumé

This paper explores a connection between randomness extraction and channel (source) coding problems. It is explained how efficient extractors can be used to define efficient coding schemes and reciprocally, a new deterministic extractor based on a polar coding scheme is proposed. Since the source model used in extractors for computer science (cryptography) do not assume i.i.d. or known distributions, a generalized polarization phenomenon for sources with block memory and unknown distributions is developed. It is shown that in this setting, the min-entropy (as usual in extractors) rather than Shannon entropy can be efficiently extracted. The derived polar coding results also apply to compound channels with memory.

Source officielle

https://infoscience.epfl.ch/entities/publication/f2714fae-24d5-4ad1-9a43-560331b8c9ae

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Emmanuel Abbé
2011
Conference Papers

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/f2714fae-24d5-4ad1-9a43-560331b8c9ae

À propos de ce résultat

Concepts associés (32)

Théorie des codes

En théorie de l'information, la théorie des codes traite des codes et de leurs propriétés et de leurs aptitudes à servir sur différents canaux de communication. On distingue deux modèles de communication : avec et sans bruit. Sans bruit, le codage de source suffit à la communication. Avec bruit, la communication est possible avec les codes correcteurs. En définissant l'information de façon mathématique, l'étape fondatrice de la théorie des codes a été franchie par Claude Shannon.

Loi normale

En théorie des probabilités et en statistique, les lois normales sont parmi les lois de probabilité les plus utilisées pour modéliser des phénomènes naturels issus de plusieurs événements aléatoires. Elles sont en lien avec de nombreux objets mathématiques dont le mouvement brownien, le bruit blanc gaussien ou d'autres lois de probabilité. Elles sont également appelées lois gaussiennes, lois de Gauss ou lois de Laplace-Gauss des noms de Laplace (1749-1827) et Gauss (1777-1855), deux mathématiciens, astronomes et physiciens qui l'ont étudiée.

Randomness extractor

A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weak entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent from the source and uniformly distributed. Examples of weakly random sources include radioactive decay or thermal noise; the only restriction on possible sources is that there is no way they can be fully controlled, calculated or predicted, and that a lower bound on their entropy rate can be established.

Afficher plus

Publications associées (8)

Afficher plus

Polarization and randomness extraction

Chattez avec Graph Search

Analysis of Topography, Climate, Soil and Viticulture in Switzerland and Europe

A methodology for the rigorous verification of plasma simulation codes

Simulation based Synthesis of Population