Lecture

Shannon-Fano Codes

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

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

Description

This lecture introduces Shannon-Fano codes, a method for uniquely decodable and prefix-free coding. The instructor explains the definitions of uniquely decodable, prefix-free, and instantaneous codes, as well as encoding maps and trees. The lecture covers the Craft inequality and the existence of D-ary prefix-free codes. The instructor demonstrates the construction of a Shannon-Fano code for a given source distribution and discusses the optimality of these codes compared to the entropy. The lecture concludes by showing that Shannon-Fano codes are not optimal but provide a close approximation to the entropy, making them a practical choice for coding applications.

Instructors (2)

Bixio Rimoldi

Bixio Rimoldi received the Dipl. El.-Ing degree as well as the Dr. ès Sciences degree from the ETHZ, Switzerland. Since 1997, he holds a full professor position at the School of Computer and Communication Sciences at EPFL and he is the director of EPFL's Mobile Communications Laboratory (LCM). Prior to joining EPFL, he was in the faculty of the Electrical Engineering department of Washington University. In 1993, he received a US National Science Foundation Young Investigator Award. In 2000, he was elected to the grade of Fellow of the IEEE. During the period 2002-2009 he has been on the Board of Governors of the IEEE Information Theory Society, where he served in several offices including President. He was co-chairman with Bruce Hajek of the 1995 IEEE Information Theory Workshop on Information Theory, Multiple Access, and Queueing (St Louis, MO), and co-chairman with Jim Massey of the 2002 IEEE International Symposium in Information Theory (Lausanne, Switzerland). He has been a member of the editorial board of "Foundations and Trends on Communications and Information Theory," and was an editor of the European Transactions on Telecommunications. During 2005 and 2006 he was the Director of EPFL's Bachelor program in Communication Systems. His interests are in various aspects of digital communications, information theory, and software-defined radio.

Michael Christoph Gastpar

Michael Gastpar is a (full) Professor at EPFL. From 2003 to 2011, he was a professor at the University of California at Berkeley, earning his tenure in 2008. He received his Dipl. El.-Ing. degree from ETH Zürich, Switzerland, in 1997 and his MS degree from the University of Illinois at Urbana-Champaign, IL, USA, in 1999. He defended his doctoral thesis at EPFL on Santa Claus day, 2002. He was also a (full) Professor at Delft University of Technology, The Netherlands. His research interests are in network information theory and related coding and signal processing techniques, with applications to sensor networks and neuroscience. He is a Fellow of the IEEE. He is the co-recipient of the 2013 Communications Society & Information Theory Society Joint Paper Award. He was an Information Theory Society Distinguished Lecturer (2009-2011). He won an ERC Starting Grant in 2010, an Okawa Foundation Research Grant in 2008, an NSF CAREER award in 2004, and the 2002 EPFL Best Thesis Award. He has served as an Associate Editor for Shannon Theory for the IEEE Transactions on Information Theory (2008-11), and as Technical Program Committee Co-Chair for the 2010 International Symposium on Information Theory, Austin, TX.

Official source

Ontological neighbourhood

Information engineering

Information theory: Coding theory

Related concepts (18)

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

Coding theory

Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied by various scientific disciplines—such as information theory, electrical engineering, mathematics, linguistics, and computer science—for the purpose of designing efficient and reliable data transmission methods.

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.

Prefix code

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

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.

Related lectures (64)

Compression: Prefix-Free Codes

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

Information Theory: Source Coding, Cryptography, Channel Coding

Covers source coding, cryptography, and channel coding in communication systems, exploring entropy, codes, error channels, and future related courses.

Source Coding: Compression

Covers entropy, source coding, encoding maps, decodability, prefix-free codes, and Kraft-McMillan's inequality.

Data Compression and Shannon's Theorem Summary

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

Entropy and Algorithms: Applications in Sorting and Weighing