Jak znaleźć wielomian dla zdziesiątkowanego LFSR?

Question

Wiem, że jeśli zdziesiątkujesz serię generowaną przez rejestr przesuwny z liniowym sprzężeniem zwrotnym, otrzymasz nową serię i nowy wielomian. Na przykład, jeśli pobierzesz co piątą część z serii wygenerowanej przez LFSR z wielomianem x + x + 1, otrzymasz serię wygenerowaną przez x + x + 1. Mogę znaleźć drugi wielomian (x + x + 1) przez brutalną siłę, co jest dobre dla wielomianów niskiego rzędu. Jednak w przypadku wielomianów wyższego rzędu czas wymagany do brutalnej siły jest nieuzasadniony.

Pytanie brzmi: czy możliwe jest analityczne odszukanie zdziesiątkowanego wielomianu?

Answer 1

Ostatnio przeczytać ten artykuł i myśl o tym, kiedy widząc swoje pytanie, mam nadzieję, że pomaga ..: OTH

Biorąc prymitywne wielomian nad GF (q), można uzyskać kolejną prymitywną wielomian przez dziesiątkuje sekwencję LFSR uzyskanej od początkowego wielomianu. Zostało to wykazane w poniższym kodzie.

K: = GF (7); C: = PrimitivePolominomial (K, 2); C; D^2 + 6 * d + 3 w celu wygenerowania sekwencji LFSR, należy najpierw pomnożyć wielomian przez odpowiedni stałej tak, że współczynnik wzdłużny staje 1.

C: = C * Współczynnik (C 0)^- 1; C; 5 * D^2 + 2 * D + 1 Możemy teraz wygenerować sekwencję LFSR o długości 72 - 1. Początkowy stan może być dowolny niż [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] Dekodujemy sekwencję przez wartość d mającą właściwość gcd (d, 48) = 1.

t: = dziesiątkowanie (t, 1, 5); t; [1, 5, 0, 6, 5, 6, 4, 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 Aby uzyskać odpowiedni wielomian pierwotny, mnożymy przez stałą, aby stała się moniką.

B: = B * Współczynnik (B, 2)^- 1; B; D^2 + 4 * D + 5 IsPrimitive (B); true