¿Por qué o por qué no utilizar un polinomio irreducible para una verificación de redundancia cíclica?

Question

Entiendo la necesidad de usar un polinomio irreducible de una potencia principal campo finito cuando se hace la multiplicación con números en los campos. Para ciertas aplicaciones, tales como la Q de paridad de bytes utilizados en RAID6, un número distinto de cero debe tener un inverso multiplicativo que puede fallar si puede ser multiplicado por otro número distinto de cero en ese campo y el rendimiento cero. Sin embargo, no entiendo bien su importancia en su uso con comprobaciones de redundancia cíclica. Este parece ser un poco diferente escenario, porque en lugar de trabajar con números dentro del campo, un mensaje que representa un número que, en general, mucho, mucho más grande que el campo y la dividen hacia abajo para encajar en el campo. Después de eso, su muy cerca se ha hecho con los derechos del niño con tal vez un XOR para completar el trabajo.

Como ejemplo contrario, he descubierto que el polinomio utilizado para el CRC32 en CD-ROM se compone de dos pequeños polinomio: $(x^{16} + x^{15} + x^2 + 1) \cdot (x^{16} + x^2 + x + 1)$.

Tal vez la pregunta que tengo que preguntar es ¿por qué tendría que usar un polinomio irreductible en este caso en lugar de un conocido irreductible?

Answer 1

Digamos que usted quiere transmitir un polinomio $M(x)$, pero el destinatario recibe un poco diferente polinomio $M'(x)$. Podemos definir el error de "polinomio":

$$E(x)=M'(x)-M(x)$$

Llame a la CRC-polyomial $P$. A continuación, un error no será detectada iff $P$ divide $E$, o en otras palabras, si cada divisor de $P$ también es un divisor de a $E$. Por lo tanto, podemos garantizar que ciertos tipos de errores de quedar atrapados por el análisis de los divisores de a$P$$E$. Aquí están algunos ejemplos simples:

$E(x)=x^{n+m}+x^{n+m-1}+...+x^n=x^n(x^m+x^{m-1}+...+1)$, una ráfaga de error, es decir,. $m+1$ volteado bits en una fila. Este va a ser atrapado si $P$ tiene un valor distinto de cero término constante (por lo que no tiene divisores comunes con $x^n$) y es de grado mayor que $m$ (ya que entonces no se puede dividir un polinomio de grado $m$).

$E(1)=1$, es decir. un número impar de volteado de bits. Este va a ser atrapado si $x+1$ divide $P(x)$, desde entonces $P(1)=0$.

$E(x) = x^{n+m} + x^m=x^n(x^m+1)$, es decir. dos volteado bits de $m$ bits appart. Este va a ser atrapado si $P$ es un múltiplo de una primitiva polinomio de orden mayor que $m$. Así que una primitiva polinomio de grado $d$ va a la captura de dos de los errores si son menos de $2^d-1$ bits appart.

Así que, en resumen, el uso de un polinomio irreductible de hecho, puede ser deseable si se quiere garantizar ciertos tipos de errores de quedar atrapados.