Construction of Instantaneous Codes
Consider encoding of a 5 symbol source into Binary instantaneous codes i.e. S = {s1, s2, s3, s4}, D = {0, 1}
We may start by assigning ‘ 0’ to s1
i.e. s1-> 0
If this is the case, to have prefix property, all other source symbols must correspond to code words beginning with 1. If we let s2 correspond to ‘ 1’, we would be left with no code symbol for encoding the remaining three source symbols. We might have
s2 -> 10
This in turn would require the remaining code words to start with 11. If
s3 -> 110;
then the only 3 bit prefix unused is 111 and we might set
s4 -> 1110
s5 -> 1111
Thus the possible instantaneous code is
s1 -> 00
s2 -> 01
s3 -> 10
s4 -> 110
s5 -> 111
One may wish to construct an instantaneous code by pre-specifying the word lengths. The necessary and sufficient conditions for the existence of such a code are provided by the ‘Kraft Inequality’
Statlearner
Statlearner