Uniquely decodable code

format_list_bulleted Contenido keyboard_arrow_down
ImprimirCitar

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:

  1. 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.
  2. 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.
  3. 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

Command & Conquer is a real-time strategy video game franchise, originally created by Westwood Studios and later acquired by Electronic Arts. Command...

Random access memory

Random Access Memory is short-term storage memory. The operating system of computers or other devices uses RAM to temporarily store all programs and their...

Richard Stallmann

Richard Matthew Stallman often abbreviated as rms, is an American physicist, programmer, activist and founder of the free software movement, the GNU operating...
Más resultados...
Tamaño del texto:
undoredo
format_boldformat_italicformat_underlinedstrikethrough_ssuperscriptsubscriptlink
save