Data Compression and Shannon's Theorem: Shannon-Fano Coding

This lecture covers the Shannon-Fano coding method, which aims to represent sequences with the fewest bits per letter. By analyzing letter frequencies and minimizing differences between left and right partitions, the algorithm constructs efficient codes. The lecture demonstrates the step-by-step process of creating Shannon-Fano codes and compares them to Huffman codes. It also explores the concept of entropy and how it relates to the efficiency of the coding process. Through examples and calculations, students learn how to apply Shannon-Fano coding to achieve optimal data compression. The lecture concludes by discussing the implications of lossy compression methods in data storage and transmission.

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 (149)

Related concepts (34)

CS-119(d): Information, Computation, Communication

L'objectif de ce cours est d'introduire les étudiants à la pensée algorithmique, de les familiariser avec les fondamentaux de l'Informatique et de développer une première compétence en programmation (

Lossy compression

In information technology, lossy compression or irreversible compression is the class of data compression methods that uses inexact approximations and partial data discarding to represent the content. These techniques are used to reduce data size for storing, handling, and transmitting content. The different versions of the photo of the cat on this page show how higher degrees of approximation create coarser images as more details are removed. This is opposed to lossless data compression (reversible data compression) which does not degrade the data.

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

Lossless compression

Lossless compression is a class of data compression that allows the original data to be perfectly reconstructed from the compressed data with no loss of information. Lossless compression is possible because most real-world data exhibits statistical redundancy. By contrast, lossy compression permits reconstruction only of an approximation of the original data, though usually with greatly improved compression rates (and therefore reduced media sizes).

Compression artifact

A compression artifact (or artefact) is a noticeable distortion of media (including , audio, and video) caused by the application of lossy compression. Lossy data compression involves discarding some of the media's data so that it becomes small enough to be stored within the desired or transmitted (streamed) within the available bandwidth (known as the data rate or bit rate). If the compressor cannot store enough data in the compressed version, the result is a loss of quality, or introduction of artifacts.

Data compression

In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compression reduces bits by identifying and eliminating statistical redundancy. No information is lost in lossless compression. Lossy compression reduces bits by removing unnecessary or less important information.

Compression: Prefix-Free Codes COM-406: Foundations of Data Science

Explains prefix-free codes for efficient data compression and the significance of uniquely decodable codes.

Quantum Information PHYS-758: Advanced Course on Quantum Communication

Explores the CHSH operator, self-testing, eigenstates, and quantifying randomness in quantum systems.

JPEG 2000: Image Compression EE-550: Image and video processing

Explores image compression principles, focusing on JPEG 2000, covering transform-based coding, quantization, entropy coding, region of interest, error resilience, and software implementations.

Data Compression and Entropy: Conclusion CS-119(d): Information, Computation, Communication

Covers the definition of entropy, Shannon–Fano algorithm, and upcoming topics.

Data Compression and Shannon's Theorem Summary CS-119(d): Information, Computation, Communication

Summarizes Shannon's theorem, emphasizing the importance of entropy in data compression.