블록 부호

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

 정의 
 해밍 결합 도식 속의 블록 부호 
블록 부호 는 다음과 같은 데이터로 구성된다.
 유한 집합 . 이를 알파벳()이라고 한다.
 양의 정수 . 이를 블록 길이()라고 하고, 의 원소를 블록()이라고 한다.
 부분 집합 . 의 원소인 블록을 부호어(符號語, )라고 한다.

블록 부호 의 전송률(電送率, )은

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

 위에 해밍 거리

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

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

 일반 결합 도식 속의 블록 부호 
위 정의는 결합 도식의 개념을 통해 일반화된다.

구체적으로, 다음이 주어졌다고 하자.
 결합 도식 
 의 부분 집합 
이 경우, 의 부분 집합 가 다음 조건을 만족시킬 경우, -블록 부호()라고 한다.
 임의의 에 대하여, 
 속의 블록 부호란 -블록 부호를 뜻한다.

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

결합 도식  속의 블록 부호 에 대하여,
 의 원소를 블록이라고 한다.
 의 원소를 부호어라고 한다.
 의 전송률은 이다. 이는 인 실수이다.
 의 이항 관계가 라고 할 때, 의 내부 분포(內部分布, )는 다음과 같은 유리수열이다.

특히,

가 성립한다.

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

를 정의할 수 있다.

 성질 
 블록 부호를 사용한 데이터의 전송 
-블록 부호 이 주어졌다고 하고, 편의상 가 정수라고 하자. 이 경우, 임의의 전단사 함수

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

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

만약 문자열 를 수신하였을 때, 다음과 같은 알고리즘을 사용하여 데이터를 교정한다고 하자.
 만약 라면, 를 인 유일한 원소 로 교정한다.
 만약 라면, 데이터의 교정은 실패한다.
이 경우,
 만약 개의 성분 가운데 개 이하가 잘못되었다고 가정하면, 수신된 데이터를 오류 없이 교정할 수 있다.
 만약 개의 성분 가운데 개 이하가 잘못되었다고 가정하면, 데이터의 송신 도중 오류가 발생하였는지 여부를 항상 확인할 수 있다. (그러나 이 오류를 항상 교정할 수 있지는 않다.)

 블록 부호가 존재할 필요 조건 
모든 -블록 부호는 다음 두 조건을 만족시킨다.
 (싱글턴 상계 )
 (해밍 상계 )

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

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

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

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

이다.

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

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

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

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

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

그렇다면, 다음과 같은 맥윌리엄스 부등식(MacWilliams不等式, )이 성립한다.

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

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

이에 따라,

이므로,

이다.

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

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

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

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

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

 선형 부호 

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

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

 역사 
싱글턴 상계는 리처드 콜럼 싱글턴()이 1964년에 증명하였다. 해밍 상계는 리처드 해밍이 증명하였다.

 같이 보기 
 채널 용량
 각주 

 외부 링크 







분류:부호 이론