Codificación desigual. Longitud media de codificación. Tecnologías de la información

La idea de guardar el número de caracteres con codificación desigual es asignar palabras más cortas a mensajes más probables (repetidos con más frecuencia) y, por el contrario, palabras más largas a mensajes menos probables (frecuentes). Esto garantiza un número medio bajo de caracteres por mensaje. Sin embargo, es necesario cuidar simultáneamente decodificación inequívoca. Este último se proporciona, en particular, para códigos de prefijo en los que ninguna palabra es el fragmento inicial ( prefijo) otro.

Ejemplo 1.3.1 El siguiente código ( METRO=4) no es únicamente decodificable:

De hecho, si la combinación 00111111 aparece en la salida del codificador, se puede leer como incógnita 1 , incógnita 2 , incógnita 3 , incógnita 4, o incógnita 1 , incógnita 2 , incógnita 4 , incógnita 3, o incógnita 1 , incógnita 1 , incógnita 4 , incógnita 4, o incógnita 1 , incógnita 1 , incógnita 3 , incógnita 3 , incógnita 3 .

Ejemplo 1.3.2 A diferencia del anterior, el siguiente código ( METRO=4) tiene prefijo y, por lo tanto, es decodificable de forma única:

Entonces, si la secuencia en la salida del codificador es 0011010111110, se puede decodificar de la única manera: incógnita 1 , incógnita 1 , incógnita 3 , incógnita 2 , incógnita 4 , incógnita 3 .

Cualquier código de prefijo se puede decodificar instantáneamente. Esto significa que cualquiera de sus palabras puede ser reconocida inmediatamente tras la aparición del último de sus personajes.

Teorema 1.3.1 (desigualdad de Kraft). Código que contieneMETRO palabras de código, pueden tener prefijos si y sólo si la longitud de sus palabras de códigonorte 1 , norte 2 , …, norte Msujeto a la desigualdad

La longitud promedio de un código impar está determinada por la igualdad

Teorema 1.3.2 La longitud promedio de los mejores códigos de prefijo se encuentra dentro de

Código Shannon-Fano

En el primer paso del algoritmo considerado, el conjunto fuente se divide en dos subconjuntos, cuyas probabilidades totales son lo más cercanas posible entre sí, es decir a 1/2. A todos los mensajes del primero de los subconjuntos se les asigna el primer símbolo de la palabra de código 0, y al segundo, el primer símbolo 1. En el segundo paso, cada uno de los subconjuntos se divide nuevamente en dos con las probabilidades acumulativas más cercanas posibles, y las palabras de código del primero de los subconjuntos resultantes reciben 0 como segundo símbolo, y el segundo – 1, etc. Tan pronto como el mensaje es único en el subconjunto, se verifica su codificación. El procedimiento se repite hasta que se agoten todos los mensajes del conjunto.

Es fácil demostrar que la longitud promedio del código Shannon-Fano satisface la desigualdad de la derecha del Teorema 1.3.2:

Ejemplo 1.3.3 Codifiquemos una fuente discreta. METRO= 8 mensajes que tienen las probabilidades enumeradas en la tabla.

incógnita	pag(incógnita)
incógnita 1	0.40
incógnita 2	0.20
incógnita 3	0.15
incógnita 4	0.10
incógnita 5	0.05
incógnita 6	0.04
incógnita 7	0.03
incógnita 8	0.03

En este caso iniciar sesión METRO=3, entropía de fuenteh(incógnita)"2,44 bits , A Longitud promedio de la palabra clave:

código huffman

Este código es óptimo en el sentido de que ningún código de prefijo puede tener una longitud de palabra promedio más corta. En el primer paso de la codificación de Huffman, los dos mensajes menos probables se combinan en un mensaje total, cuya probabilidad es igual a la suma de las probabilidades de los originales. En este caso, a uno de los mensajes originales se le asigna el símbolo de código 0 y al otro, 1. En el segundo paso, se repite lo mismo con un nuevo conjunto de METRO-1 mensajes y nuevamente los dos mensajes menos probables se combinan en uno, asignando el carácter 0 a uno de ellos y 1 al otro. Se repite el procedimiento METRO-1 vez, es decir, hasta el paso en el que a uno de los dos mensajes restantes se le asigna el símbolo 0 y al otro - 1. El resultado es árbol de código, leyendo de derecha a izquierda, se forman palabras clave para todos los mensajes del conjunto codificado.

Es más conveniente, al iniciar el procedimiento de codificación, anotar todos los mensajes en orden descendente de probabilidades. También cabe señalar que, a diferencia del algoritmo de Shannon-Fano, durante la codificación de Huffman, cualquier palabra de código aparece en orden inverso.

El siguiente ejemplo ilustra el proceso de codificación y demuestra la ventaja comparativa del código Huffman.

Ejemplo 1.3.4 Codifiquemos Huffman el conjunto del Ejemplo 1.3.3:

Longitud promedio:

Ejemplo 16. Codifique los mensajes fuente que figuran en la Tabla 7 utilizando código binario Huffman. Evaluar la efectividad del código resultante.

Solución. De acuerdo con el algoritmo para construir el código Huffman, realizamos los siguientes pasos secuencialmente:

1) organizamos los mensajes fuente en orden descendente de probabilidades;

2) formamos un alfabeto auxiliar combinando las letras más improbables tu 1 y tu 4 (metro 0 =2), entonces la probabilidad de una nueva letra es pag 1 =r(tu 1)+r(tu 4)=0,1+0,05=0,15. Dejamos esta carta en su lugar, ya que pag 1 =r(tu 6);

3) combinar la primera letra auxiliar y la letra tu 6 , entonces la probabilidad de la segunda letra auxiliar es r 2 =r 1 +r(tu 6)=0,15+0,15=0,3; lo subimos de acuerdo con esta probabilidad;

4) seguimos combinando hasta que solo quede un mensaje en el conjunto con probabilidad uno.

La construcción del código Huffman se muestra en la Fig. 4.

Los mensajes fuente son ahora los nodos hoja del árbol de código. Habiendo asignado los valores de símbolo 1 y 0 a los nodos finales, escribimos las designaciones de código usando la siguiente regla: para obtener la palabra de código correspondiente al mensaje tu 4, tracemos la transición tu 4 en el grupo con mayor probabilidad, escribimos los símbolos del código de derecha a izquierda (del menos significativo al más significativo), obtenemos 1100.

Para mensaje tu 1-1101, etc. (ver figura 4).

Evaluemos la eficiencia del código resultante.

Entropía de origen del mensaje:

por letra en la salida de origen.

Longitud promedio de la palabra clave (fórmula (4.14))

Para evaluar la eficiencia del código, utilizamos el coeficiente de eficiencia.

Para un código binario óptimo y .

El código que recibimos tiene redundancia. R=0,0109, es decir El código está cerca de ser óptimo.

Ejemplo 17. Mensaje fuente incógnita está compuesto por letras estadísticamente independientes extraídas del alfabeto A, B, C con probabilidades de 0,7; 0,2; 0.1. Realice codificación binaria utilizando el método Shannon-Fano de letras individuales y bloques de dos letras. Compare códigos según su efectividad.

Solución. Realizamos codificación letra por letra utilizando el método Shannon-Fano.

1) Organizamos las letras del alfabeto fuente en orden descendente de probabilidades.

2) Divida el alfabeto fuente en dos ( metro=2) grupos aproximadamente igualmente probables. Asignamos 1 como primer carácter de código a todos los mensajes del grupo superior (letra A) y asignamos 0 a todos los mensajes del grupo inferior.

3) Hacemos una segunda división en dos grupos (letras B y C) y nuevamente asignamos el símbolo 1 a la letra del grupo superior (B), y asignamos 0 a la letra del grupo inferior (C) como segundo símbolo. de la palabra clave Como había una letra en cada grupo, terminamos de codificar. El resultado se muestra en la tabla. 8.

Evaluemos la eficiencia del código resultante. Entropía de origen

Longitud promedio de palabra de código

vemos que l>h(incógnita), y factor de eficiencia

y redundancia R 1 =0,1102.

Demostremos que la codificación en bloques de 2 letras ( k=2) aumenta la eficiencia del código. Construimos un alfabeto auxiliar a partir de norte=3 2 cuadras. Encontramos las probabilidades de bloque usando la fórmula (1.8), considerando las letras del alfabeto original como independientes. Organizamos los bloques en orden descendente de probabilidades y realizamos la codificación mediante el método de Shannon-Fano. Todos los bloques de dos letras obtenidos, sus probabilidades y códigos correspondientes se resumen en la tabla. 9.

Con la codificación de bloques, la longitud promedio de una palabra de código por letra

Al mismo tiempo, el coeficiente de eficiencia.

Redundancia en codificación de dos letras R 2 =0,0045.

Tenemos γ 2 > γ 1, R 2 <<R 1, que es lo que había que mostrar.

Ejemplo 18. El método de codificación lo especifica la tabla de códigos.

a) crear una matriz de distancias

b) encontrar la distancia del código;

c) determinar la multiplicidad de errores detectados y corregidos;

d) determinar la redundancia del código, suponiendo que las letras fuente sean igualmente probables.

Solución. a) Escribimos la matriz de distancias en forma de tabla (Tabla 10).

b) Según la tabla. 10 encontrar la distancia del código

c) La multiplicidad de errores detectados está determinada por la fórmula (3.5), de donde q≤3.

La multiplicidad de errores corregidos se encuentra utilizando la fórmula (3.6) q y ≤1,5.

Por lo tanto, el código proporcionado le permite detectar todo tipo de errores simples, dobles y triples y corregir cualquier error simple.

d) Encontramos redundancia de código a partir de las siguientes consideraciones. Para transmitir señales igualmente probables. un 1, un 2, un 3, un 4 basta con transmitir las palabras de código 00, 10, 01 y 11, respectivamente. Dicho código no tiene redundancia, pero no permite detectar errores y mucho menos corregirlos. Para detectar y corregir errores se introducen cinco caracteres redundantes, es decir cuantitativamente la redundancia es igual a .

Ejemplo 19. Un código de bloque lineal (5,2) viene dado por una matriz generadora GRAMO en forma sistemática (canónica)

Deja que el vector sea aceptado. b=00110 y se sabe que sólo son posibles errores individuales.

Realice la decodificación utilizando los siguientes métodos:

a) a una distancia mínima;

b) cálculo del síndrome.

Solución. Si la matriz generadora está escrita en forma canónica, esto significa que consta de dos bloques: una matriz diagonal de tamaño k k, que consta de unidades y una matriz rectangular de tamaño r k. En este caso, la primera k Los caracteres de cualquier palabra clave son informativos.

matriz de cheques norte También se puede escribir en forma canónica y consta de dos bloques. El primer bloque es una matriz rectangular de tamaño. k r, obtenido transponiendo el segundo bloque de la matriz GRAMO. Como segundo bloque de la matriz. norte escribir una matriz diagonal de tamaño r r, compuesto por unidades.

Para el código dado obtenemos

.

Asegurémonos de que la matriz obtenida de esta manera norte satisface la relación (3.18). En realidad,

aquellos. los 6 elementos de la matriz ght son iguales a cero.

Construyamos una tabla de códigos usando la regla para la formación de palabras de código según la fórmula (3.21):

un 1=00000, un 2=10110, un 3=01011, un 4= 11101=un 2+un 3.

En total, la tabla de códigos contiene 2 k= 4 vectores.

A partir de la tabla de códigos determinamos el valor de la distancia del código.

En consecuencia, el código en cuestión detecta errores simples y dobles y corrige errores simples.

Decodificando el vector recibido b = 00110.

a) El método de decodificación de distancia mínima es el que, habiendo calculado las distancias del vector b relativo a todos los vectores y yo tabla de códigos, identificamos el vector recibido con aquel cuya distancia es mínima. Distancias reb se dan en la tabla. 11.

Por tamaño reb mín=1 decidimos que se transmitió un vector un 2=10110, por lo tanto, el error está en el primer símbolo de la palabra clave y la secuencia de información tiene la forma incógnita = 10.

b) El método de decodificación mediante cálculo de síndrome incluye las siguientes operaciones:

1) Usando la fórmula (3.17), establecemos de antemano una conexión inequívoca entre los vectores de errores únicos mi y sus correspondientes síndromes. Todos los vectores posibles se dan en la tabla. 12.

2) Calcular el síndrome de la palabra aceptada. b según la fórmula (3.16) Con=bHT:

c 1 =(00110)(10100)=1, c 2 =(00110)(11010)=1,

con 3 =(00110)(01001)=0,

aquellos. vector Con= 110. El síndrome no es cero, por lo tanto hay un error.

Vector Con= 110 en la tabla. 12 corresponde al vector de error en el primer carácter. mi=10000. Decodificamos sumando el vector recibido con el vector de error.

Entonces obtuvimos el mismo resultado: el vector fue transmitido un 2=10110, correspondiente a la secuencia de información incógnita=10.

Ejemplo 20. Para el código dado en el ejemplo 19, cree un diagrama del dispositivo de codificación.

Solución. Denotemos por letras A 1 ,...,A 5 caracteres a la salida del codificador, y A 1 y A 2 hay símbolos de información que llegan a su entrada y símbolos A 3 , A 4 y A 5 se generan en el codificador.

De la relación (3.22) obtenemos

Una de las variantes del circuito codificador determinada por estas relaciones se muestra en la Fig. 5.

El codificador funciona de la siguiente manera. Durante los dos primeros pasos, el registro de desplazamiento de dos bits se llena con caracteres de información. A 1 y A 2, y dentro durante los próximos tres ciclos su estado permanece sin cambios. Simultáneamente con el llenado del registro, comienza la conmutación del multiplexor (conmutador) MUX. De esta manera, se forman 5 símbolos de palabras en clave que satisfacen las relaciones requeridas.

Ejemplo 21. Construya un código Hamming con los siguientes parámetros: código d=3, r=3.

Solución. Comenzamos a construir el código con una matriz de verificación. Como siete columnas de la matriz de control de paridad norte Seleccionamos todos los números binarios de 3 bits posibles, excluyendo el número cero. La matriz de cheques tiene la forma

Para determinar las ubicaciones de los símbolos de prueba e información, la matriz norte presente en forma canónica

Dónde I– matriz de identidad.

Para ello es suficiente en la matriz norte seleccione columnas que contengan una unidad cada una y muévalas hacia el lado derecho. Entonces obtenemos

De la fórmula (4.3.5) obtenemos las siguientes relaciones para los símbolos a 1 , ..., A 7 palabras clave:

Usando estas relaciones, componemos una tabla de códigos.

Ejemplo 22. Para un código Hamming definido por una matriz de paridad h, construido en el ejemplo 21, decodifica el vector recibido 1011001.

Solución. Para el vector recibido b=1011001 usando la fórmula (3.16) calculamos el síndrome

Síndrome Con≠0, es decir hay un error. En el caso de un único error (y sólo uno), el valor calculado del síndrome siempre coincide con una de las columnas de la matriz. norte y el número de columna indica el número del símbolo dañado. Vemos que el error ocurrió en el primer carácter y se transmitió el vector.

Ejemplo 23. La codificación se realiza mediante un código de bloques lineal (15,15- r). Encuentre el número mínimo de caracteres de prueba r, en el que el código podría corregir cualquier error simple, doble o triple.

Por tanto, para corregir todos los errores mencionados, es necesario que las combinaciones transmitidas contengan al menos 10 caracteres de verificación, es decir k=5.

Ejemplo 24. Para la codificación, se utiliza un código BCH (15,5) con una distancia de código código d=7, capaz de corregir todos los errores hasta tres veces inclusive.

Probabilidad de error de bit en un canal de transmisión pag=10 -4, los errores son independientes. Determine la probabilidad de error al decodificar una combinación de códigos y la probabilidad de error de bits en la salida del decodificador.

Solución. La probabilidad de error al decodificar una combinación de códigos está determinada por la fórmula (3.59)

Determinamos la probabilidad de error de bit en la salida del decodificador usando la fórmula (3.60) es decir, se produce un error en promedio por bit.

Información es un conjunto de información que está sujeta a almacenamiento, transmisión, procesamiento y uso en la actividad humana.

Cambiar las características del medio que se utiliza para representar la información se llama señal , y el valor de esta característica, relacionado con una determinada escala de medición, se llama parámetro de señal .

Distinguir dos tipos de señales (y por lo tanto dos tipos de mensajes ): continuo y discreto.

Para garantizar la simplicidad y confiabilidad del reconocimiento de señales discretas ( signos ), es aconsejable reducir su número al mínimo. Como regla general, recurren a la operación de representar los caracteres originales en otro alfabeto con un número menor de caracteres, llamado simbolos . Al denotar esta operación, se utiliza el mismo término: " codificación ».

Información propia

La cantidad de información que contiene una carta. incógnita i alfabeto, llamémoslo propia información contenido en incógnita i y denotar
.

.

la fórmula de shannon

Promedimos nuestra propia información, es decir Calculemos la cantidad promedio de información que contiene un carácter del alfabeto.
:
.

Cantidad promedio de información, pendiente por una letra, llamado entropía alfabeto (o fuente) y es designado h:

- la fórmula de shannon .

Es obvio que promedio 1 cantidad de información en la longitud del mensaje norte calculado por la fórmula:

.

Comentario.La cantidad de información se atribuye al propio mensaje.

Comentario. La entropía es una característica de la fuente del mensaje. (alfabeto).

la fórmula de hartley

En equiprobabilidad caracteres del alfabeto
, de la fórmula de Shannon obtenemos: .

- la fórmula de hartley .

Unidades de información

La unidad de información por elemento del mensaje (unidad de entropía) se llama poco .

Considere un alfabeto de símbolos igualmente probables cuya entropía es igual a 1:
. Ya que de aquí se sigue
, entonces está claro que 1 bit es la cantidad de información que está contenida en un mensaje binario (alfabeto (0,1)) de longitud 1.

En lo que sigue, en las expresiones para I y H siempre usaremos logaritmos con base 2.

Propiedades de la entropía

1. Entropía norte- magnitud

- no negativo(norte  0) ,

- limitado, Estas propiedades se derivan del hecho de que todos sus componentes tienen las mismas cualidades.
.

2. entropía igual a cero si la probabilidad de uno de los símbolos es 1. En este caso, se habla de una fuente completamente determinista y de la ausencia de incertidumbre en ella, ya que el observador conoce el mensaje de la fuente antes del momento de su observación.

3. También se puede demostrar que la entropía es máximo si todos los caracteres del alfabeto son igualmente probables, es decir. norte máx = registro metro. Por tanto, para encontrar el valor de entropía máximo posible (para un número fijo de símbolos), se utiliza la fórmula de Hartley.

4. De particular interés son mensajes binarios, usando alfabeto binario(0,1). Desde cuando metro= 2 probabilidades de caracteres alfabéticos pag 1  1 y pag 2  1, entonces podemos poner pag 1 = pag Y pag 2 = 1-pag. Entonces la entropía está determinada por la relación

En los ejemplos de codificación anteriores, todas las palabras clave tenían la misma longitud. Sin embargo, este no es un requisito obligatorio. Además, si las probabilidades de aparición de mensajes difieren notablemente entre sí, entonces es mejor codificar los mensajes con una alta probabilidad de aparición con palabras cortas y codificar los mensajes raros con palabras más largas. Como resultado, el texto del código se acortará en promedio bajo ciertas condiciones.

Un indicador de la economía o eficiencia de un código no uniforme no es la longitud de las palabras de código individuales, sino su longitud "promedio", determinada por la igualdad:

donde es la palabra clave con la que está codificado el mensaje, a es su longitud, es la probabilidad del mensaje y es el número total de mensajes fuente. Para mayor brevedad al escribir fórmulas, se pueden utilizar las siguientes notaciones: Y . Tenga en cuenta que la designación de la longitud promedio de codificación enfatiza el hecho de que este valor depende tanto de fuente del mensaje y sobre el método de codificación.

El código más económico es el que tiene la longitud media más pequeña. Comparemos, usando ejemplos, la rentabilidad de diferentes métodos de codificar la misma fuente.

Deje que la fuente contenga 4 mensajes con probabilidades. Estos mensajes se pueden codificar con palabras clave de dos caracteres de longitud constante en el alfabeto. de acuerdo con la tabla de códigos.

	00
	01
A_3	10
A_4	11

Evidentemente, para representar (transmitir) cualquier secuencia, se necesitarán, en promedio, 2 caracteres por mensaje. Comparemos la efectividad de dicha codificación con la codificación descrita anteriormente con palabras de longitud variable. La tabla de códigos para este caso puede verse así:

	0
	1
	10
	11

En esta tabla, a diferencia de la anterior, los mensajes más frecuentes están codificados con un carácter binario. Para la última opción de codificación tenemos

mientras que para un código uniforme la longitud promedio (es la misma que la longitud total de las palabras en código). Del ejemplo considerado se desprende claramente que codificar mensajes con palabras de diferente longitud puede dar un aumento significativo (casi el doble) en la eficiencia de la codificación.

Cuando se utilizan códigos desiguales, surge un problema que explicaremos utilizando el ejemplo de la última tabla de códigos. Usemos esta tabla para codificar una secuencia de mensajes. , como resultado de lo cual se convierte en el siguiente texto binario: 010110. El primer carácter del mensaje original se decodifica de forma única: esto es . Sin embargo, comienza una mayor incertidumbre: o . Estas son sólo algunas de las posibles opciones para decodificar la secuencia original de caracteres.

Cabe señalar que la ambigüedad en la decodificación de palabras apareció a pesar de que se cumple la condición de decodificación inequívoca de signos (inyectividad del mapeo del código).

La esencia del problema es la imposibilidad de identificar sin ambigüedades las palabras clave. Para solucionarlo sería necesario separar una palabra clave de otra. Por supuesto, esto se puede hacer, pero sólo utilizando una pausa entre palabras o un signo de separación especial, que requiere una designación de código especial. Ambos métodos, en primer lugar, contradicen el método de codificación de palabras descrito anteriormente mediante la concatenación de códigos de caracteres que forman una palabra y, en segundo lugar, conducirán a un alargamiento significativo del texto del código, anulando las ventajas de utilizar códigos de longitud variable.

La solución a este problema es poder seleccionar palabras de código individuales en cualquier texto de código sin utilizar delimitadores especiales. En otras palabras, es necesario que el código cumpla el siguiente requisito: cualquier secuencia de caracteres de código se puede dividir de forma única en palabras de código. Los códigos para los cuales se cumple el último requisito se denominan únicamente decodificables (a veces llamados códigos sin comas).

Veamos el código (esquema de codificación alfabética) , especificado por la tabla de códigos

y varias palabras compuestas por códigos elementales.

Definición. Se dice que un código es únicamente decodificable si

es decir, cualquier palabra compuesta de códigos elementales se descompone de forma única en códigos elementales.

Si la tabla de códigos contiene las mismas palabras de código, es decir, si

entonces, obviamente, el código no es decodificable de forma única (el circuito no es separable). Estos códigos no se consideran más.

Códigos de prefijo

Los códigos más simples y más utilizados sin un separador especial de palabras clave son los llamados códigos de prefijo.

Definición . Un código que tiene la propiedad de que ninguna palabra de código es el comienzo (prefijo) de otra palabra de código se llama prefijo.

Teorema 1. El código de prefijo es decodificable de forma única.

Prueba . Supongamos lo contrario. Luego hay una palabra que se puede representar de dos maneras diferentes, y hasta el número, todas las subpalabras en ambas representaciones (descomposiciones) coinciden y las palabras son diferentes. Al descartar los mismos prefijos de dos palabras iguales (representaciones), obtenemos terminaciones coincidentes que comienzan con palabras diferentes. Como las terminaciones son iguales, las primeras letras de las palabras deben coincidir. Por la misma razón, las segundas letras de estas palabras deben coincidir, etc. Esto significa que la desigualdad de las palabras sólo puede consistir en que tienen diferentes longitudes y, por tanto, una de ellas es prefijo de la otra. Esto contradice el prefijo del código.