Communication Signal Design Lab.

한국어

송홍엽 교수의 잡글

채널코딩 세째 이야기

2003.11.13 05:43

송홍엽 조회 수:5120 추천:168

오늘은 선형부호에 관한 이야기를 주로 하겠습니다.
이진부호로 한정하고요.
그러면 다음과 같은 파라미터를 가집니다.
[n,k,d]
그래서 코드 C가 [n,k,d] binary linear code 이라는 말의 정의는
이진 n-tuple vector space의 k-dimensional subspace로서
minimum Hamming diatance가 d인 벡터 부분공간이라는 뜻입니다.
여기서 minimum Hamming distance d를 굳이 포함시키지 않는다면
[n,k] binary linear code 라고도 합니다.

학기초에 on-line HW으로 이야기했듯이
[n,k] binary linear code는 상당히 많은 수가 존재합니다.
n-tuple vector space의 k-dimensional subspace의 수는 정확히 계산가능합니다만...

이들중 어떻게 k-dimensional subspace를 택해야 좋은 코드인가 하는 문제는
결국 minimum distance를 최대화시키는 것이라고 할수있습니다.
왜냐면 minimum distance가 클수록 오류정정능력이 커지기 때문입니다.
예를 들겠습니다.
n=6, k=2라고 합시다.

64개의 binary 6-tuple중에서 4개를 선택하는 문제입니다.
다음 두가지의 선택을 생각합시다.

Code A:
000000
000111
111000
111111

Code B:
000000
000011
010000
010011

둘다 2-dimensional subspace를 이루며
중간의 두개가 basis를 이룹니다.
차이가 뭘까요?
바로 minimum distance가 다릅니다.
즉, Code A의 최소거리는 3이고
Code B의 최소거리는 1입니다.
Code A를 사용할때 만일 1-bit error가 발생한다면
어디에 발생하든지에 상관없이 이를 검출하여 제대로 수정가능합니다.
Code B를 사용한다면 심지어 특정한 1-bit error는 검출도 불가능합니다.

물론 2-bit error가 발생하면 Code A를 사용한다고 해도 반드시 제대로
수정가능하다고 보장할수는 없습니다만 적어도 1-bit error에 대해서는 그러합니다.
이는 상당한 차이를 줍니다.

앞으로 다음 세가지 문제에 대해서 논의하려고 합니다.
1. 주어진 [n,k] binary linear code의 minimum hamming distance가 d일때 오류정정능력은 어떻게 결정되는가?
2. n,k가 고정되어 있을때, 선택을 잘해서 d를 늘릴수있는 한계는 어디인가?
3. encoding/decoding 방식은 어떠한가?

기대하세요...
번호 제목 글쓴이 날짜 조회 수
공지 논문에 영어작문 주의사항 몇 가지 송홍엽 2008.05.22 9438
공지 젊은 학부생 여러분에게... 송홍엽 2008.11.20 6394
공지 우리학과 대학원생 모두에게 (특히, 박사과정들에게) 하고싶은 말입니다. 송홍엽 2014.01.20 8462
87 학위논문 작성에 관한 조언 file 송홍엽 2014.01.25 2255
86 2013년 12월 31일 오후에 작성한 글: 새해는 시속 1400키로의 속도로 달려온다. file 송홍엽 2014.01.17 2555
85 [펀글] 한겨레 2011.12.23. 정봉주 유죄판결은 법적 착시현상 송홍엽 2011.12.25 2433
84 [퍼온글] 외국계 기업, `출신대 간판` 안 본다 송홍엽 2011.12.15 3851
83 [펀글] 영문이력서 작성법 송홍엽 2011.03.27 5820
82 [펀글] 왜 우린 이런거 못만드냐고... 송홍엽 2010.05.09 3063
81 [펀글] 프로그램 설계시 좋은 코딩 습관 송홍엽 2009.12.27 5441
80 [펀글]프로운동선수의 대학학업 병행하기 송홍엽 2009.12.17 3019
79 [퍼온글] 수학의 힘 -- 동아일보 컬럼 2008.12.18 송홍엽 2008.12.18 3811
78 [퍼온글] 해석학적 극한의 의미 송홍엽 2008.12.18 4121
77 [퍼온글] FM방식 개발한 암스트롱 송홍엽 2008.09.24 4163
76 움직이는 글자 태그 송홍엽 2008.09.04 3927
75 [펀글]수학의 open problems 모음. 송홍엽 2008.07.30 15234
74 김정한 교수의 '창의적 수학교육' [1] file 송홍엽 2008.06.20 6154
73 수학사 바로잡기 (3) - 월간 과학동아 2008년 7월호 강석기 기자의 글 송홍엽 2008.06.20 4327
72 수학사 바로잡기 (2) 송홍엽 2008.06.03 7903
71 수학사 바로잡기 (1) - 오일러의 36명 장교문제와 조선시대 최석정 (수정본 - 일부 오류 수정) [1] file 송홍엽 2008.06.03 7294
70 [펀글] 전화기를 최초로 발명한 사람은 누구인가 송홍엽 2008.05.23 7003