1. 반복 코드
ㅇ 메세지 내 각 비트가, 여러번 반복되어 만들어지는, 매우 단순한 코드
ㅇ 例) 3 비트 반복코드 (Triple Repetition Code) : 0 -> 000, 1 -> 111
2. 반복 코드의 특징
ㅇ 부호어가, 동일 비트로 구성됨
- 모두 `0` 또는 `1` 인 비트 열
. C = {[0, 0, . . . , 0], [1, 1, . . . , 1]}
ㅇ `블록 부호` 형태로써, 가장 단순한 `선형 블록부호` 임
- 1개 메세지 비트가, n개 동일 비트 블록으로, 선형 부호화되는, 선형 블록 부호 임
ㅇ 부호화율이, r = 1/n 임
- 1개 메세지 비트가, n개의 동일 갯수의 비트를 갖도록, 부호화된 블록 부호 형태 임
- 즉, (n,1) 블록코드 임
- 따라서, 부호화율 R은, R = 1/n
ㅇ 부호어 길이가, 항상 홀수가 됨
- 원 메세지 길이가, m 일때,
- 부호어 길이는, n (n = 2m + 1 : 항상 홀수) 이 됨
ㅇ 부호어 생성의 수학적 표현이 다음과 같음
- 수학적으로, 생성행렬 또는 생성다항식의 곱에 의해, 부호어의 생성 표현이 가능 함
. 생성행렬 : {# G = [1\;1\;\cdots\;1] #} (행렬크기 : 1 x n)
. 생성된 부호어 : {# c = m G = [m\;m\;\cdots\;m] #}
. 생성다항식 : {#g(x) = \sum^{n-1}_{i=0} x^i = x^{n-1} + x^{n} + \cdots + x + 1 #}
. 생성된 부호어 : {# c(x) = m(x) g(x) = m + mx + \cdots + mx^{n-1} #}
ㅇ 해밍 최소거리 : dmin = n
- 즉, (n,1,n) 블록 부호 임
. (n, k, dmin) ☞ 블록 부호 명칭 참조
- 사실상, (n,1) 또는 (n,1,n) 해밍 부호와 동등 함
. (3,1,3) 경우, 가장 작은 반복 부호인 동시에 해밍 부호 임
ㅇ 오류검출능력, 오류정정능력
- 例) (3,1,3) 경우, dmin = 3 이므로,
. 오류검출능력 : td ≤ dmin - 1 = 3 - 1 = 2
. 오류정정능력 : tc ≥ (dmin - 1)/2 ≥ (3-1)/2 = 1
ㅇ 반복 부호는 완전 부호로 간주됨
- 복호 실패 (Decoding Error) 없이, 반드시 복호 가능한 부호
3. 반복 코드의 복호화
ㅇ (n,1) 반복 부호의 복호시, 비트 결정 방식의 종류
- 다수결 복호화 (Majority Decoding)
. 수신된 n 비트에서, 0의 개수가 1의 개수보다 많으면, -> 0 로 복호 판정
. 수신된 n 비트에서, 1의 개수가 0의 개수보다 많으면, -> 1 로 복호 판정
- 해밍중에 의한 복호화
. dH = wH ≤ (n-1)/2 이면, -> 0 로 복호 판정
. dH = wH ≥ (n-1)/2 이면, -> 1 로 복호 판정
4. 반복 코드의 비트오류확률, 심볼오류확률
ㅇ 비트오류확률
- 가정
. 이진 대칭 채널 (BSC)
.. 비트 오류 발생 확률 p 인 채널을 통해 전송한다면,
.. (pe = p12 = p21 = p)
. 다수결 복호
- 이때, 과반수 k = (n+1)/2 이상 오류 발생 시에, => 복호 오류 발생
. n 비트 블록에서, j개 비트 오류 발생 확률 ☞ 이항 분포 및 이항 정리 참고
. 길이 n 비트열을 비트 오류 발생 확률 p 인 BSC 채널을 통해 전송할 때,
. 수신된 n 비트열(부호어) 내에, 1개 이상(1 ≤ k ≤ n)의 비트 오류가 발생할 확률은,
[# P_E = \sum^n_{k=1} \begin{pmatrix} n \\ k \end{pmatrix} (1-p)^{n-k} p^k #]
[# P(j,n) #]
[# P_b = \sum_{k=\frac{n+1}{2}}^{n} \binom{n}{k} p^k (1-p)^{n-k} #]
. (편집중)