View
3
Download
0
Category
Preview:
Citation preview
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
mmeraz@ipn.mx
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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
FIGURA A: Imagen de la pantalla que presenta el programa que simula una
Codificación / decodificación de una secuencia de datos.
36
TCM 36
FIGURA A: Imagen de la pantalla que presenta el programa que simula una
37
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 40
FIGURA E: Resultados teóricos vs. canal AWGN simulado.
41
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Instituto Politécnico Nacional | La Modulación Codificada Entramada TCM 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
Recommended