왜 $ x ^ {15} + x ^ {14} + 1 $ 대부분의 32768 비트에서 모든 오류를 탐지합니까?

Question

Foouzon Book 컴퓨터 네트워크에서 질문을 참조하십시오. 2 개의 격리 된 단일 비트 오류와 관련된 다음 생성기의 상태를 찾습니다. $$ x ^ {15} + x ^ {14} + 1 $$ 답변 주어진 : 이 다항식은 t가 32,768 미만이면 $ x ^ t + 1 $ 의 오류를 나눌 수 없습니다.이는 수단을 의미합니다 서로 옆에있는 두 개의 격리 된 오류가있는 코드 워드 또는 최대 32,768 비트 이 발전기에 의해 감지 될 수 있습니다. 어떤 사람이 왜 이것이 사실인지 도와주세요.또는 심지어 그런 질문을 분석하기 위해 일반적인 접근 방식을 어떻게 갖추어야합니까? (이것이 매우 어리 석다면 미안하지만 나는 그 이유가 어떻게 작동 하는지를 이해할 수 없다 ...!)

Answer 1

귀하의 다항식은 원시 입니다. 이는 $ x $ modulo 당신의 다항식은 정확히 $ 2 ^ {15} -1 $ 입니다.특히 $ x ^ a \ not \ equiv 1 $ modulo 모든 $ 1 \ leq a \ leq 2 ^{15} -2 $ 은 귀하의 다항식이 $ x ^ a-1 $ 을 나누지 않는다는 것을 의미합니다.수학 용기 "> $ a $ .

(이는 또한 귀하의 다항식이 $ x ^ {2 ^ {15} -1} -1 $ 을 분열해야한다는 것을 의미합니다.)