Concept# Huffman coding

Summary

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). The algorithm derives this table from the estimated probability or frequency of occurrence (weight) for each possible value of the source symbol. As in other entropy encoding methods, more common symbols are generally represented using fewer bits than less common symbols. Huffman's method can be efficiently implemented, finding a code in time linear to the number of input weights if these weights are sorted. However, although optimal among methods encodi

Official source

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 publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related people (8)

Related courses (15)

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 and techniques that come from probability, information theory as well as signal processing.

DH-405: Foundations of digital humanities

This course gives an introduction to the fundamental concepts and methods of the Digital Humanities, both from a theoretical and applied point of view. The course introduces the Digital Humanities circle of processing and interpretation, from data acquisition to new understandings.

COM-621: Advanced Topics in Information Theory

The class will focus on information-theoretic progress of the last decade. Topics include: Network Information Theory ; Information Measures: definitions, properties, and applications to probabilistic models.

Related publications (72)

Loading

Loading

Loading

Related units (3)

Related concepts (17)

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.

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 b

Entropy (information theory)

In information theory, the entropy of a random variable is the average level of "information", "surprise", or "uncertainty" inherent to the variable's possible outcomes. Given a discrete random vari

In this paper, we study the redundancy of Huffman codes. In particular, we consider sources for which the probability of one of the source symbols is known. We prove a conjecture of Ye and Yeung regarding the upper bound on the redundancy of such Huffman codes, which yields in a tight upper bound. We also derive a tight lower bound for the redundancy under the same assumption. We further apply the method introduced in this paper to other related problems. It is shown that several other previously known bounds with different constraints follow immediately from our results.

Oscillatory patterns of activity in various frequency ranges are ubiquitously expressed in cortical circuits. While recent studies in humans emphasized rhythmic modulations of neuronal oscillations ("second-order" rhythms), their potential involvement in information coding remains an open question. Here, we show that a rhythmic (similar to 0.7 Hz) modulation of hippocampal theta power, unraveled by second-order spectral analysis, supports encoding of spatial and behavioral information. The phase preference of neuronal discharge within this slow rhythm significantly increases the amount of information carried by action potentials in various motor/cognitive behaviors by (1) distinguishing between the spikes fired within versus outside the place field of hippocampal place cells, (2) disambiguating place firing of neurons having multiple place fields, and (3) predicting between alternative future spatial trajectories. This finding demonstrates the relevance of second-order spectral components of brain rhythms for decoding neuronal information.

Nicolae Cleju, Pascal Frossard, Nikolaos Thomos

Network coding permits to deploy distributed packet delivery algorithms that locally adapt to the network availability in media streaming applications. However, it may also increase delay and computational complexity if it is not implemented efficiently. We address here the effective placement of nodes that implement randomized network coding in overlay networks, so that the goodput is kept high while the delay for decoding stays small in streaming applications. We first estimate the decoding delay at each client, which depends on the innovative rate in the network. This estimation permits to identify the nodes that have to perform coding for a reduced decoding delay. We then propose two iterative algorithms for selecting the nodes that should perform network coding. The first algorithm relies on the knowledge of the full network statistics. The second algorithm uses only local network statistics at each node. Simulation results show that large performance gains can be achieved with the selection of only a few network coding nodes. Moreover, the second algorithm performs very closely to the central estimation strategy, which demonstrates that the network coding nodes can be selected efficiently in a distributed manner. Our scheme shows large gains in terms of achieved throughput, delay and video quality in realistic overlay networks when compared to methods that employ traditional streaming strategies as well as random network nodes selection algorithms.

2011Related lectures (21)