| 1 |
1
가변길이 코드 테이블 및 탐색너비 N을 입력받는 단계;
상기 가변길이 코드 테이블 및 상기 탐색너비 N으로부터 K-ary 트리를 생성하는 단계; 및
상기 K-ary 트리로부터 N-비트 코드 테이블을 생성하는 단계를 포함하며,
상기 K-ary 트리는 하나의 노드가 가질 수 있는 자식노드의 개수가 최대 K개인 트리를 의미하고,
상기 K-ary 트리의 K와 상기 탐색너비 N은 K=2N를 만족하며,
N-비트 코드 테이블을 생성하는 단계는,
상기 K-ary 트리에 속하는 모든 내부노드를 포함하는 내부노드 리스트를 생성하는 단계;
상기 내부노드 리스트의 첫 번째 노드부터 시작하여 타입 A인 내부노드에는 N-비트 코드 테이블의 행 번호를 증가시키면서 하나의 행씩 할당하고, 타입 B인 내부노드에는 자식노드의 데이터가 저장될 엔트리의 위치를 결정하기 위해 사용되는 이진수인 조정자를 할당하는 단계; 및
상기 내부노드 리스트의 첫 번째 노드부터 각 내부노드를 차례로 방문하여 상기 N-비트 코드 테이블의 각 엔트리에 소정 데이터를 저장하는 단계를 포함하며,
상기 타입 A인 내부노드는 하나 이상의 내부노드를 자식노드로 갖는 내부노드이고, 상기 타입 B인 내부노드는 자식노드가 모두 단말노드인 내부노드를 의미하
는 것을 특징으로 하는 가변길이 코드 복호화를 위한 테이블 생성 방법
|
| 2 |
2
삭제
|
| 3 |
3
제 1 항에 있어서, 상기 K-ary 트리를 생성하는 단계는,
루트노드를 생성하여 현재노드로 할당하는 제 1 단계;
상기 가변길이 코드 테이블로부터 하나의 코드워드를 입력받는 제 2 단계;
상기 입력받은 코드워드의 길이를 상기 탐색너비 N과 비교하는 제 3 단계; 및
상기 제 3 단계에서의 비교 결과 상기 코드워드의 길이가 상기 탐색너비 N보다 작거나 같은 경우, 현재 노드의 자식노드로 상기 코드워드를 갖는 단말노드를 삽입하는 제 4 단계를 포함하는 것을 특징으로 하는 가변길이 코드 복호화를 위한 테이블 생성 방법
|
| 4 |
4
제 3 항에 있어서,
상기 제 3 단계에서의 비교 결과 상기 코드워드의 길이가 상기 탐색너비 N 보다 큰 경우, 상기 코드워드로부터 N비트만큼을 잘라내는 제 5 단계;
현재노드의 자식노드 중에서 잘라낸 N비트 코드를 갖는 내부노드가 존재하는지 여부를 판단하는 제 6 단계;
상기 제 6 단계에서의 판단 결과가 참이면 상기 잘라낸 N 비트 코드를 갖는 내부노드를 현재노드로 할당하는 제 7 단계를 더 포함하며,
상기 제 7 단계가 수행된 후, 상기 입력받은 코드워드에 대한 단말노드가 생성될 때까지 상기 제 3 단계 내지 상기 제 7 단계가 반복하여 수행되는 것을 특징으로 하는 가변길이 코드 복호화를 위한 테이블 생성 방법
|
| 5 |
5
제 4 항에 있어서,
상기 제 6 단계에서의 판단 결과가 거짓이면 현재노드의 자식노드로 상기 N 비트 코드를 갖는 내부노드를 삽입하고 현재노드로 할당하는 제 8 단계를 더 포함하며,
상기 제 8 단계가 수행된 후, 상기 입력받은 코드워드에 대한 단말노드가 생성될 때까지 상기 제 3 단계 내지 상기 제 8 단계가 반복하여 수행되는 것을 특징으로 하는 가변길이 코드 복호화를 위한 테이블 생성 방법
|
| 6 |
6
제 5항에 있어서,
상기 제 1 단계 내지 제 8 단계는 상기 가변길이 코드 테이블에 포함된 모든 코드워드에 대해 반복하여 수행되는 것을 특징으로 하는 가변길이 코드 복호화를 위한 테이블 생성 방법
|
| 7 |
7
삭제
|
| 8 |
8
제 1 항에 있어서,
상기 조정자의 길이는 상기 탐색너비 N에서 해당 내부노드가 갖는 자식노드에 저장된 코드의 길이 중 최대값을 뺀 값인 것을 특징으로 하는 가변길이 코드 복호화를 위한 테이블 생성 방법
|
| 9 |
9
제 1 항에 있어서,
상기 내부노드 리스트를 생성하는 단계에서, 내부노드의 정렬 순서는,
내부노드의 타입이 서로 다른 경우에는 타입 A인 내부노드가 타입 B인 내부노드에 비해 앞선 순서를 갖고,
내부노드가 모두 타입 A 인 경우에는 노드 번호가 작은 쪽이 앞선 순서를 갖고,
내부노드가 모두 타입 B 인 경우에는 해당 내부노드가 갖는 자식노드에 저장된 코드의 길이 중 최대값이 큰 노드가 앞선 순서를 갖는 것을 특징으로 하는 가변길이 코드 복호화를 위한 테이블 생성 방법
|
| 10 |
10
제 1 항에 있어서,
상기 N-비트 코드 테이블의 각 엔트리에 소정 데이터를 저장하는 단계에서, 데이터가 저장될 엔트리의 위치는,
자식노드가 내부노드이거나 상기 탐색너비 N의 길이의 코드를 갖는 단말노드인 경우에는 상기 자식노드의 코드만으로 결정하고,
자식노드가 상기 탐색너비 N보다 작은 길이의 코드를 갖는 단말노드인 경우에는 현재 방문중인 내부노드의 조정자 및 상기 자식노드의 코드의 조합으로 결정하는 것을 특징으로 하는 가변길이 코드 복호화를 위한 테이블 생성 방법
|
| 11 |
11
제 1 항에 있어서,
상기 N-비트 코드 테이블의 각 엔트리에 소정 데이터를 저장하는 단계에서,
해당 엔트리에 할당된 자식노드가 단말노드인 경우에는 추가탐색 값으로 0을 저장하고 상기 할당된 자식노드의 코드 길이 및 심볼을 저장하며,
해당 엔트리에 할당된 자식노드가 내부노드인 경우에는 추가탐색 값으로 1을 저장하고 상기 할당된 자식노드의 조정자의 길이, 조정자 및 다음 행 번호를 저장하는 것을 특징으로 하는 가변길이 코드 복호화를 위한 테이블 생성 방법
|
