Prefix code

In a prefix code no codeword is the prefix of another, so concatenated messages have unique instantaneous decoding.

Kraft inequality

The lengths of every decipherable binary code satisfy

\sum_{i} 2^{- l_{i}} \leq 1.

Conversely, any positive integer lengths satisfying this bound can be realized by a prefix code.

McMillan inequality

The lengths of a finite uniquely decodable code satisfy

\sum_{a} 2^{- l (a)} \leq 1

, even when the code is not a prefix code. Distinct concatenations of

r

codewords remain distinct; counting the possible binary strings of each total length bounds

(\sum_{a} 2^{- l (a)})^{r}

by

r max_{a} l (a)

. Taking

r

th roots proves the claim.

Equivalence of decipherable and prefix code lengths

Prescribed positive word lengths admit a decipherable code if and only if they admit a prefix code. Counting length-

L

concatenations of

m

words proves the Kraft inequality for any decipherable code; choosing free vertices of the ordered

D

-ary tree constructs a prefix code whenever this inequality holds. Each prefix code has unique decodability.

Total length lower bound for a decipherable binary code

If a decipherable binary code has

N

codewords of lengths

l_{1}, \dots, l_{N}

, then

\sum_{i = 1}^{N} l_{i} \geq N lo g_{2} N .

This follows by applying the entropy lower bound with the uniform source distribution.

Shannon-Fano coding

Shannon--Fano coding assigns a symbol of probability

p_{i}

a prefix-code length near

- lo g_{2} p_{i}

.

Shannon coding

Cumulative Shannon code

Order source probabilities as

p_{1} \geq \dots \geq p_{N}

, put

b_{i} = \sum_{j < i} p_{j}, l_{i} = ⌈ - lo g_{2} p_{i} ⌉,

and take the first

l_{i}

binary digits of

b_{i}

as the codeword for symbol

i

. Since

b_{j} - b_{i} \geq p_{i} \geq 2^{- l_{i}}

for

j > i

, two cumulative probabilities cannot lie in the same dyadic interval selected by the earlier codeword. The resulting code is prefix-free.

Competitive optimality of the Shannon code

If the Shannon length is

l_{S} (x) = ⌈ lo g_{2} (1/ p_{x})⌉

and

l_{C}

is the length of any binary decipherable code, then

P {l_{S} (X) \geq l_{C} (X) + k} \leq 2^{- k + 1} .

Thus the probability that the Shannon code loses to another code by

k

or more bits decreases exponentially in

k

.

Entropy lower bound for prefix codes

Every binary prefix code has expected length at least its source entropy; Shannon lengths achieve expected length strictly below

H + 1

.

Shannon source coding theorem

For a discrete memoryless source of entropy

H

, every uniquely decodable binary code has expected length at least

H

. Shannon code lengths satisfy

H \leq \overline{ℓ} < H + 1

, and block coding can make the expected length per source symbol arbitrarily close to

H

.

 Ancestors (7)

 Incoming links (27)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Wikipedia Bot  1

A **prefix code** is a type of code used in coding theory and data compression. It is a set of codes where no code in the set is a prefix of any other code in the set. In simpler terms, this means that no complete codeword can be formed by concatenating one or more shorter codewords from the same set. The significance of prefix codes lies in their ability to facilitate unique decoding.

 Read the full article

  See all articles in the same topic Create my own version