Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Code préfixe
Résumé
A prefix code is a type of code system distinguished by its possession of the "prefix property", which requires that there is no whole code word in the system that is a prefix (initial segment) of any other code word in the system. It is trivially true for fixed-length code, so only a point of consideration in variable-length code.
For example, a code with code words {9, 55} has the prefix property; a code consisting of {9, 5, 59, 55} does not, because "5" is a prefix of "59" and also of "55". A prefix code is a uniquely decodable code: given a complete and accurate sequence, a receiver can identify each word without requiring a special marker between words. However, there are uniquely decodable codes that are not prefix codes; for instance, the reverse of a prefix code is still uniquely decodable (it is a suffix code), but it is not necessarily a prefix code.
Prefix codes are also known as prefix-free codes, prefix condition codes and instantaneous codes. Although Huffman coding is just one of many algorithms for deriving prefix codes, prefix codes are also widely referred to as "Huffman codes", even when the code was not produced by a Huffman algorithm. The term comma-free code is sometimes also applied as a synonym for prefix-free codes but in most mathematical books and articles (e.g.) a comma-free code is used to mean a self-synchronizing code, a subclass of prefix codes.
Using prefix codes, a message can be transmitted as a sequence of concatenated code words, without any out-of-band markers or (alternatively) special markers between words to frame the words in the message. The recipient can decode the message unambiguously, by repeatedly finding and removing sequences that form valid code words. This is not generally possible with codes that lack the prefix property, for example {0, 1, 10, 11}: a receiver reading a "1" at the start of a code word would not know whether that was the complete code word "1", or merely the prefix of the code word "10" or "11"; so the string "10" could be interpreted either as a single codeword or as the concatenation of the words "1" then "0".
Source officielle
À 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.
Proximité ontologique
Cours associés (19)
COM-406: Foundations of Data Science
We discuss a set of topics that are important for the understanding of modern data science but that are typically not taught in an introductory ML course. In particular we discuss fundamental ideas an
COM-102: Advanced information, computation, communication II
Text, sound, and images are examples of information sources stored in our computers and/or communicated over the Internet. How do we measure, compress, and protect the informatin they contain?
COM-404: Information theory and coding
The mathematical principles of communication that govern the compression and transmission of data and the design of efficient methods of doing so.
Séances de cours associées (77)
Correction d'erreur quantique : Code du shor
Couvre les principes de correction d'erreur quantique, en se concentrant sur le code de correction d'erreur quantique de Shor.
Compression: Connexion forte et codes sans préfixe
Explore la relation entre la longueur des mots de code et la distribution des probabilités, en se concentrant sur la conception de codes sans préfixe pour une compression efficace.
Le théorème de ShannonMOOC: Information, Calcul, Communication: Introduction à la pensée informatique
Introduit le théorème de Shannon sur les codes binaires, l'entropie et les limites de compression des données.
Publications associées (160)
Personnes associées (35)
Unités associées (5)
Concepts associés (4)
Code universel
En compression de données, un code universel est un code préfixe dont les mots ont une longueur dont l'espérance mathématique ne dépasse pas celle de la longueur des mots du code optimal à un facteur constant près. Les codages gamma, delta et omega d'Elias, les codages Zeta, de Fibonacci, de Levenshtein, d'Even-Rodeh produisent des codes préfixes et universels. Les codages unaire, de Rice et de Golomb produisent des codes préfixes non universels. Codage entropique Catégorie:Codage entropique Catégorie:Théo
Codage entropique
Le codage entropique (ou codage statistique à longueur variable) est une méthode de codage de source sans pertes, dont le but est de transformer la représentation d'une source de données pour sa compression ou sa transmission sur un canal de communication. Les principaux types de codage entropique sont le codage de Huffman et le codage arithmétique. Le codage entropique utilise des statistiques sur la source pour construire un code, c'est-à-dire une application qui associe à une partie de la source un mot de code, dont la longueur dépend des propriétés statistiques de la source.
Code (information)
vignette|redresse|Code morse international. En sciences et techniques, notamment en informatique et en théorie de l'information, un code est une règle de transcription qui, à tout symbole d'un jeu de caractères (alphabet source) assigne de manière univoque un caractère ou une chaîne de caractères pris dans un jeu de caractères éventuellement différent (alphabet cible). Un exemple est le code morse qui établit une relation entre lettres de l'alphabet latin et des séquences de sons courts et longs.