Una teoría matemática de la comunicación Por SHANNON de la C.E. INTRODUCCIÓN El desarrollo reciente de varios métodos de modulación tales como PCM y el PPM que intercambian la anchura de banda para el cociente signal-to-noise tiene intensificando el interés en una teoría general de la comunicación. Una base para tal teoría se contiene en los papeles importantes de Nyquist y de Hartley en este tema. En el documento ampliaremos la teoría para incluir a número de nuevos factores, particularmente el efecto de ruido en el canal, y el posible de los ahorros debido a la estructura estadística del mensaje original y debido a la naturaleza de la destinación final de la información. El problema fundamental de la comunicación es el de la reproducción en un punto exactamente o aproximadamente un mensaje seleccionado en otro punto. Los mensajes tienen con frecuencia "significado"; este se refiere o es correlacionado según un cierto sistema con ciertas entidades físicas o conceptuales. Estos aspectos semánticos de la comunicación son inaplicables a problema de la ingeniería. El aspecto significativo es que es el mensaje real es una seleccion de un sistema de mensajes posibles. El sistema debe ser diseñado para funcionar para cada selección posible, no apenas el una que realmente elegirte puesto que esto es desconocido a la hora de diseño. Si el número de mensajes en el sistema es finito entonces este número o cualquiera la función monotónica de este número se puede mirar como medida de en la información produjo cuando un mensaje se elige del sistema, todas las opciones siendo igualmente probable. Al igual que fue precisada por Hartley el más natural la opción es la función logarítmica. Aunque esta definición debe ser generalizado considerablemente cuando consideramos la influencia de la estadística del mensaje y cuando tenemos una gama continua de mensajes, nosotros voluntad en todos los casos utilizan una medida esencialmente logarítmica. La medida logarítmica es más conveniente por varias razones: 1. Es prácticamente más útil. Parámetros de la importancia de la ingeniería por ejemplo tiempo, anchura de banda, el número de relays, el etc., tiende a variar linealmente con el logaritmo del número de posibilidades. Por ejemplo, agregando un relay a un grupo dobla el número de los estados posibles de los relays. Agrega 1 al logaritmo de la base 2 de este número. Doblar el tiempo ajusta áspero el número de mensajes posibles, o dobles el logaritmo, el etc. 2. Es más cercano a nuestra sensación intuitiva en cuanto a la medida apropiada. Esto es relacionado de cerca con (1) puesto que intuitivamente medimos entidades de comparacion lineal con estándares comunes. Uno se siente, por ejemplo, que dos perforaron las tarjetas deben tener dos veces la capacidad de una para el almacenaje de información, y dos canales idénticos dos veces la capacidad de una para la información que transmite. 3. Es matemáticamente más conveniente. Muchas de las operaciones limitadoras ser simple en términos de logaritmo pero requeriría la nueva exposición torpe adentro términos del número de posibilidades. La opción de una base logarítmica corresponde a la opción de una unidad para información que mide. Si se utiliza la base 2 las unidades que resultan pueden ser dígitos binarios llamados, o más brevemente bils, una palabra sugerida por J.W. Tukey. Un dispositivo con dos posiciones estables, tales como un relay o un circuito de flip-flop, puede almacenar un bit de información. N dispositivos puede almacenar N bits, desde el número total de estados posibles es 2^N y el registro, 2^N = N. Si es la base 10 utilizó las unidades puede ser llamado los dígitos decimales. Desde entonces log_2(M) = log_10(M)/log_10(2) = 3.32 registran, M, un dígito decimal es aproximadamente 10/3 bits. Una rueda del dígito en una máquina que computa del escritorio tiene diez posiciones estables y por lo tanto tiene una memoria de un dígito decimal. En trabajo analítico donde están implicadas la integración y la diferenciación la base e es a veces útil. Las unidades que resultan de la información serán llamadas unidades naturales. El cambio de la base a a la base b requiere simplemente multiplicación por el log_b(A). Por un sistema de comunicación significaremos un sistema del tipo indicado esquemáticamente en la Fig 1. Consiste en esencialmente cinco partes: 1. Una fuente de informacion que produce un mensaje o una secuencia de mensajes que se comunicarán al terminal de recepción. El mensaje puede ser de varios tipos: e.g. (a) secuencia de A de letras como en un telégrafo o un teletipo sistema; (b) Una sola función del tiempo f (l) como en radio o telefonía; (c) A función del tiempo y de otras variables como en la TV en blanco y negro - aquí el mensaje se puede expresar en funciónes f(x,y,t)dos cordenadas y tiempo, la intensidad de luz en el punto (x, y) y tiempo t en un tubo de la recolección placa; (d) Dos o más funciones del tiempo, opinión f (l), g (l), h (l) - éste es caso en la transmisión sonora “tridimensional” o si se piensa el sistema para mantener varios canales del individuales en múltiplexación ; (e) Varias funciones de varias variables - en la televisión de color el mensaje consisten en tres funciones f(x,y,t), g(x,y,t) , h(x,y,t) definido en una serie continua tridimensional - podemos también pensar en estas tres funciones como componentes de un campo vectorial definido en la región - similar, varias fuentes blancas y negras de la televisión produciría los “mensajes” que consisten en un número de funciones de tres variables; (f) Las varias combinaciones también ocurren, por ejemplo en la televisión con un canal audio asociado. 2. Un transmisor funciona en el mensaje de cierta manera al produciendo una señal conveniente para la transmisión sobre el canal. En telefonía esta operacion consiste simplemente del cambio sonoro de presión en proporcion a la corriente eléctrica. En telegrafía tenemos una operación de codificación que produzce una secuencia de puntos, de rociadas y de espacios en el canal que corresponde a el mensaje. En un sistema múltiplex del PCM las diversas funciones del discurso deben ser muestreado, comprimido, quantized y codificado, y finalmente interpolado para construir correctamente la señal. Sistemas, televisión, y la modulación en frecuencia son ejemplos de las operaciones complejas aplicadas a el mensaje para obtener la señal. 3. Los canales son simplemente el medio que transmitía la señal de transmisor al receptor. Puede ser un par de alambres, un cable coaxial, una venda de radiofrecuencias, un haz de luz, etc. 4. el receptor realiza la operación inversa hecha por el transmisor, reconstruyendo el mensaje de la señal. 5. el destinatario es la persona (o cosa) para en quién el mensaje está tendido. Deseamos considerar ciertos problemas generales que implican la comunicación sistemas. Para hacer esto es primero necesario representar los varios elementos implicado como entidades matemáticas, idealizadas convenientemente de su contrapartes fisicas. Podemos clasificar áspero sistemas de comunicación en tres categorías principales: discreto, continuo y mezclado. Por un sistema discreto nosotros significará uno en de el cual el mensaje y la señal sean una secuencia de símbolos discretos. Un caso típico es telegrafía donde está a el mensaje secuencia de las letras y de la señal una secuencia de puntos, de rociadas y de espacios. Un sistema continuo es uno en el cual se tratan el mensaje y la señal ambos como funciones continuas, e.g. radio o televisión. Un sistema mezclado es uno adentro las variables discretas y continuas cuál aparecen, e.g., PCM tranmicion del discurso. Primero consideramos el caso discreto. Este caso tiene usos no sólo en teoría de comunicación, pero también en la teoría de máquinas que computan, el diseño de los intercambios de teléfono y de otros campos. Además el discreto encajonar las formas una fundación para los casos continuos y mezclados que serán tratado por la mitad segundo del documento. PARTE I: SISTEMAS DISCRETOS SIN RUIDO 1. EL CANAL DISCRETO SIN RUIDO El teletipo y la telegrafía son dos ejemplos simples de un canal discreto para la información que transmite. Generalmente, un canal discreto significará a sistema por el que una secuencia de opciones de un sistema finito de sym- elementalSr de los bols. S, se puede transmitir a partir de un punto a otro. Cada uno de los símbolos S_i se asumen para tener una cierta duración en tiempo t_i en segundos (no necesariamente iguales para diferentes S_i, por ejemplo los puntos y las rociadas adentro telegrafía). No se requiere que todas las secuencias posibles del S_i sean casquillo capaz de la transmisión en el sistema; ciertas secuencias pueden ser permitidas solamente. Éstas serán señales posibles para el canal. Así en telegrafía suponer los símbolos son: (1) Un punto, una línea que consiste en encierro para una unidad del tiempo y entonces línea abierta para una unidad del tiempo; (2) Una rociada, consistiendo en tres unidades del tiempo de encierro y de una unidad abrirte; (3) Un espacio de la letra que consiste en, por ejemplo, tres unidades de línea abrirte; (4) Un espacio de la palabra de seis unidades de línea abiertas. Puede ser que coloquemos la restricción en secuencias permisibles que ningunos espacios se siguen (para si dos espacios de la letra son adyacentes, es idéntica con un espacio de la palabra). la pregunta que ahora consideramos es cómo una puede medir la capacidad de tal a canal para transmitir la información. En la caja del teletipo donde están todos los símbolos de la misma duración, y cualquiera la secuencia de los 32 símbolos no se prohibe la respuesta es fácil. Cada símbolo representa cinco pedacitos de información. Si el sistema transmite símbolos de n por segundo es natural decir que el canal tiene una capacidad de los pedacitos 5n por en segundo lugar. Esto no significa que el canal del teletipo será siempre transporte la información mitting en este tarifa-este es la tarifa posible máxima y si o no la tarifa real alcanza este máximo depende de la fuente de la información que alimenta el canal, como aparecerá más adelante. Una teoría matemática de la comunicación En el caso más general con diversas longitudes de símbolos y de apremios en las secuencias permitidas, hacemos el definition siguiente: Definición: La capacidad C de un canal discreto se da cerca donde está el número N (T) de señales permitidas de la duración 7'. Se ve fácilmente que en la caja del teletipo éste reduce al anterior resultado. Puede ser demostrado que el límite en la pregunta existirá como numérico finito azufaifas en la mayoría de los casos del interés. Suponer todas las secuencias del Sr de los símbolos, -. , Se permite S, y estos símbolos tienen duraciones 11. , t. Cuál es ¿capacidad de canal? Si N (1) representa el número de secuencias uration de d' 1 que tenemos N (t) = N (1 -11) + N (1 -12) + +. + N (1 -1,) El número total es igual a la suma de los números de las secuencias que terminan adentro El Sl, SZ, el *-*, S, y éstos son N (1 -1r), N (1 - es). , N (1 - I~), respectively. Según un resultado bien conocido en diferencias finitas, N (1) entonces está asintótico para I grande a XI donde está la solución X0 verdadera más grande del ecuación característica: XL' + xf2 +. + X'” = 1 y por lo tanto c = registro x0 En caso de que haya restricciones en secuencias permitidas podemos' a menudo ob- inmóvil tain una ecuación de diferencia de este tipo y hallazgo C de la característica ecuación. En el caso de la telegrafía mencionado arriba N (1) = N (1 -2) + NO -4) + N (1 -5) + N (1 -7) + N (1 -8) + N (1 -10) como vemos contando secuencias de símbolos según el último o al lado de el ocurrir pasado del símbolo. Por lo tanto C es - el registro ~0 donde está el positivo ~0 raíz de 1 = c; ” - I l.f4 - i PK 4 P7 + PUB+ P' O* que soluciona esto que encontramos C = 0.539. Un tipo muy general de restricción que se puede poner en el SE permitido los quences son el siguiente: Imaginamos un número de al posible de los estados, a2, * *. , a. Para ciertos símbolos de cada estado solamente del sistema y, * * *, del S, puede estar transmitido (diversos subconjuntos para los diversos estados). Cuando uno de éstos se ha transmitido los cambios del estado a un nuevo estado dependiendo ambos encendido el viejo estado y el símbolo particular transmitidos. La caja del telégrafo es un ejemplo simple de esto. Hay dos estados dependiendo de si o no C.E. Shannon un espacio era el símbolo pasado transmitido. Si tan entonces solamente un punto o una rociada se pueden enviar después y siempre los cambios añejos. Si no, cualquier símbolo puede ser transmitido y los cambios del estado si se envía un espacio, si no permanece iguales. Las condiciones pueden indicado a.C. en un gráfico linear según las indicaciones de Higo 2. Los puntos de la ensambladura corresponden a los estados y las líneas indican los símbolos posibles en un estado y el estado que resulta. En el apéndice I está demostrado que si las condiciones en scqucnccs permitidos pueden descrito a.C. en esto la forma C existirá y poder calculada a.C. de acuerdo con el siguiente resultado: Theorem1: Dejar 6: ; ' ser la duración del símbolo del sul que es permisible adentro indicar i y conduce para indicar el J. Entonces la capacidad de canal C es igual al registro W donde está la raíz W verdadera más grande de la ecuación determinante: donde está cero 6ij = 1 si i = J' y de otra manera. ROCIADA PUNTO ROCIADA ESPACIO DE WORD Representación del higo 2-Graphical de los apremios en símbolos del telégrafo. Por ejemplo, en la caja del telégrafo (higo 2) el determinante está: -1 (1Y-2 + > del W “; (Intravenoso de P 4 i “) (W” + 1r4 -1) = O En la extensión esto conduce a la ecuación dada arriba para este caso. 2. FUENTE DISCRETA DE TIIE DE LA INFORMACIÓN Hemos visto que bajo condiciones muy generales el logaritmo del el número de señales posibles en un canal del discrctc aumenta linear con tiempo. La capacidad de transmitir la información puede ser especificada dando este índice de aumentar, el número de pedacitos por el segundo requerido para especificar el detalle señal usada. Ahora consideramos la fuente de información. Cómo es una fuente de información ser descrito matemáticamente, y cuánto información en pedacitos por el sec- ¿el ond se produce en una fuente dada? El punto en la edición principal es el efecto de conocimiento estadístico sobre la fuente en la reducción de la capacidad requerida Una teoría matemática de la comunicación del canal, por el uso de la codificación apropiada de la información. En tcleg- el raphy, por ejemplo, los mensajes que se transmitirán consiste en secuencias de letras. Estas secuencias, sin embargo, no son totalmente al azar. En general, forman oraciones y tienen la estructura estadística, por ejemplo, del inglés lish. La letra E ocurre más con frecuencia que Q, la secuencia TIS más con frecuencia que XI', el etc. La existencia de esta estructura permite uno a hacer un ahorro a tiempo (o la capacidad de canal) correctamente codificando el mes- secuencias sabias en secuencias de la señal. Esto se hace ya a un ex limitado tienda en telegrafía usando el símbolo más corto del canal, un punto, para más letra inglesa común E; mientras que forman arcos las letras infrecuentes, Q, X, 2, rcpre- sented por secuencias más largas de puntos y de rociadas. Esta idea todavía se lleva fomentar en ciertos códigos comerciales donde forman arcos las palabras y las frases comunes representado por cuatro o grupos del código de la cinco-letra con un ahorro considerable adentro tiempo medio. Los telegramas estandardizados del saludo y del aniversario ahora funcionando ampliar esto al punto de codificar una oración o dos en a relativamente poner en cortocircuito la secuencia de números. Podemos pensar en una fuente discreta como generación del mensaje, símbolo cerca símbolo. Elegirá símbolos sucesivos según ciertas probabilidades el depender, generalmente de opciones precedentes así como los símbolos particulares en la pregunta. Un sistema físico, o un modelo matemático de un sistema que produce tal secuencia de los símbolos gobernados por un sistema de probabilidades es sabido como un process.3 estocástico nosotros puede considerar una fuente discreta, allí delantero, a representado a.C. por un proceso estocástico. Inversamente, estocástico proceso que produce una secuencia discreta de los símbolos elegidos de un finito el sistema se puede considerar una fuente discreta. Esto incluirá los casos tales como: 1. Idiomas escritas naturales tales como inglés, alemán, chino. 2. Información continua fuentes que han sido hechas discretas por alguno cuantificar proceso. Por ejemplo, el discurso quantized de un PCM transmisor, o una señal quantized de la televisión. 3. Matemático casos donde definimos simplemente abstractly un estocástico proceso que genera una secuencia de símbolos. Los siguientes son exes amples de este último tipo de fuente. (a) Suponer que tenemos cinco letras A, B, C, D, E que se eligen cada uno con la probabilidad .2, opciones sucesivas que son independientes. Esto conduciría a una secuencia de la cual lo que sigue es un ejemplo típico. BDCBCECCCADCBDDAAECEEA ABBDAEECACEEBAEECBCEAD Esto fue construida con el uso de una tabla de numbers.4 al azar un considerar, por ejemplo, S. Chandrasekhar, “problemas de Stachastic en la física y la astronomía, ” Rcuicwso ModernPlrysics, V. 15, no 1, el enero de 1943, P. 1. 4 Ken d toda y Smith, las “tablas del muestreo al azar numera,” Cambridge, 1939. C.E. Shannon (b) Con las mismas cinco letras dejar las probabilidades ser .4, .l, .2, .2, .l respectivamente, con las opciones sucesivas independientes. Un típico el mensaje de esta fuente es entonces: AAACDCBDCEAADADACEDA EADCABEDADDCECAAAAAD (c) A se obtiene una estructura más complicada si son los símbolos sucesivos no elegido independientemente solamente sus probabilidades dependen de preced- letras del ing. En el caso más simple de este tipo una opción depende solamente en la letra precedente y no en unas antes {sombrero. El estadístico la estructura se puede entonces describir por un sistema de probabilidades de la transición el pi (j), la probabilidad que letra i es por carta J. seguido. En corta la gama de i en cubitos y de j sobre todos los símbolos posibles. Un segundo cquiv- la manera alent de especificar la estructura es dar el prob- del “digram” capacidades p (i, j), es decir, la frecuencia relativa del digram i J. poner letras a las frecuencias p (i), (la probabilidad de la letra i), la transición las probabilidades pi (j) y las probabilidades p (i, j) del digram se relacionan cerca los fórmulas siguientes. PC4 = PCi 7, j) = 7 P (j) 4 = T P (j> Pi (4 P (i9.d = PCi) PiW 7 pi (i) = 7 PC4 = z P (i, j) = 1. Como un ejemplo específico supone allí las letras A, B, C del arco tres con el prob- tablas de la capacidad: ; B$+ O B++ i B 2~ 27 0 c+ Z.& aire T& de j c x27 C; da de s Un mensaje típico de esta fuente es el siguiente: ABBABABABABABABBBABBBBBAB ABABABABBBACACABBABBBBABB ABACBBBABA El aumento siguiente en complejidad implicaría frecuencias del trigram pero no más. La opción de una letra dependería de preceder dos letras pero no en el mensaje antes que señalan. Un sistema de tri frecuencias p (i, j, k) del gramo o equivalente un sistema de prob- de la transición Una teoría matemática de la comunicación el pii de las capacidades sería requerido. Continuación en este ob- de la manera una los tains sucesivamente complicaron más procesos estocásticos. En caso general del n-gramo un sistema de las probabilidades p del n-gramo (ir, il. s., &) o de las probabilidades pi de la transición, IX,… , i, -, (el iJ se requiere a especificar la estructura estadística. (d) Los procesos estocásticos pueden también ser definidos que producen un con- del texto el sisting de una secuencia de “palabras.” Suponer que hay cinco letras A, B, C, D, probabilidades: E y 16 “redacta” en la lengua con asociado .lO A .04 ADEB .05 ADEE . Ol BADD .16 BEBE .04 CAMA .02 BEED .05 CA .ll CABED .05 CEED . LENGUADO de Og .04 PAPÁ .04 DEB .15 HECHO . Ol EAB .0.5 EE Suponer que las “palabras sucesivas” están elegidas independientemente separado por un espacio. Un mensaje típico pudo ser: y ser DAB EE UN DEB BEBE DEL DEB ADEE ADEE EE DEL HECHO DE BEBE BEBEBEBEADEEBEDDEEDDEEDCEEDADEEADEED TRASPASAR EL HECHO ADEB DEL LENGUADO DE LA CAMA DE BEBE CABED BEBE Si todas las palabras están de longitud finita este proceso es equivalente a uno del tipo precedente, pero de la descripción puede ser más simple en términos de la estructura y de las probabilidades de la palabra. Podemos también generalizar aquí e introducir las probabilidades de la transición entre las palabras, el etc. Estas idiomas artificiales son útiles en construir problemas simples y ejemplos para ilustrar varias posibilidades. Podemos también aproximar a a lengua natural por medio de una serie de idiomas artificiales simples. la aproximación de la cero-orden es obtenida eligiendo todas las letras con igual probabilidad e independientemente. Se obtiene la aproximación de primer orden eligiendo letras sucesivas independientemente pero cada letra que tiene la misma probabilidad que hace en el language.6 natural así, en el primero pedir la aproximación al inglés, E se elige con la probabilidad .12 (su fre- el quency en inglés normal) y W con la probabilidad .02, pero allí está no adentro fluence entre las letras adyacentes y ninguna tendencia de formar preferido digrams tales como TIT, ED, etc. En la aproximación second-order, digram se introduce la estructura. Después de que se elija una letra, la siguiente se elige adentro acuerdo con las frecuencias con las cuales las varias letras siguen primer uno. Esto requiere una tabla de las frecuencias pi (j) del digram. En el tercero se introduce la aproximación de la orden, estructura del trigram. Se elige cada letra con las probabilidades que dependen de las dos letras que preceden. Las frecuencias de la letra 6, del digram y del trigram se dan en “secreto y urgente” por Fletcher Pratt, la cinta azul reserva 1939. Las frecuencias de la palabra se tabulan en la frecuencia de LRelative del `de los sonidos ingleses del discurso,” G. Dewey, prensa de la universidad de Harvard, 1923. C.E. Shannon 3. SERIE DE T~IE DE APROXIMACIONES AL INGLÉS Para dar una idea visual de cómo esta serie de procesos acerca a una lengua, las secuencias típicas en las aproximaciones al inglés se han construido y se dan abajo. En todos los casos hemos asumido 27 un símbolo “alfabeto,” las 26 letras y un espacio. 1. Cero-orden aproximación (independiente de los símbolos y equi-probable). XFOML RXKHR JFF JU J ZLPWCFWKCY J FFJEYVKCQSGXYD QI' AAMKBZAACIBZLHJQD 2. Aproximación de primer orden (independiente de los símbolos pero con frecuencias del inglés texto). TH EEI DEL EU LL NBNESEBYA DE OCR0 HLI RGWR NMIELWIS ALHENH' ITPA OOBTTVA NAH BRL 3. Aproximación Second-order (estructura del digram como en inglés). EN EL IE ANTSOUTINYS SON ST DE T INCTORE SEAN S DEAMY ACHIN D ILONASIVE TUCOOWE EN TEASONARE FUSO ANDY TOBE SEACE CTISBE DE TIZIN 4. Aproximación Third-order (estructura del trigram como en inglés), EN NINGÚN SUERO CRATICT FROURE BIRS GROCID DEL LAT DE IST PONDENOME DE DEMONSTURES DEL REPTAGIN ES REGOACTIONA DE CRE 5. De primer orden Aproximación de la palabra. Más bien que continuar con tetra el gramo, *.*, estructura del Él-gramo es más fácil y mejor saltar en esto punto para redactar unidades. Aquí las palabras se eligen independientemente pero con sus frecuencias apropiadas. LA REPRESENTACIÓN Y ES RÁPIDO UNA BUEN CONVENIENTE O DIVERSO NATURAL VENIDA DE LA PODER AQUÍ ÉL LA A ADENTRO VINO AL GRIS EXPERTO VIENEN A LA PIEL NISHES QUE LA LÍNEA MENSAJE TENÍA SER ÉSTAS. 6. Aproximación Second-Order de la palabra. El probabil- de la transición de la palabra los ities están correctos pero no hay otra estructura incluida. EL PRINCIPAL Y EN ATAQUE FRONTAL CONTRA UN INGLÉS ESCRITOR QUE ES EL CARÁCTER DE ESTE PUNTO POR LO TANTO OTRO MÉTODO PARA LAS LETRAS QUE LA ÉPOCA DEL WHO DIJO SIEMPRE EL PROBLEMA PARA UN INESPERADO La semejanza al texto del inglés corriente aumenta absolutamente perceptiblemente en cada uno de los pasos antedichos. Observar que estas muestras tienen razonablemente bueno estructurar hacia fuera alrededor dos veces a la gama que considerado en su construcción. Así en (3) el proceso estadístico asegura el texto razonable para la secuencia two-letter, pero las secuencias de la cuatro-letra de la poder de la muestra caberte generalmente en buenas oraciones. En (6) secuencias de cuatro o más Una teoría matemática de la comunicación las palabras se pueden poner fácilmente en oraciones sin inusual o filtrar con- structions. La secuencia particular ataque de diez palabras “contra un inglés escritor que el carácter de esto” es en absoluto desrazonable. Aparece entonces que un proceso estocástico suficientemente complejo dará un satisfactorio representación de una fuente discreta. Las primeras dos muestras fueron construidas por el uso de un libro de al azar números conjuntamente con (por ejemplo 2) una tabla de las frecuencias de la letra. Este método se pudo haber continuado para (3), (4), y (s), desde digram, trigram, y arco de las tablas de la frecuencia de la palabra disponible, pero un equivalente más simple el método fue utilizado. Para construir (3) por ejemplo, uno abre un libro en funcionó el dom y selecciona una letra al azar en la página. Se registra esta letra. El libro entonces se abre en otra página y uno lee hasta que es esta letra encontrado. La letra que tiene éxito entonces se registra. El dar vuelta a otro paginar esta segunda letra se busca para y la letra que tiene éxito registrada, etc. Un proceso similar fue utilizado para (4), (s), y (6). Sería intercst- ing si otras aproximaciones podrían ser construidas, solamente el trabajo implicado llega a ser enorme en la etapa siguiente. 4. REPRESENTACIÓN DE GRAIWCAL DE UN PROCESO DE MARKOFP ' Procesos estocásticos del tipo descrito sobre mathe- sabido arco matically como procesos discretos de Markoff y se han estudiado extensivamente adentro el literature.6 el caso general puede ser descrito como sigue: Existen a número finito de “estados posibles” de un sistema; 5' 1, SC. , S. En el tion del addi- hay un sistema de probabilidades de la transición; Cerdo) la probabilidad que si el sistema está en el silicio del estado que irá después a indicar Sj. Para hacer este Markoff proceso en una fuente de información que necesitamos solamente. asumir que una letra es favorable duced para cada transición a partir de un estado a otro. Los estados quieren el corre- spond al “residuo de la influencia” de letras precedentes. La situación se puede representar gráficamente según las indicaciones de cerdos. 3, 4 y 5. Los “estados” son los puntos de la ensambladura en el gráfico y las probabilidades y las letras produjeron para un arco de la transición dado al lado de la línea correspondiente. El cuadro 3 está por el ejemplo B en la sección 2, mientras que el higo 4 corresponde a ejemplo C. En el higo 3 hay solamente un estado puesto que son las letras sucesivas independiente. En el higo 4 son tantos estados como letras. Si un trigram el ejemplo fue construido allí a.C. a lo más el corresponder de los estados lz2 a los pares posibles de letras que preceden el que está que es elegido. Cuadro 5 es un gráfico para el caso de la estructura de la palabra en el ejemplo D. Aquí S corresponde al símbolo del “espacio”. 6 para un tratamiento detallado ver M. Frechet, “los arbitraires de los lonctions del DES de los métodos. Theo& ¿fini d' C del nombre del cas d' un del Ic de los dans del chaine del en del DES Cn6nements? possibles del ats.” París, Gauthier- Villars, 1938. C.E. Shannon 5. FUENTES ERGÓDICAS Y MEZCLADAS Como hemos indicado sobre una fuente discreta para nuestros propósitos podemos ser con- sidered para ser representado por un proceso de Markoff. Entre el discreto posible Los procesos de Markoff allí son un grupo con las características especiales de la significación adentro E . I Gráfico del higo 3-A que corresponde a la fuente en ejemplo 1). & B C AA .a 2 5 .5 B C B .4 5 . I Gráfico del higo 4-A que corresponde a la fuente en el ejemplo C. Higo. Gráfico del S-A que corresponde a la fuente en el ejemplo D. teoría de comunicación. Esta clase especial consiste en el proc- “ergódico” los esses y nosotros llamaremos las fuentes correspondientes las fuentes ergódicas. Aunque la definición de a.rigorous de un proceso ergódico está algo implicada, el general la idea es simple. En un proceso ergódico cada secuencia produjo por el proc- Una teoría matemática de la comunicación 17 los ess están iguales en características estadísticas, así las frecuencias de la letra, frecuencias del digram, etc., obtenidos de voluntad particular de las secuencias, como las longitudes de las secuencias aumentan, acercan a independiente definida de los límites de la secuencia particular. Esto no es realmente verdad de cada secuencia pero fijar para cuál es falso tiene probabilidad cero. Áspero la característica ergódica significa homogeneidad estadística. Todos los ejemplos de las idiomas artificiales dadas arriba son ergódicos. Esto la característica se relaciona con la estructura del gráfico correspondiente. Si el gráfico, tiene las dos características siguientes' que el proceso correspondiente será ergódico: 1. El gráfico no consiste en dos partes aisladas A y B tales que es imposible ir de la ensambladura señala en la parte A a los puntos de la ensambladura adentro pieza B a lo largo de las líneas del gráfico en la dirección de flechas y también del im- posible ir de ensambladuras en la parte B. a las ensambladuras en la parte A. 2. Una serie cerrada de líneas en el gráfico con todas las flechas en las líneas el señalar en la misma orientación será llamado un “circuito.” La “longitud” de a el circuito es el número de líneas en él. Así en el higo 5 la serie BEBES es un circuito de la longitud 5. La segunda característica requerida es que el divisor común más grande de las longitudes de todos los circuitos en el gráfico sea uno. Si la primera condición está satisfecha solamente segunda violada teniendo el divisor común más grande igual al > de d; 1, las secuencias tiene cierto tipo de la estructura periódica. Las varias secuencias bajan en diversas clases de d cuáles son estadístico iguales aparte de una cambio del origen (es decir, que la letra en la secuencia se llama la letra 1). Por una cambio de a partir de la 0 hasta d -1 cualquier secuencia se puede hacer estadístico equivalente a cualquier otro. Un simple el ejemplo con d = 2 es el siguiente: Hay tres letras posibles a, b, C. Letra a se sigue con b o c con las probabilidades $ y $ de respec- tively. B o c es siempre por carta A. seguido. Así una secuencia típica es abacacacabacababacac Este tipo de situación no es de mucha importancia para nuestro trabajo. Si se viola la primera condición el gráfico se puede separar en un sistema de subgraphs que satisface la primera condición. Asumiremos eso la segunda condición también está satisfecha para cada subgraph. Tenemos en esto caso qué se puede llamar una fuente “mezclada” compuesta de un número de puro componentes. Los componentes corresponden a los varios subgraphs. Si Ll, Lz, La. +. son las fuentes componentes que podemos escribir L = PlLl - p& de I-PJ2 f; - I' -' donde está la probabilidad el pi de la fuente componente LC. 7These son términos del restatementsin del gráfico de las condiciones dadas en & amolar. C.E. Shannon La situación representada es físicamente ésta: Hay vario d& alquiler LI de las fuentes, Lz, L~, - el sewhich es cada uno de la estructura estadística homogénea (es decir, son ergódicas). El WC no sabe a priori que debe ser utilizado, pero una vez que la secuencia comience en un Li componente puro dado continúa el indcf- nitely según la estructura estadística de ese componente. Pues un ejemplo uno puede tomar dos de los procesos delined arriba y asumir pl = .2 y pz = .8. Una secuencia de la fuente mezclada L = .2 Ll+ .8 Lz ser obtenido eligiendo primer L1 o Lz con las probabilidades .2 y .8 y después de esta opción la generación de una secuencia del whichcvcr fue elegida. A menos que cuando se indica el contrario asumamos una fuente a.C. a crgodic. Esta asunción permite a uno identificar promedios a lo largo de una secuencia con promedios sobre el conjunto de las secuencias posibles (la probabilidad de un dis- crepancy que es cero). Por ejemplo la frecuencia relativa de la letra A en una secuencia infinita particular a.C., con la probabilidad una, igual a tu frecuencia relativa en el conjunto de secuencias. Si el pi es la probabilidad del estado i y de pi (j) la probabilidad de la transición a indicar j, después para el proceso a.C. a inmóvil él está claro que debe el pi satisfacer las condiciones del equilibrio: En el caso ergódico puede demostrado a.C. que con cualquier condición que comienza #V de las probabilidades Z el') de estar en el estado j después de símbolos de N, acerca al equi- valores del librium como N + 00. 6. OPCIÓN, INCERTIDUMBRE Y ENTROPÍA Hemos representado una fuente de información discreta como proceso de Markoff. Dehne del WC de la poder a la cantidad que medirá, en un cierto sentido, en cuánto la formación “es producida” por tal proceso, o mejor, en qué informa- de la tarifa ¿se produce el tion? Suponer que tenemos un sistema de los acontecimientos posibles que probabilidades de la ocurrencia son los pl, p2, * * *, p. Se saben estas probabilidades pero ése es todo lo que sabemos refiriéndose ocurrirá a qué acontecimiento. Podemos encontramos una medida de cuánto la “opción” está implicada en la selección del acontecimiento o de cómo es incierto somos ¿del resultado? Si hay tal medida, decir ZZ (banda, 122, *. *, p,), es razonable a los res mano de papel de ella las características siguientes: 1. ZZ si .be continuo en el pi. 2. Si todos los pi son iguales, el pi = k, entonces ZZ deben ser un aumento monotónico Una teoría matemática de la comunicación función de 12. Con acontecimientos igualmente probables hay más bien escogido, o un- certeza, cuando hay acontecimientos más posibles. 3. Si un bien escogido se analice en dos opciones sucesivas, el origina H debe ser la suma cargada de los valores individuales del H. el significado de esto se ilustra en el higo 6. En la izquierda tenemos tres posibilidades pl = 3, PZ = g, $3 = F. A la derecha que primero elegimos estar possibilitiesleach del tween dos con la probabilidad 4, y si ocurre el segundo hacer otra opción con las probabilidades $, 5. Los resultados finales tienen las mismas probabilidades que antes. Requerimos, en este caso especial, eso H (& 4, 3) = a ($, 3) + $ZZ ($, f) El coeficiente $ es porque ocurre esta segunda opción solamente mitad del tiempo. Higo 6-Decomposition de una opción a partir de tres posibilidades. En el apéndice II, se establece el resultado siguiente: TJzeorem 2: El único H que satisface las tres asunciones antedichas está de forma: donde está una constante K positiva. Este teorema, y las asunciones requeridas para su prueba, están de ninguna manera necesario para la actual teoría. Se da principalmente para prestar cierto plausi- bility a algunas de nuestras definiciones más últimas. La justificación verdadera del defi- del thcsc los nitions, sin embargo, residirán en sus implicaciones. Cantidades de la forma H = --Registro pi (de K las cantidades constantes de Z pi mekely a una opción de una unidad del juego de la medida) un papel central en teoría de información como medidas de información, de opción y de incertidumbre. La forma de II será reconocido tan que de la entropía como definido en ciertas formulaciones de estadístico mechanics8 donde está la probabilidad el pi de un sistema que está en la célula i de su fase espacio. U entonces es, por ejemplo, el U en el teorema famoso de ZZ de Boltzmann. Llamaremos H = - I: registro pi del pi la entropía del sistema de probabilidades *See, por ejemplo, R.C. Tolman, “principios de mecánicos estadísticos,” Oxford. Clarendon, 1938. 20 C.E. Shannon Pl, - * *, P* * si x es una variable chance escribimos U (X) para su entropía; así x no es una discusión de una función sino de una etiqueta para un número, al differen- tiate él de la opinión de ZZ (y), la entropía de la variable chance Y. La entropía en el caso de dos posibilidades con las probabilidades p y q = 1 - p, a saber H= - (PhzPf~~yQ?) se traza en el higo 7 en función del P. La cantidad ZZ tiene un número de properti& interesante; qué otro submarino stantiate él como medida razonable de opción o de información. Higo t--Entropía en el caso de dos posibilidades con las probabilidades p y (1 - p). 1. ZZ = 0 si y solamente si todos los pi pero uno son cero, éste que tiene unidad del valor. Así solamente cuando estamos seguros del resultado hace II desaparecen. Si no ZZ es positivo. 2. Para una n dada, ZZ es un máximo y un igual para registrar n cuando son todos los pi igual es decir, -1. Ésta es también intuitivo la situación más incierta. (IL> 3. Suponer que hay dos acontecimientos, x y y, en la pregunta con posibilidades de m para el primer y la n para el segundo. Dejar p (i, j) sea la probabilidad del empalme ocurrencia de i para el primer y de j para el segundo. La entropía del empalme el acontecimiento es H (x, y) = - Una teoría matemática de la comunicación mientras que H (x) = - B (y) = - PÁGINA del lg, PÁGINA 3 1% ly, 3. Se demuestra fácilmente eso con igualdad solamente si los acontecimientos son independientes (es decir, p (i, J) = p (i) PO')). La incertidumbre de un acontecimiento común es inferior o igual la suma de incertidumbres individuales. 4. Cualesquiera cambian hacia la igualación de la banda de las probabilidades, pz, - -. , p, aumentos ZZ. Así si < de la banda; PZ y nosotros aumentamos la banda, disminuyendo el pz un igual ascender de modo que banda y el pz sea más casi igual, entonces H aumente. Más generalmente, si realizamos algún “hacer un promedio” de la operación en el pi de la forma p: = pj del aij de C i donde el aij de c = el aij de c = 1, y todo el aij 2 0, entonces H aumenta (excepto en i i caso especial donde esta transformación asciende no más que un permuta- tion del pj con ZZ por supuesto restante iguales). 5. Suponer que hay dos acontecimientos chance x y y como en 3, no no necesariamente independiente. Para cualquier valor particular i que x pueda asumir hay un con- la probabilidad pi (j) del ditional esa y tiene el valor J. Esto se da cerca PC4 .i) Pd.9 = c p(i, j> * i Definimos la entropía condicional de y, Zi=(y) como el promedio de la entropía de y para el valor del eacli de x, cargado según la probabilidad de conseguir ese X. particular. Eso es my> = - c i, i PÁGINA, j> El 1% pi (j). Esta cantidad mide cómo es incierto estamos de y en el promedio cuando nosotros saber que X. que substituye el valor del cerdo) que obtenemos Hertzio (y) = - PÁGINA de C, j> PC del registro, j> + PC DE C; , j> PÁGINA del registro C, j) ii ij i = H (x, y) - ZZ (x) o wx, y> = H (x) + fIz (y) C.E. Shannon La incertidumbre (o la entropía) del acontecimiento común 2, y es la incertidumbre de x más la incertidumbre de y cuando se sabe x. 6. A partir del 3 y de 5 tenemos H (x) + H (y) 2 ah, y) = H (x) + hertzio (y) Por lo tanto H (Y) 2 ZJzb) La incertidumbre de y nunca es aumentada en el knowleclge del X. A.C. de- arrugado a menos que x y y sean acontecimientos independientes, en este caso no se cambia. 7. Trr~ ENTKOPY de una FUENTE de INFORMACIÓN Considerar una fuente discreta del tipo finito del estado considerado arriba. Para cada estado posible allí seré un sistema de las probabilidades pi (j) de favorable ducing los varios símbolos posibles J. Así hay una entropía ZZi para cada estado. La entropía de la fuente será clelincd como el promedio de este Zli cargado de acuerdo con la probabilidad del occurrcncc del estados en la pregunta: II = C pi ZZi Del = registro pi (j) 1% PiPi Ésta es la entropía de la fuente por el símbolo del texto. Si el proc- de Markoff los ess están procediendo en una tarifa definida del tiempo allí son también una entropía por segundo Jilii 7 de ZZ' = el wherefi es la frecuencia media (ocurrencias por segundo) del estado i. Claramente II' = ntIZ donde está el número el IU medio de los símbolos producidos por segundo. ZZ o II' mide la cantidad de información generada por la fuente por símbolo o por segundo. Si la base logarítmica es 2, representarán pedacitos por símbolo o por segundo. Si los símbolos sucesivos son entonces ZZ independientes están simplemente - el registro pi de z pi donde está la probabilidad el pi del símbolo i. suponer que en este caso consideramos a desea el mensaje de los símbolos de N. Contendrá con alta probabilidad alrededor ocurrencias del plN del primer símbolo, ocurrencias de PzN del segundo, etc. Por lo tanto la probabilidad de este mensaje particular estará áspero p = pf~NP; =N. .pbnN o Una teoría matemática de la comunicación registro p G N c p; registro pi i ZZ es así aproximadamente el logaritmo de la probabilidad recíproca de a la secuencia larga típica se dividió por el número de símbolos en la secuencia. Los mismos asimientos del resultado para cualquier fuente. Indicó que tenemos más exacto (véase Apéndice III) : Theorem3: Dado cualquier > de e; > 0 y 6; 0, podemos encontrar no tales que los quences del SE de Lhe de cualquier longitud N 2 ninguna caída en dos clases: 1. Un sistema que probabilidad total es menos que el E. 2. El resto, todos los que miembros tienen satisfacción de las probabilidades desigualdad registro---IIN p--' < Es Es decir estamos casi seguros de tener registro pi de N muy cerca de II cuando N es grande. Un resultado de cerca relacionado se ocupa del número de secuencias de vario probabilidades. Considerar otra vez las secuencias de la longitud N y dejarlas ser arreglado en orden de la probabilidad que disminuye. Nosotros dehne s (q) a ser número que debemos tomar de este sistema comenzando con el más probable adentro orden para acumular una probabilidad total q para ésos tomados. Teorema 4: Registro n (rl) de Lim = ZZ N-tm N cuando q no iguala 0 o 1. Podemos interpretar el registro IZ (~) como el número de los pedacitos requeridos especificar secuencia cuando consideramos solamente las secuencias más probables con un total Entonces * ¡probabilidad Q. l?!.!?! @ 1s el número de pedacitos por el símbolo para N especificación. El teorema dice que para N grande ésta será independiente de Q y del igual a ZZ. El índice de crecimiento del logaritmo del número de las secuencias razonablemente probables son dadas por ZZ, sin importar nuestro intcrpreta- tion “razonablemente del probable.” Debido a estos resultados, que se prueban en el apéndice III, es posible para que la mayoría de los propósitos traten las secuencias largas como si había 21fN justos de ellas, cada uno con una probabilidad 2 “N. C.E. Shannon Los dos teoremas siguientes demuestran que ZZ e II' se pueden determinar por límite operaciones del ing directamente de la estadística de las secuencias del mensaje, sin referencia a los estados y a las probabilidades de la transición entre los estados. Theorem5: Dejar p (BI) sea la probabilidad de una secuencia i3i de símbolos de la fuente. Dejado GN = -; F Pm> registro p (l&) donde está la suma sobre todas las secuencias B; contener símbolos de N. Entonces GN es una función el disminuir monotónica de N y Lim GN = ZZ. N--a, Theorem6: Dejar p (O< , Sj) sea la probabilidad de la secuencia Ui seguida cerca símbolo Sj y PSI (Sj) = p (8i, Sj) /p (ZJJ sea la probabilidad condicional de Sj después del BI. Dejado FN = - C P (a.C., sj> foi del registro (Sj) i.i donde está la suma sobre todo bloquea el BI de los símbolos y del excedente de N -1 todos los símbolos Sj . Entonces el FN es una función que disminuye monotónica de N, ZJN = NGN - (N -1) CN-~, y Lim FN = ZZ. Thzse*results se deriva en el apéndice III. Demuestran a eso una serie de las aproximaciones a ZZ pueden ser obtenidas considerando solamente el estadístico estructura de las secuencias que extienden sobre 1, 2. - símbolos de una N. El PN es una aproximación mejor. De hecho el PN es la entropía del approxi- de la orden de Nlh mation a la fuente del tipo discutido arriba. Si allí el arco ningunas influencias estadísticas que amplían el excedente más que los símbolos de N, de que es si el condicional la probabilidad del símbolo siguiente que sabe preceder (N -1) no es cambiado por un conocimiento de cualesquiera antes que, entonces ZJN = ZZ. El PN por supuesto está la entropía condicional del símbolo siguiente cuando (N -1) el preceder se saben unos, mientras que GN es la entropía por el símbolo de bloques de los símbolos de N. El cociente de la entropía de una fuente al valor máximo que podría tener mientras que todavía está restringido a los mismos símbolos será llamado su enlropy relaiive. Ésta es la compresión máxima posible cuando codificamos en igual alfabeto. Uno menos la entropía relativa es el redwdancy. El redun- Una teoría matemática de la comunicación el dancy del inglés corriente, no en vista de mayores distancias del excedente estadístico de la estructura que cerca de ocho letras es el áspero 50%. Esto significa eso cuando escribimos la mitad inglesa de lo que escribimos somos determinados por la estructura de la lengua y la mitad se elige libremente. El cuadro el 50% fue encontrado por varios métodos independientes que todos dieron a resultados en esta vecindad. Uno es por el cálculo de la entropía de las aproximaciones al inglés. Un segundo el método es suprimir cierta fracción de las letras de una muestra del texto inglés y después dejó a alguien procurar restaurarlas. Si pueden estar re- almacenado cuando se suprimen los 50% la redundancia debe ser el grcatcr que 500/. Un tercer método depende de ciertos resultados sabidos en criptografía. Dos extremos de la redundancia en prosa inglesa son representados por básico Inglés y por libro “estela de James Joyces' de Finigans.” El inglés básico el vocabulario se limita a 850 palabras y la redundancia es muy alta. Esto se refleja en la extensión que ocurre cuando un paso se traduce a Inglés básico. Joyce por otra parte agranda el vocabulario y está alegado para alcanzar una compresión del contenido semántico. La redundancia de una lengua se relaciona con la existencia del crucigrama rompecabezas. Si la redundancia es cero cualquier secuencia de letras es una razonable el texto en la lengua y cualquier arsenal de dos dimensiones de letras forma un rompecabezas cruzado de la palabra. Si la redundancia es demasiado alta la lengua impone también muchos apremios para que crucigramas grandes sean posibles. Un más de- el análisis atado demuestra que si asumimos los apremios impuestos por la lengua está de una naturaleza algo caótica y al azar, crucigramas grandes ser apenas posible cuando la redundancia es el 50%. Si la redundancia es el 33%, los crucigramas tridimensionales deben ser posibles, etc. 8. REPRESENTACIÓN DE LAS OPERACIONES DE LA CODIFICACIÓN Y EL DESCIFRAR Tenemos todavía representar matemáticamente las operaciones realizadas cerca el transmisor y el receptor en la codificación y descifrar de la información. Cualquiera de éstos será llamada un transductor discreto. La entrada a el transductor es una secuencia de los símbolos de la entrada y de su salida una secuencia de hacia fuera poner los símbolos. El transductor puede tener una memoria interna de modo que su la salida depende no sólo del actual símbolo de la entrada pero también del pasado historia. Asumimos que la memoria interna es finita, es decir existe un número finito m de los estados posibles del transductor y de ése su salida es una función del estado actual y del actual símbolo de la entrada. El siguiente el estado será una segunda función de estas dos cantidades. Así un transductor puede ser descrito por dos funciones: C.E. Shannon donde: x, es el símbolo de la entrada de jt.lh, (Y, es el estado del transductor cuando se introduce el símbolo de la entrada del ftfh, y” es el símbolo de la salida (o secuencia de los símbolos de la salida) producida cuando se introduce x, si es el estado (Y. Si los símbolos de la salida de una poder del transductor identificada a.C. con la entrada de Lhc los símbolos de un segundo, pueden ser conectados en tándem y el resultado está también un transductor. Si existe un segundo transductor que funcione encendido la salida puesto del primer y recupera la entrada original, el primer transductor será llamado no singular y el segundo será llamado su lo contrario. Teorema 7: La salida de un transductor finito del estado conducido por un estado finito la fuente estadística es una fuente estadística del estado finito, con entropía (por unidad tiempo) inferior o igual el de la entrada. Si el transductor está no singular forman arcos igual. Dejado (reprcscnt de Y el estado de la fuente, de la cual produce una secuencia símbolos XI; y dejar /3 sea el estado del transductor, que produce, en tu salida, bloques del yj de los símbolos. El sistema combinado puede ser representado por el “producto indicar el espacio” de los pares (a, p). Dos puntos en el espacio, (en, pi) anuncio ((112Pz), son conectados por una línea si la calidad de copia puede producir un x que cambia /31 a /3z, y esta línea se da la probabilidad de ese x en este caso. La línea se etiqueta con el bloque de los símbolos del yi producidos por el transductor. La entropía de la salida se puede calcular como la suma cargada sobre estados. Si sumamos primero en 0 por cada uno términos que resultan somos inferior o igual el término correspondiente para 01, por lo tanto la entropía no se aumenta. Si el transporte el ducer es no singular dejó su salida conectada a.C. con el transductor inverso. Si ZZ: , ZZ: y ZZ; forman arcos las entropías de la salida de 1 él fuente, la primera y segundos transductores respectivamente, entonces ZZ: 2 ZZ: 2 ZZ; = ZZ: y por lo tanto n: = zi: . Suponer que tenemos un sistema de apremios en las secuencias posibles del tipo cuál se puede representar por un gráfico linear como en el higo 2. Si probabilidades p$' fueron asignados a las varias líneas que conectaban el statej bajo del estado i que esto se convirtió en una fuente. Hay una asignación particular que maximiza entropía que resulta (véase el apéndice IV). Theorem8: Dejar el sistema de los apremios considerados como canal tener a capacidad C. Si asignamos donde está la duración Eiy del símbolo del sfh que conduce del estado i al estado, j y el BI satisfacen entonces ZZ es maximizado e igual a la C. Una teoría matemática de la comunicación Por la asignación apropiada de las probabilidades de la transición la entropía del sym- los bols en un canal se pueden maximizar en la capacidad de canal. 9. TEOREMA DE TIIE FUNDAIVIENTAL PARA UN CIIAWEL SILENCIOSO. Ahora justificaremos nuestra interpretación de ZZ como el índice de gcncrating *** información probando que ZZ determina la capacidad de canal requerida con la mayoría de la codificación eficiente. Theorent9: Dejar una fuente tener la entropía ZZ (pedacitos por símbolo) y un canal tener una capacidad C (pedacitos por segundo). Entonces es posible codificar la salida de la fuente a fin de transmitir en la tarifa media i - símbolos de E por segundo sobre el canal donde está arbitrariamente sinall c. II no es posible transmitir en una tarifa media 2 mayor que II * La parte inversa del teorema, ese g no puede excedido a.C., puede ser probado observando que la entropía del canal entrado por segundo es igual a el de la fuente, puesto que el transmisor debe ser noksingular, y también esta entropía no puede exceder la capacidad de canal. < por lo tanto de ZZ'; C y número de símbolos por < del segundo = de /ZZ de ZZ'; C/N. La primera parte del teorema será probada de dos diversas maneras. el primer método es considerar el sistema de todos los sequencds de los símbolos de N producidos por la fuente. Para N grande podemos dividir éstos en dos grupos, uno que contiene menos de 2 (“+ “miembros del jN y el segundo que contiene menos que los miembros 2RN (donde está el logaritmo R del número de diversos símbolos) y que tiene a probabilidad total menos que el P. Como N aumenta 11 y el acercamiento cero de /J. el número de señales de la duración T en el canal es los 2' CBES mayor que' T con o pequeño cuando T es grande. Si elegimos entonces habrá un número del suflkicnt de secuencias de los símbolos del canal para el alto grupo de la probabilidad cuando N y T son suficientemente grandes (sin embargo x pequeño) y también algunos adicionales. El alto grupo de la probabilidad es cifrado en arbitrario a una forma en este sistema. Las secuencias restantes son representados por secuencias más grandes, comenzando y terminando con una de secuencias no usadas para el alto grupo de la probabilidad. Esta secuencia especial actos como señal del comienzo y de parada para un diverso código. Entre un sufkient se da un plazo la hora de dar bastantes diversas secuencias para todos los mensajes bajos de la probabilidad de Lhc. Esto requerirá C.E. Shannon donde está pequeño Q. El índice malo de la transmisión en símbolos del mensaje por entonces ser en segundo lugar mayor que [(1 - fj); + 6; I' = [(1 - a> g + 1) + 6 (g + PJJ-' Como N aumenta 6, X y el acercamiento cero de p y los acercamientos g de la tarifa, Otro método de realizar esta codificación y de probar el teorema puede describirte como sigue: Arreglar los mensajes de la longitud N en la orden de la probabilidad del ing del dccreas- y suponerlos que son sus probabilidades. PA del pz 2 del pi 2. 2 pn. n-1 Dejar P, = F pi; ése es P. es la probabilidad acumulativa hasta, pero no m& ding, p. Primero codificamos en un sistema binario. El código binario para el mensaje s es obtenido ampliando P, como número binario. La extensión se realiza al ns. lugares, donde wz.is la satisfacción del número entero: Así los mensajes de la alta probabilidad son representados por códigos cortos y los de la probabilidad baja por códigos largos. De estas desigualdades tenemos El código para el P. diferenciará del al \ el tener éxito en uno o más de su ¿? lugares n8, puesto que todos los pi restantes son por lo menos & más grande y su binario las extensiones por lo tanto diferencian en el primer fti2, lugares. Por lo tanto todos los códigos son diferentes y es posible recuperar el mensaje de su código. Si las secuencias del canal no son ya secuencias de dígitos binarios, pueden ser números binarios atribuidos en una manera arbitraria y el código binario así traducido a las señales convenientes para el canal. El número medio II' de los dígitos binarios usados por símbolo del mes- original el sabio se estima fácilmente. El WC tiene ¿II' = f z?? t, P. Pero, ; z log2 f (8) < de P8 5 $%p*; ;. (1 + log23. y por lo tanto, Una teoría matemática de la comunicación < del ~~; ' < II; - I GN $ Como N aumenta los acercamientos 11 de GN, la entropía de la fuente y un' ap- proaches 11. Vemos de esto que el incfliciency en la codificación, cuando solamente un finito retrasa de Los símbolos de N se utilizan, no necesitan ser $ mayor que más la diferencia en medio la entropía verdadera Ii y la entropía GN calculaban para las secuencias de la longitud N. Exceso del tiempo de los por ciento necesario sobre el ideal es por lo tanto menos que Este método de codificación es substancialmente igual que un inde- encontrado ¿penclcntly por R.M. Fano? Su método es arreglar los mensajes de la longitud N en orden de la probabilidad que disminuye. Dividir esta serie en dos grupos de como probabilidad casi igual como sea posible. Si el mensaje está en el primer grupo su primer dígito binario será 0, si no 1. Dividen a los grupos semejantemente en los subconjuntos de la probabilidad casi igual y el subconjunto particular determina el segundo dígito binario. Se continúa este proceso hasta que cada subconjunto contiene solamente un mensaje. Se ve fácilmente que aparte de las diferencias de menor importancia (GEN erally en el dígito pasado) esto asciende a la misma cosa que la aritmética proceso descrito arriba. 10. DISCUSIÓN Y EJEMPLOS Para obtener la transferencia máxima de la energía de un generador a una carga deber en general introducir un transformador para el generador según lo visto de la carga tiene la resistencia de la carga. La situación aquí es áspero anal ogous. El transductor que hace la codificación debe emparejar la fuente al canal en un sentido estadístico. La fuente según lo visto del canal a través del transductor debe tener la misma estructura estadística que fuente que maximiza la entropía en el canal. El contenido de El teorema 9 es que, aunque un fósforo exacto no es en general posible, el WC puede aproximarlo tan de cerca como deseado. El cociente del índice real de la misión del transporte a la capacidad C se puede llamar el eflicicncy del sistema de codificación. Éste es por supuesto igual al cociente de la entropía real del canal símbolos a la entropía posible máxima. La codificación generalmente ideal o casi ideal requiere un largo retrasa en transmisor y receptor. En el caso silencioso que hemos sido considerando, la función principal de esto retrasa es permitir razonablemente bueno 0 informes técnicos no 65, el laboratorio de investigación de Electrofiics, M.I.T. C.E. Shannon el emparejar de probabilidades a las longitudes correspondientes de secuencias. Con a buen código el logaritmo de la probabilidad recíproca de un mensaje largo debe ser proporcional a la duración de la señal el corresponder, de hecho El 1% p' _ c T debe ser el Br pequeño todo pero una fracción pequeña de los mensajes largos. Si una fuente puede producir solamente un mensaje particular su entropía es cero, y no se requiere ningún canal. Por ejemplo, una máquina que computa fijada hasta calcular los dígitos sucesivos de a produce un sequcncc del dctinite sin chance el elemento. No se requiere ningún canal “transmite” esto a otro punto. Uno podía construir una segunda máquina para computar el mismo sequcncc en el punto. Sin embargo, esto puede ser impráctico. En tal caso poder del WC el cl~oose para no hacer caso de alguno o todo el WC estadístico del conocimiento tiene de fuente. Puede ser que consideremos los dígitos de R para ser una secuencia al azar en eso construimos un sistema capaz de enviar cualquier secuencia de dígitos. En a manera similar que podemos elegir para utilizar algo de nuestro conocimiento estadístico del inglés lish en construir un código, pero no todo de él. En tal caso nos consideramos la fuente con la entropía máxima conforme a las condiciones estadísticas desear conservar. La entropía de esta fuente determina la capacidad de canal cuál es necesario y suficiente. En el ejemplo de R la única información se conserva que todo el arco de los dígitos elegido del sistema 0, 1, 9. En el caso del inglés uno pudo desear no utilizar el posible del ahorro estadístico debido a las frecuencias de la letra, pero nada. La fuente máxima de la entropía entonces está la primera aproximación al inglés y a su entropía determina requerido capacidad de canal. Como un ejemplo simple de algunos de estos resultados considera una fuente que produce una secuencia de las letras elegidas entre de A, 11, C, D con el prob- capacidades 4, 4, $, i, símbolos sucesivos que son elegidos indcpcndently. Nosotros tener II = - (registro $ de $ - +; registro 4 + 8 registro +> = 2 pedacitos por símbolo. Así podemos aproximar un sistema de codificación para codificar mensajes de esto fuente en dígitos binarios con un promedio del dígito binario de z por símbolo. En este caso podemos alcanzar realmente el valor límite por el código siguiente (obtenido por el método de la segunda prueba del teorema 9): Una teoría matemática de la comunicación Un 0 l3 10 c 110 D 111 El número medio de los dígitos binarios usados en la codificación de una secuencia del sym- de N los bols serán N ($ X 1 + $ X 2 + $ X 3) = - $N Se ve fácilmente que los dígitos binarios 0, 1 tienen probabilidades 3, i: ; el II para las secuencias cifradas es tan un pedacito por símbolo. Puesto que, en el promedio, el WC tiene p los símbolos binarios por letra original, las entropías sobre una base del tiempo son iguales. La entropía posible máxima para el sistema original es el registro 4 = 2, ocurriendo cuando el li, 13, C, D tiene probabilidades f, 4, 3, 1. Hcncc la entropía relativa es G. Podemos traducir las secuencias binarias al sistema original de símbolos en a dos--uno a base por la tabla siguiente: Al 00 01 U' 10 C' 11 D' Este proceso doble entonces codifica el mensaje original en los mismos símbolos pero con un cociente medio S. de la compresión. Pues un segundo ejemplo considera una fuente que produzca una secuencia de las a y u con la probabilidad p para A y Q para el U. Si < de p; < q que tenemos II = - registro p” (1 - p> `-” = - `p del registro p (1 de p - py-p) En tal caso uno puede construir una codificación bastante buena del mensaje en a 0, 1 canal enviando una secuencia especial, opinión 0000, para el infrecuente símbolo n y entonces una secuencia que indica el nu& er de los b que lo siguen. Esto se podía indicar por la representación binaria con todos los números con- taining la secuencia especial suprimió. Todos los números hasta 16 se representan como de costumbre; 16 es representado por el número binario siguiente después de 16 que lo hace no contener cuatro ceros, a saber 17 = 10001, etc. Puede ser demostrado que como p - + 0 que la codificación acerca a ideal proporcionó la longitud de la secuencia especial se ajusta correctamente. C.E. Shannon PARTE II: EL CANAL DISCRETO CON RUIDO 11. REPRESENTACIÓN DE UN CANAL RUIDOSO DE DISCRIXTIZ Ahora consideramos el caso durante donde la señal es perturbada por el ruido transmisión o en uno o el otro de los terminales. Esto significa que la señal recibida no es necesariamente igual que ésa enviada por el transporte mitter. Dos casos pueden ser distinguidos. Si una señal transmitida particular produce siempre igual señal recibida, es decir la señal recibida es una función definida de la señal transmitida, entonces el efecto se puede llamar distorsión. Si esta función tiene lo contrario--el producir transmitido de las señales de no dos la misma señal-distorsión recibida se puede corregir, por lo menos en principio, cerca simplemente ejecución de la operación funcional inversa en la señal recibida. El caso del interés aquí es el en las cuales la señal no experimenta siempre el mismo cambio en la transmisión. En este caso podemos asumir recibido señalar E para ser una función de la señal transmitida 5' y de una segunda variable, el ruido N. E = f (S, N) El ruido se considera ser una variable chance tan justo que el mensaje era sobre. En general puede ser representado por un proceso estocástico conveniente. El tipo más general de canal discreto ruidoso que consideraremos es un ization general del canal silencioso del estado finito descrito previamente. Nosotros asumir un número finito de estados y un sistema de probabilidades Pa.dA3. ¡Ésta es la probabilidad, si el canal está en el estado a! y el símbolo i es transporte mitted, ese símbolo j será recibido y el canal a la izquierda en el estado P. Así (Y y /3 se extienden sobre los estados posibles, i sobre las señales transmitidas posibles y j sobre las señales recibidas posibles. En el caso donde sym- sucesivo *** los bols son perturbados independientemente por el ruido allí son solamente un estado, y el canal es descrito por el sistema de las probabilidades pi (j), la capacidad de la transición del prob- del símbolo transmitido i que es recibido como J. Si un canal ruidoso es alimentado por una fuente hay dos procesos estadísticos en trabajo: la fuente y el ruido. Así hay un número de entropías eso puede ser calculado. Primero hay la entropía 11 (x) de la fuente o del la entrada al canal (éstos serán igual si el transmisor es no singular), la entropía de la salida del canal, es decir la señal recibida, será denotado por U (y). ¡En el caso silencioso I! (y) = N (x). La entropía común de la entrada y la salida serán 116~~). Finalmente hay entro- del condicional dos empanadas Ii, (y) e II& x), la entropía de la salida cuando se sabe la entrada e inversamente. Entre estas cantidades tenemos las relaciones H (x, y) = U (x) + II, (y) = H (y) + I$ (4 Una teoría matemática de la comunicación Todas estas entropías se pueden medir en un por-segundo o un por-símbolo base. 12. CAPACIDAD DE LA AMBIGÜEDAD Y DE CANAL Si el canal es ruidoso no es en general posible reconstruir el mensaje del inal del orig- o la señal transmitida con cerfainiyby ninguna operación en señal recibida E. Hay, sin embargo, maneras de transmitir la información cuáles son óptimos en ruido que combate. Éste es el problema que nosotros ahora considerar. Suponer que hay dos símbolos posibles 0 y 1, y estamos transmitiendo en un índice de 1000 símbolos por segundo con probabilidades p0 = p, = 3. Así nuestra fuente está produciendo la información en el índice de 1000 pedacitos por segundo. Dur- la transmisión del ing el ruido introduce errores para, en el promedio, recibir 1 en 100 incorrectamente (un 0 como 1, o 1 como 0). ¿Cuál es el índice de la transmisión de la información? Ciertamente menos de 1000 pedacitos por el segundo desde entonces el cerca de 1% de los símbolos recibidos ser incorrecto. Nuestro primer impulso pudo ser decir la tarifa es 990 pedacitos por el segundo, restando simplemente el número previsto de errores. Esto no es satisfactorio puesto que no puede considerar la carencia del recipiente del conocimiento de donde ocurren los errores. Podemos llevarlo a un extremo encajonar y suponer el ruido tan grande que los símbolos recibidos están enteramente independiente de los símbolos transmitidos. La probabilidad de recibir 1 es 3 lo que fue transmitida y semejantemente para 0. Entonces sobre la mitad del los símbolos recibidos son correcto debido a solo chance, y estaríamos dando el crédito del sistema para transmitir 500 pedacitos por segundo mientras que realmente no la información se está transmitiendo en todos. Igualmente “buena” transmisión ser obtenido dispensando con el canal enteramente y moviendo de un tirón a acuñar en el punto de recepción. Evidentemente la corrección apropiada a aplicarse a la cantidad de información se transmite la cantidad de esta información que falte en los res ceived la señal, o alternativomente la incertidumbre cuando hemos recibido a señal de qué fue enviada realmente. De nuestra discusión anterior de la entropía como una medida de incertidumbre él se parece razonable utilizar el condicional entropía del mensaje, sabiendo la señal recibida, como medida de esto información que falta. Ésta es de hecho la definición apropiada, pues veremos más adelante. Después de esta idea el índice de la transmisión real, R, sería ob- tained restando del índice de la producción (es decir, la entropía del fuente) el índice medio de la entropía condicional. La entropía condicional H& r), para la conveniencia, será llamado el equi- vocación. Mide la ambigüedad media de la señal recibida. C.E. Shannon En el ejemplo considerado arriba, si un 0 se recibe un prob- del posleriori la capacidad que un 0 fue transmitido es .99, y que un 1 fue transmitido es . Ol. Se invierten estas figuras si se recibe un 1. Por lo tanto H, (x) = registro 0.011 de -1.99log .99 + 0.01 = .081 pedacito/símbolo o 81 pedacitos por segundo. Podemos decir que el sistema está transmitiendo en una tarifa 1000 - 81 = 919 pedacitos por segundo. En el caso extremo donde está un 0 igualmente ser recibido probablemente como un 0 o 1 y semejantemente para 1, los bilities de un proba- del postcriori son 3, 3 y N, (x) = - registro de I+ + + 3 registro 41 = 1 pedacito por símbolo o 1000 pedacitos por segundo. El índice de la transmisión es entonces 0 como él deber ser. El teorema siguiente da una interpretación intuitiva directa del la ambigüedad y también sirve para justificarlo como el mcasurc apropiado único. Consideramos un sistema de comunicación y un dispositivo del observador (o auxiliar) quién pueden ver se envía qué y se recupera qué (con errores debido al ruido). Este observador observa los errores en el mensaje recuperado y transmite datos al excedente de recepción del punto un “canal de la corrección” para permitir al receptor corregir los errores. La situación se indica esquemáticamente en el higo 8. Tlzeorenz 10: Si el canal de la corrección tiene una capacidad igual a H, (x) es posible codificar tan los datos de la corrección en cuanto a enviarlo sobre este canal y corregir todos pero una fracción arbitrariamente pequeña E de los errores. ¿Esto no es posible si la capacidad de canal es menos que L? , (x). Áspero entonces, IIU (z) es la cantidad de información adicional que debe a.C. proveído por segundo en el punto de recepción para corregir el mensaje recibido. Para probar la primera parte, considerar las secuencias largas del mensaje recibido M' y mensaje original correspondiente M. Allí voluntad a.C. logarítmico Tll, (x) del m que habría podido razonablemente producir cada M'. Así tenemos T& , (x) dígitos binarios para enviar cada uno segundos de T. Esto puede ser hecha con la frecuencia de e de errores en un canal de la capacidad Ii, (r). La segunda parte puede ser probada observando, primera, de que para cualquier ocasión discreta variables x, y, z II& , 2) 2 II, kl9 El lado izquierdo se puede ampliar a la elasticidad I& (z) + I& /a (X) 2 112/h) K/44 2 m4 - II, (z) 2 II, (x) - H (z) Una teoría matemática de la comunicación Si identificamos z como la salida de la fuente, de y como la señal recibida y de z como la señal enviada sobre el canal de la corrección, entonces el lado derecho-hancl es la ambigüedad menos el índice de la transmisión sobre el canal de la corrección. Si la capacidad de este canal es menos que la ambigüedad el lado derecho será cero mayor que e IZ, el > 2 (del ~); 0. Pero ésta es la incertidumbre de qué fue enviada, sabiendo la señal recibida y la señal de la corrección. Si éste es cero mayor que la frecuencia de errores no puede estar arbitrariamente pequeño. Ejemplo: Suponer que los errores ocurren al azar en una secuencia de dígitos binarios: proba- bility p que un dígito es incorrecto y r] = 1 - p que correcto. Estos errores poder corregida a.C. si se sabe su posición. Así el canal de la corrección la necesidad envía solamente la información en cuanto a estas posiciones. Esto asciende al transporte DATOS DE LA CORRECCIÓN EL CORREGIR DEL RECEPTOR DEL TRANSMISOR DISPOSITIVO Cerdo. Diagrama del S-Diagrama esquemático de un sistema del corrcclion. el mitting de una fuente para la cual produce dígitos binarios con la probabilidad p 1 (correcto) y q para 0 (incorrecto). Este rcquircs un canal de la capacidad - [P el 1% ql de p + del registro de p cuál es la ambigüedad del sistema original. El índice de la transmisión R centímetro se escriba en dos otras formas debido a identidades conocidas arriba. Tenemos R = U (x) - II, (x) = 11 (y) - IL (y) = IzI (n) + II (y) - I-l (x, y). La primera expresión que definía se ha interpretado ya como la cantidad de la información envió menos la incertidumbre de qué fue enviada. El segundo meas- C.E. Shannon los ures la cantidad recibieron menos la parte de el que es debido al ruido. el tercero es la suma de las dos cantidades menos la entropía común y por lo tanto en un sentido está el número de pedacitos por el segundo común a los dos. Así los tres las expresiones tienen cierta significación intuitiva. La capacidad C de un canal ruidoso debe ser la tarifa posible máxima de la transmisión, es decir, la tarifa cuando la fuente se empareja correctamente a canal. Por lo tanto definimos la capacidad de canal cerca C = máximo (H (X) - H, (x)) donde está el máximo con respecto a todas las fuentes de información posibles usadas como entrada al canal. Si TEOREMA FUNDAMENTAL PARA UN CIIANNEL DISCRETO CON RUIDO Puede parecerse el sorprender ese nosotros wilh como pequeño un jre- el quency de los equivocalionas de los errores OY deseó por la codificación apropiada. Este estado ment no es verdad para ninguna tarifa C. mayor que. Si una tentativa se hace a transmitir en una tarifa más alta que C, la opinión C f RI, después allí voluntad necesariamente ser una ambigüedad igual a un mayor que el exceso RI. Tomas de la naturaleza pago requiriendo apenas que mucha incertidumbre, de modo que no seamos realmente consiguiendo más que C a través correctamente. La situación se indica en el higo 9. El índice de la información en el canal se traza horizontalmente y la ambigüedad verticalmente. Cualquier punto sobre la línea pesada en la región sombreada se pueden lograr y ésos abajo no poder. La línea de los puntos 011the no se puede en general lograr, pero allí voluntad ser generalmente dos puntos en la línea que puede. Una teoría matemática de la comunicación Estos resultados son la justificación principal para la definición de C y voluntad ahora probarte. Teorema 11. Dejar un canal discreto tener la capacidad C y un discreto fuente la entropía por el segundo N. Si < II; C allí existe un sistema de codificación tales que la salida de la fuente se puede transmitir sobre el canal con una frecuencia arbitrariamente pequeña de errores (o de una ambigüedad arbitrariamente pequeña). Si > Ii; C es posible codificar la fuente de modo que la ambigüedad sea menos de $1 - C + B donde está arbitrariamente pequeña c. No hay método de encod- ing que da una ambigüedad menos que H - C. El método de probar la primera parte de este teorema no está exhibiendo un método de la codificación que tiene las características deseadas, pero demostrando a eso tal a el código debe existir en cierto grupo de códigos. De hecho haremos un promedio de la frecuencia de errores sobre este grupo y demuestra que este promedio puede ser hecho menos de 6. Si el promedio de un sistema de números es menos que e allí debe existe por lo menos uno en el sistema que es menos que el E. Esto establecerá resultado deseado. Higo. ambigüedad del g-The posible para una entropía dada de la entrada a un canal. La capacidad C de un canal ruidoso se ha definido como C = máximo (H (X) - I-l, (x)) donde está la entrada y la y x la salida. La maximización está sobre todas las fuentes cuál se pudo utilizar como entrada al canal. Dejado TAN ser una fuente que alcanza la capacidad máxima C. Si esto el máximo no es alcanzado realmente por ninguna fuente dejó sea TAN una fuente que aproxima a dar la tarifa máxima. Suponer así que se utiliza como entrada a el canal. Consideramos las secuencias transmitidas y recibidas posibles de una duración larga T. Lo que sigue será verdad: 1. Las secuencias transmitidas bajan en dos clases, un alto grupo de la probabilidad con alrededor “(z) los miembros 2* y las secuencias restantes del total pequeño probabilidad. 2. Las secuencias recibidas tienen semejantemente una alta probabilidad fijada de alrededor 2TH miembros (u) y un sistema bajo de la probabilidad de secuencias restantes. 3. Cada alta salida de la probabilidad se podía producir por cerca de 2” las entradas “del `@). La probabilidad de el resto de los casos tiene una probabilidad total pequeña. C.E. Shannon Todas las e y 6 implicaron por las palabras “pequeñas” y “sobre” en el acercamiento cero de estas declaraciones como permitimos que T aumente y tan al acercamiento maximización de fuente. La situación se resume en el higo 10 donde están las secuencias de entrada puntos a la izquierda los puntos de las secuencias y de la salida a la derecha. El ventilador de las líneas cruzadas representan la gama de las causas posibles para una salida típica. Ahora suponer que tenemos otra fuente produciendo la información en la tarifa R con el < de R; C. En el período T esta fuente tendrá alta probabilidad 2TR salidas. Deseamos asociar éstos a una selección del canal posible 2Hk) T ALTA PROBABILIDAD MENSAJES 2li (y) T ALTA PROBABILIDAD SEÑALES RECIBIDAS . EFECTOS de REASOibABLE. DE CADA M . Higo. Representación del bajo-Diagrama esquemático de las relaciones entre las entradas y las salidas en a canal. entradas a fin de conseguir una frecuencia pequeña de errores. Instalaremos esta asociación de todas las maneras posibles (que usan, sin embargo, solamente el alto proba- grupo del bility de entradas según lo determinado por la fuente 30) y medio el frc- quency de los errores para esta clase grande de los sistemas de codificación posibles. Éste es iguales que calculando la frecuencia de los errores para una asociación al azar del los mensajes y las entradas del canal de la duración T. suponen una salida particular se observa el yl. Cuál es la probabilidad de más de un mensaje en el sistema ¿de causas posibles del año? Hay los mensajes 2TR distribuidos al azar adentro puntos 2TM (Z). La probabilidad de un punto particular que es un mensaje es así 2 T (R--H (d) Una teoría matemática de la comunicación La probabilidad que ningunos de los puntos en el ventilador son un mensaje (aparte de el mensaje que origina real) es T (R--H (r)) ” & 2T;) P= [l-2 1 AHORA < DE R; H (Z) - H, (x) TAN R -11 (x) = - I& &) -9 con el positivo 7. Por lo tanto P= [l 2 THy (d--T~ 12TN& acercamientos (como T --+ a) 1 -2-T”. Por lo tanto la probabilidad de un error acerca a cero y a la primera parte de se prueba el teorema. La segunda parte del teorema es demostrada fácilmente observando esa nosotros podría enviar simplemente los pedacitos de C por el segundo de la fuente, totalmente el descuidar resto de la información generada. En el receptor la parte descuidada da una ambigüedad U (z) - C y la necesidad transmitida parte agrega solamente el F. Este límite se puede también lograr de muchas otras maneras, como demostrarán cuando nos considerar el caso continuo. La declaración pasada del teorema es una consecuencia simple de nuestra definición de la C. suponer que podemos codificar una fuente con R = C + a fin de obtener una ambigüedad H, (x) = a - t con el positivo de e. Entonces R = H (x) = C + a y IW - I& (x) = c + e con el positivo de t esto contradice la definición de C como el máximo de H (x) - H” (x). Más se ha probado realmente que fue indicado en el teorema. Si el promedio de un sistema de números está dentro de t de su máximo, una fracción de en la mayoría del & pueden ser más que & debajo del máximo. Puesto que e está arbitrariamente pequeño podemos decir que casi todos los sistemas están arbitrariamente cerca del ideal. 14. DISCUSIÓN La demostración del teorema 11, mientras que no una prueba pura de la existencia, tiene algunas de las deficiencias de tales pruebas. Una tentativa de obtener un bueno la aproximación a la codificación ideal siguiendo el método de la prueba es GEN erally impráctico. De hecho, aparte de algunos casos algo triviales y ciertas situaciones limitadoras, ninguna descripción explícita de una serie de approxima- el tion al ideal se ha encontrado. Éste no es ningún accidente sino es probablemente relacionado a la dificultad de dar una construcción explícita para una buena aproximación a una secuencia al azar. C.E. Shannon Una aproximación al ideal tendría la característica que si la señal es alterado de una manera razonable por el ruido, la original puede todavía ser recuperado. Es decir la alteración en general no la traerá más cercano a otra señal razonable que la original. Esto se logra en el coste de a cierta cantidad de redundancia en la codificación. La redundancia debe ser introducido de la manera apropiada de combatir la estructura particular del ruido implicado. Sin embargo, cualquier redundancia en la fuente ayudará generalmente si es utilizado en el punto de recepción. Detalle de Ih, si la fuente tiene ya a no se hace cierta redundancia y ninguna tentativa de eliminarla en emparejar a el canal, esta redundancia ayudará a combatir ruido. Por ejemplo, en un silencioso el canal de telégrafo uno podía ahorrar el cerca de 50% a tiempo por la codificación apropiada de los mensajes. Esto no se hace y la mayor parte de la redundancia del inglés restos en los símbolos del canal. Esto tiene la ventaja, sin embargo, de permitir ruido considerable en el canal. Una fracción importante de las letras puede ser recibido incorrectamente y todavía ser reconstruido por el contexto. En el hecho esto no es probablemente una mala aproximación al ideal en muchos casos, puesto que la estructura estadística del inglés es algo implicada y la razonable Las secuencias inglesas no son demasiado lejanas (en el sentido requerido para el teorema) de a selección al azar. Como en el caso silencioso retrasa se requiere generalmente para acercar al ideal codificación. Ahora tiene la función adicional de permitir una muestra grande de divulgar para afectar la señal antes de que cualquier juicio se haga en el punto de recepción en cuanto a el mensaje original. El aumento del tamaño de muestra afila siempre aserciones estadísticas posibles. El contenido del teorema 11 y de su prueba se puede formular en a algo diversa manera que exhibe la conexión con el caso silencioso más claramente. Considerar las señales posibles de la duración T y suponer un subconjunto de ellas se selecciona para ser utilizado. Dejar ésos en el subconjunto todo ser utilizado con el igual la probabilidad, y supone que el receptor está construido para seleccionar, como la original señalar, la causa más probable del subconjunto, cuando una señal perturbada se recibe. Definimos N (T, q) para ser el número máximo de señales nosotros puede elegir para el subconjunto tales que la probabilidad de un inter incorrecto el pretation es inferior o igual Q. Teorema 12: Lim STu = C, donde está la capacidad C de canal, favorable T-r00 vided que q no iguala 0 o 1. Es decir no importa cómo fijamos nuestros límites de la confiabilidad, podemos distinguir confiablemente a tiempo T bastantes mensajes para corresponder alrededor a CT pedacitos, cuando T es suficientemente grande. El teorema 12 se puede comparar con definición de la capacidad de un canal silencioso dado en la sección 1. Una teoría matemática de la comunicación 1.5. EJEMPLO DE UN CANAL DISCRETO Y DE SU CAPACIDAD Un ejemplo simple de un canal discreto se indica en el higo 11. Allí son tres símbolos posibles. El primer nunca es afectado por el ruido. El segundo y tercer cada uno tiene probabilidad p de venir con imperturbado, y q de ser cambiado en el otro del par. El WC tiene (dejando LY = - [registro de p P 9 TRANSMITIDO RECIBIDO SÍMBOLOS DE LOS SÍMBOLOS Q x P Higo 11-Example de un canal discreto el registro q de p + de q] y P y Q sea las probabilidades de usar el primer o en segundo lugar símbolos) II (x) = - registro Q del registro P -2Q de I' H, (x) = 2Qa Deseamos elegir P y Q a fin de maximizar II (x) - H, (x), conforme al constreñimiento P - i 2Q = 1. Por lo tanto consideramos U = - registro P -2Qlog Q de P - ~QCY+ X (P + 2Q) gripe -1 - = todos - logP+x=o au - = -2 -2 1ogQ -2a+2x=o. aQ Eliminación de X ¡registro P = registro Q + a! P = Qe " = Q/3 p=P Q-L. P-i-2 P-l-2 La capacidad de canal entonces está C.E. Shannon Nota cómo esto comprueba los valores obvios en los casos p = 1 y p = ij. En el primer, /3 = 1 y C = el registro 3, que está correcto puesto que el canal isthen silencioso con tres símbolos posibles. Si p = a, p = 2 y C = registro 2. Aquí los segundos y terceros símbolos no pueden ser distinguidos en todos y actuar junto como un símbolo. El primer símbolo se utiliza con probabilidad P = $ y el segundo y tercero junto con la probabilidad 3. Esto puede ser distribuido de cualquier manera deseada y todavía alcanzar la capacidad máxima. Para los valores intermedios de p la capacidad de canal mentirá entre el registro 2 y registro 3. La distinción entre los segundos y terceros símbolos transporta una cierta información pero tanto como en el caso silencioso. El primer símbolo se utiliza algo más con frecuencia que los otros dos debido a su libertad de ruido. 16. CAPACIDAD de Tnz CIIANNJXL EN CIERTOS CASOS ESPECIALES Si el ruido afecta símbolos sucesivos del canal independientemente puede ser descrito por un sistema de pij de las probabilidades de la transición. Ésta es la probabilidad, si se envía el símbolo i, ese j será recibido. La tarifa máxima del canal es entonces dado por el máximo de, Pij del pij 10s del registro Z$ pi Pij -5 pi de E PiPii conforme a donde el WC varía el pi BPI = 1. Esto conduce por el método de Lagrange a las ecuaciones, s = 1.2, ***. Multiplicándose por P, y sumando en s demuestra ese p = - C. Dejar lo contrario de p, (si existe) ser h, l de modo que teniente de c, p, j = 6lj. Entonces: II registro P8j - hoyo de 5 h8f P*j del registro J$ pi = - lzaf de C F. Por lo tanto: Hoyo de F pi = exp tc T kc + 5 h, registro p, j del p*j de f] o, Exp del kf del pi = de F [l& de C C I; f + registro p.j de C8.j libra p, de j]. Éste es el sistema de las ecuaciones para determinar los valores de maximización de Pi, con C que se determinará de modo que B pi = 1. Cuando se hace esto C será la capacidad de canal, y el pi las probabilidades apropiadas para el canal símbolos para alcanzar esta capacidad. Una teoría matemática de la comunicación Si cada símbolo de la entrada tiene el mismo sistema de probabilidades en las líneas el emerger de ella, e igual es verdad de cada símbolo de la salida, la capacidad puede ser calculado fácilmente. Los ejemplos se demuestran en el higo 12. En tal caso H&) es la independiente de la distribución de probabilidades en los símbolos de la entrada, y se da cerca --Registro pi de Z pi donde están los valores los pi del proba- de la transición bilities de cualquier símbolo de la entrada. La capacidad de canal es Máximo [J-W - rrlb> l =MaxIZ (~~) +ZpilogPi. El máximo de 11 (y) es claramente el registro m donde está el número m de la salida a b C Higo 12--Ejemplos de canales discretos con las mismas probabilidades de la transición para cada uno nput y para cada salida. i símbolos, puesto que es posible haceros todo el igualmente probable haciendo los símbolos de la entrada igualmente probables. La capacidad de canal está por lo tanto C = registro m + registro pi de Z pi. En el higo 12a estaría c = registro 4 - log2 = log2. Esto podía ser alcanzada usando solamente el 1r y los símbolos 3d. En el higo 12b C = registro 6 de # del registro 4 - registro 3 de $ - = registro 2 del registro 4 - registro 3 - f = log& 29. higo 12c de h que tenemos C = registro G del registro -4 2 - registro 3 de f - Q del registro 3 C.E. Shannon Suponer la caída de los símbolos en varios grupos tales que el ruido nunca hace un símbolo en un grupo ser confundido desde un símbolo en otro grupo. Dejar la capacidad para el grupo del listón ser C, cuando utilizamos solamente los símbolos en este grupo. Entonces se demuestra fácilmente que, para el mejor uso del sistema entero, la probabilidad total I', de todos los símbolos en el grupo de la semilla debe ser P, = &. Dentro de un grupo se distribuye la probabilidad apenas pues sería si éstos eran los únicos símbolos que eran utilizados. La capacidad de canal es c = registro Z2c”. 17. UN EJEMPLO DE LA CODIFICACIÓN EFICIENTE El ejemplo siguiente, aunque algo es poco realista, es un caso en el cual el emparejar exacto a un canal ruidoso es posible. Hay de dos vías los símbolos, 0 y 1, y el ruido los afecta en los bloques de siete símbolos. A el bloque de siete se transmite sin error, o exactamente un símbolo de los siete es incorrectos. Estas ocho posibilidades son igualmente probables. Tenemos C = máximo [II (y) - UJy)] = `+ 17 + *I del registro de $ = pedacitos/símbolo de $. Un código eficiente, permitiendo la corrección completa de errores y transmitiéndola en la tarifa C, es la siguiente (encontrado por un método debido a R. Hamming): Dejar un bloque de siete símbolos ser XI, XZ. XT. De este X3, XS, X6 y XT son símbolos del mensaje y elegido arbitrariamente por la fuente. El otro tres son redundantes y calculados como sigue: ¡X4 se elige para hacer a! = X4 + X6 + X6 + Xv incluso `de la XA (““`(p = x, +xa+xg + x, `( Xl “(`I del `((y = Xl + x, + xrj + x, `( Cuando un bloque de siete se recibe (se calculan Y, /3 y y y si incluso está llamada cero, si llamado el impar. El número binario /3 y entonces da el subíndice de el XI que es incorrecto (si 0 allí no era ningún error). APÉNDICE 1 EL CRECIMIENTO DEL NÚMERO DE TIIE DE BLOQUES DE SÍMBOLOS CON A CONDICIÓN FINITA DEL ESTADO Dejar N& 5) sean el número de bloques de símbolos de la longitud L conclusión en estado i. Entonces tenemos Una teoría matemática de la comunicación 45 donde', bij. el byj es la longitud de los símbolos que pueden ser elegidos en el estado i y conducir para indicar el J. Éstas son ecuaciones de diferencia lineares y comportamiento como L - + 00 deben estar del tipo iVj = AjW " El substituir en la ecuación de diferencia `De Ajw = c AiW=-b::) i.s o ¡Aj = c Ai W-b! ; ' F (T WwbC' -6ij) Ai = 0. Para esto a ser posible el determinante D (W) = 1 Uijl = 17 Wmb$: ' - Sijl debe desaparecer y esto determina W, que es, por supuesto, la raíz verdadera más grande ofD = 0. La cantidad C entonces se da cerca c = `De ZAj W del registro de Lirn = registro W L-m L y también observamos que resultan las mismas características del crecimiento si requerimos que todos los bloques comienzan en el mismo estado (arbitrariamente elegido). APÉNDICE 2 DERIVACIÓN DE 11 = --Registro pi de Z pi Dejar H 1 L. , i) = A (n). De la condición (3) podemos descomponernos n' lz' una opción de posibilidades igualmente probables de s”' en una serie 7n de las opciones cada uno de posibilidades igualmente probables de s y obtener ¿A (? `) = nz A Semejantemente A (1” ) = 1z A (t) Podemos elegir n arbitrariamente grande y encontrar un m para satisfacer < de Srn; r del < P+l) C.E. Shannon ¿Así, tomando logaritmos y dividiéndose cerca? Registro S de E, donde está arbitrariamente pequeña e. Ahora de la característica monotónica de A (n) * _< de A (s' “); ¿A (f) i A (? + > del `; tzA del nz A (s) 5 (1) 5 (VE - i 1) A (s) Por lo tanto, dividiéndose por nA (s), A (1) ~< ----< ~+~ o A (4 1) < del registro de A (; 2e A (I) = - registro 1 de K n - registro S - donde K debe ser positiva satisfacer (2) . Ahora suponer que tenemos una opción de posibilidades de n con el prob- cornmeasurable ¿capacidades pi = 3 donde? Zi es intcgcrs. Podemos analizamos una opción Zlti de Bt; posibilidades en una opción de ella posibilidades con probabilidades pi. e e p, y entonces, si el ith fue elegido, una opción de Izi con el prob- igual capacidades. Usando la condición 3 otra vez, comparamos la opción total de Zjti según lo computado por dos métodos Registro Btii = ZZ (banda 9 de K. , 9 pn) 3 - registro Iti de KZ pi Por lo tanto H = K [tti del registro Z de LX pi - I: registro del pi Hi] = - KZpilogz~.= - KKpiIogpi. , Si los pi son incommeasurable, pueden ser aproximados por números racionales y la misma expresión debe sostener por nuestra asunción de la continuidad. Así la expresión sostiene en general. La opción de K coetlicient es un con- de la materia N-F veniencc y cantidades a la opción de una unidad de la medida. APÉNDICE 3 TEOREMAS EN FUENTES ERGÓDICAS Si es posible ir de añejo con el > de P; 0 a cualquier otro a lo largo de una trayectoria del > de la probabilidad p; 0, el sistema es ergódico y la ley fuerte de numérico grande los bers pueden ser aplicados. Así el número de épocas un pij dado de la trayectoria en la red Una teoría matemática de la comunicación el trabajo se atraviesa en una secuencia larga de la longitud N es alrededor de proporcional a probabilidad de estar en i y después de elegir esta trayectoria, ipijN de Z'. Si N es grande bastante la probabilidad del error f 6 del porcentaje en esto es menos que e de modo que para todos pero un sistema de la probabilidad pequeña los números reales mienten dentro de los límites (Pipij rt 6) N Por lo tanto casi todas las secuencias tienen una probabilidad p dada cerca p = npiTiPij*a) N El 1% P * y - fi- 1s limitado cerca El 1% P _ _ = pij del registro de Z (Pipij f S) N o El 1% P - < del pij del registro de ZPipij; ve N Esto prueba el teorema 3. El teorema 4 sigue inmediatamente de esto en calcular superior y más bajo límites para n (q) basada en la gama posible de valores de p en el teorema 3. En el caso (no ergódico) mezclado si L= ZpiLi y las entropías de los componentes son > de ZZr 2 ZZz; . 2 ZZ, tenemos ¡T! zeoretn: El `9 de Lim = p (q) es una función del paso que disminuye, N-W.3 r-1 p (q) = H, en el < del intervalo c ai; < de q; f= ai. I 1 Probar los teoremas 5 y la primera nota 6 que el FN es el disminuir monotónico está la causa que aumenta N agrega un subíndice a una entropía condicional. Un simple la substitución para el pei (Sj) en la definición del FN demuestra eso CNI de PN= NGN- (N-~) y sumar esto para toda la N da GN = f Z PN. Por lo tanto > de GN; _ 17~ y GN el disminuir monotónico. También deben acercar al mismo límite. Usando el teorema 3 vemos ese Lim GN = II. N--m * APÉNDICE 4 MAXIMIZACIÓN DE LA TARIFA PARA UN SISTEMA DE APREMIOS Suponer que tenemos un sistema de apremios en secuencias de símbolos de el cual esté el tipo finito del estado y se puede representar por lo tanto por un gráfico linear. C.E. Shannon Dejar C$r ser las longitudes de los varios símbolos de los cuales puede ocurrir en pasar indicar i para indicar el J. Qué distribución de las probabilidades pi para el diferente ¿estados y fi (l? para el símbolo que elige s en el estado i y el ir al statej maximiza ¿el índice de generar la información bajo estos apremios? Los apremios definir un canal discreto y la tarifa máxima debe ser menos que o igual a la capacidad C de este canal, desde entonces si eran todos los bloques de la longitud grande igualmente probablemente, esta tarifa resultaría, y si es posible esto sería la mejor. Nosotros demostrará que esta poder de la tarifa alcanzada a.C. por la opción apropiada del pi y del pi:. La tarifa en la pregunta es - zPip:: ¡Registro p de J! ¿`? = _N (a) (1) eij M de Pij del zP (i)' Dejado Cij = C tfy. ¿Evidentemente para un máximo pi? = exp 419 de k. El con- los straints en la maximización del `son ZPi = 1, p< de C; j = 1, 2 pi (pij -6ij) = 0. i Por lo tanto maximizamos u=---ZPi ZPi pij pij registro lij pij + A F + Pij + Ztlj Pi& ii -6ij) Pi XPi au - =-Wi (l + registro Pij) + NPi Cj + h + clli + ttiiipi = 0 lw de .apij El solucionar para el pij p, = & de /ii; L+ja Desde entonces Fij de F = 1, EN' = BjD-li del ~' BjZFdij Pii = C B, D-li8. 8 El valor correcto de D es la capacidad C y el Bj es soluciones de BI = 2 Bj-+j para entonces p, = 2 (J--b. t xpi 3 Cvcii = P, BI o Una teoría matemática de la comunicación TAN eso si XI satisface Z; yic-Gii = yj Pi= Biyi Ambos sistemas de las ecuaciones para I3 6 y 7; puede ser satisfecho puesto que C es tal que 1 cpdii - aij 1 = 0 En este caso la tarifa está P c Registro del pij de ZPi; I BPI de pij Cij pero Z; Pipij (registro Bj - BI del registro) = registro Bj de C Pj - BI del registro de ZPi = 0 i Por lo tanto la tarifa es C y como esto podría nunca ser excedida éste es el máximo' justificar la solución asumida. C.E. Shannon PARTE III: PRELIMINARES MATEMÁTICOS En esta instalación fmal del papel consideramos el caso donde las señales o los mensajes o ambos son continuamente variables, al contrario de la naturaleza discreta asumida hasta este momento. A un grado considerable el con- el caso tinuous se puede obtener con un proceso limitador del discreto caso dividiendo la serie continua de mensajes y de señales en un grande pero finito número de regiones pequeñas y de calcular los varios parámetros implicados encendido una base discreta. Como el tamaño de las regiones se disminuye estos parámetros adentro acercamiento general como límites los valores apropiados para el caso continuo. Allí son, sin embargo, algunos nuevos efectos de los cuales y también aparece un cambio general el énfasis en la dirección de la especialización del general resulta al particu- casos lar. No procuraremos, en el caso continuo, obtener nuestros resultados con la generalidad más grande, o con el rigor extremo de las matemáticas puras, desde entonces esto implicaría teoría abstracta mucha de la medida y ob- scure el hilo de rosca principal del análisis. Un estudio preliminar, sin embargo, indi- cates que la teoría se puede formular en un totalmente axiomático y manera rigurosa que incluye los casos continuos y discretos y muchos otros. Las libertades ocasionales tomadas con la limitación de procesos en el actual análisis se puede justificar en todos los casos del interés práctico. 18. SISTEMAS Y CONJUNTOS DE FUNCIONES Tendremos que tratar en el caso continuo de los sistemas de funciones y conjuntos de funciones. Un sistema de funciones, como el nombre implica, es simplemente a clase o colección de funciones, generalmente de una variable, tiempo. Puede ser especificado dando una representación explícita de las varias funciones en fijar, o implícito dando una característica que las funciones en el sistema posean y otros no. Algunos ejemplos son: 1. El sistema de funciones: = pecado (1 + 0) . Cada valor particular de 0 determina una función particular en el sistema. je (O Una teoría matemática de la comunicación 2. El sistema de todas las funciones de tiempo no contener ninguna frecuencia sobre W completa un ciclo por segundo. 3. El sistema de todo funciona limitado en venda a W y en amplitud al A. 4. El sistema de todas las señales de discurso inglesas como funciones del tiempo. Un conjunto de funciones es un sistema de funciones junto con una probabilidad medir por el que poder determinar la probabilidad de una función en fijar tener ciertas características.' Por ejemplo con el sistema, h (l) = sin@+@, podemos dar una distribución para 0, P (0) de la probabilidad. El sistema entonces se convierte un conjunto. Algunos otros ejemplos de conjuntos de funciones son: 1. Un sistema finito de functionsf&) (K = 1, 2, * * *, n) con la probabilidad de jk siendo pk. 2. Una familia dimensional finita de funciones f& l) QZ, * * *, %I, * 1) con una distribución de la probabilidad para los parámetros ai: pb1, * * *, WI) Por ejemplo podríamos considerar el conjunto defmed cerca con las amplitudes ai distribuidas normalmente e independientemente, y BI de las frases distribuido uniformemente (a partir de la 0 a 27r) e independientemente. 3. El conjunto j (ai, 1) = pecado 7~ (2W1 -4 de la diversión n--co 7r (2W1 - n) con el ai normal y la independiente toda con la misma desviación de estándar Z/g. Ésta es una representación del ruido “blanco”, band-limited a la venda a partir de la 0 a W completa un ciclo por segundo y con la energía media N. ¡1 en matemáticas! la terminología matical las funciones pertenece a un espacio de la medida que total la medida es umty. 1 esta representación se puede utilizar como definición del ruido blanco limitado venda. Tiene ¡ciertas ventajas en que implica menos I! ¿el mlting de Op. Sys., erations que d? definiciones que se han utilizado en el pasado. El “ruido blanco conocido, ya lirmly mtrenched m la literatura, es quizás algo desafortunada. En la óptica la luz blanca significa cualquiera espectro continuo según lo puesto en contraste con un espectro del punto, o un espectro que es plano con el wauelmglh (que no es igual que un espectro plano con frecuencia). C.E. Shannon 4. Dejado los puntos se distribuyan en el eje de t según un distribu- de Poisson tion. En cada punto seleccionado se pone el functionf (f) y el diferente las funciones agregaron, dando el conjunto donde está los puntos el lk de la distribución de Poisson. Este conjunto se pueden considerar como tipo de impulso o de ruido tirado donde todos los impulsos ser idéntico. 5. El sistema de funciones inglesas del discurso con la medida de la probabilidad dada por la frecuencia de la ocurrencia en uso ordinario. Un conjunto de functionsf&) es slalio~tary si resulta el mismo conjunto cuando todas las funciones se cambian de puesto cualquier fijo ascender a tiempo. El conjunto f&) = pecado (b + e) es inmóvil si 0 distribuyó uniformemente a partir de la 0 a 2~. Si cambiamos de puesto cada uno funcional tion por 11 que obtenemos f0 (t + 11) = pecado (1 + II + 0) = pecado (1 + V) con el cp distribuido uniformemente a partir de la 0 a 25~. Cada función ha cambiado pero el conjunto en su totalidad es invariante bajo traducción, la otra los ejemplos dados arriba son también inmóviles. Un conjunto es ergo& c si es inmóvil, y allí no es ningún subconjunto del funcional tions en el sistema con una probabilidad diferente a partir de la 0 y de 1 que es inmóvil. El conjunto pecado (1 + e) es ergódico. No se transforma ningún subconjunto de estas funciones del #O de la probabilidad, 1 is transformed into itself under all time translations. On the other hand the ensemble a sin (1 + 0) with a distributed normally and 8 uniform is stationary but not ergodic. The subset of these functions with a between 0 and 1 for example is stationary. Of the examples given, 3 and 4 are ergodic, and 5 may perhaps be con- sidered so. If an ensemble is ergodic we may say roughly that each func- tion in the set is typical of the ensemble. More precisely it is known that with an ergodic ensemble an average of any statistic over the ensemble is equal (with probability 1) to an average over all the time translations of a A Mathematical Theory of Communication particular function in the set.3 Roughly speaking, each function can bc cx- petted, as time progresses, to go through, with the proper frequency, all the convolutions of any of the functions in the set. Just as we may perform various operations on numbers or functions to obtain new numbers or functions, we can perform operations on cnscmbles to obtain new ensembles. Suppose, for example, we have an ensemble of functionsf,(i) and an operator T which gives for each functionf,(/) a result &40 : Probability measure is defined for the set gn(l) by means of that for the set f&). Tlx probab 1 1 i i y of a certain subset of the g,(l) functions is equal to that of the subset of the ja(l) functions which produce mcmbcrs of the given subset of g tunctions under the operation I’. Physically this corrc- sponds to passing the cnscmble through some dcvicc, for exan~plc, a filter, a rectifier or a modulator. The output functions of the device form the ensemble ge(l). A device or operator T will bc called invariant if shifting the input merely shifts the output, i.e., if g&> = TJ,!O implies g&l -I- fd = Tf,(f + 4) for allf&l) and all II . It is easily shown (see appendix 1) that if T is in- variant and the input enscn~blc is stationary then the output cnscmblc is stationary. Likewise if the input is ergodic the output will also bc crgodic. A filter or a rectifier is invariant under all time translations. The opera- tion of modulation is not since the carrier phase gives a certain time struc- ture. However, modulation is invariant under all translations which arc multiples of the period of the carrier. Wiener has pointed out tlic intiinatc relation bctwcen the invariance of physical devices under time translations a.nd Fourier tllcory.4 1-1~ has 3 This is the famous crgo:lic Lhcorcm or ralhcr one aspect of Lhis theorem which was t~roved is son~cwhat differen formulations by JSir$off, van Neumann, and Koopman, and subsequently gcncralizetl by Wicncr, I-Iopf! JIurcwcz and olhcrs. The lilcralure on crgo:!ic theory is quite exlcnsive and the reader 1s referred lo the papers of these writers for pre- cise and general Iormulalions; e.g., 11. HopI “JSrgo~!cntheoric” Ergcbnissc tier Malhcmatic und ihrer Grcnzgebiet~, Vol. 5, “On Causality SLaLisLics and Probability” Journal of Mathematics and Physics, Vol. XIII, No. 1, 1934; N. Weiner “The Ergodic Theorem” Duke Mathematical Journal., Vol. 5, 1939. 4 CommunicaLion theory IS heavily indcbtcd Lo Wiener for much of ils basic philosophy and theory. His classic NDRC report “The Intcrt~olalion, 15xLral~olaLion, and Smoolhing of Stationary Time Series,” Lo appear soon in book form, contains the lirst clear-cul formulaLion of communication theory as a statistical problem, the study of opcralions C. E. Shannon shown, in fact, that if a device is linear as well as invariant Fourier analysis is then the appropriate mathematical tool for dealing with the problem, An ensemble of functions is the appropriate m.athematical representation of the messages produced by a continuous source (for example speech), of the signals produced by a transmitter, and of the perturbing noise. Com- munication theory is properly concerned, as has been emphasized by Wiener, not with operations on particular functions, but with operations on en- sembles of functions. A communication system is designed not for a par- ticular speech function and still less for a sine wave, but for-the ensemble of speech functions. 19. BAND LIMITED ENSEMDLES OF FUNCTIONS If a function of timej(1) is limited to the band from 0 to W cycles per second it is completely determined by giving its ordinates at a series of dis- crete points spaced &w seconds apart in the manner indicated by the follow- ing result.6 Tkeorm 13: Let j(1) contain no frequencies over 11’. , Then f(1) = -g x, Sk 742TY1 -1zj --m 742Wl -n) where In this expansion j(l) is reprcsentcd as a sum of orthogonal functions. The coefficients X, of the various terms can be considered as coordinates in an infinite dimensional “function space.” In this space each function cor- responds to precisely one point and each point to one function. A function can be considered to be substantially limited to a time T if all the ordinates X, outside this interval of time arc zero. In this case all but 27747 of the coordinates will be zero. Thus functions limited to a band W and duration T correspond to points in a space of 2TW dimensions. A subset of the functions of band W and duration T corresponds to a re- gion in this space. For example, the functions whose total energy is less on time series. This work, although chiefly concerned with the linear prediction and filtering problem, is an important collateral reference in connection with the present paper. We may also refer here to Wiener’s forthcoming book “Cybcrnctics” dealing with the general problems of communication and control. 6 For a proor of this theorem and further discussion see the author’s paper “Communi- cation in the Presence of Noise” to be published in the Proceedirzgs o/ llre Z~slil~la of Radio Ettgitteers. A Mathematical Theory of Communication than or equal to 23 correspond to points in a 2TW dimensional sphere with radius I = 42WE. An ensemble of functions of limited duration and band will be represented by a probability distribution &xl . . . x,) in the corresponding 12 dimensional space. If the ensemble is not limited in time we can consider the 2TW co- ordinates in a given interval T to represent substantially the part of the function in the interval T and the probability distribution p(xr , . . . , x,) to give the statistical structure of the ensemble for intervals of that duration. 20. ENTROPY OF A CONTINUOUS DISTRIBUTION The entropy of a discrete set of probabilities pr , * . . p,, has been defined as: II = -CpilOgpi. In an analogous manner we deline the entropy of a continuous distribution with the density distribution function p(x) by: zz = - J-1 P(x) 1% P(x) dx With an 11 dimensional distribution p(xr , . * * , x,) we have If we have two arguments x and y (which may themselves bc multi-dimen- sional) the joint and conditional entropies of p(x, y) are given by I& Y> = -j-/ z’b, Y> log Pb, y> dx dy and II,(y) = -/-I p(x, y) log ‘3 dx dy II,(x) = -I/ p(x, y) log ‘g dx dy where P(x) = /- P(G Y) dy P(Y) = /- P(X, Y> dx. The entropies of continuous distributions have most (but not all) of the properties of the discrete case. In particular we have the following: C. E. Shannon 1. If x is limited to a certain volume v in its space, then ZZ(r) is a maximum and equal to log v when p(x) is constant -1 in the volume. 0 V 2. With any two variables x, y we have ax, y> 5 Wx) + WY) with equality if (and only if) x and y are independent, i.e., p(x, y) = p(s) p(y) (apart possibly from a set of points of probability zero). 3. Consider a generalized averaging operation of the following type: P’(Y) = /- ah, Y>P(X> dx with a(x, y) dx = &, Y> dy = 1, 4% Y> 2 0. s s Then the entropy of the averaged distribution p’(y) is equal to or greater than that of the original distribution p(x). 4. We have zax, y> = fG> + NAY) = NY) + Z&!(x) and K(Y) I NY) . 5. Let p(x) be a one-dimensional distribution. The form of p(x) giving a maximum entropy subject to the condition that the standard deviation of x be fixed at u is gaussian. To show this we must maximize N(x) = -1 p(x) log P(x) dx with a2 = p(x)%” dx and 1 = p(x) dx s s as constraints. This requires, by the calculus of variations, maximizing s[--P(x) log P(x) + XP(x>; + /&>I dx. The condition for this is -l-logp(x)+X~2+_t=o and consequently (adjusting the constants to satisfy the constraints) p(x) = & ~ e-(~2/2u*). A Mathematical Theory of Communication Similarly in 18 dimensions, suppose the second order moments of p(s , * * - , x,) arc fixed at Aij : nij= J . . . J xixjp(xl, **a pXn)dxl .*a dx,. Then the maximum entropy occurs (by a similar calculation) when P(Xl , - * * , x,) is the IZ dimensional gaussian distribution with the second order moments A ii . 6. The entropy of a one-dimensional gaussian distribution whose standard deviation is u is given by ZI(X) = log 42aecr. This is calculated as follows: p(x) = Au e-(r*12sP) -log p(x) = log 60 + g2 H(x) = -1 P(x) log P(x) dx = p(x) log 42;; cr dx + p(x) $,* dx J J =log&r+&2 = log 4% + log 6 = log &G u. Similarly the IZ dimensional gaussian distribution with associated quadratic form aii is given by p(x1 , . . * , x,) = ~ 1aij It exp (- $2&j Xi Xj) (2?r)“‘ 2 and the entropy can be calculated as II = log (2*C)“” (Uij (’ where 1 aij 1 is the determinant whose elements are aij . 7. If x is limited to a half line (p(x) = 0 for z 5 0) and the first moment of x is fixed at a: C. E. Shannon then the maximum entropy occurs when p(x) = ; e-(z’o) and is equal to log ea. 8. There is one important difference between the continuous and discrete entropies. In the discrete case the entropy measures in an absolzcle way the randomness of the chance variable. In the continuous case the measurement is rela&e lo he coordirtdfe system. If we change coordinates the entropy will in gcncral change. In fact if we change to coordinates y1* * - y,, the new entropy is given by where J E is the Jacobian of the coordinate transformation. 011 cx- 0 Y panding the logarithm and changing variables to ~1 . * . x,, , we obtain: N(y) = II(x) -1 * * * /- p(q) * * - , XJ log J ; dx1. *. dx,. 0 Thus the new entropy is the old entropy less the expected logarithm of &SC the Jacobian. In the continuous the entropy can bc considered a measure of randomness relalive LO au assumed slathdard, namely the co- ordinate system chosen with each small volume element dxl . . . dx, given equal weight, When we change the coordinate system the entropy in the new system mcasurcs the randomness when equal volume clemcnts dyl - . - dy” in the new system are given equal weight. In spite of this dependence on the coordinate system the entropy concept is as important in the continuous case as the discrete case. This is due to the fact that the derived concepts of information rate and chamiel capacity depend on the difference of two entropics and this difference does ltol depend on the coordinate frame, each of the two terms being changed by the same amount. The entropy of a continuous distribution can be negative. The scale of measurements sets an arbitrary zero corresponding to a uniform dis- tribution over a unit volume. A distribution which is more confined than this has less entropy and will be negative. The rates and capacities will, however, always be non-negat.ive. 9. A particular case of changing coordinates is the linear transformation ‘yj = C UijXi . , A Mathematical Theory of Communication In this case the Jacobian is simply the determinant 1 a;j 1-l and ZZ(y) = H(X). + log 1 Uij 1 s In the case of a rotation of coordinates (or any measure preserving trans- formation) J = 1 and I-l(y) = B(x). 21. ENTROPY OF AN ENSEMBLE OF FUNCTIONS Consider an ergodic ensemble of functions limited to a certain band of width W cycles per second. Let p(a * - - X”> be the density distribution function for amplitudes zr - . - x,, at 12 successive sample points. We define the entropy of the ensemble per degree of free- dom by We may also define an entropy H per second by dividing, not by 15, but by the time Tin seconds for 12 samples. Since n = 2TW, H’ = 2WH. With white thermal noise p is gaussian and we have ZZ’ = log d2*eN, H = W log 2neN. For a given average power N, white noise has the maximum possible entropy. This follows from the maximizing properties of the Gaussian distribution noted above. The entropy for a continuous stochastic process has many properties analogous to that for discrete processes. In the discrete case the entropy was related to the logarithm of the probability of long sequences, and to the number of reasonably probable sequences of long length. In the continuous case it is related in a similar fashion to the logarithm of the probabililj dettsily for a long series of samples, and the volunte of reasonably high prob- ability in the function space. More precisely, if we assume p(s * . * x,) continuous in all the Xi for all 12, then for sufficiently large 92 for all choices of (x1 , . . * , r,) apart from a set whose total probability is less than 6, with 6 and e arbitrarily small. This follows from the ergodic property if WC divide the space into a large number of small cells. C. E. Shannon The relation of H to volume can be stated as follows: Under the same as- sumptions consider the it dimensional space corresponding to p(zr , . . - , x,). Let V,,(q) be the smallest volume in this space which includes in its interior a total probability q. Then Lim log Im(q) = N’ “-%W n provided 9 does not equal 0 or 1. These results show that for large n there is a rather well-defined volume (at least in the logarithmic sense) of high probability, and that within this volume the probability density is relatively uniform (again in the logarithmic sense). In the white noise case the distribution function is given by Since this depends only on Xx: the surfaces of equal probability density are spheres and the entire distribution has spherical symmetry. The region - of high probability is a sphere of radius d,zN. As I&--+ Q, the probability of being outside a sphere of radius dm approaches zero and k times the logarithm of the volume of the sphere approaches log m. In the continuous case it is convenient to work not with the entropy ZZ of an ensemble but with a derived quantity which we will call the entropy power. This is defined as the power in a white noise limited to the same band as the original ensemble and having the same entropy. In other words if H’ is the entropy of an ensemble its entropy power is N1 = 2be exp 211’. In the geometrical picture this amounts to measuring the high probability volume by the squared radius of a sphere having the same volume. Since white noise has the maximum entropy for a given power, the entropy power of any noise is less than or equal to its actual power. 22. ENTROPY Loss IN LINEAR FILTERS Theorem 14: If an ensemble having an entropy ZZr per degree of freedom in band W is passed through a filter with characteristic l’(J) the output ensemble has an entropy zz, = ZZI + tfi s, log / I’(I) 1” dj. A Mathematical Theory of Communication The operation of the filter is essentially a linear transformation of co- ordinates. If we think of the different frequency components as the original coordinate system, the new frequency components are merely the old ones multiplied by factors. The coordinate transformation matrix is thus es- TABLE I ENTROPY ENTROPY GAIN POWER POWER GAIN IMPULSE RESPONSE FACTOR IN DECIBELS I SIN’? %‘t (ntF cost-1 co5 t SIN t’ 0.384 ---+- t4 2t.2 t3 , - “3 ----) 11 0 GJ I q J, W -2.66 P----t -6.66 a -!- [ cos (I-cqt-cos t 1 at* sentially diagonalized in terms of these coordinates. The Jacobian of the transformaCon is (for 18 sine and IZ cosine components) J = Q I Y(fi) I2 C.E.Shannon where the ji are equally spaced through the limit the band W. This becomes in expf jw log I Y(j) I2 df. Since J is constant its average value is this same quantity and applying the theorem on the change of entropy with a change of coordinates, the result follows. We may also phrase it in terms of the entropy power. Thus if the entropy power of the first ensemble is N1 that of the second is NI exp 1: Jw log I y(j) I2 dfr The final entropy power is the initial entropy power multiplied by the geo- metric mean gain of the filter. If the gain is measured in db, then the output entropy power will be increased by the arithmetic mean db gain over W. In Table I the entropy power loss has been calculated (and also expressed in db) for a number of ideal gain characteristics. The impulsive responses of these filters are also given for W = 27r, with phase assumed to be 0. The entropy loss for many other cases can be obtained from these results. For example the entropy power factor f for the first case also applies to any gain characteristic obtained from 1 - w by a measure preserving transforma- tion of the o axis. In particular a linearly increasing gain G(o) = 0, or a “saw tooth” characteristic between 0 and 1 have the same entropy loss. The reciprocal gain has the reciprocal factor. Thus i has the factor e2. Raising the gain to any power raises the factor to this power. 23. ENTROPY OF THE SUM OF Two ENSEMBLES If we have two ensembles of functionsf,(l) and ga(l) we can form a new ensemble by “addition.” Suppose the first ensemble has the probability density function p(xr , * * - , x,) and the second q(x1 , - . - , 2,). Then the density function for the sum is given by the convolution: -q(xl -yi, ... , x,, -y,,) dyi, dyz, . .-- ,, dy,. Physically this corresponds to adding the noises or signals represented by the original ensembles of functions. A Mathematical Theory of Communication The following result is derived in Appendix 6. Theorem 15: Let the average power of two ensembles be Nr and N2 and let their entropy powers be Nr and fi2. Then the entropy power of the sum, f13 , is bounded by White Gaussian noise has the peculiar property that it can absorb any other noise or signal ensemble which may be added to it with a resultant entropy power approximately equal to the sum of the white noise power and the signal power (measured from the average signal value, which is normally zero), provided the signal power is small, in a certain sense, compared to the noise. Consider the function space associated with thcsc enscmblcs having ?E dimensions. The white noise corresponds to a spherical Gaussian distribu- tion in this space. The signal ensemble corresponds to another probability distribution, not necessarily Gaussian or spherical. Let the second moments of this distribution about its center of gravity be aij. That is, if Pbl, **-9 x,) is the density distribution function Uij = * * * p(:ri -ai)(xj -aj) dxl, * * * , dx, s s where the ai are the coordinates of the center of gravity. Now aij is a posi- tive definite quadratic form, and we can rotate our coordinate system to align it with the principal directions of this form. aij is then reduced to diagonal form bii . We require \hat each bii be small compared to N, the squared radius of the spherical distribution. In this case the convolution of the noise and signal produce a Gaussian distribution whose corresponding quadratic form is N + bii , The entropy power of this distribution is [II(N + bii)I”” or approximately = [(N)” + Zbii(N)“-‘]l’” The last term is the signal power, while the first is the noise power. C. E. Shannon PART IV: THE CONTINUOUS CHANNEL 24. TIIE CAPACITY OF A CONTINUOUS CHANNEL In a continuous channel the input or transmitted signals will be con- tinuous functions of time/(L) belonging to a certain set,,and the output or received signals wili be perturbed versions of these. We will consider only the case where both transmitted and received signals are limited to a certain band W. They can then be specified, for a time T, by 2TW numbers, and their statistical structure by finite dimensional distribution functions. Thus the statistics of the transmitted signal will be determined by P(x1, * - ’ ,%I) = P(x) and those of the noise by the conditional probability distributidh P q ,..., X.(Yl , * * * , y*) = P,(y). The rate of transmission of information for a continuous channel is defined in a way analogous to that for a discrete channel, namely R = H(x) -Ii,(x) where H(X) is the entropy of the input and 11&) the equivocation. Tbc channel capacity C is defined as the maximum of R when we vary the input over all possible ensembles. This means that in a finite dimensional ap- proximation we must vary P(x) = P(xl , * * * , 2,) and maximize - 1 P(x) log P(x) dx + 11 P(x, y) log ‘# dx dy. This can be written ax,Y) log --&, y) ss P(x)P(y) dx dy using the fact that P(x, y) log P(x) dx dy = P(x) log P(x) d.r. The s channel capacity is thus expressed C = Lim Max 1 p(x, Y> 1% ‘(‘7 Y) dx dy r--ra, p(z) T PbmY) * It is obvious in this form that R and C are independent of the coordinate system since the numerator and denominator in log P(x, Y> will be multi- PWYY) plied by the same factors when x and y are transformed in any one to one way. This integral expression for C is more general than N(x) -ri,(x). Properly interpreted (see Appendix 7) it will always exist while H(x) -H*(x) A Mathematical Theory of Communication may assume an indeterminate form m -~0 in some cases. This occurs, for example, if x is limited to a surface of fewer dimensions than 18 in its IZ dimen- sional approximation. If the logarithmic base used in computing II(X) and I-l,(x) is two then C is the maximum number of binary digits that can be sent per second over the channel with arbitrarily small equivocation, just as in the discrete case. This can be seen physically by dividing the space of signals into a large num- ber of small cells, sufficiently small so that the probability density P,(y) of signal x being perturbed to point y is substantially constant over a cell (either of N or y). If the cells are considered as distinct points the situation is essentially the same as a discrete channel and the proofs used there will apply. But it is clear physically that this quantizing of the volume into individual points cannot in any practical situation alter the final answer significantly, provided the regions are sutliciently small. Thus the capacity will be the limit of the capacities for the discrete subdivisions and this is just the continuous capacity defined above. On the mathematical side it can be shown first (see Appendix 7) that if u is the message, x is the signal, y is the received signal (perturbed by noise) and v the recovered message then Zi(x) -ZZJX) 2 ZZ(u) -H,(u) regardless of what operations are performed on u to obtain x or on y to obtain u. Thus no matter how we encode the binary digits to obtain the signal, or how we decode the received signal to recover the message, the discrete rate for the binary digits does not exceed the channel capacity WC have defined. On the other hand, it is possible under very general conditions to find a coding system for transmitting binary digits at the rate C with as small an equivocation or frequency of errors as desired. This is true, for example, if, when we take a finite dimensional approximating space for the signal func- tions, P(r, y) is continuous in both x and y except at a set of points of prob- ability zero. An important special case occurs when the noise is added to the signal and is independent of it (in the probability sense). Then P,(y) is a function only of the difference n = (y -x), Pz(Y) = Q(Y -4 and we can assign a definite entropy to the noise (independent of the sta- tistics of the signal), namely the entropy of the distribution Q(lt). This entropy will be denoted by ZZ(n). Theorem Id: If the signal and noise are independent and the received signal is the sum of the transmitted signal and the noise then the rate of C. E. Shannon transmission is R * ZZ(y) -U(H) i.e., the entropy of the received signal less the entropy of the noise. The channel capacity is c = ~~zx N(y) -II(N). We have, since y = x + 12: ZZ(x, y) = zz(x, u). Expanding the left side and using the fact that x and IZ are independent my) + B”(X) = Jw + H(4. Hence R = ZZ(x) -Ziv(x) = U(y) -a(n) . Since ZZ(w) is independent of P(x), maximizing R requires maximizing a(y), the entropy of the received signal. If there are certain constraints on the ensemble of transmitted signals, the entropy’of the received signal must be maximized subject to these constraints. 25. CHANNEL CAPACITY WITH AN AVIZRAGE POWER LIMITATION A simple application of Theorem 16 is the case where the noise is a white thermal noise and the transmitted signals arc limited to a certain average power P. Then the received signals have an average power P + N where N is the average noise power. The maximum entropy for the received sig- nals occurs when they also form a white noise ensemble since this is the greatest possible entropy for a power P + N and can be obtained by a suitable choice of the ensemble of transmitted signals, namely if they form a white noise ensemble of power P. The entropy (per second) of the re- ceived ensemble is then NY) = w log 27re(P + iv), and the noise entropy is ZZ(n) = w log 27reN. The channel capacity is c = ZZ(y) -M(n) = w log N P+N . Summarizing we have the following: Theorem 17: The capacity of a channel of band W perturbed by white A Mathematical Theory of Communication 67 thermal noise of power iV when the average transmitter power is P is given by C = w log 7 P+N . This means of course that by sufficiently involved encoding systems we can transmit binary digits at the rate W log2 P+N N bits per second, with arbitrarily small frequency of errors. It is not possible to transmit at a higher rate by any encoding system without a definite positive frequency of errors. To approximate this limiting rate of transmission the transmitted signals must approximate, in statistical properties, a white noise.6 A system which approaches the ideal rate may be described as follows: Let M = 2” samples of white noise be constructed each of duration T. These are assigned binary numbers from 0 to (U -1). At the transmitter the message se- quences are broken up into groups of s and for each group the corresponding noise sample is transmitted as the signal. At the receiver the M samples are known and the actual received signal (perturbed by noise) is compared with each of them. The sample which has the least R.M .S. discrepancy from the received signal is chosen as the transmitted signal and the corresponding binary number reconstructed. This process amounts to choosing the most probable (a posleriori) signal. The number M of noise samples used will depend on the tolerable frequency t of errors, but for almost all selections of samples we have Lim Lim log M(e, T) = w log P f N e-so T-boa T -, N so that no matter .how small e is chosen, we can, by taking T sufficiently P+N large, transmit as near as we wish to TW log N binary digits in the time T. Formulas similar to C = IV log c;J for the white noise case have been developed independently by several other writers, although with some- what different interpretations. We may mention the work of N. Wiener,’ W. G. Tuller,’ and II. Sullivan in this connection. In the case of an arbitrary perturbing noise. (not necessarily white thermal noise) it does not appear that the maximizing problem involved in deter- eThis and other properties of the white noise case are discussed from the geometrical point of view in “Communication in the Presence of Noise,” lot. cit. “‘Cybernetics,” lot. cit. OSc. D. thesis, Dcpartmcnt of Electrical Engineering, M.I.T., 1948 C. E. Shannon mining the channel capacity C can be solved explicitly. Hawcver, upper and lower bounds can be set for C in terms of the average noise power N and the noise entropy power Nl . These bounds are sufficiently close to: gether in most practical cases to furnish a satisfactory solution to the problem. Theorem 18: The capacity of a channel of band IV perturbed by an arbi- trary noise is bounded by the inequalities w log - P + Nl NI 5 c < w log 7 P-I-N 1 where P = average transmitter power N = average noise power Nl = entropy power of the noise. Here again the average power of the perturbed signals will be P + N. The maximum entropy for this power would occur if the received signal were white noise and would be W log 2ne(P + N). It may not be possible to achieve this; i.e. there may not be any ensemble of transmitted signals which, added to the perturbing noise, produce a white thermal noise at the receiver, but at least this sets an upper bound to El(y). We have, therefore C = max U(y) -ZZ(n) 5 W log 2ne(P i-N) -W log 2reNr. This is the upper limit given in the theorem. The lower limit can be ob- tained by considering the rate if we make the transmitted signal a white noise, of power P. In this case the entropy power of the received signal must be at least as great as that of a white noise of power P + ATI since we have shown in a previous theorem that the entropy power of the sum of two ensembles is greater than or equal to the sum of the individual entropy powers. Hence max H(y) >_ W log 2?re(P + N1) and C 2 W log 2re(P -I- NI) -W log 2rreNr = w log P~ + NI . Nl As P increases, the upper and lower bounds approach each other, so we have as an asymptotic rate PfN w log - Nl A Mathematical Theory of Communication If the noise is itself white, N = iVr and the result reduces to the formula proved previously: C=Wlog 1+;, ( > If the noise is Gaussian but with a spectrum which is not necessarily flat, Nr is the geometric mean of the noise power over the various frequencies in the band W. Thus Nl = exp $ logNJ)dJ sW where N(J) is the noise power at frequencyf. Theorem 19: If we set the capacity for a given trausmitter power P equal to C = w log P+N-t,N 1 then v is monotonic decreasing as P increases and approaches 0 as a limit. Suppose that for a given power PI the channel capacity is PI + N -tl~ w 1% N 1 This means that the best signal distribution, say P(X), when added .to the noise distribution q(x), gives a received distribution r(y) whose entropy power is (PI + N -VI). Let us increase the power to PI + AP by adding a white noise of power AP to the signal. The entropy of the received signal is now at least H(yj = W log 2re(Pl+ N -r]l + AP) by application of the theorem on the minimum entropy power of a sum. Hence, since we can attain the I. indicated, the entropy of the maximizing distribution must be at least as great and 7 must be monotonic decreasing. To show that q -+ 0 as P + 00 consider a signal which is a white noise with a large P. Whatever the perturbing noise, the received signal will be approximately a white noise, if P is sufficiently large, in the sense of having an entropy power approaching P + N. 26. THE CHANNEL CAPACITY WITH A PEAK POWER LIMITATION In some applications the transmitter is limited not by the average power output but by the peak instantaneous power. The problem of calculating the channel capacity is then that of maximizing (by variation of the ensemble of transmitted symbols) Jw -a4 C. E. Shannon subject to the constraint that all the functions j(l) in the ensemble be less than or equal to 6, say, for all 1. A constraint of this type does not work out as well mathematically as the average power limitation. The most we have obtained for this case is a lower bound valid for all $ an “asymptotic” upper band valid for large $ and an asymptotic value of C for $ small. ( > Theorem 20: The channel capacity C for a band IV perturbed by white thermal noise of power N is bounded by where 5’ is the peak allowed transmitter power. For sufficiently large c < w logre N (1 + 4 where B is arbitrarily small. As $ + 0 (and provided the band W starts at 0) C+Wlog 1+$ . ( > We wish to maximize the entropy of the received signal. If i is large this will occur very nearly when we maximize the entropy of the trans- mitted ensemble. The asymptotic upper bound is obtained by relaxing the conditions on the ensemble. Let us suppose that the power is limited to S not at every instant of time, but only at the sample points. The maximum entropy of the transmitted ensemble under these weakened conditions is certainly greater than or equal to that under the original conditions. This altered problem can be solved easily. The maximum entropy occurs if the different samples are independent and have a distribution function which is constant from -z/J; to + a. The entropy can be calculated as w log 4s. The received signal will then have an entropy less than W log (4s + 2*eN)(l + e) A Mathematical Theory of Communication with c -+ 0 as i + 00 and the channel capacity is obtained by subtracting the entropy of the white noise, W log 2neN -?S+N W log (4s + 2?reN)(l -I- e) -117 log (27reN) = W log ?re N (1 + 4. This is the desired upper bound to the channel capacity. To obtain a’lower bound consider the same ensemble of functions. Let these functions be passed through an ideal filter with a triangular transfer characteristic. The gain is to be unity at frequency 0 and decline linearly down to gain 0 at frequeney W. We first show that the output functions of the filter have a peak power limitation 5’ at all times (not just the sample sin 2ifWt points). First we note that a pulse 2 7r going into the filter produces 1 sin” ?rWt 2 (?TWt)2 in the output. This function is never negative. The input function (in the general case) can be thought of as the sum of a series of shifted functions sin 27rlV1 a 27rwt where a, the amplitude of the sample, is not greater than 6. Hence the output is the sum of shifted functions of the non-negative foim above with the same coeflicients. These functions being non-negative, the greatest positive value for any t is obtained when all the coefficients a have their maximum positive values, i.e. l/s. In this case the input function was a constant of amplitude 4 and since the filter has unit gain for D.C., the output is the same. Hence the output ensemble has a peak power 5’. The entropy of the output ensemble can be calculated from that of the input ensemble by using the theorem dealing with such a situation. The output entropy is equal to the input entropy plus the geometrical mean gain of the filter; ~wlogG2dJ = ~wlog(~)2dJ = -2W Hence the output entropy is w log 4s -2w = w1og4; C. E. Shannon and the channel capacity is greater than w log $-* 5. We now wish to show that, for small 5 (peak signal power over average white noise power), the channel capacity is approximately C=Wlog 1+; . ( > More precisely C/W log + 1 as G -+ 0. Since the average signal power P is less than or equal to the peak S, it follows that for all S N c 5 kVlog(l +;) 5 lVlog(l -I-s>. Therefore, if we can find an ensemble of functions such that they correspond to a rate nearly W log 1 + g and are limited to band IV and peak S the ( > result will be proved. Consider the ensemble of functions of the following type. A series of t samples have the same value, either +z/s or -<S, then the next 1 samples have the same value, etc. The value for a scrics is chosen at random, probability 3 for +a and $ for -& If this ensemble be passed through a filter with triangular gain characteristic (unit gain at D.C.), the output is peak limited to fS. Furthermore the average power is nearly S and can be made to approach this by taking I sufficiently large. The entropy of the sum of this and the thermal noise can be found by applying the theorem on the sum of a noise and a small signal. This theorem will apply if is sufficiently small. This can be insured by taking i small enough (after 1 is chosen). The entropy power will be S + N to as close an approximation as desired, and hence the rate of transmission as near as we wish to A Mathematical Theory of Communication PART V: THE RATE I;OR A COKTINUOUS SOURCE 27. FIDELITY EVALUATION FUNCTIONS In the case of a discrete source of information we were able to determine a definite rate of generating information, namely the entropy of the under- lying stochastic process. With a continuous source the situation is con- siderably more involved. In the first place a continuously variable quantity can assume an infinite number of values and requires, therefore, an infinite number of binary digits for exact specification. This means that to transmit the output of a continuous source with exac.4recovery at the receiving point requires, in general, a channel of infinite capacity (in bits per second). Since, ordinarily, channels have a certain amount of noise, and therefore a finite capacity, exact transmission is impossible. This, however, evades the real issue. Practically, we are not interested in exact transmission when we have a continuous source, but only in trans- mission to within a certain tolerance. The question is, can we assign a definite rate to a continuous source when we require only a certain fidelity of recovery, measured in a suitable way. Of course, as the fidelity require- ments are increased the rate will increase. It will be shown that we can, in very general cases, define such a rate, having the property that it is possible, by properly encoding the information, to transmit it over a channel whose capacity is equal to the rate in question, and satisfy the fidelity requirements. A channel of smaller capacity is insufficient. It is first necessary to give a general mathematical formulation of the idea of fidelity of transmission. Consider the set of messages of a long duration, jay T seconds. The source is described by giving the probability density, in the associated space, that the source will select the message in question P(X). A given communication system is described (from the external point of view) by giving the conditional probability P*(y) that if message x is produced by the source the recovered message at the receiving point will be y. The system as a whole (including source and transmission system) is described by the probability function P(r, y) of having message I\: and final output y. If this function is known, the complete characteristics of the system from the point of view of fidelity are known. Any evaluation of fidelity must correspond mathematically to an operation applied to I-‘@, y). This operation must at least have the properties of a simple order- ing of.systems; i.e. it must be possible to say of two systems represented by Pl(x, y) and P2(x, y) that, according to our fidelity criterion, either (1) the first has higher fidelity, (2) the second has higher fidelity, or (3) they have C. E. Shannon equal fidelity. This means that a criterion of fidelity can be represented by a numerically valued function: vu% Y)> whose argument ranges over possible probability functions P(x, y). We will now show that under very general and reasonable assumptions the function v(P(x, y)) can be written in a seemingly much more specialized form, namely as an average of a function p(x, y) over the set of possible values of x and y: v(P(x, Y)> = //-P(x, Y> P(X, Y) dx dr To obtain this we need only assume (1) that the source and system are ergodic so that a very long sample will be, with probability nearly 1, typical of the ensemble, and (2) that the evaluation is “reasonable” in the sense that it is possible, by observing a typical input and output x1 and yr , to form a tentative evaluation on the basis of these samples; and if these samples are increased in duration the tentative evaluation will, with proba- bility 1, approach the exact evaluation based on a full knowledge of P(x, y). Let the tentative evaluation be p(x, y). Then the function p(x, y) ap- proaches (as T 4 a) a constant for almost all (x, y) which are in the high probability region corresponding to the system: Pb, Y) --+ wx, Y>> and we may also write Pb,Y) + SJ Pb, YMX, Y> dx, dr since SJP(x, y) dx dy = 1 This establishes the desired result. The function p(x, y) has the general nature of a “distance” between x and y.’ It measures how bad it is (according to our fidelity criterion) to receive y when x is transmitted. The general result given above can be restated as follows: Any reasonable evaluation can be represented as an average of a distance function over the set of messages and recovered mes- sages x and y weighted according to the probability P(x, y) of getting the pair in question, provided the duration T of the messages bc taken sufh- ciently large. 9It is not a “metric” in the strict sense, however, since in general it does not satisfy tither P(X, Y) = P(Y, 2) or P@, y) -t dr, 2) 2 ~6% 2). A Mathematical Theory of Communication 75 The following are simple examples of evaluation functions: 1. R.M.S. Criterion. v = (x(0 -Ym2 In this very commonly used criterion of fidelity the distance function p(x, y) is (apart from a constant factor) the square of the ordinary euclidean distance between the points x and y in the associated function spa05 Pb, Y> = f s0 = [x(t) -y(t)l” dt 2. Frequency weighted R.M.S. criterion. More generally one can apply different weights to the different frequency components before using an R.M.S. measure of fidelity. This is equivalent to passing the difference x(r) -y(l) through a shaping filter and then determining the average power in the output. Thus let 4 = 4) -y(t) and ‘(‘I = I”, e(T)h(t -,-) & then PC%Y> = f oT J(t)2 dt. s 3. Absolute error criterion. PC%Y> = f ! o T 1 x(t) -r(t) I dt 4. The structure of the ear and brain determine implicitly an evaluation, or rather a number of evaluations, appropriate in the case of speech or music transmission. There is, for example, an “intelligibility” criterion in which p(x, y) is equal to the relative frequency of incorrectly interpreted words when message x(t) is received as y(t). Although we cannot give an explicit representation of p(x, y) in these cases it could, in principle, be determined by sufficient experimentation. Some of its properties follow from well-known experimental results in hearing, e.g., the ear is relatively insensitive to phase and the sensitivity to amplitude and fre- quency is roughly logarithmic. 5. The discrete case can be considered as a specialization in which we have C. E. Shannon tacitly assumed an evaluation based on the frequency of errors. The function p(x, y) is then defined as the number of symbols in the sequence y differing from the corresponding symbols in x divided by the total num- ber of symbols in x. 28. TIIE RATE POR A SOURCE RELATIVE TO A FIDELITY EVALUATION We are now in a position to define a rate of generating information for a continuous source. We are given P(X) for the source and an evaluation determined by a distance function p(x, y) which will be assumed continuous in both x and y. With a particular system P(x, y) the quality is measured by v= dx, y) P(x, y) dx dy Furthermore the rate of flow of binary digits corresponding to P(x, y) is R= p(x, Y) pb, Y> 1% p(z>p(r) dx dY* We define the rate RI of generating information for a given quality vr of reproduction to be the minimum of R when we keep v fied at vr and vary P,(y). That is: RI = Min P(x, y) log ‘(‘3 Y) dx ,jy P,(U) ~‘CWY) subject to the constraint: Pb, Y)P(X, y> dx dy. This means that we consider, in effect, all the communication systems that might be used and that transmit with the required fidelity. The rate of transmission in bits per second is calculated for each one and we cl~oose that having the least rate. This latter rate is the rate we assign the source for the fidelity in question. The justification of this definition lies in the following result: Tlgeorenz 21: If a source has a rate RI for a valuation v1 it is possible to encode the output of the source and transmit it over a channel of capacity C with fidelity as near vr as desired provided RI < C. This is not possible if RI > C. The last statement in the theorem follows immediately from the definition of RI and previous results. If it were not true we could transmit more than C bits per second over a channel of capacity C. The first part of the theorem is proved by a method analogous to that used for Theorem 11. We may, in the first place, divide the (x, y) space into a large number of small cells and A Mathematical Theory of Communication 77 represent Lhc situation as a discrete case. This will not change the cvalua- tion function by more than an arbitrarily small amount (when the cells are very small) because of the continuity assumed for p(.z., y). Suppose that Pr(x, y) is the particular system which minimizes the rate and gives RI . We choose from the high probability y’s a set at random containing p, + 4 P members where e --+ 0 as T + Q). With large T each chosen point will be connected by a high probability line (as in Fig. 10) to a set of 2s. A calcu- lation similar to that used in proving Theorem 11 shows that with large T almost all x’s are covered by the fans from the chosen y points for almost all choices of the y’s. The communication system to bc used operates as follows: The selected points are assigned binary numbers. When a message x is originated it will (with probability approaching 1 as T + m) lie within one at least of the fans. The corresponding binary number is transmitted (or one of them chosen arbitrarily if there are several) over the channel by suitable coding means to give a small probability of error. Since RI < C this is possible. At the receiving point the corresponding y is reconstructed and used as the recovered message. The evaluation V: for this system can be made arbitrarily close to ~1, by taking T sufliciently large. This is due to the fact that for each long sample of message ~(1) and recovered message y(f) the evaluation approaches vl (with probability 1). It is interesting to note that, in this system, the noise in the recovered message is actually produced by a kind of general quantizing at the trans- mitter and is not produced by the noise in the channel. It is more or less analogous to the quantizing noise in P.C.M. 29. TIE CALCULATION OF RATES The definition of the rate is similar in many respects to the dctinition of channel capacity. In the former R = Min P,(Y) with P(X) and r~r = P(x, y)&, y) dx dy fixed. In the latter C = Max P(x , y) log !%L~-dx dyP(Z) I-’ with P,(y) fixed and possibly one or more other constraints (e.g., an average power limitation) of the form A = JJ I’(-\., y) X(X, y) dx dy. C. E. Shannon A partial solution of the general maximizing problem for determining the rate of a source can be given. Using Lagrange’s method we consider Z’(x, y) log --z’(xy r) + /.I P(x, y)p(x, y) + Y(X)Z’(X, y)] dx dy ss [ fwP(Y) The variational equation (when we take the tirst variation on Y(x, y)) leads to Py(x) = n(x) e--xp(=*y) where X is determined to give the required fidelity and U(X) is chosen to satisfy ,Ij(x)e-XP(=‘U) dx = 1 s This shows that, with best encoding, the conditional probability of a cer- tain cause for various received y, Z’,,(X) will decline exponentially with the distance function p(x, y) between the x and y is question. In the special case where the distance function p(x, y) depends only on the (vector) difference between x and y, P(% Y> = Pb -Y> we have B(x)e+‘(+-“) dr = 1. s Hence B(z) is constant, say 01, and p&) = a~-~p(‘--y) Unfortunately these formal solutions arc diflicult to cvaluatc in particular cases and seem to bc of little value. In fact, the actual calculation of rates has been carried out in only a few very simple cases. If the distance function p(x, y) is the mean square discrepancy between x and y and the message ensemble is white noise, the rate can bc determined. In that case we have R = Min Ill(x) -ZZ,(z)] = ZZ(r) -Max ZZ,(r) with N = (X - y)‘. But the Max ZZV(x) occurs when y -z is a white noise, and is equal to IV1 log 2*e N where 1Vr is the bandwidth of the message en- semble. Therefore R = WI log 2reQ -11’1 log 2reh’ where Q is the avcragc message power. This proves the following: A Mathematical Theory of Communication Theorem 22: The rate for a white noise source of power Q and band WI r&live to an R.M.S. measure of fidelity is R = WI log $ where N is t:.e allowed mean square error between original and recovered messages. More generally with any message source we can obtain inequalities bound- ing the rate relative to a mean square error criterion. Theorem 23: The rate for any source of band WI is bounded by wllog$ 2 RI W&g; where Q is the average power of the source, Q1 its entropy power and N the allowed mean square error. The lower bound follows from the fact that the max III(~) for a given (x -r)” = N occurs in the white noise case. The upper bound results if we place the points (used in the proof of Theorem 21) not in the best way but at random in a sphere of radius 4Q -N. ACKNOWLEDGMENTS The writer is indebted to his colleagues at the Laboratories, particularly to Dr. H. W. Bode, Dr. J. R. Pierce, Dr. B. McMillan, and Dr. 13. M. Oliver for many helpful suggestions and criticisms during the course of this work. Credit should also be given to Professor N. Wiener, whose elegant solution of the problems of filtering and prediction of stationary ensembles has con- siderably influenced the writer’s thinking in this field. APPENDIX 5 Let St be any measurable subset of the g ensemble, and SZ the subset of thef ensemble which gives S1 under the operation T. Then & = T&s Let 11’ be the operator which shifts all functions in a set by the time X. Then I?& = i?TSz = TII’S, since T is invariant and therefore commutes with 11”. Hence if m[S] is the probability measure of the set S m[II”&] = m[TIIXS2] = m[d&] = m[Sd = m[S11 80 C. E. Shannon where the second equality is by definition of measure in the g space the third since thef ensemble is stationary, and the last by definition of 6 meas- ure again. To prove that the ergodic property is preserved under invariant operations, let Sr be a subset of the g ensemble which is invariant under NX, and let 5’~ be the set of all functionsf which transform into Si. Then HxSl = HAT& = TIIA& = S, so that 11’Sr is included in Si for all X. Now, since m[IIAS21 = m[&l this implies II”& = sz for all X with nt[&] # 0, 1. This contradiction shows that St does not exist. APPENDIX 6 The upper bound, fi, 2 Nr + Nz , is due to the fact that the maximum possible entropy for a power Ni + Nz occurs when we have a white noise of this power. In this case the entropy power is Nr + Nz. To obtain the lower bound, suppose we have two distributions in 12 dimen- sions p(xJ and q(xi) with entropy powers Nr and fl,. What form should p and q have to minimize the entropy power ma of their convolution Y(xi): Y(G) = fi(ri)q(% -ri> dyi * s The entropy HB of Y is given by IIs = -Y(Xi) log Y(X<) dXi* J We wish to minimize this subject to the constraints HI = - J P(G) 1% p(G) dxi Hz= logdx- -sq(xi) i q(xi) We consider then II = -j- 144 1% 44 + Mx> 1% PM + WI(x) 1% &>I dx 611 = -s [I1 + log Y(x)lsY(4 + Ml + log p(x>lsp(x) + P11 + log qbdM4ll ok A Mathematical Theory of Communication If P(X) is varied at a particular argument xi = si, the variation in Y(X) is 6Y(X) = Q(Xi - S,) and 6U = -q(xi -Si) log Y(r\.i) dxi -X log $(.yi) = 0 s and similarly when q is varied. Hence the conditions for a minimum are JrlCxi -Si) log Y(Xi) = -A log p(S,) PCxi -Si) log Y(Xi) = -p log q(Si). s If WC multiply the first by p(Si) and the second by q(si) and integrate with respect to s we obtain II3 = -A III IIS = -p zzz or solving for X and ~1 and replacing in the equalions IIIJ Q(Xi -Si) log Y(Xi) dXi = -II, log p(Si) 112 p(Xi -Si) log Y(Xi) dXi = -113 log j?(Si). s NOW suppose #(Xi) and q(Xi) are normal P(Xi) = !A!& exp -fZA;jX;Xj q(xi) = I$“; exp -~ZBijXiXj. Then T(Xi) will also be normal with quadratic form Cij. If the inverses of these forms are aij, bij, cij then cij = a;j + bij. We wish to show that these functions satisfy the minimizing conditions if and only if aij = Kbij and thus give the minimum 113 under Ihe constraints. First we have log Y(~‘i) = f log ~ 1 Cij 1 -~ZCijXiXj sq(xi -si) log I(%;) = T log $ 1 Cij I -+2;CijSiSj-$Xijbij. C. E. Shannon This should equai 2 T log & I flij I -~zAijS;Sj 1 [ 1 which requires /1 ii = s Cij s 3 In this case A ii = IS Bij and both equations reduce to identities. 2 APPENDIX 7 The following will indicate a more general and more rigorous approach to the central definitions of communication theory. Consider a probability measure space whose elements are ordered pairs (x, r). The variables x, y are to be identified as the possible transmitted and received signals of some long duration T. Let us call the set of all points whose x belongs to a subset Sr of x points the strip over SI , and similarly the set whose y belongs to .I& the strip over SZ . We divide x and y into a collection of non-overlapping measurable subsets Xi and I’; approximate to the rate of transmission R by where .P(Xi) is the probability measure of the strip over Xi P( Vi) is the probability measure of the strip over 1’; P(X;, Ui) is the probability measure of the intersection of the strips. A further subdivision can never decrease RI. For let Xr be divided into X1 = Xi + Xi’ and let P(I’1) = a P(X,) = b + c Ii = b zyx:, Y,) = d P(X:‘) = c P(X:‘, Yl) = e P(Xl, Yl) = d + e Then, in the sum we have replaced (for the Xi, 1’1 intersection) by a! log $ + e log 5. ac It is easily shown that with the limitation we have on b, c, d, e, d f e d-ts< 82” -. bd C. bfc L-1 A Mathematical Theory of Communication and consequently the sum is increased. Thus the various possible subdivi- sions form a directed set, with R monotonic increasing with refinement of the subdivision. We may define R unambiguously as the least upper bound for the RI and write it P(x, Y> R=# P(x, Y) 1% p(x)p(y) dx dY* This integral, understood in the above sense, includes both the continuous and discrete cases and of course many others which cannot be represented in either form. It is trivial in this formulation that if x and u are in one-to- one correspondence, the rate from u to y is equal to that from x to y. If v is any function of y (not necessarily with an inverse) then the rate from x to y is greater than or equal to that from x to v since, in the calculation of the approximations, the subdivisions of y are essentially a finer subdivision of those for v. More generally if y and v are related not functionally but statistically, i.e., we have a probability measure space (y, v), then R(x, v) < R(x, y). This means that any operation applied to the received signal, even though it involves statistical elements, does not increase R. Another notion which should be defined precisely in an abstract formu- lation of the theory is that of “dimension rate,” that is the average number of dimensions required per second to specify a member of an ensemble. In the band limited case 2W numbers per second are sufficient. A general definition can be framed as follows. Letf,(l) be an ensemble of functions and let ~~If&),fddl be a metric measuring the “distance” from fa to Ifa over the time T (for example the R.M.S. discrepancy over this interval.) Let N(e, 6, T) be the least number of elementsf which can be chosen such that all elements of the ensemble apart from a set of measure d are within the distance E of at least one of those chosen. Thus we are covering the space to within t apart from a set of small measure 6. We define the di- mension rate X for the ensemble by the triple limit log N(e, 6, T) X = Lim Lim Lim -___. 6-0 a-10 T-.-a T log E This is a generalization of the measure type delinitions of dimension in topology, and agrees with the intuitive dimension rate for simple ensembles where the desired result is obvious.