Un Método Para La Construcción De Códigos De Redundancia Mínima-terminado.docx

Escuela Superior de Ingeniería Mecánica y Eléctrica Unidad Culhuacán Ingeniería en Comunicaciones y Electrónica

Materia: Teoría de la Comunicación y Manejo de la Información

Grupo: 8EM15

Alumno: De La Cruz Carbajal Jose Alfredo

Matricula: 2016350437

Profesor: Serrano Orozco Fernando Adán

Tema:

Un Método para la Construcción de Códigos de Redundancia Mínima

PROCEDIMIENTOS DE LA I.R.E Un Método para la Construcción de Códigos de Redundancia Mínima Resumen: se desarrolla un método óptimo para codificar un conjunto de mensajes que consiste en un número finito de miembros. Un código de redundancia mínima es uno construido de tal manera que se minimiza el número promedio de dígitos de codificación por mensaje. Un método importante para transmitir mensajes es transmitir en su lugar secuencias de símbolos. Si hay más mensajes que pueden enviarse que tipos de símbolos disponibles, entonces algunos de los mensajes deben usar más de un símbolo. Si se supone que cada símbolo requiere el mismo tiempo para la transmisión, entonces el tiempo de transmisión (longitud) de un mensaje es directamente proporcional al número de símbolos asociados con él. En este documento, el símbolo o secuencia de símbolos asociados con un mensaje dado se llamará "código de mensaje”. El número total de mensajes que podrían transmitirse se denominará "conjunto de mensajes". El acuerdo mutuo entre el transmisor y el receptor sobre el significado del código para cada mensaje del conjunto se denominará "código conjunto". Probablemente el código de conjunto más familiar se mencionó en la frase "uno si por tierra y dos si por mar". En este caso, el conjunto de mensajes consistía en los dos mensajes individuales "por tierra" y "por mar", y los códigos de mensaje eran "uno" y "dos". Para formalizar los requisitos de un código de conjunto, los símbolos de codificación se representarán mediante números. Por lo tanto, si hay D diferentes tipos de símbolos para ser usados en la codificación, estos serán representados por los dígitos 0, 1, 2,…. (D- 1). Por ejemplo, un código ternario se construirá utilizando los tres dígitos 0, 1 y 2 como símbolos de codificación. La cantidad de mensajes en el conjunto se llamará N. Sea P (i) la probabilidad del mensaje i. Entonces: 𝑵

∑ 𝑷(𝒊) = 𝟏 𝒊=𝟏

La longitud de un mensaje, L (i), es el número de dígitos de codificación que se le asigna. Por lo tanto, la longitud promedio del mensaje es: 𝑁

𝐿𝑎𝑣 = ∑ 𝑃(𝑖)𝐿(𝑖) 𝑖=1

El término 'redundancia "ha sido definido por Shannon' como una propiedad de los códigos. Un" código de redundancia mínima "se definirá aquí como un código conjunto que, para un conjunto de mensajes que consiste en un número finito de

miembros, N, y para un número dado de dígitos de codificación, D, produce la menor longitud de mensaje promedio posible. Con el fin de evitar el uso del término largo "mínima redundancia", este término será reemplazado aquí por "óptimo". Se entenderá entonces que, en este documento, "código óptimo" significa "código de redundancia mínima". Las siguientes restricciones básicas se impondrán en un código conjunto: a) No hay dos mensajes que consistirán en arreglos idénticos de dígitos de codificación. b) Los códigos de mensaje se construirán de tal manera que no sea necesaria ninguna indicación adicional para especificar dónde comienza y termina un código de mensaje una vez que se conoce el punto de inicio de una secuencia de mensajes. La restricción (b) requiere que ningún mensaje se codifique de tal manera que aparezca su código, dígito por dígito, como la primera parte de cualquier código de mensaje de mayor longitud. Por lo tanto, 01, 102, 111 y 202 son códigos de mensaje válidos para un conjunto de cuatro miembros. Por ejemplo, una secuencia de estos mensajes 1111022020101111102 se puede dividir en los mensajes individuales 111-102-20201-01-111-102. Todo lo que el receptor necesita saber es el código conjunto. Sin embargo, si el conjunto tiene códigos de mensaje individuales que incluyen 11, 111, 102 y 02, entonces cuando una secuencia de mensajes comienza con los dígitos 11, no se sabe de inmediato si el mensaje 11 se recibió o si son solo los dos primeros. Dígitos del mensaje 111. Además, incluso si la secuencia resulta ser 11102, todavía no es seguro si se transmitió 111-02 o 11-102. En este ejemplo, se indica el cambio de uno de los dos códigos de mensaje 111 u 11. C. E. Shannon y R. M. Fano han desarrollado procedimientos de codificación en conjunto con el fin de demostrar que el número promedio de dígitos binarios requeridos por mensaje se acerca a la cantidad promedio de información por mensaje. Sus procedimientos de codificación no son óptimos, pero se aproximan al comportamiento óptimo cuando N se acerca al infinito. Kraft ha realizado algunos trabajos para descifrar un método de codificación que proporciona una longitud de código promedio lo más cercana posible al ideal cuando el conjunto contiene un número finito de miembros. Sin embargo, hasta el momento, no se ha sugerido ningún procedimiento definido para la construcción de dicho código para el conocimiento del autor. El propósito de este documento es derivar tal procedimiento. Requisitos de codificación derivados. Para un código óptimo, la longitud de un código de mensaje dado nunca puede ser menor que la longitud de un código de mensaje más probable. Si no se cumpliera

este requisito, entonces se podría obtener una reducción en la longitud promedio de los mensajes intercambiando los códigos de los dos mensajes en cuestión de tal manera que el código más corto se asocie con el mensaje más probable. Además, si hay varios mensajes con la misma probabilidad, es posible que los códigos para estos mensajes puedan diferir en longitud. Sin embargo, los códigos para estos mensajes pueden intercambiarse de cualquier manera sin afectar la longitud promedio del código para el conjunto de mensajes. Por lo tanto, se puede suponer que los mensajes del conjunto se han ordenado de manera tal que: 𝑃(1) ≧ 𝑃(2) ≧ ⋯ ≧ 𝑃(𝑁 − 1) ≧ 𝑃(𝑁) y que, además, para un código óptimo, la condición se cumple. 𝐿(1) ≧ 𝐿(2) ≧ ⋯ ≧ 𝐿(𝑁 − 1) ≧ 𝐿(𝑁) Se supone que este requisito se cumple a lo largo de la siguiente discusión. Podría imaginarse que un código de conjunto podría asignar q más dígitos al mensaje N que al mensaje (N-l). Sin embargo, los primeros dígitos L (N-1) del mensaje N no deben usarse como el código para ningún otro mensaje. Por lo tanto, los dígitos q adicionales no servirían para ningún propósito útil y aumentarían innecesariamente L av. Por lo tanto, para un código óptimo es necesario que L (N) sea igual a L (N-1). El prefijo KTH de un código de mensaje se definirá como los primeros dígitos k de ese código de mensaje. La restricción básica (b) podría entonces ser reescrita como: ningún mensaje será codificado de tal manera que su código sea un prefijo de cualquier otro mensaje, o que cualquiera de sus prefijos se utilice en otra parte como código de mensaje. Imagine un código óptimo en el que no dos de los mensajes codificados con longitud L (N) tienen prefijos idénticos de orden L (N)-1. Dado que se ha asumido un código óptimo, ninguno de estos mensajes de longitud L (N) puede tener códigos o prefijos de cualquier orden que correspondan a otros códigos. Entonces sería posible soltar el último dígito de todo este grupo de mensajes y así reducir el valor de lav. Por lo tanto, en un código óptimo, es necesario que al menos dos (y no más de D) de los códigos con longitud L (N) tengan prefijos idénticos de orden L (N)-1. Un requisito adicional se puede hacer para un código óptimo. Supongamos que existe una combinación de los diferentes tipos de dígitos de codificación de D que es menor que L (N) dígitos de longitud y que no se utiliza como un código de mensaje o que no es un prefijo de un código de mensaje. A continuación, esta combinación de dígitos podría utilizarse para sustituir el código para el mensaje nth con la consecuente reducción de la.. Por lo tanto, todas las secuencias posibles de L (N)-1 los dígitos se deben utilizar como códigos de mensaje, o deben tener uno de sus prefijos usados como código de mensaje. Las restricciones derivadas de un código

óptimo se resumen en forma condensada a continuación y se consideran además de las restricciones (a) y (b) dadas en la primera parte de este documento: (c) L (1) < L (2) < L (N-;) L (N). (5) (d) por lo menos dos y no más que tPof los mensajes con la longitud del código L (N) tiene códigos que son iguales a excepción de sus dígitos finales. (e) cada secuencia posible de L (N)-1 dígitos debe ser utilizado como un código de mensaje o NUST tiene uno de sus prefijos Código Binario Optimo para facilitar el desarrollo del procedimiento de codificación de optinium, permítanos ahora restringirnos al problema de la codificación binaria. Posteriormente, este procedimiento se extenderá al caso general de los dígitos D. Restricción (c) hace necesario que los dos mensajes menos probables tengan códigos de igual longitud. La restricción (d) coloca el requisito que, para D igual a dos, hay solamente dos de los mensajes con la longitud codificada L (N) que son idénticos a excepción de sus últimos dígitos. Los dígitos finales de estos dos códigos serán uno de los dos dígitos binarios, 0 y 1. Se imprescindibles para asignar estos dos códigos de mensaje a la nth y los (N-l) St mensajes ya que en esta pinta no se sabe si o no otros códigos de longitud l (n) existen. Una vez hecho esto, estos dos mensajes son equivalentes a un único mensaje compuesto. Su código (aún indeterminado) será los prefijos comunes del orden L (N)-1 de estos dos mensajes. Su probabilidad será la suma de las probabilidades de los dos mensajes de la que se creó. El conjunto que contiene este mensaje compuesto en el lugar de sus dos mensajes de componente se llamará el primer conjunto de mensajes auxiliares. Este conjunto recién creado contiene menos mensaje que el original. Sus miembros deben oscilar en caso de necesidad de modo que los mensajes se ordenen otra vez según sus probabilidades. Puede considerarse exactamente como el ensamble original. Los códigos para cada uno de los dos mensajes menos probables en este nuevo conjunto deben ser idénticos excepto en sus dígitos finales; 0 y 1 se asignan como estos dígitos, uno para cada uno de los dos mensajes. Cada nuevo conjunto auxiliar contiene un mensaje menos que el conjunto precedente. Cada ensamble auxiliar presenta el ensamble original con el uso completo de los requisitos de codificación necesarios acumulados. El procedimiento se aplica una y otra vez hasta que el número de miembros en el conjunto de mensajes auxiliares formado más recientemente se reduzca a dos. Uno de cada uno de los dígitos binarios se asigna a cada uno de estos dos mensajes compuestos. Estos mensajes se combinan entonces para formar un solo mensaje compuesto con la unidad de la probabilidad, y la-codificación es completa.

Ahora examinemos la Tabla I. La columna de la izquierda contiene las probabilidades de mensajes ordenados del conjunto a codificar. N es igual a 13. Dado que cada combinación de dos mensajes (indicada por un corchete) está acompañada por la asignación de un nuevo dígito a cada uno, entonces el número total de dígitos que debe asignarse a cada mensaje original es el mismo que el número de Combinaciones indicadas para ese mensaje. Por ejemplo, el mensaje marcado $, o un compuesto del que forma parte, se combina con otros cinco veces y, por lo tanto, se le debe asignar una longitud de código de cinco dígitos. Cuando no hay alternativa al elegir los dos mensajes menos probables, entonces está claro que los requisitos, establecidos como necesarios, también son suficientes para obtener un código óptimo. Pueden surgir situaciones en las que se puede elegir entre dos o más grupos de mensajes menos probables. Tal caso surge, por ejemplo, en el cuarto conjunto auxiliar de la Tabla I. Cualquiera de los mensajes de probabilidad 0.08 podría haberse combinado con el de probabilidad 0.06. Sin embargo, es posible reorganizar los códigos de cualquier manera entre mensajes igualmente probables sin afectar la longitud promedio del código, por lo que se podría haber elegido cualquiera de las alternativas. Por lo tanto, el procedimiento dado siempre es suficiente para establecer un código binario óptimo. Las longitudes de todos los mensajes codificados derivados de la tabla I se dan en la tabla II. Habiendo determinado las longitudes de código apropiadas para cada mensaje, el problema de especificar los dígitos reales permanece. Existen muchas alternativas. Dado que la combinación de mensajes en sus composites es similar a las sucesivas confluencias de trickles, rivulets, arroyos, y

arroyos en un río grande final, el procedimiento hasta ahora descrito pudo ser considerado análogo a la colocación de muestras por un insecto agua-transmitido en cada uno de estas ensambladuras mientras que él viaja río abajo. Debe recordarse que el código que deseamos es aquél que el insecto debe recordar para poder trabajar su camino de vuelta hacia arriba. Puesto que la colocación de las muestras no necesita seguir la misma regla, por ejemplo “cero-derecho-que regresa" en cada ensambladura, puede ser visto que hay por lo menos 212 diversas maneras de asignar los dígitos del código para nuestro ejemplo.

El código de la tabla II se obtuvo utilizando el dígito 0 para el mensaje superior y el dígito 1 para el mensaje inferior de cualquier corchete. Es importante notar en la tabla I que la restricción de codificación (e) se cumple automáticamente siempre y cuando dos mensajes (y no uno) se colocan en cada soporte. Generalización del método La codificación óptima de un conjunto de mensajes utilizando tres o más tipos de dígitos es similar al procedimiento de codificación binaria. Se utilizará una tabla de conjuntos de mensajes auxiliares similares a la tabla I. Los corchetes que indican los mensajes combinados para formar mensajes compuestos se utilizarán de la misma manera que se hizo en la tabla I. Sin embargo, para satisfacer la restricción (e), se requerirá que todos estos corchetes, con la posible excepción de uno que combine los mensajes menos probables del conjunto original, combinen siempre

una serie de mensajes iguales a D. Se señalará que el conjunto auxiliar de terminación siempre tiene un mensaje de probabilidad de unidad. Cada conjunto precedente se incrementa en número por D-1 hasta que se alcanza el primer conjunto auxiliar. de terminación siempre tiene un mensaje de probabilidad de unidad. Cada conjunto precedente se incrementa en número por D-1 hasta que se alcanza el primer conjunto auxiliar. Por lo tanto, si N1 es el número de mensajes en el conjunto del primer auxiliar, entonces (N1-1)/(D-1) debe ser un entero. Sin embargo, ni = NI-no + 1, donde no es el número de los mensajes menos probables combinados en un corchete en el original. En la tabla III se considera un ejemplo utilizando un conjunto de ocho mensajes que se codifican con cuatro dígitos no se encuentra para ser 2. El código enumerado en la tabla se obtiene asignando los cuatro dígitos 0, 1, 2 y 3, en orden, a cada uno de los corchetes.

ACK, NOTACIONES el autor está en deuda con el Dr. w. k. Linvill y el Dr. r. m. Fano, ambos del Massachusetts Institute of Technology, por su crítica útil de este documento.

Codificación con sistemas lineales JOHN P. COSTASt, ASSOCIATE, IRE Se considera la transmisión del mensaje resumido sobre un canal ruidoso. Se deben diseñar dos redes lineales: una que se utiliza para tratar el mensaje antes de la transmisión y la segunda para filtrar el mensaje tratado más el ruido del canal en el extremo receptor. El error cuadrado medio entre la salida del circuito de transmisión real y el mensaje retrasado se minimiza para una potencia de señal media permitida dada por el diseño de red adecuado. Los ejemplos numéricos se dan y se discuten. Introducción El problema para considerar es el de la transmisión del mensaje sobre un canal ruidoso. Como se muestra en la Fig. 1, una función de mensaje, FM (t), debe ser enviada hacia abajo de un canal en el cual una función de ruido, FN (t), se introduce aditivamente. La salida del sistema resultante se representa byfo (t). En la mayoría de los sistemas de comunicación, la oportunidad existe para codificar el mensaje antes de su introducción en el canal de transmisión. Recientemente, Wiener, Shannon, y otros han considerado procesos de codificación de una naturaleza bastante compleja donde la función de mensaje es muestreada, cuantificada, y los valores de muestra resultantes convertidos en un código de pulso para la transmisión. Aunque esta técnica puede ser bastante útil en muchos casos, su aplicación estará restringida por la complejidad de los equipos terminales requeridos. En este debate, los sistemas de codificación y decodificación se ha limitado a las redes lineales. En la Fig. 1, la red H (w) se utilizará para codificar el mensaje antes de la transmisión y la red G (c) realizará la decodificación necesaria. La red H (w) debe diseñarse de modo que el mensaje esté predistorsionado o codificado de tal manera que permita que la red de decodificación o filtrado G (w) dé una mejor salida del sistema de la que hubiera sido posible si el mensaje se hubiese enviado sin modificaciones.

Antes de ir más lejos, se debe elegir un criterio de rendimiento para el sistema de transmisión. Es decir, se debe decidir una cantidad cuantificable para permitirnos determinar si un par de red en particular H (w)-G (w) es más satisfactorio que algún otro par. No se puede esperar que un único criterio de rendimiento se aplique en todas las situaciones y no se hace tal reclamación para los medios son la medida de error de rendimiento que se va a utilizar.