CUESTIONARIO DE PREGUNTAS GRUPO 4

1. Explique los principales métodos usados en la codificación de canal para la detección y corrección de errores (EDC, ECC, EDAC, FEC)

Codificación de canal

Durante el proceso de comunicaciones hay miles de eventos que influyen en el deterioro de la señal de información, para ello requerimos muchas formas de proteger nuestra moduladora, la codificación de canal desarrolla un papel fundamental en el proceso de la comunicación ya que realiza el proceso de protección en contra del ruido en el canal de información. En este canal pueden haber muchos ruidos que llegan a degradar total o parcialmente nuestra señal; principalmente se tienen ruidos como: ruido blanco, ruido rosa, ruido impulsivo, ruido intermitente. Esta codificación de canal también ejecuta un elemento fundamental en la comunicación y es la redundancia de información, con el fin de revestir nuestra señal de seguridad en la forma de comunicación.

La fidelidad de la transmisión de información se mide en términos de la tasa de errores o probabilidad de error es decir, la probabilidad de que el símbolo a la salida del receptor o reproductor sea diferente al símbolo transmitido o grabado. Tanto los sistemas de transmisión como de grabación y reproducción están sujetos a errores [1].

Imagen tomada de: http://sertel.upc.edu/tdatos/Transparencias/CodCanPant.pdf

Cuando hablamos de codificación de canal tenemos que tener en cuenta que este tipo de sistemas nos permiten proteger nuestra información y nos ofrecen servicios distintos tales como recuperación o detección de bits erróneos ,códigos de detección y corrección de errores, dichos

códigos están representados por las siglas EDC(código detector de errores), ECC(código corrector de errores ) y FEC(Correccion de errores hacia adelante)

CODIGOS DE DETECCION DE ERRORES

Es una importante práctica para el mantenimiento e integridad de los datos a través de diferentes procedimientos y dispositivos como medios de almacenamiento confiables. Se considera como precursor de este tipo de tecnologías el Acme Comodity and Phrase Code usado en los telegramas

La comunicación entre varias computadoras produce continuamente un movimiento de datos,

generalmente por canales no diseñados para este propósito (línea telefónica), y que

introducen un ruido externo que produce errores en la transmisión.

Por lo tanto, debemos asegurarnos que si dicho movimiento causa errores, éstos puedan ser

detectados. El método para detectar y corregir errores es incluir en los bloques de datos

transmitidos bits adicionales denominados redundancia.[2]

Incluir sólo la información redundante necesaria en cada bloque de datos para detectar

los errores. En este caso el número de bits de redundancia es menor. Se utilizan

códigos de detección de errores

PARIDAD SIMPLE: Consiste en añadir un bit de más a la cadena que queremos enviar, y que nos indicará si el número de unos (bits puestos a 1) es par o es impar. Si es par incluiremos este bit con el valor = 0, y si no es así, lo incluiremos con valor = 1.

Ejemplo de generación de un bit de paridad simple:

Queremos enviar la cadena “1110100”:

1º Contamos la cantidad de unos que hay: 4 unos

2º El número de unos es par por tanto añadimos un bit con valor = 0

3º La cadena enviada es 11101000

Tomado de: https://es.wikipedia.org/wiki/Detecci%C3%B3n_y_correcci%C3%B3n_de_errores

Este método es bastante efectivo sin embargo presenta grandes problemas que se confunda con información dentro de la trama, además de esto presenta problemas cuando cambio dos bits de la misma trama.

CODIGOS DE BLOQUE:

Un código de bloque se genera cuando la secuencia de información de longitud K se procesa dentro de un registro de longitud fija L, donde L < K (ver Figura 3.1). Este bloque de tamaño L se presenta como el codificador del canal, el cual genera uno de los M posibles símbolos del alfabeto

{Xk}1 , {Xk}2 , . . . , {Xk}M , k = 1, ..., L, donde M = DL y D es la longitud del alfabeto básico de la secuencias (el cual se considera binario (D = 2), si no se expresa otra cosa). El código de bloques queda entonces compuesto por un vector de dimensiones X (K, L) ∗ L, donde L es el número de columnas y X (K, L), el cual es una función dependiente de la técnica utilizada, es el número de filas. En la mayoría de los casos X (K, L) = K.[3]

Algoritmo Viterbi

Imagen tomada de: http://www.virtual.unal.edu.co/cursos/sedes/manizales/4040051/html/capitulos/cap_iii/codigos_de_deteccion_de_errores.pdf

La capacidad de detección de errores depende básicamente de la velocidad de los datos , si los datos van a una tasa de transferencia muy alta la redundancia será alta pero también afectara el BER mientras que si la tasa de transferencia es baja la detección de errores será eficaz y tendremos un BER bajo.

CODIGOS DE AUTOCHEQUEO (ECC)

El hecho de añadir un único bit de paridad no siempre resulta suficiente para datos que se

mueven constantemente de un lado para otro, especialmente en el caso de transmisión de

datos a largas distancias, donde las señales transmitidas están expuestas a interferencias

eléctricas (por ejemplo: en una red de computadoras, donde los datos viajan de

una computadora a otra que puede estar, incluso, en otro país).

Este problema ha conducido al desarrollo de códigos que detectan más de un error e incluso

corrigen los errores que encuentran.

Algunas de estas técnicas han sido desarrolladas por el ingeniero estadounidense Richard W.

Hamming, y se conocen como Códigos de Hamming.[4]

CODIGO DE REDUNDANCIA CICLICA

Este tipo de código se usa básicamente para la detección de errores en la cual se verifica a través

de ciertos bits de que están repetidos o redundantes en la comunicación con el fin de identificar

ciertos cambios en cadena transmitida

La verificación de redundancia cíclica consiste en la protección de los datos en bloques,

denominados tramas. A cada trama se le asigna un segmento de datos denominado código de

control (al que se denomina a veces FCS, secuencia de verificación de trama, en el caso de una

secuencia de 32 bits, y que en ocasiones se identifica erróneamente como CRC). El código CRC

contiene datos redundantes con la trama, de manera que los errores no sólo se pueden detectar

sino que además se pueden solucionar.

CODIGOS EDAC

La EDAC es una memoria protegida particularmente deseable para aplicaciones de alta tolerancia a fallos, como los servidores, así como aplicaciones de espacio profundo debido al aumento de la radiación.

Controladores de memoria de corrección de errores que tradicionalmente utilizan códigos de Hamming, aunque algunos utilizan la redundancia modular triple.

Intercalado permite distribuir el efecto de un solo rayo cósmico potencialmente múltiples bits físicamente vecinos molestos a través de múltiples palabras asociando bits de vecinos de diferentes palabras. Mientras un malestar solo evento (SEU) no supera el umbral de error (por ejemplo, un solo error) en cualquier palabra en particular entre los accesos, se puede corregir (por ejemplo, mediante un código de corrección de errores de un solo bit), y la ilusión de un sistema de memoria libre de errores puede ser mantenido.

Además del hardware que proporciona las características necesarias para la memoria ECC para operar, sistemas operativos generalmente contienen relacionadas instalaciones de informes que se utilizan para proporcionar notificaciones cuando los errores de software se recuperan de forma transparente. Un creciente tasa de errores de software podría indicar que un módulo DIMM necesita ser reemplazado, y dicha información de realimentación no sería fácilmente disponible sin las capacidades de informes relacionados. Un ejemplo es el subsistema del kernel de Linux EDAC (anteriormente conocido como Bluesmoke), que recoge los datos de los componentes de comprobación de errores habilitado en el interior de un sistema informático; junto recoger e informar los eventos relacionados con la memoria ECC, también soporta otros errores de suma de comprobación, incluidos los detectados en el bus PCI. [5]

CODIFICACION FEC: Corrección de errores hacia adelanteDiagrama de codificación FEC

Imagen tomada de: Codificacion de Canal: Codigo Hamming y Codigo Convolucional, Mariangela Mezoa, pag 5

Es un tipo de mecanismo de corrección de errores que permite su corrección en el receptor sin retransmisión de la información original. Se utiliza en sistemas sin retorno o sistemas en tiempo real donde no se puede esperar a la retransmisión para mostrar los datos. Este mecanismo de corrección de errores se utiliza por ejemplo, en las comunicaciones vía satélite,

en las grabadoras de DVD y CD o en las emisiones de TDT para terminales móviles (estándar DVB-H), concretamente en este último caso se trata de un tipo especial de FEC, el denominado MPE-FEC.

2. Mencione y explique la técnica de codificación de canal denominada como “CODIGO HAMMING”.

CODIGO HAMMINGCódigo de Hamming es un código detector y corrector de errores que lleva el nombre de su inventor, Richard Hamming. En los datos codificados en Hamming se pueden detectar errores en un bit y corregirlos, sin embargo no se distingue entre errores de dos bits y de un bit (para lo que se usa Hamming extendido). Esto representa una mejora respecto a los códigos con bit de paridad, que pueden detectar errores en sólo un bit, pero no pueden corregirlo.

Algoritmo de código haming 1. Todos los bits cuya posición es potencia de dos se utilizan como bits de paridad (posiciones 1, 2, 4, 8, 16, 32, 64, etc.). 2. Los bits del resto de posiciones son utilizados como bits de datos (posiciones 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc.). 3. Cada bit de paridad se obtiene calculando la paridad de alguno de los bits de datos. La posición del bit de paridad determina la secuencia de los bits que alternativamente comprueba y salta, a partir de éste, tal y como se explica a continuación.

* Posición 1: salta 1, comprueba 1, salta 1, comprueba 1, etc. * Posición 2: comprueba 1, salta 2, comprueba 2, salta 2, comprueba 2, etc. * Posición 4: comprueba 3, salta 4, comprueba 4, salta 4, comprueba 4, etc. * Posición 8: comprueba 7, salta 8, comprueba 8, salta 8, comprueba 8, etc. * Posición 16: comprueba 15, salta 16, comprueba 16, salta 16, comprueba 16, etc. * Y así sucesivamente.

Así pues en la Posición 1, comprobaríamos los bits: 3, 5, 7, 9, 11...; en la Posición 2, los bits: 3, 6, 7, 10, 11, 14, 15...-; en la Posición 4 tendríamos: 5, 6, 7, 12, 13, 14, 15... Así hasta completar la nueva cadena. 1. Todos los bits cuya posición es potencia de dos se utilizan como bits de paridad (posiciones 1, 2, 4, 8, 16, 32, 64, etc.). 2. Los bits del resto de posiciones son utilizados como bits de datos (posiciones 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc.). 3. Cada bit de paridad se obtiene calculando la paridad de alguno de los bits de datos. La posición del bit de paridad determina la secuencia de los bits que alternativamente comprueba y salta, a partir de éste, tal y como se explica a continuación.

* Posición 1: salta 1, comprueba 1, salta 1, comprueba 1, etc. * Posición 2: comprueba 1, salta 2, comprueba 2, salta 2, comprueba 2, etc. * Posición 4: comprueba 3, salta 4, comprueba 4, salta 4, comprueba 4, etc. * Posición 8: comprueba 7, salta 8, comprueba 8, salta 8, comprueba 8, etc. * Posición 16: comprueba 15, salta 16, comprueba 16, salta 16, comprueba 16, etc. * Y así sucesivamente.

Así pues en la Posición 1, comprobaríamos los bits: 3, 5, 7, 9, 11...; en la Posición 2, los bits: 3, 6, 7, 10, 11, 14, 15...-; en la Posición 4 tendríamos: 5, 6, 7, 12, 13, 14, 15... Así hasta completar la nueva cadena. [7]

3. Mencione y explique la técnica de codificación de canal denominada como “CODIGOS CONVOLUCIONALES”

CODIGOS CONVOLUCIONALES

Un código convolucional es un tipo de código de detección de errores donde:

1. Cada símbolo de m bits de información se transforma, al ser codificado, en un símbolo de n bits, donde m/n es la tasa del código (n ≥ m)

2. La transformación es función de los k símbolos anteriores, donde k es la longitud del código

CARACTERISTICAS

Los códigos convolucionales son códigos lineales al igual que los códigos bloque (como los códigos de Hamming, por ejemplo) y, por tanto, se utilizan para proteger la información añadiendo redundancia a la misma, de manera que las palabras del código tengan la distancia mínima necesaria.

Sin embargo, a diferencia de los códigos bloque, las palabras de un código convolucional se generan no sólo a partir de los dígitos de información actuales sino también con la información anterior en el tiempo. Es decir, un codificador convolucional es un sistema con memoria y, en consecuencia, lleva asociada una cadena de Markov aunque ésta no es visible en la salida pero sí la condiciona.

CodificaciónExisten varios métodos de codificación de códigos convolucionales, aunque una de la más usuales es la basada en registros de desplazamiento conectados con sumadores base 2 en los que se realiza la codificación. Por cada bit que entre en el codificador se obtienen n bits.

DecodificaciónLa decodificación de un código convolucional consiste en escoger la secuencia más probable entre todas las posibles. Existen diversos algoritmos que permiten la decodificación de este tipo de códigos y la decodificación óptima se consigue mediante el algoritmo de Viterbi.[8]

    Ejemplo: Codificador convolucional (2,1,3)

El conmutador con las dos entradas hace el papel de un registro de desplazamiento de dos

estados.

El código convolucional es generado introduciendo un bit de datos y dando una revolución

completa al conmutador.

Inicialmente se supone que los registros intermedios contienen ceros.

 En este ejemplo la palabra codificada se obtiene como resultado de sumas módulo-2 entre los bits indicados que están almacenados en los registros intermedios.supongamos que se quiere enviar la secuencia de bits 0101 (donde los bits más a la derecha son los más antiguos). El proceso de codificación es el siguiente:

Se introduce el primer bit de la secuencia en el codificador:

Se introduce el segundo bit de la secuencia en el codificador:

Se introduce el tercer bit de la secuencia en el codificador:

Se introduce el cuarto bit de la secuencia en el codificador:

      Al final del proceso de codificación obtenemos que la secuencia codificada es 01 01 01 11.Sigamos con la exposición del proceso de codificación.Debido a la memoria del código es necesario de disponer de medios adecuados para determinar la salida asociada a una determinada entrada.    Hay tres métodos gráficos:

Diagrama árbol o árbol del código: representación mediante un árbol binario de las

distintas posibilidades.

Diagrama de estados: es la forma menos utilizada.

Diagrama de Trellis o enrejado: es la forma más utilizada porque es la que permite

realizar

la decodificación de la forma más sencilla.

    Para el ejemplo del codificador (2,1,3) anteriormente especificado tenemos el siguiente Arbol del código:Para el ejemplo del codificador (2,1,3) anteriormente especificado tenemos el siguiente Arbol del código:

    La profundidad del árbol es 2· (m-1), y el número de estados es 2 (m-1) . k

    La interpretación del árbol del código es la siguiente: Hay dos ramas en cada nodo.  

La rama superior corresponde a una entrada de un 0.

La rama inferior corresponde a la entrada de un 1.

En la parte exterior de cada rama se muestra el valor de salida.

El número de ramas se va multiplicando por dos con cada nueva entrada.

A partir del segundo nivel el árbol se vuelve repetitivo. En realidad, solo hay cuatro tipos de nodos: A,B,C,D. Estos tipos de nodos en realidad son estados del codificador. A partir de estos nodos, se producen los mismos bits de salida y el mismo estado. Por ejemplo, de cualquier nodo etiquetado como C se producen el mismo par de ramas de salida: Salida 10 y estado A Y Salida 01 y estado B[9 ]

4. Mencione y explique la técnica de codificación de canal denominada como “CODIGOS REED-SOLOMON”

REED SOLOMON

Es un código cíclico no binario y constituye una subclase de los códigos BCH. Los códigos cíclicos son una subclase de los códigos de bloque estándar de detección y corrección de errores que protege la información contra errores en los datos transmitidos sobre un canal de comunicaciones. Este tipo de código pertenece a la categoría FEC (Forward Error Correction), es decir, corrige los datos alterados en el receptor y para ello utiliza unos bits adicionales que permiten esta recuperación a posteriori.[10]

Este código se forma en base a grupos de bits que se denominan símbolos. El código Reed-Solomon trabaja con los símbolos en vez de con los bits individuales.

Un símbolo es una secuencia de "m" bits individuales que aparecen en serie. Un símbolo es erróneo cuando al menos un bit del símbolo tiene error.

El código Reed-Solomon, tiene las siguientes características:

Cada símbolo está constituido por "m" bits consecutivos agrupados.

Cada palabra-código consta de "k" símbolos de información (en lugar de bits), y "r" símbolos

de paridad.

La longitud de la palabra-código es:   símbolos,(longitud=n m expresada en nº de

bit).

Se establece la relación:   entre la longitud de la palabra código (n) y el número

de símbolos ( ).

Es capaz de corregir errores en "t" símbolos, donde  .[10]

REFERENCIAS

1. http://sertel.upc.edu/tdatos/Transparencias/CodCanPant.pdf2. https://es.wikipedia.org/wiki/Detecci%C3%B3n_y_correcci%C3%B3n_de_errores

3. http://www.virtual.unal.edu.co/cursos/sedes/manizales/4040051/html/capitulos/cap_iii/codigos_de_deteccion_de_errores.pdf

4. https://es.wikipedia.org/wiki/C%C3%B3digo_de_correcci%C3%B3n_de_errores5. https://en.wikipedia.org/wiki/Error_detection_and_correction6. Codificacion de Canal: Codigo Hamming y Codigo Convolucional, Mariangela

Mezoa,

7. http://html.rincondelvago.com/codigo-de-hamming.html

8. Tomado de : Codigo convolucional, Ivan Dario Hastamorir, Juan Diego Melenje,

Richard Anderson Rodriguez, Ivan Dario Ladino Fundacion Universitaria los

libertadores

9. dcetxdatos.wikispaces.com/file/view/codigconvolucionales.doc10.https://es.wikipedia.org/wiki/Reed-Solomon