블록 부호

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

정의

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

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

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

블록 부호 $(\mathrm{\Sigma },n,C)$의 전송률(電送率, 틀:Llang)은

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

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

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

${\mathrm{d}}_{\mathrm{H}}(s,t)=|\{i\in \{1,\dots ,n\}:s_i\ne t_i\}|$

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

$d=\underset{a,b\in {\mathrm{\Sigma }}^k,a\ne b}{\min }{\mathrm{d}}_{\mathrm{H}}(C(a),C(b))$

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

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

위 정의는 결합 도식의 개념을 통해 일반화된다.틀:Rp

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

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

이 경우, $X$의 부분 집합 $C\subseteq X$가 다음 조건을 만족시킬 경우, $E$-블록 부호(틀:Llang)라고 한다.틀:Rp

• 임의의 $x,y\in C$에 대하여, $\partial (x,y)\in ̸E$

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

만약 $X={\mathrm{\Sigma }}^n$이 $\mathrm{\Sigma }$ 위의 $n$차원 해밍 결합 도식일 경우, $\partial ={\mathrm{d}}_{\mathrm{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$의 내부 분포(內部分布, 틀:Llang)는 다음과 같은 유리수열이다.틀:Rp

  ${\alpha }_i=\frac{|C^2\cap R_i|}{|C|}$

특히,

$\sum _i{\alpha }_i=|C|$

가 성립한다.

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

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

를 정의할 수 있다.

성질

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

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

$f:{\mathrm{\Sigma }}^k\to C\subseteq {\mathrm{\Sigma }}^c$

를 고르자. 이를 부호화 함수(符號化函數, 틀:Llang)라고 한다.

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

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

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

이 경우,

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

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

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

$k\le n+1-d$ (싱글턴 상계 틀:Llang)

$k\le n-{\log }_q(\sum _{i=0}^{\lfloor (d-1)/2\rfloor }(\genfrac{}{}{0ex}{}{n}{i})(q-1{)}^i)$ (해밍 상계 틀:Llang)

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

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

싱글턴 상계의 증명:

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

$C^{\prime }\subseteq {\mathrm{\Sigma }}^{n-d+1}$

$C^{\prime }=\{(s_1,s_2,\dots ,s_{n-d+1}):s\in C\}$

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

$|C|=|C^{\prime }|\le q^{n-d+1}$

이다.

맥윌리엄스 부등식

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

$E_0,E_1,\dots ,E_p$

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

$E_a=\sum _i{Q}_{ai}{D}_i$

라고 하자 ($D_i$는 각 이항 관계 $R_i\subseteq X^2$의 인접 행렬).

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

${\alpha }_i=\frac{|C^2\cap R_i|}{|C|}$

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

${\beta }_a=\sum _i{Q}_{ai}{\alpha }_i$

그렇다면, 다음과 같은 맥윌리엄스 부등식(MacWilliams不等式, 틀:Llang)이 성립한다.틀:Rp

$0\le {\beta }_a\le |C|\mathrm{\forall }a$

$\sum _a{\beta }_a=|C|$

증명:

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

$0\le ⟨x|E_a|y⟩\le 1\mathrm{\forall }a$

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

이에 따라,

$\begin{array}{cc}{\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}⟨x|D_i|y⟩\\ & =\frac{1}{|C|}\sum _{x,y\in C}⟨x|E_a|y⟩\end{array}$

이므로,

$0\le {\beta }_a\le |C|$

$\sum _a{\beta }_a=\frac{1}{|C|}\sum _{x,y\in C}⟨x|\left(\sum _a{E}_a\right)|y⟩=\frac{1}{|C|}\sum _{x,y\in C}⟨x|y⟩=|C|$

이다.

예

자명한 부호

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

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

$C:{\mathrm{\Sigma }}^k\to {\mathrm{\Sigma }}^n$

$C:(s_1,s_2,\dots ,s_k)\mapsto (s_1,s_2,\dots ,s_k,{\underbrace{\alpha ,\alpha ,\dots ,\alpha }}^{n-k})$

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

반복 부호

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

$C:{\mathrm{\Sigma }}^k\to {\mathrm{\Sigma }}^{mk}$

$C:(s_1,s_2,\dots ,s_k)\mapsto (\underset{m}{\underbrace{s_1,\dots ,s_1}},\underset{m}{\underbrace{s_2,\dots ,s_2}},\dots ,\underset{m}{\underbrace{s_k,\dots ,s_k}})$

이를 $m$중 반복 부호($m$重反復符號, 틀:Llang)라고 한다. 특히, $(k,m,q)=(1,3,2)$일 경우 이는 $r=2$ 이진 해밍 부호와 같다.

선형 부호

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

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

역사

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

같이 보기

• 채널 용량

외부 링크

• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:Nlab
• 틀:웹 인용
• 틀:웹 인용