블록 부호

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

## 정의
### 해밍 결합 도식 속의 블록 부호
**블록 부호** (\Sigma,n,k,C)는 다음과 같은 데이터로 구성된다.
* 유한 집합 \Sigma. 이를 **알파벳**()이라고 한다.
* 양의 정수 n\in\mathbb Z^+. 이를 **블록 길이**()라고 하고, \Sigma^n의 원소를 **블록**()이라고 한다.
* 부분 집합 C\colon \Sigma^k\to\Sigma^n. C의 원소인 블록을 **부호어**(符號語, )라고 한다.

블록 부호 (\Sigma,n,C)의 **전송률**(電送率, )은
:R=\frac1n\log_{|\Sigma}/n
이며, 항상 0\le R\le 1이다. 블록 부호 (\Sigma,n,C)의 **상대 길이**(相對-, )는 유리수 \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)의 **최소 거리**(最小距離, )는 다음과 같다.
:d=\min_{a,b\in\Sigma^k,\;a\ne b}\operatorname{d_H}(C(a),C(b))

최소 거리가 d인 블록 부호 (\Sigma,n,C)는 흔히 **<math>[n,\log_{\Sigma}|C|,d]_</math>-블록 부호**라고 불린다.

### 일반 결합 도식 속의 블록 부호
위 정의는 결합 도식의 개념을 통해 일반화된다.

구체적으로, 다음이 주어졌다고 하자.
* 결합 도식 (X,\partial\colon X^2\to D)
* D의 부분 집합 E\subseteq D
이 경우, X의 부분 집합 C\subseteq X가 다음 조건을 만족시킬 경우, **<math>E</math>-블록 부호**()라고 한다.
* 임의의 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의 **내부 분포**(內部分布, )는 다음과 같은 유리수열이다.
*:\alpha_i=\frac
특히,
:\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
를 고르자. 이를 **부호화 함수**(符號化函數, )라고 한다.

이제, \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 (**싱글턴 상계** )
:k\le n-\log_q\left(\sum_{i=0}^{\lfloor(d-1)/2\rfloor}\binom ni(q-1)^i\right) (**해밍 상계** )

싱글턴 상계를 포화시키는 (즉, k+d=n+1인) 블록 부호를 **최대 거리 분리 부호**(最大距離分離符號, , 약자 MDS 부호)라고 한다.

해밍 상계를 포화시키는 블록 부호를 **완전 부호**(完全符號, )라고 한다.


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

최소 거리가 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_이며, \mathsf J_는 모든 성분이 1인 행렬(아다마르 곱의 항등원)이다. 또한,
:E_a=\sum_iQ_{ai}D_i
라고 하자 (D_i는 각 이항 관계 R_i\subseteq X^2의 인접 행렬).

이제, X 속의 블록 부호 C\subseteq X가 주어졌다고 하고, 그 내부 분포
:\alpha_i=\frac
를 생각하자. 그렇다면, **쌍대 내부 분포**(雙對內部分布, )는 다음과 같은 수열이다.
:\beta_a=\sum_iQ_{ai}\alpha_i
그렇다면, 다음과 같은 **맥윌리엄스 부등식**(MacWilliams不等式, )이 성립한다.
: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\sum_iQ_{ai}|C^2\cap R_i|\\
&=\frac1\sum_{x,y\in C}\sum_iQ_{ai}\langle x|D_i|y\rangle\\
&=\frac1\sum_{x,y\in C}\langle x|E_a|y\rangle
\end{aligned}

이므로,
:0\le\beta_a\le |C|
:\sum_a\beta_a=\frac1\sum_{x,y\in C}\langle x|\left(\sum_aE_a\right)|y\rangle
=\frac1\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)
이를 **<math>m</math>중 반복 부호**(m重反復符號, )라고 한다. 특히, (k,m,q)=(1,3,2)일 경우 이는 r=2 이진 해밍 부호와 같다.

### 선형 부호

**[[선형 부호]]**의 경우, \Sigma는 유한체이며, C\colon\Sigma^k\to\Sigma^n은 \Sigma-선형 변환이다.

선형 부호의 예로는 해밍 부호나 이진 골레 부호가 있다.

## 역사
싱글턴 상계는 리처드 콜럼 싱글턴()이 1964년에 증명하였다. 해밍 상계는 리처드 해밍이 증명하였다.

## 같이 보기
* 채널 용량
## 각주

## 외부 링크
* 
* 
* 
* 
* 
* 

분류:부호 이론