Warum macht $ x ^ {15} + x ^ {14} + 1 $ alle Fehler höchstens 32768 Bits auseinander?

Question

Referenzfrage von Forouzon-Buch-Computernetzwerk. Finden Sie den Status des folgenden Generators in Verbindung mit zwei isolierten Einzelbitfehlern. $$ x ^ {15} + x ^ {14} + 1 $$ Antwort angegeben: Dieses Polynom kann keinen Fehler des Typs $ × ^ T + 1 $ teilen, wenn t weniger als 32.768 beträgt.Das heisst dass ein Codewort mit zwei isolierten Fehlern, die nebeneinander oder bis zu 32.768 Bits sind Apart kann von diesem Generator erkannt werden. Kann mir jemand helfen, warum ist das wahr ...?Oder sogar, wie sollte ich ein allgemeiner Ansatz haben, um solche Fragen zu analysieren ...? (Sorry, wenn das sehr dumm ist, aber ich kann nicht verstehen, wie der Grund funktioniert ...!)

Answer 1

Ihr Polynom ist primitiv , was bedeutet, dass die Reihenfolge der $ x $ modulo Ihr Polynom ist genau $ 2 ^ {15} -1 $ .Insbesondere $ X ^ A \ NOT \ EQUIV 1 $ modulo Ihr Polynom für alle $ 1 \ leq a \ leq 2 ^{15} -2 $ , was bedeutet, dass Ihr Polynom nicht teilt $ x ^ A-1 $ für diesen Bereich von $ A $ .

(Dies bedeutet auch, dass Ihr Polynom, dass Ihr Polynom $ x ^ {2 ^ {~ 15} -1} -1 $ dividiert wird, im Gegensatz zu dem, was die Frage behauptet.)