Linear Code, Linear Coding   선형 부호, 선형 코드

(2023-08-26)

Linear Block Code, 선형 블록 부호, 선형 블록 코드


1. 선형 부호 (Linear Code)부호어 집합선형 벡터공간을 형성하는 부호
     - 블록부호 구조에 추가적으로 선형 조건이 가해지면, 선형 블록부호가 얻어짐
        . 즉, 선형 블록부호블록 부호부분 집합임

  ※ (블록 부호 vs 선형 부호)
     - 블록 부호 그 자체로는, 유익한 구조가 없으나, 
     - 선형 블록 부호는, 채널 부호화를 위한 좋은 구조이며, 이를 만족하는 꽤많은 부호들이 존재함


2. 선형 부호의 주요 성질/특징중첩의 원리 (superposition)
     - 임의의 두 부호어(Codeword)의 합(또는,차)이 그 부호에 속하는 다른 부호어가 됨
        . 닫힘 성질이라고도 함

  ㅇ 전 영 특성 (all zero)
     - 모두 영(`0`)인 부호어유효 부호어가 됨

  ㅇ 두 부호어 간의 거리 특성이 모든 부호어에서 동일함
     - 따라서, 모든 부호어 간의 거리를, 전영 `0`인 부호어로부터의 거리로 특징지울 수 있음
     - 이로써, 모두 `0`인 부호어 이외 부호어들에서,
         . 최소무게 = 최소거리 (d = w)
     - 결국, 선형부호에서, 해밍 최소거리해밍 최소무게와 같아짐
         . (dmin = wmin)  

  ※ 결국, 유효 부호어 집합이 항상 선형 벡터공간을 형성하게 됨
     - 例) 만일, (n,k) 선형 블록부호이면, 
        . 부호길이가 n 이고, 랭크가 k 로써 선형 벡터공간생성함
           .. 즉, 임의 유효 부호어를 k개의 선형독립부호어들의 선형결합에 의해 나타낼 수 있음
        . 이때의 부호율은 R = k/n 임


3. 선형 블록부호의 例)선형 블록부호가 아닌 경우 : C = {0000,1010,1111,1100}
     - 1010 ⊕ 1111 = 0101 인데, 0101은 유효 부호어에 속해있지 않음

  ㅇ 선형 블록부호인 경우 : C = {0000,1010,0101,1111}
     - (전 영 특성) 
        . 모두 영(`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 => d=2
        . w(1010)=2, w(0101)=2, w(1111)=4, w(0000)은 제외 => w=2
        . 따라서, d = w = 2


4. 선형 블록부호의 응용 상의 특징행렬 표현에 의해, 부호화,복호화가 쉽게 이루어짐          ☞ 생성 행렬, 패리티 검사 행렬 참조
     - (부호화) 선형 블록부호의 생성        =>  `생성행렬`  :  k x n 크기의 행렬
     - (복호화) 유효 부호어 확인/오류 검출  =>  `패리티검사행렬`  :  (n − k) × n 크기의 행렬

  ㅇ 빠르고 쉬운 부호화/복호화
     - 선형성,행렬계산에 의해, 빠르고 쉽게 부호화(Coding) 및 복호화(Decoding)가 가능

  ㅇ 조직적 부호 형태로 표현 가능
     - 모든 선형부호는 조직적 부호 형태로 표현될 수 있음

  ㅇ 부호화,복호화의 유일성
     - (부호화 유일성)
        . 각 결과 부호어(n 튜플)가 입력 부호어(k 튜플)에 의해 유일하게(Uniquely) 결정됨
     - (복호화 유일성) 
        . 정정 가능한 오류 패턴과 이의 오증(신드롬,오류 진단)이 일대일 대응 관계를 갖음 
        . [참고] ☞ 오류패턴,신드롬,표준 배열 참조

  ㅇ 선형부호의 생성을, 조합논리회로로써 구현 가능
     - 선형 피드백 시프트 레지스터(LFSR)에 의해 생성 가능

  ㅇ 주요 선형 블록부호 例
     - 반복 부호, 해밍 부호, 순회 부호, 짝수 패리티 부호, 직각 부호5. 선형 부호의 생성 및 에러검출선형 블록 부호의 생성 및 에러검출 (편리한 수학적 도구가 존재함)
     - [생성]
        . 생성행렬   => 선형 블록부호  (블록부호화 과정을 행렬로 표시)
           .. 부호화 : 행렬의 곱으로 표현
           .. 부호어 : 행 또는 열 벡터로 표현
        . 생성다항식 => 순환부호      (비트의 전후 위치에 따른 순서까지도 표현이 가능)
           .. 부호화 : 다항식의 곱으로 표현
           .. 부호어 : 다항식으로 표현
     - [오류검출] => 생성행렬에 대응시킨 패리티검사행렬
     * 한편, 생성행렬의 선택이 유일하지 않음 

  ㅇ 직교 코드의 생성
     - 例) ☞ 왈시 하다마드 행렬, 하다마드 행렬 참조
     * 에러제어 보다는 직교성,식별성,랜덤성 등을 강조한 선형 블록 부호


6. 선형 부호의 복호최근접 이웃 복호 (Nearest Neighbor Decoding, Minimum Distance Decoding)
     - 수신 부호 시퀸스와 모든 가능한 기지의 부호 시퀸스 간에, 해밍거리가 최소인 것을 찾음
  ㅇ 신드롬 복호 (Syndrom Decoding)
     - 선형성, 룩업 테이블(look-up table) 이용
        . 신드롬 계산 => 오류 패턴 찾음 => 오류 정정


7. [참고사항]선형블록부호 용어 명칭 및 표기  ☞ 블록 부호 표기 참조

선형 부호
   1. 선형 블록부호  


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