**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Variable-length code

Summary

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. This is in contrast to fixed-length coding methods, for which data compression is only possible for large blocks of data, and any compression beyond the logarithm of the total number of possibilities comes with a finite (though perhaps arbitrarily small) probability of failure.
Some examples of well-known variable-length coding strategies are Huffman coding, Lempel–Ziv coding, arithmetic coding, and context-adaptive variable-length coding.
Codes and their extensions
The extension of a code is the mapping of finite

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

Related publications (13)

Loading

Loading

Loading

Related units (1)

Related lectures (3)

Related courses (3)

EE-512: Applied biomedical signal processing

The goal of this course is twofold: (1) to introduce physiological basis, signal acquisition solutions (sensors) and state-of-the-art signal processing techniques, and (2) to propose concrete examples of applications for vital sign monitoring and diagnosis purposes.

EE-608: Deep Learning For Natural Language Processing

The Deep Learning for NLP course provides an overview of neural network based methods applied to text. The focus is on models particularly suited to the properties of human language, such as categorical, unbounded, and structured representations, and very large input and output vocabularies.

COM-401: Cryptography and security

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how they work and sketch how they can be implemented.

Related concepts (2)

Shannon, in his landmark 1948 paper, developed a framework for characterizing the fundamental limits of information transmission. Among other results, he showed that reliable communication over a channel is possible at any rate below its capacity. In 2008, Arikan discovered polar codes; the only class of explicitly constructed low-complexity codes that achieve the capacity of any binary-input memoryless symmetric-output channel. Arikan's polar transform turns independent copies of a noisy channel into a collection of synthetic almost-noiseless and almost-useless channels. Polar codes are realized by sending data bits over the almost-noiseless channels and recovering them by using a low-complexity successive-cancellation (SC) decoder, at the receiver. In the first part of this thesis, we study polar codes for communications. When the underlying channel is an erasure channel, we show that almost all correlation coefficients between the erasure events of the synthetic channels decay rapidly. Hence, the sum of the erasure probabilities of the information-carrying channels is a tight estimate of the block-error probability of polar codes when used for communication over the erasure channel. We study SC list (SCL) decoding, a method for boosting the performance of short polar codes. We prove that the method has a numerically stable formulation in log-likelihood ratios. In hardware, this formulation increases the decoding throughput by 53% and reduces the decoder's size about 33%. We present empirical results on the trade-off between the length of the CRC and the performance gains in a CRC-aided version of the list decoder. We also make numerical comparisons of the performance of long polar codes under SC decoding with that of short polar codes under SCL decoding. Shannon's framework also quantifies the secrecy of communications. Wyner, in 1975, proposed a model for communications in the presence of an eavesdropper. It was shown that, at rates below the secrecy capacity, there exist reliable communication schemes in which the amount of information leaked to the eavesdropper decays exponentially in the block-length of the code. In the second part of this thesis, we study the rate of this decay. We derive the exact exponential decay rate of the ensemble-average of the information leaked to the eavesdropper in Wyner's model when a randomly constructed code is used for secure communications. For codes sampled from the ensemble of i.i.d. random codes, we show that the previously known lower bound to the exponent is exact. Our ensemble-optimal exponent for random constant-composition codes improves the lower bound extant in the literature. Finally, we show that random linear codes have the same secrecy power as i.i.d. random codes. The key to securing messages against an eavesdropper is to exploit the randomness of her communication channel so that the statistics of her observation resembles that of a pure noise process for any sent message. We study the effect of feedback on this approximation and show that it does not reduce the minimum entropy rate required to approximate a given process. However, we give examples where variable-length schemes achieve much larger exponents in this approximation in the presence of feedback than the exponents in systems without feedback. Upper-bounding the best exponent that block codes attain, we conclude that variable-length coding is necessary for achieving the improved exponents.

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.

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

This paper investigates the achievable rates using variable length codes when transmitting independent informationover a degraded broadcast channel. In this note, we define the transmission rates from the perspective of the receivers and allow the decoders to make their decision at a different instant of time. We give an outer bound to the region of achievable rates, as well as examples of code that achieve this bound in some settings.

2008In multiple-user communications, the bursty nature of the packet arrival times cannot be divorced from the analysis of the transmission process. However, in traditional information theory the random arrival times are smoothed out by appropriated source coding and no consideration is made for the end-to-end delay. In this thesis, using tools from network theory, we investigate simple models that consider the end-to-end delay and/or the variability of the packet arrivals as important parameters, while staying in a information theoretic framework. First, we simplify the problem and focus on the transmission of a bursty source over a single-user channel. We introduce a new measure of channel features that enable us to incorporate the possibility to code among several packets in a scheduling problem. In this setup, we look for policies that minimize the average packet delay. Assuming that the packets are independent and sufficiently large to perform capacity achieving coding, we then consider the problem of allocating rates among a finite number of users communicating through a multiple-user channel. Following the previous work in the context of multiple-access channel, we formulate a scheduling problem in which the rate of each user is chosen from the capacity region of the multiple-user channel. Here, the goal is to find a scheduling policy that minimizes the sum of the transmitter queue lengths, such a policy is called delay optimal. In particular settings, for the additive Gaussian multiple-access channel we show the delay optimality of the Longer Queue Higher Rate policy introduced by Yeh. And, when the users communicate through a symmetric broadcast channel, we propose and show the delay optimality of a Best User Highest Possible Rate policy, among a large class of admissible policies. Finally, in the last part of this thesis, we look at the multiple-user channel coding problem from the perspective of the receivers. By measuring the transmission rates at the receivers, we are able to define variable length codes and to characterize the region of achievable rates when the receivers can decode their intended messages at different instants of time. For the two-user degraded broadcast channel and for the two-user multiple-access channel, we show that the gain in using variable length codes essentially comes from the possibility for the receivers to decode the transmitted messages in non-overlapping periods of time.