KR100269808B1 - 압축률 편차를 보상하는 데이터 압축 시스템 - Google Patents

Abstract

본 발명은 입력되는 데이터 코드 스트링에 대하여 균일한 압축률을 갖도록 압축률 편차를 보상할 수 있는 데이터 압축 시스템에 관한 것이다. 이를 위하여 본 발명은 최대 길이로 매칭된 구문화된 코드와 그에 이어지는 다음번의 구문화된 코드의 압축률 편차가 기설정 임계값보다 클 때, 감축 코드 스트링 매칭부에서 상기 최대 길이의 구문화된 코드의 마지막 비트를 제외한 나머지의 감축된 코드에 대하여 구문화를 수행하고, 구문화된 코드에 대응하는 인덱스를 사전 저장부로부터 찾아 압축 부호화를 수행한다.

따라서, 인접한 두 개의 구문화된 코드간의 압축률 편차가 균일하게 유지되므로, 제한된 채널 용량을 효율적으로 사용할 수 있게한다.

Description

압축률 편차를 보상하는 데이터 압축 시스템

본 발명은 스트링 매칭을 통한 데이터 압축 시스템에 관한 것으로서, 더욱 상세하게는 최대 길이로 구문화된 코드와 그에 이어지는 다음번의 구문화된 코드간의 압축률 편차를 보상하여 균일한 데이터 압축률로 전송하는 데이터 압축 시스템에 관한 것이다.

일반적으로, 통상의 전송 채널에서 이용 가능한 주파수 대역폭은 제한되어 있으므로, 많은 양의 데이터를 전송하기 위해서 모뎀과 같은 다양한 전송 시스템은 전송 데이터의 양을 압축하거나 줄일 수 있는 효과적인 데이터 압축 기법을 이용해 왔다.

다양한 압축기법 중의 하나는 국제 전기 통신 동맹(ITU : International Telecommunication Union)에 의해 표준화된 부호화 알고리즘으로, 모뎀과같은 데이터 전송 시스템에서 채용하고 있는 CCITT V.42 bis 이다. 이 부호화 표준안에 적용된 기초는 Ziv-Lempel code(ZLC)이며, 이 방식은 입력 데이터로부터 적응적으로 사전을 형성해 가면서 앞의 입력 데이터와 동일한 구문(phrase)가 저장되어있는 사전의 주소값을 부호어로 전송하는 방법이다. 사전화(dictionary) 작업은 입력 데이터와 계속적인 스트링 매칭(string matching)을 수행하여 최대 길이의 매칭 스트링에 매칭안된 문자를 결합하여 사전에 추가하는 과정으로 사전을 업데이트한다.

예를 들면, a, b, c, d, e, ab, bc, abc라는 문자 스트링이 기존의 사전에 등록되어있는 상황에서, "...abcde..."라는 문자 스트링이 입력되면, 스트링 매칭을 통하여 abc, d, e로 구문화(parsing)를 수행한다. 이때 "abc"는 사전에 등록되어있는 최대 길이 매칭 스트링이고, "d"가 매칭안된 문자이다. 따라서, "abcd"를 사전에 새로이 추가 등록하고, 매칭안된 "d"로부터 다시 스트링 매칭을 수행하여 "de"를 또다시 사전에 추가 등록하는 방식으로 사전화한다. 즉, 하나의 매칭안된 문자 스트링이 나올 때 마다 스트링 매칭을 수행하여 다시 하나의 요소를 새로이 사전에 추가 등록하는 것이다.

이때, 새로이 추가되는 "abcd"가 사전의 "100" 번지에 등록된다면, 이후에 "...abcd..."라는 문자 스트링이 입력될 때 "abcd"라는 문자 스트링을 "100"이라는 주소값으로 부호화하여 전송하게된다.

그러나, 상술한 V.42 bis 알고리즘의 압축 방식에서, 최대 길이로 매칭되는 문자 스트링, 예로, abc와 같은 부분에서는 압축률이 높고, 짧은 길이로 매칭되는 문자 스트링, 예로, d, e와 같은 부분에서는 압축률이 낮다. 그러므로, 이들과 같이 구문화된 두 문자 스트링이 서로 시간적으로 인접하게 전송되는 경우, 두 문자 스트링간의 압축률 편차가 심하며, 이러한 큰 압축률 편차는 제한된 채널 용량을 갖는 전송 채널에서 오버플로우(overflow) 현상을 유발시킴으로써 제한된 채널 용량을 효과적으로 사용하지 못한다는 단점이 있다.

그러므로, 본 발명은 비교적 균일한 부분 압축률을 갖는 데이터를 전송할 수 있도록 압축률 편차를 보상하는 데이터 압축 시스템을 제공하는 것을 그 목적으로 한다.

상기 목적을 달성하기 위한 본 발명에 따르면, 균일한 압축률로 데이터를 전송하기위하여 압축률 편차를 보상하는 데이터 압축 시스템은, 상기 데이터 코드 스트링에 대하여 구문화된 코드를 사전(dictionary) 방식으로 계속적으로 등록하여 저장하는 저장수단; 상기 데이터 코드 스트링을 구문화(parsing)하고, 상기 구문화된 코드를 상기 저장 수단에 저장된 구문화된 코드와 매칭하고, 매칭안된 구문화된 코드가 상기 저장수단에 새로이 등록되게하는 스트링 매칭부; 상기 스트링 매칭부로부터 제공되는 구문화된 코드를 일시 저장하는 제 1 버퍼; 상기 스트링 매칭부에서 최대 길이로 매칭된 구문화된 코드를 일시 저장하는 제 2 버퍼; 상기 제 1 및 제 2 버퍼에 저장된 구문화된 코드들로부터 계산된 압축 편차율과 기설정 압축 편차율의 임계값을 비교하는 비교 수단; 상기 비교 수단에서 상기 계산된 압축 편차율이 상기 기설정 임계값보다 클 때, 상기 제 2 버퍼에 저장된 최대 길이의 구문화된 코드의 마지막 비트를 제외한 나머지의 감축된 코드에 대하여 구문화하고, 상기 구문화된 코드를 상기 저장 수단에 저장된 구문화된 코드와 매칭하고, 매칭안된 구문화된 코드가 상기 저장수단에 새로이 등록되게하는 감축 코드 스트링 매칭부; 상기 제 1 버퍼 또는 제 2 버퍼를 통하여 제공되는 구문화된 코드에 대응하는 인덱스를 상기 저장 수단으로부터 찾아 압축 부호화를 수행하는 인코더를 포함하는 것을 특징으로 한다.

도 1은 본 발명에 따른 균일 데이터 압축률을 갖도록 압축률 편차를 보상하는 데이터 압축 시스템의 부호화 장치의 블록 구성도.

＜도면의 주요부분에 대한 부호의 설명＞

100 : 사전 데이터 저장부 200 : 스트링 매칭부

300 : 제 1 버퍼 400 : 제 2 버퍼

500 : 비교부 600 : 감축 코드 스트링 매칭부

이하, 첨부된 도면을 참조하여 본 발명의 실시예를 상세히 설명하기로 한다.

도 1을 참조하면, 본 발명에 따라서 균일한 압축률로 데이터를 전송하기위하여 압축률 편차를 보상하는 데이터 압축 시스템의 부호화 장치의 블록 구성도로서, 본 발명의 데이터 압축 시스템의 부호화 장치는 모뎀과같은 데이터 전송 시스템에서 채용하고 있는 CCITT V.42 bis 알고리즘을 이용하는 시스템에 적용된다.

도 1에 도시된 바와 같이, 발명의 압축률 편차 보상을 위한 데이터 압축 시스템의 부호화 장치는 데이터 코드 스트링이 입력되는 사전(dictionary) 데이터 저장부(100), 스트링 매칭부(200), 제 1 버퍼(300), 제 2 버퍼(400), 비교부(500), 감축 코드 스트링 매칭부(600) 및 인코더(700)를 포함한다.

메모리로서 구현될 수 있는 사전 데이터 저장부(100)는 입력되는 데이터 코드 스트링에 대하여 구문화된 코드를 사전방식으로 계속적으로 등록하여 저장한다. 사전 데이터 저장부(100)에 등록되는 구문화된 코드는 각기 상이한 저장 영역에 할당되어 저장되며, 이 저장 영역의 어드레스는 인코더(700)에서 부호화하는데 필요한 인덱스 신호로서 사용된다.

스트링 매칭부(200)은 입력 데이터 코드 스트링을 구문화(parsing)하고, 구문화된 코드를 사전 데이터 저장부(100)에 저장된 구문화된 코드와 매칭을 수행한다.스트링 매칭부(200)에서 매칭안된(unmatched) 구문화된 코드가 발생되는 경우, 매칭안된 구문화된 코드는 사전 데이터 저장부(100)에 새로이 등록된다. 스트링 매칭부(200)에서 스트링 매칭되는 구문화된 코드는 통상적으로 제 1 버퍼(300)로 제공되며, 스트링 매칭중에 최대 길이로 매칭된 구문화된 코드가 발생되는 경우에는 제 2 버퍼(400)로 제공된다.

제 1 버퍼(300) 및 제 2 버퍼(400)는 스트링 매칭부(200)에서 전달된 구문화된 코드를 일시 저장한 후 다음단의 인코더(700)로 제공하는데, 제 1 버퍼(300)는 하기에 설명되는 비교부(500)의 비교 동작을 위하여 제 2 버퍼(400)에 저장되는 최대 길이 구문화된 코드의 다음에 이어지는 순서의 구문화된 코드를 저장한다.

비교부(500)는 스트링 매칭부(200)에서 최대 길이의 구문화된 코드가 발생되는 경우, 인접하게 구문화된 코드들간의 압축률 편차를 보상하기위하여 제 1 버퍼(300)와 제 2 버퍼(400)에 일시 저장되는 구문화된 코드의 길이로부터 압축률 편차를 계산한다. 보다 상세히 말해서, 제 2 버퍼(400)에 저장된 구문화된 코드의 길이가 네(4)자리이고, 제 1 버퍼(300)에 저장된 구문화된 코드의 길이가 한(1)자리라고 가정하면, 이들 간의 압축 비율은 4 : 1로서, 압축률 편차는 75％에 이른다. 그러나, 이들 인접한 입력 데이터 스트링을 세(3)자리와 두(2)자리로 각기 구문화하게 된다면, 이들간의 압축률 편차는 약 33％로 줄어들게된다. 따라서, 비교부(500)는 기설정된 압축률 편차 임계값(threshold)과 제 1 버퍼(300)와 제 2 버퍼(400)에 각기 저장된 구문화된 코드간의 계산된 압축률 편차를 비교한다.

비교부(500)의 비교 결과, 계산된 압축률 편차가 압축률 편차 임계값보다 적으면 제 2 버퍼(400)에 저장된 구문화된 코드가 인코더(700)로 제공된다. 그러나, 비교부(500)의 비교 결과, 계산된 압축률 편차가 압축률 편차 임계값보다 크다면, 제 2 버퍼(400)에 저장된 구문화된 코드는 감축 스트링 매칭부(600)로 제공된다.

감축 스트링 매칭부(600)는 최대 길이로 매칭된 구문화된 코드로부터 마지막 비트를 제외한 나머지의 감축된 코드에 대하여 스트링 매칭부(200)에서와 같이 구문화를 수행하고, 구문화된 코드를 사전 데이터 저장부(100)에 저장된 구문화된 코드와 매칭을 수행한다. 감축 코드 스트링 매칭부(600)에서 매칭안된 구문화된 코드가 발생되는 경우, 매칭안된 구문화된 코드는 사전 데이터 저장부(100)에 새로이 등록된다. 감축 코드 스트링 매칭부(600)에서 구문화된 코드는 다시 제 2 버퍼(400)로 제공된 다음 인코더(700)로 출력된다.

이때, 감축 코드 스트링 매칭부(600)는 구문화된 코드를 제 2 버퍼(400)를 통하여 인코더(700)로 제공한 다음, 감축된 코드가 전송 완료되었다는 신호를 라인(650)상에 발생한다. 따라서, 제 1 버퍼(300)에 저장된 구문화된 코드가 제 2 버퍼(400)의 출력된 이후 순서적으로 인코더(700)로 제공될 수 있다.

상술한 비교부(500)와 감축 코드 스트링 매칭부(600)의 동작은 최대 길이 매칭을 이용한 구문화를 기본으로 하면서 다음 구문과의 연결을 고려하여 최대 길이로 구문화를 수행하지않는 대신 다음 구문과의 압축률 편차를 줄여주는 보상을 수행하는 것이다. 그 결과, 연속적으로 인접한 두 구문간의 압축률 편차를 줄일 수 있고, 전체적인 압축률의 변화를 거의 유발하지 없으면서 부분 압축률의 균일성을 향상시킬 수 있다.

인코더(300)는 스트링 매칭부 모듈(200)로부터 제공되는 구문화된 코드에 대응하는 어드레스 값을 사전 데이터 저장부(100)로부터 찾고, 이 어드레스 값에 대하여 압축 부호화를 수행한다. 인코더(300)에서 수행되는 압축 부호화 방식은 본 기술 분야에서 널리 알려진 이산 여현 변환(discrete cosine transform : DCT)과 가변장 부호화(variable length coding) 기법을 포함하며, 압축 부호화된 데이터 즉, 부호어(codeword)들은 전송 채널(800)을 통하여 복호화 장치(도시안됨)로 전송된다.

그러므로, 본 발명에 따라 인접한 두 구문화된 코드간의 압축률 편차를 보상함으로써 연속적으로 인접한 두 구문간의 압축률 편차를 줄일 수 있고, 전체적인 압축률은 거의 변화가 없으면서 부분 압축률의 균일성이 향상된다. 이것은 결국 전송채널을 통하여 전송되는 데이터의 균일성을 보장하게되므로, 제한된 채널 용량을 효율적으로 사용할 수 있게한다.

Claims (3)

1. 입력되는 데이터 코드 스트링에 대하여 균일한 압축률을 갖도록 압축률 편차를 보상하는 데이터 압축 시스템에 있어서,

   상기 데이터 코드 스트링에 대하여 구문화된 코드를 사전(dictuonary) 방식으로 계속적으로 등록하여 저장하는 저장수단;

   상기 데이터 코드 스트링을 구문화(parsing)하고, 상기 구문화된 코드를 상기 저장 수단에 저장된 구문화된 코드와 매칭하고, 매칭안된 구문화된 코드가 상기 저장수단에 새로이 등록되게하는 스트링 매칭부;

   상기 스트링 매칭부로부터 제공되는 구문화된 코드를 일시 저장하는 제 1 버퍼;

   상기 스트링 매칭부에서 최대 길이로 매칭된 구문화된 코드를 일시 저장하는 제 2 버퍼;

   상기 제 1 및 제 2 버퍼에 저장된 구문화된 코드들로부터 계산된 압축 편차율과 기설정 압축 편차율의 임계값을 비교하는 비교 수단;

   상기 비교 수단에서 상기 계산된 압축 편차율이 상기 기설정 임계값보다 클 때, 상기 제 2 버퍼에 저장된 최대 길이의 구문화된 코드의 마지막 비트를 제외한 나머지의 감축된 코드에 대하여 구문화하고, 상기 구문화된 코드를 상기 저장 수단에 저장된 구문화된 코드와 매칭하고, 매칭안된 구문화된 코드가 상기 저장수단에 새로이 등록되게 하는 감축 코드 스트링 매칭부;

   상기 제 1 버퍼 또는 제 2 버퍼를 통하여 제공되는 구문화된 코드에 대응하는 인덱스를 상기 저장 수단으로부터 찾아 압축 부호화를 수행하는 인코더를 포함하는 것을 특징으로하는 균일 데이터 압축률을 갖는 데이터 압축 시스템.
2. 제 1 항에 있어서, 상기 비교부에서 비교 결과 상기 계산된 압축 편차율이 상기 기설정 임계값보다 적을 때, 상기 제 2 버퍼에 저장된 최대 길이로 구문화된 코드가 상기 인코더로 제공되는 것을 특징으로하는 특징으로하는 균일 데이터 압축률을 갖는 데이터 압축 시스템.
3. 제 1 항에 있어서, 상기 감축 코드 스트링 매칭부는 상기 구문화된 코드를 상기 제 2 버퍼에 제공하고, 상기 제 1 버퍼(400)로 상기 구문화된 코드의 전송 완료를 알리는 신호를 발생하는 것을 특징으로하는 균일 데이터 압축률을 갖는 데이터 압축 시스템.

Images