Por que alta e de bits mais baixa do gerador deve ser 1?

Question

Aqui está um excerto do Andrew S.Tanenbaum, Redes de computadores, 5ª edição, Capítulo 3 (A camada de link de dados), Página 213:

Quando o polinˆ omio de código do método é empregado, o remetente e o receptor devem concordar com uma o polinômio gerador, $G(x)$, antecipadamente.Tanto a alta e a baixa-bits de ordem, o gerador deve ser de 1.Para calcular o CRC para algum quadro com $m$ bits correspondente ao o polinˆ omio $M(x)$, o quadro deve ser maior do que o polinômio gerador.A idéia é acrescentar um CRC para o fim da moldura de uma maneira tal que o polinômio representado pela soma de verificação de quadro é divisível por $G(x)$.Quando o receptor recebe a soma de verificação de quadro, ele tenta dividi-lo por $G(x)$.Se há um resto, tem havido um erro de transmissão.

A minha pergunta é como você determina o bit de ordem alta?E por que o bit de ordem superior e de ordem inferior bits, ambos tem de ser um?No meu entendimento, ela é usada para detectar ruptura de erro, mas é o meu entendimento é verdade?

Answer 1

O bit de ordem inferior, também conhecido como o bit menos significativo (LSB), é o "os" bits do número.Por exemplo, em 001101, o LSB é o bit mais à direita 001101.

O bit de ordem alta, também conhecido como o bit mais significativo (MSB), é o "superior" bit do número.No nosso exemplo 001101, é o bit mais à esquerda 001101.

Os dois termos são usados também em sentido figurado (em geral, o discurso):um bit de ordem alta é algo muito importante, e um bit de ordem inferior é algo que não é importante.

Agora a sua pergunta.Nós representamos uma mensagem $m_0,\ldots,também$ por um polinômio $M(x) = \sum_i m_i x^i$.Dado um polinˆ omio gerador $G(x)$, a ideia é estender a mensagem a uma nova mensagem de $M'(x)$ que satisfaz $G(x) \meados de M'(x)$.

Se o bit de ordem inferior $G(x)$ é zero, então, como uma extensão nem sempre é possível.De fato, o bit de ordem inferior $G(x)$ é zero iff $x \meados de G(x)$.Se este for o caso, em seguida, $G(x) \meados de M'(x)$ implica $x \meados de M'(x)$, i.é. $m_0 = 0$.Assim, se o menor bit de ordem $G(x)$ é zero, só seremos capazes de estender $M$ para $M'$ se $m_0 = 0$ (e mesmo isso não é necessariamente uma condição suficiente).

Se o bit de alta ordem $G(x)$ é zero, então o problema é outro.A probabilidade de que $G(x) \meados de M'(x)$ por um acaso $M'$ é $2^{-\deg G(x)}$ (supondo que $G$ é irredutível, isto é, não pode ser considerado nontrivially).Portanto CRC oferece-nos $\deg G(x)$ bits de proteção.Nós, portanto, quer $G(x)$ para ter o máximo grau possível.Isto corresponde a ter um bit de ordem superior a um.

Na prática, $G(x)$ é armazenado sem o bit de ordem alta:um 8-bit CRC polinômio realmente corresponde a 9 bits 1xxxxxxxx, mas não há necessidade de armazenar a 1.