Standard Array   표준 배열

1. 표준 배열

  ㅇ 모든 가능한 수신 벡터를, 한눈에 보이도록, 2n개의 n 튜플들로 배열화시킨 표현 형식

  ㅇ 특히,
     - 선형 블록 부호의 전체 윤곽이 드러나 보이므로,
     - 이해 및 해석에 도움을 주며, 복호 원리를 잘 나타냄
 

2. 표준 배열의 형태

   

  ㅇ 例)
     - 만일, 어떤 블록 부호가,
        . 심볼 종류가 q개(즉, q-ary)인, (n,k) 선형부호 이라면,
     - 이때, 표준 배열 구성은,
        . (qk)개의 유효 부호어와,
        . 그 각각이 (qn - qk)개의 오류패턴을 갖는,
        . (qn-k x qk = qn)개의 부호들이 존재 가능함


3. 표준 배열의 특징

  ㅇ 표준 배열은, 
     - 벡터공간 상에, 수신 가능한 모든 순서쌍(2n개 요소들)을, 배열 형태로 보여주고 있음
     - 각 요소(원소)는, 유일한 오류 위치를 하나도 빠지지 않고, 나타내고 있음
        . 단, 첫 행은, 오류 없음을 나타냄
     - 각 열은, 모든 가능한 유효 부호어 및 그로부터 오염된 부호어들을 나타냄
     - 각 행(코셋)은, 모든 가능한 오류패턴 및 매 첫 요소와 동일한 오류패턴들을 나타냄
        . 즉, 동일한 오류패턴들이 총 2k개로 구성됨

  ㅇ 구체적으로, 표준 배열의 행과 열에서,
     - 첫 행은, 모든 유효 부호어 즉, 오류 없음을 보여줌
        . 맨좌측에 모두 0인(all-zero) 부호어(v1=0)로부터 출발하여 모든 유효 부호어들을 포함
     - 각 행은, 코셋(Coset) 이라고 함
        . 그 의미는, 공통된 특징(즉,동일 오류 패턴)을 갖는 요소들로 이루어짐을 말함
        . 한편, 행(코셋)의 수(즉,오류 패턴의 수)는, (2n)/(2k) = 2n-k개가 있음
     - 첫 열은, 코셋 리더(Coset Leader) 이라고 함
        . 모든 정정 가능한 오류 패턴을 포함 
           .. 오류 패턴(코셋 리더) : ej (j = 1,2,...,2n-k) 임
        . 코셋 리더(오류 패턴)와 신드롬과는 일대일 대응됨
           .. 신드롬 : ejHT
        . 例) (vi + ej)에 대한 신드롬은,
           .. s = (vi + ej)HT = viHT + ejHT = ejHT
     - 나머지 열,행들은 (요소들은), 
        . 첫 열의 오류 패턴 방식에 의해 동일하게 오염된 부호어들
           .. 이들은, `코셋리더 (첫열 오류패턴)`와 `오류없는 유효 부호어 (첫행)`와의 합 임 


4. 표준 배열에 의한 복호  :  (≒ 신드롬 복호)

  ㅇ 표준 배열 복호  :  (복호화 특징)
     - (의미)
        . 둘째행 이후, 오염된 수신 벡터를, 맨 위 첫 행에 있는 유효 부호어로 바꾸는 것임
     - (핵심 동작 : Look Up 검색)
        . 전체 표준 배열 내 가장 가까운 유효 부호어를 찾는 것 (Look Up)
           .. 즉, 수신 받은 오류 섞힌 코드로부터 가장 가까운 유효 부호어를 찾는 것
           .. 사실상, 이는 `최대 우도 복호 (MLD)`로 볼 수 있음
     - (비 효율적)
        . 매번 전체 검색이 필요하여, 비 효율적인 방식임

  ㅇ 신드롬 복호  :  (복호화 단계)
     - ① 수신된 부호 벡터 (r = c + e)에 대해 신드롬을 계산  :  s = r HT
     - ② 해당 신드롬을 신드롬 열(syndrome column)에서 찾음  
     - ③ 해당 신드롬에 대응하는 코셋 리더(coset leader)를 결정
        . 이는 바로 `오류 벡터 e`임  
     - ④ 이 오류 벡터를 수신된 단어에서 빼서, 코드워드(codeword)를 구함  :  c = r - e

  ㅇ 신드롬 복호기  :  (블록도)
      
     - 특히, 어떤 오류패턴이 어떤 신드롬과 매칭되는지 만을, 알 필요 있음

  ㅇ 표준 배열 복호, 신드롬 복호  :  (비교)
     - 표준 배열 복호는, 전체 코셋을 표준 배열을 통해 명시적으로 구성하는 방식 
        . 수신 부호 벡터가 표준 배열의 어느 코셋에 속하는지 찾은 후, 
        . 해당 코셋 리더(오류 벡터)를 제거하여, 올바른 코드 워드를 복원함
     - 신드롬 복호는, 수신 벡터의 신드롬을 직접 계산하여, 해당 코셋 리더를 찾는 방식
     - 사실상, 표준 배열 복호화,신드롬 복호화는, 
        . 동일 개념을 기반으로 한 유사 형태 임