수학 과 컴퓨터 과학 에서 블록 부호 (block符號, 영어 : block code 블록 코드[* ] )는 데이터를 중복해서 “블록”으로 부호화하되, 각 비트 또는 블록의 성분이 전송 과정에서 노이즈를 겪어 바뀌는 것을 일부 경우 교정할 수 있게 하는 부호화 체계이다.[1] [2] [3] [4]
블록 부호
(
Σ
,
n
,
k
,
C
)
{\displaystyle (\Sigma ,n,k,C)}
유한 집합
Σ
{\displaystyle \Sigma }
알파벳 (영어 : alphabet )이라고 한다.양의 정수
n
∈
Z
+
{\displaystyle n\in \mathbb {Z} ^{+}}
블록 길이 (영어 : block length )라고 하고,
Σ
n
{\displaystyle \Sigma ^{n}}
블록 (영어 : block )이라고 한다.
부분 집합
C
:
Σ
k
→
Σ
n
{\displaystyle C\colon \Sigma ^{k}\to \Sigma ^{n}}
C
{\displaystyle C}
부호어 (符號語, 영어 : codeword )라고 한다.블록 부호
(
Σ
,
n
,
C
)
{\displaystyle (\Sigma ,n,C)}
전송률 (電送率, 영어 : rate )은
R
=
1
n
log
|
Σ
/
n
{\displaystyle R={\frac {1}{n}}\log _{|\Sigma }/n}
이며, 항상
0
≤
R
≤
1
{\displaystyle 0\leq R\leq 1}
(
Σ
,
n
,
C
)
{\displaystyle (\Sigma ,n,C)}
상대 길이 (相對-, 영어 : relative distance )는 유리수
δ
=
d
/
n
{\displaystyle \delta =d/n}
유리수 이다.
Σ
n
{\displaystyle \Sigma ^{n}}
해밍 거리
d
H
(
s
,
t
)
=
|
{
i
∈
{
1
,
…
,
n
}
:
s
i
≠
t
i
}
|
{\displaystyle \operatorname {d_{H}} (s,t)=|\{i\in \{1,\dotsc ,n\}\colon s_{i}\neq t_{i}\}|}
를 정의하면, 이는 거리 공간 을 이룬다. 블록 부호
(
Σ
,
n
,
C
)
{\displaystyle (\Sigma ,n,C)}
최소 거리 (最小距離, 영어 : minimum distance )는 다음과 같다.
d
=
min
a
,
b
∈
Σ
k
,
a
≠
b
d
H
(
C
(
a
)
,
C
(
b
)
)
{\displaystyle d=\min _{a,b\in \Sigma ^{k},\;a\neq b}\operatorname {d_{H}} (C(a),C(b))}
최소 거리가
d
{\displaystyle d}
(
Σ
,
n
,
C
)
{\displaystyle (\Sigma ,n,C)}
[
n
,
log
Σ
|
C
|
,
d
]
|
Σ
|
{\displaystyle [n,\log _{\Sigma }|C|,d]_{|\Sigma |}}
위 정의는 결합 도식 의 개념을 통해 일반화된다.[5] [6] :2483–2486, §Ⅲ
구체적으로, 다음이 주어졌다고 하자.
결합 도식
(
X
,
∂
:
X
2
→
D
)
{\displaystyle (X,\partial \colon X^{2}\to D)}
D
{\displaystyle D}
부분 집합
E
⊆
D
{\displaystyle E\subseteq D}
이 경우,
X
{\displaystyle X}
C
⊆
X
{\displaystyle C\subseteq X}
E
{\displaystyle E}
영어 :
E
{\displaystyle E}
[6] :2483, Definition 5
임의의
x
,
y
∈
C
{\displaystyle x,y\in C}
∂
(
x
,
y
)
∉
E
{\displaystyle \partial (x,y)\not \in E}
X
{\displaystyle X}
블록 부호 란
∅
{\displaystyle \varnothing }
만약
X
=
Σ
n
{\displaystyle X=\Sigma ^{n}}
Σ
{\displaystyle \Sigma }
n
{\displaystyle n}
해밍 결합 도식 일 경우,
∂
=
d
H
{\displaystyle \partial =\operatorname {d_{H}} }
해밍 거리 가 되며, 이 경우 위의 기초적 정의로 귀결된다.
결합 도식
X
{\displaystyle X}
C
⊆
X
{\displaystyle C\subseteq X}
X
{\displaystyle X}
블록 이라고 한다.
C
{\displaystyle C}
부호어 라고 한다.
C
{\displaystyle C}
전송률 은
R
=
ln
C
/
ln
X
{\displaystyle R=\ln C/\ln X}
0
≤
R
≤
1
{\displaystyle 0\leq R\leq 1}
X
{\displaystyle X}
이항 관계 가
(
R
i
⊆
X
2
)
i
∈
I
{\displaystyle (R_{i}\subseteq X^{2})_{i\in I}}
C
{\displaystyle C}
내부 분포 (內部分布, 영어 : inner distribution )는 다음과 같은 유리수 열이다.[6] :2483, Definition 4
α
i
=
|
C
2
∩
R
i
|
|
C
|
{\displaystyle \alpha _{i}={\frac {|C^{2}\cap R_{i}|}{|C|}}}
특히,
∑
i
α
i
=
|
C
|
{\displaystyle \sum _{i}\alpha _{i}=|C|}
가 성립한다.
만약 거리 함수의 공역
D
{\displaystyle D}
전순서 집합 일 때, 마찬가지로 최소 거리
d
=
min
x
,
y
∈
C
∂
(
x
,
y
)
{\displaystyle d=\min _{x,y\in C}\partial (x,y)}
를 정의할 수 있다.
[
n
,
k
,
d
]
q
{\displaystyle [n,k,d]_{q}}
C
⊆
Σ
n
{\displaystyle C\subseteq \Sigma ^{n}}
k
{\displaystyle k}
전단사 함수
f
:
Σ
k
→
C
⊆
Σ
c
{\displaystyle f\colon \Sigma ^{k}\to C\subseteq \Sigma ^{c}}
를 고르자. 이를 부호화 함수 (符號化函數, 영어 : coding function )라고 한다.
이제,
Σ
k
{\displaystyle \Sigma ^{k}}
v
∈
Σ
n
{\displaystyle v\in \Sigma ^{n}}
n
{\displaystyle n}
만약 문자열
v
∈
Σ
n
{\displaystyle v\in \Sigma ^{n}}
만약
min
c
∈
C
d
H
(
v
,
c
)
<
d
/
2
{\displaystyle \min _{c\in C}\operatorname {d_{H}} (v,c)<d/2}
v
{\displaystyle v}
d
H
(
v
,
f
(
c
)
)
<
d
/
2
{\displaystyle \operatorname {d_{H}} (v,f(c))<d/2}
c
∈
Σ
k
{\displaystyle c\in \Sigma ^{k}}
만약
min
c
∈
C
d
H
(
v
,
c
)
≥
d
/
2
{\displaystyle \min _{c\in C}\operatorname {d_{H}} (v,c)\geq d/2}
이 경우,
만약
n
{\displaystyle n}
⌈
d
/
2
−
1
⌉
{\displaystyle \lceil d/2-1\rceil }
만약
n
{\displaystyle n}
d
−
1
{\displaystyle d-1}
모든
[
n
,
k
,
d
]
q
{\displaystyle [n,k,d]_{q}}
k
≤
n
+
1
−
d
{\displaystyle k\leq n+1-d}
싱글턴 상계 영어 : Singleton bound )
k
≤
n
−
log
q
(
∑
i
=
0
⌊
(
d
−
1
)
/
2
⌋
(
n
i
)
(
q
−
1
)
i
)
{\displaystyle k\leq n-\log _{q}\left(\sum _{i=0}^{\lfloor (d-1)/2\rfloor }{\binom {n}{i}}(q-1)^{i}\right)}
해밍 상계 영어 : Hamming bound )싱글턴 상계를 포화시키는 (즉,
k
+
d
=
n
+
1
{\displaystyle k+d=n+1}
최대 거리 분리 부호 (最大距離分離符號, 영어 : maximum-distance-separable code , 약자 MDS 부호)라고 한다.
해밍 상계를 포화시키는 블록 부호를 완전 부호 (完全符號, 영어 : perfect code )라고 한다.
보다 일반적으로, 임의의 결합 도식
(
X
,
∂
)
{\displaystyle (X,\partial )}
X
{\displaystyle X}
반단순 대수 이며, 그 최소 멱등원 들을
E
0
,
E
1
,
…
,
E
p
{\displaystyle E_{0},E_{1},\dotsc ,E_{p}}
라고 하자. 여기서
E
0
=
|
X
|
−
1
J
|
X
|
×
|
X
|
{\displaystyle E_{0}=|X|^{-1}{\mathsf {J}}_{|X|\times |X|}}
J
|
X
|
×
|
X
|
{\displaystyle {\mathsf {J}}_{|X|\times |X|}}
아다마르 곱 의 항등원)이다. 또한,
E
a
=
∑
i
Q
a
i
D
i
{\displaystyle E_{a}=\sum _{i}Q_{ai}D_{i}}
라고 하자 (
D
i
{\displaystyle D_{i}}
이항 관계
R
i
⊆
X
2
{\displaystyle R_{i}\subseteq X^{2}}
이제,
X
{\displaystyle X}
C
⊆
X
{\displaystyle C\subseteq X}
α
i
=
|
C
2
∩
R
i
|
|
C
|
{\displaystyle \alpha _{i}={\frac {|C^{2}\cap R_{i}|}{|C|}}}
를 생각하자. 그렇다면, 쌍대 내부 분포 (雙對內部分布, 영어 : dual inner distribution )는 다음과 같은 수열이다.
β
a
=
∑
i
Q
a
i
α
i
{\displaystyle \beta _{a}=\sum _{i}Q_{ai}\alpha _{i}}
그렇다면, 다음과 같은 맥윌리엄스 부등식 (MacWilliams不等式, 영어 : MacWilliams inequality )이 성립한다.[6] :2484, Theorem 3
0
≤
β
a
≤
|
C
|
∀
a
{\displaystyle 0\leq \beta _{a}\leq |C|\qquad \forall a}
∑
a
β
a
=
|
C
|
{\displaystyle \sum _{a}\beta _{a}=|C|}
증명:
각
E
a
{\displaystyle E_{a}}
멱등원 이므로, 그 고윳값 은 0 또는 1이다. 따라서, 임의의
x
,
y
∈
X
{\displaystyle x,y\in X}
⟨
x
|
y
⟩
=
δ
x
y
{\displaystyle \langle x|y\rangle =\delta _{xy}}
0
≤
⟨
x
|
E
a
|
y
⟩
≤
1
∀
a
{\displaystyle 0\leq \langle x|E_{a}|y\rangle \leq 1\qquad \forall a}
이다. (
δ
x
y
{\displaystyle \delta _{xy}}
크로네커 델타 이다.)
이에 따라,
β
a
=
∑
i
Q
a
i
α
i
=
1
|
C
|
∑
i
Q
a
i
|
C
2
∩
R
i
|
=
1
|
C
|
∑
x
,
y
∈
C
∑
i
Q
a
i
⟨
x
|
D
i
|
y
⟩
=
1
|
C
|
∑
x
,
y
∈
C
⟨
x
|
E
a
|
y
⟩
{\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}}}
이므로,
0
≤
β
a
≤
|
C
|
{\displaystyle 0\leq \beta _{a}\leq |C|}
∑
a
β
a
=
1
|
C
|
∑
x
,
y
∈
C
⟨
x
|
(
∑
a
E
a
)
|
y
⟩
=
1
|
C
|
∑
x
,
y
∈
C
⟨
x
|
y
⟩
=
|
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|}
이다.
자명한 예로,
n
=
k
{\displaystyle n=k}
C
{\displaystyle C}
순열 인 경우를 생각하자. 이 경우 최소 거리는 1이다. 즉, 이 부호는 최고의 송신률
k
/
n
=
1
{\displaystyle k/n=1}
마찬가지로, 예를 들어 어떤 임의의
α
∈
Σ
{\displaystyle \alpha \in \Sigma }
C
:
Σ
k
→
Σ
n
{\displaystyle C\colon \Sigma ^{k}\to \Sigma ^{n}}
C
:
(
s
1
,
s
2
,
…
,
s
k
)
↦
(
s
1
,
s
2
,
…
,
s
k
,
α
,
α
,
…
,
α
⏟
n
−
k
)
{\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})}
를 생각하자. 그 효율은
k
/
n
{\displaystyle k/n}
임의의 알파벳
Σ
{\displaystyle \Sigma }
|
Σ
|
=
q
{\displaystyle |\Sigma |=q}
k
∈
Z
+
{\displaystyle k\in \mathbb {Z} ^{+}}
m
{\displaystyle m}
[
m
k
,
k
,
m
]
q
{\displaystyle [mk,k,m]_{q}}
C
:
Σ
k
→
Σ
m
k
{\displaystyle C\colon \Sigma ^{k}\to \Sigma ^{mk}}
C
:
(
s
1
,
s
2
,
…
,
s
k
)
↦
(
s
1
,
…
,
s
1
⏟
m
,
s
2
,
…
,
s
2
⏟
m
,
…
,
s
k
,
…
,
s
k
⏟
m
)
{\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})}
이를
m
{\displaystyle m}
m
{\displaystyle m}
영어 :
m
{\displaystyle m}
(
k
,
m
,
q
)
=
(
1
,
3
,
2
)
{\displaystyle (k,m,q)=(1,3,2)}
r
=
2
{\displaystyle r=2}
이진 해밍 부호 와 같다.
선형 부호
Σ
{\displaystyle \Sigma }
유한체 이며,
C
:
Σ
k
→
Σ
n
{\displaystyle C\colon \Sigma ^{k}\to \Sigma ^{n}}
Σ
{\displaystyle \Sigma }
선형 변환 이다.
선형 부호의 예로는 해밍 부호 나 이진 골레 부호 가 있다.
싱글턴 상계는 리처드 콜럼 싱글턴(영어 : Richard Collom Singleton )이 1964년에 증명하였다.[7] 리처드 해밍 이 증명하였다.
↑ van Lint, Jacobus Hendricus (1999). 《Introduction to coding theory》. Graduate Texts in Mathematics (영어) 86 3판. Springer-Verlag. doi :10.1007/978-3-642-58575-3 . ISBN 978-3-540-64133-9 ISSN 0072-5285 . Zbl 0936.94014 . ↑ MacWilliams, Florence Jessie; Sloane, Neil James Alexander (1977). 《The theory of error-correcting codes》 . North-Holland Mathematical Library (영어) 16 . North-Holland. ISBN 978-0-444-85193-2 Zbl 369.94008 . ↑ Huffman, W. Cary; Pless, Vera (2003). 《Fundamentals of error-correcting codes》 (영어). Cambridge University Press. ISBN 978-0-521-78280-7 ↑ Lin, S.; Costello, Daniel J. Jr. (2005). 《Error control coding: fundamentals and applications》 (영어) 2판. Prentice-Hall. ISBN 978-0-13-042672-7 ↑ Zieschang, Paul-Hermann (2005). 《Theory of association schemes》. Springer Monographs in Mathematics (영어). Springer-Verlag. doi :10.1007/3-540-30593-9 . ISBN 978-3-540-26136-0 ISSN 1439-7382 . ↑ 가 나 다 라 Delsarte, Philippe; Levenshtein, Vladimir Iosifovich (1998년 10월). “Association schemes and coding theory”. 《Institute of Electrical and Electronics Engineers Transactions on Information Theory》 (영어) 44 (6): 2477–2504. doi :10.1109/18.720545 . ISSN 0018-9448 . ↑ Singleton, Richard Collom (1964). “Maximum distance q -nary codes”. 《Institute of Electrical and Electronics Engineers Transactions on Information Theory》 (영어) 10 (2): 116–118. doi :10.1109/TIT.1964.1053661 . ISSN 0018-9448 .
![{\displaystyle [n,\log _{\Sigma }|C|,d]_{|\Sigma |}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1682ea6945ed0b24aa18337cbdc5e5fd9d8c8246)
![{\displaystyle [n,k,d]_{q}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5eef76e1d6b74cc535236a6249e75afeea540ee3)
![{\displaystyle [mk,k,m]_{q}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a238ccdd4845c2864a975969090d8e0f5cc72ef9)
이 부분의 본문은 선형 부호입니다.