Communication Signal Design Lab.

한국어

송홍엽 교수의 잡글

채널코딩 세째 이야기

2003.11.13 05:43

송홍엽 조회 수:5036 추천: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 9200
공지 젊은 학부생 여러분에게... 송홍엽 2008.11.20 6145
공지 우리학과 대학원생 모두에게 (특히, 박사과정들에게) 하고싶은 말입니다. 송홍엽 2014.01.20 8215
27 대학원생 생활 가이드 [퍼온글] 송홍엽 2007.10.11 8394
26 [펀글] 조선일보 1월2일 사설: 교육개혁 송홍엽 2008.01.03 2982
25 [펀글] 교육의 의미 송홍엽 2008.02.19 2965
24 [펀글] 한반도 운하 건설을 반대하며 송홍엽 2008.02.20 3285
23 [펀글] 추장의 선언 [1] 송홍엽 2008.02.22 7903
22 암호이야기 송홍엽 2008.05.21 3010
21 우리학부 전공 2-3학년생에 대한 조언 송홍엽 2008.05.22 3905
20 글 잘 쓰는 이공계가 성공한다 송홍엽 2008.05.22 27476
19 [펀글] 전화기를 최초로 발명한 사람은 누구인가 송홍엽 2008.05.23 6841
18 수학사 바로잡기 (1) - 오일러의 36명 장교문제와 조선시대 최석정 (수정본 - 일부 오류 수정) [1] file 송홍엽 2008.06.03 7163
17 수학사 바로잡기 (2) 송홍엽 2008.06.03 7777
16 수학사 바로잡기 (3) - 월간 과학동아 2008년 7월호 강석기 기자의 글 송홍엽 2008.06.20 4246
15 김정한 교수의 '창의적 수학교육' [1] file 송홍엽 2008.06.20 6085
14 [펀글]수학의 open problems 모음. 송홍엽 2008.07.30 15035
13 움직이는 글자 태그 송홍엽 2008.09.04 3840
12 [퍼온글] FM방식 개발한 암스트롱 송홍엽 2008.09.24 4042
11 [퍼온글] 해석학적 극한의 의미 송홍엽 2008.12.18 4036
10 [퍼온글] 수학의 힘 -- 동아일보 컬럼 2008.12.18 송홍엽 2008.12.18 3723