블록 부호

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

정의

해밍 결합 도식 속의 블록 부호

블록 부호 ${\displaystyle (\Sigma ,n,k,C)}$는 다음과 같은 데이터로 구성된다.

• 유한 집합 ${\displaystyle \Sigma }$. 이를 알파벳(영어: alphabet)이라고 한다.
• 양의 정수 ${\displaystyle n\in \mathbb {Z} ^{+}}$. 이를 블록 길이(영어: block length)라고 하고, ${\displaystyle \Sigma ^{n}}$의 원소를 블록(영어: block)이라고 한다.
• 부분 집합 ${\displaystyle C\colon \Sigma ^{k}\to \Sigma ^{n}}$. ${\displaystyle C}$의 원소인 블록을 부호어(符號語, 영어: codeword)라고 한다.

블록 부호 ${\displaystyle (\Sigma ,n,C)}$의 전송률(電送率, 영어: rate)은

${\displaystyle R={\frac {1}{n}}\log _{|\Sigma }/n}$

이며, 항상 ${\displaystyle 0\leq R\leq 1}$이다. 블록 부호 ${\displaystyle (\Sigma ,n,C)}$의 상대 길이(相對-, 영어: relative distance)는 유리수 ${\displaystyle \delta =d/n}$이며, 마찬가지로 1 이하의 양의 유리수이다.

${\displaystyle \Sigma ^{n}}$ 위에 해밍 거리

${\displaystyle \operatorname {d_{H}} (s,t)=|\{i\in \{1,\dotsc ,n\}\colon s_{i}\neq t_{i}\}|}$

를 정의하면, 이는 거리 공간을 이룬다. 블록 부호 ${\displaystyle (\Sigma ,n,C)}$의 최소 거리(最小距離, 영어: minimum distance)는 다음과 같다.

${\displaystyle d=\min _{a,b\in \Sigma ^{k},\;a\neq b}\operatorname {d_{H}} (C(a),C(b))}$

최소 거리가 ${\displaystyle d}$인 블록 부호 ${\displaystyle (\Sigma ,n,C)}$는 흔히 ${\displaystyle [n,\log _{\Sigma }|C|,d]_{|\Sigma |}}$-블록 부호라고 불린다.

일반 결합 도식 속의 블록 부호

위 정의는 결합 도식의 개념을 통해 일반화된다.^{[5][6]:2483–2486, §Ⅲ}

구체적으로, 다음이 주어졌다고 하자.

• 결합 도식 ${\displaystyle (X,\partial \colon X^{2}\to D)}$
• ${\displaystyle D}$의 부분 집합 ${\displaystyle E\subseteq D}$

이 경우, ${\displaystyle X}$의 부분 집합 ${\displaystyle C\subseteq X}$가 다음 조건을 만족시킬 경우, ${\displaystyle E}$-블록 부호(영어: ${\displaystyle E}$-block code)라고 한다.^{[6]:2483, Definition 5}

• 임의의 ${\displaystyle x,y\in C}$에 대하여, ${\displaystyle \partial (x,y)\not \in E}$

${\displaystyle X}$ 속의 블록 부호란 ${\displaystyle \varnothing }$-블록 부호를 뜻한다.

만약 ${\displaystyle X=\Sigma ^{n}}$이 ${\displaystyle \Sigma }$ 위의 ${\displaystyle n}$차원 해밍 결합 도식일 경우, ${\displaystyle \partial =\operatorname {d_{H}} }$는 해밍 거리가 되며, 이 경우 위의 기초적 정의로 귀결된다.

결합 도식 ${\displaystyle X}$ 속의 블록 부호 ${\displaystyle C\subseteq X}$에 대하여,

• ${\displaystyle X}$의 원소를 블록이라고 한다.
• ${\displaystyle C}$의 원소를 부호어라고 한다.
• ${\displaystyle C}$의 전송률은 ${\displaystyle R=\ln C/\ln X}$이다. 이는 ${\displaystyle 0\leq R\leq 1}$인 실수이다.
• ${\displaystyle X}$의 이항 관계가 ${\displaystyle (R_{i}\subseteq X^{2})_{i\in I}}$라고 할 때, ${\displaystyle C}$의 내부 분포(內部分布, 영어: inner distribution)는 다음과 같은 유리수열이다.^{[6]:2483, Definition 4}

  ${\displaystyle \alpha _{i}={\frac {|C^{2}\cap R_{i}|}{|C|}}}$

특히,

${\displaystyle \sum _{i}\alpha _{i}=|C|}$

가 성립한다.

만약 거리 함수의 공역 ${\displaystyle D}$가 전순서 집합일 때, 마찬가지로 최소 거리

${\displaystyle d=\min _{x,y\in C}\partial (x,y)}$

를 정의할 수 있다.

성질

블록 부호를 사용한 데이터의 전송

${\displaystyle [n,k,d]_{q}}$-블록 부호 ${\displaystyle C\subseteq \Sigma ^{n}}$이 주어졌다고 하고, 편의상 ${\displaystyle k}$가 정수라고 하자. 이 경우, 임의의 전단사 함수

${\displaystyle f\colon \Sigma ^{k}\to C\subseteq \Sigma ^{c}}$

를 고르자. 이를 부호화 함수(符號化函數, 영어: coding function)라고 한다.

이제, ${\displaystyle \Sigma ^{k}}$의 한 원소를 노이즈가 있는 채널로 전송한다고 하자. 즉, 전송 도중 벡터 ${\displaystyle v\in \Sigma ^{n}}$의 ${\displaystyle n}$개의 성분 가운데 일부가 다른 값으로 바뀔 수 있다.

만약 문자열 ${\displaystyle v\in \Sigma ^{n}}$를 수신하였을 때, 다음과 같은 알고리즘을 사용하여 데이터를 교정한다고 하자.

• 만약 ${\displaystyle \min _{c\in C}\operatorname {d_{H}} (v,c)<d/2}$라면, ${\displaystyle v}$를 ${\displaystyle \operatorname {d_{H}} (v,f(c))<d/2}$인 유일한 원소 ${\displaystyle c\in \Sigma ^{k}}$로 교정한다.
• 만약 ${\displaystyle \min _{c\in C}\operatorname {d_{H}} (v,c)\geq d/2}$라면, 데이터의 교정은 실패한다.

이 경우,

• 만약 ${\displaystyle n}$개의 성분 가운데 ${\displaystyle \lceil d/2-1\rceil }$개 이하가 잘못되었다고 가정하면, 수신된 데이터를 오류 없이 교정할 수 있다.
• 만약 ${\displaystyle n}$개의 성분 가운데 ${\displaystyle d-1}$개 이하가 잘못되었다고 가정하면, 데이터의 송신 도중 오류가 발생하였는지 여부를 항상 확인할 수 있다. (그러나 이 오류를 항상 교정할 수 있지는 않다.)

블록 부호가 존재할 필요 조건

모든 ${\displaystyle [n,k,d]_{q}}$-블록 부호는 다음 두 조건을 만족시킨다.

${\displaystyle k\leq n+1-d}$ (싱글턴 상계 영어: Singleton bound)

${\displaystyle k\leq n-\log _{q}\left(\sum _{i=0}^{\lfloor (d-1)/2\rfloor }{\binom {n}{i}}(q-1)^{i}\right)}$ (해밍 상계 영어: Hamming bound)

싱글턴 상계를 포화시키는 (즉, ${\displaystyle k+d=n+1}$인) 블록 부호를 최대 거리 분리 부호(最大距離分離符號, 영어: maximum-distance-separable code, 약자 MDS 부호)라고 한다.

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

싱글턴 상계의 증명:

최소 거리가 ${\displaystyle d}$인 블록 부호 ${\displaystyle C\subseteq \Sigma ^{n}}$가 주어졌다고 하자. 그렇다면, 모든 부호어에서 처음 ${\displaystyle d-1}$개의 성분들을 삭제하여 블록 부호

${\displaystyle C'\subseteq \Sigma ^{n-d+1}}$

${\displaystyle C'=\{(s_{1},s_{2},\dotsc ,s_{n-d+1})\colon s\in C\}}$

를 정의할 수 있다. 따라서,

${\displaystyle |C|=|C'|\leq q^{n-d+1}}$

이다.

맥윌리엄스 부등식

보다 일반적으로, 임의의 결합 도식 ${\displaystyle (X,\partial )}$이 주어졌다고 하자. ${\displaystyle X}$의 복소수 계수 보스-메스너 대수는 복소수 반단순 대수이며, 그 최소 멱등원들을

${\displaystyle E_{0},E_{1},\dotsc ,E_{p}}$

라고 하자. 여기서 ${\displaystyle E_{0}=|X|^{-1}{\mathsf {J}}_{|X|\times |X|}}$이며, ${\displaystyle {\mathsf {J}}_{|X|\times |X|}}$는 모든 성분이 1인 행렬(아다마르 곱의 항등원)이다. 또한,

${\displaystyle E_{a}=\sum _{i}Q_{ai}D_{i}}$

라고 하자 (${\displaystyle D_{i}}$는 각 이항 관계 ${\displaystyle R_{i}\subseteq X^{2}}$의 인접 행렬).

이제, ${\displaystyle X}$ 속의 블록 부호 ${\displaystyle C\subseteq X}$가 주어졌다고 하고, 그 내부 분포

${\displaystyle \alpha _{i}={\frac {|C^{2}\cap R_{i}|}{|C|}}}$

를 생각하자. 그렇다면, 쌍대 내부 분포(雙對內部分布, 영어: dual inner distribution)는 다음과 같은 수열이다.

${\displaystyle \beta _{a}=\sum _{i}Q_{ai}\alpha _{i}}$

그렇다면, 다음과 같은 맥윌리엄스 부등식(MacWilliams不等式, 영어: MacWilliams inequality)이 성립한다.^{[6]:2484, Theorem 3}

${\displaystyle 0\leq \beta _{a}\leq |C|\qquad \forall a}$

${\displaystyle \sum _{a}\beta _{a}=|C|}$

증명:

각 ${\displaystyle E_{a}}$는 멱등원이므로, 그 고윳값은 0 또는 1이다. 따라서, 임의의 ${\displaystyle x,y\in X}$에 대하여, ${\displaystyle \langle x|y\rangle =\delta _{xy}}$이므로,

${\displaystyle 0\leq \langle x|E_{a}|y\rangle \leq 1\qquad \forall a}$

이다. (${\displaystyle \delta _{xy}}$는 크로네커 델타이다.)

이에 따라,

${\displaystyle {\begin{aligned}\beta _{a}&=\sum _{i}Q_{ai}\alpha _{i}\\&={\frac {1}{|C|}}\sum _{i}Q_{ai}|C^{2}\cap R_{i}|\\&={\frac {1}{|C|}}\sum _{x,y\in C}\sum _{i}Q_{ai}\langle x|D_{i}|y\rangle \\&={\frac {1}{|C|}}\sum _{x,y\in C}\langle x|E_{a}|y\rangle \end{aligned}}}$

이므로,

${\displaystyle 0\leq \beta _{a}\leq |C|}$

${\displaystyle \sum _{a}\beta _{a}={\frac {1}{|C|}}\sum _{x,y\in C}\langle x|\left(\sum _{a}E_{a}\right)|y\rangle ={\frac {1}{|C|}}\sum _{x,y\in C}\langle x|y\rangle =|C|}$

이다.

예

자명한 부호

자명한 예로, ${\displaystyle n=k}$이며 ${\displaystyle C}$가 순열인 경우를 생각하자. 이 경우 최소 거리는 1이다. 즉, 이 부호는 최고의 송신률 ${\displaystyle k/n=1}$을 갖지만, 아무런 오류를 교정하지 못한다.

마찬가지로, 예를 들어 어떤 임의의 ${\displaystyle \alpha \in \Sigma }$에 대하여

${\displaystyle C\colon \Sigma ^{k}\to \Sigma ^{n}}$

${\displaystyle C\colon (s_{1},s_{2},\dotsc ,s_{k})\mapsto (s_{1},s_{2},\dotsc ,s_{k},\underbrace {\alpha ,\alpha ,\dotsc ,\alpha } ^{n-k})}$

를 생각하자. 그 효율은 ${\displaystyle k/n}$이지만, 이 부호 역시 최소 거리가 1이므로, 아무런 오류를 교정하지 못한다.

반복 부호

임의의 알파벳 ${\displaystyle \Sigma }$ (${\displaystyle |\Sigma |=q}$) 및 양의 정수 ${\displaystyle k\in \mathbb {Z} ^{+}}$ 및 양의 정수 ${\displaystyle m}$에 대하여, 다음과 같은 ${\displaystyle [mk,k,m]_{q}}$-블록 부호를 얻을 수 있다.

${\displaystyle C\colon \Sigma ^{k}\to \Sigma ^{mk}}$

${\displaystyle 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})}$

이를 ${\displaystyle m}$중 반복 부호(${\displaystyle m}$重反復符號, 영어: ${\displaystyle m}$-tuple repetition code)라고 한다. 특히, ${\displaystyle (k,m,q)=(1,3,2)}$일 경우 이는 ${\displaystyle r=2}$ 이진 해밍 부호와 같다.

선형 부호

 이 부분의 본문은 선형 부호입니다.

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

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

역사

싱글턴 상계는 리처드 콜럼 싱글턴(영어: Richard Collom Singleton)이 1964년에 증명하였다.^[7] 해밍 상계는 리처드 해밍이 증명하였다.

같이 보기

• 채널 용량