1. 순회 부호 (Cyclic Code)
ㅇ 선형 블록 부호 (선형 부호)의 일종
- 즉, 선형 블록 부호의 부분집합 임
. 선형성에 순회성 (순환성 : 무한 반복/되풀이)이 추가적으로 부과됨
ㅇ 주요 특징
- 잘 정의된 수학적 구조
- 부호화,복호화의 용이성 등
※ 1957년 Eugene 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)
* (0...0), (1...1) 처럼, 모두 `0`, 모두 `1`인 부호어는, 항상 포함됨
ㅇ 순회부호 실제 例
- 순회 해밍 부호, 순회 Golay 부호, BCH 부호, RS 부호, CRC, PN 코드 등
3. 순회부호의 특징
ㅇ 효율적인 부호화/복호화 가능
- 수학적으로 간결한 표현
* 특히, 순회 부호는 유한체(Galois Field) 이론에 크게 의존 함
. 순회부호에 대해, 갈로아 유한체(Galois Finite Field) 행렬 표현에 의해,
. 아주 단순하고도 효율적인 부호화/복호화 알고리즘을 도모할 수 있음
. 또한, 갈로아 유한체 이론은 효율적인 알고리즘 설계에 특히 유용함
ㅇ 따라서, 매우 간단하고 저렴한 전자회로로 쉽게 구현 가능
- 코드 그 자체가 구조적이고 규칙성을 갖으므로, 설계구현 용이
. 부호화 및 신드롬 계산이 간단한 시프트 레지스터를 이용하여 쉽게 구현 가능
.. 즉, 직렬 구현도 가능
ㅇ 주로, 오류제어 기능 위주 보다는, 구현이 간단하여 오류검출 용도로 더 폭넓게 쓰임
- 다중 비트오류에 대한 오류정정도 가능
4. 순회부호의 표현 및 생성 ☞ 부호 다항식 표현, 생성 다항식 참조
ㅇ `선형 블록부호`의 표현/생성은,
- 주로, 부호 벡터 (부호어 표현), 생성 행렬 (부호어 생성 : 부호화)에 의해 가능하나,
ㅇ `순회 부호`의 표현/생성은,
- 주로, 부호 다항식 (부호어 표현), 생성 다항식 (부호어 생성 : 부호화)에 의함
※ 부호 다항식 표현 例) q진 (n,k) 순회 부호는,
- (n-k) 차수의 다항식에 의해 다음과 같이 표현 가능
[# \mathbf{g}(X) = g_0 + g_1X + g_2X^2 + \cdots + g_{n-k-1}X^{n-k-1} + X^{n-k} #]
. 단, {#g_0 \neq 0#}, {#g_i \in GF(q)#} ({#GF(q)#} : q개 원소를 갖는 유한체)
. 한편, 2진(q=2)의 경우 : {#g_i#} = {0,1}, 3진(q=3)의 경우 : {#g_i#} = {0,1,2}
5. 순회부호의 구현
ㅇ 순회부호는 시프트 레지스터(LFSR)에 의해 쉽게 구현 가능함
ㅇ 선형 피드백 시프트레지스터(LFSR)에 의한 순회부호 회로구현 例)
1.
2.
3.
4.
5.
6.
7.
8.
9.