Bit de paridad

Un bit de paridad, o bit de verificación, se agrega a una cadena de código binario. Los bits de paridad son una forma simple de código de detección de errores. Los bits de paridad generalmente se aplican a las unidades más pequeñas de un protocolo de comunicación, generalmente octetos (bytes) de 8 bits, aunque también se pueden aplicar por separado a una cadena de bits de mensaje completa.

El bit de paridad garantiza que el número total de bits de 1 en la cadena sea par o impar. En consecuencia, existen dos variantes de bits de paridad: bit de paridad par y bit de paridad impar. En el caso de paridad par, para un conjunto dado de bits, se cuentan los bits cuyo valor es 1. Si ese recuento es impar, el valor del bit de paridad se establece en 1, lo que hace que el recuento total de ocurrencias de 1 en todo el conjunto (incluido el bit de paridad) sea un número par. Si la cuenta de 1 en un conjunto dado de bits ya es par, el valor del bit de paridad es 0. En el caso de paridad impar, la codificación se invierte. Para un conjunto dado de bits, si el recuento de bits con un valor de 1 es par, el valor del bit de paridad se establece en 1, lo que hace que el recuento total de 1 en todo el conjunto (incluido el bit de paridad) sea un número impar. Si el conteo de bits con un valor de 1 es impar, el conteo ya es impar, por lo que el valor del bit de paridad es 0. La paridad par es un caso especial de una verificación de redundancia cíclica (CRC), donde el bit de 1 CRC es generado por el polinomio x+1.

Paridad

En matemáticas, la paridad puede referirse a la paridad o imparidad de un número entero que, cuando se escribe en su forma binaria, puede determinarse simplemente examinando su bit menos significativo.

En tecnología de la información, la paridad se refiere a la paridad o imparidad, dado cualquier conjunto de dígitos binarios, del número de esos bits con valor uno. Debido a que la paridad está determinada por el estado de cada uno de los bits, esta propiedad de la paridad, que depende de todos los bits y cambia su valor de paridad par a impar si cambia un bit, permite su uso en esquemas de detección y corrección de errores..

En telecomunicaciones, la paridad a la que se refieren algunos protocolos es para la detección de errores. El medio de transmisión está predeterminado, en ambos puntos finales, para acordar una paridad impar o una paridad par. Para cada cadena de bits lista para transmitir (paquete de datos), el emisor calcula su bit de paridad, cero o uno, para que se ajuste a la paridad acordada, par o impar. El receptor de ese paquete primero verifica que la paridad del paquete como un todo esté de acuerdo con el acuerdo preestablecido, luego, si hubo un error de paridad en ese paquete, solicita una retransmisión de ese paquete.

En informática, la banda de paridad o el disco de paridad en un RAID proporciona corrección de errores. Los bits de paridad se escriben a razón de un bit de paridad por n bits, donde n es la cantidad de discos en la matriz. Cuando se produce un error de lectura, cada bit de la región de error se vuelve a calcular a partir de su conjunto de n bits. De esta forma, usar un bit de paridad crea "redundancia" para una región del tamaño de un bit al tamaño de un disco. Consulte § Arreglo redundante de discos independientes a continuación.

En electrónica, la transcodificación de datos con paridad puede ser muy eficiente, ya que las puertas XOR emiten lo que es equivalente a un bit de verificación que crea una paridad uniforme, y el diseño lógico XOR se adapta fácilmente a cualquier número de entradas. Las estructuras XOR y AND comprenden la mayor parte de la mayoría de los circuitos integrados.

Detección de errores

Si se transmite incorrectamente un número impar de bits (incluido el bit de paridad), el bit de paridad será incorrecto, lo que indica que se produjo un error de paridad en la transmisión. El bit de paridad solo es adecuado para detectar errores; no puede corregir ningún error, ya que no hay forma de determinar qué bit en particular está dañado. Los datos deben descartarse por completo y retransmitirse desde cero. Por lo tanto, en un medio de transmisión ruidoso, la transmisión exitosa puede llevar mucho tiempo o incluso nunca ocurrir. Sin embargo, la paridad tiene la ventaja de que usa solo un bit y requiere solo una cantidad de puertas XOR para generar. Consulte el código de Hamming para ver un ejemplo de un código de corrección de errores.

La comprobación de bits de paridad se usa ocasionalmente para transmitir caracteres ASCII, que tienen 7 bits, dejando el octavo bit como bit de paridad.

Por ejemplo, el bit de paridad se puede calcular de la siguiente manera. Suponga que Alice y Bob se están comunicando y Alice quiere enviar a Bob el mensaje simple 1001 de 4 bits.

Este mecanismo permite la detección de errores de bit único, porque si un bit se invierte debido al ruido de línea, habrá un número incorrecto de unos en los datos recibidos. En los dos ejemplos anteriores, el valor de paridad calculado por Bob coincide con el bit de paridad en su valor recibido, lo que indica que no hay errores de un solo bit. Considere el siguiente ejemplo con un error de transmisión en el segundo bit usando XOR:

Existe una limitación a los esquemas de paridad. Solo se garantiza que un bit de paridad detecte un número impar de errores de bit. Si un número par de bits tiene errores, el bit de paridad registra el número correcto de unos, aunque los datos estén corruptos. (Consulte también Detección y corrección de errores). Considere el mismo ejemplo que antes con un número par de bits dañados:

Bob observa incluso la paridad, como se esperaba, por lo que no detecta los errores de dos bits.

Uso

Debido a su simplicidad, la paridad se utiliza en muchas aplicaciones de hardware en las que se puede repetir una operación en caso de dificultad o en las que es útil simplemente detectar el error. Por ejemplo, los buses SCSI y PCI utilizan la paridad para detectar errores de transmisión y muchas memorias caché de instrucciones de microprocesadores incluyen protección de paridad. Debido a que los datos de I-cache son solo una copia de la memoria principal, se pueden ignorar y recuperar si se descubre que están corruptos.

En la transmisión de datos en serie, un formato común es de 7 bits de datos, un bit de paridad par y uno o dos bits de parada. Este formato acomoda todos los caracteres ASCII de 7 bits en un byte de 8 bits. Son posibles otros formatos; 8 bits de datos más un bit de paridad pueden transmitir todos los valores de bytes de 8 bits.

En contextos de comunicación en serie, la paridad generalmente se genera y verifica mediante hardware de interfaz (por ejemplo, un UART) y, al recibirlo, el resultado se pone a disposición de un procesador como la CPU (y también, por ejemplo, el sistema operativo).) a través de un bit de estado en un registro de hardware en el hardware de la interfaz. La recuperación del error generalmente se realiza retransmitiendo los datos, cuyos detalles generalmente los maneja el software (por ejemplo, las rutinas de E/S del sistema operativo).

Cuando el número total de bits transmitidos, incluido el bit de paridad, es par, la paridad impar tiene la ventaja de que los patrones de todos ceros y todos unos se detectan como errores. Si el número total de bits es impar, solo uno de los patrones se detecta como un error y la elección se puede realizar en función de cuál se espera que sea el error más común.

Matriz RAID

Los arreglos RAID (arreglo redundante de discos independientes/económicos) utilizan los datos de paridad para lograr la redundancia. Si falla una unidad del arreglo, los datos restantes en las otras unidades se pueden combinar con los datos de paridad (usando la función booleana XOR) para reconstruir los datos que faltan.

Por ejemplo, suponga que dos unidades en una matriz RAID 5 de tres unidades contienen los siguientes datos:

Para calcular los datos de paridad de las dos unidades, se realiza un XOR en sus datos:

Los datos de paridad resultantes, 10111001, se almacenan en la unidad 3.

Si alguna de las tres unidades falla, el contenido de la unidad fallida se puede reconstruir en una unidad de reemplazo sometiendo los datos de las unidades restantes a la misma operación XOR. Si la unidad 2 fallara, sus datos podrían reconstruirse utilizando los resultados XOR del contenido de las dos unidades restantes, la unidad 1 y la unidad 3:

como sigue:

El resultado de ese cálculo XOR produce el contenido de Drive 2. 11010100 luego se almacena en la unidad 2, reparando completamente la matriz.

La lógica XOR también es equivalente a la paridad par (porque a XOR b XOR c XOR... puede tratarse como XOR(a,b,c,...) que es un operador n-ario que es verdadero si y solo si un número impar de argumentos son verdadero). Entonces, el mismo concepto XOR anterior se aplica de manera similar a arreglos RAID más grandes con paridad, usando cualquier cantidad de discos. En el caso de una matriz RAID 3 de 12 unidades, 11 unidades participan en el cálculo XOR que se muestra arriba y generan un valor que luego se almacena en la unidad de paridad dedicada.

Extensiones y variaciones del mecanismo de bit de paridad "doble," "doble," o "diagonal" paridad, se utilizan en RAID-DP.

Historia

Una pista de paridad estaba presente en el primer almacenamiento de datos de cinta magnética en 1951. La paridad en esta forma, aplicada a través de múltiples señales paralelas, se conoce como verificación de redundancia transversal. Esto se puede combinar con la paridad calculada sobre múltiples bits enviados en una sola señal, una verificación de redundancia longitudinal. En un bus paralelo, hay un bit de verificación de redundancia longitudinal por señal paralela.

La paridad también se utilizó en al menos algunos sistemas de entrada de datos de cinta de papel (cinta perforada) (que precedieron a los sistemas de cinta magnética). En los sistemas vendidos por la empresa británica ICL (anteriormente ICT), la cinta de papel de 1 pulgada de ancho (25 mm) tenía 8 posiciones de orificios a lo largo, siendo el octavo para la paridad. Se utilizaron 7 posiciones para los datos, por ejemplo, ASCII de 7 bits. La octava posición tenía un agujero perforado dependiendo de la cantidad de agujeros de datos perforados.