Código prefijo

Código prefijo

Un código prefijo es un código, típicamente un código de longitud variable, con la "propiedad de prefijo": ninguna palabra de código es prefijo de cualquier otra palabra de código del conjunto. Un código con las palabras de código {0, 10, 11} tiene la propiedad de prefijo; un código {0, 1, 10, 11} no la tiene, porque "1" es prefijo de tanto "10" como "11".

A los códigos prefijo también se les conoce como códigos sin prefijo y códigos instantáneos. Aunque la codificación Huffman es sólo uno de los muchos algoritmos para obtener códigos prefijo, a los códigos prefijo también se les llama "códigos Huffman", incluso cuando el código no se produjo con un algoritmo Huffman.

Usando códigos prefijo, un mensaje puede transmitirse como una secuencia de palabras de código concatenadas, sin ninguna señal fuera de banda para distinguir las palabras del mensaje. El receptor puede descodificar el mensaje sin ambigüedad, encontrando y quitando repetidamente los prefijos que forman una palabra de código válida. Esto no es posible con código que no tienen la propiedad de prefijo, como en nuestro ejemplo de {0, 1, 10, 11}: un receptor que leyera un "1" al principio de una palabra de código no sabría si éste es la palabra de código completa "1", o simplemente el prefijo de la palabra de código "10" o "11".

Los códigos Huffman de longitud variable, los prefijos telefónicos internacionales, las partes del país y la editorial del ISBN, y los códigos de sincronización secundaria usados en el estándar inalámbrico 3G UMTS W-CDMA son códigos prefijo. Los códigos prefijo también son una forma de codificación de entropía usados en compresión de datos sin pérdidas.

Los códigos prefijo no son códigos correctores de error. En la práctica, un mensaje puedes estar primero comprimido con un código prefijo, y después codificado de nuevo (con un código de corrección de errores) antes de la transmisión.

Contenido

Técnicas

Las técnicas para construir un código prefijo pueden ser simples, o bastante complicadas.

Si cada palabra en el código tiene la misma longitud, el código se llama código de longitud fija. Por ejemplo, las letras del ISO 8859-15 son siempre de 8 bits de longitud. Las letras del UTF-32/UCS-4 son siempre de 32 bits de longitud. Los paquetes ATM son siempre de 424 bits de longitud. Los prefijos no pueden existir en un código de longitud fija. Desafortunadamente, la codificación de longitud fija es ineficiente en situaciones donde algunas palabras son mucho más probables de ser transmitidas que otras.

Algunos códigos de longitud variable señalan el final de una palabra de código con un símbolo especial. Éste es de alguna manera análogo al punto del final de una frase; marca donde acaba una frase y comienza la siguiente. Si cada palabra de código acaba en un símbolo especial, y el símbolo especial no aparece en la palabra de código, es un código sin prefijo. Sin embargo, los sistemas de comunicación modernos envían todo como secuencias de "0" y "1" – añadir un tercer símbolo sería caro, y usarlo sólo al final de las palabras sería ineficiente. El código Morse es un ejemplo cotidiano de un código de longitud variable con un símbolo especial. Las pausas largas entre letras, y las pausas aún más largas entre palabras, ayudan a la gente a reconocer donde una letra (o palabra) acaba, y donde comienza la siguiente.

La codificación Huffman es una técnica más sofisticada para construir códigos prefijo de longitud variable. El algoritmo de codificación Huffman toma como entrada las frecuencias que las palabras de código derían tener, y construye un código prefijo que minimiza la media ponderada de la longitud de las palabras de código.

La desigualdad de Kraft caracteriza los conjuntos de longitudes de palabras de código que son posibles en un código prefijo.

Códigos prefijo en uso hoy en día

El sistema UTF-8 para codificar caracteres Unicode usando entre uno y cuatro bytes por carácter puede verse como una forma de codificación prefijo, como también los códigos VCR Plus+ y el sistema de códigos telefónicos de los países para la telefonía internacional.

Entre las técnicas comúnmente usadas para construir códigos prefijo se encuentran la codificación Shannon-Fano, la codificación Huffman, y los códigos universales con la codificación delta de Elias, la codificación gamma de Elias, la codificación omega de Elias, la codificación Fibonacci, y la codificación Levenshtein.

Referencias

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Código de aeropuertos de OACI — Bandera de la OACI. El Código de aeropuertos de OACI es un código de designación de aeropuertos compuesto de cuatro caracteres alfanuméricos que sirve para identificarlos alrededor del mundo. Dichos códigos son definidos por la Organización de… …   Wikipedia Español

  • Código de longitud variable — Se conoce como código de longitud variable (o varchar) en la teoría de la información a un código en donde su ancho de palabra es variable de longitud, es decir, al codificar el abecedario no es necesario hacerlo con el mismo número de bits cada… …   Wikipedia Español

  • Código unario — La codificación unaria es una codificación entrópica que representa a un número natural n, como un string de n unos. Por ejemplo, 5 se representa en código unario como 11111. Algunas representaciones utilizan un cero para reemplazar el último uno …   Wikipedia Español

  • Prefijo telefónico — Saltar a navegación, búsqueda Un prefijo telefónico (también llamado indicativo telefónico) es una sucesión numérica que se marca delante del número de usuario al realizar una llamada telefónica, con el propósito de seleccionar la demarcación… …   Wikipedia Español

  • Código de barras — EAN13 El código de barras es un código basado en la representación mediante un conjunto de líneas paralelas verticales de distinto grosor y espaciado que en su conjunto contienen una determinada información. De este modo, el código de barras… …   Wikipedia Español

  • Código Único de Identificación Laboral — El Código Único de Identificación Laboral (CUIL) es el número que se otorga a todo trabajador al inicio de su actividad laboral en relación de dependencia que pertenezca al Sistema Integrado de Jubilaciones y Pensiones (SIJP), y a toda otra… …   Wikipedia Español

  • Código Lyoko — Code Lyoko Logo de Código Lyoko Título Código Lyoko Género Ficción Creado por Thomas Romain y Tania Palumbo …   Wikipedia Español

  • prefijo — {{#}}{{LM P31413}}{{〓}} {{SynP32172}} {{[}}prefijo{{]}}, {{[}}prefija{{]}} ‹pre·fi·jo, ja› {{《}}▍ adj./s.m.{{》}} {{<}}1{{>}} {{♂}}En lingüística, referido a un morfema,{{♀}} que se une por delante a una palabra o a una raíz para formar derivados… …   Diccionario de uso del español actual con sinónimos y antónimos

  • Página de código 437 — Saltar a navegación, búsqueda La página de código 437 (code page 437, en inglés) de IBM PC o MS DOS, a menudo abreviado CP437 y también conocida como DOS US, OEM US o a veces incorrectamente referida como el OEM font, High ASCII o Extended… …   Wikipedia Español

  • Codificación Huffman — Árbol de Huffman generado para las frecuencias de apariciones exactas del texto Esto es un ejemplo de árbol de Huffman . las frecuencias y códigos de cada carácter se muestran abajo. Codificar esta frase usando este código requiere 156 bits, sin… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”