Scribd
Upload
21 views2 pages

Tunstal Code

The document discusses the construction of Tunstall codes, which are fixed-size codes encoding variable-length strings of input symbols, highlighting their advantage of non-propagating errors. It outlines an algorithm for developing the best n-bit Tunstall code for a given alphabet, detailing the iterative process of concatenating symbols based on their probabilities. An example is provided using an alphabet of three symbols with specified probabilities, demonstrating the construction of a 3-bit Tunstall code through iterations.

Uploaded by

Mir
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
21 views2 pages

Tunstal Code

The document discusses the construction of Tunstall codes, which are fixed-size codes encoding variable-length strings of input symbols, highlighting their advantage of non-propagating errors. It outlines an algorithm for developing the best n-bit Tunstall code for a given alphabet, detailing the iterative process of concatenating symbols based on their probabilities. An example is provided using an alphabet of three symbols with specified probabilities, demonstrating the construction of a 3-bit Tunstall code through iterations.

Uploaded by

Mir
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

The idea is to construct a set of fixed-size codes, each encoding a variable-size string of input symbols.

The lengths of Tunstall Codes are equal but the codes represent variable length of symbols.
The main advantage of a Tunstall code is that errors in codewords do not propagate, unlike other
variable-length codes, such as Huffman codes, in which an error in one codeword will cause a series
of errors to occur.
Instead of giving higher probability symbol fewer bits code, Tunstall coding concatenate symbol
having highest probability with every other symbol together to from strings replacing the original
symbol.
An n-bit Tunstall code should use all 𝟐 codes.
Thus, an algorithm is needed in order to develop the best n-bit Tunstall code for a given alphabet of N
symbols and such an algorithm is given:
Given an alphabet of N symbols, we start with a code table that consists of the symbols.

• Each iteration performs the following steps:


1. Select the symbol with largest probability in the table.
2. Remove the entry in the codebook that has the highest probability and add the N strings obtained by
concatenating this letter with every letter in the alphabet (including itself). This will increase the size
of the codebook from N to N(N − 1).
3. The probabilities of the new entries will be the product of the probabilities of the letters concatenated
to form the new entry.
4. Each time we perform this operation we increase the size of the codebook by N − 1. Therefore, this
operation can be performed K times, where N + K(N − 1) <=𝟐n
n=bits required for tunstall code
N= size of source (No of letters)
K= no of iterations

Ques: Given an alphabet with the three symbols {A, B,and C} with probabilities 0.7, 0.2, and 0.1,
respectively, construct 3-bit Tunstall codes?
Ans: Using this: N + K(N − 1) <=𝟐n
n=bits required for tunstall code (3)
N= size of source (No of letters) (3)
K= no of iterations (????)
3 + K(3 − 1) <=𝟐3
3+2K <=8
2K <=5
K<=2.5
K =𝟐
Code Table
Letters Prob
A 0.7
B 0.2
C 0.1
Code Table
Letters Prob
A 0.7
B 0.2
C 0.1
First Iteration
Letters Prob
B 0.2
C 0.1
AA 0.49
AB 0.14
AC 0.07
Code Table
Letters Prob.
A 0.7
B 0.2
C 0.1
First Iteration Second Iteration
Letters Prob. Letters Prob. Codeword
B 0.2 B 0.2 0 (000)
C 0.1 C 0.1 1 (001)

AA 0.49 AB 0.14 2 (010)


AB 0.14 AC 0.07 3 (011)
AC 0.07 AAA 0.343 4 (100)
AAB 0.098 5 (101)
AAC 0.049 6 (110)

You might also like