La Modulación Codificada Entramada (TCM) en los nuevos ...sappi.ipn.mx/cgpi/archivos_anexo/20071367_5395.pdfW, la densidad espectral de potencia del ruido N 0, y la potencia de la

Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 1

La Modulación Codificada Entramada (TCM) en los

nuevos estándares de telecomunicaciones Registro asignado por la SIP: 20071367

Periodo de realización: Enero 2007 - Diciembre 2007

Director de proyecto:

Miguel Sánchez Meraz Ext. 54755

[email protected]

Resumen.- Se realizó un estudio de la aplicación de la técnica de Modulación Codificada Entramada en los nuevos estándares de comunicaciones. Se desarrollaron módulos de software para simular las etapas de una transmisión TCM. Se evaluó el desempeño de diferentes configuraciones de sistemas de comunicación que operan con la técnica TCM.

Introducción.- El uso de técnicas de codificación para control de error permite mejorar el desempeño de probabilidad de error de los sistemas de comunicaciones. Esta mejora en el desempeño se logra a costa de incrementar el ancho de banda del canal usado o bien, de reducir la tasa de transferencia con el mismo ancho de banda de canal. La modulación codificada entramada TCM ofrece una alternativa para mejorar el desempeño de probabilidad de error de los sistemas de comunicación sin tener que incrementar el ancho de banda o disminuir la tasa de transferencia. En esta técnica se considera de forma conjunta el proceso de modulación y el proceso de codificación. El diseño del codificador depende del modulador, en particular del tamaño de la constelación usada. En esta técnica se incrementa el número de símbolos usados en la modulación, es decir se considera el uso de constelaciones más complejas. Esta técnica de modulación - codificación está siendo considerada como una alternativa en diferentes estándares de comunicación ya que hace un uso más eficiente del ancho de banda, el cual es uno de los recursos más preciados en las actuales redes de telecomunicaciones. En este trabajo se presenta una revisión a las bases teóricas que dan soporte a la técnica TCM, es decir códigos convolucionales y modulaciones m-arias. Se presentan también casos de simulación con diferentes parámetros de configuración y los resultados obtenidos.

2


I. ESTANDARES DE COMUNICACIÓN

Las tecnologías de telecomunicaciones han progresado incesantemente de la investigación hacia

la estandarización de la implementación de sistemas. Los estándares de telecomunicaciones son

conjuntos de normas y recomendaciones técnicas que regulan la transmisión en los sistemas de

comunicaciones.

El proceso de comunicación es regido por las siguientes cuatro leyes:

La ley de Shannon

+=

WN

PWC

0

2 1log ...........................................(1)

Donde C es la capacidad de un sistema de comunicaciones en bits por segundo, P es la potencia de la

señal en Watts, W es el ancho de banda de la señal en Hertz, y N0 es la densidad espectral de la potencia del

ruido unilateral en Watts/Hertz. La ley de Shannon dice que si hay un transmisor y un receptor, la capacidad

del canal de comunicación depende linealmente del ancho de banda disponible y logarítmicamente de la

relación señal a ruido (RSR). Esto significa que es más difícil incrementar la capacidad de canal

incrementando la relación señal a ruido que incrementando el ancho de banda disponible.

La ley de Moore

Establece que el nivel de integración de los circuitos integrados se duplicará cada 18 meses.

Tercer principio. La utilidad de una red es proporcional al cuadrado de la velocidad de conexión.

Cuarto Principio. Nos dice que la utilidad de una red es proporcional al cuadrado del número de

dispositivos que pueden ser conectados. Con respecto a un dispositivo en particular esta regla dice que la

utilidad de un dispositivo es proporcional al cuadrado del número de dispositivos con los cuales puede

comunicarse.

Las tecnologías de comunicación y los estándares de comunicación han buscado, desde los trabajos de

Shannon en 1948, acercarse más a la capacidad de Shannon. Mientras los dos primeros principios de

refieren a la pregunta de qué puede ser perfecto, el tercero y cuarto se refieren a cómo un incremento en la

utilidad puede ser perfecto —incrementando la razón de comunicación e incrementando el número de

dispositivos unidos—. El desarrollo de los estándares de telecomunicaciones de la IEEE 802 es una buena

manifestación de esas leyes fundamentales de comunicación. Los estándares de Comunicación

proporcionan la tecnología para interconectar un gran número de dispositivos a tasas de datos cada vez

mayores.

3


Antes de describir los estándares de comunicación es importante identificar las principales

características de la tecnología de telecomunicaciones. Esas características incluyen las siguientes:

a) Habilidad de transportar voz, audio y video, además de datos de computadora.

b) Incluyen dispositivos con diferente precio, consumo de potencia y tasas de datos para operar.

c) Asignación de espectro eficiente y dinámica entre los dispositivos conectados

De manera adicional se puede encontrar en el anexo la tabla 1 que incluye una cronología de la

fundación de algunas organizaciones estandarizadoras y la publicación de los estándares más importantes.

Algunas de las organizaciones estandarizadoras son: ISO International Standards Organization

(Organización Internacional de Normas), el IEEE (Instituto de ingenieros electrónicos y eléctricos) que es la

encargada de fijar los estándares de los elementos físicos de una red, cables, conectores, etc., ANSI

American Nacional Standards Institute (Instituto Nacional Americano de estandarización ), TIA

Telecommunications Industry Association ( Asociación de industrias de telecomunicaciones) y EIA

El comité que se ocupa de los estándares de computadoras a nivel mundial es de la IEEE en su división

802, los cuales se dedican a lo referente de sistema de red.

En los últimos años se han desarrollados diversos estándares para comunicaciones digitales

inalámbricas con distinto tipo de accesos a redes de comunicaciones e interacción de sistemas. Estos

estándares los podemos clasificar en 3 grades grupos. Los WPAN (Wireless Personal Area Network), WLAN

(Wireless Local Area Network) y los WMAN (Wireless Metropolitan Area Network). Los primeros están

ideados para comunicaciones de muy bajo alcance y muy baja potencia, siendo el estándar más conocido de

esta familia bluetooth, que nos permite transmisiones de hasta 1Mbps a distancias de varios metros. En

general, estos estándares están diseñados para que los dispositivos que los implementan sean de bajo

coste. Los estándares WLAN son los estándares que nos permiten conexiones de hasta varias decenas de

Mbps para alcances de hasta centenares de metros. El estándar más conocido de esta familia es el WiFi que

permite conexiones de hasta 11Mbps. Por ultimo los WMAN son estándares que permiten conexiones de

varios kilómetros y velocidades de hasta 75Mbps, en la configuración actual de WiMax.

El estándar de la IEEE que regula las conexiones WLAN es el IEEE 802.11. Este estándar, a su vez, tiene

más subdivisiones entre las que destaca la norma IEEE 802.11b que se basa en la tecnología de espectro

extendido y logra razones de datos de 5.5 Mb/s y 11Mb/s. Por ello muchos de los productos del mercado

siguen esta norma. Nuestro interés radica en que trabaja a nivel físico y determina como alternativa de

funcionamiento un esquema llamado codificación convolucional binaria empaquetada (PBCC por sus siglas

en ingles). Esta codificación algunas veces se denomina como modo de alto desempeño. Se usa un

codificador convolucional de 64 estados y una razón de 1/2, además de una secuencia de protección.

Después de pasar por el codificador los bits son mapeados, para transmisiones de 5.5 Mb/s el mapeo es

BPSK (Binary phase shift keying) una modulación en fase y para transmisiones de 11 Mb/s se mapea usando

4


QPSK (quadrature phase shift keying). La norma IEEE 802.11a usa un nuevo modo de transmisión llamado

OFDM (orthogonal frecuency division multiplexing) que debido a su bajo costo fácilmente se ha incluido en

los dispositivos inalámbricos del mercado. A pesar de esta novedosa forma de modulación la norma IEEE

802.11a contempla el uso de codificadores convolucionales de razones ½, 2/3 o ¾. En el caso de la razón ½

el codificador tiene los polinomios 133 y 171 en notación octal. Las otras razones se obtienen por omisión

de pinchado de ciertos bitas de la palabra. La decodificación se realiza indiscutiblemente con el algoritmo

de Viterbi.

II. CODIFICACION PARA CONTROL DE ERROR

Tres investigadores marcaron el inicio en el campo del manejo del error y echaron abajo teorías antes

planteadas, ellos fueron Shannon, Hamming y Golay. Shannon echó abajo la teoría que explicaba los

limitantes fundamentales de la eficiencia de los sistemas de comunicación, Hamming y Golay fueron los

primeros en desarrollar esquemas prácticos de control de error. La fórmula más famosa del trabajo de

Shannon trata sobre la capacidad de canal de un canal ideal gaussiano de banda limitada.

...........................................(2)

Donde

C= Capacidad de canal (el máximo número de bits que se pueden transmitir a través del canal por

unidad de tiempo).

W= Ancho de banda del canal

S/N= relación señal a ruido del receptor

S= Potencia de la señal

N= Potencia del ruido

[ ]segbitsN

sWC /)1(log 2 +=

5


)1(log0

2WN

PWC +=

Debido a su gran importancia, de la fórmula de Shannon se obtienen ciertas variantes que se aplican a

distintos tipos de canales de transmisión como es el caso del canal de ruido blanco gaussiano AWGN

(additive white Gaussian noise) que tiene la siguiente forma:

...........................................(3)

De esto se puede concluir que los factores que determinan la capacidad de canal son el ancho de banda

W, la densidad espectral de potencia del ruido N0, y la potencia de la señal P, y que existe una relación

directa entre P y W en el sentido en que uno compensa al otro.

Si se piensa en incrementar la potencia de la señal de entrada obviamente incrementa la capacidad de

canal, debido a que cuando se tiene disponible más potencia, es posible elegir un mayor número de niveles

de entrada al canal de forma que estén más apartados y en consecuencia sea posible enviar más bits de

información por transmisión. Sin embargo, el incremento en la capacidad con el aumento de la potencia es

logarítmico y suave. Esto se debe a que si se transmite con cierto número de niveles de entrada separados

Δ, para permitir cierto nivel de inmunidad al ruido y se desea incrementar el número de niveles, es

necesario introducir nuevos niveles con amplitudes mayores que la de los niveles existentes y esto requiere

gran cantidad de potencia. A pesar de esto, la capacidad de canal podría incrementarse en cualquier valor

incrementando la potencia de entrada.

El efecto del ancho de banda del canal, sin embargo, es muy diferente. El incrementar W tiene dos

efectos opuestos. Por un lado, sobre un canal de ancho de banda mayor es posible transmitir más muestras

por segundo y de esta forma incrementar la velocidad de transmisión. Por otro lado, un ancho de banda

mayor significa mayor potencia de ruido en el receptor y esto degrada el desempeño. Esto se observa en los

dos W que se encuentran en la relación (3) que describe la capacidad de canal.

Para enviar la información a través de un canal de comunicación se usan actualmente esquemas de

codificación tanto en la fuente como en el canal, la codificación del canal tiene como tarea codificar la

información adicionando redundancia al mensaje de tal manera que ante la presencia de ruido en el canal

se pueda detectar y corregir los errores generados por este; además con la codificación de canal se puede

operar con transmisión de baja potencia, realizar transmisiones a largas distancias, mayor tolerancia a la

interferencia, transmitir a altas tasas de datos y hacer posible usar antenas pequeñas.

6


Un sistema de codificación de canal además de corregir errores debe ser capaz de corregir otras fallas

que se pueden presentar en la degradación del canal tales como: atenuación de la señal debido al medio, el

ruido térmico, interferencia ínter simbólica, interferencia del múltiple usuario, la propagación

multidireccional, y limitaciones de potencia.

Para el diseño de la codificación y modulación del canal se deben tener en cuenta cuatro factores:

1. Probabilidad de error (Pe): este factor nos dice que tan confiable es la transmisión, es decir mide el

desempeño de un sistema de comunicación digital.

2. Eficiencia espectral o ancho de banda ( W Rs ): esto mide la eficacia en gasto del ancho de banda, nos

dice cuántos bits por segundo (Rs) pueden ser transmitidos en un ancho de banda dado W.

3. Tasa de relación señal a ruido (SNR), este factor es necesario para alcanzar el factor de calidad (QoS)

requerido: este parámetro mide cómo el esquema de codificación y modulación hace uso eficientemente de

la potencia disponible.

4. Complejidad: Este factor está estrechamente relacionado con el costo del equipo.

En la codificación de canal se distinguen dos métodos:

· Corrección de error hacia atrás BEC (Backward error correction) ó ARQ. El cual solo emplea detección

de errores, si un error es detectado se solicita retransmisión de todo el mensaje. Mientras este método

tiene una baja complejidad en los esquemas de corrección de errores, se debe disponer de una

comunicación dúplex, además la retransmisión trae como consecuencia retardos a nivel del tiempo, que en

aplicaciones críticas como las de tiempo real no es aconsejable.

· Corrección de error hacia delante FEC (Forward error correction). En el transmisor un codificador de

FEC agrega redundancia a los datos en la forma de información de paridad de la siguiente manera: un

codificador binario de FEC toma k bits a la vez y produce una salida (o palabra de código) de n bits, donde

n>k.

7


Mientras que hay 2n secuencias posibles de n bits, solamente hay un subconjunto pequeño de ellos, 2k,

que serán palabras de código válidas. El cociente k/n se llama la tasa de código.

· Entonces en el receptor, un decodificador de FEC puede explotar la redundancia de una manera tal

que un número razonable de los errores de canal pueda ser corregido. Con un código FEC se logra tolerar

más errores de canal, los sistemas codificados pueden permitirse funcionar con más baja transmisión de

potencia, transmitir a largas distancias y tolerar más interferencia, y hace posible el uso de antenas más

pequeñas, y se podría transmitir a una mayor velocidad para una potencia de transmisión dada. El método

FEC solo requiere una comunicación simplex, este método es muy atractivo en sistemas de comunicación

inalámbrica, ayudando a mejorar la eficiencia de la energía de los sistemas.

En el método de corrección de error hacia delante (FEC) se encuentran los códigos de corrección de

bloques, los códigos convolucionales y los turbo códigos.

Códigos de bloque

Estos códigos hacen la corrección de errores a nivel de bits tomando la información por bloques, dentro

de ellos se encuentran los códigos Hamming, Golay, BCH, ReedSolomon (estos códigos como trabajan con

símbolos de código marios, los hace eficientes para corregir errores de ruido en ráfaga).

Los Turbo códigos

Los turbo códigos son un método de corrección de errores basado en los códigos convolucionales más

intercalación y realimentación. Consiste en una estructura de codificación concatenada más un algoritmo

iterativo, estos fueron introducidos en 1993 por Berrou y Glavieux en la conferencia internacional de la IEEE

en Ginebra Suiza. El esquema propuesto en dicho trabajo alcanzaba una probabilidad de error de bit de 105

usando una tasa de codificación de ½ sobre un canal de ruido blanco gausiano (AWGN) y modulación BPSK

con una relación de energía promedio de bit sobre la densidad espectral de potencia de ruido (Eb/N0 ) de

0.7 dB, lo cual está cercano al límite de Shannon que es 0.1dB.

Códigos Convolucionales

Los códigos convolucionales trabajan serialmente, y tienen memoria lo cual los hace comparablemente

más eficientes que los códigos de bloque, por su simplicidad y capacidad de corrección. A continuación se

presenta una descripción más detallada de éste método de detección de error FEC que es uno de los temas

de estudio incluidos en el presente trabajo.

8


III. CODIGOS CONVOLUCIONALES

Los códigos convolucionales son códigos lineales que tienen una estructura adicional en la matriz

generadora de modo que la operación de codificación puede ser visto como una operación de filtrado (o

convolución). Un codificador convolucional se puede ver como no más que un conjunto de filtros digitales -

sistemas lineales e invariantes en el tiempo- con la secuencia de código como la salida intermedia de las

salidas filtradas. En la práctica los códigos convolucionales son a menudo preferidos sobre los códigos de

bloques, porque proporcionan excelente rendimiento cuando se comparan con los códigos de bloques de

complejidad de codificación/decodificación comparable.

Los códigos convolucionales se especifican mediante tres parámetros, (n, k, m) donde n es el número

de bits a la salida del codificador, k el número de bits de información a la entrada de éste y m, el número

de registros de memoria. La relación k/n es la relación o tasa de código, tiene el mismo significado que para

los códigos de bloque y proporciona una medida de la eficiencia de codificación. En la práctica, k y n suelen

variar de 1 a 8, m de 2 a 10 y k/n de 1/8 a 7/8. En algunas aplicaciones de comunicaciones con vehículos

espaciales a distancias muy grandes de la tierra se han utilizado tasas de código muy bajas, del orden de

1/100 o menores.

Es común que los fabricantes de circuitos integrados especifiquen los parámetros del código

convolucional como (n, k, L) en que L se designa como longitud de constricción y está dada por L = k(m – 1)

L representa el número de bits en la memoria del codificador, previos al bit actual de entrada, que afectan

a la generación del código.

Los elementos básicos de un codificador convolucional son un registro de desplazamiento, constituido

por m elementos de memoria (flip-flops) y n generadores de señal que, en este caso, no son otra cosa que

sumadores en módulo1 2 (es decir en el campo GF (2) usando compuertas OR exclusivas). En la figura 1 se

ilustra un decodificador convolucional simple.

Se representan las secuencias y funciones de transferencia como series de potencias en la variable x1.

Una secuencia {...m-2, m-1, m-0, m1, m2,...} con elementos del campo F es representada como una formal

1 La suma en módulo 2 sigue la regla: 0 + 0 = 0; 0+1 = 1; 1+ 0 = 1; 1 + 1 = 0.

9


[ ] .F[[x]] (x)m (x)m)( 2(2)(1) ∈=xm

serie de Laurent ∑∞

−∞==

l

l

l xmm . El conjunto de todas las series de Laurent bajo F es un campo, el

cual es usualmente denotado como F [[x]]. Entonces ∈)(xm F [[x]].

Para múltiples cadenas de entrada se usa un superíndice, así m(1)

(x) representa la primera cadena de

entrada y m(2)

(x) representa la segunda cadena de entrada. Para múltiples cadenas de entrada, es

conveniente reunir las cadenas de entrada dentro de un vector simple (columna), como en

...........................................(4)

Un codificador convolucional es típicamente representado como un conjunto de filtros digitales

(binarios).

Ejemplo 1. La figura 2 muestra un ejemplo de un codificador convolucional. (Hay que recordar que los

bloques D representan dispositivos de almacenamiento de 1 bit, o flip flops). La cadena de entrada mk para

a través de dos filtros (elementos de memoria compartida) produciendo dos cadenas de salida. En este

encoder se observa que hay k=1 entradas y n=2 salidas por lo que el encoder es de razón R= k/n y además L

( la longitud de restricción o longitud restringida del código) vale 3.

2

)1(

−+= kkk mmc y 21

)2(

−− ++= kkkk mmmc

Estas dos cadenas son procesadas juntas para producir la cadena codificada ck. Por lo tanto, para

cualquier bit de entrada, hay dos bits de salida, resultando en un código de razón R=1/2.

Para la entrada m= {1, 1, 0, 0, 1, 0,1}, las salidas son

c(1) = {1, 1, 1, 1, 1, 0, 0, 0, 1} y c(2)

= {1, 0, 0, 1, 1, 1, 0, 1, 1}

y la cadena intercalada es c = {11, 10, 10, 11, 11, 01, 00, 01, 11}

10


+

++=

2

2

x 1

x x 1 1)(xGb

donde las comas separan los pares de salidas en tiempos de entrada únicos. Se puede representar la

función de transferencia de la entrada m(x) hacia la salida c (1)

(x) como g (1)

(x)= 1+x2, y la función de

transferencia desde m(x) hasta la salida c (2)

(x) como g(2)

(x) = 1+ x +x2. La cadena de entrada m = {1, 1, 0, 0,

1, 0, 1} puede ser representada como m(x) = 1+ x +x4+ x

6 Є G F (2)[[x]]. Las salidas son:

c(1)

(x) = m(x)g1(x) = (1+ x +x4+ x

6)( 1+ x

2) = 1+ x + x

2 + x

3 + x

4+ x

8

c(2)

(x) = m(x)g2(x) = (1+ x +x4+ x

6)( 1+ x + x

2) = 1+ x

3 + x

4+ x

5 + x

7+ x

8

Un código convolucional de razón R = k / n tiene asociado a él un encoder, una matriz función de

transferencia G(x). Para la razón de ½ del ejemplo resulta

Ga(x) = [1 + x2 1 + x + x

2 ]

Sin embargo la función de transferencia convolucional no siempre tiene entradas polinomiales. Por

ejemplo:

Cuya implementación en hardware puede quedar como en la figura 3.

Para encoders con alimentación directa es común que los polinomios de conexión se indiquen como

vectores de números representando la respuesta al impulso del encoder, en vez de polinomios. La matriz

función de transferencia G(x)= [1+ x2, 1+ x + x

2] es representada por los vectores

g(1)

= [101] y g(2)

= [111]

11


Estos son con frecuencia expresados en forma octal (en las tablas de códigos), donde los tríos de bits

son representados usando los números enteros correspondientes 0 a 7. De esta forma el encoder es

representado usando g(1)

= 5 y g(2)

= 7. Debido a la facilidad de manejo se usan encoders con alimentación

directa con los vectores especificados en notación octal para implementar la simulación de la codificación

convolucional en Matlab.

Dado que el codificador convolucional tiene memoria finita, es posible representarlo con un diagrama

de transición de estados. En este diagrama, cada estado del codificador se representa mediante un bloque

y las transiciones entre estados son las líneas que conectan cada bloque. Sobre cada línea están

especificadas tanto las entradas que causan la transición como las salidas correspondientes. El número de

líneas que salen de cada estado es igual al número de entradas posibles al codificador de ese estado, la cual

es igual a 2k. El número de líneas que van hacia cada estado es igual la número de estados del cual es

posible una transición hacia ese estado. Este es igual al número de combinaciones de bits posibles que

dejan el codificador cuando k bits entran al codificador. Este número es otra vez 2k. En la figura 4(b) se

puede ver el diagrama de transición de estados del codificador convolucional del ejemplo1.

Otra forma de describir códigos convolucionales es el diagrama trellis que es una forma de representar

las transiciones de estados mientras transcurre el tiempo. El diagrama trellis se obtiene al especificar los

estados en el eje vertical y extendiendo éste a lo largo del eje del tiempo (el eje horizontal).

Posteriormente las transiciones entre estados se representan con una recta que une esos estados sobre los

dos ejes verticales correspondientes a los dos instantes de tiempo. Para una mayor claridad de lo anterior

en la figura 4(c) y 4(d) se observan una etapa y tres etapas respectivamente, del diagrama trellis

correspondiente al encoder del ejemplo 1.

Para un encoder básico G(x) con elementos polinomiales se tiene que ))(deg(max xg ijj

i =ν denota el

máximo grado de los polinomios en la fila i de G(x). Este es el número máximo de elementos de memoria

necesarios para almacenar la porción de realización del encoder correspondiente a la entrada i.

Ejemplo 2. Consideremos el codificador convolucional (2, 1, 2), n=2, k=1 y m=2, o sea que se trata de

un encoder de razón ½ y 2 elementos de memoria o longitud de restricción L=3,

( )1 0, 1, g ,)1 ,1 ,1( (1)

0

)0(

0 ==g , o lo que es igual G(t)= [111, 101], teniendo una entrada mj = (0 1 0 1 0 0 0)

y se desea hallar la salida dada por el codificador (desde el estado inicial ‘todos ceros’) de acuerdo a tal

entrada..

12


Para poder resolver este problema usamos la ecuación de codificación convolucional que es:

∑=

−=m

i

iijj Gmx0

Por tanto tenemos que de acuerdo a (1)

0

)0(

0 gy g resulta G0= [1 1], G1= [1 0] y G2= [1 1], entonces x0=

m0G0 ⊕ m-1G1 ⊕ m-2G2 y como el estado inicial es (u-1, u-2, . . .) =(0, 0, 0,…),

x0 =0 [1 1] ⊕ 0[1 0] ⊕ 0[1 1] = [0 0],

x1=1 [1 1] ⊕ 0[1 0] ⊕ 0[1 1] = [1 1]

x2=0 [1 1] ⊕ 1[1 0] ⊕ 0[1 1] = [1 0]

x3=1 [1 1] ⊕ 0[1 0] ⊕ 1[1 1] = [0 0]

x4=0 [1 1] ⊕ 1[1 0] ⊕ 0[1 1] = [1 0]

x5=0 [1 1] ⊕ 0[1 0] ⊕ 1[1 1] = [1 1]

x6=0 [1 1] ⊕ 0[1 0] ⊕ 0[1 1] = [0 0].

Reuniendo todos estos pares de bits en una salida tenemos: Uj=[00, 11, 10, 00, 10, 11, 00, 00] y como se

puede ver en negritas he puesto los bits de entrada al encoder que corresponden la mj.

IV. DECODIFICACION CONVOLUCIONAL: ALGORITMO DE VITERBI

Se han manejado varios algoritmos para decodificar los códigos convolucionales, uno de ellos y el más

empleado es el algoritmo de Viterbi que fue propuesto por Andrew Viterbi en 1967, éste es un Estimador

de Secuencia de Máxima Probabilidad (MLSE por sus siglas en inglés). Una variación del algoritmo de

Viterbi es el algoritmo de Viterbi de salida suave (SOVA), que proporciona no sólo símbolos decodificados

sino además un indicativo de la confiabilidad de los valores decodificados. Otro algoritmo es el

decodificador Máximo a Posteriori (MAP) comúnmente referido como algoritmo BCJR el cual calcula

probabilidades de los bits decodificados.

13


Para ubicar la etapa que decodificación tenemos la siguiente figura en la que la base de tiempo se

denota con t e indica los tiempos a los cuales son distinguidos los estados en el diagrama de estados; hay

entonces k bits de entrada al encoder y n bits de salida a cada paso de tiempo t.

Canal

m x c a r

n

FIGURA: Etapas de procesamiento de un código convolucional.

Como se puede observar se cuenta con un mensaje de datos de entrada que puede tener una secuencia

añadida que permita manejar el estado a cero al final de cada bloque de entrada. Al tiempo t hay k bits de

entrada denotados como k. ..., 2, 1, i , xo (i)

t

)( =i

tm El conjunto de k bits de entrada se de notan como

) ..., , ,( )()2()1( k

tttt mmmm = y los que cuentan con la secuencia agregada son xt. Por lo que una secuencia

con L bloques es denotada como x:

].,...,,[ 110 −= Lxxxx

Los bits codificados correspondientes se denotan como n. ..., 2, 1, i ,)( =i

tc La secuencia completa

codificada es c = [c0, c1, …, cL-1].

La secuencia codificada de salida es mapeada en como una secuencia de M símbolos seleccionados de

una constelación de señales con Q puntos en algún espacio de señales., con Q = 2p. Por facilidad se

asumirá p = 1 así que L = M. Las señales mapeadas se denotan como ,)(i

ta i = 1,2,…, n y la secuencia

completa es a = {a0, a1, …, aL-1} estos símbolos at pasan a través del canal, que en este caso consideramos

un canal AWGN, resultando los símbolos recibidos )(i

tr , i = 1, 2, …, n, o un bloque rt. Como anteriormente

se describió, el ruido AWGN tiene una distribución de voltaje en el tiempo con características que pueden

ser descritas por una distribución estadística Gaussiana o normal, como por ejemplo la campana de Gauss.

Esta distribución de voltaje tiene media cero y una desviación estándar que es función de la relación señal

Añade el estado cero

Una secuencia

forzada (Opcional)

Codificador

Convolucional

Mapeo de

señal

14


).(log)(log1

0

tt

L

t

xrfxrf ∑−

=

=

a ruido (RSR) de la señal recibida. Si consideramos que el nivel de la señal está dado, entonces si la RSR es

alta, la desviación estándar del ruido es pequeña, y viceversa.

La ventaja de la decodificación con el algoritmo de Viterbi es que tiene un determinado tiempo de

decodificación, por ello es muy usado en la implementación de hardware. Una desventaja podría ser que

los requerimientos computacionales crecen exponencialmente con respecto a la longitud de restricción y

por ello en la práctica se utilizan longitudes por debajo de K=9.

Revisando la notación utilizada para la decodificación tenemos que el estado al tiempo t en la trellis del

encoder es denotado como ψt. Los estados son representados con valores enteros en el rango de 0 ≤ ψt ≥

2ν, donde ν es la longitud de restricción del encoder. (Usamos 2

ν puesto que nos referimos a encoders

binarios.)

Como se puede ver en la figura 5, la entrada que causa la transición del estado ψt = p al estado ψt+1 = q

es denotada como x(p,q). (Si la trellis tiene diferentes estructuras en distintos tiempos, se usa la notación

),( qp

tx . La secuencia de bits código de salida como resultado de esta transición de estados es c(p,q) y los

símbolos mapeados son a(p,q).

El algoritmo de Viterbi es esencialmente un algoritmo de trayectoria más corta, puesto que se trata de

calcular la trayectoria más corta a través de la trellis asociada con el código.

Para una entrada xt la salida ct depende del estado del codificador ψt, el cual en cambio depende de

las entradas previas. Esta dependencia entre entradas implica que las decisiones óptimas no se puedan

basar en una función de probabilidad para un solo tiempo f(rt|xt). En lugar de eso, las decisiones óptimas se

basan en una entera secuencia de símbolos recibida. La función de probabilidad a ser maximizada es f(r|x),

donde

∏−

=−

−− ===1

0

110

1

0

1

0 ).(),..., ,()()(L

t

ttL

LL xrfrrrfxrfxrf

Puesto que estamos considerando un canal sin memoria se puede tener la igualdad anterior. Esto es

conveniente para manejar la función log de probabilidad,

15


).ˆ,()()ˆ,()ˆ,()( ),(1

0

1

qp

it

t

i

ttttiitt xrpMxrxrqM µµµ +=+=∑−

=−

Si tomamos en cuenta que una secuencia { }110

1

0ˆ ..., ,ˆ ,ˆˆ −

− = t

t xxxx deja al encoder en el estado ψt = p al

tiempo t, esta secuencia determina una trayectoria (o secuencia de estados) a través de la trellis del

código. Entonces { }∏ ΨΨΨ=t t .,...,, 10

La función log de probabilidad para esta secuencia es .)x̂f(r log )x̂f(r log1-t

0i

ii

1-t

0

1-t

0 ∑=

=

Sea )ˆ(log 1

0

1

01

−−− −= tt

t xrfM la métrica de trayectoria del camino Пt a través de la trellis definida

por la secuencia x 1

0

−ty que termina en el estado p. El signo negativo indica buscamos minimizar la métrica

de la trayectoria (para maximizar la probabilidad).

Si ahora hacemos que )ˆ(log)ˆ,( ttttt xrfxr −=µ denote la probabilidad negativa de una entrada

que hace que al tiempo t+1 el estado sea ψt-1= q. Podemos usar de manera equivalente

[ ],)ˆ(log)ˆ,( ),( bxrfaxr qp

tttt −−=µ para cualquier a<0. La cantidad )ˆ,( ttt xrµ es llamada métrica

de rama del encoder. Puesto que x̂ mueve la trellis del estado p al tiempo t estado q al tiempo t+1,

podemos escribir )ˆ,( ttt xrµ como ).ˆ,( ),( qp

tt xrµ Entonces

Esto es, la métrica del camino (o de trayectoria) a lo largo de una trayectoria hacia el estado q al

tiempo t se obtiene sumando la métrica del camino hasta el estado p al tiempo t-1 a la métrica de rama

para una entrada la cual mueve el codificador del estado p al estado q. (Si no hay tal entrada entonces la

métrica de rama es ∞).

Ahora llegamos a un punto medular del algoritmo de Viterbi, el momento en el que dos caminos

confluyen o se unen. Supongamos que Mt-1(p1) es la métrica de trayectoria de un camino que termina en el

estado p1 al tiempo t y Mt-1(p2) es la métrica de trayectoria del camino que finaliza en el estado p2 al

tiempo t. Supongamos además que ambos estados están conectados al estado q al tiempo t+1, como se

sugiere en la figura 6, las métricas de camino resultantes en el estado q son

).ˆ,()(My )ˆ,()(),(

21-t

),(

1121 qp

tt

qp

ttt xrpxrpM µµ ++−

16


)}ˆ,()(M,)ˆ,()(min{)(),(

21-t

),(

1121 qp

tt

qp

tttt xrpxrpMqM µµ ++= −

El Principio que gobierna el algoritmo de Viterbi es: Para obtener la trayectoria más corta a través de

la trellis, la trayectoria al estado q debe ser lo más corto posible. Entonces, cuando dos o más trayectorias

se juntan, la trayectoria con la métrica de trayectoria más corta es retenida mientras que la otra

trayectoria ya no se toma en cuenta. Esto es.

y la trayectoria con la mínima longitud se convierte en la trayectoria al estado q. Este camino es

llamado trayectoria sobreviviente.

Puesto que no se sabe en el tiempo t<L a través de cuales estados pasa la trayectoria final, se busca la

trayectoria de cada estado en cada tiempo. El algoritmo de Viterbi mantiene la siguiente información:

• Una métrica de camino para cada estado en el tiempo t.

• Un camino para cada estado en el tiempo t.

Finalmente podemos resumir el algoritmo de Viterbi en 4 sencillos puntos:

1.- Para cada estado q al tiempo t +1, encontrar la métrica de trayectoria para cada camino hacia q por

medio de la suma de la métrica de camino Mt-1(p) de cada trayectoria sobreviviente del estado p en el

tiempo t a la métrica de rama ).ˆ,( ),( qp

tt xrµ

2.- La trayectoria sobreviviente hacia q se seleccionada como la trayectoria al estado q que tiene la

métrica de trayectoria más pequeña.

3.- Almacenar la trayectoria y la métrica de trayectoria para cada estado q.

4.- Incrementar t y repetir hasta completar.

Es preciso apuntar que en el caso en que haya dos trayectorias que se unen y que además tienen la

misma métrica lo que se hace es una selección aleatoria sin que esto pueda tener repercusiones negativas

en la probabilidad.

17


Para que quede más claro este algoritmo hay que ver el siguiente ejemplo:

Ejemplo 3: Consideremos el encoder G =[x2+1 x

2 + x +1] del ejemplo 1, cuya realización y diagrama

trellis se observa en la figura 3, pasando los datos a través de un BSC. Donde la secuencia de datos m =[1, 1,

0, 0, 1, 0, 1, 0, …] = [m0, m1, m2, m3, m4, m5, m6, m7, …] se aplica al encoder, la secuencia de bits de salida e c

= [11, 10, 10, 11, 11, 01, 00, 01, …] que corresponde a c = [c0, c1, c2, c3, c4, c5, c6, c7, …].

Por facilidad digamos que los datos pasan por un Canal Binario Simétrico (BSC), en tal caso

consideramos los datos mapeados iguales a la salida del encoder at = ct. La secuencia de salida y los

estados correspondientes se muestran en la tabla 2, donde ψ0 = 0 es el estado inicial.

La secuencia de estados en la trellis para este encoder se muestra en la siguiente figura A (para facilitar

la comprensión del método se incluyen las figuras en esta parte del reporte) donde la línea oscura

representa la secuencia de estados correspondiente a esta secuencia de salidas.

FIGURA A: Trayectoria a través de la trellis que corresponde a la secuencia en cuestión

La secuencia codificada de salida pasa a través de un canal, produciendo con ello la secuencia recibida r

= [11 10 00 10 11 01 00 01…] = [r0, r1, r2, r3, r4, r5, r6, r7,…]. Los bits que están subrayados son resultado del

ruido existente en el canal.

Entonces vamos a entrar en materia con el algoritmo, para esto vamos a ir paso por paso en cada

instante de tiempo t:

En t = 0; sabemos que es el estado inicial y la secuencia recibida es r0= 11, se calcula la métrica para

cada estado en el tiempo t = 1 encontrando la distancia (de Hamming) entre r0 y la posible secuencia

transmitida c0, a lo largo de las ramas de este primer estado de la trellis. Como sabemos que el estado 0 es

18


el estado inicial, tenemos sólo dos trayectorias, con métricas de trayectoria de 2 y 0, como se muestra a

continuación:

0

1

2

3t = 0 t = 1

r0=11

2

0

Para t= 1 la secuencia recibida es r1= 10. Nuevamente cada trayectoria al tiempo t = 1únicamente es

extendida sumando la métrica de trayectoria a cada métrica de rama.

t = 2: la secuencia recibida es r2= 00. Cada trayectoria al tiempo t = 2 es ampliada, sumando la métrica

de trayectoria a cada métrica de rama de cada camino.

Ahora hay múltiples caminos hacia cada nodo en el tiempo t =3. Seleccionamos la trayectoria hacia

cada nodo con la mejor métrica y eliminamos las otras trayectorias. Esto nos da el siguiente diagrama:

19


t = 3: La secuencia recibida es r3= 10. Cada camino al tiempo t = 3 es extendido, sumando la métrica de

trayectoria a cada métrica de rama de cada trayectoria.

Nuevamente se selecciona la mejor trayectoria de cada estado. Es preciso notar que durante la

selección de las mejores trayectorias, algunas trayectorias en algunos estados en tiempos anteriores no

tienen sucesores; estas trayectorias huérfanas ahora se eliminarán del diagrama.

0

1

2

3

t = 0 t = 1 t = 3t = 2

r3=10

2

1

2

2

t = 4

En t = 4: La secuencia recibida es r4= 11. Cada trayectoria al tiempo t = 4 se amplia, como se ha venido

haciendo en pasos anteriores.

20


En este caso se observa que hay dos trayectorias en el estado 3 que tienen la misma métrica de

trayectoria, de igual manera se tiene el caso en el estado 2. Dado que una de las dos trayectorias tiene que

seleccionarse, dicha selección se puede hacer arbitrariamente. Después de la selección y eliminación de las

trayectorias huérfanas obtenemos:

En t = 5: La secuencia recibida es r5= 01

Después de la selección y el depurado

21


t = 6: La secuencia recibida es r6= 00.

Después de la selección y el depurado

En t = 7: La secuencia recibida es r7= 01.

22


Después de la selección y el depurado se tiene:

La decodificación se finaliza al final de la transmisión (los 16 bits de datos recibidos) mediante la

selección de estado tras estado del que tuvo el menor costo, atravesando hacia atrás a lo largo del camino

también indicado en el comienzo de la trellis, también atravesando hacia delante a lo largo del mejor

camino, leyendo los bits de entrada y decodificando los bits de salida a lo largo de la trayectoria. Esto se

muestra en seguida con una línea continua, donde se indican los pares entrada/salida de bits.

23


Hay que notar que la trayectoria a través de la trellis es la misma que la de la figura 9 y que la

secuencia de bits de entrada recibida es la misma que la secuencia original. Entonces en nuestra secuencia

de 16 bits, dos bits de error han sigo corregidos.

Decodificaciones dura y suave.

Los datos provenientes del canal deben suministrarse al decodificador, y pueden ser manejados con dos

tipos de decodificación, designados como dura o firme (hard) y suave (soft). En términos muy simples,

puede decirse que la decodificación dura se da cuando el demodulador entrega al decodificador de canal la

información tal como la detecta sin intentar efectuar ninguna corrección, dejando esa tarea al decodificador

de fuente. Esto significa que la señal recibida del canal es cuantizada con sólo dos niveles Si ahora

suponemos que los datos se introdujeron a un canal con AWGN y que en la detección se toma en cuenta la

distancia Euclidiana y la métrica de rama, entonces estamos hablando de una decodificación suave.

Haciendo una comparación entre la decodificación con decisión suave usando BPSK bajo un canal AWGN y

la decodificación con decisión dura bajo un canal BSC, en los cuales los valores recibidos son convertidos a

valores binarios con una probabilidad de error pc = ( )02 NEQ b , se ha determinado que la decodificación

con decisión suave proporciona una ganancia de 2 a 3 dB sobre la decodificación con decisión dura.

Para comprender mejor lo anterior consideremos la señal recibida del canal como la variable aleatoria

y. En la Figura 7 se representa la probabilidad de la señal recibida condicionado al hecho de haber enviado

un ‘0’ f (y |’0’) y la probabilidad al hecho de haber enviado un ‘1’ f (y |’1’) cuando se introduce ruido AWGN

al canal.

El demodulador aplicado a un decodificador con decisión suave cuantifica una graduación entre los dos

niveles de señal del emisor ‘0’ y ‘1’. Así, la decisión de si un símbolo es ‘1’ o ‘0’ se suaviza (decisión suave).

En la figura, el decodificador Viterbi interpretará el símbolo ‘000’ como un ‘0’ con máxima probabilidad y el

símbolo ‘111’ como un ‘1’ con máxima probabilidad. En medio se encuentran el resto de símbolos.

El ejemplo de la sección anterior corresponde al algoritmo de Viterbi con decisión dura. El proceso del

cálculo de las métricas de rama en el algoritmo de Viterbi con decisión suave es un tanto diferente, por

ejemplo: si para una rama en particular de la trellis las etiquetas conocidas (las salidas del encoder) son ν1 y

ν2 como se observa en la figura siguiente, y las entradas correspondientes del decodificador son r1 y r2 ,

entonces la métrica de rama se calcula como sigue

∑=

+=2

1

2)(j

jjrbm ν

24


]][1[

]][1[

picb

pipm

+

+

n]][[

]][[

nicb

nipm

]][1[

]][1[

qicb

qipm

+

+

]32][1[

]32][1[

cb

pm

sobrante

aTrayectori

Ejemplo 4: para resumir los principales pasos del algoritmo de Viterbi con decisión suave se considerará

el codificador convolucional con polinomios generadores (en notación octal) [133,171] con tasa R= ½ y, por

tanto con una K=7. Se asume que la salida del codificador es +/- 1 y un canal con AWGN. Por simplicidad, las

entradas del decodificador r2i y r2i+1 en la ventana i se consideran valores continuos. Para 0 ≤ i ≥ K-2 la trellis

crece pero como se ve en la figura se considerará la transición más común. A cada nodo de la trellis se

asigna una métrica de camino continua y para el nodo p está dada por:

2

212

2

12 )()(]][[]][1[ νν −+−+=+ +ii rrnipmpipm

i=0 1 2 5 6 7

r2i,r2i+1

i i+1

16 ui=0 p=

2

n

32

ui=1

48 q=

2

n+32

FIGURA: Diagrama trellis para el código [133,171] R= ½ y K=7.

Aquí, ν1 y ν2 son las etiquetas para el caso ui=0 debido al estado actual n. Además de las dos métricas

de rama se agrega la información necesaria para realizar el traceback tomando en cuenta la trayectoria con

mejor probabilidad.

25


En la figura siguiente se muestra una transición de estados para el ejemplo que se maneja. Para la rama

pn una métrica de rama temporal se calcula como:

mp= 2

212

2

12 )()(]][[ νν −−+ +ii rrpipm y de manera similar para mq. Asumiendo, por ejemplo, que mp

< mq entonces pmnipm =+ ]][1[ ; cb[i+1][n]=p.

p=2n

i etapa,i i+1

p r2i,r2i+1 0≤ n < 32 n

mp q=2n+1

n

` mq p=2(n-32)

Q 31< n < 64 n

p=2(n-32)+1

Trellis repetitiva para el codificador [133,171] con decodificación con el algoritmo de Viterbi

Finalmente, considerando la decodificación con traceback. Suponiendo que deseamos la decodificación

del bit de información ui dada una ventana de decodificación de W etapas (como en la figura de a

continuación). El estado Si+W correspondiente a la métrica de trayectoria más chica no es necesaria en la

trayectoria del decodificador, pero es un buen punto de inicio para el trazo hacia atrás (traceback). Se

realiza el trazo W etapas hacia atrás usando el algoritmo

S[j] = cb [j+1] [Si+1], con j = i + W -1, ..., i+1,i

]][[

]][[

picb

pipm

]][[

]][[

qicb

qipm

]][1[

]][1[

nicb

nipm

+

+

26


]][[

]][[

Wi

Wi

SWicb

SWipm

+

+

+

+

W etapas

i i+1 i+W

Si+W

Si

Si+W-1

ui

Si+1

Decodificación hacia atrás para ui

Proporcionando W = 5K o más, entonces los estados Si y Si+1 identificarán con mayor precisión la

métrica de camino para la etapa correspondiente, también tiene más probabilidad de identificar la trayectoria

usada por el codificador para la etapa i. En el algoritmo se siguen algunas reglas simples, por ejemplo ui = 0

si Si+1< Si.

Ejemplo 5: Finalmente, para terminar de comprender el algoritmo tómese en cuenta un ejemplo real en

el que se tiene parte de la trellis de un codificador convolucional de razón R= 1/2. La etiquetas de cada rama

corresponden al par de símbolos codificados ν1, ν2 y también se observan las métricas de trayectoria en cada

nodo, la métrica de trayectoria por nodo se encuentra como sigue:

9.5

i

-1,1

27


r

10.6 1,1

p

1,-1

j

1,1 1,-1

q k

8.2 12.1

-1,-1

s

Entrada suave 0.9,-0.5 1.3,0.2

Ilustración de una decodificación con decisión suave

Para el nodo j se tiene:

mp =10.6+(0.9-1)2 + (-0.5-(-1))

2 = 10.86

mq =8.2+(0.9-1)2 + (-0.5-1)

2 = 10.46

Así que la métrica para el nodo j es 10.46. La métrica de camino para el nodo r es

mj =10.46+(1.3-1)2 + (0.2-1)

2 = 11.19

28


mi =9.5+(1.3-(-1))2 + (0.2-1)

2 = 15.43

De modo que la métrica para el nodo r es 11.19. Finalmente, para el nodo s se tiene

mj =10.6+(1.3-1)2 + (0.2-(-1))

2 = 11.99

Por lo tanto, aparentemente el trazo hacia atrás sería siguiendo la trayectoria r → j → q.

Con respecto a códigos convolucionales y algoritmo de Viterbi es suficiente con lo tratado hasta el

momento, sólo resta incluir las simulaciones y los resultados arrojados por ellas. Antes, es preciso incluir

información relacionada con la Codificación trellis para saber el porqué de la importancia de los códigos

convolucionales.

V. MODULACIÓN CODIFICADA TRELLIS (TCM)

La modulación codificada trellis es un método simple para diseñar esquemas de modulación que

puedan lograr un buen desempeño general. Este esquema de modulación-codificación se basa en el

concepto de mapeo por par de conjuntos desarrollado por Ungerboeck (1982). El mapeo por

particionamiento de conjuntos puede utilizarse conjuntamente con ambos tipos de códigos,

convolucionales y de bloques, pero debido a la existencia de un algoritmo de decodificación con decisión

suave simple y óptimo (el algoritmo de Viterbi), se ha empleado mayoritariamente con convolucionales.

Cuando se utiliza con códigos convolucionales, el esquema de modulación resultante se conoce como

modulación codificada trellis.

En la modulación codificada se logra una ganancia de codificación a través del incremento del tamaño

de la constelación de la señal, en lugar de incrementar la tasa de símbolos como en los esquemas FEC

convencionales. El incremento del tamaño de la constelación genera la redundancia necesaria para llevar a

cabo la FEC. La figura 8 ilustra el concepto de este tipo de modulación. El modulador o mapper de la figura

8(a) se modifica en la figura 8(b) de modo que k bits de entrada generan una constelación de 2k+1

símbolos

en lugar de 2k. Entonces duplicando el tamaño de la constelación podemos utilizar un código convolucional

de razón (n-1/)/n. Lo importante aquí es que un símbolo de salida todavía es generado por cada k bits de

datos, de modo que la tasa y el ancho de banda no se modifican, aún habiendo agregado el FEC. Es

29


( ) ( )( ) ( ) ( )( ) ( ) ( )( )( )

.2

5

23234232822416

1

2

0

2

0

2

0

2

0

2

0

2

0

2

0

d

ddddddEs

=

+++++=

importante resaltar que los sistemas TCM las funciones de codificación y mapeo se diseñan en conjunto

como se indica en la figura 8(b), esto con la intención de reducir la complejidad del decodificador.

Para comenzar con el estudio de TCM hay que repasar el concepto de constelación de señales. Una

constelación de señales S es un subconjunto de los reales ℜ o al plano 2ℜ (algunas veces considerado

como el plano complejo). La constelación unidimensional se usa en la modulación por desplazamiento de

amplitud (amplitude shift keying ASK), y la constelación unidimensional con dos puntos bE± se llama

frecuentemente modulación binaria por desplazamiento de fase (binary phase-shift keying BPSK). Una

constelación de dos dimensiones con todos los puntos sobre un círculo se conoce como constelación phase

shift keying (PSK). La constelación con frecuencia se expresa en términos del número de puntos, tales como

4-PSK, 8-PSK, o 16-PSK. La constelación 4-PSK también se conoce como QPSK. En la figura 9 podemos ver

estas constelaciones. En la figura se tiene que la energía de las constelaciones es Es. La distancia mínima

entre los puntos de señal se denota como d0. La constelación con bidimensional con puntos en una

cuadricula se denomina modulación en cuadratura de amplitud (QAM).

La densidad espectral η de una constelación es el número de bits portados por cada símbolo.

Asumiendo que los bits son idénticamente distribuidos, la energía promedio por símbolo Es, es el promedio

de el cuadrado de las distancias de los puntos de la constelación al origen. Por ejemplo, para la constelación

16- QAM con distancia mínima d0,

La energía promedio por bit está dada por sb EEη1

= . Además para una constelación cuadrada con M

puntos resulta que .6

1 2

0dM

Es

−=

Los elementos de un punto (a1, a2) ∈ S ⊂ 2ℜ de una constelación, representan las amplitudes de dos

funciones base, las cuales se denotan como φ1(t) y φ2(t), y se consideran ortonormales ( es decir, que

tienen energía unitaria y son ortogonales entre sí ). Además un corrimiento de estas funciones por el

periodo de los símbolos (T) sigue siendo ortogonal,

0)()( =−∫∞

∞−dtkTtt ii ϕϕ con i=1,2,…, para todos los enteros k ≠ 0.

La señal transmitida s(t) se obtiene al yuxtaponer una secuencia de señales base escaladas, cada una

con su propia amplitud representada por el símbolo transmitido

30


∑ −+−=k

kk kTtakTtats ).()()( 2,21,1 ϕϕ

Finalmente, en el receptor la señal recibida r(t) es otra vez proyectada sobre el plano de la constelación

de señales por un conjunto de filtros. En cada intervalo de símbolos, cuando se ha recibido el punto (r1, r2),

el detector de máxima probabilidad (ML por sus siglas en inglés) determina el punto de la constelación más

cercano a (r1, r2). Es importante mencionar que los esquemas TCM más sencillos (cuatro estados) pueden

mejorar en 3dB la ganancia total del sistema, mientras que los más complejos pueden sobrepasar los 6dB.

Otro concepto de vital importancia para el estudio de los esquemas TCM es el de particionamiento de

conjuntos que consiste en la subdivisión de la constelación más grande en pequeños subconjuntos lo que da

como resultado que la distancia euclidiana d0 entre los puntos de los subconjuntos de cada nivel es

substancialmente incrementada. El particionamiento será repetido k+1 veces hasta que la distancia dk+1 es

igual o más grande que la distancia libre deseada para el esquema TCM que se esté diseñando. Los

subconjuntos obtenidos finalmente, etiquetados como D0, D1, D2, ..., D7, en el caso de la figura 11 serán

llamados subconjuntos. La forma de etiquetar las ramas en el diagrama de particionamiento para los k+1

bits codificados 0,,1 n

k

n cc K , de acuerdo a la figura 11 genera la etiqueta que se denota como cn =

[ ]0,,1 n

k

n cc K para cada subconjunto. La etiqueta determina la posición del subconjunto en el diagrama.

Esta forma de etiquetar da paso a una importante propiedad. Si las etiquetas de dos subconjuntos

coinciden en las pasadas q posiciones, pero no en el bit q

nc , entonces las señales de los dos subconjuntos

son elementos del mismo subconjunto en el nivel q del diagrama de particionamiento; por lo tanto las

señales tienen al menos la distancia dq.

En la trellis, las señales de los subconjuntos se han asociado con las 22k transiciones paralelas. La

distancia libre de un código TCM se puede expresar entonces como:

dfree= Min[dk1+1,dfree(k1)],

donde dk1+1 es la distancia mínima entre transiciones paralelas y dfree(k1) denota la distancia mínima entre

trayectorias no paralelas del diagrama trellis. En el caso especial en el que k1=k2 los subconjuntos sólo

contienen una señal y por tanto no hay transiciones paralelas en el diagrama (más adelante se aclarara el

porqué de este hecho).

En la figura 13 se observa el diagrama de bloques de un codificador TCM en donde un bloque de

longitud k se divide en dos subbloques de longitudes k1 y k2 respectivamente. Los primeros k1 bits se aplican

a un codificador binario (N1, k1). La salida del codificador consiste en n1 bits. Esos bits se utilizan para elegir

una de las 12nparticiones de la constelación. Esto significa que la constelación ha sido particionada en 12n

31


subconjuntos. Después de que la constelación ha sido elegida, los k2 bits restantes se utilizan para elegir

uno de los puntos de la constelación elegida. Esto significa que existen 22kpuntos en cada partición. En

consecuencia, la partición que se utiliza contiene 12nsubconjuntos y cada subconjunto contiene 22k

puntos. Esto determina una regla para determinar el tamaño de la constelación requerido y cuántos pasos

de particionamiento deben seguirse sobre la constelación.

Ungerboeck (1982) demostró que eligiendo n1 = k1+1 y k2=1 y utilizando códigos convolucionales

simples es posible diseñar esquemas de modulación codificados que logran una ganancia total de

codificación entre 3 y 6 dB.

Ejemplo 6: En la figura 14 se tiene un esquema TCM con k1= 1, n1=2 y k2=1. La constelación tiene 212 kn +

=23 = 8 puntos, que están particionados en 12n

= 22 =4 subconjuntos cada uno de los cuales contiene 22k

=

21=2 puntos. La constelación elegida aquí es 8-PSK y se particiona como se ilustra en la figura 11. El

codificador convolucional que se usa tiene una taza R= ½. La longitud de restricción se puede elegir de

manera que se obtenga la ganancia de codificación deseada. Como veremos más adelante, en los resultados

de las simulaciones, para longitudes de restricción mayores se tiene una mayor ganancia al precio de

incrementar la complejidad del codificador/decodificador además de los cálculos computacionales se

incrementan considerablemente. En este ejemplo se tienen una longitud de restricción de 3. En la figura

14(b) se incluye una etapa del diagrama trellis.

Como se puede ver en el diagrama trellis, hay una particularidad en relación con la trellis común de un

codificador convolucional, se trata de que aquí se tienen dos caminos que conectan dos estados. Esto se

debe a que existe un bit de más, k2=1, que selecciona un punto en cada partición. En realidad, los dos

caminos paralelos que conectan dos estados corresponden a una partición, y cualquier camino simple

corresponde a un punto en la partición.

A continuación incluyo unas reglas que se deben seguir para conseguir un buen desempeño de los

esquemas TCM:

1.- Las transiciones en paralelo corresponden a puntos de señal en una única partición en la etapa

siguiente del particionamiento. En el ejemplo anterior, C0 = {D0, D4}, C2 = {D2, D6}, C1={D1, D5}, y C3 = {D3, D7}

corresponden a transiciones en paralelo. Esos puntos están separados por una distancia Euclidiana máxima

de d2= sε2 .

32


2.- Las transiciones que se originan y vuelven a cualquier estado se asignan en la siguiente etapa del

particionamiento que tiene una partición pariente simple en la etapa precedente. En el ejemplo anterior

esas particiones serían B0 = {C0, C2} Y B1 = {C1, C3}. La distancia máxima en este caso es d1= sε2 .

3.- Los puntos de señal deberían ocurrir con igual frecuencia.

El funcionamiento de la trellis de la figura 14(b) se basa en el concepto antes mencionado, la distancia

libre (dfree), para determinar esta distancia se consideran primero las transiciones en paralelo ya que suelen

tener la menor dfree, en nuestro caso tenemos que esta distancia vale sd ε22 = . En la figura 15 se

muestra también otro posible camino con dfree, sin embargo, la distancia euclidiana entre esos dos caminos

es sddd ε58.42 2

1

2

0

2 =+= .

Es evidente que este valor es mayor que la distancia de los caminos paralelos por lo que para este

código se elige una la dfree= sd ε22 = .

Ahora la pregunta es: ¿La distancia euclidiana elegida es la que realmente proporciona el mejor

desempeño para el esquema TCM que se maneja?, para poder responder a esta pregunta nos basamos de la

cantidad

DCd

d

E

E

free

free

s

s γγγ =

=

2

codificada,

2

codificar sin,

codificada,

codificar sin,

que se conoce como ganancia de codificación del código. En esta fórmula dfree, sin codificar es la distancia

mínima entre los puntos de la constelación original y dfree, codificada es la distancia mínima que se tiene en la

codificación. El término

=

codificada,

codificar sin,

s

s

E

ECγ se conoce como factor de expansión de la constelación y

cuenta la energía promedio de las constelaciones – a mayor energía promedio en la constelación de

codificación se reduce la ganancia de codificación. El factor

=

2

codificada,

2

codificar sin,

free

free

d

dDγ se llama factor de

distancia incrementada. En este caso vale 1 por que en las constelaciones PSK se requiere la misma energía

por símbolo. Con frecuencia la ganancia de codificación γ se expresa en decibeles (dB) de la siguiente

forma: γdB = 10log10(γ).

Tomando en cuenta lo anterior y considerando que la distancia entre la trayectoria C0 y C0, donde en un

caso se envía el símbolo D0 y en otro caso se envía D4. Entonces la distancia es:

d2

= (D0, D4)= sd ε42

2 =

33


la cual es más pequeña que la distancia que hemos encontrado. De esta manera, la ganancia de codificación

para nuestro ejemplo es dBs

s 322

4≅==

εε

γ . De esta manera podemos demostrar que este esquema de

codificación proporciona la mejor ganancia de codificación para un código TCM de cuatro estados sin

incrementar el ancho de banda. No hay que pasar por alto para lograr esta ganancia se incrementa la

complejidad de el codificador/decodificador.

Las trellis de más de 4 estados producen mayores ganancias de codificación. Como demostró

Ungerboeck con varias simulaciones por computadora los esquemas con 8, 16, 32, 128 y 256 estados se

pueden lograr ganancias de codificación en el rango de 3.6 a 5.75 dB.

Existen sistemas de comunicaciones en donde es de vital importancia mantener un ancho de banda

reducido como las comunicaciones digitales en canales telefónicos, las comunicaciones espaciales, los

módems para líneas telefónicas y los reproductores de discos compactos. Es en estas áreas donde ha

tenido gran auge el uso de la modulación codificada.

VI. SIMULACIÓN Y RESULTADOS

En esta sección se incluyen los códigos fuente de los programas de prueba así como los resultados

obtenidos con ellos.

En primer lugar se incluye el código fuente de un programa en turbo C que hace la codificación,

simulación de un canal con AWGN y decodificación, usando el algoritmo de Viterbi con decisión

suave, de una cadena de datos que el usuario mismo introduce además de las características

básicas del codificador convolucional como son: el numero de entradas, salidas y elementos de

memoria (para poder determinar la longitud de restricción del codificador).

Es preciso mencionar que el programa incluye funciones declaradas de manera externa pero por

facilidad se incluyen en el código fuente.

34


En la figura A se presenta una impresión de la pantalla de resultados al ejecutar este programa.

El desempeño de la codificación convolucional depende en gran medida de la longitud de restricción

del codificador y del tipo de cuantización en la decodificación, como se señala en [3], para medir el

desempeño del proceso de codificación/decodificación se utiliza lo que anteriormente se mencionó, la

razón de error por bit (BER, por sus siglas en inglés). Además de esto en las simulaciones existe un factor

más que puede hacer variar los resultados, se trata de la longitud de la ventana de decodificación, para

evitar complicar más el proceso se decidió fijar el valor de éste parámetro al valor utilizado con mayor

frecuencia, 32 bits. Considerando que se maneja un codificador de ranzón R = ½ con una decodificación con

decisión dura entonces se procede a medir el desempeño del codificador con respecto a la longitud de

restricción. Para lograr esto se creó el siguiente programa en Matlab que simula el proceso de codificación,

el paso por un canal AWGN y la decodificación con el método de Viterbi con decisión dura para diferentes

valores de longitud de restricción y, por tanto diferentes polinomios generadores, éstos últimos se listan en

seguida en notación de polinomio y en notación octal:

TABLA A: Diferentes longitudes de restricción usadas para la simulación

k g1(x) g2(x) g1(x)oct g2(x)oct dfree 3 1+x

2 1+x+x

2 5 7 5

4 1+x+x3 1+x+x

2+x

3 15 17 6

5 1+x3+x

4 1+x+x

2+x

4 23 35 7

6 1+x2+x

4+x

5 1+x+x

2+x

3+x

5 53 75 8

7 1+x2 +x

3+x

5+x

6 1+x+x

2+x

3+x

6 133 171 10

8 1+x2 +x

5+x

6+x

7 1+x+x

2+x

3+x

4+x

7 247 371 10

El programa consiste en una función que se encarga de realizar la simulación en base a los siguientes

parámetros:

1.- EbN0_dB. Es el o los valores de la Relación Señal a Ruido en decibeles (RSR dB).

2.- K. La longitud de restricción deseada para el codificador.

3.- codegen. Los valores de las secuencias generadoras introducidas como una matriz en notación octal,

por ejemplo codegen = [5 7].

4.- decisión. El tipo de decisión con el que se desea realizar la decodificación, éste es un dato de tipo

cadena de caracteres ya sea ‘dura’ para decisión dura o ‘suave’ para decisión suave.

En las figuras B, C y D, se observan las gráficas de los resultados obtenidos mediante la ejecución del

programa. Se presenta la gráfica de la BER vs. La Relación señal a Ruido en decibeles. Si se comparan los

35


datos de la gráfica de la figura A con los presentados en [3] se puede ver la gran similitud entre ellos, de

manera que se confirma el comportamiento en el desempeño de un codificador convolucional al variar la

longitud de restricción. Esta primera etapa de prueba fue superada, sin embargo había todavía que verificar

que para estos mismos codificadores y en las mismas condiciones excepto que bajo una decodificación con

decisión suave se lograra (según lo descrito anteriormente) esa ganancia de 2 dB en los resultados. Aquí se

encontró un ligero problema pues primero, aplicando los umbrales de decisión directamente sobre los

datos obtenidos del canal, se obtuvieron los resultados que se presentan en la figura B. Aquí hubo partes

en las que tal ganancia no se alcanzaba, sobre todo para k=7 por lo que se tomó la decisión de aplicar un

concepto que se manejaba en una de las fuentes consultadas, realizar una cuantización adaptativa.

Se trata de normalizar los datos obtenidos del canal en base a la Eb/N0 dB que se maneja, y por tanto

de la varianza. De esta forma los datos que se encuentran muy dispersos se acercan más hacia los

umbrales de decisión y con ello se reduciría considerablemente la incidencia de error. Como última

alternativa se procedió a agregar este concepto a la parte de decodificación del programa logrando con ello

conseguir la ganancia deseada en todos los codificadores/decodificadores simulados. Los resultados se

pueden observar en la figura D.

Es importante hacer mención que, debido a la gran cantidad de cálculos y operaciones de cómputo que

implica simular todos los codificadores incluidos en la tabla A, se optó por realizar sólo los que en [3] se

proponen.

Instituto Politécnico Nacional

FIGURA A: Imagen de la pantalla que presenta el programa que simula una

Codificación

nico Nacional | La Modulación Codificada Entramada TC


Codificación / decodificación de una secuencia de datos.

36

TCM 36


37


FIGURA B: BER como función de la RSR para un codificador R= ½ con una ventana de 32 bits y decodificación con el

algoritmo de Viterbi usando decisión dura.

38


FIGURA C: BER como función de la RSR para un codificador R= ½ con una ventana de 32 bits y decodificación con el

algoritmo de Viterbi usando decisión suave con 8 niveles de cuantización.

39


FIGURA D: Decisión suave adaptada según la RSR que se proporciona como argumento.

Sólo resta mencionar que para verificar el buen comportamiento del módulo de software desarrollado

para simular el canal AWGN que se está manejando, se comparó con el comportamiento teórico del paso

de una señal BPSK no codificada por dicho canal. Esto se realizo con la aplicación de la función

Q(sqrt(2*EbN0)) que genera datos con distribución gaussiana. Teniendo como resultado las gráficas

presentadas en la figura E, de esta manera podemos decir que el canal AWGN que se implemento es

confiable y puede ser usado en nuestras simulaciones.

Los resultados arrojados por este programa se presentan a continuación:

40


FIGURA E: Resultados teóricos vs. canal AWGN simulado.

41


VII. CONCLUSIONES

Como se pudo ver en los resultados de las simulaciones, los códigos convolucionales en combinación

con el algoritmo de Viterbi proporcionan un buen desempeño en cuanto a la tasa de error que manejan, y

más aún si la decodificación se realiza con decisión suave. Es por ello que en la actualidad se utilizan

ampliamente en las comunicaciones digitales y su estudio facilita una mejor comprensión de la codificación

modulada TCM que utiliza éstas dos herramientas para proporcionar mayores ganancias de codificación de

datos.

El presente trabajo documenta el uso de técnicas de codificación TCM en estándares de comunicación y

presenta resultados de la simulación de este tipo de sistemas, de manera que se convierte en una

herramienta muy valiosa para introducirse al manejo de técnicas más sofisticadas de control de error.

42


VIII.- FUENTES DE INFORMACION

• BIBLIOGRAFICAS: [1] Christian B. Shlegel and Lance C. Pérez “Trellis and Turbo Coding”, 2004 Institute of

Electrical and Electronics Engineers.

[2] Todor Koolev “Wireless Communication Standards”, Ed. IEEE pág. 100-105

[3] Tood K. Moon “Error correction coding”, mathematical methods algorithms, Ed. Wiley

interscience, 2005, pp 453-580.

[4] Shu Lin & Daniel J. Costello “Error control coding” fundamentals and applications, Ed.,

Prentice Hall, pp. 287-348.

[5] Stephen B. Wicker “Error control systems” for digital communication and storage, Ed.

Prentice Hall, 1995, pp 269-330, 356- 390.

[6] Graham Wade “Coding techniques” an introduction to compression and error control,

Ed. Palgrave, 2000.

• DE INTERNET: * http://www.eie.fceia.unr.edu.ar/ftp/Radioenlaces/1502.pdf

* http://bips.bi.ehu.es/~inma/psc/

* http://fiee.uni.edu.pe/publicaciones/TecniaEsp/10art/index.html

* http://w3.iec.csic.es/ursi/articulos_gandia_2005/articulos/SC3/327.pdf

* http://personales.unican.es/perezvr/pdf/CH3%20TV.pdf

* http://www.engineering.usu.edu/ece/faculty/tmoon/eccbook/FILES/

* http://home.netcom.com/~chip.f/viterbi/tutorial.html

* http://internet-solutions.com.co/deacosta/tcm/refuerzo_convol/frame.html

* http://home.netcom.com/~chip.f/viterbi/examples.html

Documents

La Modulación Codificada Entramada (TCM) en los nuevos ...sappi.ipn.mx/cgpi/archivos_anexo/20071367_5395.pdfW, la densidad espectral de potencia del ruido N 0, y la potencia de la