Communication Signal Design Lab.

한국어

송홍엽 교수의 잡글

채널코딩에 관한 첫번째 이야기

2003.10.13 08:12

송홍엽 조회 수:4822 추천:141

오류정정부호는 디지털 모뎀의 성능을 개선시키는 최후의 수단입니다.
이 방식은 아날로그 모뎀에는 원천적으로 사용이 불가능합니다.
그런 관점에서 디지털통신방식의 중요한 장점이라고 할수있지요.
이론적으로 할수있는 많은 중요한 것들은 다 생략하기로하고
여기에서는 과연 어떻게 오류를 찾아내고 이를 정정할수있는지에 대한 설명을 하도록 하겠습니다.
이는 우리가 문장을 읽으면서 오타를 찾아낼수도 있고,
어떤 경우에는 찾아낸 오타를 수정하여 원래의 글자를 회복가능할 때도 있는데,
다음과 같은 비유가 참으로 적절하다는 생각입니다.

다음과 같은 글을 읽어 봅시다.

"서운특별시 서대문구 신촌동 135번지 연세대학교 전지공학과의 학생들은 ..."

여러곳에서 무언가 이상하다고 느낍니까? 그 이상하다고 느끼는 부분에서 여러분은 오류를 검출(Error Detection)한것입니다.
하나씩 찾아봅시다. 첫째는 "서운특별시"입니다.
이 부분은 주소를 말하고있는데 우리나라에 서운특별시는 없다는게 명백합니다.
즉각적으로 여러분은 "서울특별시"를 잘못 기록했구나 라고 오류 검출 즉시 오류를 수정할수있습니다.
꽤 자신있는 오류정정입니다.

둘째는 "전지공학과"입니다. 그런데 이 부분은 잘못되었다는건 확신할수있어도
(왜냐면 이러한 이름의 학과는 없기 때문이죠)
전자공학과에서 한획이 지워진건지, 전기공학과에서 한획이 덧붙여진건지 모호합니다.
둘중 하나인건 확실한데 양쪽이 모두 다 "그럴듯"하다는 뜻입니다. unique decoding이 불가능한 경우입니다.

또하나가 있습니다. 우리 학교의 주소는 134번지인데 135번지라고 되어있습니다.
이는 주소의 번지를 정확히 알고있다면 찾아낼수있지만, 그렇지 않다면
오류가 있는지 알아낼 방법이 없습니다.
그 이유는 무엇일까요? 바로 135라는 숫자가 정당하게 사용되는 숫자(단어)이기 때문입니다.
앞의 두 경우는 바로 정당하게 사용되어지는 단어가 아니기 때문이라는 해석도 가능합니다.
사실, 이점이 가장 중요한 핵심사항입니다.

채널부호는 이렇게, n-bit word 2^n(2의 n승)개 중에서 일정한 규칙으로 일부분만 사용하기로
미리 약정하는데 있습니다. 수신단에서 이렇게 약정된 단어가 아닌 n-bit word가 수신되면
즉각적으로 오류가 발생했다고 알아낼수있습니다. 이것이 오류검출입니다.
검출되지 않은 오류는 당연히 정정될수없습니다. 검출된 오류라 할지라도
모두 정정가능한것은 아닙니다. 어떤것은 자연스럽게 그리고 유일하게 그리고 자신있게 정정될수있지만
어떤것은 모호하여 정정가능하지 않은 경우도 있습니다.

법칙 1. 검출되지 않은 오류는 정정할수 없다.

오류정정은 어떻게 가능할까요? 약정한 단어중에서 가장 "그럴듯"한 것으로 추측하는것입니다.
여기서 그럴듯하다는 뜻은 정량적으로 말해서 "거리"가 가장 가갑다고도 말할수있습니다.
"서운특별시"라는 오류가 첨부된 단어로부터 가장 "가까이" 있는 사전에 있는 단어는 바로 "서울특별시"일것입니다.
그러나 "전지공학과"와 가장 가까운 단어는 2개가 존재하여
어느것으로 결정하더라도 상당한양의 오류확률을 수반하게 됩니다.
심지어 "135번지"에는 오류가 있는지조차 알아낼수없기에 정정은 꿈도 못꿉니다.

오류에는 크게 검출가능오류와 검출 불가능한 오류가 있습니다.
검출가능하기 위해서는 약정한 단어가 아닌 단어로 변화시키는 오류여야 합니다.
만일, 전자공학과라고 쓴다면서 전기공학과라고 썼다면 이는 검출 불가능한 오류가 됩니다.
왜냐면 전기공학과라는 단어도 사전에 있는 단어이기 때문입니다. 읽는 사람은 여기에 이상한점이 있다고 느끼지 못합니다.
검출불가능한 오류는 약정한 단어를 또다를 약정한 단어로 변화시키는 오류입니다.
이를 다른말로 표현하면 codeword를 또다른 codeword로 변화시키는 오류라고 할수있습니다.

단어와 단어 사이의 거리를 정의하는 방법에는 여러가지가 있습니다. discrete coding channel model에 따라서
이러한 거리의 개념과 정의는 바뀔수있습니다. AWGN채널과 simple additive channel model에서는
해밍거리(Hamming distance)라는 정의가 유용합니다. 이는 두 단어를 component별로 비교하여
서로 다른 component의 갯수로 정의합니다.

000111000 과
110111000 의 Hamming distance는 2가 됩니다.
만일 이 두 단어가 모두 codeword라면
이 코드는 특별한 오류벡터 110000000 이 발생하는경우 검출이 불가능해질수도 있습니다.

000111000을 송신하고서 여기에 110000000 이라는 오류가 더해져서(처음 두 bit가 변형되어)
110111000을 수신하는경우
수신기의 decoder는 약정한 codeword를 즉시 알아보기 때문에 오류가 없다고 판단한다는 것입니다.
만일 100000000 이라는 오류가 더해져서(처음 한 bit가 변형되어)
100111000을 수신한다면 즉시 오류가 발생했다는 것을 알아낼수있겠지요?
왜냐면
100111000은 송신기가 절대로 송신하지 않는 단어라는것을 수신기도 알고있기 때문입니다...
그러나 이경우 000111000 에 100000000 이 더해진건지, 아니면 110111000 에 010000000이 더해진건지 모호합니다.
정확한(꽤 정확한) 정정은 불가능하다는 뜻입니다.

만일
000111011을 수신했다고 합시다. 여러분같으면 둘중 어떤 codeword라고 decoding하고 싶은지요?
당연히
000111000이라 생각이 들겁니다.
만일
110111000을 송신했다면 여기에 110000011이라는 4bit 오류가 더해진건데
이보다는
000000011 이라는 2bit 오류가 더해진것으로 보는것이 훨씬 더 "그럴듯"하기 때문입니다.
이렇게 그럴듯하다는 표현의 뜻은 hamming distance가 가깝다는 표현입니다.
즉 수신벡터와 송신하기로 약정된 모든 codeword와 hamming distance를 비교하여 가장 가까이에 있는
codeword로 decoding하는것을
minimum distance decoding이라고 하며, 적절한 가정 하에서
이러한 decoding은 ML decoding (Maximum Likelihood decoding)이 됩니다.

법칙2. (적절한 가정하에서) Minimum distance decoding은 Maximum Likelihood decoding이다.

codeword 숫자가 많아지면 시간도 길어지고 복잡한 계산을 해야합니다. 통신시스템의 오류정정부호의
발전은 이렇게 ML decoding을 수행하기위하여 적절한 대수학적 구조를
codeword 집합에 부여함으로써 상당히 빠르고 편리하게 decoding을 가능케하도록
설계하고 연구해온 결과입니다.....
오늘은 여기까지 하겠습니다.......................







165.132.155.170 최영빈: 복잡한 개념이 교수님의 설명을 들으면 손에 잡힐듯 쉬워지는것 같습니다. 감사합니다. -[10/13-11:50]-

165.132.59.119 송홍엽: 영빈이 코멘트가 나에게 보람이구나... 여기 내용은 단순이 관심있는 사람만 보라는게 아니고 수업시간에 다룰 내용을 미리 소개하는 것입니다. 모두들 자세히 읽고 또 일고 하여 숙지해야하는 내용입니다. -[10/13-19:56]-

165.132.120.251 이효빈: 그렇군요... 문득 작년에 통신이론 배울때 디통분야를 들으면서 느꼈던 "!"가 생각나네요...^^ -[10/15-12:57]-

219.241.32.177 오현영: 0과 1의 세계에서는 정말 별것이 가능하군요^^; -[10/15-22:06]-
번호 제목 글쓴이 날짜 조회 수
공지 논문에 영어작문 주의사항 몇 가지 송홍엽 2008.05.22 9200
공지 젊은 학부생 여러분에게... 송홍엽 2008.11.20 6145
공지 우리학과 대학원생 모두에게 (특히, 박사과정들에게) 하고싶은 말입니다. 송홍엽 2014.01.20 8215
89 학위논문 작성에 관한 조언 file 송홍엽 2014.01.25 2132
88 [펀글] 한겨레 2011.12.23. 정봉주 유죄판결은 법적 착시현상 송홍엽 2011.12.25 2340
87 2013년 12월 31일 오후에 작성한 글: 새해는 시속 1400키로의 속도로 달려온다. file 송홍엽 2014.01.17 2460
86 [펀글]프로운동선수의 대학학업 병행하기 송홍엽 2009.12.17 2923
85 [펀글] 왜 우린 이런거 못만드냐고... 송홍엽 2010.05.09 2964
84 [펀글] 교육의 의미 송홍엽 2008.02.19 2965
83 [펀글] 조선일보 1월2일 사설: 교육개혁 송홍엽 2008.01.03 2982
82 암호이야기 송홍엽 2008.05.21 3010
81 [펀글] 한반도 운하 건설을 반대하며 송홍엽 2008.02.20 3285
80 디지털 이야기... 송홍엽 2003.10.06 3342
79 [소고] 수학이란.... 송홍엽 2004.04.13 3411
78 [펀글-조선일보] 대중적인 책 내면 ‘이단아’ 취급 송홍엽 2006.09.18 3412
77 Re..랜덤변수의 variance가 0이면? 김태환 2005.07.30 3432
76 손바닥/손등 게임 송홍엽 2005.09.30 3446
75 유명한 퍼즐1 송홍엽 2004.04.01 3488
74 DMS와 정보량 송홍엽 2004.04.04 3531
73 [일반인을 위한 교양강좌] CDMA 통신기술 (2001.7) 송홍엽 2003.10.13 3575
72 [퍼온글]독도대첩 송홍엽 2005.03.15 3610
71 [교양상식] 정수와 암호 송홍엽 2004.04.13 3634
70 Golomb-Puzzle 2003.12 file 송홍엽 2004.04.02 3635