블록 부호 문서 원본 보기

{{위키데이터 속성 추적}}
[[수학]]과 [[컴퓨터 과학]]에서 '''블록 부호'''(block符號, {{llang|en|block code|블록 코드}})는 데이터를 중복해서 “블록”으로 부호화하되, 각 [[비트 (단위)|비트]] 또는 블록의 성분이 전송 과정에서 노이즈를 겪어 바뀌는 것을 일부 경우 교정할 수 있게 하는 부호화 체계이다.<ref>{{서적 인용|이름=Jacobus Hendricus|성=van Lint|날짜=1999|제목=Introduction to coding theory|총서=Graduate Texts in Mathematics|권=86|issn=0072-5285|판=3|출판사=Springer-Verlag|isbn=978-3-540-64133-9|doi=10.1007/978-3-642-58575-3|zbl=0936.94014|언어=en}}</ref><ref>{{서적 인용|이름=Florence Jessie|성=MacWilliams|이름2=Neil James Alexander|성2=Sloane|날짜=1977|제목=The theory of error-correcting codes|출판사=North-Holland|isbn=978-0-444-85193-2|총서=North-Holland Mathematical Library|권=16|url=https://www.elsevier.com/books/the-theory-of-error-correcting-codes/macwilliams/978-0-444-85193-2|zbl=369.94008|언어=en}}</ref><ref>{{서적 인용|이름=W. Cary|성=Huffman|이름2=Vera|성2=Pless|날짜=2003|제목=Fundamentals of error-correcting codes|출판사=Cambridge University Press|isbn=978-0-521-78280-7|url=http://www.cambridge.org/catalogue/catalogue.asp?isbn=0521782805|언어=en}}</ref><ref>{{서적 인용|이름=S.|성=Lin|이름2=Daniel J. Jr.|성2=Costello|날짜=2005|제목=Error control coding: fundamentals and applications|출판사=Prentice-Hall|isbn=978-0-13-042672-7|url=https://www.pearson.com/us/higher-education/program/Lin-Error-Control-Coding-2nd-Edition/PGM40742.html|판=2|언어=en}}</ref>

== 정의 ==
=== 해밍 결합 도식 속의 블록 부호 ===
'''블록 부호''' <math>(\Sigma,n,k,C)</math>는 다음과 같은 데이터로 구성된다.
* [[유한 집합]] <math>\Sigma</math>. 이를 '''알파벳'''({{llang|en|alphabet}})이라고 한다.
* 양의 정수 <math>n\in\mathbb Z^+</math>. 이를 '''블록 길이'''({{llang|en|block length}})라고 하고, <math>\Sigma^n</math>의 원소를 '''블록'''({{llang|en|block}})이라고 한다.
* [[부분 집합]] <math>C\colon \Sigma^k\to\Sigma^n</math>. <math>C</math>의 원소인 블록을 '''부호어'''(符號語, {{llang|en|codeword}})라고 한다.

블록 부호 <math>(\Sigma,n,C)</math>의 '''전송률'''(電送率, {{llang|en|rate}})은
:<math>R=\frac1n\log_{|\Sigma}/n</math>
이며, 항상 <Math>0\le R\le 1</math>이다. 블록 부호 <math>(\Sigma,n,C)</math>의 '''상대 길이'''(相對-, {{llang|en|relative distance}})는 [[유리수]] <math>\delta=d/n</math>이며, 마찬가지로 1 이하의 양의 [[유리수]]이다.

<math>\Sigma^n</math> 위에 [[해밍 거리]]
:<math>\operatorname{d_H}(s,t)=|\{i\in\{1,\dotsc,n\}\colon s_i\ne t_i\}|</math>
를 정의하면, 이는 [[거리 공간]]을 이룬다. 블록 부호 <math>(\Sigma,n,C)</math>의 '''최소 거리'''(最小距離, {{llang|en|minimum distance}})는 다음과 같다.
:<math>d=\min_{a,b\in\Sigma^k,\;a\ne b}\operatorname{d_H}(C(a),C(b))</math>

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

=== 일반 결합 도식 속의 블록 부호 ===
위 정의는 [[결합 도식]]의 개념을 통해 일반화된다.<ref>{{서적 인용| last=Zieschang | first=Paul-Hermann |  title=Theory of association schemes |  publisher=Springer-Verlag |  year=2005 |doi=10.1007/3-540-30593-9 | 총서=Springer Monographs in Mathematics|isbn=978-3-540-26136-0|issn=1439-7382|언어=en }}</ref><ref name="DL">{{저널 인용|doi=10.1109/18.720545|제목=Association schemes and coding theory|issn=0018-9448|저널= Institute of Electrical and Electronics Engineers Transactions on Information Theory|권=44|호=6|날짜=1998-10|이름=Philippe|성=Delsarte|이름2=Vladimir Iosifovich|성2=Levenshtein|저자링크2=블라디미르 레벤시테인|쪽= 2477–2504|언어=en}}</ref>{{rp|2483–2486, §Ⅲ}}

구체적으로, 다음이 주어졌다고 하자.
* [[결합 도식]] <math>(X,\partial\colon X^2\to D)</math>
* <math>D</math>의 [[부분 집합]] <math>E\subseteq D</math>
이 경우, <math>X</math>의 부분 집합 <math>C\subseteq X</math>가 다음 조건을 만족시킬 경우, '''<math>E</math>-블록 부호'''({{llang|en|<math>E</math>-block code}})라고 한다.<ref name="DL"/>{{rp|2483, Definition 5}}
* 임의의 <math>x,y\in C</math>에 대하여, <math>\partial(x,y)\not\in E</math>
<math>X</math> 속의 '''블록 부호'''란 <math>\varnothing</math>-블록 부호를 뜻한다.

만약 <math>X=\Sigma^n</math>이 <math>\Sigma</math> 위의 <math>n</math>차원 [[해밍 결합 도식]]일 경우, <math>\partial=\operatorname{d_H}</math>는 [[해밍 거리]]가 되며, 이 경우 위의 기초적 정의로 귀결된다.

[[결합 도식]] <math>X</math> 속의 블록 부호 <math>C\subseteq X</math>에 대하여,
* <math>X</math>의 원소를 '''블록'''이라고 한다.
* <math>C</math>의 원소를 '''부호어'''라고 한다.
* <math>C</math>의 '''전송률'''은 <math>R=\ln C/\ln X</math>이다. 이는 <math>0\le R\le 1</math>인 실수이다.
* <math>X</math>의 [[이항 관계]]가 <Math>(R_i\subseteq X^2)_{i\in I}</math>라고 할 때, <math>C</math>의 '''내부 분포'''(內部分布, {{llang|en|inner distribution}})는 다음과 같은 [[유리수]]열이다.<ref name="DL"/>{{rp|2483, Definition 4}}
*:<math>\alpha_i=\frac{|C^2\cap R_i|}{|C|}</math>
특히,
:<math>\sum_i\alpha_i=|C|</math>
가 성립한다.

만약 거리 함수의 [[공역]] <math>D</math>가 [[전순서 집합]]일 때, 마찬가지로 '''최소 거리'''
:<math>d=\min_{x,y\in C}\partial(x,y)</math>
를 정의할 수 있다.

== 성질 ==
=== 블록 부호를 사용한 데이터의 전송 ===
<math>[n,k,d]_q</math>-블록 부호 <math>C\subseteq\Sigma^n</math>이 주어졌다고 하고, 편의상 <math>k</math>가 정수라고 하자. 이 경우, 임의의 [[전단사 함수]]
:<math>f\colon\Sigma^k\to C\subseteq \Sigma^c</math>
를 고르자. 이를 '''부호화 함수'''(符號化函數, {{llang|en|coding function}})라고 한다.

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

만약 문자열 <math>v\in\Sigma^n</math>를 수신하였을 때, 다음과 같은 알고리즘을 사용하여 데이터를 교정한다고 하자.
* 만약 <math>\min_{c\in C}\operatorname{d_H}(v,c)<d/2</math>라면, <math>v</math>를 <math>\operatorname{d_H}(v,f(c))<d/2</math>인 유일한 원소 <math>c\in\Sigma^k</math>로 교정한다.
* 만약 <math>\min_{c\in C}\operatorname{d_H}(v,c)\ge d/2</math>라면, 데이터의 교정은 실패한다.
이 경우,
* 만약 <math>n</math>개의 성분 가운데 <math>\lceil d/2-1\rceil</math>개 이하가 잘못되었다고 가정하면, 수신된 데이터를 오류 없이 교정할 수 있다.
* 만약 <math>n</math>개의 성분 가운데 <math>d-1</math>개 이하가 잘못되었다고 가정하면, 데이터의 송신 도중 오류가 발생하였는지 여부를 항상 확인할 수 있다. (그러나 이 오류를 항상 교정할 수 있지는 않다.)

=== 블록 부호가 존재할 필요 조건 ===
모든 <math>[n,k,d]_q</math>-블록 부호는 다음 두 조건을 만족시킨다.
:<math>k\le n+1-d</math> ('''싱글턴 상계''' {{llang|en|Singleton bound}})
:<math>k\le n-\log_q\left(\sum_{i=0}^{\lfloor(d-1)/2\rfloor}\binom ni(q-1)^i\right)</math> ('''해밍 상계''' {{llang|en|Hamming bound}})

싱글턴 상계를 포화시키는 (즉, <math>k+d=n+1</math>인) 블록 부호를 '''최대 거리 분리 부호'''(最大距離分離符號, {{llang|en|maximum-distance-separable code}}, 약자 MDS 부호)라고 한다.

해밍 상계를 포화시키는 블록 부호를 '''완전 부호'''(完全符號, {{llang|en|perfect code}})라고 한다.

<div class="mw-collapsible mw-collapsed toccolours">
'''싱글턴 상계의 증명''':
<div class="mw-collapsible-content">
최소 거리가 <math>d</math>인 블록 부호 <math>C\subseteq\Sigma^n</math>가 주어졌다고 하자. 그렇다면, 모든 부호어에서 처음 <math>d-1</math>개의 성분들을 삭제하여 블록 부호
:<math>C'\subseteq\Sigma^{n-d+1}</math>
:<math>C'=\{(s_1,s_2,\dotsc,s_{n-d+1})\colon s\in C\}</math>
를 정의할 수 있다. 따라서,
:<math>|C|=|C'|\le q^{n-d+1}</math>
이다.
</div></div>

==== 맥윌리엄스 부등식 ====
보다 일반적으로, 임의의 [[결합 도식]] <math>(X,\partial)</math>이 주어졌다고 하자. <math>X</math>의 복소수 계수 보스-메스너 대수는 복소수 [[반단순 대수]]이며, 그 최소 [[멱등원]]들을
:<math>E_0,E_1,\dotsc,E_p</math>
라고 하자. 여기서 <math>E_0=|X|^{-1}\mathsf J_{|X|\times|X|}</math>이며, <Math>\mathsf J_{|X|\times|X|}</math>는 모든 성분이 1인 행렬([[아다마르 곱]]의 항등원)이다. 또한,
:<math>E_a=\sum_iQ_{ai}D_i</math>
라고 하자 (<math>D_i</math>는 각 [[이항 관계]] <math>R_i\subseteq X^2</math>의 인접 행렬).

이제, <math>X</math> 속의 블록 부호 <math>C\subseteq X</math>가 주어졌다고 하고, 그 내부 분포
:<math>\alpha_i=\frac{|C^2\cap R_i|}{|C|}</math>
를 생각하자. 그렇다면, '''쌍대 내부 분포'''(雙對內部分布, {{llang|en|dual inner distribution}})는 다음과 같은 수열이다.
:<math>\beta_a=\sum_iQ_{ai}\alpha_i</math>
그렇다면, 다음과 같은 '''맥윌리엄스 부등식'''(MacWilliams不等式, {{llang|en|MacWilliams inequality}})이 성립한다.<ref name="DL"/>{{rp|2484, Theorem 3}}
:<math>0\le\beta_a\le|C|\qquad\forall a</math>
:<math>\sum_a\beta_a=|C|</math>
<div class="mw-collapsible mw-collapsed toccolours">
'''증명:'''
<div class="mw-collapsible-content">
각 <math>E_a</math>는 [[멱등원]]이므로, 그 [[고윳값]]은 0 또는 1이다. 따라서, 임의의 <math>x,y\in X</math>에 대하여, <math>\langle x|y\rangle=\delta_{xy}</math>이므로,
:<math>0\le\langle x|E_a|y\rangle\le 1\qquad\forall a</math>
이다. (<math>\delta_{xy}</math>는 [[크로네커 델타]]이다.)

이에 따라,
:<math>\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}
</math>
이므로,
:<math>0\le\beta_a\le |C|</math>
:<math>\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|</math>
이다.
</div></div>

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

마찬가지로, 예를 들어 어떤 임의의 <math>\alpha\in\Sigma</math>에 대하여
:<math>C\colon\Sigma^k\to\Sigma^n</math>
:<math>C\colon (s_1,s_2,\dotsc,s_k)\mapsto (s_1,s_2,\dotsc,s_k,\underbrace{\alpha,\alpha,\dotsc,\alpha}^{n-k})</math>
를 생각하자. 그 효율은 <math>k/n</math>이지만, 이 부호 역시 최소 거리가 1이므로, 아무런 오류를 교정하지 못한다.

=== 반복 부호 ===
임의의 알파벳 <math>\Sigma</math> (<math>|\Sigma|=q</math>) 및 양의 정수 <math>k\in\mathbb Z^+</math> 및 양의 정수 <math>m</math>에 대하여, 다음과 같은 <math>[mk,k,m]_q</math>-블록 부호를 얻을 수 있다.
:<math>C\colon\Sigma^k\to\Sigma^{mk}</math>
:<math>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>
이를 '''<math>m</math>중 반복 부호'''(<math>m</math>重反復符號, {{llang|en|<math>m</math>-tuple repetition code}})라고 한다. 특히, <math>(k,m,q)=(1,3,2)</math>일 경우 이는 <math>r=2</math> [[이진 해밍 부호]]와 같다.

=== 선형 부호 ===
{{본문|선형 부호}}
'''[[선형 부호]]'''의 경우, <math>\Sigma</math>는 [[유한체]]이며, <math>C\colon\Sigma^k\to\Sigma^n</math>은 <math>\Sigma</math>-[[선형 변환]]이다.

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

== 역사 ==
싱글턴 상계는 리처드 콜럼 싱글턴({{llang|en|Richard Collom Singleton}})이 1964년에 증명하였다.<ref>{{저널 인용| first=Richard Collom |last=Singleton | title=Maximum distance ''q''-nary codes | journal=Institute of Electrical and Electronics Engineers Transactions on Information Theory | volume=10 | pages=116–118 | year=1964 | doi=10.1109/TIT.1964.1053661 | issue=2 | issn=0018-9448 | 언어=en }}</ref> 해밍 상계는 [[리처드 해밍]]이 증명하였다.

== 같이 보기 ==
* [[채널 용량]]
== 각주 ==
{{각주}}

== 외부 링크 ==
* {{매스월드|id=Error-CorrectingCode|title=Error-Correcting code}}
* {{매스월드|id=CodingTheory|title=Coding theory}}
* {{매스월드|id=PerfectCode|title=Perfect code}}
* {{nlab|id=coding theory|title=Coding theory}}
* {{웹 인용|url=http://www.ktword.co.kr/abbr_view.php?m_temp1=2608|제목=블록 부호, 블록 부호화, 블록 코딩, 블록 코드|웹사이트=정보통신기술용어해설|저자=차재복|날짜=2017-03-27|언어=ko}}
* {{웹 인용|url=http://ctl.sangji.ac.kr/common/downLoad.action?siteId=com&fileSeq=12777316|제목=정보 및 부호이론|날짜=2015|출판사=상지대학교 컴퓨터정보공학부|저자=성현경|언어=ko}}

[[분류:부호 이론]]