일반기술

고정된 길이의 이동량을 갖는 패턴매칭 판별방법 및 그 장치

본 기술은 이전 데이터 값 중 현재 필요한 최소한의 정보를 저장하여 패턴매칭을 수행함으로서 설정된 입력 데이터 열에서 해당 패턴의 고속 검색이 가능한 고정된 길이의 이동량을 갖는 패턴매칭 판별방법 및 그 장치이다. 본 기술의 장치는 입력버퍼, 제 1저장수단, 제 2저장수단, 비교수단, 버퍼제어기로 이뤄지며, 그 방법은 다음과 같다. 제1단계에서는 입력버퍼의 하나의 비트 열을 제 1저장수단에 저장하고, 제2단계에서는 원하는 패턴과 제 1저장수단에 저장된 비트 열이 패턴매칭되지 않으면 제 1저장수단에 저장된 비트 열을 제 2저장수단에 저장하고 입력버퍼로부터 하나의 비트열을 재수신하여 제 1저장수단에 저장한다. 그리고, 제 1 및 제 2저장수단에 있는 비트 열을 비교수단에 나란히 배열하여 패턴매칭 여부를 판단한다. 일반적으로 중복성이 있는 데이터는 최대전송효율을 내기위해서 가변길이부호(VLC)를 이용하여 데이터를 압축 및 전송한다. VLC는 심볼의 발생 빈도수를 조사하여 발생률이 높은 심볼에 적은 비트를 할당하는 방식으로, 고정 길이 부호에 비하여 하드웨어가 복잡하게 구성되고, 전송오류가 잘못된 부호로 디코딩 되더라도 신속하게 감지하지 못하여 계속적으로 다음 부호에 영향을 미친다. 이에 대비하여 가변길이 부호기는 부호화된 비트 열에 고정된 길이의 특정 패턴을 갖는 동기부호를 주기적으로 삽입하는 데, 기존의 기술은 순방향 매치수와 역방향 매치수를 이용하여 고정된 이동량을 갖는 하드웨어 설계를 하였다. 따라서 1비트씩 이동하면서 동일 패턴을 검색하는 소요 시간과 전송오류 발생시 복원 시간이 길고, 하드웨어의 동작회수가 많으며, 덧셈기 등의 하드웨어가 별도로 필요하였다.. 그러나, 본 기술은 주어진 입력 데이터 열에 재동기 부호와 같이 원하는 패턴을 고속으로 찾는 방법 및 그 장치를 제공하는 기술로, 이전의 데이터 값 중 현재에 필요한 최소한의 정보를 저장하여 패턴매칭을 수행하기 때문에 하드웨어를 최적화하여 구성할 수 있고, 재동기의 고속 동작이 가능하다. 따라서, 고속처리를 요구하는 비디오 코덱, 광대역 단말, 고선명 TV, 멀티미디어 등에 이용할 수 있으며, 특히 비디오 디코더의 가변길이 부호기에 사용하는 아키텍쳐에 응용함으로서 그 적용성이 매우 크다.