Generator Polynomial   생성 다항식

1. 생성 다항식 (Generator Polynomial)

  ㅇ 입력 시퀸스로부터 유효 부호어를 `생성시킬 수 있는 다항식` 형태의 표현
     - 입력 비트들로부터 출력 비트들의 생성을 표현하는 다항식

  ㅇ 조합논리의 표현을, 부울대수가 아닌 추상대수의 대수적 표현 방법에 의함


2. 생성 다항식의 의미

  ㅇ 생성행렬 처럼 유효 부호어를 생성시키는 도구의 개념
     - `생성 행렬 (벡터,행렬 표현)`과 `생성 다항식 (다항식 표현)`은 등가적 개념임

        

  ㅇ 즉, 생성 다항식의 의미 : (부호어 생성) = (다항식의 곱 표현) = (부호화)


3. 생성 다항식의 표현

  ㅇ 생성 다항식의 표현식
       
[# g(x) = g_0 + g_1x + \cdots + g_rx^r #]

  ㅇ 생성 다항식에 의한 부호어 생성
       
[# c(x) = m(x) g(x) \\
        \qquad = (m_0+m_1x+\cdots+m_{k-1}x^{k-1}) (g_0 + g_1x + \cdots + g_rx^r) \\
        \qquad = m_0g_0 + m_1g_1x + \cdots + m_{k-1}g_rx^{r+k-1} \\
        \qquad = c_0 + c_1x + \cdots + c_{n-1}x^{n-1} #]
`
     - c(x) : 부호어 다항식(code polynomial),    차수 deg[c(x)] ≤ n - 1
     - m(x) : 메세지 다항식(message polynomial), 차수 deg[m(x)] ≤ k - 1
     - g(x) : 생성 다항식(generator polynomial), 차수 deg[g(x)] = n - k
     - g(x)의 차수 : (n-1) = (r+k-1) => r = n-k
        . 즉, g(x)의 차수는 검사 비트 수 n-k 와 같아야 함

  ㅇ 생성 다항식의 조합논리 표현 例)
       


4. (n,k) 순환부호에서, 생성다항식 g(x)의 성질, 특징

  ㅇ (xn + 1)를 다항식 인수(Factor)로 갖음

  ㅇ 만일, 
     - 부호 다항식 c(x)가, 유효 부호어 이면,
     - 부호 다항식 c(x)가, 생성 다항식 g(x)으로 나누어 떨어지게 됨 (즉, 나머지 = 0)

  ㅇ 항상 유일(Unique) 하게됨

  ㅇ 생성 다항식은, 원시 다항식 임
     - (원시 다항식 : 약분 불가능한 기약 다항식)
     - 생성된 CRC의 길이를 정의하게 됨
        . 例) 만일, 16 비트 CRC가 필요하다면,
              생성 다항식은, 17 비트 길이가 되어야 함
              첫,끝 비트는 반드시 1 이어야 하며, 
              생성 다항식 그 자체는 원시 다항식이거나 원시 다항식에서 유도된 것이어야 함


5. 생성 다항식의 선택

  ㅇ 임의적이기 보다는, 몇가지 요인에 의해 결정됨

  ㅇ (추가편집중)