Upsampling using Zero-Padding and Interpolation Filter

Upsampling

어떤 신호의 Sampling Rate을 올려주는 것을 Upsampling이라고 한다. (반대로 Sampling Rate을 낮추는 것을 Downsampling이라고 한다.)

아래 그림의 왼쪽에 있던 낮은 sampling rate을 가지는 신호를 오른쪽 그림처럼 높은 sampling rate을 가지도록 만들어 주는 작업이다.

출처: http://simplemachines.it/martin/mizar32/1.6.0-AT32UC3/APPLICATIONS/EVK1104-EVK1105-DSPLIB-DEMO/DOC/html/filtering_interpolation.gif

 

Upsampling 하는 이유

Upsampling을 하는 이유는 여러 가지가 있을 수 있는데 몇 가지를 나열해 보면 다음과 같다.

1. Sampling Rate 변환 자체가 목적인 경우

   예) Block A의 출력은 fs인데, 그 뒤에 붙어있는 Block B에 들어가야 할 데이터의 sampling rate은 4fs가 되는 경우

2. 좀 더 Smooth한 신호가 필요한 경우

   예) 위 그림에서 보면, 왼쪽의 그림 보다 오른쪽 그림의 신호가 더 smooth하고 연결성이 좋은 것을 알 수 있다.

3. 입력된 신호의 샘플과 샘플 사이 중간 값이 필요한 경우

   예) 위 그림에서 보면, 왼쪽의 원래 sampling 위치 중간에 데이터들이 만들어진 것을 알 수 있다. 이 중간에 데이터들 자체가 필요한 경우이다.

 

Upsampling 방법

Upsampling을 하는 방법 중에 가장 간단한 방법은 Zero Padding을 하고 Interpolation Filter를 걸어주는 방법이다.

개념적으로 다음과 같다

원래 fs였던 sampling rate을 4fs로 올려주는 과정을 보여주는 그림이다.

출처: http://soundev.tistory.com/108

 

여기에서 Interpolation Filter는 다름 아닌 Low-pass Filter이다. 왜 Low-pass Filter가 필요한지는 아래 그림의 주파수 영역 그림을 보면 쉽게 이해할 수 있다.

 

출처: http://flylib.com/books/en/2.729.1.101/1/

 

위 그림에 대한 설명은 다음과 같다.

1. Upsampling 하기 전의 데이터와 주파수 spectrum을 보여주고 있다. Sampling Rate는 f_old이다. Nyquist frequency인 f_old/2 이후부터는 주파수 Spectrum이 계속해서 복사된다.
2. Upsampling을 위해서 zero-padding을 수행한 결과 이다. 중간에 0을 3개씩 넣었으므로, sampling rate이 4배 증가 했다. Sampling rate이 4배 증가 했는데, 원래 복사된 주파수 Spectrum이 그대로 남아 있으므로 aliasing이 일어나게 된다.
3. Interpolation Filter (Low-pass Filter)를 통한 결과이다. 원래 표현 가능했던 f_old/2에 해당하는 데이터만 남기고 나머지 aliasing데이터들은 제거했다.

    

 

Interpolation Filter의 설계

그러면 Interpolation Filter는 어떤 것을 쓰면 될까?

그냥 Gaussian Filter나 Moving Average Filter를 쓰면 될까? Cutoff는 어떻게 하면 될까?

그냥 위의 그림처럼 구현하면 Upsampling이 실제로 잘 될까?

 

실제로 실험을 해보면서 생각해보자

 

 

입력 신호

아래와 같은 신호가 있다고 하자. 왼쪽은 시간 축 (Time Domain)에서 그린 것이고, 오른쪽은 주파수 축 (Frequency Domain) 에서 Magnitude Spectrum을 그린 것이다.

(주파수축의 단위는 sampling rate로 normalize 되었다. 즉 범위는 -0.5f_s ~ 0.5f_s 이다.)

 

 

Zero-Padding

이것을 4배로 Upsampling 한다고 하고 Zero-padding을 하면 다음과 같다. 예상대로 aliasing이 일어나서 같은 Spectrum이 반복되는 것을 볼 수 있다.

 

 

Low-pass Filter

자 그럼 여기에서 마지막으로 low-pass filter를 zero-padding 된 신호에 적용해 주면 된다.

 

먼저 적당한 Filter를 설계 해보자.

주파수 밴드가 4배 늘어났다. 즉 원래 0.5f_s에 있던 신호가 이제는 0.5/4f_s = 0.125f_s에 있게 된 것이다. 따라서 이상적인 interpolation filter로서의 cutoff는 0.125f_s이다.

또한, zero-padding 된 신호의 주파수 spectrum에서 aliasing 된 신호의 세기와, 가장 낮은 신호의 세기 차이는 대략 30 [dB]이다. 따라서 filter의 stopband attenuation은 최소한 30 [dB]가 되어야 한다.

 

 

Filter 예시 1

먼저 다음과 같은 low-pass Filter를 생각해 보자. (Scipy의 firwin 함수를 이용해서 9-tap, hamming window, cutoff=0.125 의 파라미터를 이용해서 만들었다.)

위에서 stopband attenuation은 최소한 30 [dB]가 되어야 한다고 했는데, 이 filter는 0.3f_s가 다 되어서야 그 값에 근접하기 시작한다.

따라서 충분히 aliasing을 제거 하지 못하게 될 것이다.

 

 

위의 필터를 적용한 결과는 다음과 같다. 예상한대로 0.25f_s 영역의 aliasing을 충분히 제거 하지 못했고, 이 때문에 시간축 신호를 보면 oscillation이 일어나는 것을 알 수 있다.

즉, interpolation filter가 충분히 잘 설계되지 못하면, 제대로 된 interpolation 결과를 얻기 힘들게 되는 것이다.

 

 

 

Filter 예시 2

그러면 좀더 filter의 tap수를 늘려서 stopband attenuation이 충분하도록 설계를 해보자. 아래 filter는 위 filter에서 tap만 16으로 늘인 것이다.

Stopband attenuation이 0.2f_s부터 -30[dB]에 가까운 것을 알 수 있다.

 

 

위의 필터를 적용한 결과는 다음과 같다.

 

Aliasing 주파수의 신호들이 다 잘 제거 되었으며, 이에 따라 시간 축에서도 oscillation이 거의 보이지 않는다.

 

 

게인 보상

그런데 문제는 신호의 크기 이다.

Upsampling된 신호와 원래 신호를 다시 비교해 보자.

 

원래 신호에 비해서 interpolation 이후의 신호의 값이 너무나 작아졌다.

맨 위의 개념을 설명하는 그림에 보면 신호의 크기는 유지 되면서 중간의 값들이 생기는 것으로 나타났는데, 이상하게 이 결과는 신호의 크기가 줄어들어 버렸다.

이론대로 했는데 뭐가 잘못된 건가?

 

Interpolation filter전과 후의 주파수 spectrum을 비교해보자.

Filter 전에는 봉우리가 총 4개가 있다. (-0.5에 반 개, -0.25에 한 개, 0에 한 개, 0.25에 한 개, 0.5에 반 개)

그리고 filter 후에는 봉우리가 1개가 있다.

다시 말해서 Filter에 의해서 원래 4개였던 봉우리가 1개로 줄어든 것이고, 이것은 즉 신호의 에너지가 4분의 1로 줄어들었다는 것을 의미한다.

따라서 원래 신호의 크기를 유지하기 위해서는 이렇게 4분의 1로 줄어든 것을 보상해주어야 한다. 즉, 다시 말하면 interpolation 배율만큼 보상해 주면 된다.

 

그러면 결과적으로 다음과 같은 신호를 얻을 수 있고, 원본 신호와 비슷한 크기 (amplitude)를 가지는 결과를 얻을 수 있다.

 

여기에서 신호의 마지막 부분에서 신호의 값이 0으로 떨어지는 현상을 볼 수 있는데, 이것은 interpolation filter와 convolution 연산을 할 때 boundary 처리를 해주지 않아서 나타나는 transient response라고 볼 수 있다.

Filter의 길이가 길면 길수록 이 현상이 더 커지게 된다.

 

 

Filter 예시 3

위의 필터 2의 경우 충분히 좋은 결과를 보여주고 있으나, 문제는 filter의 길이가 16-tap으로 길다는데 있다.

Application이나 상황에 따라 다르지만, 길이가 16-tap인 filter를 적용하는 것은 상당히 높은 연산량을 필요로 하며, transient response 또한 길어지게 된다.

연산량은 작으면서 interpolation을 잘 할 수 있는 filter는 어떤 것일까?

 

다시한번 zero-padding된 신호를 들여다 보자. Aliasing이 일어난 봉우리 들이 일정한 간격으로 반복되고 있다.

 

 

그리고, Moving average filter를 생각해보자. Moving average filter는 rectangular window 또는 boxcar filter라고도 불린다.

Moving average filter는 시간축에서 rectangular function이고, 시간축에서 rectangular function은 주파수축에서 sinc function이다.

그런데 이 sinc function은 특이한 성질이 하나 있는데, 함수의 값이 일정한 주기로 0을 지난다. 이점을 zero-crossing point 또는 null point라고 이야기 한다.

출처: https://en.wikipedia.org/wiki/Rectangular_function

 

여기에서 생각해볼 수 있는 것은 "moving average filter를 잘 조절해서 저 null point와 aliasing된 봉우리들을 잘 맞추면 저 봉우리들을 쉽게 제거할 수 있지 않겠는가?" 이다.

 

다음은 4-tap moving-average filter의 주파수 spectrum 이다. 이것을 다시 위의 zero-padding된 신호의 주파수 spectrum과 나란히 놓고 보면 filter의 null point와 신호의 aliasing 봉우리의 위치가 같다는 것을 알 수 있다.

 

이것은 일반화를 할 수 있다. 즉, n배 upsampling의 aliasing 봉우리의 위치와 n-tap moving average filter의 null point는 항상 같다.

 

n-tap moving average filter를 이용한 interpolation filtering 결과는 다음과 같다. Aliasing 위치에 있는 주파수 성분들이 완벽하게 제거된 것을 알 수 있다.

 

다만, 시간 축에서 보면 신호들이 smooth 하지 않고, 계단형태로 나타난 것을 알 수 있다. 이것은 moving average filter가 notch filter처럼 aliasing이 일어난 위치에 대해서만 filter를 수행하고 나머지 고주파 성분들을 제거하지 않았기 때문이라고 볼 수 있다.

하지만 4-tap 이라는 작은 길의 필터를 사용함으로 해서 연산량이 줄어들게 될 수 있으며, transient response의 길이 또한 매우 짧다는 이점이 있다.

 

 

 

결론

1. Zero-padding과 Interpolation Filter를 이용하면 간단히 어떤 신호를 Upsampling 할 수 있다.
2. Interpolation Filter를 잘 설계 해야만 제대로 된 Upsampling을 할 수 있다.
3. Upsampling 이후에 원래 신호와 동일한 크기의 결과 신호를 얻기 위해서는 보상을 해주어야 한다.
4. N배 Upsampling의 경우 N-tap Moving Average Filter를 이용하면 경제적으로 Interpolation Filtering을 수행할 수 있다.

 

 

위 그림들을 만드는 python 코드는 다음의 github repository에 업로드 되어있다.

https://github.com/jihankim/interpolationFilterExample