생성 다항식

생성 다항식(Generator polynomial)

• 입력 시퀀스로부터 유효 부호어를 생성시킬 수 있는 다항식 형태의 표현
  시퀀스: 어떤 규칙에 따라 / 또는 랜덤하게 순서화된 요소들의 열.

유효 부호어, 무효 부호어

• 전체 부호어 집합(Codeword Set)
  모든 가능한 부호어를 말하며, 길이가 $n$인 $q$진 배열은 $q^n$개의 가능한 부호어를 가진다.

• 유효 부호어 집합(Valid Codeword Set)
  모든 가능한 부호어 $q^n$개 중 유효 부호어는 제한적인 부분공간을 형성한다.
  

  • 원 메시지로부터 1:1 매핑될 수 있는 $q^k$개의 부호어만이 유효.
  • 나머지 무효 부호어는 오류검출용으로 사용된다.

선형 블록 부호화에 의한 채널 부호화

오류 검출 등 성능향상을 위해, 처음에는 코드 집합 크기를 더 확장시킨다.

• Information Sequence:
  전송하려는 원래의 정보 데이터. 전송과정에서 손상될 가능성이 있다.

• Encoder:
  정보 시퀀스에 오류 정정을 위한 Redundancy(중복성)을 추가하여 유효한 시퀀스를 생성함. 유효 시퀀스 외의 데이터는 무효 시퀀스가 된다.

• Noisy Channel:
  인코딩된 시퀀스는 노이즈 채널을 통해 전송된다. 이 과정에서 오류나 잡음이 발생하여 시퀀스가 손상될 가능성이 있다.

• Received Sequence:
  수신 측에서 잡음이 섞인 시퀀스를 받는다. 송신 측이 보냈던 인코딩된 원래 데이터와 다를 수 있다.

• Decoder:
  디코더는 수신된 시퀀스를 Codebook(유효 시퀀스 목록)을 참조하여 원래의 정보로 복원한다. 오류가 정정되어 최종 복호 판정 코드가 생성된다.

• Codebook:
  디코더가 사용하는 참조 테이블. 모든 유효한 시퀀스 및 그에 대응하는 정보 시퀀스 포함.

생성 다항식의 의미

• 유효 부호어를 생성시키는 도구의 개념.
• 입력 비트 시퀀스로부터 유효 부호어를 생성시킬 수 있는 다항식 형태의 표현

Ex) CRC-32 생성다항식

위의 다항식을 바이너리 코드로 나타내면

위의 코드에서 31번째 비트 ~ 0번째 비트까지 16진수로 표현하면 0x04C11DB7이고, 역순으로 0번째 비트 ~ 31번째 비트까지 16진수로 표현하면 0xEDB88320가 된다.

이는 CRC-32의 생성다항식으로, 만약 사용자가 "A"라는 문자를 전송하려고 한다면

1. 생성다항식의 차수만큼 데이터 뒤에 0을 붙여준다.

2. 생성다항식을 이용해 나눗셈(XOR연산)을 실시하여 나머지(CRC 코드)를 구한다.

3. CRC 코드를 원래 데이터 뒤에 붙여 유효부호어로 만든 후 전송한다.

4. 수신측은 데이터를 받아 동일한 생성다항식으로 나눗셈(XOR연산)을 한다.

   • 나머지가 0이라면 오류가 검출되지 않음.
   • 나머지가 0이 아니라면 오류가 검출됨.

---