Communication Signal Design Lab.

한국어

송홍엽 교수의 잡글

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

2003.10.13 08:12

송홍엽 조회 수:4914 추천: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 9436
공지 젊은 학부생 여러분에게... 송홍엽 2008.11.20 6393
공지 우리학과 대학원생 모두에게 (특히, 박사과정들에게) 하고싶은 말입니다. 송홍엽 2014.01.20 8462
89 [퍼온글] 우리전공의 학부생이 공부하면 좋을 수학과목 ?? 송홍엽 2003.03.23 6529
88 지금 내 전공분야는 공부한던 시절엔 나에게 가장 힘든 분야였답니다... 송홍엽 2003.06.03 5034
87 벡터공간이란 무엇일까.. 송홍엽 2003.10.06 14178
86 유클리디안 n차원 벡터공간 (and Online-HW1) 송홍엽 2003.10.06 7648
85 basis란.. (and Online-HW2) 송홍엽 2003.10.06 82624
84 디지털 이야기... 송홍엽 2003.10.06 3405
83 하다마드 행렬에 대해서 (part 1) [1] 송홍엽 2003.10.06 10717
82 [일반인을 위한 교양강좌] CDMA 통신기술 (2001.7) 송홍엽 2003.10.13 3654
» 채널코딩에 관한 첫번째 이야기 송홍엽 2003.10.13 4914
80 쉬었다가는 페이지 file 송홍엽 2003.10.20 3822
79 채널코딩 둘째이야기... 송홍엽 2003.11.12 18204
78 채널코딩 세째 이야기 송홍엽 2003.11.13 5120
77 Dr. Shannon 송홍엽 2003.12.07 26846
76 [공지] 게시판을 열면서 송홍엽 2004.03.30 3901
75 funny story 송홍엽 2004.04.01 14081
74 [퍼온글] 달력의 유래 송홍엽 2004.04.01 5321
73 유명한 퍼즐1 송홍엽 2004.04.01 3579
72 Golomb-Puzzle 2003.12 file 송홍엽 2004.04.02 3721
71 DMS와 정보량 송홍엽 2004.04.04 3570
70 수집합이란... 송홍엽 2004.04.13 3730