KR100280497B1

KR100280497B1 - 격자구조의 이산 웨이브렛 변환 장치

Info

Publication number: KR100280497B1
Application number: KR1019980036504A
Authority: KR
Inventors: 김준태; 이용훈
Original assignee: 김영환; 현대반도체주식회사
Priority date: 1998-09-04
Filing date: 1998-09-04
Publication date: 2001-02-01
Also published as: US6539412B1; KR20000018752A

Abstract

본 발명은 한 해상레벨을 위한 격자구조 직각 대칭 필터(QMF; Quadrature Mirror Filter) 뱅크를 이용하여 전 해상레벨의 변환을 해낼 수 있는 스케일러블한 격자구조의 이산 웨이브렛 변환(DWT; Discrete Wavelet Transform) 장치에 관한 것으로, 본 발명에 따른 이산 웨이브렛 변환(DWT) 장치는 복수의 직렬 접속된 격자단(lattice stage)(PE₀,...,PE_M-1), 각 격자단 사이에 삽입된 지연조절기, 그리고 궤환된 출력 및 입력과 제1 격자단 사이에 설치된 데이터 형태 변환기(DFC; Data Form Convertor)를 포함한다. 우선 한 개의 격자구조 직각 대칭 필터(QMF) 뱅크를 가지고 전 해상레벨을 필터링 하기 위해 각 해상레벨의 연산시간을 중복이 되지 않도록 할당/결정하는 나무구조의 체계적 일정설계 방법이 본 발명에서 제공된다. 제안된 일정 설계방법에 따르면 j 해상레벨의 l 번째 연산시간을 t_j(l) 이라고 할 때, t_j(l)=2^j+2^j ^-1-1 로 나타내어지며, 이는 레벨 j의 출력은 매 2j 시간마다 계산되어 나와야 한다는 것과 레벨 j의 l 번째 계산을 위해 필요한 레벨 j-1 의 2l 번째와 2l-1 번째 출력들은 레벨 j 의 l 번째 계산 시간 전에 계산되어야 한다는 두 가지 조건을 만족한다. 그리고 설계된 일정에 따라 해상 레벨간의 데이터 전달을 맡고 있는 데이터 형태 변환기(DFC)와, 격자와 격자 사이의 데이터 지연을 조절하는 데이터 지연조절기의 구현에 있어서 필요한 레지스터 수가 해상레벨의 레벨 수와 선형관계에 있도록 한 새로운 레지스터 할당기법이 아울러 제공된다. 이로써 데이터 형태 변환기(DFC)와 지연 조절기(DCU; Delay Control Unit)를 채용한 이산 웨이브렛 변환(DWT) 장치는 해상레벨의 변화나 필터길이의 변화에 쉽게 적응할 수 있는 스케일러블한 성질을 띄게 되며, 종래의 구현방식에 견주어 필요한 하드웨어도 상당히 줄어들게 된다.

Description

격자구조의 이산 웨이브렛 변환 장치

본 발명은 이산 웨이브렛 변환(DWT)을 위한 장치에 관한 것으로, 특히 격자구조를 채택하고, 해상레벨에 대한 필요한 레지스터 수가 해상레벨과 선형관계를 갖는 격자구조의 스케일러블한 이산 웨이브렛 변환(DWT) 장치에 관한 것이다.

일반적으로 트리(tree) 구조 서브밴드 분해라고 할 수 있는 이산 웨이브렛 변환(DWT)은 계층적 신호 변환 방법이다. 이산 웨이브렛 변환(DWT)을 구성하는 각 단(stage)은 신호를 저역성분 및 고역성분으로 필터링 하는 것을 포함하며, 각각은 2 만큼 샘플링비를 감소시켜 필터링이 이루어진다.

이러한 이산 웨이브렛 변환(DWT)을 이용하는 분야는 다양하다. 예를 들면 비디오 이미지를 수신기 측에 전송하기 위해 압축하는데 사용될 수도 있고, 음성신호 전송에도 사용될 수 있다. 더욱이, 비디오 코딩 응용에 이산 웨이브렛 변환(DWT)을 사용할 경우 블록들의 경계에 기인하여 인지될 수 있는 화질저하를 제거할 수도 있다.

이산 웨이브렛 변환(DWT)을 실시간으로 사용하기 위해서는 이를 수행할 수 있게 하는, 예를 들면 대규모 집적 회로(VLSI)의 제공을 필요로 한다. 집적회로로의 실현을 가능하게 하는 많은 구현방법이 제안되어 있다. 다음에 몇 가지 종래의 예를 설명한다.

도 1 은 3-레벨(혹은 3-단) 트리 구조의 직각 대칭 필터(QMF) 뱅크에 의해 이산 웨이브렛 변환(DWT)을 수행하는 예를 도시한 것이다. 3-레벨 신호처리 시스템은 도 1(a)에 도시한 해석(analysis) 직각 대칭 필터(QMF) 뱅크를 갖는 신호 전송부(11) 및 도 1(b)에 도시한 합성(synthesis) 직각 대칭 필터(QMF) 뱅크를 갖는 신호 수신부(12)를 포함한다.

앞에서 언급한 바와 같이 신호는 많은 협대역 신호로 분해되는데, 이를 위해서 레벨 1에서 입력신호 u(n)는 전달함수 G(z)를 갖는 고역 통과 디지털 필터(13)에 의해서 고역성분과 전달함수 H(z)를 갖는 저역통과 디지털 필터(14)에 의해서 저역성분으로 분해된다. 필터 처리된 각각의 신호, 즉 디지털 필터에 의해 필터 처리된 이산 시간 신호는 1/2로 각각 다운 샘플링된다. 환원하여, 필터 처리된 이산 시간 신호에서 매 2개의 샘플값 중 하나는 제거됨을 의미한다. 이와 같이 레벨 2 및 레벨 3에서도 같은 동작이 반복되어 원신호는 결국 여러 개의 서브밴드 성분으로 분해된다. 이들은 신호 수신부(12)의 합성 직각 대칭 필터(QMF) 뱅크 내의 각 레벨의 전달함수, G'(z), H'(z)를 각각 갖는 저역 및 고역 합성필터들(15, 16)에 의해서 원신호로 환원된다. 물론 이때 샘플링비는 2배로 업 샘플링된 후에 필터 처리된다.

도 1에 도시한 바와 같이, 여기에 사용된 4 종류의 필터 G(z), H(z), G'(z) 및 H'(z)는 완전 재생 특성(perfect reconstruction property)을 가지며, 각 레벨을 구성하고 있는 필터 뱅크는 모두 같은 것으로서, 중복되어 사용되고 있음을 볼 수 있다. 또한 각 레벨에서 필터링 되는 속도가 반씩 떨어지고 있는 사실로부터 매 샘플당 계산되어야 하는 샘플 수는 레벨의 개수에 상관없이 최대 2로 국한된다. 이것은 한 개의 완전 재생 필터 뱅크만을 사용하여 여러 레벨의 계산을 행할 수 있음을 시사한다.

일반적으로, 이산 웨이브렛 변환(DWT)을 집적회로로 구현하기 위해서, 도 1의 완전 재생 필터 뱅크의 형태에 따라 다이렉트 형식의 이산 웨이브렛 변환(DWT)과, 격자구조(lattice-structured)를 사용한 이산 웨이브렛 변환(DWT)으로 대별된다.

도 2는 다이렉트 형식의 3-레벨(해상레벨이 3을 의미함) 이산 웨이브렛 변환(DWT)을 실현하는 예를 도시한 것으로, 특히 필터길이가 4인 예를 보인 것이다. 이것은 도 1에 관련하여 볼 때, 신호 송신부(11)에 대응하며, 고역통과 디지털 필터(13) 및 저역통과 디지털 필터(14)의 구체적인 예를 나타내고 있다. 도 2에서, 참조부호 17로 표시된 D는 워드 단위의 지연소자 혹은 레지스터를 나타낸다. 그리고, 도면에서 l은 이산 시간을 나타낸다.

각각의 디지털 필터(13, 14)는 4개의 FIR 필터 계수, g₀-3(n), h₀-3(n)을 갖고 있고, 4 개의 곱셈기 및 4 개의 가산기로 구성된다. 레지스터는 소정의 계산순서에 의해서 현 레벨의 출력을 저장하고 있다가 다음 레벨을 계산할 때 필요한 경우 사용하기 위해 제공된 것이다. 도 2의 구성 예는 하나의 예를 도시한 것이며, 특히 레지스터의 수를 최소화하도록 하는 알려진 설계방법에 의해 도출된 구조이다.

그러나, 이 예는 도 1의 구성을 구체적으로 실현할 수 있게 하지만, 해상레벨이 달라지거나 필터길이가 달라질 경우 재설계하여야 하며 설계가 용이하지 않은 문제가 있다. 이러한 점을 감안한 것이 도 3에 도시한 바와 같이 구성된 구조로서, 이 구조는 보다 적응형으로 설계가 가능하게 한다. 도 3이 도 2와 상이한 것은 참조부호 18과 같이 루팅망(routing network)이 채용된 점이다. 이 루팅망(18)은 레지스터 어레이 혹은 메모리 및 어드레스 발생부(AGU; Address Generation Unit)로 구현되는 것으로, 도 2의 경우보다 레지스터 수가 많이 사용되더라도 해상레벨이나 필터길이에 따른 가변성, 즉 스케일러블(scalable)한 특성을 갖도록 한 점에서 설계상에 이점이 있다.

한편, 앞에서 설명한 바와 같이, 이산 웨이브렛 변환(DWT)을 실현함에 있어서는 다이렉트 형식을 채용하는 것 외에도 다음과 같이 격자 구조의 이산 웨이브렛이 또한 제공되고 있다. 이 예를 도 4에 도시하였다. 이 예는 도 2 및 도 3과 같이 레벨 3, 필터길이 4의 예에 관한 것을 단지 격자구조로 실현한 것이며, 이 구조가 제공하는 이점은 도시된 바와 같이 두 개의 격자(19, 20)는 6개의 곱셈기와 4개의 가산기만을 필요로 하기 때문에 복잡도가 감소된다는 것이다. 격자(19, 20)간에 설치된 지연소자들로 구성된 데이터 조절기(22)는 8개의 지연기가 필요하고, 출력 x(n)가 입력 측으로 궤환된 데이터를 처리하는 데이터를 처리하는 데이터 형태 변환기(DFC), 혹은 데이터 저장기(21)는 6개의 지연기가 필요하게 된다.

그러나, 이러한 하드웨어적으로 이점이 있는 격자 구조를 채용하더라도 해상레벨을 한 레벨 증가시킬 때마다 필요한 지연기의 수가 지수함수적으로 증대하는 문제가 있다. 이것은 집적회로로 구현시 칩 면적을 증가시키는 요인으로 작용한다. 더욱이 도 2의 경우와 같이 스케일러블한 특성이 없어 필요할 때마다 설계하기가 용이하지 않는 문제가 있다.

따라서, 본 발명의 목적은 이산 웨이브렛 변환(DWT)을 실현하는 기존의 방법이 갖고 있는 문제를 해결하기 위한 것으로, 필요로 하는 하드웨어 구조를 단순화시키고, 아울러 상이한 해상레벨 및 상이한 필터길이에 대해 스케일러블한 특성을 갖고 구현할 수 있게 하는 이산 웨이브렛 변환(DWT) 구조를 제공하는 것이다.

본 발명의 목적에 따라, 이를 달성하기 위해서 본 발명에서는 이산 웨이브렛 변환(DWT)을 위한 장치에 있어서, 선택된 필터길이에 따라 연이어 설치된 것으로서, 각각이 상위 신호경로 및 하위 신호경로를 가지며, 상기 이산 웨이브렛 변환(DWT) 장치의 출력을 공급하는 복수의 제1 내지 제M의 격자단과, 상기 입력 신호의 형태를 변환하여 상기 제1 격자단에 공급하는 데이터 형태 변환 수단과, 상기 각각의 격자단 사이에 삽입된 지연 조절 수단을 포함하며,

해상레벨 j중 어느 레벨이 할당받는 시간이 t_j(1) = 2^j*1 + 2^j ^-1- 1 일 때, 상기 제M 격자단의 상위 신호경로로부터의 출력을 또한 받는 상기 데이터 형태 변환 수단은:

X는 데이터 형태 변환 수단의 입력, u(n)는 이산 웨이브렛 변환(DWT) 장치의 입력, Y는 제M 격자단의 출력, n은 이산시간, l은 임의의 숫자, U는 상위 신호경로, L은 하위 신호경로를 나타낼 때,

X₀ ^U(n)=u(n),

n = 2l일 경우,

=Y_M-1 ^U(n-2^j-1),

n = 2^j*1 + 2^j ^-1- 1일 경우,

X₀ ^L(n)=u(n-1),

n = 2l일 경우,

Y_M-1 ^U(n-2^j-1-2^j-2),

n = 2^j*1 + 2^j ^-1- 1일 경우의 관계를 갖고, 이를 만족하는 변수 유지 수단 및 신호 선택 수단을 포함하며,

상기 해상레벨 j 중 어느 레벨이 할당받는 시간이 t_j(1) = 2^j*1 + 2^j ^-1- 1 일 때, 상기 지연 조절수단의 입출력은:

X가 입력, Y가 출력을 나타낼 때,

X_i ^U(n)=Y_M-1 ^U(n)

X_i ^L(n)=Y_i-1 ^L(n-2^j),

n = 2^j*1 + 2^j ^-1- 1일 경우의 관계를 갖고, 이를 만족하는 변수 유지 수단 및 신호 선택 수단을 포함하는 격자구조의 이산 웨이브렛 변환(DWT) 장치를 제공한다.

본 발명에 대한 상기한 목적, 특징 및 효과에 대해서 첨부한 도면을 참조하여 다음의 상세한 설명으로부터 본 발명에 대해 충분히 이해될 것이다.

도 1 은 종래 3-레벨 트리 구조의 직각 대칭 필터(QMF) 뱅크에 의해 이산 웨이브렛 변환(DWT)을 수행하는 구성을 도시한 블록도.

도 2 는 종래 다이렉트 형식의 2-채널 직각 대칭 필터(QMF) 뱅크를 이용하여 3-레벨 이산 웨이브렛 변환(DWT)을 실현하는 예로서 필터 길이가 4인 예를 보인 도면.

도 3 은 종래 다이렉트 형식의 2-채널 직각 대칭 필터(QMF) 뱅크를 이용하여 3-레벨 이산 웨이브렛 변환(DWT)을 실현하는 예로서, 특히 루팅망(Routing Network)이 구비된 이산 웨이브렛 변환(DWT)을 위한 구성을 보인 도면.

도 4 는 종래의 격자구조의 2-채널 직각 대칭 필터(QMF) 뱅크를 채용하여 3-레벨 이산 웨이브렛 변환(DWT)을 실현한 것을 보인 도면.

도 5 는 본 발명에 따른 스케일러블한 격자구조의 이산 웨이브렛 변환(DWT) 장치의 구성을 도시한 블록도.

도 6 은 본 발명에 따른 일정설계에 관련한 이진 나무구조를 사용한 설계 방법을 설명하기 위한 도면.

도 7 은 본 발명에 따라, 특히 해상레벨이 3일 경우, 도 5에서 데이터 형태 변환기(DFC)에 대한 변수의 라이프 타임 차트의 예를 도시한 표.

도 8 은 본 발명에 따라, 도 7의 라이프 타임 차트를 기초하여 작성된 레지스터 할당을 보인 표.

도 9 는 본 발명에 따라, 도 8의 레지스터 할당 표에 기초한 클럭 분할 표.

도 10 은 도 8 및 도 9의 표를 참조하여 해상레벨이 3인 경우의 데이터 형태 변환기(DFC)에 대한 구체적인 구성을 보인 블록도.

도 11 은 본 발명에 따라, 특히 해상레벨이 3일 경우, 도 5에서 지연 조절기(DCU)에 대한 변수의 라이프 타임 차트의 예를 도시한 표.

도 12 는 본 발명에 따라, 도 11의 라이프 타임 차트를 기초하여 작성된 레지스터 할당을 보인 표.

도 13 은 본 발명에 따라, 도 12의 레지스터 할당 표에 기초한 클럭 분할 표.

도 14 는 도 12 및 도 13의 표를 참조하여 해상레벨이 3인 경우의 지연 조절기(DCU)에 대한 구체적인 구성을 보인 도면.

도 15 는 임의의 해상레벨 j에 대한 데이터 형태 변환기(DFC)의 구성을 도시한 도면.

도 16 은 임의의 해상레벨 j에 대한 지연 조절기(DCU)의 구성을 도시한 도면.

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

23, 23': 데이터 형태 변환기(DFC) 24, 24': 지연 조절기(DCU)

100: 이산 웨이브렛 변환(DWT) 장치

231, 231', 232, 232', 241, 241': 멀티플렉서

본 발명의 목적에 따른 바람직한 실시예를 첨부한 도면을 사용하여 다음에 설명한다.

본 발명에서 제공하는 격자구조의 스케일러블 이산 웨이브렛 변환(DWT)을 위한 구조에 대한 개략적인 것을 도 5에 블록도로 도시하였다.

도시된 바와 같이, 본 발명에 따른 격자구조의 스케일러블한 이산 웨이브렛 변환(DWT) 장치(100)는 복수의 직렬 접속된 격자단(PE₀,...,PE_M-1)과, 각 격자단 사이에 삽입된 지연 조절기(24)와, 제1 격자단(PE₀)과 입력 u(n) 및 궤환출력 s_j(l) 간에 설치된 데이터 형태 변환기(23)를 포함한다.

더욱이, 도 5에서는 입력 u(n)와 데이터 형태 변환기(24) 사이에 스케일 펙터로서의 곱셈기(s)가 설치되어 있다. 일반적으로 격자단 내에서는 도시된 바와 같이 상위 신호경로와 하위 신호경로를 서로 연결하는 신호경로 상의 2개의 곱셈기에 더하여 상기 각각의 상위 및 하위 신호 경로에도 곱셈기가 필요하나, 이는 공통된 인자를 가지므로, 곱셈기(s)는 데이터 형태 변환기(23) 앞단에 설치하여 곱셈기의 개수를 줄이기 위한 것이다.

도 5에서 M개의 격자단이 사용된 것을 도시하였으나, 이는 필터길이를 2M으로 설정했을 경우에 따른 것으로 서브밴드로 분해할 때, 보다 샤프하게 분해되게 하고자 할 때 선택될 수 있다.

본 발명에서, 예를 들면 2M개의 필터길이 및 3-레벨의 이산 웨이브렛 변환(DWT)을 본 발명의 장치를 사용하여 구현하였을 때, 각각의 격자단에 포함되는 하드웨어 구성은 종래와 동일할 수 있으나, 다음에 상세히 설명된 바로부터 알 수 있듯이 지연조절기(24)의 경우, 3개의 레지스터만이 사용되고, 데이터 형태 변환기(23)에도 3개의 레지스터만이 소요될 뿐이기 때문에, 종래의 경우보다 훨씬 적은 수의 소자가 사용되고 복잡성이 덜한 장치가 제공된다. 더욱이, 해상레벨이 증가한 경우라도 지연조절기(24) 및 데이터 형태 변환기(23)에 사용될 필요한 하드웨어가 선형적으로 증가하기 때문에, 해상레벨이 클 경우, 효율적인 장치가 된다.

다음에, 지연 조절기(24) 및 데이터 형태 변환기(23) 설계에 대해서 보다 구체적으로 설명한다.

하나의 격자형 필터뱅크를 사용하여 이산 웨이브렛 변환(DWT)의 모든 레벨을 계산하기 위해서는 "각 레벨이 어느 이산 시간에 계산되어야 한다"라고 하는 일정(schedule)이 미리 정해져 있어야 한다. 이러한 일정은 다음의 조건에 따르도록 하여 올바르게 정해져야 하며, 이에 따라 소정의 레벨을 갖는 이산 웨이브렛 변환(DWT) 장치를 설계할 수 있다.

그 조건은,

(1) 해상레벨 J에서 J중에 레벨 번호를 j로 표시할 때, 레벨 j에서 나와야 할 출력은 매 2j 시간마다 계산되어져 나와야 하며;

(2) 임의의 이산시간을 l로 표시할 때, 레벨 j-1의 2l 번째와 2l-1 번째의 출력들은 레벨 j의 n 번째 출력의 계산을 위해 궤환 되어야 하므로, 이를 위해 레벨 j-1의 2l 번째와 2l-1 번째 출력시간은 레벨 j의 l 번째 출력시간보다 앞서도록 일정이 정해져야 한다는 것이다.

이러한 일정설계에 관련하여, 본 발명에서 제공하는 이진 나무구조를 사용한 일정 설계 방법을 도 6에 도시하였다.

이산 웨이브렛 변환(DWT) 장치에 대해 레벨 수가 J라고 일반적인 상태를 가정하고, 본 발명에서는 이산 시간, 혹은 양자화된 시간 n을 짝수의 시간 2l과 홀수의 시간 2l-1로 나눈다.

먼저, J 개의 레벨 중 레벨 1이 우선적으로 수행되어야 하므로 시간 2l을 레벨 1을 수행하는 시간으로 할당한다.

그 다음 2l+1의 시간은 4l+1과 4l+3의 시간으로 나눌 수 있고, 둘 중에 2l+1로부터 가까운 쪽의 4l+1이 레벨 2의 필터링 시간으로 할당된다.

이와 같은 방식으로 도 6과 같이 레벨 J까지 시간을 각 레벨마다 할당하면 할당된 시간들, 즉 잡혀진 일정은 앞에서 언급한 조건 (1) 및 (2)을 만족할 수 있게 된다.

이들 조건으로부터 레벨 J 중 어느 레벨 j가 할당받는 시간은 다음과 같이 식(1)으로 표현될 수 있다.

t_j(l)=2^j⋅l+2^j-1-1

식(1)

이 식(1)에서 t_j(l)은 j 레벨의 l 번째 필터링을 하는 시간을 나타낸다.

격자는 2개의 신호경로를 갖는데, 하나는 U 기호를 사용하여 표시한 상위 신호경로와, L 기호를 사용하여 표시한 하위 신호경로를 갖는다. 상기 일정에 따르면 도 5에서, 마지막 격자(PE_M-1)의 출력,

Y_M-1 ^U(n)

과

Y_M-1 ^L(n)

이 제1 격자(PE₀)의 입력,

X₀ ^U(n)

및

Y₀ ^L(n)

으로서 궤환 되게 되는 입출력 관계를 얻을 수 있고 이를 수식으로 표현하면 다음의 식(2a), 식(2b)과 같다.

X₀ ^U(n)=u(n)

, n = 2l 일 경우,

=Y_M-1 ^U(n-2^j-1),

n = 2^j*1 + 2^j ^-1- 1 일 경우 식(2a)

X₀ ^L(n)=u(n-1)

, n = 2l 일 경우,

=Y_M-1 ^U(n-2^j-1-2^j-2),

n = 2^j·1 + 2^j ^-1- 1 일 경우 식(2b)

그리고, 격자와 격자사이의 입출력 관계도 다음과 같은 식3(a), 식3(b)으로 표현될 수 있다.

X_i ^U(n)=Y_i-1 ^U(n)

식3(a)

X_i ^L(n)=Y_i-1 ^L(n-2^j),

n = 2^j*1 + 2^j ^-1- 1 일 경우 식3(b)

이와 같이 하여, 도 5의 각 격자간 관계와 시간에 다라 어느 레벨이 계산되어야 하는지를 모두 정할 수 있게 된다. 그러면, 이를 바탕으로 하여 다음에 구체적인 특정한 예로서 해상레벨이 3으로 주어진 경우에 대해서 본 발명이 적용된 예를 설명한다.

해상레벨이 3일 경우, 먼저 출력 격자단과 이의 출력을 궤환한 입력간의 관계는 다음의 식(4a)과 식(4b)으로 표현될 수 있다.

X₀ ^U(n)=u(n)

n = 2l 일 경우,

=Y_M-1 ^U(n-1),

n = 4l + 1 일 경우,

=Y_M-1 ^U(n-2),

n = 8l + 3 일 경우, 식4(a)

X₀ ^L(n)=u(n-1)

n = 2l 일 경우,

=Y_M-1 ^U(n-3),

n = 4l + 1 일 경우,

=Y_M-1 ^U(n-6),

n = 8l + 3 일 경우, 식4(b)

그리고, 해상레벨이 3일 경우, 각각의 격자단간의 입출력 관계는 다음의 식5(a), 식5(b)와 같이 표현될 수 있다.

X_i ^U(n)=Y_i-1 ^U(n)

식5(a)

X_i ^L(n)=Y_i-1 ^L(n-2),

n = 2l 일 경우,

=Y_i-1 ^L(n-4),

n = 4l + 1 일 경우,

=Y_i-1 ^L(n-8),

n = 8l + 3 일 경우, 식5(b)

이와 같이, 해상레벨이 3일 경우, 도 5의 각 격자단간 시간에 다른 입출력 관계를 도출할 수 있고, 이러한 일정 설계를 행한 후, 다음에는 이들을 실제 수행함에 있어 필요한 레지스터 할당에 관련하여 소위 라이프타임 차트(lifetime chart)를 작성하도록 한다. 이 작성의 결과에 다라 해상레벨이 3일 경우 필요한 레지스터 수 역시 3 개로 만족됨을 알 수 있다. 이에 대해 다음에 구체적으로 설명한다.

각 변수가 어느 시간 동안에 필요한지에 따라 필요한 레지스터를 정할 수 있다. 이를 위한 라이프타임 차트로부터 각 시간대에 기억되어야 할 변수의 개수를 세어 그중 최대값을 지연조절기(24)나 데이터 형태 변환기(23) 구현에 필요한 최소 레지스터의 수로 정하고 각 레지스터에 변수를 할당을 행한다. 먼저, 데이터 형태 변환기(23)의 설계과정에 대해서 설명한다.

도 7은 특히 해상레벨이 3일 경우, 상기한 식(4a), 식(4b)에 근거하여 도 5에서 데이터 형태 변환기(23)에 대한 변수의 라이트 타임 차트의 예를 도시한 것이다.

격자단의 상위 신호경로에 대해서는 데이터 형태 변환기(23)에 대해 상기한 식(4a)의 관계가 적용되고, 하위 신호경로에 대해서는 데이터 형태 변환기(23)에 대해 식(4b)의 관계가 적용된다.

먼저 상위 신호경로에 관련하여, 식(4a)을 참조하면, 시간 n이 0에서 시작하여 1 단위씩 이산적으로 증가할 때, 궤환된 값이 유지되어야 하는 기간, 즉 증가된 n값 중 어느 값에서 유지되었던 값이 사용되어 제1 격자단의 상위 신호경로로 제공될 것인가에 따라 라이프타임 차트가 작성될 수 있다.

식(4a)에서, N이 짝수인 시간에는 입력 u(n)가 그대로 사용되므로 저장할 변수가 없으며, 이산 시간 n이 4l+1인 1, 5, 9,...와 같은 시간에서는 바로 전의 궤환된 값이 사용되므로 하나의 변수가 한 단위 시간 동안 저장될 필요가 있으며, 이산 시간 n이 8l+3인 3, 11, 19,...와 같은 시간에서는 그 시간에서 2단위 전의 궤환된 값이 사용되므로 변수가 2단위 시간 동안 저장될 필요가 있음을 알 수 있다.

따라서, 도 7의 라이프타임 차트를 보면, 상위 신호경로에 대해 이산시간 n이 1, 5, 9,...에서는 출력 격자(PE_M-1)로부터 온 출력값이 1 단위 이전의 값을 저장하고 있기 위한 변수 s¹(0), s¹(2), s¹(4),...이 사용된다. s기호는 도 5를 참조한다. 또한 상위 신호경로에 대해 n이 3, 11, 19,...에서는 출력 격자(PE_M-1)로부터 온 출력값이 2 단위 이전의 값을 유지하기 위한 변수 s²(0), s²(2), s²(4),...이 사용된다.

다음에 하위 신호경로에 관련하여, 이때에는 식(4b)이 사용되어야 하므로, 상기한 바와 같은 마찬가지 방식으로, n이 1, 5, 9,...에서는 출력 격자(PE_M-1)로부터 온 출력값이 3 단위 이전의 값을 유지하기 위한 변수 s¹(1), s¹(3), s¹(5),...이 사용되고, n이 3, 11, 19,...에서는 출력 격자(PE_M-1)로부터 온 출력값이 6 단위 이전의 값을 유지하기 위한 변수 s²(1), s²(3), s²(5),...이 사용된다.

이들의 관계를 상위 및 하위 신호경로 모두의 경우를 포함한 도 7과 같이 종축의 이산 시간 n에 대해서 각 변수의 라이프타임을 화살표 길이로 표시할 수 있다 그러면 도 7의 우측 칼럼과 같이 해당 이산 시간에서 필요한 변수의 개수를 산출할 수 있다. 이것으로부터 최대 변수 개수는 3개임을 알 수 있고, 이는 해상레벨 3에 관련한다.

그러면, 이 라이프타임 차트 근거로 하여, 도 5에서 데이터 형태 변환기(23)를 하드웨어적으로 구성하기 위해 도 8과 같이 각 레지스터에 변수를 할당한다. 할당하는 방법은 다음과 같다.

임의의 시간대에 들어온 입력을 비어있는 레지스터에 할당하고, 저장된 값이 필요 없게 되는 시간까지 그 할당된 레지스터에 저장된 데이터를 계속 저장하고 있도록 하는 방식으로 도 8의 레지스터 할당 표가 작성될 수 있다. 즉, 도 7에서 필요한 레지스터는 3개이므로 도 8에서 레지스터, R1, R2, R3이 사용된다. 도 7에서 시간 N=1에서는 s¹(0)이 필요하다, 이를 위해서 도 8의 제1 레지스터(R1)에 s¹(0)이 1 단위 시간 저장된다. 또한 n=3에서는 s²(0)가 필요하다, 이를 위해서 도 8에서 다시 제1 레지스터(R1)에 s²(0)가 2 단위 시간 동안 저장되었음을 알 수 있다. 이와 같이 도 7을 참조로 도 8의 레지스터 할당표를 작성할 수 있다. 이것은 하드웨어 구성을 실현할 수 있게 한다.

그 다음에는 입력으로부터 할당된 레지스터에 저장되기 시작하는 첫 시간에 클럭을 인가함으로써 올바른 로딩이 이루어지게 해야 하는데, 이를 위해서 본 발명과 같이 도 9의 클럭 분할표를 작성하여 두면 하드웨어 구현이 보다 용이해 질 수 있다. 도 9는 도 8을 참조하여 각 레지스터의 클럭이 인가되는 시기를 정한 것이므로 상세한 설명은 생략한다.

도 8 및 도 9의 표를 참조하여 해상레벨 3인 경우의 데이터 형태 변환기(23)에 대한 구체적인 구성을 도출할 수 있다. 이를 도 10에 도시하였다.

도 10은 해상레벨 3인 경우, 데이터 형태 변환기(23)에 대해 도 8 및 도 9를 참조로 하여 구성된 것을 도시한 것으로, 도시된 바와 같이 3개의 레지스터(R1, R2, R3)가 사용됨을 보이고 있다. 도면에서 2l+0, 2l+1,... 등등은 그 해당시간에 해당 멀티플렉서(231, 232)로 보낸다는 것을 나타내고, 레지스터의 경우에는 그 해당시간에 클럭이 인가됨을 나타낸다.

도 10과 같이 구현된 데이터 형태 변환기(23)는 도 5에 적용될 수 있다.

상기한 예는 해상레벨이 3인 경우에 변수를 저장하여 사용하기 위한 3개의 레지스터가 사용됨을 예시하고 있다. 그러나, 본 발명은 해상레벨이 3인 경우만을 위한 것이 아니며, 이것으로 한정되지 않는다. 해상레벨이 4 이상 임의의 것이라도 상기한 바와 같은 원리에 의해 도 10과 같은 바람직한 데이터 형태 변환기(23)를 구현할 수 있다. 이것은 식(2)로부터 시작하여 요구하는 해상레벨에 대해 식(4a) 및 식(4b)과 같은 형태를 도출할 수 있고, 이에 근거하여 앞에서 설명한 방식대로 설계되는 것이다. 이에 따라 본 발명에서는 해상레벨이 증가해도 필요한 레지스터 수가 선형적으로 사용되게 하나.

다음에, 해상레벨이 3인 경우의 식(5)을 근거하여 지연 조절기(24)를 설계하는 과정을 설명한다.

도 11은 특히 해상레벨이 3일 경우, 상기한 식(5a) 및 식(5b)에 근거하여 도 5에서 지연 조절기(24)에 대한 변수의 라이프타임 차트의 예를 도시한 것이다.

상위 신호경로에 대해서는 지연 조절기(24)에 대해 상기한 식(5a)의 관계가 적용되고, 하위 신호경로에 대해서는 지연 조절기(24)에 대해 식(5b)의 관계가 적용된다.

식(5a)에서, 상위 경로의 경우 임의의 n 시간에 입력이 그대로 사용되므로 저장할 변수가 없다.

다음에 하위 신호 경로에 관련하여, 이때에는 식(5b)이 사용되어야 하므로, 이산 시간 n이 2, 4, 6,...에서는 이전 격자로부터 온 출력값이 2 단위 이전의 값을 유지하기 위한 변수 a, c, e, g, i,...가 사용되고, n이 1, 5, 9, 13,...에서는 이전 격자로부터 온 출력값이 4 단위 이전의 값을 유지하기 위한 변수 b, f, j,...가 사용되고, n이 3, 11, 19,...에서는 이전 격자부터 온 출력값이 8 단위 이전의 값을 유지하기 위한 변수 d, l,...이 사용된다.

이들의 관계를 도 11과 같이 종축의 이산시간 n에 대해서 각 변수의 라이프타임을 화살표 길이로 표시할 수 있으며, 그러면 도 11의 우측 칼럼과 같이 해당 이산시간에서 필요한 변수의 개수를 산출할 수 있다. 이것으로부터 최대 변수 개수는 3개임을 알 수 있고, 이는 해상레벨 3에 관련한다.

그러면, 이 라이프타임 차트를 근거로 하여, 도 5에서 지연 조절기(24)를 하드웨어적으로 구성하기 위해 도 12와 같이 각 레지스터에 변수를 할당한다. 할당하는 방법은 앞에서 이미 설명한 바와 같이, 임의의 시간대에 들어온 입력을 비어있는 레지스터에 할당하고, 저장된 값이 필요 없게 되는 시간까지 그 할당된 레지스터에 저장된 데이터를 계속 저장하고 있도록 하는 방식으로 하여 도 12의 레지스터 할당표가 작성될 수 있다. 즉, 도 12에서 필요한 레지스터는 3개이므로 레지스터(R1, R2, R3)가 사용된다. 도 11에서 시간 n=2에서는 a가 필요하다. 이를 위해서 도 12의 제1 레지스터(R1)에 a가 2 단위 시간 저장된다. 또한 n=4에서는 c가 필요하다. 이를 위해서도 도 12에서 다시 제1 레지스터(R1)에 c가 2 단위 시간 동안 저장되었음을 알 수 있다. 이와 같이 도 11을 참조로 도 12의 레지스터 할당표를 작성할 수 있다. 그 다음에는 입력으로부터 할당된 레지스터에 저장되기 시작하는 첫 시간에 클럭을 인가함으로써 올바른 로딩이 이루어지게 해야 하는데, 이를 위해서 본 발명과 같이 도 13의 클럭 분할표를 작성하여 두면 하드웨어 구현이 보다 용이해 질 수 있다.

도 11 및 도 12의 표를 참조하여 해상레벨 3인 경우의 지연 조절기(24)에 대한 구체적인 구성을 도출할 수 있다. 이를 도 14에 도시하였다.

도 14는 해상레벨이 3인 경우 지연 조절기(24)에 대해 도 12 및 도 13을 참조로 하여 구성된 것을 도시한 것으로, 도시된 바와 같이 3개의 레지스터(R1, R2, R3)가 사용됨을 보이고 있다. 도면에서 2l+0, 2l+1,... 등등은 그 해당시간에 해당 멀티플렉서(241)로 보낸다는 것을 나타내고, 레지스터의 경우에는 그 해당시간에 클럭이 인가됨을 나타낸다.

도 14와 같이 구현된 지연 조절기(24)는 도 5에 적용될 수 있다.

상기한 예는 해상레벨이 3인 경우에 변수를 저장하여 사용하기 위해 3개의 레지스터가 사용됨을 예시하고 있다. 그러나, 본 발명은 해상레벨이 3인 경우만을 위한 것이 아니며, 이것으로 한정되지 않는다. 해상레벨이 4 이상 임의의 것이라도 상기한 바와 같은 원리에 의해 도 14와 같은 바람직한 지연 조절기(24)를 구현할 수 있다. 이것은 식(3)으로부터 시작하여 요구하는 해상레벨에 대해 식(5)과 같은 형태를 도출할 수 있고, 이에 근거하여 앞에서 설명한 방식대로 설계되는 것이다. 이에 따라 본 발명에서는 해상레벨이 증가해도 필요한 레지스터 수가 선형적으로 사용되게 한다.

이러한 특정 예를 일반화시켜, 여기 개시된 과정을 임의의 해상레벨 J에 대한 지연조절기(24') 및 데이터 형태 변환기(23')의 구성 예를 도 15 및 도 16에 도시하였다.

도 5에서 데이터 형태 변환기(DFC)에 대한 특정의 예가 아닌 이들을 포함하는 일반적인 구성을 도 15에 도시하였다. 데이터 형태 변환기(23')는 도시된 바와 같이, 다음의 지연 조절기(24')의 구성과 유사하게 병렬로 배치된 제1 그룹의 복수의 레지스터(R1,...,R[(J-1)/2]), 이의 출력을 선택적으로 출력하기 위한 멀티플렉서(231'), 병렬로 배치된 제2 그룹의 복수의 레지스터(D, R₁,...,R_J-1) 및 이의 출력을 선택적으로 출력하기 위한 또 다른 멀티플렉서(232')로 구성된다.

이들 도면에서 멀티플렉서 앞에 기입된 2l+0, 4l+1, 8l+3의 의미는 각각의 선택되는 시간을 나타낸다. 예를 들면, n을 0, 1, 2,...이라 할 때, n=2l은 짝수 번째 시간을 뜻하므로 이 시간에 입력된 값을 멀티플렉서의 출력으로 내보내는 것이다. 또한 레지스터의 클럭(ck)의 입력으로 기입된 2l+1, 4l+2, 8l+2의 의미는 시간 n이 그 시간에 해당할 경우, 그 시간에 해당 레지스터에 클럭(ck)을 인가함을 의미한다. 그리고, 격자의 위쪽의 입출력은 U 윗첨자를 사용하여 표기되었고, 격자의 아래쪽의 입출력은 L 윗첨자를 사용하여 표기되어 각각의 입출력은 u(n),

Y_M-1 ^L(n)

,

X₀ ^U(n)

,

X₀ ^L(n)

으로 표기되었다.

도 5에서 지연 조절기(DCU)에 대한 특정의 예가 아닌 이 예를 포함하는 일반적인 구성을 도 16에 도시하였다. 지연 조절기(24')는 도시된 바와 같이, 병렬로 배치된 복수의 레지스터(R1,..., RJ) 및 이들의 출력을 선택적으로 출력하기 위한 하나의 멀티플렉서(241')로 구성된다. 이 지연 조절기(23')는 도 5에서 각각의 지연 조절기(DCU)마다 동일한 형태로 설치된다.

이러한 구성으로부터 알 수 있듯이, 지연 조절기(DCU) 및 데이터 형태 변환기(DFC)의 구조는 규칙적이고 또한 모듈화 될 수 있기 때문에 시스템의 설계에 따라 쉽게 가변되어 설계될 수 있는 이점을 제공한다.

도 15에서 R_J-1및 도16에서 R_J로 표시된 바로부터 알 수 있듯이 본 발명에 따라 레지스터의 개수는 해상레벨 J에 선형적인 관계가 있음을 알 수 있다. 이것은 종래의 지수함수적으로 증가하는 경우에 현격히 비교되는 것이다. 더욱이, J가 증가하더라도 설계를 용이하게 할 수 있게 한다.

본 발명에 따라 이산 웨이브렛 변환(DWT)은 격자구조를 근간으로 하고 있기 때문에 일반적인 FIR 방식의 직각 대칭 필터(QMF) 뱅크에 비해 그 자체에서 덧셈기와 곱셈기를 거의 1/2 정도로 줄일 수 있다.

더욱이, 지연 조절기(DCU)와 데이터 형태 변환기(DFC)도 최소의 개수만의 레지스터로 구현이 가능하므로 해상레벨의 증가에 따른 레지스터 수의 지수함수적 증가는 없다. 이는 VLSI 칩의 면적을 상당히 줄일 수 있다.

더욱이, 본 발명의 구조는 스케일러블한 특성을 제공하므로 임의의 시스템 요구조건, 즉 해상레벨이나 필터의 길이의 변화에 대해서도 쉽게 설계할 수 있다.

본 발명에 따른 이산 웨이브렛 변환(DWT) 구조는 스케일러블한 특성을 갖게 하면서 격자 구조(100)에 따른 하드웨어상의 이점을 제공한다. 본 발명에서 제공하는 설계방법에 따라 필요로 하는 해상레벨 및 필터길이를 갖는 효율적인 이산 웨이브렛 변환(DWT) 구조가 실현될 수 있다. 이 분야의 통상의 지식을 가진 자는 이러한 본 발명에 따른 이산 웨이브렛 구조를 사용하여 이미지 압축이나 음성 전송 등에 효과적으로 사용할 수 있음을 알 것이다.

Claims

이산 웨이브렛 변환을 위한 장치에 있어서,

선택된 필터길이에 따라 연이어 설치된 것으로서, 각각이 상위 신호경로 및 하위 신호경로를 가지며, 상기 이산 웨이브렛 변환 장치의 출력을 공급하는 복수의 제1 내지 제M 의 격자단과,

상기 입력 신호의 형태를 변환하여 상기 제1 격자단에 공급하는 데이터 형태 변환 수단과,

상기 각각의 격자단 사이에 삽입된 지연 조절 수단을 포함하며,

해상레벨 j 중 어느 레벨이 할당받는 시간이 t_j(l) = 2^j·l + 2^j-1- 1 일 때, 상기 제 M 격자단의 상위 신호경로로부터의 출력을 또한 받는 상기 데이터 형태 변환 수단은,

X는 데이터 형태 변환 수단의 입력, u(n)는 이산 웨이브렛 변환(DWT) 장치의 입력, Y는 제M 격자단의 출력, n은 이산시간, l은 임의의 숫자, U는 상위 신호경로, L은 하위 신호경로를 나타낼 때,

X₀ ^U(n)=u(n) , n = 2l 일 경우,

=Y_M-1 ^U(n-2^j-1), n = 2^j*1 + 2^j ^-1- 1 일 경우

X₀ ^L(n)=u(n-1) , n = 2l 일 경우,

=Y_M-1 ^U(n-2^j-1-2^j-2), n = 2^j·1 + 2^j ^-1- 1 일 경우의 관계를 갖고, 이를 만족하는 변수 유지 수단 및 신호 선택 수단을 포함하며,

상기 해상레벨 j 중 어느 레벨이 할당받는 시간이 t_j(l) = 2^j·l + 2^j-1- 1 일 때, 상기 지연 조절 수단의 입출력은,

X 가 입력, Y 가 출력을 나타낼 때,

X_i ^U(n)=Y_i-1 ^U(n)

X_i ^L(n)=Y_i-1 ^L(n-2^j), n = 2^j*1 + 2^j ^-1- 1 일 경우의 관계를 갖고, 이를 만족하는 변수 유지 수단 및 신호 선택 수단을 포함하는 것을 특징으로 하는 격자구조의 이산 웨이브렛 변환 장치.
제1 항에 있어서, 상기 데이터 형태 변환 수단의 변수 유지 수단은 상기 입력 u(n)와 제M 격자단의 출력을 받아 각각 소정 시간 동안 유지하는 복수의 레지스터를 포함하며,

상기 신호 선택 수단은 상기 레지스터의 출력을 선택적으로 제1 격자단의 상위 신호경로에 공급하기 위한 제1 멀티플렉서와,

상기 레지스터의 출력을 선택적으로 제2 격자단의 상위 신호경로에 공급하기 위한 제2 멀티플렉서를 포함하는 것을 특징으로 하는 격자구조의 이산 웨이브렛 변환 장치.
제1 항에 있어서, 상기 지연 조절 수단은 앞단의 격자단의 출력을 받아 각각 소정 시간 동안 유지하는 복수의 레지스터를 포함하며,

상기 신호 선택 수단은 상기 레지스터의 출력을 선택적으로 다음 격자단의 하위 신호경로에 공급하기 위한 멀티플렉서를 포함하는 것을 특징으로 하는 격자구조의 이산 웨이브렛 변환 장치.
제2 항에 있어서, 상기레지스터의 수는 해상레벨의 레벨에 따라 선형적으로 증가하는 것을 특징으로 하는 격자구조의 이산 웨이브렛 변환 장치.
제1 항에 있어서, 상기 변수 유지 수단 및 신호 선택 수단은,

해상레벨 j 중 어느 레벨이 할당받는 시간이 t_j(1) = 2^j·l + 2^j-1- 1 이고, X는 데이터 형태 변환 수단의 입력, u(n)는 이산 웨이브렛 변환 장치의 입력, Y는 제M 격자단의 출력, n은 이산시간, l은 임의의 숫자, U는 상위 신호경로, L은 하위 신호경로를 나타낼 때,

X₀ ^U(n)=u(n) , n = 2l 일 경우,

=Y_M-1 ^U(n-2^j-1), n = 2^j*1 + 2^j ^-1- 1 일 경우

X₀ ^L(n)=u(n-1) , n = 2l 일 경우,

=Y_M-1 ^U(n-2^j-1-2^j-2), n = 2^j·1 + 2^j ^-1- 1 일 경우의 관계를 갖고, 이를 만족하는 제1 변수 유지 수단 및 제2 신호 선택 수단과,

상기 각각의 격자단 사이에 삽입되는 것으로서, 상기 해상레벨 j 중 어느 레벨이 할당받는 시간이 t_j(l) = 2^j·l + 2^j-1- 1 일 때, 상기 지연 조절 수단의 입출력은,

X 가 입력, Y 가 출력을 나타낼 때,

X_i ^U(n)=Y_i-1 ^U(n)

X_i ^L(n)=Y_i-1 ^L(n-2^j), n = 2^j*1 + 2^j ^-1- 1 일 경우의 관계를 갖고, 이를 만족하는 제2 변수 유지 수단 및 제2 신호 선택 수단을 포함하는 것을 특징으로 하는 격자구조의 이산 웨이브렛 변환 장치.
제5 항에 있어서, 상기 제2 변수 유지 수단은 앞단의 격자단의 출력을 받아 각각 소정 시간 동안 유지하는 복수의 레지스터를 포함하며,

상기 제2 신호 선택 수단은 상기 레지스터의 출력을 선택적으로 다음 격자단의 하위 신호경로에 공급하기 위한 멀티플렉서를 포함하는 것을 특징으로 하는 격자구조의 이산 웨이브렛 변환 장치.