Communication Signal Design Lab.

한국어

송홍엽 교수의 잡글

채널코딩 둘째이야기...

2003.11.12 20:29

송홍엽 조회 수:18179 추천:166

이전에 약속한대로 hamming distance에 대한 이야기를 자세히 해보고자합니다.
정의는 첫째 이야기에서 이미 설명하였습니다.

C = binary linear [n,k] code 라는 말의 뜻을 충분히 이해했을것으로 가정하겠습니다.
즉, 집합 C는 이진n-튜플 집합 (vector space of dimension n over binary field)의 k차원 부분공간이라는 뜻이죠. 더도 덜도 아닙니다... 이러한 C는 참으로 많이 있고, 저 아래에 그 정확한 수를 세는 공식을 물어보는게 아마도 online HW1이었던가요? 아뭏든 괸장히 많습니다. 특히, n이 증가하면 기하급수적으로 증가하지요. 이중에서 어떤게 좋은가하는 문제를 생각해보자는 겁니다. 좋다는건 무얼 뜻할까요? 채널에서 오류가 발생해도 이를 알아챌수(error detection)있어야 합니다. 심지어 유일한 방향으로 수정가능(error correction)할수있다면 더욱 좋겠지요. 그래서 이러한 방향으로 좋다는 뜻을 설정하겠습니다.

예를 다시 들겠습니다. n=5, k=4의 경우를 생각합시다.
결국 5-tuple 32개 중에서 16개를 선택하는 문제입니다. 그런데 이 중에는 다음과 같은 16개도 있습니다. 즉,
4-tuple 16개 각각에 1의 숫자를 세어서 1의 숫자가 짝수면 0을, 홀수면 1을 마지막 5번째 비트로 붙여서 5-tuple 16개를 만드는겁니다. 이렇게 만든 5-tuple 16개는 (이 코드를 P4라고 부릅시다) 무슨 특성이 있을까요? 모든 word에 1의 갯수가 짝수입니다. 그러므로 만일, 채널에서 1비트 오류가 발생한다면 이는 그 word 안에서 1의 갯수를 홀수로 변화시키게 됩니다. 즉, 수신한 word가 codeword가 아니라는 결정적인 증거가 되는 셈입니다. 다시말해서 5개 비트위치 어디라도 단 1비트만의 오류가 발생한다면 이는 그 word 안의 1의 갯수를 짝수에서 홀수로 바꿉니다. 그러므로 이를 1-error-detecting code라고 합니다.

일반적으로 s-error-detecting code란 모든 m=1,2,3,...,s에 대해서 임의의 codeword에 어떤종류의 m-error가 발생하더라도 수신 word에 error가 있다는것을 판정할수있어야합니다. 예를 들어 2-error-detecting Code 에는 다음이 있습니다.

C3={000, 111}

이는 어떤종류의 1-error가 발생해도, 그리고 어떤종류의 2-error가 발생해도 수신결과는 000이나 111이 될수없음로 오류있음을 판정할수있습니다... 3-error는 어떠한가요? 000을 보내고 3-error가 발생하면 111을 수신하게 되는데 이때 수신기(decoder)는 오류없음이라고 판정할수밖에 없습니다. 왜냐면 111은 정당한 codeword이기때문입니다. - 이러한 오류를 undetected error라고 합니다...

정의: undetected error란 codeword를 또다른 codeword로 바꾸는 error입니다. (그 외의 모든 error는 detect가능합니다.)

주의: s-error-detecting이란 뜻은 s개 까지의 "모든종류"의 error도 detect 가능하다는 뜻입니다. "모든종류"란
위의 예에서 보면 1-error 세개 즉, 100, 010, 001, 그리고 2-error 세개 죽, 110, 101, 011을 뜻합니다.

또 다른 예를 생각합시다.
C4={0000, 1111}

이는 3-error-detecting code 입니다. 3개까지 어떠한 종류의 error가 발생해도 error발생사실을 들키고말기 때문입니다.

자, 이제 C3와 C4의 "최소해밍거리(minimum hamming distance)"에 대해서 생각해봅시다.
이 두 코드는 모두가 코드워드 오직 2개만을 포함하고있기 때문에 이 두개의 코드워드간의 해밍거리가 이 코드의 최소해밍거리가 됩니다. 놀랍게도 C3의 두개의 코드워드의 해밍거리는 3이고 C4에서는 4입니다. 만일 이렇게 반복하는 코드워드를 만든다면, 그리고 n번 반복한다면 (n-1)-error-detecting code가 된다는것을 쉽게 알수있습니다. 그 이유는 최소해밍거리가 n이기 때문입니다. codeword의 수가 좀 더 많은 예를 들까요 ? 이를 P2라고 부릅시다. P2는 길이가 3이고 k=2이며, 다음과 같은 codeword 4개를 포함합니다.

P2={
000
011
101
110
}
편의상 위의 4개의 codeword를 각각 a,b,c,d가라고 부릅시다. 그리고 이들의 모든 가능한 pair의 해밍거리를 조사합시다.

(a,b): 2
(a,c): 2
(a,d): 2
(b,c): 2
(b,d): 2
(c,d): 2

놀랍게도 모두 같으며, 최소거리는 2입니다. 자, a,b,c,d어느것이라도 1-error가 발생하여 한 codeword를 다른 codeword로 바꿀수있을까요? 없습니다. 그래서 이 P2는 1-error-detecting code입니다.codeword b와 c를 생각합시다.
011에서 101로 바뀌려면 error-pattern (혹은 오류벡터) 110 이 더해져야합니다. 즉 110이라는 double error 가 발생해야하는것입니다. 이 error pattern은 이 코드의 undetectable error입니다.

만일 100이라는 1-error가 발생하여 코드워드 011가 111로 바뀌어 수신되었다고 합시다. 일단 error는 detect됩니다. 왜냐면 1의 갯수가 홀수이므로. 다시말해서 수신된 워드가 codeword가 아니므로..
수신기는 "도데체 무얼보내서 이걸 받았을까?"하는 생각하는게 당연합니다. 그런데 codeword중 하나를 보낸건 확실합니다.그러면 각각의 경우를 따져봅시다. a를 보냈다면 000을 보내서 111을 받은것이므로 3-error가 발생한 것입니다. 상당히 희박한 확률이겠지만 완전히 불가능하다고는 못합니다. b,c,d의 경우는 각각 1-error가 발생한것이라고 추측할수있습니다. 3-error보다는 훨씬더 발생빈도가 높은 (훨씬 더 일어났음직한) 상황이라고 할수있습니다. 그런데 이 세가지 모두가 다 동일한 확률값을 가집니다. 그러므로 어느쪽으로 유일하게 결정을 내리기가 불가능합니다. 왜 그런일이 벌어질까요? 이 코드의 최소해밍거리가 겨우 2이기 때문입니다. 즉 b와 c의 거리가 바로 이 2인데 b에서 1-error가 발생하여 b와 c사이에 거리 1만큼 떨어진곳에 위치한 워드 111을 수신한것입니다. 수신기는 이 111이 011을 보내고 1-error 100이 발생한것인지
101을 보내고 1-error 010이 발생한 것인지 더 기우는 방향이 없다는 뜻입니다.

1-error-correcting code를 만들기 위해서는 그 코드의 최소해밍거리가 적어도 3은 되어야 합니다. 다음의 에를 생각합시다.

D={
00000
00111
11100
11011
}
최소해밍거리가 보이나요? 3입니다. 실제로 모든 pair의 해밍거리를 조사하면 다음과 같습니다.
a,b: 3
a,c: 3
a,d: 4
b,c: 4
b,d: 3
c,d: 3
즉, 해밍거리는 오직 3 혹은 4이고 이중에 최소는 3입니다. 이제 최소거리 3인 두개의 codeword c와 d를 생각합시다. 최소해밍거리가 3이라는 뜻은 이 두개의 코드워드 c에서도 그리고 d에서도 d혹은 c를 제외하곤 더 가까이 있는 코드워드는 없다는 뜻이기도 합니다. 즉

c d
11100 <-------------------------------거리 3 ----------------------------> 11011

이제 c에서 출발하여 d까지 가려면 어떤 코드워드 들을 거쳐가게 되는지 알아봅시다.

11100 ----->11101 -------> 11111 -----> 11011

만일 11100을 보내고 11101을 받았다면 우리는 다음과 같은 상항을 따져야합니다.
11100을 보내고 00001이라는 오류가 발생하여 11101를 수신한건지 아니면
11011을 보내고 00110이라는 오류가 발생하여 11101를 수신한건지를 저울질 해야합니다.
오직 차이는, 첫째 상황은 1-error를 판정하여 수정하는 것이고,
둘째 상황은 2-error를 판정하여 수정하는 것입니다. 어떤것으로 추측하는게 당연할까요?
일어났음직한 그리고 훨씬 더 그럴듯한 결정은 무엇일까요? 그것은 1의 갯수가 가장 적은경우로 가야한다는 것입니다.
이를 "최단거리복호"라고 합니다.

이제 각각의 codword로 부터 1-error가 만들어낼수있는 5-tuple을 적어봅시다.

00000 00111 11100 11011
10000 10111 01100 01011
01000 01111 10100 10011
00100 00011 11000 11111
00010 00101 11110 11001
00001 00110 11101 11010

위의 표는 맨 윗줄에 코드워드 4개를 적되 첫째로 00000 을 적은것입니다. 그 다음줄부터는 1-error 5개를 순서대로 맨 왼쪽에 적고 이러한 error pattern이 발생한경우 코드워드가 어떻게 변화되서 수신되는지를 표시한것입니다. 예를 들어
00111을 보내고 10000 오류가 발생하면 10111을 수신한다는 뜻입니다.

이어서 다음에 다시하죠...^^





--------------------------------------------------------------------------------
오현영: 아아.. 해밍코드방법도 ML Dicision의 원리이군요... 자세히 예를 들어주시니 이해하기 훨씬 쉬운것 같습니다^^;
아 그리고 해밍거리가 홀수로만 되게하면 디시젼할 때 긴가민가하는 상황이 안 일어나는데요... 해밍 거리가 홀수인 찾아보려고 하는데 n하고 k의 차이가 쫌 나야지 찾아 지네요...
결국 에러정정의 확률을 높이려면 비트의 낭비는 감수할 수 없는 상황인가요...; -[10/29-17:03]-

--------------------------------------------------------------------------------
송홍엽: 오호라! 아직 ML decision이야기는 안했지만 그쪽으로 끌고가려는 낌새를 눈치 챘네.... 역쉬 우리 수강생이야...ㅎㅎㅎ -[10/29-20:34]-

--------------------------------------------------------------------------------
송홍엽: 에러정정확률이 아니고 에러정정능력(error correcting capacity)이라고 하지... 그걸 높이려면 비트의 낭비는 감수해야지... 얼마나 적게 낭비하는냐가 관건... -[10/29-23:36]-

--------------------------------------------------------------------------------
오현영: 헛 제 질문에 오타가 많았었군요 ^^; 문득 1년 전에 정보처리산업기사 시험 중에 해밍코드에 대해 무작정 외웠던 일이 떠오르네요...이제 대충 이해할 것 같습니다^^ -[10/30-00:51]-

--------------------------------------------------------------------------------
송홍엽: 해밍코드와 해밍거리는 전혀 다른 이야기야... 모든 코드가 다 해밍코드인것도 아니고 거리의 종류에 해밍거리만 있는것도 아니고... -[10/30-13:50]-

--------------------------------------------------------------------------------
오현영: 아 그렇군요~~ 앞으로 나올 얘기들도 기대됩니다^^; -[10/31-02:35]-

--------------------------------------------------------------------------------
송홍엽: 앞으로 할 이야기를 생각하니 부담되네... -[11/02-19:08]-



61.98.17.57 조지현: 근데 1bit짜리로 한거는.. 패리티 비트말하는 건가요? -[11/12-22:09]-

165.132.59.119 Hong-Yeop Song: 질문내용을 이해하기 힘들구나... 다시 정확히 해볼래?? -[11/13-08:46]-

61.98.17.57 조지현: 아.. 1-error-detecting code 라는 것이, even 혹은 odd parity 랑 같은 개념인것 같아서 질문드렸어요. 보통 ASCII 7bit 에 parity 1bit 붙여서 전송하지 않나요? -[11/13-11:32]-

165.132.59.119 Hong-Yeop Song: 그렇게 하면 1-error-detecting code를 만들수 있지.... -[11/15-09:16]-