결과보고서5_디지털통신2_허프만 부호, 블록부호화

목차

1. 배경 이론 --------------------------------------- p.3
2. 실습 코드 --------------------------------------- p.6
3. 코드 분석 --------------------------------------- p.9
4. 결과 ------------------------------------------- p.15
5. 고찰 ------------------------------------------- p.17

본문내용

배경 이론
1. 허프만 부호화
A. 의미
출현 빈도수에 따라 코드 길이를 다르게 대응시키는 소스코딩 방식이다. 빈도수가 높은 심볼에는 짧은 코드를 대응시키고 빈도수가 낮은 심볼에는 긴 코드를 대응시킨다. 그래서 필요한 전체 공간을 최소화하는 가변 길이 부호화 방식이다. 이는 전체적인 데이터 길이가 짧아지므로 데이터 압축 기법이기도 하다.

B. 특징
무손실 압축에 사용되는 엔트로피 부호화의 일종이다. 평균 코드 길이가 소스의 엔트로피에 근접한다.
심볼의 출현 빈도에 따라 다른 길이의 코드를 부여한다. 적게 출현하는 심볼일수록 더 긴 코드, 자주 발생할수록 더 짧은 코드가 할당된다. 결국 전체적으로 보면 자주 반복되는 데이터는 짧게 표현이 가능해지므로 적은 메모리로 데이터를 온전히 구현할 수 있는 것이다.
심볼의 출현 빈도에 따라 접두사 코드를 만들어낸다. 주어진 빈도에 따라 항상 최적의 접두사 코드를 만들어내나 사전에 각 심볼의 발생확률을 미리 알고 모델링 되어 있어야 한다.
단점으로는 코드 길이가 가변 되므로 수신 측에서 복호화 방식이 복잡해진다는 점이 있다. 또 전송 오류가 발생하면 다음 데이터까지 영향을 받게 된다.

C. 알고리즘
i. 감축 단계
심볼들을 확률이 높은 것부터 작은 것으로 확률 크기순으로 열거한 후 r개의 심볼의 확률을 부분적으로 더해가며 다시 확률 크기순으로 열거한다. 이 작업을 마지막 데이터까지 계속한다.
ii. 확장 단계
감출 단계의 마지막으로 남아있던 r개의 심볼에 코드 알파벳을 할당하며 부호어를 생성한다.

2. Block Coding and Decoding
A. 의미
블록 코드는 고정된 코드 길이를 갖는 부호를 의미한다. 데이터를 일정 블록 단위로 묶어서 블록마다 코딩, 디코딩하는 것을 블록 코딩, 블록 디코딩이라 한다. 블록 코딩은 전송의 신뢰도를 증가시키기 위해서 디지털 워드에 여분의 비트를 추가하는 기술이다. 디지털 워드는 메시지 비티와 코드 비트가 더해져서 구성된다. 블록 코드는 존재하는 메시지 비트 혹은 블록에 코드 비트를 더하는데 인접하는 블록 간에는 서로 독립적이다.

참고 자료

없음