Bit de paridade - Parity bit

7 bits de dados
(contagem de 1 bits) 8 bits incluindo paridade
até ímpar
0000000 0 0000000 0 0000000 1
1010001 3 1010001 1 1010001 0
1101001 4 1101001 0 1101001 1
1111111 7 1111111 1 1111111 0

Um bit de paridade , ou bit de verificação , é um bit adicionado a uma string de código binário . Os bits de paridade são uma forma simples de código de detecção de erros . Os bits de paridade são geralmente aplicados às menores unidades de um protocolo de comunicação, normalmente octetos de 8 bits (bytes), embora também possam ser aplicados separadamente a uma sequência de bits de mensagem inteira.

O bit de paridade garante que o número total de bits 1 na string seja par ou ímpar . Consequentemente, existem duas variantes de bits de paridade: bit de paridade par e bit de paridade ímpar . No caso de paridade par, para um determinado conjunto de bits, são contadas as ocorrências de bits cujo valor é 1. Se essa contagem for ímpar, o valor do bit de paridade é definido como 1, tornando a contagem total de ocorrências de 1s em todo o conjunto (incluindo o bit de paridade) um número par. Se a contagem de 1s em um determinado conjunto de bits já for par, o valor do bit de paridade é 0. No caso de paridade ímpar, a codificação é invertida. Para um determinado conjunto de bits, se a contagem de bits com valor 1 for par, o valor do bit de paridade é definido como 1, tornando a contagem total de 1s em todo o conjunto (incluindo o bit de paridade) um número ímpar. Se a contagem de bits com valor 1 for ímpar, a contagem já é ímpar, de modo que o valor do bit de paridade é 0. A paridade par é um caso especial de verificação de redundância cíclica (CRC), em que o CRC de 1 bit é gerado por o polinômio x +1.

Se um bit está presente em um ponto de outra forma dedicado a um bit de paridade, mas não é usado para paridade, pode ser referido como um bit de paridade de marca se o bit de paridade for sempre 1, ou um bit de paridade de espaço se o bit for sempre 0 Em tais casos onde o valor do bit é constante, ele pode ser chamado de stick de paridade, mesmo que sua função não tenha nada a ver com paridade. A função de tais bits varia com o projeto do sistema, mas exemplos de funções para tais bits incluem gerenciamento de temporização ou identificação de um pacote como sendo de dados ou endereço significativo. Se o valor real do bit for irrelevante para sua função, o bit equivale a um termo irrelevante .

Paridade

Em matemática, a paridade pode referir-se à igualdade ou estranheza de um inteiro, que, quando escrito em sua forma binária , pode ser determinada apenas examinando seu bit menos significativo .

Na tecnologia da informação, paridade refere-se à igualdade ou estranheza, dado qualquer conjunto de dígitos binários, do número daqueles bits com valor um. Como a paridade é determinada pelo estado de cada um dos bits, esta propriedade de paridade - sendo dependente de todos os bits e mudando seu valor de paridade par para ímpar se algum bit mudar - permite seu uso em esquemas de detecção e correção de erros .

Nas telecomunicações, a paridade referida por alguns protocolos é para detecção de erros . O meio de transmissão é predefinido, em ambos os pontos finais, para concordar com a paridade ímpar ou par. Para cada string de bits prontos para transmitir (pacote de dados), o emissor calcula seu bit de paridade, zero ou um, para torná-lo compatível com a paridade acordada, par ou ímpar. O receptor desse pacote primeiro verifica se a paridade do pacote como um todo está de acordo com o acordo predefinido e, em seguida, se houver um erro de paridade nesse pacote, solicita uma retransmissão desse pacote.

Na ciência da computação a faixa de paridade ou disco de paridade em um array RAID fornece de erros de correção . Os bits de paridade são gravados na taxa de um bit de paridade por n bits, onde n é o número de discos na matriz. Quando ocorre um erro de leitura, cada bit na região de erro é recalculado de seu conjunto de n bits. Desta forma, usar um bit de paridade cria "redundância" para uma região do tamanho de um bit ao tamanho de um disco. Consulte § Matriz redundante de discos independentes abaixo.

Na eletrônica, a transcodificação de dados com paridade pode ser muito eficiente, pois as portas XOR geram o que é equivalente a um bit de verificação que cria uma paridade uniforme, e o projeto lógico XOR escala facilmente para qualquer número de entradas. As estruturas XOR e AND compreendem a maior parte dos circuitos integrados.

Detecção de erro

Se um número ímpar de bits (incluindo o bit de paridade) for transmitido incorretamente, o bit de paridade ficará incorreto, indicando que ocorreu um erro de paridade na transmissão. O bit de paridade só é adequado para detectar erros; ele não pode corrigir nenhum erro, pois não há como determinar qual bit em particular está corrompido. Os dados devem ser totalmente descartados e retransmitidos do zero . Em um meio de transmissão barulhento, uma transmissão bem-sucedida pode, portanto, levar muito tempo ou até mesmo nunca ocorrer. No entanto, a paridade tem a vantagem de usar apenas um único bit e requer apenas um número de portas XOR para gerar. Consulte o código de Hamming para obter um exemplo de código de correção de erros.

A verificação de bit de paridade é usada ocasionalmente para transmitir caracteres ASCII , que têm 7 bits, deixando o 8º bit como um bit de paridade.

Por exemplo, o bit de paridade pode ser calculado da seguinte maneira. Suponha que Alice e Bob estão se comunicando e Alice deseja enviar a Bob a mensagem simples de 4 bits 1001.

Tipo de paridade de bits Cenário de transmissão de sucesso
Paridade par

Alice quer transmitir: 1001

Alice calcula o valor do bit de paridade: 1 + 0 + 0 + 1 (mod 2) = 0

Alice adiciona bit de paridade e envia: 10010

Bob recebe: 10010

Bob calcula a paridade: 1 + 0 + 0 + 1 + 0 (mod 2) = 0

Bob relata a transmissão correta após observar o resultado uniforme esperado.

Paridade ímpar

Alice quer transmitir: 1001

Alice calcula o valor do bit de paridade: 1 + 0 + 0 + 1 (mod 2) = 0

Alice adiciona bit de paridade e envia: 1001 1

Bob recebe: 10011

Bob calcula a paridade geral: 1 + 0 + 0 + 1 + 1 (mod 2) = 1

Bob relata a transmissão correta após observar o resultado ímpar esperado.

Este mecanismo permite a detecção de erros de bit único, porque se um bit for invertido devido ao ruído da linha, haverá um número incorreto de uns nos dados recebidos. Nos dois exemplos acima, o valor de paridade calculado de Bob corresponde ao bit de paridade em seu valor recebido, indicando que não há erros de bit único. Considere o seguinte exemplo com um erro de transmissão no segundo bit usando XOR:

Tipo de erro de paridade de bit Cenário de falha de transmissão
Paridade par

Erro no segundo bit

Alice quer transmitir: 1001

Alice calcula o valor do bit de paridade: 1 ^ 0 ^ 0 ^ 1 = 0

Alice adiciona bit de paridade e envia: 10010

... ERRO DE TRANSMISSÃO ...

Bob recebe: 1 1 010

Bob calcula a paridade geral: 1 ^ 1 ^ 0 ^ 1 ^ 0 = 1

Bob relata transmissão incorreta após observar resultados ímpares inesperados.

Paridade par

Erro no bit de paridade

Alice quer transmitir: 1001

Alice calcula o valor de paridade par: 1 ^ 0 ^ 0 ^ 1 = 0

Alice envia: 10010

... ERRO DE TRANSMISSÃO ...

Bob recebe: 1001 1

Bob calcula a paridade geral: 1 ^ 0 ^ 0 ^ 1 ^ 1 = 1

Bob relata transmissão incorreta após observar resultados ímpares inesperados.

Existe uma limitação para os esquemas de paridade. Um bit de paridade só tem garantia de detectar um número ímpar de erros de bit. Se um número par de bits tiver erros, o bit de paridade registra o número correto de bits, mesmo que os dados estejam corrompidos. (Consulte também detecção e correção de erros .) Considere o mesmo exemplo de antes com um número par de bits corrompidos:

Tipo de erro de paridade de bit Cenário de falha de transmissão
Paridade par

Dois bits corrompidos

Alice quer transmitir: 1001

Alice calcula o valor de paridade par: 1 ^ 0 ^ 0 ^ 1 = 0

Alice envia: 10010

... ERRO DE TRANSMISSÃO ...

Bob recebe: 1 1 01 1

Bob calcula a paridade geral: 1 ^ 1 ^ 0 ^ 1 ^ 1 = 0

Bob relata transmissão correta, embora na verdade incorreta.

Bob observa paridade par, conforme esperado, falhando assim em detectar os erros de dois bits.

Uso

Devido à sua simplicidade, a paridade é usada em muitos aplicativos de hardware onde uma operação pode ser repetida em caso de dificuldade ou onde simplesmente detectar o erro é útil. Por exemplo, os barramentos SCSI e PCI usam paridade para detectar erros de transmissão e muitos caches de instrução de microprocessador incluem proteção de paridade. Como os dados do I-cache são apenas uma cópia da memória principal , eles podem ser desconsiderados e buscados novamente se estiverem corrompidos.

Na transmissão de dados seriais , um formato comum é de 7 bits de dados, um bit de paridade par e um ou dois bits de parada . Este formato acomoda todos os caracteres ASCII de 7 bits em um byte de 8 bits. Outros formatos são possíveis; 8 bits de dados mais um bit de paridade podem transmitir todos os valores de bytes de 8 bits.

Em contextos de comunicação serial, a paridade é geralmente gerada e verificada pelo hardware de interface (por exemplo, um UART ) e, na recepção, o resultado disponibilizado para um processador como a CPU (e também, por exemplo, o sistema operacional ) por meio de um bit de status em um registro de hardware no hardware de interface . A recuperação do erro geralmente é feita retransmitindo os dados, cujos detalhes são geralmente tratados por software (por exemplo, as rotinas de E / S do sistema operacional).

Quando o número total de bits transmitidos, incluindo o bit de paridade, é par, a paridade ímpar tem a vantagem de que os padrões todos zeros e todos uns são detectados como erros. Se o número total de bits for ímpar, apenas um dos padrões é detectado como um erro e a escolha pode ser feita com base em qual é o erro mais comum.

Matriz RAID

Os dados de paridade são usados ​​por matrizes RAID ( Redundant Array of Independent / Inexpensive Disks ) para obter redundância . Se uma unidade na matriz falhar, os dados restantes nas outras unidades podem ser combinados com os dados de paridade (usando a função Booleana XOR ) para reconstruir os dados ausentes.

Por exemplo, suponha que duas unidades em uma matriz RAID 5 de três unidades contivessem os seguintes dados:

Unidade 1: 01101101
Unidade 2: 11010100

Para calcular os dados de paridade para as duas unidades, um XOR é executado em seus dados:

01101101
  XOR     11010100
10111001

Os dados de paridade resultantes, 10111001 , são então armazenados na Unidade 3.

Se qualquer uma das três unidades falhar, o conteúdo da unidade com falha pode ser reconstruído em uma unidade de substituição, submetendo os dados das unidades restantes à mesma operação XOR. Se a unidade 2 falhasse, seus dados poderiam ser reconstruídos usando os resultados XOR do conteúdo das duas unidades restantes, unidade 1 e unidade 3:

Unidade 1: 01101101
Unidade 3: 10111001

do seguinte modo:

10111001
  XOR     01101101
11010100

O resultado desse cálculo XOR produz o conteúdo do Drive 2. 11010100 é então armazenado na unidade 2, reparando totalmente a matriz.

A lógica XOR também é equivalente à paridade par (porque a XOR b XOR c XOR ... pode ser tratado como XOR ( a , b , c , ...) que é um operador n-árico que é verdadeiro se e somente se um número ímpar de argumentos é verdadeiro). Portanto, o mesmo conceito XOR acima se aplica de forma semelhante a matrizes RAID maiores com paridade, usando qualquer número de discos. No caso de uma matriz RAID 3 de 12 unidades, 11 unidades participam do cálculo XOR mostrado acima e geram um valor que é então armazenado na unidade de paridade dedicada.

Extensões e variações no mecanismo de bit de paridade "dupla", "dupla" ou "diagonal" de paridade são usadas em RAID-DP .

História

Uma trilha de paridade estava presente no primeiro armazenamento de dados em fita magnética em 1951. A paridade nesta forma, aplicada em vários sinais paralelos, é conhecida como verificação de redundância transversal . Isso pode ser combinado com a paridade calculada em vários bits enviados em um único sinal, uma verificação de redundância longitudinal . Em um barramento paralelo, há um bit de verificação de redundância longitudinal por sinal paralelo.

A paridade também foi usada em pelo menos alguns sistemas de entrada de dados em fita de papel ( fita perfurada ) (que precederam os sistemas de fita magnética). Nos sistemas vendidos pela empresa britânica ICL (anteriormente ICT), a fita de papel de 1 polegada de largura (25 mm) tinha 8 posições de orifício, sendo a 8ª para paridade. 7 posições foram usadas para os dados, por exemplo, ASCII de 7 bits. A 8ª posição tinha um furo feito dependendo do número de furos de dados feitos.

Veja também

Referências

links externos