Perché $ x ^ {15} + x ^ {14} + 1 $ rileva tutti gli errori al massimo 32768 bit a parte?
-
29-09-2020 - |
Domanda
Domanda di riferimento dalla rete del computer del libro Fouzon. Trova lo stato del generatore seguente relativo a due errori isolati, a singolo bit. $$ x ^ {15} + x ^ {14} + 1 $$ Risposta Dato: Questo polinomio non può dividere alcun errore di tipo $ x ^ T + 1 $ se T è inferiore a 32.768.Questo significa che un codice con due errori isolati che sono uno accanto all'altro o fino a 32.768 bit A parte può essere rilevato da questo generatore. Qualcuno può aiutarmi perché è vero ...?O anche come dovrei avere un approccio in generale per analizzare tali domande ...? (Scusa se questo è molto sciocco, ma non riesco a prendere una comprensione di come funziona la ragione ...!)
Soluzione
Il tuo polinomio è primitivo , il che significa che l'ordine della $ x $ modulo il tuo polinomiale è esattamente $ 2 ^ {15} -1 $ .In particolare, $ x ^ a \ non \ equiv 1 $ modulo il tuo polinomio per tutte le $ 1 \ Leq A \ Leq 2 ^{15} -2 $ , il che significa che il tuo polinomio non divide $ x ^ a-1 $ per questo intervallo di $ A $ .
(questo significa anche che il polinomio dovrebbe dividere $ x ^ {2 ^ {15} -1} -1 $ , in contrasto con quale afferma la domanda.)