Condición de fano invertida. Resolución de problemas sobre el tema "codificar y decodificar información".
Para utilizar vistas previas de presentaciones, cree una cuenta de Google e inicie sesión en ella: https://accounts.google.com
Títulos de diapositivas:
Decodificación inequívoca Condición directa e inversa Fano Profesor de informática y TIC MBOU escuela secundaria n.º 7 Okha, región de Sakhalin Sergienko Tatyana Gennadievna
Tarea 1 Seleccione el siguiente código para codificar la frase “Buenos días”: GOODBREUT Espacio 111 000 00 1 01 0 10 11
Los códigos de letras se "concatenan" en una cadena de un solo bit y se transmiten, por ejemplo, a través de la red: Buenos días → 11100000100001110101000 En el destino surge un problema: cómo restaurar el mensaje original y si es posible.
11100000100001110101000 Este mensaje se puede descodificar de diferentes formas. Supongamos también que consta únicamente de las letras P – 1 y U – 0. Entonces obtenemos RRRUUUUURUUURRRURRUUUU, es decir un conjunto de letras sin sentido.
Un código se denomina descodificable de forma única si cualquier mensaje de código puede descifrarse de forma única (sin ambigüedades).
Esto significa que el código no es descodificable de forma única.
Tarea 2 Códigos uniformes. Para la misma frase utilizamos el código uniforme: D O R E U T Espacio 111 000 001 101 011 010 100 110
Los códigos uniformes son antieconómicos y mucho más largos que los no uniformes. Esto conduce a una codificación más complicada, pero al mismo tiempo se descodifican de forma inequívoca, lo que naturalmente facilita la tarea.
Tarea 3 Para reducir la longitud del mensaje, puede intentar utilizar un código desigual, es decir un código en el que las palabras de código correspondientes a diferentes caracteres del alfabeto original pueden tener diferentes longitudes, de uno a varios caracteres.
Usamos el siguiente código: 01Esta cadena de bits se decodifica de forma única. D O B R E U T Espacio 01 00 1011 100 1010 1101 1110 1111
La primera letra es D (código 01), porque ninguna otra palabra de código comienza con 01. La segunda letra es O (código 00). Ninguna otra palabra comienza con 00. Esta misma propiedad, llamada condición de Fano, se aplica a palabras clave de otras letras.
CONDICIÓN FANO Ninguna palabra clave coincide con el comienzo de otra palabra clave. Estos códigos se denominan prefijo (se decodifican desde el principio del mensaje) y se decodifican de forma única.
Tarea 4 Consideremos otro código: No es prefijo, porque el código de la letra D (10) coincide con el inicio del código de la letra B (1011), U (1000) y el código de la letra O (00) coincide con el inicio del código de la letra P ( 001). D O R E U T Espacio 10 00 1011 001 0101 1000 0111 1111
Codifiquemos nuestro mensaje: BUENOS DÍAS → 10 00 1011 001 00 0101 1111 1000 0111 001 00 Comencemos a decodificar desde el principio. La primera es D o U, y luego generalmente hay diferentes opciones: P o B... Es decir. hay que “mirar” hacia adelante, lo cual es muy inconveniente.
Intentemos decodificar el mensaje desde el final: ¡definitivamente está decodificado! Se cumple la condición de Fano inversa: ninguna palabra clave coincide con la terminación de otra palabra clave.
Los códigos para los que se cumple la condición de Fano inversa se denominan sufijos.
Concluyamos: El mensaje se decodifica de forma única si se cumple la condición de Fano directa o inversa para el código utilizado.
La condición de Fano es una condición suficiente, pero no necesaria, para una descodificabilidad inequívoca. Esto significa que: - para una descodificabilidad inequívoca, es suficiente cumplir al menos una de dos condiciones: directa o inversa. - puede haber códigos para los que no se cumple ni la condición de Fano directa ni la inversa, pero que, sin embargo, proporcionan una decodificación inequívoca, porque de lo contrario se pierde el significado de la expresión.
Tarea 5 Para codificar una determinada secuencia que consta de las letras A, B, C, D y D, se utiliza un código binario no uniforme, lo que permite decodificar sin ambigüedades la secuencia binaria resultante. Aquí está el código: A – 00, B – 01, C – 100, D – 101, D – 110.
¿Es posible acortar la longitud de la palabra clave de una de las letras para que el código aún pueda decodificarse sin ambigüedades? Los códigos de las letras restantes no deberían cambiar. Elija la respuesta correcta: 1) para la letra D -11 2) esto es imposible 3) para la letra G - 10 4) para la letra D -10
SOLUCIÓN: El código fuente tiene prefijo. Para ello, se cumple la condición de Fano: ninguno de los códigos de tres bits comienza con 00 (A) o 01 (B). (En este caso, no se cumple la condición de Fano inversa: el código A (00) coincide con la terminación B (100) y el código B (01) coincide con la terminación D (101).)
Ahora revisemos las respuestas. Reduzcamos D a 11. Si el código resultante viola la condición directa de Fano, entonces se violará la propiedad de decodificación inequívoca. Pero esto no sucedió, no hay otros códigos que comiencen con 11. Esta es la decisión correcta. Revisemos las otras opciones.
No consideramos inmediatamente la opción 2: hemos encontrado la respuesta. La opción 3 viola la condición directa de Fano: el código de la letra B (101) comienza con 10. La opción 4 también viola la condición directa de Fano. Aquellos. La respuesta es clara, no hay otras opciones.
¡Gracias por su atención!
Consideremos otra tabla de códigos: A B C D D 000 01 10 011 100 Aquí no se cumple la condición de Fano, ya que el código de la letra B (01) es el comienzo del código de la letra G (011), y el código de la letra D (100) comienza con el código de la letra B (10). Sin embargo, se puede observar que se cumple la condición de Fano “inversa”: ningún código es el final de otro código (dicho código se llama sufijo). Por lo tanto, el mensaje codificado se puede decodificar sin ambigüedades desde el final. Por ejemplo, considere la cadena 011000110110. La última letra de este mensaje solo puede ser B (código 10): B 0110001101 10 La segunda letra desde el final es B (código 01): B B 01100011 01 10 y así sucesivamente: B D G B B 01 100 011 01 10.
Diapositiva 26 de la presentación "Métodos de codificación de información".Descargar presentación
Métodos de codificaciónresumen de otras presentaciones
"Codificación binaria" - Números. Codificación binaria de información textual. Tabla de codificación. Volumen de información del texto. Codificación binaria en una computadora. Codificación de información textual. Tabla de códigos ampliada. Símbolo. Código binario único. Letra del alfabeto latino. Usando el sistema binario. Computadoras.
“Codificación de información en código binario” - Definición. Sistemas numéricos. Sistema de numeración binario. Codificación. Codificación de información. Dé ejemplos de codificación. Sistema de números decimales. El significado del número. El significado de un número depende de su posición. Alfabeto. Idiomas. Sistema romano no posicional. Codificación binaria. ¿Qué está cifrado aquí?
“Métodos de codificación de información”: en la memoria de la computadora, la información se presenta en código binario. Codificación y decodificación. Puedes codificar información. Métodos de codificación de información. Creemos una tabla de códigos simple. Para descubrir la palabra cifrada, tome solo las primeras sílabas. Lo que Lom leyó en las banderas de la goleta que se aproxima. Crea tu propia forma de codificar las letras del alfabeto ruso. Asignaciones. Información cifrada. A Louis Braille se le ocurrió una forma especial de presentar la información.
“Métodos de codificación de información” - Codificación binaria en una computadora. Cantidad de información. Telégrafo óptico Shapp. Estado de Fano. Qué código usar. Mensaje recibido. "Sí o no". El primer telégrafo. Métodos de codificación de información. Grabación de información. ¿Por qué la codificación binaria? Banderas de señales. Codificación. Codificación y decodificación. Codificación de información. Seleccionar el método de codificación. Tipos de información. ¿Cuantas opciones?
Tarea número 5Al realizar esta tarea, necesita conocer la condición de Fano,código huffman
¿Cuál es el significado de la condición directa de Fano?
condición de ventilador lleva el nombre de su creador, el científico italoamericano Robert Fano. La condición es necesaria en la teoría de la codificación cuando se construye un código autoterminado. Dada la diferente terminología, dicho código se denomina código de prefijo.
Esta condición se puede formular de la siguiente manera: “ninguna palabra clave puede actuar como el comienzo de cualquier otra palabra clave ».
Desde un punto de vista matemático, la condición se puede formular de la siguiente manera: “Si el código contiene la palabra B, entonces para cualquier línea C que no esté vacía, la palabra BC no existe en el código. ».
¿Cuál es el significado de la condición de Fano inversa?
Existe también una regla de Fano inversa, cuya formulación es la siguiente: “ninguna palabra clave puede actuar como final de cualquier otra palabra clave ».
Desde un punto de vista matemático, la condición inversa se puede formular de la siguiente manera: “si el código contiene la palabra B, entonces para cualquier cadena C no vacía la palabra CB no existe en el código ».
Condición del problema: dada una secuencia que consta de las letras “A”, “B”, “C”, “D” y “E”. Para codificar la secuencia dada se utiliza un código binario no uniforme, con el que es posible realizar una decodificación inequívoca.
Carta
equivalente binario
010
011
101
111
Pregunta : ¿Es posible que uno de los símbolos acorte la longitud de la palabra clave de tal manera que se preserve la posibilidad de una decodificación inequívoca? En este caso, los códigos de los símbolos restantes no deberían modificarse.
Número de opción
Respuesta
B-01
No es posible
C-01
D–01
Solución : para preservar la posibilidad de decodificación, es suficiente cumplir con directo o inversoCondiciones de fano . Realicemos una comprobación secuencial de las opciones 1, 3 y 4. Si ninguna de las opciones es adecuada, la respuesta correcta será la opción 2 (no posible).
Opción 1. Código: A - 00, B - 01, C - 011, D - 101 y E - 111. Directocondición de ventilador no ejecutado: el código del carácter “B” coincide con el inicio del código del carácter “C”. La regla de Fano inversa no se cumple: el código del carácter "B" coincide con el final del código del carácter "D". La opción no es adecuada.
Opción 3. Código: A - 00, B - 010, C - 01, D - 101 y E - 111. Directocondición de ventilador no ejecutado: el código del carácter “C” coincide con el inicio del código del carácter “B”. La condición inversa tampoco se cumple: el código del carácter “C” coincide con el final del código del carácter “D”. La opción no es adecuada.
Opción 4. Código: A - 00, B - 010, C - 011, D - 01 y E - 111. Directocondición de ventilador no ejecutado: el código del carácter “D” coincide con el inicio del código de los caracteres “B” y “C”. Sin embargo, se observa la regla de Fano inversa: el código del símbolo “D” no coincide con el final del código de todos los demás símbolos. Por este motivo, la opción es adecuada.
Después de verificar las opciones para resolver el problema para el cumplimiento de las normas directas e inversas.condición de ventilador , se encontró que la opción 4 es correcta.
Respuesta : 4
código huffman
La idea detrás de la codificación Huffman se basa en la frecuencia de aparición de un carácter en una secuencia. El símbolo que aparece con mayor frecuencia en la secuencia recibe un nuevo código muy pequeño, y el símbolo que aparece con menor frecuencia recibe, por el contrario, un código muy largo. Esto se debe a que queremos asegurarnos de que cuando hayamos procesado toda la entrada, los caracteres más comunes ocuparán la menor cantidad de espacio (y menos que en el original), y los más raros ocuparán la mayor cantidad de espacio. (pero como son raros, no importa).
№ 1. Para codificar las letras O, B, D, P, A, decidimos utilizar la representación binaria de los números 0, 1, 2, 3 y 4, respectivamente (con la preservación de un cero insignificante en el caso de un solo representación de dígitos). Si codifica la secuencia de letras CASCADA de esta manera y escribe el resultado en código octal, obtendrá
1) 22162
2) 1020342
3) 2131453
4) 34017
Explicación.
Primero necesitas representar los datos en la condición numérica en código binario:
100
Luego codifique la secuencia de letras: CASCADA - 010010001110010. Ahora dividamos esta representación en tripletes de derecha a izquierda y conviertamos el conjunto de números resultante en código decimal, luego en código octal (la representación octal coincide con la representación decimal al dividir en tripletes )
010 010 001 110 010 - 22162.
№ 2. Para transmitir un mensaje a través de un canal de comunicación que consta únicamente de los caracteres A, B, C y D, se utiliza codificación carácter por carácter: A-00, B-11, B-010, D-011. El mensaje se transmite a través del canal de comunicación: VBGAGV. Codifique el mensaje con este código. Convierta el número binario resultante a forma hexadecimal.
1) CDBDAC
2) 511110
3) 5B1A
4) A1B5
Explicación.
Codifiquemos la secuencia de letras: VBGAGV - 0101101100011010. Ahora dividamos esta representación en cuatro de derecha a izquierda y conviertamos el conjunto de números resultante primero en código decimal y luego en hexadecimal:
0101 1011 0001 1010 - 5 11 1 10 - 5В1А.
La respuesta correcta se indica en el número 3.
№ 3. Para codificar un mensaje que consta únicamente de las letras A, B, C y D, se utiliza un código binario de longitud desigual:
010
011
Si codifica la secuencia de caracteres VGAGBV de esta manera y escribe el resultado, obtendrá:
1) CDADBC
2) A7C4
3) 412710
4) 4S7A
Explicación.
Codifiquemos la secuencia de letras: VGAGBV - 0100110001111010. Ahora dividamos esta representación en cuatro de derecha a izquierda y conviertamos el conjunto de números resultante primero en código decimal y luego en hexadecimal:
0100 1100 0111 1010 - 4 12 7 10 - 4С7А.
La respuesta correcta se encuentra en el número 4.
№ 4. Una imagen de mapa de bits en blanco y negro se codifica línea por línea, comenzando en la esquina superior izquierda y terminando en la esquina inferior derecha. Al codificar, 1 representa negro y 0 representa blanco.
Para que sea más compacto, el resultado se escribió en el sistema numérico octal. Seleccione la entrada de código correcta.
1) 57414
2) 53414
3) 53412
4) 53012
Explicación.
Código de primera línea: 10101.
Código de segunda línea: 11000.
Código de tercera línea: 01010.
Escribamos los códigos en orden en una línea: 101011100001010. Ahora dividamos esta representación en tripletes de derecha a izquierda y conviertamos el conjunto de números resultante en código decimal (la representación octal coincide con la representación decimal al dividir en tripletes).
101 011 100 001 010 - 53412.
№ 5. Para 5 letras del alfabeto latino, se especifican sus códigos binarios (para algunas letras, de dos bits, para otras, de tres). Estos códigos se presentan en la tabla:
000
110
001
Determine qué conjunto de letras está codificado por la cadena binaria 1100000100110
1)baada
2) malo
3)baco
4) bacdb
Explicación.
Vemos que se cumple la condición de Fano: ninguna palabra código es el comienzo de otra palabra código, por lo que definitivamente podemos decodificar el mensaje desde el principio.
Dividamos el código de izquierda a derecha según los datos de la tabla y tradujémoslo a letras:
110 000 01 001 10 - b a c d e.
La respuesta correcta se encuentra en el número 3.
№ 6. Para transmitir números a través de un canal ruidoso, se utiliza un código de verificación de paridad. Cada uno de sus dígitos se escribe en representación binaria, con ceros a la izquierda sumados hasta una longitud de 4, y la suma de sus elementos módulo 2 se suma a la secuencia resultante (por ejemplo, si transmitimos 23, obtenemos la secuencia 0010100110). ¿Determine qué número se transmitió a través del canal en el formulario 01100010100100100110?
1) 6543
2) 62926
3) 62612
4) 3456
Explicación.
El ejemplo muestra que 2 caracteres están codificados con 10 dígitos binarios (bits), se asignan 5 bits para cada dígito. La condición dice que cada dígito está escrito en un código de 4 caracteres, lo que significa que se puede omitir el quinto dígito.
Dividamos la notación binaria en grupos de 5 caracteres: 01100 01010 01001 00110. Descartamos el último dígito de cada 5 y lo convertimos a notación decimal:
0110 0101 0100 0011 - 6 5 4 3.
La respuesta correcta se encuentra en el número 1.
№ 7. Los mensajes que contienen solo 4 letras se transmiten a través del canal de comunicación: P, O, R, T. Para codificar letras, se utilizan palabras de código de 5 bits:
P-11111, O-11000, P-00100, T-00011.
Este conjunto de palabras clave tiene la siguiente propiedad:dos palabras cualesquiera de un conjunto difieren en al menos tres posiciones.
Esta propiedad es importante para descifrar mensajes en presencia de interferencias (suponiendo que los bits transmitidos puedan distorsionarse, pero no perderse). Se considera que un mensaje codificado se recibe correctamente si su longitud es múltiplo de 5 y cada quintil difiere de alguna palabra clave en no más de una posición; en este caso, se cree que el cinco codifica la letra correspondiente. Por ejemplo, si se recibe el cinco 00000, entonces se considera que se transmitió la letra P.
Entre los mensajes a continuación, busque el que se recibió correctamente e indique su decodificación (los espacios no son importantes).
11011 11100 00011 11000 01110
00111 11100 11110 11000 00000
1) INUNDACIÓN
2) ROTORES
3) HACHA
4) ninguno de los mensajes se recibió correctamente
Explicación.
La longitud de ambos mensajes es múltiplo de cinco.
Analizando el primer mensaje “11011 11100 00011 11000 01110”, llegamos a la conclusión de que fue recibido incorrectamente, ya que no existe ninguna palabra que difiera de la palabra “01110” en una sola posición.
Veamos el segundo mensaje. Teniendo en cuenta que cada cinco se diferencia de una determinada palabra clave en no más de una posición, sólo se puede descifrar como "AX".
№ 8. Se utiliza un código de 5 bits para transmitir datos a través de un canal de comunicación. El mensaje contiene únicamente las letras A, B y C, que están codificadas con las siguientes palabras clave:
A - 10010, B - 11111, C - 00101.
Puede haber interferencias durante la transmisión. Sin embargo, puedes intentar corregir algunos errores. Dos de estas tres palabras clave se diferencian entre sí en al menos tres posiciones. Por lo tanto, si se produjo un error como máximo en una posición al transmitir una palabra, entonces se puede hacer una suposición fundamentada sobre qué letra se transmitió. (Dicen que “el código corrige un error”). Por ejemplo, si se recibe la palabra de código 00100, se considera que se transmitió la letra B (La diferencia con la palabra de código para B está solo en una posición; para. otras palabras de código hay más diferencias.) Si la palabra de código recibida Si la palabra difiere de las palabras de código para las letras A, B, C en más de una posición, entonces se considera que ha ocurrido un error (se indica con "incógnita").
Mensaje recibido 10000 10101 11001 10111. Decodifica este mensaje: selecciona la opción correcta.
1) ABBB
2) xxxx
3) ABxB
4) AhhB
Explicación.
Decodificamos cada palabra del mensaje. La primera palabra: 10000 se diferencia de la letra A sólo en una posición. La segunda palabra: 10101 se diferencia de la letra B sólo en una posición. Tercera palabra: 11001 se diferencia de cualquier letra en más de una posición. La cuarta palabra: 10111 se diferencia de la letra B sólo en una posición.
Respuesta: ABxB.
№ 9. Para codificar una secuencia determinada que consta de las letras A, B, C, D y D, decidimos utilizar un código binario no uniforme, que nos permite decodificar sin ambigüedades la secuencia binaria que aparece en el lado receptor del canal de comunicación. Para las letras A, B, C y D, se utilizaron las siguientes palabras clave: A - 111, B - 110, C - 101, D - 100.
Indique qué palabra de código de las que se enumeran a continuación se puede utilizar para codificar la letra D. El código debe satisfacer la propiedad de decodificación inequívoca. Si se puede utilizar más de una palabra clave, introduzca la más corta.
1) 1
2) 0
3) 01
4) 10
Explicación.
Para que un mensaje escrito utilizando un código de longitud desigual pueda decodificarse sin ambigüedades, se requiere que ningún código sea el comienzo de otro código (más largo). Veamos las opciones para la letra D, comenzando por la más corta.
1) D=1: el código de letras D es el comienzo de todos los códigos de letras presentados, por lo que esta opción no es adecuada.
2) D=0: el código de la letra D no es el comienzo de otro código, por lo que esta opción es adecuada.
3) D=01: el código de la letra D no es el comienzo de otro código, por lo que esta opción es adecuada.
4) D=10: el código de la letra D es el comienzo de los códigos de las letras B y G, por lo tanto, esta opción no es adecuada.
Por tanto, son adecuadas dos opciones: 0 y 01. 0 es más corto que 01.
№ 10. Los mensajes que contienen solo 4 letras se transmiten a través del canal de comunicación:
E, N, O, T.
En cualquier mensaje, la mayoría de las letras son O, la siguiente letra más común es la E y luego la N. La letra T es menos común que cualquier otra.
Para transmitir mensajes, es necesario utilizar un código binario no uniforme que permita una decodificación inequívoca; Los mensajes deben ser lo más breves posible. El criptógrafo puede utilizar uno de los códigos que se enumeran a continuación. ¿Qué código debería elegir?
1) E-0, N-1, O-00, T-11
2) O-1, N-0, E-01, T-10
3) E-1, N-01, O-001, T-000
4) O-0, N-11, E-101, T-100
Explicación.
Elijamos códigos para los que se cumpla la condición de Fano. Estos son los códigos 3 y 4.
Para que el mensaje sea lo más breve posible, es necesario que cuanto más a menudo aparezca una letra, más corto sea su código.
Por tanto, la respuesta es 4, ya que la letra O es la letra más común y la opción 4 utiliza un carácter para codificarla.
№ 11. Para codificar una determinada secuencia que consta de las letras K, L, M, N, decidimos utilizar un código binario no uniforme que satisfaga la condición de Fano. Para la letra H, se usó la palabra de código 0, para la letra K, se usó la palabra de código 110. ¿Cuál es la longitud total más corta posible de las cuatro palabras de código?
1) 7
2) 8
3) 9
4) 10
Nota. La condición de Fano significa que ninguna palabra clave es el comienzo de otra palabra clave. Esto hace posible descifrar mensajes cifrados sin ambigüedades.
Explicación.
Encontremos para los dos símbolos restantes la representación más corta que satisfaga la condición de Fano. La palabra clave 1 no se puede utilizar, ya que violaría la condición de Fano. De las palabras de código de dos dígitos, se puede utilizar la palabra 10, pero no las palabras 11 y 01. Con esta construcción de códigos, es imposible seleccionar una palabra de código de dos dígitos para el cuarto símbolo. Por lo tanto, utilizamos una palabra de tres dígitos, concretamente 111.
Por lo tanto, la longitud total más corta posible de las cuatro palabras en código será 1 + 3 + 2 + 3 = 9.
La respuesta correcta se encuentra en el número 3.
№12. Los mensajes se transmiten a través del canal de comunicación, cada uno de los cuales contiene 16 letras A, 8 letras B, 4 letras C y 4 letras G (no hay otras letras en los mensajes). Cada letra está codificada como una secuencia binaria. A la hora de elegir el código se tuvieron en cuenta dos requisitos:
a) ninguna palabra de código es el comienzo de otra (esto es necesario para que el código permita una decodificación inequívoca);
b) la longitud total del mensaje codificado debe ser lo más corta posible.
¿Qué código de los siguientes debería elegir para codificar las letras A, B, C y D?
1) A:0, B:10, C:110, D:111
2) A:0, B:10, C:01, D:11
3) A:1, B:01, C:011, D:001
4) A:00, B:01, C:10, D:11
Explicación.
2 y 3 no son adecuados porque contienen pares de códigos, uno de los cuales es el comienzo del otro.
La longitud de los mensajes al usar el primer código será igual a .
La longitud de los mensajes al utilizar el cuarto código será igual a .
El uso del primer código da como resultado mensajes más cortos, por lo que se debe utilizar este.
¡Hola! Mi nombre es Alexander Georgievich y soy un tutor profesional en informática y programación en Moscú. ¿Se ha encontrado con un problema relacionado con la codificación y está confundido acerca del algoritmo para resolverlo? Necesitas reunirte urgentementecondición de ventilador, y también apuntarte a clases privadas conmigo. En mis lecciones me centro en la resolución de ejercicios temáticos simples y complejos.
¿Cuál es el significado de la condición directa de Fano?
condición de ventilador lleva el nombre de su creador, el científico italoamericano Robert Fano. La condición es necesaria en la teoría de la codificación cuando se construye un código autoterminado. Dada la diferente terminología, dicho código se denomina código de prefijo.
Esta condición se puede formular de la siguiente manera: “ ninguna palabra clave puede actuar como el comienzo de cualquier otra palabra clave».
Desde un punto de vista matemático, la condición se puede formular de la siguiente manera: “ si el código contiene la palabraB, entonces para cualquier cadena que no esté vacíaLa palabra C BC no existe en el código.».
¿Cuál es el significado de la condición de Fano inversa?
Existe también una regla de Fano inversa, cuya formulación es la siguiente: “ ninguna palabra clave puede actuar como final de cualquier otra palabra clave».
Desde un punto de vista matemático, la condición inversa se puede formular de la siguiente manera: “ si el código contiene la palabra B, entonces para cualquier cadena C no vacía la palabra CB no existe en el código».
Aplicación práctica de la condición de Fano
Veamos los números de teléfono en la telefonía tradicional. Si el número "102" ya existe, entonces el número "1029876" simplemente no se emitirá. Si se marcan los primeros tres dígitos, la centralita deja de reconocer y aceptar todos los demás dígitos y se conecta al suscriptor mediante el número 102. Sin embargo, esta regla no es válida para operadores de telefonía móvil. Esto se debe a que para marcar un número es necesario presionar la tecla correspondiente, que es básicamente la tecla con la imagen de un auricular de color verde. Por este motivo, los números “102”, “1020” y “1029876” pueden existir y asignarse a diferentes destinatarios.
Condición del problema: dada una secuencia que consta de las letras “A”, “B”, “C”, “D” y “E”. Para codificar la secuencia dada se utiliza un código binario no uniforme, con el que es posible realizar una decodificación inequívoca.
Pregunta: ¿Es posible que uno de los símbolos acorte la longitud de la palabra clave de tal manera que se preserve la posibilidad de una decodificación inequívoca? En este caso, los códigos de los símbolos restantes no deberían modificarse.
Solución: para preservar la posibilidad de decodificación, es suficiente cumplir con directo o inversoCondiciones de fano. Realicemos una comprobación secuencial de las opciones 1, 3 y 4. Si ninguna de las opciones es adecuada, la respuesta correcta será la opción 2 (no posible).
Opción 1. Código: A - 00, B - 01, C - 011, D - 101 y E - 111. Directo condición de ventilador no ejecutado: el código del carácter “B” coincide con el inicio del código del carácter “C”. La regla de Fano inversa no se cumple: el código del carácter "B" coincide con el final del código del carácter "D". La opción no es adecuada.
Opción 3. Código: A - 00, B - 010, C - 01, D - 101 y E - 111. Directo condición de ventilador no ejecutado: el código del carácter “C” coincide con el inicio del código del carácter “B”. La condición inversa tampoco se cumple: el código del carácter “C” coincide con el final del código del carácter “D”. La opción no es adecuada.
Opción 4. Código: A - 00, B - 010, C - 011, D - 01 y E - 111. Directo condición de ventilador no ejecutado: el código del carácter “D” coincide con el inicio del código de los caracteres “B” y “C”. Sin embargo, se observa la regla de Fano inversa: el código del símbolo “D” no coincide con el final del código de todos los demás símbolos. Por este motivo, la opción es adecuada.
Después de verificar las opciones para resolver el problema para el cumplimiento de las normas directas e inversas. condición de ventilador, se encontró que la opción 4 es correcta.
Respuesta: 4
Y ahora les sugiero que se familiaricen con la solución multimedia al problema que se propuso en la versión demo del Examen Estatal Unificado de Informática y TIC. Por cierto, este problema pertenece al tipo de problemas resueltos usando Condiciones de fano.
¿Aún tienes preguntas?
Si después de leer esta publicación todavía tienes algunas dudas, malentendidos o quieres consolidar el material que has cubierto con soluciones prácticas, llámame e inscríbete conmigo para recibir clases privadas de informática y TIC.
Versión de demostración del Examen Estatal Unificado 2019 – tarea n.° 5
Para codificar una determinada secuencia que consta de las letras A, B, C, D, D, E, decidimos utilizar un código binario no uniforme que satisfaga la condición de Fano. Para la letra A se utilizó la palabra clave 0; para la letra B – palabra de código 10. ¿Cuál es la suma más pequeña posible de las longitudes de las palabras de código para las letras B, D, D, E?
Nota. La condición de Fano significa que ninguna palabra clave es el comienzo de otra palabra clave. Esto hace posible descifrar mensajes cifrados sin ambigüedades.
Solución:
Respuesta:
Versión de demostración del Examen Estatal Unificado 2018 – tarea n.° 5
A través del canal de comunicación se transmiten mensajes cifrados que contienen solo diez letras: A, B, E, I, K, L, R, S, T, U. Para la transmisión se utiliza un código binario impar. Las palabras clave se utilizan para nueve letras.
Indique la palabra de código más corta para la letra B de modo que el código satisfaga la condición de Fano. Si hay varios códigos de este tipo, indique el código con el valor numérico más bajo. Nota. La condición de Fano significa que ninguna palabra clave es el comienzo de otra palabra clave. Esto hace posible descifrar mensajes cifrados sin ambigüedades.
Solución:
Respuesta: 1100
Para codificar una determinada secuencia que consta de las letras A, B, C, D, D, E, decidimos utilizar un código binario no uniforme que satisfaga la condición de Fano. Para la letra A se utilizó la palabra clave 0; para la letra B – palabra clave 10. ¿Cuál es la suma más pequeña posible de las longitudes de las seis palabras clave?
Nota. La condición de Fano significa que ninguna palabra clave es el comienzo de otra palabra clave. Esto hace posible descifrar mensajes cifrados sin ambigüedades.
Versión de demostración del Examen Estatal Unificado 2017 - Tarea No. 5
Solución:
Para encontrar palabras de código usaremos esta tabla.
Si los códigos de las letras restantes comienzan con 0, el código de la letra A=0 será el comienzo de sus códigos, por lo que esta opción no es adecuada. Si el código B = 10, los códigos de las letras B, D, D, E comienzan con 11. Para obtener 4 códigos diferentes, debe utilizar códigos de 4 caracteres (1111, 1110, 1101, 1100).
| 0 | 1 | ||||
| 1 | |||||
| 1 | 0 | ||||
| 1 | 0 | 1 | 0 | ||
A - 0 (1 carácter)
B - 10 (2 caracteres)
B - 1100 (4 caracteres)
G - 1101 (4 caracteres)
D - 1110 (4 caracteres)
E-1111 (4 caracteres)
1+2+4+4+4+4 = 19
Respuesta: 19
Versión de demostración del Examen Estatal Unificado 2016 – tarea número 5
A través del canal de comunicación se transmiten mensajes que contienen sólo cuatro letras: P, O, S, T; Para la transmisión se utiliza un código binario que permite una decodificación inequívoca. Para las letras T, O, P, se utilizan las siguientes palabras de código: T: 111, O: 0, P: 100.
Especifique la palabra de código más corta para la letra C, en la que el código permitirá una decodificación inequívoca. Si hay varios códigos de este tipo, indique el código con el valor numérico más bajo.
Solución:
Para encontrar palabras clave usaremos este esquema.
Si los códigos de las letras restantes comienzan con 0 , código de letras ACERCA DE=0 será el comienzo de sus códigos, por lo que esta opción no es adecuada. Desde el código de letras PAG=100 y el código de letras t =111 , entonces la carta CON No puede comenzar ni terminar con estos números.
Respuesta: 101
Para codificar un mensaje que consta únicamente de las letras A, B, C y D, se utiliza un código binario de longitud desigual:
Si codifica la secuencia de caracteres GAVBGV de esta manera y escribe el resultado en código hexadecimal, obtendrá:
1) DACBDC 1 6 2) AD26 16 3) 621310 16 4) 62DA 16
Solución:
GAVBGV = 0110001011011010
| 0110 | 0010 | 1101 | 1010 |
| 6 | 2 | D | A |
Respuesta: 4
Una imagen de mapa de bits en blanco y negro se codifica línea por línea, comenzando en la esquina superior izquierda y terminando en la esquina inferior derecha. Al codificar, 1 representa negro y 0 representa blanco.
Para que sea más compacto, el resultado se escribió en el sistema numérico octal. Seleccione la entrada de código correcta.
1) 57414 2) 53414 3) 53412 4) 53012
Solución:
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 101 | 011 | 100 | 001 | 010 |
| 5 | 3 | 4 | 1 | 2 |
Respuesta: 3
Para transmitir números a través de un canal ruidoso, se utiliza un código de verificación de paridad. Cada uno de sus dígitos se escribe en representación binaria, con ceros a la izquierda sumados hasta una longitud de 4, y la suma de sus elementos módulo 2 se suma a la secuencia resultante (por ejemplo, si transmitimos 23, obtenemos la secuencia 0010100110). ¿Determine qué número se transmitió a través del canal en el formulario 01100010100100100110?
1) 6543 2) 62926 3) 62612 4) 3456
Solución:
01100010100100100110
| 01100 | 01010 | 01001 | 00110 |
| 6 | 5 | 4 | 3 |
Respuesta: 1
Para codificar las letras O, L, A, Z, K, se utilizan códigos binarios de los números 0, 1, 2, 3 y 4, respectivamente (con la preservación de un cero insignificante en el caso de una representación de un solo dígito). Si codificas la secuencia de caracteres BARRIER de esta forma y escribes el resultado en código hexadecimal, obtendrás:
1) 4531253 2) 9876 3) E832 4) 238E
Solución:
| ACERCA DE | l | A | z | A |
| 0=00 | 1=01 | 2=10 | 3=11 | 4=100 |
BARRERA = 1110100000110010
| 1110 | 1000 | 0011 | 0010 |
| mi | 8 | 3 | 2 |
Respuesta: 3
Para transmitir un mensaje a través de un canal de comunicación que consta únicamente de las letras A, B, C, D, decidieron utilizar un código de longitud desigual: A=00, B=11, C=100. ¿Cómo se debe codificar la letra G para que la longitud del código sea mínima y el mensaje codificado pueda dividirse sin ambigüedades en letras?
1) 010 2) 0 3) 01 4) 011
Solución:
A=00, B=11, C=100, D=?
Respuesta: 3
Para codificar una secuencia determinada que consta de las letras A, B, C, D y D, decidimos utilizar un código binario no uniforme, que nos permite decodificar sin ambigüedades la secuencia binaria que aparece en el lado receptor del canal de comunicación. Para las letras A, B, C y D, se utilizaron las siguientes palabras clave: A - 111, B - 110, C - 101, D - 100.
Indique qué palabra clave de las que se enumeran a continuación se puede utilizar para codificar la letra D.
El código debe satisfacer la propiedad de decodificación inequívoca. Si se puede utilizar más de una palabra clave, introduzca la más corta.
1) 1 2) 0 3) 01 4) 10
Solución:
A-111, B-110, C-101, D-100, D-?
Respuesta: 2
A través del canal de comunicación se transmiten mensajes que contienen solo 4 letras: A, B, C, D. Para codificar las letras A, B, C, se utilizan palabras de código de 5 bits: A - 10110, B - 11000, C - 00101. Para este conjunto de códigos, las palabras tienen la siguiente propiedad: dos palabras cualesquiera del conjunto difieren en al menos tres posiciones. Esta propiedad es importante para descifrar mensajes en presencia de interferencias. ¿Cuál de las siguientes palabras en código se puede utilizar para la letra G de modo que la propiedad especificada se cumpla para las cuatro palabras en código?
1) 01110 2) 01011 3) 10001 4) ninguna de las palabras anteriores es adecuada
Solución:
1) 01 110: A - 10 110 - no difieren en al menos tres posiciones
2) 01011: A - 101 10, B - 1 1000, C - 0010 1 - difieren en al menos tres posiciones
Respuesta: 2
Se utiliza un código de 5 bits para transmitir datos a través de un canal de comunicación. El mensaje contiene únicamente las letras A, B y C, que están codificadas con las siguientes palabras clave:
A - 10001, B - 01101, C - 10110.
Puede haber interferencias durante la transmisión. Sin embargo, puedes intentar corregir algunos errores. Dos de estas tres palabras clave se diferencian entre sí en al menos tres posiciones. Por lo tanto, si se produjo un error como máximo en una posición al transmitir una palabra, entonces se puede hacer una suposición fundamentada sobre qué letra se transmitió. (Dicen que “el código corrige un error”). Por ejemplo, si se recibe la palabra de código 01111, se considera que se transmitió la letra B (La diferencia con la palabra de código para B está solo en una posición; para. otras palabras de código hay más diferencias). Si la palabra de código recibida difiere de las palabras de código para las letras A, B, C en más de una posición, se considera que ha ocurrido un error (se indica con ' incógnita').
Mensaje recibido 00110 11101 11000 11001. Decodifica este mensaje: selecciona la opción correcta.
1) VBxx 2) VBVA 3) xxxx 4) VBxA
Solución:
| 00110 | 11101 | 11000 | 11001 |
| B=1 0110 | B=0 1101 | incógnita | A=10 001 |
Respuesta: 4
Para codificar una determinada secuencia que consta de las letras A, B, C, D y D, se utiliza un código binario no uniforme, lo que permite decodificar sin ambigüedades la secuencia binaria resultante. Aquí está el código: A – 1; B-0100; B-000; G – 011; D – 0101. Es necesario reducir la longitud de la palabra clave de una de las letras para que el código aún pueda decodificarse sin ambigüedades. Los códigos de las letras restantes no deberían cambiar. ¿Cuál de los siguientes métodos se puede hacer esto?
1) para la letra G – 11 2) para la letra B – 00 3) para la letra G – 01 4) esto es imposible
Solución:
Respuesta: 2
Para codificar una secuencia determinada que consta de las letras A, B, C, D, decidieron utilizar un código binario no uniforme que satisfaga la condición de Fano. Para la letra A, se usó la palabra de código 1, para la letra B, se usó la palabra de código 011. ¿Cuál es la longitud total más corta posible de las cuatro palabras de código?
1) 7 2) 8 3) 9 4) 10
Solución:
A-1, B-011, B-00, G-010
Respuesta: 9
Los mensajes se transmiten a través del canal de comunicación, cada uno de los cuales contiene 15 letras A, 10 letras B, 6 letras C y 4 letras G (no hay otras letras en los mensajes). Cada letra está codificada como una secuencia binaria. A la hora de elegir el código se tuvieron en cuenta dos requisitos:
a) ninguna palabra de código es el comienzo de otra (esto es necesario para que el código permita una decodificación inequívoca);
b) la longitud total del mensaje codificado debe ser lo más corta posible.
¿Qué código de los siguientes debería elegir para codificar las letras A, B, C y D?
1) A:1, B:01, C:001, D:111
2) A:1, B:01, C:10, D:111
3) A:00, B:01, C:10, D:11
4) A:100, B:101, C:11, D:0
Solución:
Ninguna palabra clave es el comienzo de otra: A es el comienzo GRAMO en la 1ª y 2ª opción.
La longitud total del mensaje codificado debe ser lo más corta posible.
3) A:00 (15), B:01 (10), C:10 (6), D:11 (4)
2.15+2.10+2.6+2.4 = 70
4) A:100 (15), B:101 (10), C:11 (6), D:0 (4)
3.15+3.10+2.6_1.4 = 61
Respuesta: 3
Los mensajes que contienen solo 4 letras P, R, S, T se transmiten a través de un canal de comunicación utilizando un código binario uniforme. Cada letra tiene su propia palabra de código y se cumple la siguiente propiedad para un conjunto de palabras de código: dos palabras cualesquiera de la. conjunto difieren en al menos tres posiciones. Esta propiedad es importante para descifrar mensajes en presencia de interferencias. Para codificar las letras P, P, C, se utilizan palabras de código de 5 bits: P: 01111, P: 00001, C: 11000. El código de 5 bits para la letra T comienza con 1 y termina con 0. Determine la palabra de código para la letra t
Solución:
S: 1 1000
T: 1 011 0 (T comienza con 1 y termina con 0)
S y T: 2 letras son iguales, esto significa que las 3 letras restantes deben ser diferentes.
Respuesta: 1 0110
