UNIVERSIDAD NACIONAL DE LOJA
CARATULA
AREA DE LA ENERGÍA Y LOS RECURSOS NATURALES NO RENOVABLES
INGENIERIA EN TELECOMUNICACIONES
TEORÍA DE LA INFORMACION INFORME
TRABAJO GRUPAL Nro. _1_
DOCENTE:
ING. Santiago Medina
INTEGRANTES:
• Juan Guerrero.
• Alan Jaramillo.
• Nicolás Marin.
Ciclo: 4º “A”
Fecha de Entrega Planificada: 18/02/2024
Fecha de Entrega Realizada: 19/02/2024
LOJA - ECUADOR
2024
UNIVERSIDAD NACIONAL DE LOJA FACULTAD DE LA ENERGÍA, LAS
INDUSTRIAS Y LOS RECURSOS NATURALES NO RENOVABLES
CARRERA DE INGENIERÍA EN TELECOMUNICACIONES
Fecha: 19/02/2024
Tema: Desigualdad de Kraft.
Introducción:
La Desigualdad de Kraft es “un principio fundamental en la teoría de códigos, esencial
para garantizar la eficiencia y la integridad en la transmisión de información”
([Link], 2016). Nombrada en honor a León G. Kraft, un estudiante del MIT, esta
desigualdad establece condiciones necesarias para la existencia de códigos prefijo y
unívocamente decodificables.
Desde su formulación en 1949, ha sido ampliamente estudiada y aplicada en diversas
áreas de la ciencia de la computación y la teoría de la información.
La Desigualdad de Kraft es “un concepto fundamental en la teoría de la información y la
teoría de códigos. Fue propuesta por primera vez por Leon G. Kraft en su tesis de maestría
titulada "A Device for Quantizing, Grouping, and Coding Amplitude Modulated Pulses",
presentada en el Instituto de Tecnología de Massachusetts (MIT) en 1949” (Paul Penfield,
Jr.). Aunque el trabajo de Kraft no era específicamente sobre la desigualdad que lleva su
nombre, su trabajo sentó las bases para la formulación y la comprensión de esta
desigualdad, que fue formalizada por McMillan en 1956.
Fig 1.1 Retrato de Leon G. Kraft.
La desigualdad de Kraft establece condiciones necesarias para la existencia de códigos
prefijo, los cuales son esenciales en la codificación de datos para asegurar la unicidad de
decodificación. Esta desigualdad afirma que, para un conjunto dado de longitudes de
palabra, las longitudes de las palabras en un código prefijo deben satisfacer ciertas
restricciones para que el código sea válido.
En términos más simples, limita la cantidad de información que se puede transmitir en
un código prefijo, asegurando que sea posible decodificar la información de manera
única.
Fórmula:
Fig 1.2 Formula de la inecuación de Kraft.
• q es el número total de palabras código.
• li son las longitudes de cada palabra código.
• r es el número de símbolos en el alfabeto código.
Origen y Propósito:
La Desigualdad de Kraft se creó para establecer condiciones que permitan la existencia
de códigos eficientes y decodificables en la transmisión de información.
Su objetivo es garantizar la integridad y la fiabilidad de los datos transmitidos,
minimizando la redundancia y maximizando la capacidad de compresión. Esta
desigualdad es fundamental en la teoría de la información y ha sido aplicada en el diseño
de algoritmos de compresión y transmisión de datos.
Funcionamiento y Principios
La Desigualdad de Kraft establece “una relación entre las longitudes de las palabras en
un código prefijo y la probabilidad de ocurrencia de esas palabras. Esta relación es crucial
para garantizar la existencia de códigos válidos y unívocamente decodificables. En
términos más simples, limita la cantidad de información que se puede transmitir en un
código prefijo, asegurando que sea posible decodificar la información de manera única”
(textoscientificos, 2020).
Para cumplir con esta desigualdad, las longitudes de las palabras en un código prefijo
deben cumplir con ciertas condiciones, lo que permite determinar la viabilidad y
eficiencia del código propuesto.
Aplicaciones en la Teoría de la Información
La Desigualdad de Kraft tiene aplicaciones en diversos campos, desde la compresión de
datos hasta la transmisión de información en sistemas de comunicación. En la compresión
de datos, ayuda a diseñar algoritmos eficientes que minimizan la redundancia en la
representación de la información.
En sistemas de comunicación, garantiza una transmisión confiable al limitar la longitud
de los códigos, facilitando así su decodificación precisa. Además, se utiliza en el diseño
de códigos de corrección de errores y en la optimización de sistemas de almacenamiento
de datos.
Conclusiones
• La Desigualdad de Kraft, esencial en la teoría de códigos, garantiza la eficiencia
en la transmisión de información. Aunque propuesta por Leon G. Kraft, su
formulación fue formalizada por McMillan en 1956, sentando las bases para su
comprensión y aplicación.
• Esta desigualdad tiene aplicaciones fundamentales en la compresión de datos, la
transmisión de información y otros campos relacionados. Su comprensión y
aplicación adecuadas son cruciales para el diseño eficiente de sistemas de
comunicación y almacenamiento de datos, con potencial para mejorar
significativamente la eficiencia y la fiabilidad de dichos sistemas.
Recomendaciones
• Se sugiere realizar un estudio exhaustivo de la Desigualdad de Kraft,
comprendiendo sus principios y aplicaciones en profundidad, lo que permitirá una
implementación más efectiva en proyectos de codificación y transmisión de datos.
• Es fundamental integrar activamente la Desigualdad de Kraft en el proceso de
diseño de sistemas de comunicación y almacenamiento de datos, considerando sus
restricciones y condiciones para garantizar la eficiencia y la fiabilidad de los
sistemas implementados.
ANEXOS
• Anexo 1.
Código funcional realizado en Matlab
% Ingresa el numero de codigos y la base del codigo
numCodigos = input('Ingrese el numero de codigos: ');
baseCodigo = input('Ingrese la base del codigo (por ejemplo, 2 para binario, 3 para
ternario, etc.): ');
% Inicializa la matriz de longitudes de codigo
longitudesCodigos = zeros(1, numCodigos);
% Ingresa las longitudes de cada codigo
disp('Ingrese las longitudes de los codigos:');
for i = 1:numCodigos
longitud = input(['Codigo ' num2str(i) ': ']);
longitudesCodigos(i) = longitud;
end
% Muestra las longitudes de los codigos antes de ordenar
disp('Longitudes de los codigos antes de ordenar:');
disp(longitudesCodigos);
% Ordena las longitudes de los codigos de menor a mayor
longitudesCodigos = sort(longitudesCodigos);
% Muestra las longitudes de los codigos después de ordenar
disp('Longitudes de los codigos después de ordenar:');
disp(longitudesCodigos);
% Realiza la inecuacion
suma = sum(1 ./ baseCodigo .^ longitudesCodigos);
% Verifica si la desigualdad de Kraft se cumple
if suma <= 1
disp(['La desigualdad de Kraft se cumple. Suma: ' num2str(suma)]);
% Genera el codigo instantaneo con las longitudes proporcionadas
disp('Codigo instantaneo generado:');
symbols = cell(1, baseCodigo);
for i = 1:baseCodigo
symbols{i} = num2str(i - 1);
end
generaCod = cell(1, numCodigos);
for i = 1:numCodigos
codigoInstantaneo = generadorCodigoInstantaneo(longitudesCodigos(i),
baseCodigo, symbols, generaCod);
generaCod{i} = codigoInstantaneo;
disp(codigoInstantaneo);
% Verifica si el código generado es prefijo de otro
for j = 1:i-1
if strncmp(codigoInstantaneo, generaCod{j}, length(codigoInstantaneo))
disp(['El código generado es prefijo de otro código: ' codigoInstantaneo ' es
prefijo de ' generaCod{j}]);
end
end
end
else
disp(['La desigualdad de Kraft no se cumple. Suma: ' num2str(suma)]);
end
function codigoInstantaneo = generadorCodigoInstantaneo(longitud, baseCodigo,
symbols, generatedCodes)
codigoInstantaneo = '';
while length(codigoInstantaneo) < longitud
selecSymbol = symbols{randi(baseCodigo)};
tiempoCodigo = [codigoInstantaneo selecSymbol];
% Verifica si el código generado es un prefijo de algún código existente
if ~any(strcmp(generatedCodes, tiempoCodigo))
codigoInstantaneo = tiempoCodigo;
end
% Si la longitud del código generado es igual a la longitud deseada,
% pero ya existe en la lista de códigos generados, sal del bucle
if length(codigoInstantaneo) == longitud && any(strcmp(generatedCodes,
codigoInstantaneo))
break;
end
end
• Anexo 2.
Interfaz ilustrativa realizada en Matlab
• Anexo 3.
Presentación sobre la Inecuación de Kraft
Manual de Usuario:
Este programa en MATLAB te permite generar códigos instantáneos basados en la
desigualdad de Kraft. Sigue estos pasos para utilizarlo de manera efectiva:
1. Inicio del Programa: Ejecuta el programa desde MATLAB ejecutando el archivo
principal.
2. Ingreso de Datos: Cuando se te solicite, ingresa el número de códigos que deseas
generar. Este número debe ser un valor entero positivo. Luego, ingresa la base del
código. La base del código debe ser un número entero mayor que 1. Por ejemplo,
2 para códigos binarios, 3 para códigos ternarios, etc.
3. Ingreso de Longitudes de Códigos: Se te pedirá que ingreses las longitudes de
cada uno de los códigos. Asegúrate de ingresar valores enteros positivos para cada
longitud.
4. Visualización de Longitudes: Verás las longitudes de los códigos ordenadas de
menor a mayor. Esto te permitirá verificar la entrada de datos.
5. Verificación de la Desigualdad de Kraft: El programa verificará si se cumple la
desigualdad de Kraft. Esta es una propiedad necesaria para que los códigos
instantáneos sean generados correctamente.
6. Resultados: Si la desigualdad de Kraft se cumple, verás los códigos instantáneos
generados. Si no se cumple, se mostrará un mensaje explicativo y el programa
terminará. Finalización del Programa: Una vez que hayas revisado los códigos
instantáneos generados, el programa finalizará su ejecución.
7. Generación de Códigos Instantáneos y unívocos: Si la desigualdad de Kraft se
cumple, el programa generará los códigos instantáneos. Estos códigos se
generarán de acuerdo con las longitudes proporcionadas y se mostrarán en la
consola.
Manual de Programador
Este es el funcionamiento interno del código en MATLAB:
1. Ingreso de Datos: El programa solicita al usuario que ingrese el número de
códigos que desea generar (numCodigos) y la base del código (baseCodigo).
2. Inicialización de Matriz: Se inicializa una matriz (longitudesCodigos) con
ceros, con la misma longitud que el número de códigos ingresado. Esto
proporciona un almacenamiento para las longitudes de los códigos. Ingreso de
Longitudes: El usuario ingresa las longitudes de cada uno de los códigos, que se
almacenan en la matriz (longitudesCodigos).
3. Ordenamiento de Longitudes: Se muestran las longitudes de los códigos antes
y después de ser ordenadas de menor a mayor. Esto ayuda al usuario a verificar la
entrada de datos.
4. Verificación de Desigualdad de Kraft: Se verifica si se cumple la desigualdad
de Kraft. Si se cumple, el programa procede a generar los códigos instantáneos.
Si no se cumple, se muestra un mensaje correspondiente y el programa termina.
5. Generación de Códigos Instantáneos: Para generar los códigos instantáneos, se
utiliza una función auxiliar llamada (generadorCodigoInstantaneo). Esta
función genera un código instantáneo de una longitud dada, utilizando un conjunto
de símbolos y verificando que el código generado no sea un prefijo de ningún
código existente.
6. Verificación de Prefijos: Se verifica si cada código generado es prefijo de otro
código. Si es así, se muestra un mensaje indicando cuál código es prefijo de cuál.
Bibliografía
[Link]. (12 de 06 de 2016). [Link]. Obtenido de .[Link]:
[Link]
[Link]
Paul Penfield, Jr. (s.f.). libretexts. Obtenido de libretexts.:
[Link]
Da_(Penfield)/06%3A_Comunicaciones/6.01%3A_Modelo_de_origen/6.1.01%
3A_Desigualdad_Kraft
textoscientificos. (11 de 11 de 2020). textoscientificos. Obtenido de textoscientificos:
[Link]
