FIND ME ON

GitHub

LinkedIn

Uniquely Decodable

🌱

Definition
InfoTheory

Definition

A (K,n)(K,n) D-ary block code for the source is called uniquely decodable or lossless if the encoder: f:Xn{0,1,,D1}Kf:\mathcal{X}^n\to\{0,1,\cdots,D-1\}^Kis an invertible map (i.e. ff is bijective) and g=f1g=f^{-1} (i.e. the decoder is the inverted map of the encoder).

For a UD code, since ff is invertible, we have that Xn=DK|\mathcal{X}|^n=D^K hence the code rate RR is: R=Kn=logDXR=\frac{K}{n}=\log_D|\mathcal{X}| For such a code, the probability of decoding error Pe=0P_e=0 n1\forall n\ge1 or that the code is lossless!

A VLC is uniquely decodable (UD), (or lossless), if all finite sequences of source nn-tuples are mapped onto distinct sequences of codewords (f(x1n),,f(xKn))=(f(y1n),,f(yKn)) \mboxforK=K\mboxandxin=yin, i=1,,K(f(x_{1}^{n}),\cdots,f(x_{K}^{n}))=(f(y_{1}^{n}),\cdots,f(y_{K'}^{n})) \ \mbox{ for } K=K' \mbox{ and }x_{i}^{n}=y_{i}^{n}, \ i=1,\cdots,Kor that f is a injective map on all finite sequences of source nn-tuples. In other words, any concatenation of codewords can be uniquely decoded.

Linked from