¿Cómo se puede encontrar el polinomio para un LFSR diezmado?

Question

Sé que si se diezma la serie generada por un registro de desplazamiento de retroalimentación lineal, se obtiene una nueva serie y un nuevo polinomio. Por ejemplo, si muestras cada quinto elemento de la serie generada por un LFSR con polinomio x + x + 1, obtienes la serie generada por x + x + 1. Puedo encontrar el segundo polinomio (x + x + 1) por fuerza bruta, lo que está bien para polinomios de bajo orden. Sin embargo, para polinomios de orden superior, el tiempo requerido para la fuerza bruta no es razonable.

Entonces la pregunta es: ¿es posible encontrar el polinomio diezmado analíticamente?

Answer 1

Recientemente Lee este artículo y el pensamiento de él al ver su pregunta, creo que sirve ..: OTH

Dado un polinomio primitivo sobre GF (q), se puede obtener otro polinomio primitivo al diezmar una secuencia LFSR obtenida desde el polinomio inicial. Esto se demuestra en el código a continuación.

K: = GF (7); C: = Polinomio Primitivo (K, 2); C; D^2 + 6 * D + 3 el fin de generar una secuencia LFSR, debemos multiplicar primero este polinomio por una constante adecuada, de modo que el coeficiente de arrastre se convierte en 1.

C: = C * Coeficiente (C, 0)^- 1; C; 5 * D^2 + 2 * D + 1 Ahora podemos generar una secuencia LFSR de longitud 72 - 1. El estado inicial puede ser distinto de [0, 0].

t: = LFSRSequence (C, [K | 1,1], 48); t; [1, 1, 0, 2, 3, 5, 3, 4, 5, 5, 0, 3, 1, 4, 1, 6, 4, 4, 0, 1, 5, 6, 5, 2, 6, 6, 0, 5, 4, 2, 4, 3, 2, 2, 0, 4, 6, 3, 6, 1, 3, 3, 0, 6, 2, 1, 2, 5] Diezmamos la secuencia por un valor d que tiene la propiedad gcd (d, 48) = 1.

t: = Decimation (t, 1, 5); t; [1, 5, 0, 6, 5, 6, 4, 3, 1, 0, 4, 1, 4, 5, 5, 2, 3, 0, 5, 3, 5, 1, 1, 6, 2, 0, 1, 2, 1, 3, 3, 4, 6, 0, 3, 6, 3, 2, 2, 5, 4, 0, 2, 4, 2, 6, 6] B: = BerlekampMassey (t); B; 3 * D^2 + 5 * D + 1 Para obtener el polinomio primitivo correspondiente, multiplicamos por una constante para hacer que sea monico.

B: = B * Coeficiente (B, 2)^- 1; B; D^2 + 4 * D + 5 IsPrimitive (B); verdadero