주 메뉴 열기

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

정의편집

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

블록 부호  는 다음과 같은 데이터로 구성된다.

  • 유한 집합  . 이를 알파벳(영어: alphabet)이라고 한다.
  • 양의 정수  . 이를 블록 길이(영어: block length)라고 하고,  의 원소를 블록(영어: block)이라고 한다.
  • 부분 집합  .  의 원소인 블록을 부호어(符號語, 영어: codeword)라고 한다.

블록 부호  전송률(電送率, 영어: rate)은

 

이며, 항상  이다. 블록 부호  상대 길이(相對-, 영어: relative distance)는 유리수  이며, 마찬가지로 1 이하의 양의 유리수이다.

  위에 해밍 거리

 

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

 

최소 거리가  인 블록 부호  는 흔히  -블록 부호라고 불린다.

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

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

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

  • 결합 도식  
  •  부분 집합  

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

  • 임의의  에 대하여,  

  속의 블록 부호 -블록 부호를 뜻한다.

만약    위의  차원 해밍 결합 도식일 경우,  해밍 거리가 되며, 이 경우 위의 기초적 정의로 귀결된다.

결합 도식   속의 블록 부호  에 대하여,

  •  의 원소를 블록이라고 한다.
  •  의 원소를 부호어라고 한다.
  •  전송률 이다. 이는  인 실수이다.
  •  이항 관계 라고 할 때,  내부 분포(內部分布, 영어: inner distribution)는 다음과 같은 유리수열이다.[6]:2483, Definition 4
     

특히,

 

가 성립한다.

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

 

를 정의할 수 있다.

성질편집

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

 -블록 부호  이 주어졌다고 하고, 편의상  가 정수라고 하자. 이 경우, 임의의 전단사 함수

 

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

이제,  의 한 원소를 노이즈가 있는 채널로 전송한다고 하자. 즉, 전송 도중 벡터   개의 성분 가운데 일부가 다른 값으로 바뀔 수 있다.

만약 문자열  를 수신하였을 때, 다음과 같은 알고리즘을 사용하여 데이터를 교정한다고 하자.

  • 만약  라면,   인 유일한 원소  로 교정한다.
  • 만약  라면, 데이터의 교정은 실패한다.

이 경우,

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

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

모든  -블록 부호는 다음 두 조건을 만족시킨다.

  (싱글턴 상계 영어: Singleton bound)
  (해밍 상계 영어: Hamming bound)

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

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

싱글턴 상계의 증명:

최소 거리가  인 블록 부호  가 주어졌다고 하자. 그렇다면, 모든 부호어에서 처음  개의 성분들을 삭제하여 블록 부호

 
 

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

 

이다.

맥윌리엄스 부등식편집

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

 

라고 하자. 여기서  이며,  는 모든 성분이 1인 행렬(아다마르 곱의 항등원)이다. 또한,

 

라고 하자 ( 는 각 이항 관계  의 인접 행렬).

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

 

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

 

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

 
 

증명:

 멱등원이므로, 그 고윳값은 0 또는 1이다. 따라서, 임의의  에 대하여,  이므로,

 

이다. ( 크로네커 델타이다.)

이에 따라,

 

이므로,

 
 

이다.

편집

자명한 부호편집

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

마찬가지로, 예를 들어 어떤 임의의  에 대하여

 
 

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

반복 부호편집

임의의 알파벳   ( ) 및 양의 정수   및 양의 정수  에 대하여, 다음과 같은  -블록 부호를 얻을 수 있다.

 
 

이를  중 반복 부호( 重反復符號, 영어:  -tuple repetition code)라고 한다. 특히,  일 경우 이는   이진 해밍 부호와 같다.

선형 부호편집

선형 부호의 경우,  유한체이며,   -선형 변환이다.

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

역사편집

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

참고 문헌편집

  1. van Lint, Jacobus Hendricus (1999). 《Introduction to coding theory》. Graduate Texts in Mathematics (영어) 86 3판. Springer-Verlag. ISBN 978-3-540-64133-9. ISSN 0072-5285. Zbl 0936.94014. doi:10.1007/978-3-642-58575-3. 
  2. 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. 
  3. Huffman, W. Cary; Pless, Vera (2003). 《Fundamentals of error-correcting codes》 (영어). Cambridge University Press. ISBN 978-0-521-78280-7. 
  4. Lin, S.; Costello, Daniel J. Jr. (2005). 《Error control coding: fundamentals and applications》 (영어) 2판. Prentice-Hall. ISBN 978-0-13-042672-7. 
  5. Zieschang, Paul-Hermann (2005). 《Theory of association schemes》. Springer Monographs in Mathematics (영어). Springer-Verlag. ISBN 978-3-540-26136-0. ISSN 1439-7382. doi:10.1007/3-540-30593-9. 
  6. 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. ISSN 0018-9448. doi:10.1109/18.720545. 
  7. Singleton, Richard Collom (1964). “Maximum distance q-nary codes”. 《Institute of Electrical and Electronics Engineers Transactions on Information Theory》 (영어) 10 (2): 116–118. ISSN 0018-9448. doi:10.1109/TIT.1964.1053661. 

외부 링크편집