블록 부호 용어, 블록 코드 용어

1. 블록 부호 및 선형 부호의 주요 용어들

  ㅇ 블록 부호  :  고정 길이의 블록 단위로 부호화를 수행하는 부호
  ㅇ 선형 부호  :  블록부호 중 선형성을 갖춘 부호
  ㅇ 순회 부호  :  블록부호 중 선형성,순회성을 모두 갖춘 부호
  ※ (블록 부호 > 선형 부호 > 순회 부호)
  ※ (블록 부호 그 자체로는 유익한 구조가 없으나, 선형 블록 부호에는 좋은 구조가 존재함)

  ㅇ 메세지어  :  부호화 이전 원래의 정보가 담겨있는 비트들의 시퀸스
  ㅇ 부호어  :  부호화에 의해 생성된 비트들의 시퀸스 
     - (수신측에서 독립적으로 복호화 가능한 단위)

  ㅇ 부호 크기(규모)  :  가능한 유효부호어 수 (2k)
  ㅇ 최소 거리 : 임의의 두 부호어들 간의 해밍거리 중에서 가장 작은 거리 (dmin)
  ※ (부호 크기와 최소거리 간에는 상충적) : (최소 거리 ↑, 부호 크기 ↓)  ☞ 아래 4.항 참조

  ㅇ 블록 길이 (부호 길이) :  블록 내 포함된 비트 수 (n)
  ㅇ 차원  :  메세지 비트 길이 (k)

  ㅇ 패리티 비트 : 패리티 검사를 위해 추가되는 비트들 
     - (메세지 비트들의 선형결합으로 만들어짐)
  ㅇ 부호화율  :  부호화시 실제 정보 비트가 어느 정도 포함될 수 있는지를 나타냄 (k/n)

  ㅇ 생성 행렬  :  행렬 곱셈에 의해 선형 블록부호를 생성시키는 수학적 도구 (G)
  ㅇ 생성 다항식  :  생성 행렬 처럼 유효 부호어를 생성시키는 부호 다항식 형태의 수학적 도구 (g(x))
  ㅇ 부호 다항식  :  부호어 표현 수단 중 하나 (특히, 순회부호의 부호어 표현에 유용)
  ㅇ 체계적 블록 부호  :  부호화에 의해 비트열이 변형되지 않고 동일 형태로 그대로 전송되는 부호

  ㅇ 패리티 검사 행렬  :  주어진 부호어가 유효 부호어인지 여부를 쉽게 검출할 수 있는 행렬 (H)
  ㅇ 신드롬  :  오류 검출에 사용 가능한 유일한 오류 패턴 (S)
  ㅇ 표준 배열  :  모든 가능한 수신 벡터들을 2n개의 n 튜플로 배열화시킨 표현 형식


2. (n,k) 체계적 블록 부호에서, 요소별 명칭 例)

     

  ㅇ 메세지어 (Message Word)
     - 메세지어 길이 (Length)  : k   (Dimension,차원)
        . 例) k 차원 벡터 (k-tuple Vector) : {# C = (c_0,c_1,\cdots,c_{k-1}) #}
     - 메세지어 갯수 (Size)    : 2k

  ㅇ 패리티 비트 (Parity Bit)
     - 패리티 비트 길이  : n-k (Redundant Length,리던던시)

  ㅇ 부호어 (Code Word)
     - 표현 가능 코드 알파벳 수 (Alphabet)  : 2 = q   (2진 Code Alphabet)
     - 부호어 길이 (Length)                 : n   (Blocklength,블록 길이)
     - 총 부호어 갯수 (Cardinality)         : 2n 
     - 유효 부호어 갯수 (Size)              : 2k = M
    
  ㅇ 블록 부호 부호화기 (Block Code Encoder)
     - 역할 : 매핑/변환/부호화
        . 부호길이 k 의 메세지어(2k개의 가능한 메세지어)를, 
        . 에러검출/에러정정이 가능한,
        . 좀더 긴 부호길이 n 의 부호어(2n개의 가능한 부호어)로 변환

  ㅇ 부호율 (Code Rate)
     -  R = k / n    (0 < R < 1)
        . k : 메세지어 길이 (블록부호의 차원)
        . n : 부호어 길이


3. 블록부호 (특히,선형블록부호)의 표기 및 명칭 例)

  ㅇ `2진 (5,4) 블록 부호` (2-ary 22 5-tuples)
     - 심볼 종류 : 2진 알파벳 (2-ary) {0,1}
     - 부호 길이 또는 블록 길이 (n, n-tuple) : 5  (5-tuples)
     - 부호 크기 또는 부호 차원 (M) : 4 = 22

  ㅇ `2진 (5,4,3) 블록 부호`  : (n, k, dmin)
     - 여기서,
        . n : 블록 길이 (블록부호화된 비트 수) = 5
        . k : 차원 (원래 정보 비트 수) = 4
        . dmin : 최소 거리 = 3
        . R = k/n : 부호화율 = 4/5
     - 최소 3개 이상 비트 차이(최소 거리, dmin)가 남
        . 최소해밍거리 : dmin = 3 비트
        . 오류검출능력 : td ≤ dmin - 1 = 3 - 1 = 2 비트
        . 오류정정능력 : tc ≤ (dmin - 1)/2 ≥ (3-1)/2 = 1 비트
        . 따라서,
           .. 오류 비트 2개를 검출 가능 (오류검출능력)
           .. 오류 비트 1개를 정정 가능 (오류정정능력)

  ※ 例) C = {0000, 1010, 0101, 1111}
     - n = 4, k = 2 (4개 부호어 있으므로, 2k = 4), 부호화율 = k/n = 1/2, dmin = 2
     - 선형부호 임 : 2진 (4,2,2) 선형블록부호 
        . (전 영 특성) 
           .. 모두 영(`0`)인 부호어도 유효 부호어가 됨 : (0000)
        . (중첩의 원리)
           .. 1010 ⊕ 1111 = 0101, 1010 ⊕ 0101 = 1111, 1111 ⊕ 1111 = 0000, ... 등
           .. 그 어떤 두 부호어의 합도 모두 C에 속하므로 C은 선형부호임
        . (최소 해밍 거리 = 최소 해밍 무게)
           .. d(0000,1010)=2, d(0000,0101)=2, d(0000,1111)=4, d(1010,0101)=4,
              d(1010,0101)=4, d(1010,1111)=2, d(0101,1111)=2 => dmin=2
           .. w(1010)=2, w(0101)=2, w(1111)=4, w(0000)은 제외 => wmin=2
           .. 따라서, dmin = wmin = 2
      - 오류검출능력 있음 : td ≤ dmin - 1 = 2 - 1 = 1 비트 이하
      - 오류정정능력 없음


4. 한편, 이상적인/좋은 부호는? 

  ㅇ 부호 길이(n)는, 짧을수록 좋고,
  ㅇ 유효 부호어 종류/갯수(2k)는, 많을수록 좋고,
  ㅇ 최소거리(dmin)는, 클수록 이상적 임
  ※ 즉, q진 (n, k, d)에서, n은 짧고, k 및 d는 클수록 좋은 부호 임