블록 부호

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

수학컴퓨터 과학에서, 블록 부호(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. doi:10.1007/978-3-642-58575-3. ISBN 978-3-540-64133-9. ISSN 0072-5285. Zbl 0936.94014. 
  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. doi:10.1007/3-540-30593-9. ISBN 978-3-540-26136-0. ISSN 1439-7382. 
  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. doi:10.1109/18.720545. ISSN 0018-9448. 
  7. 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. 

외부 링크[편집]