CAPTULO 6

CODIFICACIN DE CANAL La codificacin de canales se refiere a la clase de transformacin de seales diseadas para la mejora de la performance de las comunicaciones permitiendo a las seales transmitidas resistir bien los efectos de varios deterioros del canal, como el ruido, interferencias y el fading. Estas tcnicas de procesamiento de seales pueden pensarse como el camino por lograr los costo beneficio (trade-offs) del sistema deseable (por ejemplo performance del error versus ancho de banda , potencia versus ancho de banda). Por que supone Ud. que la codificacin de canal se ha puesto tan popular de manera que provoque estos efectos beneficiosos?. El uso de tcnicas de circuitos integrados de gran potencia (loarge-scale) (LSI) y procesamientos de seales digitales a gran velocidad (high-speed) (DSP) han hecho posible proporcionar tanto como 10 dB de mejora de la performance a travs de estos mtodos. A mucho menos costo que a travs del uso de la mayora de los otros mtodos como transmisores de muy alta potencia o grandes antenas. 6.1 CODIFICACIN DE LA FORMA DE ONDA La codificacin de canales puede ser dividida en dos partes para su estudio. Codificanion de Forma de onda (o diseo de seales) y secuencias estructuradas (o redundancia estructurada), como mostramos en la figura 6.1. La codificacin de la forma de onda trata en transformar la forme de onda en una forma de onda mejor para hacer el proceso de deteccin menos sujeto a errores. La secuencia estructurada trata en transformar la secuencia de datos en mejores secuencias habiendo estructurado la redundancia (bits redundantes). Los bits redundantes pueden luego ser usados para deteccin y correccin de errores. El procedimiento de la codificacin proporciona la seal codificada (siendo la forma de onda o la secuencia estructurada) con las propiedades de distancia mejoradas (entre seales) como aquellos de su contraparte sin codificacin. Primero consideremos algunas tcnicas de codificacin de la forma de onda. Luego, continuamos con la seccin 6.3. tratando las secuencias estructuradas.

Figura 1

6.1.1 Seales Antipodales Y Ortogonales

Seales antipodales y ortogonales han sido discutidos antes: Debemos repetir las caractersticas principales de este tipo de seales. El ejemplo mostrado en la figura 6.2 ilustra la representacin analtica, s1 (t) = -s2 (t)=sin 0t, 0tT, de un set de seales senoidales antipodales, como as tambin las formas de onda y la representacin vectorial. Cules son alguno de los sinnimos o analogas que son usados para describir seales antipodales?. Podemos decir que tales seales son imgenes espejo o que una seal es la negativa de la otra o que las seales estn 180 desfasadas. El ejemplo mostrado en la figura 6.3 ilustra un set de seales ortogonales compuesto por pulsos como forma de onda, descrito por: ( ) ( )tpts =1 0tT

y

( )

=22Ttpts 0tT

1

Donde p(t) es un pulso con duracin = T/2, y T es la duracin del smbolo. Otro set de formas de ondas ortogonales frecuentemente utilizadas en sistemas de comunicacin es el sen(x) y el cos(x) En general, un set de seales si(t) de igual energa, donde i=1,2,.....,M, constituyen un set ortonormal (ortogonal, normalizado a la unidad) s y solo s:

( ) ( ) == 011 0

T

jiij dttstsEz (6.1)

Para i=j Caso contrario

Donde zij es llamado coeficiente de correlacin cruzada, y donde E es la energa de la seal, expresada como :

( )=T i dttsE0

2 (6.2)

La representacin de las formas de ondas en la figura 6.3 ilustra que s1(t) y s2(t) no pueden interferir una con otra dado que son distintas en el tiempo. La representacin vectorial ilustra la relacin perpendicular entre las seales ortogonales. Considere algunas descripciones alternativas de seales o vectores ortogonales.

2

Podemos decir que el producto punto o producto interno de dos vectores diferentes en un set ortogonal debe ser igual a cero. En un espacio de dos o tres dimensiones de las coordenadas cartesianas, podemos describir la seal vectorial, geomtricamente, por ser entre s mutuamente perpendiculares. Podemos decir que un vector tiene proyeccin cero sobre otro, o que una seal no puede interferir con otra, desde que ellos no comparten el mismo espacio sealado. 6.1.2 Sealizacin M-aria Con sealizacin M-ary, el proceso acepta k bits de datos en un tiempo. Le da la instruccin al modulador para luego producir una de M = 2k formas de onda; la sealizacin binara es un caso especial donde k = 1. Para k > 1, la sealizacin M-ary exclusivamente puede considerarse como un procedimiento de codificacin de forma de onda. Para sealizacin ortogonal (Ej. MFSK), como k aumenta aqu mejorando la performance de error o una reduccin en Eb/N0 requerida, al costo de un ancho de banda, sealizacin no ortogonal (Ej. MPSK) manifiesta mejoras en la eficiencia del ancho de banda, al costo del decremento de la performance de error o un aumento en Eb/N0 requerida. Con la apropiada eleccion de la forma de onda de la seal, uno puede tener un costo beneficio (trade off) de la probabilidad del error, la Eb/N0, y la eficiencia del ancho de banda. Trataremos tales costos beneficios (trade-offs) con mayor detalle en el captulo 9.

6.1.3 Codificacion De La Forma De Onda La codificacin de formas de ondas procede a la transformacin de un set de formas de ondas (representar un set de mensajes) dentro de un mejor set de formas de ondas. El mejor set de formas de ondas puede ser usados para proporcionar PB mejorado comparado al set original. Los ms populares de tales cdigos de formas de ondas son llamados como cdigos ortogonales y biortogonales. La codificacin es el esfuerzo de los procedimientos de hacer cada una de las formas de ondas en el set de seales codificadas tan diferentes como sea posible; la meta es dar los coeficientes zij de la correlacin cruzada entre todos los pares de seales, descrito en trminos de integral en la ecuacin 6.1, tan pequeo como sea posible. El valor posible ms pequeo de los coeficientes de una correlacin cruzada ocurre cuando las seales son anticorrelacionadas (zij = -1) : sin embargo, esto solo pude ser logrado cuando el nmero de smbolos en el set es dos (M=2) y los smbolos son antipodales. En general, es posible hacer todos los coeficientes de la correlacin cruzada iguales a cero [1]. Se dice entonces que el set es ortogonal. Los set de seales antipodales son ptimos en el sentido que cada seale es ms distante de otra en el set. Esto se ve en la figura 6.2 donde la distancia d entre los vectores de seal esta dado por Ed 2= , donde E representa la energa de la seal durante un smbolo de duracin T, como se expresa en la ecuacin 6.2. Comparando con las seales antipodales, las propiedades de distancias entre set de seales ortogonales pueden ser pensadas como bastante buenas (dadas por un nivel de energa de la forma de onda). En la figura 6.3 la distancia entre los vectores de seales ortogonales esta dado por

Ed 2= . La correlacin cruzada entre dos seales es una medida de la distancia entre los vectores de seal. La correlacin cruzada ms pequea, es la ms distante entre cada uno de los vectores. Esto puede ser verificado en la figura 6.2, donde las seales antipodales (cuyo zij = -1) son representadas por vectores que estn ms distantes uno de otro; y en la figura 6.3, donde las seales ortogonales (cuyo zij = 0) son representadas por vectores que estn ms cerca entre s que los vectores antipodales. Debe ser obvio que la distancia entre dos formas de onda idnticas es cero, cuyo zij = 1. La condicin de ortogonalidad de la ecuacin 6.1 es presentada en trminos de formas de ondas si(t) y sj(t), donde i,j = 1,..., M, y M es el tamao del set de formas de ondas. Cada forma de onda en el set {si(t)} puede consistir de una secuencia de pulsos. Donde cada pulso es designado con un nivel +1 o 1, que a su vez representa el digito binario 1 o 0, respectivamente.

3

Cuando el set es representado de esta manera, la ecuacin 6.1 puede ser simplificada por expresar que {si(t)} constituye un set ortogonal s y solo s :

uencialaendigitosdetotalnumeroescoincidentnodigitosdenumeroescoincidentdigitosdenumerozij sec

=

=01 Para i=j

Caso contrario (6.3)

6.1.3.1 Cdigos ortogonales

Un set de datos de un bit puede ser transformado, usando codewords ortogonal de dos dgitos cada una, descrito por las filas de la matriz H1 como sigue: set de datos set de codewords ortogonal

(6.4a) 10

=1000

1

Para este, y los siguientes ejemplos, usaremos la ecuacin 6.3 para verificar la ortogonalidad del set de codewords. Para la codificacin de un set de dos bits de datos, extendemos el set anterior a ambos horizontal y vertical, creando la matriz H2.

set de datos set de codewords ortogonal

11011000

=

=

11

111

0111

1000

1000

1000

(6.4b)

El cuadrante debajo a la derecha es el complemento del anterior set de codeword. Continuemos con la misma regla de construccin para obtener un set ortogonal para un set de datos de tres bit.

4

set de datos set de codewords ortogonal

111011101001110010100000

=

=22

223

1001011000111100010110101111000001100110110011001010101000000000

(6.4c)

En general, nosotros podemos construir un set de codeword de Hk, de dimensin 2k x 2k, llamada matriz Hadamard, por un set de datos de k bit desde la matriz Hk-1, como sigue :

=

11

11

kk

kkk (6.4d)

Cada par de palabras en cada set de codeword H1, H2, H3, ........, Hk, tiene tantos dgitos coincidentes como no coincidentes [2], de acuerdo con la ecuacin 6.3, zij = 0 (para i j), y cada uno de los set es ortogonal. As como sealizacin M-ary con un formato de modulacin ortogonal (tal como MFSK) mejora la performance de PB, la codificacin de la forma de onda con un set de seales construidas ortogonalmente, en combinacin con deteccin coherente, produce exactamente la misma mejora. Para seales ortogonales de igual energa igualmente probable, la probabilidad del error de la codeword (smbolo), PE, puede ser limitada superiormente como [2]:

( ) ( )

0

1NEQMMP sE (6.5)

Donde el set de codeword M es igual a 2k, y k es l numero de bit de datos por codeword. La funcin Q(x) es definida por la ecuacin (3.43), y Es=kEb es la energa por codeword. Para un M fijo, mientras la Eb/N0 es incrementada, el limite se vuelve chico, por PE(M)10-3. La ecuacin (6.5) es una buena aproximacin. Para expresar la probabilidad de error del bit, usaremos a continuacin la relacin entre PB y PE, dada en la ecuacin (4.112) y repetida aqu : ( )

( ) 122 1

=

k

k

E

B

kPkP

o ( )( ) ( )1

2/= M

MMPMP

E

B (6.6)

combinando la ecuacin (6.5) con la (6.6), la probabilidad del error del bit puede ser limitada como sigue :

( ) ( )

0

12NkEQkP bkB o ( )

02 NEQMMp sB (6.7)

5

6.1.3.2 Cdigos biortogonales Un set de seales biortogonales de un total de M seales o codewords pueden ser obtenidas desde un set ortogonal de M/2 seales aumentndolo con el negativo de cada seal como sigue:

=

1

1

k

kk

Por ejemplo un set de datos de tres-bit pueden ser transformados dentro de un set de codeword biortogonal como sigue:

set de datos set de codewords biortogonal

111011101001110010100000

=

10010011010111110110110010100000

3

El set biortogonal es en realidad dos set de cdigos ortogonales tal que cada codeword en uno de los set tiene su codeword antipodal en el otro set. El set biortogonal consiste de una combinacin de seales ortogonales y antipodales. Con respecto a zij de la ecuacin (6.1) los cdigos biortogonales pueden ser caracterizados como :

==

==

2,0

2,1

1

Mjijipara

Mjijipara

jipara

zij (6.8)

Una ventaja de un cdigo biortogonal sobre uno ortogonal para un mismo set de datos es que el cdigo biortogonal requiere la mitad de bits de cdigo por codeword (compare las filas de la matriz B3 con aquellas de la matriz H3 presentada antes). Por eso los requerimientos del ancho de banda para los cdigos biortogonales son la mitad de los requerimientos en comparacin a los ortogonales. Como los vectores de seales antipodales tienen mejores propiedades de distancia que los ortogonales, esto no debe ser ninguna sorpresa que los cdigos biortogonales son ligeramente mejor que los ortogonales.

6

Para seales biortogonales de igual energa igualmente probables, la probabilidad del error de la codeword (smbolo) puede ser limitada superiormente como sigue [2]:

( ) ( )

+

00

22

NEQ

NEQMMP ssE (6.9)

el cual se vuelve incrementalmente pequeo para un M fijo a medida que EB/N0 aumenta. PB(M) es una funcin complicada de PE(M); podemos aproximar esto con la siguiente relacin [2] :

( ) ( )2MPMP EB

La aproximacin es bastante buena para M>8. Por consiguiente, podemos escribir:

( ) ( )

+

00

22

21

NEQ

NEQMMP ssB (6.10)

La propuesta de estos cdigos biortogonales mejoro la performance de PB, comparada con la performance de los cdigos ortogonales, y requiere solo la mitad del ancho de banda de los cdigos ortogonales. 6.1.3.3 Cdogos transorthogonal (simplex) Un cdigo generado desde un set ortogonal por la eliminacin del primer digito de cada codeword es llamado cdigo transorthogonal o simples. Este cdigo es caracterizado por :

==

jiparaM

jiparazij

11

1

(6.11)

Un cdigo simplex representa la mnima energa equivalente (en el sentido de probabilidad de error) del set ortogonal igualmente probable. Comparando la performance del error de los cdigos ortogonal, biortogonales y simples, podemos decir que el cdigo simples requiere la mnima Es/N0 para una razn de error de smbolo especificada. Sin embargo, para un valor grande de M, los tres esquemas son esencialmente idnticos en performance de error. La codificacin biortogonal requiere la mitad del ancho de banda que los otros. Pero para cada uno de estos cdigos, requiere que el ancho de banda crezca exponencialmente con el valor de M (y sistemas complejos); por consiguiente, tales esquemas de cdigos son atractivos solo cuando estos grandes anchos de banda estn disponibles.

7

6.1.4 Ejemplo De Un Sistema De Codificacin De La Forma De Onda La figura 6.4 ilustra un ejemplo asignando un mensaje de k bit desde un set de mensajes de largo M = 2k, con una secuencia de pulsos codificados desde un set de cdigo del mismo largo. Cada mensaje de k bit escoge uno de los generadores produciendo una secuencia de pulsos codificados o codeword. La secuencia en el set codificado que reemplaza los mensajes desde un set de formas de onda con propiedades de distancia mejoradas (ejemplo, ortogonal, biortogonal). Para el cdigo ortogonal descrito en la seccin 6.1.3.1 cada codeword consiste de M = 2k pulsos (cdigo representado en bits). De 2k bits de cdigo replaza k bits de mensajes. La secuencia escogida modula una onda portadora que usa PSK binario, entonces, tal que la fase (j = 0 o ) de la portadora durante cada duracin del bit del cdigo, 0tTc, corresponde a la amplitud (j = -1 o 1) del j-simo pulso bipolar en la codeword. En el receptor en la figura 6.5 la seal es demodulada en banda base y alimentada por M correladores (o filtros acoplados). Para los cdigos ortogonales, como aquellos caracterizados por la matriz Hadamard en la seccin 6.1.3.1, la correlacin es realizada sobre la duracin de la codeword que puede ser expresada como T = 2kTc. Para un sistema de comunicacin de tiempo real, los mensajes podran no retrasarse: dado esto, las duraciones de las codeword deben ser iguales que las duraciones de los mensajes, y as, T solo pude ser expresada como T = (log2M)Tb = kTb, donde Tb es la duracin del bit de mensaje. Note que el tiempo de duracin del bit de mensaje es M/k tiempos ms largos que el de un bit de cdigo. En otras palabras, los bits de cdigo o la codificacin de pulsos (que es modulacin PSK) deben moverse a una razon M/k ms rpido que los bits de mensajes. Para tal codificacin ortogonal de formas de onda y un canal AWGN, el valor esperado a la salida de cada correlador, a un tiempo T, es cero, excepto para el correlador correspondiente a la codeword transmitida.

8

Cul es la ventaja de la codificacin ortogonal de la forma de onda comparada con enviar simplemente un bit o un pulso a un tiempo? Uno puede comparar la performance del error de bit con y sin tal codificacin por comparacin de la ecuacin (4.79) por deteccin coherente de la seal antipodal con la ecuacin (6.7) por la deteccin coherente de las codewords ortogonal. Para un largo dado del mensaje de k bit (ejemplo, k = 5) y una deseada probabilidad de error del bit (ejemplo, 10-5), la deteccin de las codewords ortogonal (cada una tiene un mensaje de 5 bit) pudo ser cumplido con aproximadamente 2.9 dB menos de Es/N0 que la deteccin bit por bit de las seales antipodales. (La demostracin es dejada en un ejercicio para el lector en el problema 6.28) Uno podra haber supuesto este resultado por comparacin de la curva de performance para la sealizacin ortogonal en la figura 4.28 con la curva binaria (antipodal) en la figura 4.29. Qu precio pagamos por esta mejora de la performance del error? El costo es ms ancho de banda para la transmisin. En este ejemplo, la transmisin de un mensaje sin codificar consiste de enviar 5 bits. Con codificacin, cuntos pulsos codificados ms son trasmitidos por cada secuencia de mensaje? Con la codificacin de la forma de onda de este ejemplo, cada secuencia de mensaje de 5 bit es representada por M = 2k = 25 = 32 bit de cdigos o pulsos codificados. Los 32 pulsos codificados en una codeword deben enviarse en la misma duracin de tiempo como los 5 bit correspondientes que proviene de ellos. As, el ancho de banda requerido para la transmisin es 32/5 veces que en el caso sin codificar. En general, el ancho de banda necesario para tales seales codificadas ortogonalmente es M/k veces mayor que aquel necesario para el caso sin codificar. Despus, se examinarn maneras ms eficaces de comerciar fuera de los beneficios de codificar contra el ancho de banda [3,4]. 6.2 TIPOS DE CONTROL DE ERROR Antes de que nosotros discutimos los detalles de redundancia estructurada, ahora describiremos las dos formas bsicas de cmo la redundancia es usada para controlar errores. Lo primero, deteccin de errores y retransmisin, utiliza bits de paridad (bits redundantes adheridos a los datos) para detectar que se est produciendo un error. Las terminales receptoras no tratan de corregir los errores, estas simplemente piden que el dato sea retransmitido. Ntese que una conexin de dos caminos es requerida para el dilogo entre el transmisor y el receptor. El segundo tipo de control de error, correccin de error avanzado (FEC), requiere solamente una conexin en una direccin.

9

Adems en este caso, los bits de paridad son designados para la deteccin y correccin de errores. Veremos que no todos los errores pueden ser corregidos : cdigos de correccin de errores son clasificados acorde a su capacidad de corregir.

6.2.1 Conectividad Terminal Con frecuencia terminales de comunicacin son clasificadas acorde a sus conectividades con otras terminales. Las posibles conexiones, mostradas en la figura 6.6, son clasificadas en Simplex (no confundir con el cdigo simple o cdigo transortogonal), Half Duplex y Full Duplex. La conexin Simplex en la figura 6.6a es una conexin en una sola direccin. Las transmisiones son hechas desde la terminal A hacia la terminal B solamente, nunca en una direccin inversa. La conexin Half Duplex en la figura 6.6b es una conexin donde las transmisiones pueden ser hechas en cada direccin pero no simultneamente. Finalmente, la conexin Full Duplex en la figura 6.6c es una conexin de dos caminos, donde las transmisiones pueden ser procesadas en ambas direcciones.

6.2.2 Requerimiento de Repeticin Automtica (Automatic Repeat Request)

Cuando el control de error consiste solamente en deteccin del error, el sistema de comunicacin generalmente necesita proveer un medio para alertar al transmisor que un error est siendo detectado y que una retransmisin es necesaria. Los procedimientos de control de error son conocidos como Automatic Repeat Request o mtodo de consulta de retransmisin automtica (ARQ, Automatic request query). La figura 6.7 ilustra tres de los ms populares procedimientos de ARQ. En cada uno de los diagramas, el tiempo est avanzando desde la izquierda hacia la derecha. El primer procedimiento llamado ARQ Stop-and-waid, es mostrado en la figura 6.7a. Esta requiere una conexin Half Duplex solamente, entonces el transmisor espera por un acknowledgment (ACK) o confirmacin de cada transmisin antes de proceder con la prxima transmisin. En la figura, el tercer bloque de transmisin recibi un error, de esta forma el receptor responde con un ACK negativo, (NAK). El transmisor retransmite su tercer mensaje antes de transmitir su prxima secuencia. El segundo procedimiento ARQ, llamado ARQ continuo con Pullback, es mostrado en la figura 6.7b.

10

Aqu la conexin Full-Duplex es necesaria. Ambas terminales estn retransmitiendo simultneamente, el transmisor esta enviando datos y el receptor est enviando ACK. Ntese que un nmero de secuencia ha sido asignado en cada bloque de datos. Tambin los ACK y NAK necesitan referirse a cada nmero, o sino estos necesitan saber el tiempo de propagacin, para as el transmisor conozca que mensaje est asociado con cada ACK. En el ejemplo de la figura 6.7b, hay una separacin fija de 4 bloques entre el mensaje que est siendo transmitido y el ACK que est simultneamente recibido. Por ejemplo, cuando el mensaje 8 est siendo enviado, un NAK correspondiente al mensaje 4 est siendo recibido. En el procedimiento de ARQ, el transmisor retorna al mensaje de error y retransmite todos los datos del mensaje, comenzando con el mensaje errneo. El mtodo final llamado ARQ con repeticin selectiva, es mostrado en la figura 6.7c. Aqu como en el segundo procedimiento ARQ, una conexin full-duplex es necesaria. Sin embargo en este procedimiento solamente los mensajes errneos son repetidos. Luego el transmisor contina la secuencia de transmisin desde donde se haba enviado el ltimo mensaje antes de la retransmisin del error. La eleccin de cada procedimiento ARQ est relacionada entre los requerimientos para una utilizacin eficiente de las fuentes de comunicacin y de las necesidades para proveer conexin full-duplex. La conectividad Half-duplex requerida en la figura 6.7a es menos costosa que full-duplex : la ineficiencia asociada puede ser medida por los tiempos sin transmisin. La utilizacin ms eficiente ilustrada en la figura 6.7b y c requiere la conexin full-duplex ms costosa. La mayor desventaja del ARQ sobre FEC es que la deteccin de error requiere un equipamiento de decodificacin ms simple y mucho menos redundante que haga la correccin de errores. Tambin ARQ es adaptativo en el sentido que la informacin es retransmitida solamente cuando los errores ocurren. Por otro lado, FEC puede ser deseable en lugar o en adicin de la deteccin de error por algunas de las siguientes razones : 1- Un canal reversible no es disponible o el retardo con ARQ podra ser excesivo. 2- La estrategia de retransmisin no es convenientemente implementada. 3- El nmero de errores esperado, sin correcciones, podra requerir retransmisiones excesivas.

11

6.3 SECUENCIA ESTRUCTURADAS En la seccin 4.8, nosotros consideramos seales digitales por medio de M=2k seales diferentes ( seales M_aria), donde cada forma de onda contiene k bits de informacin. Vimos que en el caso de seales ortogonales M_aria, nosotros podemos decrecer PB incrementando M (expandiendo el ancho de banda). Similarmente, en la seccin 6.1, demostramos que esto es posible, decrementar PB codificando k dgitos binarios dentro de M cdigos ortogonales. La mayor desventaja de las tcnicas de codificacin ortogonales es el uso ineficiente del ancho de banda asociado. Para un cdigo seteado ortogonalmente de M = 2k formas de onda, el ancho de banda requerido para la transmisin es M/K veces que necesit para el caso sin codificacin. En esta y en las secciones subsecuentes nosotros abandonamos las propiedades ortogonales y nos focalizamos en una clase de procedimiento de codificacin, conocidos como cdigo de chequeo de paridad. Como los procedimientos de codificacin de canal son clasificados como secuencias estructuradas porque ellas representan mtodos de redundancia estructurada insertadas dentro las fuentes de datos, as la presencia de errores pueden ser detectados o corregidos. Secuencias estructuradas son divididas dentro de 3 subcategoras, como se muestra en la figura 6.1: Bloque, Convolucional y Turbo. La codificacin de bloques es tratada en este captulo, y los otros son tratados en captulos 7 y 8 respectivamente.

6.3.1 Modelos de Canal

6.3.1.1 Canal discreto sin memoria Un Discrete Memoryless Channel (DMC) es caracterizado por una entrada alfanumrica discreta, una salida alfanumrica discreta y un set de probabilidades condicionales. P(j/i). (1iM), 1jQ), donde i representa un smbolos de entrada M-ary al modulador, j representa el smbolo de salida Q-ary del demodulador y P(j/i) es la probabilidad de recibir j dado que se transmiti i. Cada smbolo de salida del canal depende solamente de la entrada correspondiente, as para una secuencia de entrada U = u1,u2,....um,...un, la probabilidad condicional de la secuencia correspondiente de salida Z = z1,z2,...zm,...zn puede ser expresado como :

(6.12) =

=N

mumzmPuzP

1

)/()/(

En el caso que el canal tenga memoria (por ejemplo ruido o desvanecimiento que ocurre en la apertura), la probabilidad condicional de la secuencia Z se podra necesitar para ser expresada como una probabilidad conjunta de todos los elementos de la secuencia. La ecuacin 6.12 expresa la condicin de sin memoria del canal. El ruido de canal en un canal sin memoria es definido para afectar cada smbolo independientemente de todos los otros smbolos, la probabilidad condicional Z es vista como el producto de las probabilidades independientes de los elementos.

6.3.1.2 Canal binario Simtrico Un canal binario simtrico (BSC) es un caso especial de un (DMC); la entrada y salida alfabtica seteada consiste de los elementos binarios (0 y 1). Las probabilidades condicionales son simtricas :

12

P(0/1) = P(1/0) = p (6.13)

P(1/1) = P (0/0) = 1 - p La ecuacin 6.13 expresa las probabilidades de transicin del canal. Esto es, dado que un smbolo es transmitido en el canal, la probabilidad de que este sea recibido errneamente es p (relacionado con la energa del smbolo), y la probabilidad que este sea recibido correctamente es (1 - p). Como la salida del demodulador consiste en elementos discretos 0 y 1, el demodulador es programado para tomar una decisin Hard sobre cada smbolo. Un sistema de cdigo comnmente usado consiste en datos modulados en BPSK y demodulacin por decisin Hard. Luego la probabilidad de smbolo errneo en el canal es encontrada usando el mtodo discutido en la seccin 4.7.1 y la ecuacin (4.79) siendo : ( )NoEcQp /2= donde Ec/No es la energa del smbolo en el canal por densidad de ruido, y Q(x) es definida en la ecuacin 3.43. Cuando cada decisin Hard son usadas en un sistema de codificacin binario, el demodulador alimenta los dos cdigos de smbolo vlidos o bits de canal hacia el decodificador. Luego desde el decoder operan las decisiones hechas por el demodulador, decodificando con un canal BSC, llamndose Hard-decision decoding.

6.3.1.3 Canal Gaussiano Nosotros podemos generalizar nuestra definicin del DMC para canales alfanumricos que no son discretos. Un ejemplo es el canal Gaussiano con una entrada alfabtica discreta y una salida continua sobre el rango (-,). El canal adiciona ruido a los smbolos. Como el ruido es una variable aleatoria Gaussiana con media cero y varianza 2, la funcin de densidad de probabilidad resultante (pdf) sobre la variable aleatoria recibida z, condicionada sobre el smbolo uk (la probabilidad uk), puede ser escrita como :

( )

= 2

2

2exp

21)/(

kuzukzp (6.14)

Para toda z, donde k = 1,2,...M. Para este caso, un canal sin memoria tiene la misma media como est en la seccin 6.3.1.1. y la ecuacin 6.12 puede ser usada para obtener la probabilidad condicional para la secuencia Z. Cuando la salida del demodulador consiste de un alfabeto continuo o una aproximacin cuantizada de este (con mas de dos niveles de cuantizacion), decimos que el demodulador hace una decisin Soft . En caso de un sistema codificado, el demodulador alimenta cada cdigo cuantizado hacia el decoder. Las decodificaciones hechas por el decodificador que opera con soft decisin usando un canal Gaussiano son llamadas Soft decision decoding. En el caso de un canal Hard-decision, nosotros somos capaces de caracterizar el proceso de deteccin con una probabilidad de smbolo errneo en el canal. Por lo tanto, en el caso de un canal soft-decision, el detector realiza la clase de decisin (soft decisin) que no puede ser marcada como correcta o incorrecta. De este modo, como estas no son decisiones firmes, esta no puede ser una probabilidad de ocurrencia de error; el detector puede solamente formular una familia de probabilidades condicionales o probabilidades de los diferentes tipos de smbolos.

13

Esto hace posible disear decodificadores usando soft-decisions, pero los bloques decodificadores de cdigo soft son sustancialmente ms complejos que decodificadores hard decisions: de esta forma bloques de cdigo son usualmente implementados con decodificadores hard-desicions. Para cdigos convolucionales, ambas implementaciones (soft y hard) son igualmente populares. En este captulo nosotros consideraremos que el canal es simtrico binario (BSC) y por lo tanto el decodificador emplea hard-decisions. En el captulo 7 nosotros discutiremos modelos de canal, as como deteccin hard versus soft para cdigos convolucionales.

6.3.2 Redundancia y Velocidad de Cdigo En el caso de Bloques de cdigo, las fuentes de datos son segmentadas dentro de bloques de K bits de datos, tambin llamados bits de informacin o mensaje de bits : cada bloque puede representar alguno de los 2k mensajes distintos. El encoder transforma cada K-bit de bloque de datos dentro de un gran bloque de n bits, llamado code bit o smbolo de canal. Los (n-k) bits que el encoder suma a cada bloque de datos, son llamados bits redundantes, bits de paridad o Check bit : ellos no llevan informacin nueva. El cdigo es referido en forma (n,k). La tasa de bits redundantes por bits de datos, denotada (n-k)/k para cada bloque es llamada redundancia del codigo; la razon de bit de datos sobre bit totales, k/n es llamada razon de codigo. La razon de codigo- puede ser considerado como la porcin del cdigo que constituye la informacin. Por ejemplo, en una tasa de codigo , cada codigo de bit lleva la mitad de bits de informacin. En este captulo y en los captulos 7 y 8 consideraremos estas tcnicas de codificacin que proveen redundancia incrementando as en ancho de banda requerido para la transmisin. Por ejemplo, una tcnica de control de error que emplea una tasa cdigo (100% de redundancia) requerir doblar el ancho de banda de un sistema no codificado. Por lo tanto, si una tasa de cdigo es usada, la redundancia es 33% y la expansin del ancho de banda es solamente de 4/3. En el captulo 9 consideraremos tcnicas de modulacin / codificacin para canales de banda limitada donde complejidad a cambio de ancho de banda es empleada para una performance de error apropiada.

6.3.2.1 Nomenclatura de los elementos de cdigo Diferentes autores describen los elementos de salida de un encoder en una variedad de maneras: bits de cdigo (code bit), bit de canal (channel bit), smbolos de cdigo (code simbol), bits de paridad (parity bits), smbolos de paridad (parity symbol) los trminos son muy similares. En este texto, para un cdigo binario, los trminos code bits y channel bit son mayormente usados para describir cdigos binarios solamente. Los nombres ms genricos como code symbol y channel symbol son a menudo preferidos porque ellos pueden ser usados para describir cdigos binarios o no binarios igualmente bien. Note que cada code symbol o channel symbol no estn siendo confundidos con el grupo de bits que forman los smbolos de transmisin como fue hecha en el captulo anterior. Los trminos bit de paridad y smbolo de paridad son usados para identificar solamente aquellos elementos de cdigo que representan los componentes de redundancia adheridos a los datos originales.

6.3.3 Cdigos de Chequeo de Paridad

6.3.3.1 Cdigo de chequeo de paridad simple Este usa una suma lineal de los bits de informacin, llamados smbolos de paridad o bits de paridad, para la deteccin de error o correccin.

14

Un cdigo de chequeo de paridad simple es construido sumando un simple bit de paridad al bloque de bits de datos. El bit de paridad toma el valor uno o cero segn sea necesario para asegurar que la suma de todos los bits de la code-word de cmo resultado un nmero par o impar. La operacin de sumar es realizada usando aritmtica de mdulo 2 (lgica OR exclusiva) como se describe en la seccin 2.9.3. Si la suma de paridad es diseada para un resultado par, el mtodo es llamado de paridad par, si este es diseado para que el resultado sea impar, el mtodo es llamado de paridad impar. La figura 6.8a ilustra una transmisin de datos en serie (el bit que esta ms a la derecha es el primer bit). Un bit de simple paridad es sumado (el bit que est ms a la izquierda del bloque) para dar paridad par. En la terminal receptora, el procedimiento de decodificacin consiste en testear que la suma de mdulo 2 de los bits de la codeword resultar cero (paridad par). Si el resultado encontrado es diferente de cero, se sabe que la codeword tiene errores. La tasa del cdigo puede ser expresada como k/(k+1). Usted supone que el decoder automticamente corregir el dgito que es recibido con error? No, esto no puede ser. Este puede solamente detectar la presencia de un nmero impar de bit errneos. (Si un nmero par de bit es invertido, el test de paridad aparecer correcto, que representa el caso de un error no detectable).

Asumiendo que todos los bits errneos son igualmente probables y ocurren independientemente, nosotros podemos escribir la probabilidad de j errores ocurriendo en un bloque de n smbolos como:

( ) 11),(

= nj pp

jn

njP (6.15)

Donde p es la probabilidad que un channel symbol sea recibida con error, y donde :

)!(!/! jnjnjn =

(6.16)

15

Es el nmero de maneras en que j bits de salida de n pueden tener errores. As para un cdigo de deteccin de error de paridad simple, la probabilidad de un error no detectable Pnd con un bloque de n bits es computada de la siguiente manera :

(6.17) ( )=

=

nimparnparanparn

j

jnjnd ppj

nP

2/12/

1

22 12

Ejemplo 6.1 Cdigo de paridad par

Configurar un cdigo (4,3 = n,k)de deteccin de error de paridad par con el smbolo de paridad que aparece como el smbolo que est ms a la izquierda de la codeword. Qu patrn de error puede detectar el cdigo? Computar la probabilidad de un mensaje errneo no detectado, asumiendo que todos los smbolos errneos son eventos independientes y que la probabilidad de un channel symbol errneo es p=10e-3

Solucin Mensaje Paridad Codeword

000 0 0 000 100 1 1 100 010 1 1 010 110 0 0 110 001 1 1 001 101 0 0 101 011 0 0 011 111 1 1 111

El cdigo es capaz de detectar todos los simples y triples patrones de errores. La probabilidad de un error no detectado es igual a la probabilidad que 2 o 4 errores ocurran en algn lugar de la codeword.

( ) 42244

124

pppPnd

+

=

( ) 422 16 ppp += 432 7126 ppp += ( ) ( ) ( ) 6433323 10*61071012106 +=

6.3.3.2 Cdigo rectangular Un cdigo rectangular, tambin llamado cdigo producto, puede ser considerado como una estructura de cdigos paralelos como muestra la figura 6.8b. Primeros nosotros formamos un rectngulo de bits de mensajes comprendiendo M filas y N columnas: luego un chequeo horizontal de paridad es adherido a cada fila y un chequeo vertical es adherido a cada columna, resultando un arreglo de (M+1) *(N+1) de dimensin. La tasa de cdigo rectangular k/n puede ser escrita como : ( ) ( 1*1// ++= NMMNnk )

16

Cunto ms potente es el cdigo rectangular que el cdigo de simple paridad, que solamente es capaz de detectar errores? Ntese que algn simple bit errneo causara que el chequeo de paridad detecte un error en una fila y tambin en una columna. De esta forma, el cdigo rectangular puede corregir algn error simple ya que cada error es nicamente localizado en la interseccin del error detectado en la fila y el error detectado en la columna. Para el ejemplo mostrado en la figura 6.8b, las dimensiones del arreglo son M = N = 5 : de esta forma la figura describe un (36.25) cdigo que puede corregir un error simple localizado en algn lugar de los 36 bits de posicin. Para tal codigo bloque con correccion de errores, nosotros computaremos la probabilidad que el bloque decodificado tiene un error no corregido contando todas las formas en el que un mensaje errneo puede ser hecho. Comenzando con la probabilidad de j errores en un bloque de n smbolos, expresado en la ecuacin 6.15, podemos escribir la probabilidad de un mensaje errneo, tambin llamado un block error o word error, para un cdigo que puede corregir todos los patrones de error t o menores como :

( )+=

=

n

tj

jnj

M pjn

P p1

1 (6.18)

donde p es la probabilidad que un channel symbol es recibido con error. Para el ejemplo en la figura 6.8b, el cdigo puede corregir todos los simples error-patterns (t=1) con el bloque rectangular con N = 36 bits. Entonces, la suma en la ecuacin (6.18) comienza con j = 2 :

( )=

=

36

21

36

j

jnjM ppj

P

cuando p es razonablemente pequeo, el primer trmino en la suma es el dominante; de esta forma, para este cdigo rectangular (36.25) de ejemplo, nosotros podemos escribir :

( )342 12

36ppPM

=

La probabilidad de bit errneo PB depende del cdigo en particular y el decoder. Una aproximacin para PB es dada en la seccin 6.5.3

6.3.4 Porqu Usar Codificacin con Correccin de Error?

Los cdigos de correccin de error pueden ser considerados como un vehculo para afectar varios pro y contras. La figura 6.9 compara 2 curvas representando la performance de bits errneos versus Eb/No. Una curva representa un esquema de modulacin tpica sin codificacin. La segunda curva representa la misma modulacin con codificacin. Seguidamente se demostrarn los cuatro beneficios o pro y contras que pueden ser conseguidos con el uso de codificacin de canal.

17

6.3.4.1 Trade-off 1: Performance de error versus ancho de banda Imagina que un simple y barato sistema de comunicacin de voz ha sido recientemente desarrollado y entregado a un cliente. El sistema no usa codificacin con correccin de error. Considere que el punto operativo del sistema puede ser descrito por el punto A en la figura 6.9 (Eb/No = 8 db y Pb =10e-2). Despus de unas pocas pruebas, hay quejas sobre la calidad de la voz: el cliente sugiere que la probabilidad de bit errneo se baje a 10e-4. La manera ms usual de obtener una mayor performance de error en cada sistema podra afectar un punto operativo moviendo del punto A al punto B, en la figura 6.9. Sin embargo, suponemos que la Eb/No de 8 db es la que mejor est disponible en este sistema. La figura sugiere que un posible Pro y Contra por mover el punto operativo del punto A al punto C sobre la curva codificada puede proveer al cliente una apropiada performance de error. Cul es el costo? Aparte de los nuevos componentes, (codificador y decodificador necesarios), el ancho de banda para la transmisin es ms grande. Codificacin con correccin de error necesita redundancia. Si nosotros asumimos que el sistema es de comunicacin en tiempo real ( que el mensaje no puede ser retrasado), la adicin de bits redundantes obliga una mayor tasa de transmisin, con el uso de ms ancho de banda.

6.3.4.2 Trade-off 2 : Potencia versus ancho de banda Considere que un sistema sin codificacin operando en el punto D de la figura 6.9 Eb/No = 14 dB y Pb = 10e-6, est siendo entregada al cliente. El cliente no ha tenido quejas de la calidad de los datos, pero el equipo est teniendo algun problema como resultado de proveer una Eb/No de 14 dB. En otras palabras, el equipamiento mantiene errores. Si el requerimiento sobre Eb/No o potencia pudiesen ser reducidos, las dificultades podran tambin ser reducidas. La figura 6.9 sugiere un pro y contra por mover el punto operativo del punto D al punto E. Esto es si el cdigo de correccin de error es introducido, una reduccin en el requerido Eb/No puede ser lograda. De ese modo, el pro y contra consiste en que una misma calidad de datos es conseguido, pero los arreglos codificados para una reduccin de potencia o Eb/No. Cul es el costo? Lo mismo que lo anterior, ms ancho de banda. Ntese que para sistemas de comunicacin de tiempo no real, la codificacin con correccin de error puede ser usado con algn diferente postulado.

18

Esto es posible para obtener una apropiada probabilidad de bit errneo o potencia reducida (similar al pro y contra 1 o 2 de arriba) para pagar este precio de retardo en vez de ancho de banda.

6.3.4.3 Ganancia de Cdigo El ejemplo trade-off descripto en las secciones previas ha permitido una reduccin en Eb/No de 14 dB a 9 dB, mientras mantenemos la misma performance de error. En el contexto de este ejemplo y en la figura 6.9 definimos ahora la ganancia de codificacion. Para una dada probabilidad de error de bit, la ganancia de codificacion se define como sobrante o reduccin en Eb/No que se puede realizar con el uso de este cdigo. La ganancia de codificacion G es expresado en dB, tal como:

)()()( dBNoEbdB

NoEbdBG

cu

=

Donde: uNo

Eb

representa la relacin sin cdigo y

cNoEb

con cdigo.

6.3.4.4 Trade-off 3 : Velocidad de dato vs. Ancho de Banda. Considerar que un sistema sin cdigo, operando en el punto D en la figura 6.9 (Eb/No = 14dB y PB= 10e-6) ha sido desarrollado. Asumiendo que no hay problema la calidad del dato y no es de particular necesidad reducir la potencia. Sin embargo en este ejemplo, se supone que el cliente quiere incrementar la velocidad de dato. Recordar la relacin en la ecuacin (5.20 b):

=RNo

PNoEb r 1

Si nosotros no hacemos nada en el sistema, excepto incrementar la velocidad del dato R, la expresin anterior muestra que la Eb/No recibida podra decrecer, y en la figura 6.9 el punto que operamos podra moverse ascendiendo del punto D, digamos a algn punto F. Ahora, movindonos por debajo de la lnea vertical del punto E sobre la curva que representa la modulacin por cdigo. Incrementando la velocidad del dato se ha degradado la calidad del dato. Pero el uso del cdigo de correccin de error se vuelve de igual calidad a igual niveles de potencia (Pr/No). La Eb/No es reducida, pero el cdigo facilita consiguiendo igual probabilidad de error con un Eb/No mas bajo. Cul es el precio que pagaremos para realizar esta elevacin en la velocidad del dato, o agrandar la capacidad?. Al igual que antes incrementar el ancho de banda.

6.3.4.5 Trde-off 4 : Capacidad vs. Ancho de Banda El trde-off 4 es similar al trade-off 3, ambos sistemas logran incrementar la capacidad. El spread-spectrum de acceso mltiple, llamado acceso mltiple por divisin de cdigo (CDMA) y descripto en l capitulo 12, es uno de los mtodos usados en telefona celular. En CDMA, donde los usuarios usan simultneamente la misma parte del espectro, cada uno de los usuarios representa una interferencia para cada uno de los dems usuarios que se encuentran en la misma celda o en celdas prximas. Por lo tanto la capacidad (mximo n de usuarios) por celda es inversamente proporcional a Eb/No (Ver seccin 12.8). En esta aplicacin, una disminucin de Eb/No, produce un pequeo aumento en la capacidad: la codificacin logra una reduccin en la potencia de los usuarios, esto se permite para incrementar l numero de usuarios.

19

Otra vez el costo es un aumento del ancho de banda, pero en este caso, la expansin del ancho de banda de la seal debido al uso del cdigo de correccin de error, es pequea comparada con la mayor importancia de expansin del ancho de banda del spread-spectrum, y por eso, no hay impacto sobre el ancho de banda de transmisin. En cada uno de los ejemplos de trade-off de arriba, un cdigo tradicional comprende una redundancia de bits y seal mas rapida (para un sistema de comunicacin en tiempo real) que ha sido asumido; por lo tanto, en cada caso, el costo fue expandir el ancho de banda. Sin embargo al existir una tcnica de correccin de error, llamada modulacin trellis-coded (cdigo entrelazado) que no requiere saales rapidas o expansin del ancho de banda para un sistema en tiempo real (esta tcnica es descripta en la seccin 9.10).

Ejemplo 6.2 Codificado vs. no codificado

Comparar la probabilidad del error del mensaje para un enlace de comunicacin con y sin el uso del cdigo de correccin de error. Asumiendo que las caractersticas de transmisin sin cdigo son modulaciones BPSK. El ruido Gaussiano Pr/No = 43.776, velocidad del dato R=4800 bits/s. Para el caso del uso del cdigo, y adems asumiendo el uso de un (15.11) de cdigo de correccin de error que es capaz de corregir cualquier patrn de error simple dentro de un bloque de 15 bits. Considerar que el demodulador realiza una decisin hard y por esto colocamos los bits de cdigos demodulados directamente al decodificador el cual produce en las salidas una estimacin del mensaje original.

Solucin siguiendo la ecuacin (4.79)

o

bu N

EQP

2= y

c

c

NEQPc 2=

sea la probabilidad de error de smbolo de canal sin cdigo y con cdigo, respectivamente, donde Eb/No es la energa de bit para la densidad espectral de ruido y Ec/No es la energa del bit-cdigo por la densidad espectral de ruido.

Sin cdigo :

( )dBRNoN

Eb 12.91Pr

0

=

=

y

P Q EN

Qu b=FHGIKJ = =

2 18 24 102 100

5. . x (6.20)

donde fue usada la aproximacin siguiente de Q(x) de la Ecuacin (3.44) fueron usadas: La probabilidad que el bloque del mensaje sin el cdigo fuera recibido en error es 1 menos el producto de la probabilidad que cada bit fuera detectado correctamente. Para esto:

cM

20

( )kucM PP = 11 (6.21) ( ) 411 1012.111 == xPu

donde (1-Pu)11 es la probabilidad de que los 11 bits sin codigo del bloque sean correcto y donde 1.12e-4 es la probabilidad de que al menos 1 bit fuera de los 11 erroneo. Con codigo : Asumiendo un sistema de comunicacin en tiempo real tal que el retrazo es inaceptable, la velocidad de smbolo del canal o bit de cdigo Rc es 15/11, veces la velocidad del bit de dato :

bpsxRc 654511154800 ==

y

)3.8(69.61Pr dBRcNoNo

Eu =

=

La Eb/No para cada bits de cdigo es menor que para el bit de dato en el caso del no uso del cdigo debido ha que se ha incrementado la velocidad de bit del canal, pero la potencia de trasmisin no ha cambiado :

( ) 41036.138.132 ==

= xQ

NoEcQPc (6.22)

Esto se puede ver por simple compararacin de los resultados de la ecuacin 6.20 con aquellos de la Ec. 6.22, esto debido a que fueron sumadas las redundancias, la probabilidad de error de bit del canal ha empeorado. Mayor cantidad de bits son detectados durante intervalos de igual tiempo y con igual potencia disponible: el mejoramiento en el funcionamiento debido al uso del codigo no es aun visible. Ahora computemos la velocidad de codificado del mensaje erroneo usando la ecuacin 6.18 :

cM

( ) ( )==

=

15

2

15115n

j

jjcM PcPcj

P

La sumatoria empieza de j = 2 , dado que el cdigo corrige todos errores simples escritos en un bloque de n = 15 bits. Se obtiene una aproximacin por el uso de solo el primer termino de la sumatoria. Para pc, usamos los valores calculados en la Ec. 6.22:

(6.23) ( ) ( ) 6132 1094.112

15 =

= xppP cccM

Por comparacin de los resultados de las ec. 6.21 con la 6.23 podemos ver que la probabilidad de error del mensaje ha mejorado por un factor de 58, en el ejemplo, debido a el uso del cdigo de correccin de error.

21

Este ejemplo ilustra el comportamiento tpico de todos aquellos sistemas de comunicacin en tiempo real que usan el cdigo de correccin de error. Sumando la velocidad media de seal de redundancia, menos la energa por smbolo del canal, y mas los errores fuera del demodulador. Los beneficios surgen en el comportamiento del decodificador (a razonables valores de Eb/No) que ser mas que compensado por la escasa performance del demodulador.

6.3.4.6 Performance del cdigo a bajos valores de Eb/No

Se urge del lector solucionar el problema 6.5 el cual es similar al ejemplo 6.2. En la parte (a) del problema 6.5 donde se da un Eb/No de 14 dB, el resultado es un mejoramiento en la performance del error del mensaje a travs del uso del cdigo. Sin embargo, en la parte (b) donde el Eb/No se ha reducido a 10 dB, el uso del codificado no produce mejora: en realidad hay una degradacin. Uno podra preguntar, por que la parte (b) manifiesta una degradacin. Despus de todo el mismo procedimiento se usa para aplicar el cdigo en ambos puntos del problema. La respuesta podra encontrarse en el dibujo del cdigo vs. sin cdigo mostrado en la figura 6.9. Precisamente a travs del problema 6.5 tratando con la probabilidad del error del mensaje, y en la figura 6.9 se obtiene la probabilidad de error de bit. , esto se aplica en la siguiente explicacin. En todos estos grficos, hay un cruce entre las curvas (usualmente en algunos valores bajos de Eb/No). La razn por la que se cruzan es que siempre los sistemas con cdigo tendrn alguna capacidad de correccion de error fija. Si hay muchos errores dentro de en bloque que el cdigo sea capaz de corregir, el sistema realizara una lista. Imagine que la Eb/No es reducida continuamente. Que sucede a la salida del demodulador?. Esto producir mas y mas errores. Hasta ahora, un decrecimiento continuo en Eb/No permite eventualmente causar algn umbral para ser alcanzado donde el decodificador se agobie con el error. Cuando este umbral es atravesado, podemos interpretar que se produce un degradamiento causado por una redundancia de bits. Consumiendo energa sin dar ningn beneficio a causa de esto. Esto hace chocar al lector con una paradoja, que operando en una regin (de bajos valores de Eb/No) donde uno podra ver un mejoramiento en la performance del error, es donde el uso del cdigo hace esto peor. Hay sin embargo una clase de cdigo poderoso llamado cdigo turbo que produce un mejoramiento en la performance del error a bajos valores de Eb/No el punto de cruce es menor para el cdigo turbo comparado con el cdigo convencional (estos son tratados en la seccin 8.4). 6.4 CDIGO DE BLOQUE LINEAL El bloque de cdigo lineal (as como los descriptos en la seccin 6.2) son una clase de cdigos de chequeos de paridad que pueden ser caracterizados por (n, k) notacin antes descripta. El codificador transforma un bloque de k digitos de mensajes (vector de mensaje) dentro de un bloque de un largo de n digitos de codeword (vector de cdigo) construido de un alfabeto dado de elementos. Cuando el alfabeto consiste de dos elementos (0 y 1), el cdigo es binario que comprende dgitos binarios (bits). Nuestra discusin de bloque de cdigo lineal es restringida a dgitos binarios, en lugar de otra notacion. Los mensajes de k-bit de 2 secuencias de mensajes distintos referido como k-tuples (secuencia de k dgitos). El bloque de n-bit puede formar como 2

K

n secuencias distintas; referido a n-tuples. El procedimiento de codificado asigna a cada uno de los mensajes de k-tuples uno de los de los n-tuples. Un bloque de codificacin representa una asignacin uno a uno segn el cual los 2 mensajes k-tuples son mapeados nivocamente dentro de un nuevo conjunto de 2 codeword n-tuples: el mapeado puede ser realizado viendo una tabla. Para el codificado lineal, la transformacin de mapeo es, por supuesto lineal.

K2 n2K

K

22

6.4.1 Espacios Vectoriales

El conjunto de todos los n-tuples binarios, Vn, es llamado espacio vectorial sobre un campo binario de dos elementos (0 y 1). En el campo binario habr dos operaciones, suma y multiplicacin, tal que el resultado de todas las operaciones son un conjunto igual de dos elementos. Las operaciones aritmticas de suma y multiplicacin son definidas para la conversin del campo alfabtico (4). Por ejemplo, en el campo binario, la regla de suma y multiplicacin son las siguientes : Suma multiplicacin 00=0 0*0=0 01=1 0*1=0 10=1 1*0=0 11=0 1*1=1 Las operaciones con el smbolo , es igual a la operacin modulo descripta en la seccin 2.9.3. La sumatoria de n-tuples binarios implica siempre sumatoria en modulo-2. Sin embargo para simplificar la notacin siempre usaremos el smbolo + sin circulo.

6.4.2 Subespacios Vectoriales

Un subconjunto S del espacio vectorial Vn es llamado subespacio, si se siguen con las dos condiciones que se mencionan a continuacin : 1- Los vectores de todos ceros esta en S. 2- La suma de dos vectores cualquiera en S esta tambin S. (conocida como la propiedad de cierre). Estas propiedades son fundamentales para la caracterstica algebraica del bloque de codificacin lineal. Suponiendo que Vi y Vj son dos codeword o vectores cdigos, en un bloque de codificacin binaria de (n, k). La codificacin puede ser llamada lineal si y solo si (Vi Vj) es tambin un vector cdigo. Un bloque de codificacin lineal, es un bloque en el cual los vectores fuera del subespacio no pueden ser creados por la suma de codewords (miembros del subespacio). Por ejemplo, el espacio vectorial V4 es totalmente conocido por las siguientes =16 4-tuples : 42 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Un ejemplo de un subconjunto de V4 que forman un subespacio es: 0000 0101 1010 1111 Esto es fcil de verificar cuando se suman dos vectores cualquiera en el subespacio puede solo producir uno de los otros miembros del subespacio. Un conjunto de 2k n-tuples es llamado bloque de codificacin lineal si y solo si este es un subespacio del espacio vectorial Vn de todos los n-tuples. La figura 6.10 ilustra, con una simple analoga geomtrica, la estructura detrs del bloque de codificacin lineal.

Figura 6.10

23

Nosotros podemos imaginar el espacio vectorial Vn comprendido con n-tuples. Dentro de este espacio vectorial existe un subconjunto de n-tuples creando un subespacio. Estos vectores o puntos, se muestran en el punteado entre estos numerosos puntos , representan las verdaderas asignaciones de los codewords.

n2k2 k2

n2

Un mensaje es codificado dentro de los 2k vectores cdigos permisibles, y luego es trasmitido. A causa del ruido en el canal, se produce una versin distorsionada de los codeword (uno de los otros 2n vectores en el espacio n-tuple ) que puede ser recibido. Si el vector es perturbado no es muy diferente (no muy distante de) del verdadero codeword, el decodificador puede decodificar el mensaje correctamente. La verdadera meta en la eleccin de un cdigo en particular, similar a la meta o la verdadera finalidad en la eleccin de un conjunto de modulacin de formas de ondas, pueden ser expuestas en el contexto de la figura 6.10 como sigue : 1- Nosotros nos esforzamos para codificar eficientemente por paquetes el espacio Vn con tantos codewords como sea posible. Esto es equivalente a decir que nosotros solo queremos consumir una cantidad pequea de redundancias (exceso de ancho de banda). 2- Nosotros decimos que los codewords estn apartados unos de otro tanto como sea posible, a fin de que si los vectores experimentan algn error durante la transmisin, ello puede ser detectado y codificado correctamente, con una mayor probabilidad.

6.4.3 Un Ejemplo De Bloque De Codificacin Lineal (6,3)

Examinemos la siguiente asignacin de cdigo que describe un cdigo (6,3). Hay 2k = 23 = 8 vectores mensajes, y por lo tanto 8 codewords. Hay 2n = 26= 64 6-tuples en el espacio vectorial V6: Es fcil comprobar que los 8 codewords mostrados en la tabla 6.1 forman parte del subespacio de V6 (porque tiene el vector con todos ceros y la suma de dos cualquiera codewords producen otros codewords miembros del subspacio) por lo tanto esos codewords representan un bloque de codificacin lineal, como se define en la seccin 6.4.2. Una cuestin natural a preguntarse es como fue el proceso de asignacin de una codeword a un mensaje para el caso particular (6,3)?. No existe una asignacin nica para un cdigo en particular (n, k): sin embargo, tampoco hay una completa libertad de opcin. En la seccin 6.6.3 analizamos los requerimientos y limitaciones que hace funcionar un determinado cdigo. TABLA 6.1 Asignacin de codewords a mensajes

Vector Mensaje Codeword 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1

6.4.4 Matriz Generadora

Si k es muy grande la implementacin de la codificacin resulta prohibitiva su realizacin por observecion. Para un cdigo (127,92) hay 292 o aproximadamente 5x1027 vectores de cdigos.

24

Si el procedimiento de codificado consiste de una simple tabla, imagine el largo de la memoria necesaria para contener un gran numero de codewords. Afortunadamente, es posible reducuir la complejidad generando las codewords a medida que se necesitan, en lugar de almacenarlos. Entonces un conjunto de codewords que forman un bloque de codificacin lineal es un subespacio k-dimencional de un espacio vectorial binarios de n-dimenciones (k

G (6.26)

=

=

100101010110001011

3

2

1

VVV

Donde V1, V2 y V3 son tres vectores linealmente independientes (un subconjunto de los 8 vectores cdigo) que pueden generar todos los vectores cdigos. Ntese que la suma de dos cualquiera de los vectores generadores no produse cualquier otro vector generador dado que entre ellos son independientes (la regla de cierre no se cumple). Generamos las codeword U4 con el cuarto vector mensaje 110 en la tabla 6.1, usando la matriz generadora de la ecuacin (6.26) :

[ ] 3213

2

1

4 .0.1.1011 VVVVVV

U ++=

=

= 1 1 0 1 0 0 + 0 1 1 0 1 0 + 0 0 0 0 0 0 = 1 0 1 1 1 0 (codeword para el vector mensaje 1 1 0) De esta manera los vectores cdigo correspondientes a un vector mensaje es una combinacin lineal de las filas de G. De esto, el cdigo es definido totalmente por G, y el codificador solo puede cargar k filas de G, en lugar del total de 2k vectores cdigos. Para este ejemplo, notamos que el arreglo del generador de dimensin 3x6 en la ecuacin (6.26) reemplaza el arreglo original de codeword de dimensin 8x6 en la tabla 6.1 representando una reduccin en la complejidad del sistema.

6.4.5 Codificador De Bloque Lineal Sistemtico Un codificador de bloque lineal sistemtico (n,k) es un mapeo desde un vector mensaje de k-dimensiones a un codeword de n-dimensiones de tal manera que parte de la secuencia generada coincida con los k dgitos del mensaje. Los restantes (n-k) dgitos son dgitos de paridad. Un codificador de bloque lineal tendr una matriz generadora de :

= kIPG

.

.

.

.

( )( )

( )

=

1..00......................0..10..0..01..

21

22221

11211

knkkk

kn

kn

ppp

pppppp

(6.27)

26

donde P es la porcin del arreglo de paridad del generador de matriz pij = (0 o 1),y Ik es la matriz identidad de k x k (unos en la diagonal principal y ceros en los lugares restantes). Note que con este generador sistemtico, la complejidad del codificador se reduce mas, de esto no es necesario cargar la porcin de la matriz identidad del arreglo. Por convinacion de las ecuaciones (6.26) y (6.27) cada codeword es expresado como :

[ ]xmmmuuu kn ,....,,...., 2121 =( )( )

( )

1..00......................0..10..0..01..

21

22221

11211

knkkk

kn

kn

ppp

pppppp

donde

knii

kikiii

mupmpmpmu

=+++= ......2211

nkniparaknipara

).........1(......)(..........1......

==

dado el mensaje k-tuples

kmmmm ,....., 21= y el vector cdigo general n-tuples

nuuuU ,......,, 21= el vector cdigo sistemtico puede ser expresado como

kkn mmmpppU ,....,,.,...,, 2121 = (6.28) bits de bits de paridad mensaje donde los p son los bits de paridad y los m son los bits de mensaje y donde :

)()(22)(11

22221212

12121111

......

.............

knkkknknkn

kk

kk

pmpmpmp

pmpmpmppmpmpmp

+++=+++=+++=

(6.29)

Los codeword sistemticos son algunas veces escritas a fin de que los bits mensajes ocupen la porcin del lado izquierdo del codeword y los bits de paridad ocupen la porcin del lado derecho.

27

Este reordenamiento no tendr efecto sobre la deteccin de errores o la correccion de errores propios de los cdigos, y no sern mas considerados. Para el ejemplo de cdigo (6.3) en la seccin 6.4.3 los codewords son descriptos como siguen :

[ ]

=

100010001

.

.

.

101110011

.,, 321 mmmU (6.30)

= (6.31) N N N

63

52

41

3

32

2

21

1

31 ,,,,,uuuuuu

mmmmmmmmm +++ La ecuacin (6.31) provee alguna idea dentro de la estructura del bloque de codificacin lineal. Vemos que la redundancia de dgitos son producidas de varias maneras. El primer bit de paridad es la suma del primer y tercer bit de mensaje; el segundo bit de paridad es la suma del primer y segundo bit de mensaje; y el tercer bit de paridad es la suma del segundo y tercer bit de mensaje. Intuitivamente tal estructura nos dice que, comparado con el control de simple paridad o un simple procedimiento de repeticin de dgitos, puede generar una capacidad grandiosa para detectar y corregir errores.

6.4.6 Matriz De Control De Paridad Definimos una matriz H, llamada matriz de control de paridad, que nos permitira la decodificacion de los vectores recividos. Para cada matriz generadora G de (k x n), existe una matriz H de (n-k) x n, tal que las filas de G sean ortogonales a las filas de H: que es G.HT = 0, donde HT es la matriz transpuesta de H, y 0 es la matriz con todos ceros de k x (n-k). H transpuesta es una matriz de n x (n-k) cuyas filas son las columnas de H. Para cumplir los requerimientos de ortogonalidad para un codigo sistemtico, escribimos los componentes de H como:

H=[In-k PT] (6.32) Por lo tanto, la matriz HT es escrita como :

H (6.33a)

=

P

I knT ..........

(6.33b)

=

)(21

)(22221

)(11211

............

..

..1..00..........0..100..01

knkkk

kn

kn

ppp

pppppp

28

Esto es fcil de verificar que el producto de U.HT de cada codeword U, generados por las matrices G y HT , entonces:

0..,........., 2211 =+++= knknT ppppppUH Donde los bits de paridad p1, p2, ..., pn-k son definidos en la ecuacin (6.29). Por lo tanto una vez que la matriz de control de paridad H es construida y cumple con los requerimientos de ortogonalidad, podemos usar la prueba donde una recepcin de un vector es una parte valida del conjunto de codeword. U es una codeword generada por la matriz G si y solo si UHT=0.

6.4.7 Testeo del Sndrome (Syndrome Testing) Hacemos r = r1, r2,.....,rn como el vector recibido (uno de 2n n-tuples) resultado de la transmisin de U = u1, u2,.....,un (uno de 2k n-tuples). Podemos escribir a r como :

r = U + e (6.34) donde e = e1, e2,.....,en es un patrn de error (error pattern) introducido por el canal. Hay un total de 2n 1 patrones de error potenciales distinto de cero en el espacio de 2n n-tuples. El sndrome de r se define como:

S = (U+e)H T (6.35) El sndrome es el resultado de un chequeo de paridad sobre r para determinar si r es un miembro vlido del set de codeword. Si, en efecto r es un miembro vlido, el sndrome S tiene valor cero. Si r contiene errores detectables, el sndrome es distinto de cero. Si r tiene errores corregibles, el sndrome tiene valores distintos de cero que se pueden enmarcar en un patrn de error particular. El decoder, dependiendo de como estn implementados los FEC y ARQ, tomar acciones para localizar los errores y corregirlos (FEC) o, de otra forma, se pedir la retransmisin (ARQ). Combinando las ecuaciones (6.34) y (6.35) tenemos :

S = (U+e)H T = UH T + eH T (6.36)

Sin embargo UH T = 0 para todos los miembros del set de codeword. Por lo tanto :

S = eH T (6.37) El desarrollo anterior, comenzando con la ecuacin (6.34) y terminando con la ecuacin (6.37), es evidente que el test del sndrome, si se hace sobre cualquier vector de cdigo corrupto o sobre el patrn de error que lo causa, produce el mismo sndrome. Una propiedad importante de los cdigos de bloque lineal, fundamentalmente en el proceso de decodificacin, es que el mapeo entre el patrn de error corregible y el sndrome es uno a uno. Esto es importante para entender las siguientes dos propiedades de la matriz de chequeo de paridad: 1. Las columnas de H no deben ser de todos ceros, o de lo contrario un error en la posicin de codeword correspondiente no afectara el sndrome y no se detectara el error. 2. Todas las columnas de H deben ser nicas. Si dos columnas fueran iguales, los errores en esas dos correspondientes condiciones de codeword seran indistinguibles.

29

Ejemplo 6.3 Testeo del sindrome (Syndrome test) Suponemos que el codeword U = 101110 del ejemplo de la seccin 6.4.3 se transmite pero

se recibe el vector r = 001110 (tiene error en el 1 bit de la izquierda). Encuentre el valor del vector sndrome S = rH T y verifique que es igual a eH T.

Solucin S = rH T 1 0 0 0 1 0 = [0 0 1 1 1 0] 0 0 1 1 1 0 0 1 1 1 0 0

= [1,1+1,1+1] = [1 0 0] (sndrome de un vector de cdigo corrupto) Ahora verificamos que el sndrome de arriba es igual al sndrome del patrn de error que a causado el error: S = eH T = [1 0 0 0 0 0] H T = [1 0 0] (sndrome del error pattern)

6.4.8 Correccin de Error

Tenemos detectado un error simple y vemos que el test de sndrome hecho sobre el codeword corrupto o sobre el patrn de error producen sndromes iguales. Esto podra ser un indicio de que no solo se puede detectar el error, sino que hay una correspondencia uno a uno entre el patrn de error corregible y los sndromes, podemos corregir tal patron de error. Podemos arreglar el 2n n-tuples tal que represente los posibles vectores recibidos, en un conjunto, llamado arreglo estandar (standard array), tal que la primera fila contenga todos los codewords, comenzando con la codeword de todos ceros, y la primera columna contiene todos los patrones de error corregibles. Vemos desde las propiedades bsicas de los cdigos lineales (ver seccin 6.4.2) que un vector con todos ceros debe ser un miembro de grupo de codewords. Cada fila, llamada coset, consiste de un patrn de error en la primer columna, llamada coset lider (coset leader), seguida de los codeword perturbados por ese patron de error

(6.38) Vemos que el codeword U1, de todos ceros, juega dos roles, una que es un codeword y tambin puede ser pensado como un patrn de error e1 -patrn que representa que no hay error como r = U.

30

El conjunto contiene 2n n-tuples en el espacio Vn. cada n-tuples aparece solo en un lugar -no se pierden ni estn repetidos. Cada coset consiste de 2k n-tuples. De aqu en adelante hay (2n / 2k) =2n-k coset. El algoritmo decodificador reemplaza un vector errneo (algun n-tuples se excluye de sto en la primer fila) por un codeword vlido desde el tope de la columna que contiene el vector corrupto. Suponemos un codeword Ui (i = 1...... 2k) que se transmite por un canal con ruido y se recibe un vector (errneo o contaminado) Ui + ei. Si el patrn de error ej causado por el canal es un coset lider, donde el indice j = 1...... 2n-k , el vector recibido ser decodificado correctamente dentro del codeword transmitido Ui. Si el patrn de error no es un coset lider, entonces resultar una codificacin errnea.

6.4.8.1 El sndrome de un coset Si ej es un coset lider o patrn de error del coset jth, entonces Ui + ej es un n-tuples en este coset. El sndrome de este n-tuples se escribe como :

S = (Ui+ej)H T = UiH T + ejH T Puesto que Ui es un vector cdigo, Ui H T = 0, lo podemos escribir como la ecuacin (6.37) :

S = (Ui+ej)H T = ejH T (6.39)

El nombre coset es el nombre corto de "grupo de nmeros con caractersticas comunes" Qu miembros de alguna fila dada (coset) tienen en comn? Con la ecuacin (6.39) aclaramos que cada miembro de un coset tienen sndromes iguales. El sndrome de cada coset es diferente al de cualquier otro coset en el cdigo; es el sndrome que se usa para estimar el patrn de error.

6.4.8.2 Decodificacin y correccin de error (Error Correction Decoding) El proceso para la decodificacin y correccin de error es el siguiente :

1) Calcular el sndrome de r usando S=rH T 2) Localizar el coset lider (patron de error) ej, cuyo sndrome es rH T 3) Este patrn de error se asume como el error causado por el canal. 4) El vector recibido corregido, o codeword, se identifica como U = r + ej. Podemos decir que

recuperamos el codeword vlido sustrayendo el error identificado, en la aritmtica del mdulo 2, la operacin de sustraccin es idntica a la de adicin.

6.4.8.3 Localizacin del patrn de error

Volviendo al ejemplo de la seccin 6.4.3 arreglamos 26 n-tuples en un conjunto estndar como se muestra en la figura 6.11. Los codeword vlidos son los 8 vectores de la primera fila, y los patrones de error corregibles son los 7 coset lider distintos de cero de la primera columna. Note que todos los patrones con 1 bit de error son corregibles. Note tambin que despus de haber agotado todos los patrones con 1 bit de error, all permanece alguna capacidad de corregir errores puesto que no tenemos todava contados todos los 64 6-tuples. Hay un coset lider que no est asignado, de ahora en adelante, aqu permanece la capacidad de corregir un patrn de error adicional. Tenemos la flexibilidad de elegir el patrn de error para ser alguno de los n-tuples en el coset remanente. En la figura 6.11 se elige para el final, el patrn de error de 2 bit 010001. La decodificacin ser correcta si, y solo si, el patrn de error causado por el canal es uno de los coset lider.

31

Figura 6.11 Ahora determinamos el sndrome correspondiente a cada una de las secuencias de error corregible a travs del clculo de ej HT para cada coset lider, como sigue : 1 0 0 0 1 0 S = ej 0 0 1 1 1 0 0 1 1 1 0 1 Los resultados son listados en la tabla 6.2. Ya que cada sndrome de la tabla es nico, el decoder puede identificar el patrn de error que le corresponde a cada sndrome. TABLA 6.2 Tabla de Sndrome Look-Up

Error Pattern Sndrome 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1

6.4.8.4 Ejemplo de correccin de error

Como dijimos en la seccin 6.4.8.2 recibimos el vector r y calculamos sus sndromes usando S = rHT. Despues usamos el sndrome para encontrar el correspondiente patrn de error. Este patrn de error es una estimacin del error, y se denota como . El decoder luego suma con r para obtener una estimacin del codeword transmitido :

= r + = (U + e) + = U + (e + ) (6.40)

Si el patrn de error estimado es igual a algn patrn de error actual, esto es, se = e entonces la estimacin es igual al codewor transmitido U. Por otro lado si la estimacin es incorrecta, el decoder estimar un codeword que no fue transmitido y entonces tenemos un error de codificacin indetectable.

Ejemplo 6.4 Correccin de Error Asumimos que transmite el codeword U = 101110 del ejemplo de la seccin 6.4.3 y se

recibe el vector r = 001110. Muestre cmo un decoder, usando la tabla 6.2, puede corregir el error.

32

Solucin El sndrome de r se calcula cmo :

S = [0 0 1 1 1 0] HT = [1 0 0] Usando la tabla 6.2 el patrn de error correspondiente para el sndrome de arriba se estima para ser: = 1 0 0 0 0 0 El vector correcto se estima haciendo: = r + = 0 0 1 1 1 0 + 1 0 0 0 0 0 = 1 0 1 1 1 0 Puesto que el patrn de error estimado es el patrn de error actual en este ejemplo, el procedimiento de correccin de error produce = U. Note que el proceso de decodificar un codeword errneo y despus corregir el error se puede comparar con una analoga medica comun.

6.4.9 Implementacin del Decoder

Cuando el cdigo es corto como en el caso del cdigo (6.3) descripto en la seccin previa, el codeword se puede implementar con un circuito simple. Considere los pasos que el decoder debe hacer: 1) calcular el sndrome, 2) localizar el patrn de error y 3) realizar la suma del mdulo 2 del patrn de error y el vector recibido (la cual elimina el error). En el ejemplo (6.4) comenzamos con un vector errneo y vimos como estos pasos construyen el vector correcto (codeword). Ahora consideramos el circuito de la figura 6.12, hecho de compuertas AND y X-OR que pueden lograr un igual resultado para algn patrn de error simple en el cdigo (6.39). De la tabla 6.2 y la ecuacin 6.39, podemos escribir una expresin para cada uno de los dgitos del sndromes en trminos de los dgitos del codeword recibido como :

S = rH T 1 0 0 0 1 0 S = [r1 r2 r3 r4 r5 r6] 0 0 1 1 1 0

0 1 1 1 0 1 y s1 = r1 + r4 + r6 s2 = r2 + r4 + r5 s3 = r3 + r5 + r6 Usamos ests expresiones de sndrome para cablear el circuito de la figura (6.12). La compuerta X-OR es la misma operacin que la aritmtica del mdulo 2 y de ah que usamos este smbolo . Un pequeo crculo en la terminacin de algunas lneas que entran en las compuertas AND indican la lgica "complemento de la seal".

33

La seal corrompida entra al decoder a dos lugares simultneamente. En la parte de arriba del circuito se calcula el sndrome, y en la parte de abajo el sndrome se transforma a su correspondiente patrn de error. El error se elimina sumando sto (anterior) al vector recibido construyendo as el codeword correcto. Note que por razones didcticas, la figura (6.12) ha sido dibujada para enfatizar los pasos de decodificacin algebraica -clculo de sndrome, patrn de error y salida corregida-. En el mundo real un cdigo (n,k) usualmente se configura en forma sistemtica. El decoder no necesitar entregar el codeword entero, su salida consistir de bits de datos solamente. De aqu que el circuito de la figura (6.12) est simplificado por la eliminacin de compuertas que se muestran con un sombreado. Para cdigos largos, como la implementacin es muy compleja, y las tcnicas de decodificacin preferidas conservan la circuitera usamos una aproximacin secuencial en lugar de estos mtodos en paralelo [4]. Es importante aclarar que la figura (6.12) ha sido configurada solo para detectar y corregir patrones de error simples para el cdigo (6.3). El control de error para un patrn de error doble requerira una cirtuitera adicional.

6.4.9.1 Notacin de vector Los codewords, patrones de error, vectores recibidos y los sndromes han sido denotados por los vectores U, e, r y S respectivamente. Para una simple notacin, el subndice para denotar un vector en particular se descarta. Sin embargo, para ser precisos, cada uno de los vectores U, e, r y S son uno de un juego (set) con la forma general :

Xj = {x1, x2,.......xi,...} Considere el rango de los ndices j e i en el contexto del cdigo (6.3) en la tabla (6.1). Para el codeword Uj, el ndice j = 1,....,2k indica que hay 23 = 8 codewords distintos y en ndice i = 1,....,n indica que cada codeword es de 6 bits. Para un patrn de error corregible ej, el ndice j = 1,....,2n-k indica que hay 23 = 8 coset lider (7 patrones de error distintos de cero), y en ndice 1 = 1,....,n indica que cada patrn de error es de n = 6 bit.

34

Para el vector recibido rj, el indice j = 1,.....,2n indica que hay 26 = 64 posibles n-tuples que pueden ser recibidos y el ndice i = 1,....,n indica que cada n-tuple recibido es de n = 6 bits. Finalmente, para el sndrome Sj, el indice j = 1,.....,n-k indica que cada sndrome es de n-k = 3 bits. En este captulo el ndice a menudo se deja de lado y los vectores Uj, ej, rj y Sj se denotan como U, e, r y S respectivamente. El lector debe saber que estos vectores estn referidos a un ndice, incluso estos no estn por haberse escrito en notacin simple. 6.5 DETECCIN DE ERROR Y CAPACIDAD DE CORRECCIN

6.5.1 Peso Y Distancia De Vectores Binarios Debe quedar claro que no todos los patrones de error puedern ser decodificados correctamente. El peso de Hamming w(u) (Hamming weight) de un codeword U es el nmero de elementos distintos de cero en U. Para un vector binario equivale a nmero de unos en el vector. Por ejemplo, si U = 100101101, entonces W(u)=5, la distancia de Hamminig entre dos codeword U y V, d(U,V) se define como el nmero de elementos en el cual difieren, por ejemplo : U = 1 0 0 1 0 1 1 0 1 V = 0 1 1 1 1 0 1 0 0 d(U,V) = 6 Por las propiedades de adicin del mdulo 2, notamos que la suma de dos vectores binarios es otro vector cuyos unos binarios estn localizados en las posiciones en la cual los dos vectores difieren, por ejemplo : U + V = 1 1 1 0 1 1 0 0 1 De esta manera observamos que la distancia de Hamming entre dos codewords es igual al peso de Hamming de la suma, esto es, d(U,V) = w(U,V). Tambin vemos que el peso Hamming de un codeword es igual a su distancia de Hamming con el vector de todos ceros.

6.5.2 Mnima Distancia De Un Cdigo Lineal Considere un jugo (set) de distancias entre todos los pares de codewords en el espacio Vn. El miembro mas pequeo del set es la mnima distancia del cdigo y se denota como dmin. Por qu supones que tenemos inters en la mnima distancia; por qu no la mxima distancia? La mnima distancia, como el eslabn ms dbil en una cadena, nos da una medida de la capacidad mnimo del cdigo y por consiguiente caracteriza la fuerza del cdigo. Como discutimos antes, la suma de dos codeworsd produce otro codeword miembro del subespacio. Esta propiedad de cdigos lineales se define simplemente como : Si U y V son codewords, entonce W = U + V debe ser un codeword. Por eso la distancia entre dos codeword es igual al peso de un tercer codeword : esto es, d(U,V) = w(U+V) = w(W). De esta manera la mnima distancia de un cdigo lineal puede ser averiguada sin examinar la distancia entre todas las combinaciones de los pares de codewords. Solo necesitamos examinar el peso de cada codeword (excluyendo el codeword de todos ceros) en el subespacio; el mnimo peso corresponde a la mnima distancia, dmin. Igualmente dmin corresponde a la mnima distancia del set entre el codeword de todos ceros y todos los otros codewords.

35

6.5.3 Deteccin y Correccin de Error La tarea del decoder, teniendo el vector r (recibido), es estimar el codeword transmitido Ui. La estrategia ptima del decoder se puede expresar en trminos de el algoritmo de "mxima probabilidad" (ver apndice B) como sigue: Decidir en favor de Ui si :

(P(rUi) = max P(rUj) (6.41) sobre todo Uj Ya que para el canal simtrico binario (BSC), la probabilidad de Ui con respecto a r es inversamente proporcional a la distancia entre r y Ui, podemos escribir : Decidir en favor de Ui si

d(r,Ui) = min d(r,Uj) (6.42) sobre todo Uj En otras palabras el decoder determina la distancia entre r y cada uno de los posibles codeword transmitidos Uj, y selecciona cmo ms probable a Ui por lo cual

d(r,Ui) d(r,Uj) para i, j + 1,.....,M y i j (6.43)

donde M = 2k es el tamao del grupo de codeword. Si el mnimo no es nico, la eleccin entre mnimas distancia de codewords es arbitraria. Las distancias mtricas son tratadas ms adelante en el captulo 7. En la figura 6.13 la distancia entre dos codewords U y V se muestran usando regla calibrada en distancia de Hamming. Cada punto negro representa un codeword corrupto. La figura 6.13a ilustra la recepcin del vector r1, el cual est distanciado 1 de U a 4 de V. Un decoder de correccin de error, siguiendo la estrategia de mxima probabilidad, seleccionara U al recibir r1. Si r1 fue el resultado de un error de 1 bit para un vector de cdigo transmitido U, el decoder ha corregido bien el error. Pero si r1 ha sido el resultado de una corrupcin de 4 bits para el vector de cdigo transmitido V, el resultado es un error decodificado. Similarmente, un doble error en la transmisin de U nos da un vector recibido r2, el cual est distanciado 2 de U y 3 de V, como se muestra en la figura 6.13b. Aqu tambin el decoder seleccionar U al recibir r2. Un triple error en la transmisin de U nos dar un vector recibido r3 que se distancia 3 de U y dos de V, como muestra la figura 6.13c. Aqu el decoder seleccionara V al recibir r3, y se producir un error en la decodificacin. En la figura 6.13 est claro que si la tarea es la deteccin del error y no la correccin , un vector corrupto -caracterizado por un punto blanco y representando un error de 1 bit, 2, 3, o 4 bit- puede ser detectado. Sin embargo, cinco errores en la transmisin puede resultar un codeword V siendo recibido cuando U era actualmente transmitido, tal que error sera indetectable.

36

De la figura 6.13 podemos ver que las capacidades de deteccin y correccin de error de un cdigo estn relacionadas con la mnima distancia entre codewords. La lnea de decisin en la figura tiene el mismo propsito en el proceso de decodificacin como en el de modulacin, para definir las regiones de decisin. En la figura 6.13, por ejemplo, el criterio de decisin de elegir U si r cae en la regin 1, y elegir V si r cae en la regin 2, ilustra cmo un cdigo (con dmin = 5) puede corregir dos errores. En general, la capacidad de correccin de error t de un cdigo se define como el mximo numero de errores corregibles garantizados por codeword, y se escribe [4].

=2

1mindt (6.44)

donde [x] significa el entero ms grande para no exceder x. A menudo, un cdigo que corrige posibles secuencia de t o menos errores, puede tambin corregir secuencias de t+1 errores. Esto se puede ver en la figura 6.11. En este ejemplo dmin= 3, y as, de la ecuacin (6.44), podemos ver que todos los patrones de error de t = 1 bit son corregibles. Tambin, un simple patrn de error de t-1 o dos bits es corregible. En general, un cdigo lineal de correccin de t-errores(n, k) es capaz de corregir un total de 2n-k patrones de error. Si un bloque de cdigos de correccin de t-errores se usa para la correccin de error sobre un canal simtrico binario (BSC) con probabilidad de transicin p, la probabilidad de mensaje errneo , PM, que el decoder cometa una decodificacin errnea, y que el block de n-bit es error, puede ser calculado usando la ecuacin (6.18) como un lmite superior :

+=

n

tj

jnjB ppj

nP

1)1( (6.45)

El lmite se vuelve una igualdad cuando el decoder corrige todas las combinaciones de errores e incluso los errores, pero no las combinaciones de errores mayores que t. Algunos decoders se llaman decoders de distancia lmite. La probabilidad de bit de error decodificado PB, depende de un cdigo y un decoder particular. Esto se puede expresar con la siguiente aproximacin.

+=

=

n

tj

jnjB ppj

nj

nP

1)1(1 (6.46)

Un cdigo de bloque (blok code) necesita detectar los errores antes de corregirlos. O, puede usarse para deteccin de error solamente. Debe quedar claro de la Figura 6.13 que ningn vector recibido caracterizado por un punto negro (un codeword corrupto) debe ser identificado como un error. Por lo tanto, la capacidad de deteccin de error se define en trminos de dmin como :

e = dmin 1 (6.47) Un cdigo de blok (blok code) con distancia mnima dmin garantiza que todos los patrones de error de dmin - 1 o menos errores pueden ser detectados. Semejante cdigo tambin es capaz de detectar una l