패리티 검사 행렬
GF(2) 위의 모든 선형 부호(0과 1만으로 이루어진 체, 산술은 mod 2)는 패리티 검사 행렬 H를 갖습니다. (7,4) 해밍 부호의 경우, H는 3×7 행렬이며, 그 열들은 1부터 7까지의 이진 표현입니다:
``
H = [ 0 0 0 1 1 1 1 ] ← bit 2 of position number
[ 0 1 1 0 0 1 1 ] ← bit 1 of position number
[ 1 0 1 0 1 0 1 ] ← bit 0 of position number
``
H의 j번째 열은 j의 이진 표현입니다. 이것이 증후군 s = Hr이 오류 위치를 직접 명시하는 이유입니다.
사상 H: GF(2)^7 → GF(2)^3은 선형 사상입니다(행렬 곱셈 mod 2). 그 핵(kernel) ker(H) = { r : Hr = 0 }은 정확히 유효한 부호어(codeword)들의 집합입니다.
차원 계산: dim(ker H) = 7 − rank(H) = 7 − 3 = 4. 따라서 2^4 = 16개의 부호어가 있습니다. 이는 4개의 메시지 비트를 확인합니다.
커널로서의 부호
단어 c ∈ {0,1}^7은 Hc = 0 (mod 2)일 때만 유효한 부호어입니다. 이것이 선형 부호의 정의 방정식입니다.
예: c = 0011001. Hc mod 2를 확인합니다:
``
Row 1: 0·0+0·0+0·1+1·1+1·0+1·0+1·1 = 0+0+0+1+0+0+1 = 2 ≡ 0
Row 2: 0·0+1·0+1·1+0·1+0·0+1·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
Row 3: 1·0+0·0+1·1+0·1+1·0+0·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
``
Hc = 000. 따라서 0011001은 유효한 부호어입니다.
부호의 코셋
부호어들 C = ker(H)는 GF(2)^7의 부분군을 형성합니다. GF(2)^7의 다른 모든 단어는 정확히 하나의 C의 코셋에 속합니다.
코셋 정의: 임의의 단어 e에 대해, 코셋 C + e = { c + e : c ∈ C }입니다.
두 단어가 같은 코셋에 속할 필요충분조건은 그들의 차이가 부호어라는 것입니다. 동치적으로, 같은 증후군을 가집니다: H(r₁) = H(r₂) iff H(r₁ − r₂) = 0 iff r₁ − r₂ ∈ C.
증후군 사상 H는 동형사상 GF(2)^7 / C ≅ GF(2)^3을 유도합니다. |C| = 16, |GF(2)^7| = 128에서: 정확히 128/16 = 8개의 코셋이 있으며, GF(2)^3의 각 증후군 값 하나에 대응합니다.
표준 배열: 각 코셋당 코셋 리더 하나를 나열합니다. 그 코셋에서 해밍 무게가 최소인 단어입니다. 단일 오류 정정의 경우, 각 0이 아닌 증후군은 고유하게 무게-1 오류 패턴(7개 위치 중 하나에 단일 1)에 대응됩니다. 그래서 7개의 오류 패턴 + 1개의 오류 없음 = 8개의 코셋 = 2^3입니다.
코셋 리더를 통한 복호화
복호화 알고리즘: r을 수신 → s = Hr 계산 → 코셋 리더 e_s 찾기(증후군 s에 대한 정식 오류) → r − e_s = r + e_s(GF(2)에서 같음) 출력.
(7,4) 부호의 경우, 8개의 코셋 리더는: 0000000 (증후군 000), 1000000 (증후군 001), 0100000 (증후군 010), 0010000 (증후군 011), 0001000 (증후군 100), 0000100 (증후군 101), 0000010 (증후군 110), 0000001 (증후군 111)입니다.
(7,4)가 완벽한 이유
최소 거리 3인 부호 C ⊆ GF(2)^n은 모든 단일 오류를 정정합니다. 각 부호어 c는 반지름 1의 해밍 구: 중심 c와 그 n개의 즉각적인 이웃(무게-1 오류 패턴). 구의 부피 = 1 + n.
n = 7의 경우: 구의 부피 = 8. 16개의 부호어 포함: 16 × 8 = 128 = 2^7. 구들은 GF(2)^7을 완벽하게 타일합니다. 점이 남지 않으며 어떤 점도 두 번 덮이지 않습니다.
이것이 완벽한 부호의 정의입니다: M · Vol(n, t) = 2^n. 완벽한 단일-오류-정정 이진 부호(t=1)는 특정 매개변수에서만 존재합니다: (7,4), (15,11), (23,12) (이진 골레이 부호), 그리고 자명하게 n = 2^r − 1, k = n − r는 모든 r ≥ 2에 대해.
기하학: GF(2)^7은 코셋 분할로서 부호의 작용 아래 정확히 8개의 궤도로 분해됩니다. 각 궤도는 코셋이며, 각 코셋은 고유한 증후군을 가집니다. 증후군 사상 H는 코셋에서 GF(2)^3으로의 전단사입니다.
계산 논증
n = 2^r − 1 비트의 완벽한 단일-오류-정정 부호의 경우 r개의 패리티 검사 비트:
- 부호어의 개수: M = 2^k = 2^(n−r)
- 구의 부피: Vol(n, 1) = 1 + n = 1 + 2^r − 1 = 2^r
- 전체 덮음: M × Vol = 2^(n−r) × 2^r = 2^n ✓
n = 2^r − 1일 때 Vol(n,1) = 2^r라는 사실이 이 길이에서 완벽한 부호를 가능하게 합니다. 다른 길이에서, 1 + n은 2의 거듭제곱이 아니며, 완벽한 단일-오류-정정 이진 부호는 존재할 수 없습니다.
생성 행렬 & 쌍대성
패리티 검사 행렬 H는 커널을 통해 부호를 정의합니다. 그 쌍대: ker(H)의 기저를 형성하는 생성 행렬 G.
(7,4) 부호의 경우: G는 4×7 행렬입니다. 모든 부호어 c = mG는 어떤 메시지 벡터 m ∈ GF(2)^4입니다. G의 행들은 부호를 생성하고, H의 행들은 부호의 널 공간을 생성합니다.
핵심 관계: HG^T = 0 (mod 2). G의 모든 행이 ker(H)에 있고, H의 모든 행이 G의 모든 행을 소멸시킵니다.
쌍대 부호: C⊥ = ker(G^T) = image(H^T). (7,4) 부호의 경우, 쌍대는 [7,3,4] 부호입니다(최소 거리 4인 (7,3) 부호).
쌍대성의 기하학: C와 C⊥은 GF(2)^7의 직교 부분공간입니다. 전체 공간은 부호, 그 코셋, 그리고 증후군 사상이 인코딩하는 쌍대 구조로 분해됩니다.