Repetition Code   반복 부호, 반복 코드

(2022-06-27)

Triple Repetition Code, Repetition Coding, 반복 코딩, Majority Decoding, 다수결 복호화


1. 반복 코드메세지 내 각 비트가, 여러번 반복되어 만들어지는, 매우 단순한 코드

  ㅇ 例) 3 비트 반복코드 (Triple Repetition Code) : 0 -> 000, 1 -> 111  


2. 반복 코드의 특징부호어가 동일 비트로 구성됨
     - 모두 `0` 또는 `1` 인 비트 열
        . C = {[0, 0, . . . , 0], [1, 1, . . . , 1]}

  ㅇ 부호어 길이가 항상 홀수가 됨
     - 원 메세지 길이가,  m  일때,
     - 부호어 길이는,  n (n = 2m + 1 : 항상 홀수) 이 됨

  ㅇ `블록 부호` 형태로써, 부호화율 1/n 임
     - 1개 메세지 비트가, n개의 동일 갯수의 비트를 갖도록, 부호화블록 부호 형태 임
     - 즉, (n,1) 블록코드 임
     - 따라서, 부호화율 R은, R = 1/n

  ㅇ 가장 단순한 `선형 블록부호` 임
     - 1개 메세지 비트가, n개 동일 비트 블록으로, 선형 부호화되는, 선형 블록 부호 임

     - 즉, 생성행렬의 곱에 의해, 부호어의 생성이 가능 함  :  c = m G
        . 생성행렬  :  G = [1 1 ... 1]
           .. 생성행렬 G의 행렬크기  :  (1 x n) 크기
        . 생성된 부호어  :  c = [m m ... m]

  ㅇ 해밍 최소거리  :  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 로 복호 판정



Copyrightⓒ written by 차재복 (Cha Jae Bok)
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"