일반기술

균형 이진 검색 트리를 이용한 허프만 디코딩 방법 및 디코딩 장치

본 발명은, 코드워드(Codeword) 중 일부 길이를 먼저 검색하게 하기 위해 포인터 필드, 엔트리 수 필드 및 길이 필드를 포함하는 레인지 테이블; 상기 레인지 테이블과 연결되어 상기 레인지 테이블에 저장된 코드워드 심볼을 제외한 코드워드 필드, 상기 코드워드의 길이 필드 및 심볼 필드를 포함하는 디코딩 테이블에서 균형 이진 검색 트리(Balanced Search Tree)를 이용하여 허프만 디코딩을 수행하는 방법에 있어서, (a) 입력 비트 스트림 중 기설정된 레인징 코드 길이의 레인징 비트 스트림을 상기 레인지 테이블의 인덱스로 사용하여 상기 레인지 테이블의 엔트리에 접근하는 단계; (b) 상기 인덱스의 상기 엔트리 수 필드 값이 0이면 상기 인덱스의 상기 포인터 필드에 저장된 심볼로 디코딩하는 단계; 및 (c) 상기 인덱스의 상기 엔트리 수 필드 값이 0이 아니면 상기 인덱스의 상기 포인터 필드 값을 인덱스로 가지는 상기 디코딩 테이블의 시작 엔트리부터 상기 인덱스의 상기 엔트리 수 필드 값만큼 떨어진 엔트리 사이에서, 상기 입력 비트 스트림과 상기 코드워드 필드에 저장된 값을 비교하여 이진 검색(Binary Search)을 수행하고, 이진 검색 수행 결과 일치되는 필드에 저장된 심볼로 디코딩하는 단계를 포함하는 것을 특징으로 하는 균형 이진 검색 트리를 이용한 허프만 디코딩 방법 및 디코딩 장치에 관한 것이다.