수학 과 컴퓨터 과학 에서 블록 부호 (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} 이며, 마찬가지로 1 이하의 양의 유리수 이다.
Σ 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} -block code)라고 한다.[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|}} 는 모든 성분이 1인 행렬(아다마르 곱 의 항등원)이다. 또한,
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} 이지만, 이 부호 역시 최소 거리가 1이므로, 아무런 오류를 교정하지 못한다.
반복 부호 임의의 알파벳 Σ {\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} -tuple repetition code)라고 한다. 특히, ( 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] 해밍 상계는 리처드 해밍 이 증명하였다.
같이 보기
각주
외부 링크