Codificación hamming extendido ejemplos 2 bits de error

1. Introducción
2. Funciones (8funciones)
3. Ethernet: Tecnología Ethernet
4. Direcciones MAC (ipconfig)
5. CSMA/CD
6. Detección de errores
6.1. Bit de Paridad
6.1.1. Paridad Simple
6.1.2. Paridad por bloque
6.2. CRC (Código Redundancia)
6.3. Código de Hamming (?)
7. Control de flujo

1. Introducción

Este nivel incluya a los niveles físico y de enlace de OSI.
Misiones:
· Colocar en el (extraer del) medio de transmisión correspondiente
las señales adecuadas de acuerdo con los bits que se quieren
transmitir (recibir).
· Gestionar el acceso al medio si es un medio compartido
· Componer/descomponer tramas
· Detectar los errores de transmisión
· Opcionalmente, corregir los errores de tranmisión o retransmitir
· Opcionalmente, realizar control de flujo (con el siguiente salto)

2. Funciones (8funciones)

2.1.

Iniciación, terminación e identificador

2.2.
Segmentación y Bloqueo à Segmenta las tramas y estas tramas se hacen más pequeñas.
2.3.
Sincronización de estado y carácter à Identifica los bits y saben en que posición están colocados.
2.4.
Delimitación de trama y transparencia à Qué caracteres hay en las tramas
2.5.
Control de errores à Control de paridad, de Hamming y CRC
2.6.
Control de flujo à Sirve para que no haya obstrucción entre diferentes ordenadores.
2.7.
Recuperación de fallos à Controlar situaciones anómalas (defectuosas) como pérdida de trama, ausencia de respuesta, etc.
2.8.
Gestión y Coordinación de la comunicación à Gestionar el ordenador según se utilizan unos métodos u otros. Ej: ALOHA, TOKEM Ring, etc.

3. Ethernet: Tecnología Ethernet

3.1.

Definición:

3.1.1. Estándar de redes de computadora de área local con acceso al medio por contienda CSMA/CD. Define las carácterísticas de cableado y señalización de nivel físico y los formatos de las tramas.
3.2.

Tecnologías Ethernet

:

4. Direcciones MAC (ipconfig)

. Es la dirección física (Es el identificador exclusivo que incluye un fabricante en el hardware)
4.2. MAC à Control de Acceso al Medio
4.3. Tiene 48 bits, los 24 primeros los designa el fabricante y los últimos los designa al protocolo IEEE.
4.4. Todas las que están en la capa 2

5. CSMA/CD

5.1. Protocolo de acceso utilizado en las tarjetas de red
5.2.

Funcionamiento:

5.2.1. Cuando una estación quiere transmitir escucha en el canal si está ocupado espera a que quede libre si está libre transmite mientras transmite sigue escuchando para ver si alguien transmite a la vez, en cuyo caso aborta la transmisión
5.3.

Colisiones

:
5.3.1. Cuando dos estaciones quieren transmitir simultáneamente al ver el canal libre.
5.3.2. Cuando el canal parece libre pero no está debido al retardo de propagación de los paquetes por la red. (Esperar tiempo antes de transmitir)
5.4.

Aloha

· Aparece 1970 la universidad de Hawai
· Fue el primer protocolo de nivel de enlace de datos
· Rendimiento entre 16% y 18%
· Se puede presentar una colisión cuando dos o más estaciones esperan a que se desocupe el canal para empezar a transmitir.
El protocolo ALOHA es un protocolo del nivel de enlace de datos para redes de área local con topología de difusión.
La primera versión del protocolo era básica:
* Si tienes datos que enviar, envíalos.
* Si el mensaje colisiona con otra transmisión, intenta reenviarlos más tarde.
Muchos han estudiado el protocolo. El quid de la cuestión está en el concepto de más tarde. ¿Qué es más tarde? Determinar un buen esquema de parada también determina gran parte de la eficiencia total del protocolo, y cuan determinístico será su comportamiento (cómo de predecibles serán los cambios del protocolo).

5.5. Aloha ranurado

Para mejorar las prestaciones de Aloha se definíó Aloha ranurado (slotted) (Roberts 1972), con la única diferencia de que las estaciones sólo pueden transmitir en unos determinados instantes de tiempo o slots. De esta manera se disminuye el periodo vulnerable a t. Este sincronismo hace que cuando un terminal quiera transmitir debe esperar al inicio del nuevo periodo para hacerlo.

5.6. CSMA 1-persistente

· Siempre está escuchando al canal
· Si está libre, transmite la información
· Si está ocupado, espera a que este libre
· Si detecta una colisión, espera hasta que esta libre
· Nivel de funcionamiento
· Ventaja sobre Aloha
No intenta tomar el medio si este está ocupado.
· En los que la estación X continua escuchando a la línea, y luego envía inmediatamente después de la Y acabados

5.7. CSMA no persistente

· Escucha al canal en intervalos de tiempo alterno
· Si esta ocupado espera un intervalo aleatorio y lo vuelve a comprobar

6. Detección de errores

6.1. Bit de Paridad

· Un bit de Paridad es un digito binario que indica si el número de bits con un valor de 1 en un conjunto de bits es par o impar. Los bits de Paridad constituyen el método de detección de errores más simple.
Bits de datos Par Impar
0000000 00000000 00000001
1010001 10100011 101000110100010 1010001 10100011 10100010
1101001 11010010 110100111010011 1101001 11010010 11010011
1111111 11111111 111111111111110 1111111 11111111 11111110
00110110 001101100 00110110001101101 00110110 001101100 001101101

6.1.1. Paridad Simple

· Detectamos el error, pero no se sabe en que lugar

6.1.2. Paridad por bloque

· Se trata de organizar la información por bloques, forman una tabla por N x M bits. A continuación se calculan los bits de paridad por filas y por columnas. Por ultimo se envían por la línea de transmisión los bits de paridad calculado, junto con los bits que forman el mensaje.
00110, 01010, 11001, 11111
0011 01010 11001 11111 0 0 1 1
01010
· Para detectar un error à lo detecta y lo corrige.

6.2. CRC (Código Redundancia Cíclica , o c)

· La finalidad de este código es crear una parte de redundancia que se añade al final del código que se va a transmitir y que detecte el mayor número de errores posible.
· Se utiliza un polinomio generador que se elige previamente y que tiene la propiedad de minimizar la redundancia. Suele tener una longitud de 16 bits para mensajes de 128 bytes, lo que indica que su eficacia es buena, ya que solo incrementa la longitud del mensaje que se transmite en un valor aproximado de 1,6%.
· La selección del polinomio generador es esencial si se quiere detectar la mayoría de los errores que ocurren.
· Ejemplo Polinomios generadores Estándares
· CRC- 12: X¹² + X¹¹ + X³ + X + 1
· CRC- 16: X¹⁶ +
· Código de obtención del CRC
· Datos:
· Mensaje codificado en binario: 1101010
· Polinomio generador: X⁴ + X + 1
· Operaciones: X⁶ + X⁵ + X³ + X
· Obtener el polinomio equivalente al mensaje que se va a transmitir
· Multiplicar el polinomio obtenido: X ^{GRADO POLINOMIO GENERADOR}
· (X⁶ + X⁵ + X³ + X) ^. X⁴ = X¹⁰ + X⁹ + X⁷ + X⁵ = 11010100000
· Dividir lo que hemos obtenido por el polinomio generador (X^p x mensaje / G(x)
· Obtener el resto de la división y añadir al mensaje original el resto de la división.
· Transmitir M’ix
· El equipo receptor debe comprobar el código CRC para averiguar si se han producido errores o no

· RECEPTOR:
· 1. Acordar G(x)
· 2. Divide el código Recibido (M’ix) entre G(x)

· OPERACIONES
· 1 + 1 = 0
· 0 - 1 = 1
· (Sumar, restar y multiplicar ,,, como en montaje)
1. Se quiere transmitir el siguiente mensaje
· M(x)= 10011011
· G(x)= X³ + 1 à P = 3 [coges siempre el mayor]
· 1001
· M(x)= X⁷ + X⁴ + X³ + X + 1
· M(x)= X³

(X⁷ + X⁴ + X³ + X + 1) = X¹⁰ + X⁷ + X⁶ + X⁴ + X³ = 10011011000
· 10011011000 / 100 = 10001010 (Resto: 00010)
· Resto: 00010 [Cojo 3 por G(x)]
· 10011011000 + 010 = 10011011010 à M’(x)
· El receptor comprueba si hay errores, dividiendo el mensaje que recibe entre polinomio generador
· 10011011010 / 1001 = 10001010 (Resto: 0)

6.3. Código de Hamming (?)

· Es un código dtector y corrector de errores
· La transferencia de datos en ocasiones puede tener errores, una de las maneras de detectar y corregir errores es utilizando este código
· El algoritmo de Hamming (7, 4) puede corregir cualquier error de un solo bit y detecta todos los errores de 2 bits [ (7 bits de datos, 4 bits de paridad) 7+4
· Pasos:
· Primero se añaden tantos bits de paridad como sean necesarios de forma que se cumpla que 2^K > n + K
N à nº de bits de Datos
K à nº bits de paridad
· Segundo: Todos los bits cuya posición es potencia de 2, se utilizan para colocar los bits de paridad. Por lo tanto las posiciones serán 1, 2, 4, 8, 16, 32, 84… etc.
· Tercero: Los bits del resto de posiciones son utilizados como bits de datos.
· Cuarta: Numerar (de derecha a izquierda) izquierda a derecha los bits por 1, 2, 3, 4…
· Cinco: Cada Bit de paridad se obtiene calculando la paridad de alguno de los bits de Datos, de la siguiente manera:
· El receptor comprueba que el mensaje es correcto recalculando los bits de paridad. Si el Bit de paridad obtenido es todo 0, el mensaje enviado es correcto. Si no es 0, esos bits de paridad me darán la posición donde se encuentra el bit erróneo. Pasaremos su valor a decimal y cambiaremos el valor del bit erróneo por el correcto
Verifica los siguientes bits NOTAR que
P1 1, 3, 5, 7, 9, 11… 1 Si; 1 No
P2 1, 3, 6, 10, 11, 14, 15… 2 Si; 2 No
P4 4, 5, 6, 7, 12, 13, 14, 15… 4 Si; 4 No
P8 8, 9, 10, 11, 12, 13, 14, 15… 8 Si; 8 No
P16 16… 16 Si; 16 No
· Ejercicio:
· Considerar… 0110101
· ¿Cuántos son los bits de paridad?
· ¿Dónde se colocan?
· ¿Cuál seria el mensaje final según los bits de Paridad?
(Calcular el valor Bits de paridad)
· Respuesta:
· 2^k > n + k
· N=7
· K=?
· K=4
· = 11 bits