2019년 5월 13일 월요일

Signal Processing For Communications (9-1)

모든 textbook들은 보통 재미있는 부분이 가장 뒷 chapter에 몰려있고, 여기서 할 얘기를 위해 필요한 도구들을 소개하느라 공부하는 사람의 진을 다 빼곤합니다. 학문적 측면에서 그리고 완결된 설명을 위해서는 이런 방식의 presentation이 맞는 것이겠으나 개인적으로는 앞 부분에서 지루한 내용들만 쭉 이어지는 형태가 불만이었습니다.

도대체 무엇을 위해 이런 지루한 내용들을 배워야하는지도 알려주지 않은 채로 학습 과정을 따라가야 하는 경우, 지친 나머지 정작 중요한 내용에 갈 때쯤엔 (심지어는 학기 중 진도가 느려져서 가지도 못하고!) 힘이 다 빠져서 아무래도 좋을 상태가 되곤 했는데요.

그래서 이번에는 제 마음대로 가장 뒤에 챕터에서 우리가 어떤 것을 알기 위해 이 모든 지루한 얘기들을 배우는 것인지를 먼저 확인한 후, 그 내용을 더 제대로 이해하기 위해 필요한 도구들을 살피러 앞으로 돌아오는 순서로 소개를 해볼까 합니다.

이 방식이 싫으시다면, 목차 자체는 일반적인 학습 순서대로 되어있으니 이 글타래가 완성된 이후, 순서대로 읽으시면 되겠습니다.

Interpolation and Sampling


이전 글에서 continuous-time과 discrete-time 신호 간의 간극에 대한 논의를 짧게 한 바 있습니다. 간단히 말해 interpolation과 sampling은 정보 손실 없이 continuous-time과 discrete-time, 이 두 세계 사이를 오가는 방법에 대한 이야기입니다.

Interpolation은 discrete-time 신호를 continuous-time 신호로 바꿀 때 사용하는데요. Interpolation이 중요한 이유는 아날로그 시스템인 우리 인간이 인지할 수 있는 신호의 형태가 결국 아날로그이기 때문입니다. 또한 전자기기에 사용되는 아날로그 회로를 가장 잘 모델링 하는 방법이 real variable에 대한 함수, 즉 continuous-time 함수로 표현하는 것이기 때문이기도 합니다.

Sampling은 반대로 continuous-time 신호를 discrete-time 신호로 바꿀 때 사용하는 방법이죠. 가장 간단한 sampling 방식은 일정 주기로 반복하여 기록을 하는 것이 되겠습니다. Sampling 방법은 random부터 radial 등 여러가지가 있지만, 가장 간단한 방식이 uniform한 주기 $T_s$로 샘플을 얻는 uniform sampling이며 여기서는 이를 기준으로 설명을 하겠습니다. 중요한 것은 어떤 sampling 방식이든 관계없이 continuous-time의 임의의 값과 해당하는 discrete-time 수열의 점(points) 사이에는 언제나 어떤 대응(correspondence) 혹은 관계가 만들어진다는 것입니다.

그러므로 interpolation과 sampling 둘은 결국 동전의 양면과 같이 떼어낼 수 없는 사이라는 점을 알아야겠지요. 앞으로 다룰 내용을 간략히 소개하자면,

  • Interpolation: "이 행위(interpolation)로 인하여 기존 함수와 interpolated 함수 사이의 spectral 성질이 어떻게 달라지는가?"에 대한 것이며, 
  • Sampling: "이 행위(sampling)로 인해 정보 손실이 생기는가?" 그리고 "손실이 있다면 얼마나 생기며 이를 피할 수 있는가?"가 되겠습니다. 

여기서 만약 sampling의 첫번째 질문에 대한 답이 (최소한 특정 신호에 대해) "없다"라면, 이는 우리가 discrete-time domain에서 개발한 모든 신호 처리 도구들을 고스란히 continuous-time 신호에도 적용할 수 있다는 것을 뜻합니다. 이는 직관적으로는 잘 와닿지 않는 매우 흥미로운 점이지요.

당연하지만 interpolation 함수의 가장 필수충족 요소는 샘플 주기 $T_s$에 대해 아래가 성립해야한다는 것입니다:
$$x(t)\bigg\rvert_{t=nT_s}=x[n]$$ 이렇게 각 instants에서의 값이 같다는 것을 제외하고 나면 남은 문제는 이 "값들 사이사이를 어떻게 채울 것인가?"가 되겠습니다.

Local Interpolation


임의의 discrete-time sequence $x[n]$에 대한 continuous-time 함수 $x(t)$를 만드는 가장 간단한 방법은 $t=nT_s$에 대해 $x(t)$의 값이 $x[n]$과 같도록 한 후 그 사이를 이웃하는 sequence 값들에 대한  임의의 선형 조합으로 나타내는 것입니다.

일반적으로 local interpolation 방식은 다음과 같이 표현할 수 있습니다: $$\begin{align}x(t)=\sum^\infty_{n=-\infty} x[n]I\left (\frac{t-nT_s}{T_s}\right) \end{align}$$ 여기서 $I(t)$는 interpolation 함수를 뜻하며 $I_N(t)$와 같이 표현된 경우 $N$은 $x(t)$을 보간할 때, 현재 instants에 대응하는 샘플 외에 N개의 discrete-time 샘플을 사용하였다는 것을 말합니다.
** 여기서 식 (1)을 잘 살펴보면 신호 $x(t)$가 하나의 interpolation 함수 $I(t)$의 shifted version들의 선형 조합으로 나타내진다고 이해할 수 있다. 이런 해석은 차후 유용하게 사용될 수 있는 관점이므로 염두에 두고 넘어갈 필요가 있다. 
** 또 한 편으로 이 식이 재미있는 이유는 두 신호를 convolution 하는 것으로 생각하되, 하나는 discrete-time signal $x[n]$이고 다른 하나는 continuous-time "impulse response" $I(t)$인 "mixed-domain" convolution으로 생각할 수 있다는 점이다. 

$I(t)$에 어떤 함수를 사용하느냐에 따라 신호 $x(t)$에 대한 interpolation 성격이 정해지는데 어떤 $I(t)$이든 interpolation 함수라면 다음과 같은 성질을 만족해야 합니다:
$$\begin{align}\begin{cases} I(0)=1 \\  I(k)=0 \quad \text{for} \quad k\in\mathbb{Z}\setminus\{0\} \\ \end{cases} \end{align}$$ 두 번째 조건이 뜻하는 것은 $I(t)$가 몇 개의 support를 갖는지와는 상관없이 절대로 다른 interpolation instants에 영향을 주어서는 안 된다는 것이죠.

아래 그림은 기본적으로 사용되는 $I(t)$입니다. 하나씩 하나씩 살펴보겠습니다.

Zero-order $I(t)$ and First-order $I(t)$

Zero-Order Hold


가장 쉽게 생각할 수 있는 interpolation 방식은 piecewise-constant interpolation입니다. 즉, 샘플값 사이를 상수로 interpolation 하는 것이죠: $$x(t) = x[n], \quad \text{for} \quad\left(n-\frac{1}{2}\right)T_s\leq t \leq \left(n+\frac{1}{2}\right)T_s$$
Zero-order hold

Interpolation 함수가 불연속 함수기 때문에, 당연하지만 결과가 절대 부드럽지는 않습니다: $$I_0(t)=\text{rect}(t)$$
아래 첨자 0에서 알 수 있듯, $x(t)$ 값이 현재 discrete-time 샘플 값에만 영향을 받습니다. 

First-Order Hold


그 다음으로 생각해볼 수 있는 interpolation은 선형 interpolator가 되겠습니다. 두 샘플들 간에 일직선을 그어 보간을 하는 것으로 아래 그림과 같이 조금은 더 부드러운 모습을 볼 수 있죠. 
$$ I_1(t)=\begin{cases} 1-|t| \quad \text{if}~|t|<1 \\  0 \quad\qquad \text{otherwise} \\ \end{cases} $$
First-order hold

Higher-Order Interpolators


$I_0(t)$와 $I_1(t)$는 각각 zero-order와 first-order B-spline 함수라고 불리는데요. 이를 $N$-th-order로 확장한 것이 $t$에 대한 $N$-th-order polynomial $I_N(t)$이며 앞선 예시에서 유추할 수 있듯이 order가 커질수록 더 부드러운 보간이 가능해집니다.

이러한 local interpolation의 장점은 실제 적용이 간단하다는 점이지만, N번째 미분부터는 불연속 함수가 되기 때문에 그 이상의 부드러운 보간이 불가능하다는 단점이 존재합니다. 이를 spectral 관점에서 얘기하자면, 불연속성이 곧 high frequency에 대응하고 이는 보통 원치않는 결과를 부르기 때문에 여러가지 의미에서 좋지 않습니다.

Polynomial Interpolation


Local interpolation에서 문제가 되는 lack of smoothness는 우리가 유한한 길이의 discrete-time 샘플들을 보간해야한다면 쉽게 우회할 수 있습니다. 이렇게 신호의 범주를 유한한 길이로 제한을 두는 순간, 이 문제는 전통적인 polynomial을 이용한 보간 문제로 치환이 가능해지고 우리는 이에 대한 optimal solution을 알고 있습니다: Lagrange interpolation.

Polynomial interpolation이 좋은 점은 유한한 갯수의 점에 대한 polynomial interpolation은 모든 미분에 대해 언제나 연속을 보장한다는 것이죠. 즉, interpolated 함수가 maximally smooth한 함수가 된다는 강력한 장점을 갖고 있다는 것! (polynomials are infinitely many times differentiable.)

$2N+1$ 길이의 discrete-time signal $x[n],~(n=-N\cdots,N)$을 생각해보겠습니다. 모든 $2N+1$ 점 $(t_n,x[n])$을 지나는 $2N$-차 polynomial $P(t)$는 유일(unique)하고, 이는 Lagrange interpolator라는 것은 잘 알려져 있습니다.
** $P(t)$의 existence는 construction 자체로 자명하고 uniqueness 증명은 contradiction으로 쉽게 알 수 있다.

이런 polynomial의 coefficients는 다음과 같은 $2N+1$개의 방정식을 풀면 구할 수 있으며: $$\{P(t_n)=x[n]\}_{n=-N,\cdots,N}$$ 이보다 더 쉬운 방법은 $P(t)$를 $2N+1$ 개의 Lagrange polynomials (of degree $2N$)로 나타내는 것입니다: $$\begin{align*}L^{(N)}_n(t) &=\prod_{\substack{k=-N\\k\neq n}}^N \frac{t-t_k}{(t_n-t_k)} \\
&=\prod_{\substack{k=-N\\k\neq n}}^N \frac{t/T_s-k}{(n-k)}, \quad n=-N, \cdots, N\end{align*}$$ 이런 polynomial이 글 서두에 소개한 식 (2)의 interpolation의 성질을 만족하는 것은 자명합니다. 예를 들어 점 4개를 보간할 때 $L^{(N)}_n(t)$를 보면 아래 그림과 같습니다 (wikipedia의 그림이 좋아 그대로 빌려왔기에 notation이 안 맞을 수 있습니다.) :

$P(x)$ (dashed, black), which is the sum of the scaled basis polynomials $y_0ℓ_0(x), x_1 ℓ_1(x), y_2ℓ_2(x),~and~~y_3 ℓ_3(x)$. The interpolation polynomial passes through all four control points, and each scaled basis polynomial passes through its respective control point and is 0 where x corresponds to the other three control points. 

따라서 "global" Lagrange interpolator는 Lagrange polynomial들의 선형 조합으로 표현되며: $$P(t)=\sum_{n=-N}^Nx[n]L^{(N)}_n(t)$$ 여기서 global은 $x(t)=P(t)$는 interpolation을 할 때 언제나 모든 샘플들을 고려한다는 뜻입니다. 즉, 유한한 길이를 가진 discrete-time 신호 $x[n]$에 대해 Lagrange polynomials는 global interpolating 함수이며 이렇게 보간된 함수 $x(t)$는 maximally smooth합니다 ($x(t)\in C^\infty$).

Sinc Interpolation


본격적으로 Sinc interpolation에 대해 알아보기에 앞서, 지금까지 살펴본 local & global interpolation에 대해 장단점을 비교해보겠습니다.

Local interpolation 방식의 멋진 점은 interpolated 함수가 interpolation 함수 $I(t)$의 shifted version들 간의 선형 조합으로 표현할 수 있다는 것이죠: "An interpolated function is simply a linear combination of shifted versions of the same prototype $I(t)$." (식 (1)을 보라) 다만 smoothness에 한계가 있다는 단점이 있겠습니다.

반면에 polynomial interpolation은 완벽하게 부드러운 보간이 가능하지만 finite-length 신호에 대해서만 적용이 가능하며 다른 길이를 갖는 신호에 대해 서로 다른 interpolation 함수가 필요하다는 단점이 있습니다.

이 두 가지 방식의 장점만 쏙쏙 빼면 참 좋을텐데...에 대한 답이 바로 Sinc Interpolation입니다! 이제 지금까지 설명한 내용들을 바탕으로 infinite discrete-time 신호에 대해 maximally smooth한 interpolation 방법을 소개할 준비가 되었습니다.

앞서 살펴본 Lagrange polynomial of degree N에 대해 N을 무한대로 보내면: $$\begin{align*} \lim_{N\rightarrow\infty}L_n^{(N)}(t) &= \prod_{\substack{k=-\infty\\k\neq n}}^\infty \frac{t/T_s-k}{n-k} = \prod_{\substack{m=-\infty\\m\neq0}}^\infty \frac{t/T_s-n+m}{m}\\
&=\prod_{\substack{m=-\infty\\m\neq0}}^\infty \left(1+\frac{t/T_s-n}{m}\right)\\
&=\prod_{m=1}^\infty \left(1-\left(\frac{t/T_s-n}{m}\right)^2\right)\\
\end{align*}
$$
두번째 등호는 $m=n-k$를 사용하여 변수를 치환한 것입니다. 이후 전개는 아래와 같은 sine 함수에 대한 오일러의 infinite product expansion을 사용할 것인데: $$sin(\pi\tau) = (\pi\tau) \prod_{k=1}^\infty\left(1-\frac{\tau^2}{k^2}\right)$$ 이를 정리하면 최종적으로 아래 식을 얻을 수 있습니다: $$\lim_{N\rightarrow\infty}L_n^{(N)}(t) = \text{sinc}\left(\frac{t-nT_s}{T_s}\right) $$
포인트는 차수가 증가할 수록 Lagrange polynomial $L_0^{(N)}(t)$는 점차 sinc 함수로 수렴한다는 것인데요. 즉, 점의 갯수가 무한이 되면서 모든 Lagrange polynomial은 각각 sinc 함수에 대한 shifted version으로 수렴하게 된다는 점입니다. 따라서 식 (1)과 같이 $I(t)=sinc(t)$를 사용하여 무한수열 x[n]에 대해 $$x(t)=\sum_{n=-\infty}^\infty x[n] sinc\left(\frac{t-nT_s}{T_s}\right)$$로 표현하는 것이 가능해집니다.

Spectral Properties of the Sinc Interpolation


Interpolation을 할 때 주안점을 둘 부분이 바로 spectral 영역에서 interpolated 신호가 어떤 식으로 달라지는지 확인하는 것이라고 말한 바 있습니다. 이제 이게 어떤 의미인지 얘기할 준비물이 대략 갖춰졌습니다.

지금까지 interpolation 방법들 여럿을 살펴보았으나 일반화하면서 결국 마지막에 다다른 것은 Sinc interpolation입니다. 이렇게 얻은 Sinc interpolation은 spectral 영역에서 보면 재미있는 분석이 가능해지는데, 간단히 말하면 시간 영역의 Sinc 함수에 대응하는 주파수 영역의 형태는 ideal low-pass filter로써 0을 기준으로 한 사각형 박스처럼 생겼습니다.

그러므로 discrete-time sequence에 대한 Sinc interpolation은 continuous-time 신호가 band-limited low-pass filtering이 된 것과 정확히 일치합니다 (수식적으로도 그러하다). 즉, DTFT $X(e^{j\omega})$가 존재하면 interpolated function $X(j\Omega)$의 spectrum은 다음과 같이 얻을 수 있습니다: $$\begin{align*}X(j\Omega)
&= \int^\infty_{-\infty} \sum_{n=-\infty}^\infty x[n] sinc \left(\frac{t-nT_s}{T_s}\right) e^{-j\Omega t} dt\\
&= \sum^\infty_{n=-\infty} x[n] \int_{-\infty}^\infty sinc \left(\frac{t-nT_s}{T_s}\right) e^{-j\Omega t} dt \\
\end{align*}$$
Sinc 함수에 대한 Fourier Transform을 해주고 여기에 $T_s = \pi/\Omega_N$를 대체하면,
$$\begin{align*}X(j\Omega)
&= \left(\frac{\pi}{\Omega_N}\right)\text{rect}\left(\frac{\Omega}{2\Omega_N}\right)\sum_{n=-\infty}^\infty x[n]e^{-j\pi(\Omega/\Omega_N)} \\
&= \begin{cases} \frac{\pi}{\Omega_N}X(e^{-j\pi\Omega/\Omega_N}) \quad \text{for}~|\Omega|\leq\Omega_N \\ 0 \qquad \qquad\qquad\quad \text{otherwise}\end{cases}\end{align*}$$이를 다르게 말하면, 임의의 continuous-time 신호가 애초부터 bandlimited 신호인 경우 이 신호에 대한 적절한 sampling을 하므로써 어떠한 정보 손실도 전혀 없이 discrete-time 신호를 얻는 것이 가능하다는 뜻입니다.

이런 사실은 이후에 Fourier transform을 살펴본 다음에 자명하게 수식적으로 보일 수 있겠지만, 이렇게 미리 살짝 엿보는 것까지는 굳이 복잡한 Fourier transform 내용을 배우지 않고도 가능합니다.

이제 신호처리 초반에 왜 여러가지 복잡한 내용을 공부하는지 그리고 어째서 Sinc 함수와 같이 이상하게 생긴 것을 굳이 배워야하는지 조금은 감이 생기셨으리라 생각합니다.

여기에 대한 더 자세한 설명 및 Sampling Theorem 그리고 Aliasing 현상에 관한 내용은 Fourier transform 등의 수학적 도구를 더 든든히 갖춘 다음에 돌아와 살펴보겠습니다.

To be continued ... (planned)



참고 문헌


  • https://math.stackexchange.com/questions/1343904/are-polynomials-infinitely-many-times-differentiable
  • https://www.youtube.com/watch?v=ygcQJqcHdOM
  • http://home.iitk.ac.in/~pranab/ESO208/rajesh/03-04/interpolation.pdf



댓글 없음:

댓글 쓰기