Cyclic Code, Cyclic Coding   순회 부호, 순환 부호

(2016-11-29)
1. 순회 부호 (Cyclic Code)선형 블록 부호(선형 부호)의 일종
     - 선형성에 순회성이 추가적으로 부과됨 (즉, 선형 블록부호부분집합 임)

  ㅇ 주요 특징
     - 잘 정의된 수학적 구조, 부호화 용이성, 매우 효율적인 복호화 가능 등

  ※ 1957년 Prange가 순회 블록 부호수학적 기초를 세운 이후,
     - 선형 블록부호 대부분이 순회부호를 사용


2. 순회부호 조건 및 例

  ㅇ (선형성)  선형부호 일 것 즉, 두 부호어의 합이 그 부호에 속하는 다른 유효 부호어가 됨
  ㅇ (순환성)  임의의 한 부호어를 순환 이동(Cyclic Shift)시키어도 이 역시 유효 부호어일 것

  ※ 순회부호 例)  C = {0000,1010,0101,1111}
     - 선형성 검토
        . (중첩의 원리)  그 어떤 두 부호어의 합도 모두 C에 속하므로 C은 선형부호임
           .. 1010 ⊕ 1111 = 0101, 1010 ⊕ 0101 = 1111, 1111 ⊕ 1111 = 0000, ... 등
     - 순환성 검토
        . (0000)->(0000), (1010)->(0101)->(1010), (1111)->(1111)

  ㅇ 순회부호 실제 例 
     - 순회 해밍 부호, 순회 Golay 부호, BCH 부호, RS 부호, CRC, PN 코드
3. 순회부호 특징

  ㅇ 매우 간단하고 저렴한 전자회로로 쉽게 구현 가능
     - 코드 그 자체가 구조적이고 규칙성을 갖으므로, 설계구현 용이
        . 부호화신드롬 계산이 간단한 시프트 레지스터를 이용하여 쉽게 구현 가능
        . 즉, 직렬 구현도 가능

     - 주로, 오류제어 기능 보다는 구현이 간단하여 오류검출용으로 폭넓게 쓰임    
        . 다중 비트오류에 대한 오류정정도 가능

  ㅇ 효율적인 부호화/복호화 가능
     - 수학적으로 간결한 표현

     * 순회 부호는 유한체(Galois Field) 이론에 크게 의존 함
        . 순회부호에 대한 갈로아 유한체(Galois Finite Field) 행렬 표현에 의해
          아주 단순하고도 효율적인 부호화/복호화 알고리즘을 도모할 수 있음
        . 갈로아 유한체 이론은 효율적인 알고리즘 설계에 특히 유용함


4. 순회부호 표현 및 생성                                         ☞ 부호 다항식 표현 참조

  ㅇ 통상적인 선형 블록부호 표현이 부호벡터,생성행렬로 표현/생성 가능하나,
  ㅇ 순회부호는 주로, 부호 다항식(부호어) 및 생성 다항식(부호화)에 의해 표현/생성함


5. 순회부호 회로 구현선형 피드백 시프트레지스터(LFSR)에 의한 순회부호 회로구현 例)
     


[순회부호] 1. 순회 부호 2. CRC(순환중복검사) 3. CRC 생성 다항식 종류 4. BCH 부호 5. RS 부호 6. PN 코드 7. 최장 수열

 
        최근수정     요약목록(시험중)     참고문헌