Théorème Kraft-McMillan

Dans cours

Description

Cette séance de cours couvre le théorème Kraft-McMillan, qui affirme que si les longueurs des mots de code d'un code D-ary satisfont à l'inégalité de Kraft, alors il existe un code uniquement décodable sans préfixe avec ces longueurs. La séance de cours explore également la preuve de ce théorème, y compris le concept de codes sans préfixe, les feuilles terminales, et l'importance de remplir l'inégalité de Kraft. En outre, des exercices sont fournis pour aider à comprendre l'application du théorème dans la construction de codes sans préfixe. La séance de cours se termine par un exposé détaillé des preuves et des conséquences importantes du théorème Kraft-McMillan.

Connectez-vous pour regarder la vidéo

Enseignant

Source officielle

https://mediaspace.epfl.ch/media/0_io3dtksu

À 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.

Séances de cours associées (86)

Concepts associés (74)

Code à longueur variable

Dans la théorie des codes, le code à longueur variable est un code qui associe les symboles de la source à un nombre variable de bits. Les codes à longueur variable peuvent permettre à la source d'être compressée et décompressée avec une erreur nulle: il s'agit d'une compression sans perte. L'opération inverse du codage est alors possible pour chaque symbole. À partir d'une bonne stratégie de codage, une source i.i.d peut être compressée arbitrairement proche de son entropie, ce qui permet par exemple d'associer des mots longs aux symboles sources les moins fréquents.

Codage de Huffman

Le codage de Huffman est un algorithme de compression de données sans perte. Le codage de Huffman utilise un code à longueur variable pour représenter un symbole de la source (par exemple un caractère dans un fichier). Le code est déterminé à partir d'une estimation des probabilités d'apparition des symboles de source, un code court étant associé aux symboles de source les plus fréquents. Un code de Huffman est optimal au sens de la plus courte longueur pour un codage par symbole, et une distribution de probabilité connue.

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.

Block code

In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definition of block codes is conceptually useful because it allows coding theorists, mathematicians, and computer scientists to study the limitations of all block codes in a unified way.

Code civil (France)

Le Code civil des Français, appelé usuellement « Code civil » (souvent abrégé en « C.civ. », « C. Civ. » ou « CC »), « Code Napoléon » ou encore « Code napoléonien », est un code juridique qui regroupe les lois relatives au droit civil français, c’est-à-dire l'ensemble des règles qui déterminent le statut des personnes (livre ), celui des biens (livre II) et celui des relations entre les personnes privées (livres III et IV). Promulgué le (), par Napoléon Bonaparte, il reprend une partie des articles de la coutume de Paris et du droit écrit du Sud de la France.