la teoría de la información y codificación

Upload: buyesyohan

Post on 16-Oct-2015

59 views

Category:

Documents


0 download

TRANSCRIPT

LA TEORA DE LA INFORMACIN Y CODIFICACIN Es la ciencia que trata la informacin como un recurso que puede ser medido, convertido a smbolos (generalmente en Bits) y transmitido de un lugar a otro por medio de un canal. En general la teora de la informacin considera los soportes y los smbolos que permiten la transmisin. No considera la informacin misma en su significado ni su veracidad.La teora de la informacin se ocupa de la descripcin matemtica y evaluacin de los mtodos y transmisin, conservacin, extraccin, clasificacin y medida de la informacin.Los smbolos que permiten la codificacin de la informacin y su transmisin poseen propiedades fundamentales que sern analizadas como base para la construccin de cdigos apropiados para ser usados a travs de canales. Dichas propiedades de los smbolos se relacionan estrechamente con la cantidad de informacin que puedan contener.TEOREMA DE SHANNONEn teora de la informacin, el teorema de Shannon-Hartley es una aplicacin del teorema de codificacin para canales con ruido. Un caso muy frecuente es el de un canal de comunicacin analgico continuo en el tiempo que presenta un ruido gausiano.El teorema establece la capacidad del canal de Shannon, una cota superior que establece la mxima cantidad de datos digitales que pueden ser transmitidos sin error (esto es, informacin) que pueden ser transmitidos sobre dicho enlace de comunicaciones con un ancho de banda especfico y que est sometido a la presencia de la interferencia del ruido.En las hiptesis de partida, para la correcta aplicacin del teorema, se asume una limitacin en la potencia de la seal y, adems, que el proceso del ruido gausiano es caracterizado por una potencia conocida o una densidad espectral de potencia. La ley debe su nombre a Claude Shannon y Ralph Hartley.CODIFICACIN DE LA FUENTEEs el proceso por el cul, la salida de una fuente de informacin, se convierte en una secuencia binaria. El elemento que realiza ste proceso se conoce como codificador fuente (Codec). Alternativamente es la accin de asignar dgitos binarios a secuencias de smbolos que conllevan la informacin.

Fuente deInformacinCodificador Fuente

X (smbolos)salida binariaUno de los objetivos es el de minimizar la rata promedio de bits, necesarios para la representacin de la informacin, reduciendo la redundancia de la fuente. Existe una longitud de cdigo, y una eficiencia de cdigo. La eficiencia de la codificacin procura en aproximar la longitud promedio de las palabras de cdigo (nmero promedio de dgitos binarios), a la entropa de la fuente. CAPACIDAD DE CANALEnTeora de la Informacin, lacapacidad de un canalde comunicacin es la cantidad mxima deinformacinque puede transportar dicho canalde forma fiable, es decir, con una probabilidad de error tan pequea como se quiera. Normalmente se expresa en bits/s (bps). Existen dos definiciones equivalentes entre s del concepto de capacidad de un canal, una es para canales de tiempo continuo y la otra es para canales de tiempo discreto.Capacidad de un canal discreto. En un canal discreto sin memoria:Ejemplos de canal Canal binario sin ruido Canal ruidoso con salidas no solapadas Mquina de escribir ruidosa Canal binario simtrico (BSC) Canal binario con borrado (BEC) Canal MUC (M-ary Uniform Channel)

La capacidad de un canal discreto sin memoria viene dada por:

Ejemplo: Canal Simtrico Binario (BSC)I(X;Y) = H (Y) - H (Y|X) = H (X) - H (X|Y)H (X|Y) = H (X|Y=0)*P (Y=0) + H (X|Y=1)*P(Y=1)H (X|Y=0) = H (X|Y=1) = Pelog (1/Pe) + (1-Pe) log (1/ 1-Pe) = Hb (Pe)H (X|Y) = Hb (Pe) => I(X; Y) = H(X) - Hb (Pe)H (X) = P0 log (1/P0) + (1-P0) log (1/ 1-P0) = Hb (p0)=> I (X; Y) = Hb (P0) - Hb (Pe)

Definicin para canales discretos

Un canal discreto (sin memoria) est definido por el alfabeto de entrada, , que es el conjunto de smbolos que pueden ser transmitidos por el canal el alfabeto de salida, , que es el conjunto de smbolos que pueden ser recibidos a la salida del canal las relaciones estadsticas entre los smbolos de entrada y los de salida , esta informacin viene definida por la matriz de probabilidades condicionadas del canal donde Se define la entropa de entrada, entropa de salida y entropa de entrada condicionada por la salida como

La informacin mutua entre la entrada y la salida del canal la denotamos por y es una medida de lo que el conocimiento de la entrada reduce la incertidumbre sobre la salida y viceversa

Esta informacin mutua depende de la distribucin de probabilidad de la entrada . Para una determinada distribucin de entrada, alcanza un mximo, este mximo es precisamente lo que se conoce como la capacidad del canal

Codificacin para canal binario simtrico.Canal binario simtrico El canal simtrico mas utilizado es el llamado canal binario simtrico, el nombre binario quiere decir que n = m = 2, es decir tanto el alfabeto de entrada como el de salida tienen dos elementos. Denotando estos por 0 y 1 en ambos alfabetos el esquema del canal binario simtrico y su matriz son0 pp1 p

Ejemplos de canales discretos Canal binario simtrico

Canal binario simtrico, la probabilidad de error de bit es p.

Para el caso del canal binario simtrico con probabilidad de error de bit p, su capacidad viene dada por

La funcin es una funcin que aparece mucho en teora de la informacin. Se trata de una funcin cncava (y por tanto cumple la desigualdad de Jensen) y alcanza su mximo, igual a 1, cuando p = 0.5, por otro lado, cuando p = 0 o p = 1 vale 0.La capacidad de este canal es cero cuando p = 0.5, esto tiene sentido ya que en este caso el canal confunde los ceros y los unos con igual probabilidad lo que significa que es un canal inservible para enviar informacin, su capacidad es nula.Note que si un canal tuviese probabilidad de error de bit p = 1 eso no significa que sea un canal malo, todo lo contrario. Bastara con invertir los bits antes de enviarlos para tener un canal ideal (con probabilidad p = 0).

Canales continuos y comparacin de sistemas:

Vamos a comenzar con la medida de la informacin de una fuente que emite una continua seal. El material puede parecer pesado va al principio, pero entonces a hacer un poco su posiciones razonables sobre la transmisin de seales continuas para expresar canal de capacidad en trminos de ancho de banda y la relacin seal-ruido, un resultado conocido como la ley de Hartley-Shannon. Este resultado nos lleva a la definicin de una comunicacin idea sistema, que sirve como un estndar para la comparacin del sistema y una gua para el diseo de sistemas de comunicacin.

Canales analgicos para transmitir informacin Capacidad del canal: Mxima velocidad a la que se pueden transmitir los datos en un canal o ruta de comunicacin de datos Conceptos relacionados con la capacidad del canal Velocidad de transmisin de datos: bps a la que se pueden transmitir los datos Ancho de banda (W) (Hz): Ancho de banda de la seal transmitida Transmisor Naturaleza del medio Ruido: Nivel medio del ruido a travs del camino de transmisin Tasa de errores (p): Tasa a la que ocurren los erroresInformacin contina.Continuo de informacin Una fuente de informacin continua produce una seal variable en el tiempo x (t). Vamos a tratar el serie de seales de posibles como un conjunto de formas de onda generadas por algunos al azar proceso, supone que ergdica. Nos daremos por supuesto que an ms el proceso tiene una finita ancho de banda, lo que significa que x (t) ha sido completamente caracterizada en trminos de la muestra peridico valores. Por lo tanto, en cualquier instante de muestreo, la coleccin de valores de muestra posible constituye una variable X descrito por su densidad de probabilidad funcin p (x).

La cantidad media de informacin por muestra el valor de x (t) se mide por la funcin de entropa donde, como antes, la base logartmica es b = 2. Esta expresin ha sirnilar iti es obvia a la definicin de la entropa de una fuente discreta. Sin embargo, la ecuacin. (I) resulta como una medida relativa de la informacin en lugar de una medida absoluta. El entropa absoluta de una fuente continua puede, en principio, debe definirse desde el siguiente limitar la operacin.

Capacidad de canal contino. La definicin de capacidad para canales continuos es un poco diferente y exige utilizar el Teorema del muestreo y algunos otros conceptos de teora de la seal, adems de los conceptos puramente estadsticos vistos en el apartado anterior.

Ampliando los estudios del fsico Harry Nyquist, compaero en los Laboratorios Bell, Claude Shannon demostr en 1949 que la capacidad terica mxima de un canal de comunicaciones limitado en banda con ruido AWGN (ruido blanco aditivo gausiano) responde a la ecuacin:bits/s (bps)La ecuacin anterior muestra que la capacidad de un canal est limitada por su ancho de banda (B) y por su relacin seal/ruido (SNR). En trminos de eficiencia espectral resulta:bps/HzEs decir, la eficiencia espectral mxima depende de la calidad del canal (de su nivel de ruido).CODIFICACIN DEL CANALSu propsito: es el de disear cdigos que permitan una ptima transmisin de informacin digital sobre el canal. En ltima instancia permite desarrollar tcnicas eficientes para la deteccin y correccin de errores.La seal puede provenir de un codificador fuente de una fuente binaria directamente.Fuente deInformacinCodificador de Canal

Secuencia de bitssecuencia modificadaFuente deInformacinCodificador de CanalCodificador Fuente

X (smbolos)salida binariasecuencia modificada

TEOREMA: Dada una fuente discreta, sin memoria, [X], con una entropa H(x), y un canal con capacidad C, si H(X) < / = C, existe un esquema de codificacin, para el que la salida de la fuente, pude transmitirse por el canal, con una arbitrariamente pequea probabilidad de error. Igualmente, si H(x) > C, no es posible la transmisin libre de errores. Es posible el Cdigo, pero no se nos dice cul es.Si denominamos S = { s1, s2, ...sj } al conjunto de smbolos de un alfabeto, S; definimos un cdigo, como la correspondencia de todas las secuencias posibles de smbolos de S, a secuencias de smbolos de algn otro alfabeto X = { x1, x2, ....xj } , S recibe el nombre de alfabeto fuente, y X alfabeto cdigo.

Estos procesos de codificacin, implican la adicin de bits, al paquete original de transmisin (redundancia); generando algoritmos para que le receptor detecte y corrija posibles errores sobre el mismo bloque recibido. Hay incremento de ancho de banda y de recursos para manipularlos.Existen bsicamente dos procesos: CODIGOS DE BLOQUES, en los cules entran k smbolos al codificador, y salen n smbolos. El codificador no pose memoria, n > k. El mensaje binario, o la secuencia de datos se divide en bloques secuenciales, cada uno de k bits de largo, y cada k bits bloque, se convierte en un bloque de n bits, n > k, el bloque resultante es llamado un (n,k) , cdigo bloque. Existen los cdigos lineales y los cclicos. Ac estn por ejemplo entre los cclicos: Codificacin Hamming, BCH, Reed Solomon, Reed Miller y Golay. Siempre se asignan bloques adicionales de una manera fija a las secuencias de entrada. El otro proceso, lo constituyen los CDIGOS CONVOLUCIONALES, que constituyen un proceso de codificacin con memoria. Entran k smbolos y salen n smbolos; n smbolos de salida se ven afectados por v*k smbolos de entrada (v . 0). Hay memoria, porque la secuencia de salida depende de un numero definido de entradas previasAutomatic Request (ARQ), es simple, eficiente en manejo de ancho de banda, y presupone la existencia de bidireccionalidad en el canal. (ACK, NAC ).Forward Error Correction (FEC), es til en canales simples, en canales con altos retardos de transmisin, y permite altas velocidades en la comunicacin.