Encontrar una secuencia de entrada dado un polinomio generador y CRC

1

Estoy trabajando en un circuito que ingresa una cadena binaria pseudoaleatoria de 31 bits en un bloque CRC-16 del CCITT que genera una salida CRC de 16 bits.

Sé que M (x) / G (x) = Q (x) + R (x) y el código transmitido será R (x) anexado a M (x). [Q (x) se descarta].

Cuando simulé el circuito, obtuve un CRC de 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0. Desde el archivo de ayuda del software (VisSim / Comm), sé que el polinomio generador es G (x) = 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1.

¿Cómo puedo determinar la secuencia de entrada de 31 bits que generó el resultado CRC?

Dado que M (x) / G (x) = Q (x) + R (x), podemos decir que M (x) = [Q (x) + R (x)] G (x). Pero no sabemos Q (x). Suponiendo que el CRC de 16 bits es igual a R (x) y que se da G (x), ¿cómo hago para encontrar M (x) sin saber Q (x)?

    
pregunta JJBladester

2 respuestas

1

Lo que esto le está diciendo es que hay un número infinito de mensajes que producirán el mismo CRC, uno para cada Q (x) posible. Todo lo que necesita hacer es elegir un valor particular de Q (x) y generar la M (x) correspondiente.

    
respondido por el Dave Tweed
1

Lo siguiente es simplista, pero adecuado. Su espacio de salida tiene 2 ^ 16 valores posibles. Su espacio de entrada tiene 2 ^ 31 valores posibles. En promedio, para cualquier valor de salida dado, hay 2 ^ 15 valores de entrada que se asignan a ese valor de salida en particular. No hay forma de saber a partir de un valor de salida dado cuál de esas 2 ^ 15 entradas posibles fue responsable, ya que la asignación de entrada a salida ha descartado la información que le permite revertir el proceso.

No puede reconstruir los datos originales de la salida de CRC, lo cual está bien, ese no es el propósito de los CRC. Sin embargo, puede utilizar la combinación de la salida de CRC y los datos originales para obtener un nivel de confianza bastante razonable (99.7% o aproximadamente para los errores de CRC16 y de bit único, iirc) que no se produjeron daños en los datos originales o CRC durante por ejemplo transmisión a través de un enlace con un BER > 0.

    
respondido por el markt

Lea otras preguntas en las etiquetas