Variable-length code

VLDuniquely decodablevariable length codinguniquely decodable codevariable-length codingVariable-length encodingvariable-widthVLCnon-singularvariable length
In coding theory a variable-length code is a code which maps source symbols to a variable number of bits.wikipedia
54 Related Articles

Coding theory

algebraic coding theorycodingchannel code
In coding theory a variable-length code is a code which maps source symbols to a variable number of bits.

Huffman coding

HuffmanHuffman codeHuffman encoding
Some examples of well-known variable-length coding strategies are Huffman coding, Lempel–Ziv coding, arithmetic coding, and context-adaptive variable-length coding.
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).

Context-adaptive variable-length coding

CAVLCCAVLC entropy coding
Some examples of well-known variable-length coding strategies are Huffman coding, Lempel–Ziv coding, arithmetic coding, and context-adaptive variable-length coding.
Context-adaptive variable-length coding (CAVLC) is a form of entropy coding used in H.264/MPEG-4 AVC video encoding.

Sardinas–Patterson algorithm

In coding theory, the Sardinas–Patterson algorithm is a classical algorithm for determining in polynomial time whether a given variable-length code is uniquely decodable, named after August Albert Sardinas and George W. Patterson, who published it in 1953.

Quantization (signal processing)

quantizationquantization errorquantized
In the above formulation, if the bit rate constraint is neglected by setting \lambda equal to 0, or equivalently if it is assumed that a fixed-length code (FLC) will be used to represent the quantized data instead of a variable-length code (or some other entropy coding technology such as arithmetic coding that is better than an FLC in the rate–distortion sense), the optimization problem reduces to minimization of distortion D alone.

Code

encodingencodedencode
In coding theory a variable-length code is a code which maps source symbols to a variable number of bits.

Data compression

compressionvideo compressioncompressed
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. The latter are not very useful in the context of source coding, but often serve as error correcting codes in the context of channel coding.

Lossless compression

losslesslossless data compressioncompression
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.

Independent and identically distributed random variables

independent and identically distributedi.i.d.iid
With the right coding strategy an independent and identically-distributed source may be compressed almost arbitrarily close to its entropy.

Entropy (information theory)

entropyinformation entropyShannon entropy
With the right coding strategy an independent and identically-distributed source may be compressed almost arbitrarily close to its entropy.

LZ77 and LZ78

LZ77Lempel-ZivLempel–Ziv
Some examples of well-known variable-length coding strategies are Huffman coding, Lempel–Ziv coding, arithmetic coding, and context-adaptive variable-length coding.

Arithmetic coding

arithmetic coderarithmetic encodingarithmetic code
Some examples of well-known variable-length coding strategies are Huffman coding, Lempel–Ziv coding, arithmetic coding, and context-adaptive variable-length coding.

Formal language

formal language theoryformal languageslanguage
Using terms from formal language theory, the precise mathematical definition is as follows: Let S and T be two finite sets, called the source and target alphabets, respectively.

Alphabet (formal languages)

alphabetalphabetsinput symbol
Using terms from formal language theory, the precise mathematical definition is as follows: Let S and T be two finite sets, called the source and target alphabets, respectively.

Word (computer architecture)

wordwordsword size
A code is a total function mapping each symbol from S to a sequence of symbols over T, and the extension of C to a homomorphism of S^* into T^*, which naturally maps each sequence of source symbols to a sequence of target symbols, is referred to as its extension.

Homomorphism

homomorphichomomorphismse-free homomorphism
A code is a total function mapping each symbol from S to a sequence of symbols over T, and the extension of C to a homomorphism of S^* into T^*, which naturally maps each sequence of source symbols to a sequence of target symbols, is referred to as its extension.

Block code

linear block codedistanceblock encoding
A special case of prefix codes are block codes.

Forward error correction

FECchannel codingerror correcting codes
The latter are not very useful in the context of source coding, but often serve as error correcting codes in the context of channel coding.

Variable-length quantity

uintvarvariable-length quantities
Another special case of prefix codes are variable-length quantity codes, which encode arbitrarily large integers as a sequence of octets -- i.e., every codeword is a multiple of 8 bits.

FFV1

It can use either variable length coding or arithmetic coding for entropy coding.

List of binary codes

7-bit
Fixed-width binary codes use a set number of bits to represent each character in the text, while in variable-width binary codes, the number of bits may vary from character to character.

Prefix code

prefix-free codeprefix codesprefix-free
It is trivially true for fixed-length code, so only a point of consideration in variable-length code.

LEB128

LEB128 or Little Endian Base 128 is a form of variable-length code compression used to store an arbitrarily large integer in a small number of bytes.

Binary code

binarybinary encodingbinary codes
Those methods may use fixed-width or variable-width strings.