Kraft-McMillan Theorem

In course

Description

This lecture covers the Kraft-McMillan theorem, which states that if the codeword lengths of a D-ary code satisfy Kraft's inequality, then there exists a uniquely decodable prefix-free code with those lengths. The lecture also explores the proof of this theorem, including the concept of prefix-free codes, terminal leaves, and the importance of fulfilling Kraft's inequality. Additionally, exercises are provided to help understand the application of the theorem in constructing prefix-free codes. The lecture concludes with a detailed proof outline and important consequences of the Kraft-McMillan theorem.

Instructor

Official source

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

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related lectures (91)

Related concepts (74)

Code

In communications and information processing, code is a system of rules to convert information—such as a letter, word, sound, image, or gesture—into another form, sometimes shortened or secret, for communication through a communication channel or storage in a storage medium. An early example is an invention of language, which enabled a person, through speech, to communicate what they thought, saw, heard, or felt to others. But speech limits the range of communication to the distance a voice can carry and limits the audience to those present when the speech is uttered.

Variable-length code

In coding theory, a variable-length code is a code which maps source symbols to a variable number of bits. The equivalent concept in computer science is bit string. Variable-length codes can allow sources to be compressed and decompressed with zero error (lossless data compression) and still be read back symbol by symbol. With the right coding strategy an independent and identically-distributed source may be compressed almost arbitrarily close to its entropy.

Huffman coding

In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code is Huffman coding, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes". The output from Huffman's algorithm can be viewed as a variable-length code table for encoding a source symbol (such as a character in a file).

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.

Napoleonic Code

The Napoleonic Code (Code Napoléon), officially the Civil Code of the French (Code civil des Français; simply referred to as Code civil), is the French civil code established during the French Consulate period in 1804 and still in force, although frequently amended since. It was drafted by a commission of four eminent jurists and entered into force on 21 March 1804. The code, with its stress on clearly written and accessible law, was a major milestone in the abolition of the previous patchwork of feudal laws.