Parity Check Matrix   패리티 검사 행렬

1. [선형블록부호]  패리티 검사 행렬 (Parity Check Matrix) : H

  ㅇ 주어진 부호어가 유효 부호어인지 여부를 쉽게 검출할 수 있게 하는 행렬

       

  ㅇ 즉, 행렬 곱셈 만으로도, 주어진 부호어가 유효 부호어인지를 (오류 발생 여부를) 쉽게 파악 가능
     - 만일, (c HT = 0) 이면, 오류 없음


2. [선형블록부호]  패리티검사 행렬 H의 수신 부호어에 대한 오류 검출

  ㅇ 수신된 부호어 r와 HT를 곱한 (r HT 또는, H rT) 결과가, 0 벡터가 되는지에 따라, 오류 발생 여부 판단
     - r HT = 0 이면, 오류 없음
     - r HT ≠ 0 이면, 오류 발생


3. [선형블록부호]  패리티검사 행렬 H의 특징

  ㅇ H의 행렬 크기  :  (n-k) x n

  ㅇ 조직적 부호 형식을 취함
     - k 정보 비트열이, 부호화된 n 비트열 내에, 그대로 변형없이 포함되는 형태

  ㅇ (생성행렬 G),(패리티검사행렬 H)의 행들 간에, 서로 직교함
     - `생성행렬 G (k x n)`의 행들과 `패리티검사행렬 H ((n-k) x n)`의 행들이 서로 직교함
        . 즉, G HT = 0

     - (이유/근거)  :  c HT = 0  =>  (c = m G)  =>  m G HT = 0  =>  G HT = 0
        . 유효 부호어 c와 패리티 검사 행렬 H 간에,  c HT = 0
        . c = i G 이므로,  i G HT = 0
        . 따라서, 모든 유효 부호어애 대해서,  G HT = 0  
          
[# GH^T = \left[\begin{array}{c|c} I_k & P \end{array}\right] 
                    \left[ \begin{array}{c} P \\ \hline I_{n-k} \end{array} \right]
                  = P + P = 0 #]
           .. G  :  생성행렬, (행렬크기) k x n
           .. H  :  패리티검사행렬, (행렬크기) (n-k) x n
           .. Ik  :  단위행렬, (행렬크기) k x k
           .. P  :  부 행렬(Submatrix) 또는 계수 행렬, (행렬크기) k x (n-k)

  ㅇ H의 각 행이, 짝수 패리티 그룹을 형성
     - 각 행에서, 비트 `1` 들이, 짝수 패리티 비트가 됨
         
     - 즉, 각 행이, 패리티 검사 방정식이 됨
        . 이는, 각 부호어의 비트 선형 조합이 0 이 되는 방법을 보여줌
        . 例)  
[# H = \begin{bmatrix} 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{bmatrix} \qquad
                  \begin{array}{cc} p_1 = c_3 + c_4 = 0 \\ p_2 = c_1 + c_2 = 0 \end{array}#]

  ㅇ 동일 부호에도, 여러 등가적인 패리티 검사 행렬들이 있을 수 있음


4. [선형블록부호]  패리티검사 행렬 H의 표현 형태

   

  ㅇ   H : 패리티검사행렬, ( 행렬크기 : (n-k) x n )
  ㅇ   In-k : 단위 행렬, ( 행렬크기 : (n-k) x (n-k) )
  ㅇ   P : 부 행렬(Submatrix) 또는 계수 행렬, ( 행렬크기 : k x (n-k) )


5. [선형블록부호]  생성 행렬로부터 패리티 검사 행렬의 구성

  ㅇ 생성 행렬 G를, [ I |  P ] 형태로 변환  (I : 단위 행렬, P : 패리티 부분)
  ㅇ 패리티 검사 행렬 H를, [ PT | I ] 형태로 구성  (PT : P의 전치 행렬)
  ㅇ G와 H의 곱이 0이 되는지 확인하여, 올바르게 구성되었는지 검증  (G HT = 0)


6. [선형블록부호]  `패리티검사 행렬`, `신드롬` 간의 관계

  ㅇ c HT가 영이 아니면, 이는 오류의 징후(신드롬)을 알려줌

  ㅇ 패리티검사 행렬 H ((n-k) x n)의 어떤 열도 모두 0 이 될 수 없음
     - 만일, n개의 열 모두 0 이면, 그 열의 부호어 위치의 오류가 신드롬에 영향을 못미쳐, 검출 불가

  ㅇ 패리티검사 행렬 H ((n-k) x n)의 모든 열들이 유일(Unique)해야 함
     - 만일, 두 열이 같다면, 두 부호어 위치에서 발생한 오류는 구별 불가능