Generator Polynomial   생성 다항식

1. 생성 다항식 (Generator Polynomial)

  ㅇ 입력에 의해 출력이 결정되는 `조합 논리`의 표현을, 
     - `부울 대수`가 아닌 `추상 대수`의 대수적 표현 방법에 의함                ☞ 아래 2.항 참조

  ㅇ 입력 비트들로부터 출력 비트들의 생성을 다항식으로 표현함
     - 입력 시퀸스로부터 유효 부호어를 `생성시킬 수 있는 다항식` 형태의 표현
        . 주로, 순환부호 생성 표현에 사용됨


2. 생성 다항식의 표현 및 부호어 생성 방식

  ㅇ 생성 다항식의 표현식
       
 $$g(x) = g_0 + g_1x + \cdots + g_rx^r$$ 
     - $g_0,g_1,\cdots,g_r$ : 이진 또는 유한체의 원소들로 이루어진 계수
        . $g_0,g_r$ : 처음,끝 계수로써, 항상 그 값이 0 이 아닌 1 임
     - r : g(x)의 차수(degree), (n,k) 순환부호에서 (n - k)를 말함

  ㅇ 생성 다항식의 부호어 생성
       
 $$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 = r
        . g(x)의 차수 : (n-1) = (r+k-1)  =>  r = n - k
           .. 이는, 패리티 검사 비트 수 (n - k) 와 같음


3. 생성 다항식의 조합 논리(논리 회로)의 표현 例)

    


4. 생성 다항식에 의한 부호어 생성

  ㅇ 선형블록부호에 주로 쓰이는 생성행렬 처럼, 순회부호의 유효 부호어를 생성시키는 도구의 개념
     - 사실상, `생성 행렬 (벡터,행렬 표현)`과 `생성 다항식 (다항식 표현)`은 등가적 개념임

        

  ㅇ 例) (7,4) 순환부호의 부호어 생성 : $m(x) = [1101] = 1+x+x^3, \; g(x) = 1+x+x^3$
     - $c(x)=m(x)g(x)=(1+x+x^3)(1+x+x^3)=1+2x+x^2+2x^3+2x^4+x^6$
        . 2 mod 2 = 0 이므로, $c(x) = 1+x^2+x^6 = [1010001]$

  ㅇ 즉, 생성 다항식 이란?  :  (유효 부호어 생성) = (다항식 곱) = (부호화)

  ※ [참고]  선형 부호의 생성 및 에러검출  =>  (편리한 수학적 도구가 존재함)
     - [생성] 생성 행렬 (선형블록부호 생성에 유리), 생성 다항식 (순회부호 생성에 유리)
     - [오류검출] => 생성행렬에 대응시킨 패리티검사행렬


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

  ㅇ 생성 다항식은, 원시 다항식 이거나, 원시 다항식에서 유도된 것이어야 함
     - (원시 다항식 : 다항식이 인수가 없는 즉, 약분 불가능한 기약 다항식)
        . 例) $x^2+x+1=0,\quad x^3+x+1=0,x^3+x^2+1=0,$ 
              $x^5+x^2+1=0,x^5+x^3+1=0,x^5+x^3+x^2+x+1=0,$
              $x^5+x^4+x^2+x+1=0,\cdots$
        . 생성 다항식이 원시 다항식이면, 이는 항상 유일(Unique) 함
     - (원시 다항식에서 유도된 것)
        . 例) $g(x)=1+x+x^3,\;g'(x)=(1+x+x^3)(1+x^2)$는, 동일한 순회 부호를 생성
           .. g'(x)는 g(x)의 배수임. 즉, g(x)는 g'(x)의 약수(인수)임

  ㅇ 생성 다항식으로 생성된 CRC의 길이를 정의하게 됨                 ☞ CRC 생성 다항식 종류 참조
     - 例) 만일, 16 비트 CRC가 필요하다면, (CRC-16)                      
        . 생성 다항식은, 17 비트의 코드 길이가 되어야 함
        . 첫,끝 비트(계수값)는 반드시 1 이어야 함
     - 例) CRC-32 (코드 길이 비트수 : 32 + 1 = n - k + 1 bits)

  ㅇ 생성 다항식 g(x)은, (xn + 1)를 나누는, 약수(인수,factor)가 됨 : 
     - 例) $x^7+1=(1+x+x^3)(1+x+x^2+x^4)=g(x)h(x)$
        . (n - k = 3)인 생성 다항식 $g(x)=(1+x+x^3)$이면, (n,k) = (7,4) 순환부호 생성
        . (n - k = 4)인 생성 다항식 $g(x)=(1+x+x^2+x^4)$이면, (n,k) = (7,3) 순환부호 생성

  ㅇ 순환 부호의 유효 부호어는, 생성 다항식 g(x)로 나누어떨어지는 특성을 가짐 
     - 만일, 어떤 다항식이, 생성 다항식 g(x)으로 나누어 떨어지면 (즉, 나머지 = 0), 유효 부호어 임

  ㅇ 패리티 비트, 코드 길이와의 관계성                     ☞ 위 2.항 (차수), 블록 부호 용어 참조
     - 생성 다항식 g(x)의 최소 차수는, 패리티 비트의 개수와 관련 있음 (r = n - k)
     - 생성 다항식 g(x)의 길이는, 부호 길이와 관련 있음 (n)

  ㅇ 또한, 오류 검출 및 수정에도 활용
     - 생성 다항식 g(x)를 사용해, 유효 부호어 확인 및 오류 검출 가능
     - 신드롬 계산에 g(x)가 활용됨