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의 특징
ㅇ 부호어(C), 생성 행렬(G), 패리티 검사 행렬(H) 간의 관계
- 선형 블록 부호 C가, 생성행렬 G (크기 k x n)로 정의될 때, 패리티 검사 행렬 H는 다음을 만족
. {# GH^T = \mathbf{0} \quad \iff \quad \mathbf{c} \in C
\quad \iff \quad H\mathbf{c}^T = \mathbf{0} #}
ㅇ 직교성 : (직교성이, C,G,H 간의 관계성을 잘 보여줌)
- (생성 행렬 G의 행 공간) ⊥ (패리티 검사 행렬 H의 행 공간)
. G와 H의 행들 사이에 서로 직교 → {#GH^T = \mathbf{0}#}
. 이로부터 모든 부호어 {#\mathbf{c} = \mathbf{m}G#}에 대해 직교성이 성립
- 모든 부호어 C에 대해, {#H\mathbf{c}^T = \mathbf{0}#} 또는 {#\mathbf{c}H^T = \mathbf{0}#}
. (H의 각 행 벡터 {#\mathbf{h}_i#}와 부호어 벡터 {#\mathbf{c}#}의 내적이 모두 0)
.. (내적이 0) = (두 벡터가 직교)
. (C의 행 공간) ⊥ (H의 행 공간)
.. (부호어 C와 패리티 검사 행렬 H의 행들은, 서로 직교(수직)함)
- (부호어 C) = (패리티 검사 행렬 H의 영 공간)
. (영 공간 (Kernel) : H를 곱했을 때 {#\mathbf{0}#}이 되는 벡터들의 집합)
* [요약]
. {# GH^T = \mathbf{0} \quad \implies \quad \mathbf{c} = \mathbf{m}G \quad \implies \quad
H\mathbf{c}^T = \mathbf{0} \quad \implies \quad C = \ker(H) #}
ㅇ H의 행렬 크기 : (n - k) x n
- (n - k) : 행의 수 = 패리티 비트 수 = 랭크 (행이 선형독립)
. 독립적인 패리티 검사 식(제약조건)의 수
- n : 열의 수 = 부호어 길이
. 각 열이 부호어의 각 비트 위치에 대응
ㅇ H와 오류 검출 능력/오류 정정 능력 간의 관계
- H의 임의 d−1개 열이 선형 독립이면, => d−1개 오류 검출 가능
- H의 임의 2t개 열이 선형 독립이면, => t개 오류 정정 가능
- H와 최소 거리 간의 관계 => dmin = (H에서 선형 종속을 이루는 최소 열의 수)
* H의 열들이, 얼마나 "독립적"으로 구성되어 있는가가, 곧 그 부호의 오류 정정 능력을 결정함
ㅇ H가 조직적 부호(Systematic) 형태일 경우에,
- 생성행렬 G 및 패리티검사행렬 H를 특정 표준 형태로 표현 가능 => 아래 4,5항 참조
. (k 정보 비트열이, 부호화된 n 비트열 내에, 그대로 변형없이 포함되는 형태)
ㅇ H의 각 행이, 하나의 패리티 검사식(parity-check equation)을 구성
- 각 행에서, 비트 `1` 들이, 짝수 패리티 비트가 됨
[# p_1 = m_1p_{11} + m_2p_{11} + \cdots + m_kp_{k1} \\
p_2 = m_1p_{12} + m_2p_{22} + \cdots + m_kp_{k2} \\
\cdots \\
p_{n-k} = m_1p_{1(n-k)} + m_2p_{2(n-k)} + \cdots + m_kp_{k(n-k)} #]
- 즉, 각 행이, 패리티 검사 방정식이 됨
. 이는, 각 부호어의 비트 선형 조합이 0 이 되는 방법을 보여줌
. 例) [# H = \begin{bmatrix} 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{bmatrix} \qquad
\begin{array}{cc} c_3 + c_4 = 0 \\
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 (k x n)를, 표준형 [ Ik | P ] 형태로 변환하면,
- {# \mathbf{c} = \mathbf{m}G = \mathbf{m}[I_k \mid P]
= [\mathbf{m} \mid \mathbf{m}P] #}
. {#\mathbf{c}#} : 메세지 벡터, Ik : 단위 행렬, P : 패리티 생성 행렬
- {#GH^T = \mathbf{0}#} 조건을 만족해야 하므로,
ㅇ 패리티 검사 행렬 H를, [ PT | Ik ] 형태로 구성
- (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)해야 함
- 만일, 두 열이 같다면, 두 부호어 위치에서 발생한 오류는 구별 불가능