Uniquely decodable code
A uniquely decodable code is a type of non-singular code if any finite sequence of signs of the alphabet used by the code is the image of at most one message, ie the encoding function E is an injective function.
Formal definition
Code whose extension is non-singular. Let A be a source alphabet and B a code alphabet. Any function is called a coding function. f: A+ -> B+. The corresponding code is Uniquely Decodable (UD) if f is injective. It is part of the area of discrete mathematics and computational algorithms.
One way to calculate the best average length is by using the Kraft's inequality. The basic idea is to assign greater lengths to the words with less probability.
To clarify all this, we must go through steps:
- A code is a code word assignment wi{displaystyle w_{i}}, to a source of information either from null memory or memory (source of Markov). These words code wi{displaystyle w_{i}}, are only combinations of symbols of an alphabet T{displaystyle T}. For example: if we have the following source of null memory. S={s1,s2,s3!{displaystyle S={s_{1},s_{2},s_{3}} and we have the following alphabet T={0,1!{displaystyle T={0.1}, we can assign the following code to S{displaystyle S}, C={0,10,11!{displaystyle C={0,10,11}}. Which code is U.D.
- But what it means, accurately code Uniquely Decoded. It means that any encoding done with that code should not be ambiguous, that is, a possible message from the source 0100...... 11{displaystyle 0100dots 11} or any other, have one and only one interpretation s1s2s1...... s3{displaystyle s_{1}s_{2}s_{1}dots s_{3}}}}I mean, it's ambiguous.
- In fact, the Patterson-Sardins Theorem helps us to verify whether a code is U.D. or not, but here we must note that to prove that a code is not unevenly decoderable, it would be enough to find a chain that is ambiguous.
Contenido relacionado
Command & Conquer
Random access memory
Richard Stallmann