블록 부호

수학과 컴퓨터 과학에서 **블록 부호**(block符號, 블록 코드)는 데이터를 중복해서 “블록”으로 부호화하되, 각 비트 또는 블록의 성분이 전송 과정에서 노이즈를 겪어 바뀌는 것을 일부 경우 교정할 수 있게 하는 부호화 체계이다.언어=en언어=en언어=en언어=en
# 정의

## 해밍 결합 도식 속의 블록 부호
**블록 부호** (\Sigma,n,k,C)는 다음과 같은 데이터로 구성된다. * 유한 집합 \Sigma. 이를 **알파벳**(alphabet)이라고 한다. * 양의 정수 n\in\mathbb Z^+. 이를 **블록 길이**(block length)라고 하고, \Sigma^n의 원소를 **블록**(block)이라고 한다. * 부분 집합 C\colon \Sigma^k\to\Sigma^n. C의 원소인 블록을 **부호어**(符號語, codeword)라고 한다. 블록 부호 (\Sigma,n,C)의 **전송률**(電送率, rate)은 :R=\frac1n\log_{|\Sigma}/n 이며, 항상 0\le R\le 1이다. 블록 부호 (\Sigma,n,C)의 **상대 길이**(相對-, relative distance)는 유리수 \delta=d/n이며, 마찬가지로 1 이하의 양의 유리수이다. \Sigma^n 위에 해밍 거리 :\operatorname{d_H}(s,t)=|\\{i\in\\{1,\dotsc,n\\}\colon s_i\ne t_i\\}| 를 정의하면, 이는 거리 공간을 이룬다. 블록 부호 (\Sigma,n,C)의 **최소 거리**(最小距離, minimum distance)는 다음과 같다. :d=\min_{a,b\in\Sigma^k,\;a\ne b}\operatorname{d_H}(C(a),C(b)) 최소 거리가 d인 블록 부호 (\Sigma,n,C)는 흔히 **[n,\log_{\Sigma}|C|,d]_{|\Sigma|}-블록 부호**라고 불린다.
## 일반 결합 도식 속의 블록 부호
위 정의는 결합 도식의 개념을 통해 일반화된다.언어=en언어=en2483–2486, §Ⅲ 구체적으로, 다음이 주어졌다고 하자. * 결합 도식 (X,\partial\colon X^2\to D) * D의 부분 집합 E\subseteq D 이 경우, X의 부분 집합 C\subseteq X가 다음 조건을 만족시킬 경우, **E-블록 부호**(E-block code)라고 한다.2483, Definition 5 * 임의의 x,y\in C에 대하여, \partial(x,y)\not\in E X 속의 **블록 부호**란 \varnothing-블록 부호를 뜻한다. 만약 X=\Sigma^n이 \Sigma 위의 n차원 해밍 결합 도식일 경우, \partial=\operatorname{d_H}는 해밍 거리가 되며, 이 경우 위의 기초적 정의로 귀결된다. 결합 도식 X 속의 블록 부호 C\subseteq X에 대하여, * X의 원소를 **블록**이라고 한다. * C의 원소를 **부호어**라고 한다. * C의 **전송률**은 R=\ln C/\ln X이다. 이는 0\le R\le 1인 실수이다. * X의 이항 관계가 (R_i\subseteq X^2)_{i\in I}라고 할 때, C의 **내부 분포**(內部分布, inner distribution)는 다음과 같은 유리수열이다.2483, Definition 4 *:\alpha_i=\frac{|C^2\cap R_i|}{|C|} 특히, :\sum_i\alpha_i=|C| 가 성립한다. 만약 거리 함수의 공역 D가 전순서 집합일 때, 마찬가지로 **최소 거리** :d=\min_{x,y\in C}\partial(x,y) 를 정의할 수 있다.
# 성질

## 블록 부호를 사용한 데이터의 전송
[n,k,d]_q-블록 부호 C\subseteq\Sigma^n이 주어졌다고 하고, 편의상 k가 정수라고 하자. 이 경우, 임의의 전단사 함수 :f\colon\Sigma^k\to C\subseteq \Sigma^c 를 고르자. 이를 **부호화 함수**(符號化函數, coding function)라고 한다. 이제, \Sigma^k의 한 원소를 노이즈가 있는 채널로 전송한다고 하자. 즉, 전송 도중 벡터 v\in\Sigma^n의 n개의 성분 가운데 일부가 다른 값으로 바뀔 수 있다. 만약 문자열 v\in\Sigma^n를 수신하였을 때, 다음과 같은 알고리즘을 사용하여 데이터를 교정한다고 하자. * 만약 \min_{c\in C}\operatorname{d_H}(v,c)라면, v를 \operatorname{d_H}(v,f(c))인 유일한 원소 c\in\Sigma^k로 교정한다. * 만약 \min_{c\in C}\operatorname{d_H}(v,c)\ge d/2라면, 데이터의 교정은 실패한다. 이 경우, * 만약 n개의 성분 가운데 \lceil d/2-1\rceil개 이하가 잘못되었다고 가정하면, 수신된 데이터를 오류 없이 교정할 수 있다. * 만약 n개의 성분 가운데 d-1개 이하가 잘못되었다고 가정하면, 데이터의 송신 도중 오류가 발생하였는지 여부를 항상 확인할 수 있다. (그러나 이 오류를 항상 교정할 수 있지는 않다.)
## 블록 부호가 존재할 필요 조건
모든 [n,k,d]_q-블록 부호는 다음 두 조건을 만족시킨다. :k\le n+1-d (**싱글턴 상계** Singleton bound) :k\le n-\log_q\left(\sum_{i=0}^{\lfloor(d-1)/2\rfloor}\binom ni(q-1)^i\right) (**해밍 상계** Hamming bound) 싱글턴 상계를 포화시키는 (즉, k+d=n+1인) 블록 부호를 **최대 거리 분리 부호**(最大距離分離符號, maximum-distance-separable code, 약자 MDS 부호)라고 한다. 해밍 상계를 포화시키는 블록 부호를 **완전 부호**(完全符號, perfect code)라고 한다.

**싱글턴 상계의 증명**:

최소 거리가 d인 블록 부호 C\subseteq\Sigma^n가 주어졌다고 하자. 그렇다면, 모든 부호어에서 처음 d-1개의 성분들을 삭제하여 블록 부호 :C'\subseteq\Sigma^{n-d+1} :C'=\\{(s_1,s_2,\dotsc,s_{n-d+1})\colon s\in C\\} 를 정의할 수 있다. 따라서, :|C|=|C'|\le q^{n-d+1} 이다.

### 맥윌리엄스 부등식
보다 일반적으로, 임의의 결합 도식 (X,\partial)이 주어졌다고 하자. X의 복소수 계수 보스-메스너 대수는 복소수 반단순 대수이며, 그 최소 멱등원들을 :E_0,E_1,\dotsc,E_p 라고 하자. 여기서 E_0=|X|^{-1}\mathsf J_{|X|\times|X|}이며, \mathsf J_{|X|\times|X|}는 모든 성분이 1인 행렬(아다마르 곱의 항등원)이다. 또한, :E_a=\sum_iQ_{ai}D_i 라고 하자 (D_i는 각 이항 관계 R_i\subseteq X^2의 인접 행렬). 이제, X 속의 블록 부호 C\subseteq X가 주어졌다고 하고, 그 내부 분포 :\alpha_i=\frac{|C^2\cap R_i|}{|C|} 를 생각하자. 그렇다면, **쌍대 내부 분포**(雙對內部分布, dual inner distribution)는 다음과 같은 수열이다. :\beta_a=\sum_iQ_{ai}\alpha_i 그렇다면, 다음과 같은 **맥윌리엄스 부등식**(MacWilliams不等式, MacWilliams inequality)이 성립한다.2484, Theorem 3 :0\le\beta_a\le|C|\qquad\forall a :\sum_a\beta_a=|C|

**증명:**

각 E_a는 멱등원이므로, 그 고윳값은 0 또는 1이다. 따라서, 임의의 x,y\in X에 대하여, \langle x|y\rangle=\delta_{xy}이므로, :0\le\langle x|E_a|y\rangle\le 1\qquad\forall a 이다. (\delta_{xy}는 크로네커 델타이다.) 이에 따라, :\begin{aligned} \beta_a&=\sum_iQ_{ai}\alpha_i\\\ &=\frac1{|C|}\sum_iQ_{ai}|C^2\cap R_i|\\\ &=\frac1{|C|}\sum_{x,y\in C}\sum_iQ_{ai}\langle x|D_i|y\rangle\\\ &=\frac1{|C|}\sum_{x,y\in C}\langle x|E_a|y\rangle \end{aligned} 이므로, :0\le\beta_a\le |C| :\sum_a\beta_a=\frac1{|C|}\sum_{x,y\in C}\langle x|\left(\sum_aE_a\right)|y\rangle =\frac1{|C|}\sum_{x,y\in C}\langle x|y\rangle=|C| 이다.

# 예

## 자명한 부호
자명한 예로, n=k이며 C가 순열인 경우를 생각하자. 이 경우 최소 거리는 1이다. 즉, 이 부호는 최고의 송신률 k/n=1을 갖지만, 아무런 오류를 교정하지 못한다. 마찬가지로, 예를 들어 어떤 임의의 \alpha\in\Sigma에 대하여 :C\colon\Sigma^k\to\Sigma^n :C\colon (s_1,s_2,\dotsc,s_k)\mapsto (s_1,s_2,\dotsc,s_k,\underbrace{\alpha,\alpha,\dotsc,\alpha}^{n-k}) 를 생각하자. 그 효율은 k/n이지만, 이 부호 역시 최소 거리가 1이므로, 아무런 오류를 교정하지 못한다.
## 반복 부호
임의의 알파벳 \Sigma (|\Sigma|=q) 및 양의 정수 k\in\mathbb Z^+ 및 양의 정수 m에 대하여, 다음과 같은 [mk,k,m]_q-블록 부호를 얻을 수 있다. :C\colon\Sigma^k\to\Sigma^{mk} :C\colon (s_1,s_2,\dotsc,s_k)\mapsto (\underbrace{s_1,\dotsc,s_1}_m,\underbrace{s_2,\dotsc,s_2}_m,\dotsc,\underbrace{s_k,\dotsc,s_k}_m) 이를 **m중 반복 부호**(m重反復符號, m-tuple repetition code)라고 한다. 특히, (k,m,q)=(1,3,2)일 경우 이는 r=2 이진 해밍 부호와 같다.
## 선형 부호
선형 부호 **선형 부호**의 경우, \Sigma는 유한체이며, C\colon\Sigma^k\to\Sigma^n은 \Sigma-선형 변환이다. 선형 부호의 예로는 해밍 부호나 이진 골레 부호가 있다.
# 역사
싱글턴 상계는 리처드 콜럼 싱글턴(Richard Collom Singleton)이 1964년에 증명하였다.언어=en 해밍 상계는 리처드 해밍이 증명하였다.