왜 생성기의 상위 및 하위 비트가 1이어야 합니까?

Question

다음은 Andrew S.Tanenbaum, 컴퓨터 네트워크, 5판, 3장(데이터 링크 계층), 213페이지:

다항식 코드 방법을 사용하는 경우 송신자와 수신자는 다음 사항에 동의해야 합니다. 생성기 다항식, $G(x)$, 미리.생성기의 상위 및 하위 비트는 모두 1이어야 합니다.일부 프레임에 대한 CRC를 계산하려면 $m$ 다항식에 해당하는 비트 $M(x)$, 프레임은 생성기 다항식보다 길어야 합니다.아이디어는 체크섬 프레임으로 표현되는 다항식을 다음과 같이 나눌 수 있도록 프레임 끝에 CRC를 추가하는 것입니다. $G(x)$.수신자가 체크섬 프레임을 받으면 이를 다음과 같이 나누려고 시도합니다. $G(x)$.잔여량이 있으면 전송 오류가 발생한 것입니다.

제 질문은 상위 비트를 어떻게 결정합니까?그리고 왜 상위 비트와 하위 비트가 둘 다 하나여야 합니까?내 이해로는 버스트 오류를 ​​감지하는 데 사용되지만 내 이해가 사실입니까?

Answer 1

최하위 비트(LSB)라고도 하는 하위 비트는 숫자의 "1" 비트입니다.예를 들어 001101에서 LSB는 가장 오른쪽 비트 00110입니다.1.

최상위 비트(MSB)라고도 알려진 상위 비트는 숫자의 "최상위" 비트입니다.예제 001101에서는 가장 왼쪽 비트입니다. 001101.

두 용어는 (일반적인 담화에서) 비유적으로도 사용됩니다.높은 순서의 비트는 중요한 것이고, 낮은 순서의 비트는 중요하지 않은 것입니다.

이제 귀하의 질문에.우리는 메시지를 표현합니다 $m_0,\ldots,m_n$ 다항식으로 $M(x) = \sum_i m_i x^i$.생성자 다항식이 주어지면 $G(x)$, 아이디어는 메시지를 새로운 메시지로 확장하는 것입니다 $M'(x)$ 그것은 만족한다 $G(x) \mid M'(x)$.

낮은 차수 비트의 경우 $G(x)$ 0이면 그러한 확장이 항상 가능한 것은 아닙니다.실제로, 하위 비트의 $G(x)$ 0이면 $x \중간 G(x)$.그렇다면, $G(x) \mid M'(x)$ 암시한다 $x \중간 M'(x)$, 즉. $m_0 = 0$.따라서 하위 비트의 경우 $G(x)$ 0이면 확장만 가능합니다. $M$ 에게 $M'$ 만약에 $m_0 = 0$ (그리고 이것이 반드시 충분조건은 아닙니다).

상위 비트의 경우 $G(x)$ 0이면 문제가 달라집니다.확률은 $G(x) \mid M'(x)$ 무작위로 $M'$ ~이다 $2^{-\deg G(x)}$ (가정 $G$ 즉, 사소하지 않게 인수분해할 수 없습니다.)따라서 CRC는 우리에게 제안합니다 $\deg G(x)$ 약간의 보호.그러므로 우리는 원한다 $G(x)$ 최대한의 학위를 가지도록 합니다.이는 상위 비트 1을 갖는 것에 해당합니다.

실제로, $G(x)$ 상위 비트 없이 저장됩니다.8비트 CRC 다항식은 실제로 9비트 1xxxxxxxx에 해당하지만 1을 저장할 필요는 없습니다.