Linear Prediction 바로 알기

목차

1. Forward linear prediction

2. Backward linear prediction

3. Levinson-Durbin algorithm

4. Lattice predictors

 

---

수식 전개는 계산 용이성을 위해, complex가 아닌 real을 가정하였습니다.

1. Forward linear prediction

 

 

위 filter의 output은 과거의 $(N-1)$개의 input을 가지고 현재를 추정한 값 $\hat{u}(n|\mathcal{U}_{n-1})$입니다. $f_M(n)$은 desired signal인 $u(n)$에서 output인 $\hat{u}(n|\mathcal{U}_{n-1})$을 뺀 값으로, filter의 Forward prediction error를 의미합니다. 여기서 $M$은 filter tap을 나타냅니다.8

 

Wiener filter 정리 (Orthogonality principle, Wiener-Hopf equation, Error-performance surface)

 

앞서 배웠던 Wiener-Hopf equation을 풀기 위해, 필요한 값들을 정리해보았습니다. $\textbf{R}, \textbf{r}$과 input signal variance 등 autocorrelation을 알면 linear prediction을 수행할 수 있다는 걸 알 수 있습니다.

 

 

Wiener filter와 Forward predictor 간 수식 표기를 나타낸 표입니다. 

 

 

$$\textbf{Rw}_f = \textbf{r}$$

$$P_M=r(0)-\textbf{r}^T \textbf{w}_f$$

 

Forward linear prediction에서 필터 계수는 $\textbf{w}_f=\textbf{R}^{-1}\textbf{r}$의 계산을 통해 얻을 수 있습니다. 그러나 $\textbf{R}^{-1}$ (공분산 행렬의 역행렬)을 구하는 것은 계산 복잡도가 높기 때문에, 이를 재귀적으로 풀어 연산량과 메모리를 절약하려는 방법이 고안되었습니다. 이 방법을 Levinson-Durbin 알고리즘이라고 합니다.

 

 

Forward prediction-error filter에서는 $f_M(n)$이 output으로 나옵니다. 여기서 $\mathcal{a}_{M,k}$는 forward prediction error coefficient를 나타냅니다.

 

 

기존의 Wiener-Hopf equation을 $(M+1)\times(M+1)$ autocorrelation matrix로 dimension을 하나 추가해주고 forward prediction error coefficient인 $\mathcal a_M$을 곱함으로써, 여러 변수를 고려한 최적의 필터 설계를 위한 augmented Wiener-Hopf equation으로 변형할 수 있습니다.

 

2. Backward linear prediction

 

Forward predictor와 비교했을 때 Backward predictor는 tap input과 desired 간 cross-correlation vector 순서가 반대입니다. 하지만, prediction error power $P_M$는 forward나 backward나 같은 값을 가집니다. 

 

 

 

3. Levinson-Durbin algorithm

Levinson-Durbin algorithm은 augmented Wiener-Hopf equation을 푸는데 쓰이는 recursive한 알고리즘으로, $m$차 해을 얻기 위해 $m-1$차 prediction error filter의 augmented Wiener-Hopf equation의 해를 사용합니다. 복잡한 행렬 계산 대신 재귀적인 방식으로 해를 구하기 때문에, 효율적으로 메모리를 사용하고 연산량을 줄인다는 장점을 가집니다.

 

 

위 필기에서도 알 수 있듯이, $m$차 prediction error coefficient는 $m-1$차 forward/backward prediction error coefficient에 대한 식으로 나타낼 수 있습니다.

 

 

$m-1$차 coefficient를 이용해 $m$차 coefficient를 구하도록, augmented Wiener-Hopf equation을 풀어보면 $\kappa_{m}$과 $m$차 prediction error power에 대한 식을 얻을 수 있습니다. $P_{m-1}$을 알면 $\kappa_{m}$을 구할 수 있고, $\kappa_{m}$을 알면 다음 $P_m$을 구할 수 있습니다. 또한, 전개 과정에서 얻은 $P_m$에 대한 관계식을 통해 predictor 차수가 증가할수록 error power가 감소하는 것을 알 수 있습니다. 이렇게, 재귀적으로 augmented Wiener-Hopf equation을 풀어나감으로써, 연산량도 줄이고 유용한 부차적인 정보도 얻을 수 있게 됩니다.

 

$\kappa_{m}$과 $\Delta_{m-1}$의 의미를 해석해봅시다.

 

 

$\kappa_{m}$은 마지막 $m$차 forward prediction error coefficient로 정의되고 $\Delta_{m-1}$은 forward prediction error와 delayed backward prediction erorr 간 cross correlation을 나타냅니다. $\Delta_{m-1}$이 왜 이렇게 정의되는지 수식을 통해 알아보도록 하겠습니다.

 

 

$u(n-m)$의 backward prediction을 가정하고 $\Delta_{m-1}=\mathrm{E}[u(n-m)f_{m-1}(n)]$ 식을 이용해 풀어쓰면, $\Delta_{m-1}$가 forward prediction error와 delayed backward prediction error의 cross-correlation이라는 것을 알 수 있습니다.

 

 

0차 forward/backward prediction error를 모두 $u(n)$이라 두었을 때, Levinson-Durbin algorithm 메커니즘을 정리하였습니다. 첫 번째 coefficient는 항상 1이고, 마지막 coefficient는 reflection coefficient ($\kappa_2=a_{2,2}$)입니다. 여기서 $\kappa_1$은 power 대비 한 샘플 delay 됐을 때 signal의 correlation을 나타냅니다.

 

 

reflection coefficient $\kappa_m$와 partial correlation coefficient $\rho_m$의 관계식은 위와 같습니다.

 

 

inverse Levinson-Durbin algorithm을 통해 $m$차 coefficient로부터 과거의 $m-1$차 coefficient를 구할 수 있습니다.

 

4. Lattice predictors

 

 

Lattice predictor는 linear prediction을 수행하는 또 다른 방법으로, 입력 $u(n)$이 들어왔을 때, 낮은 차수에서 높은 차수까지 마치 결정과 같은 구조로 reflection coefficient를 재귀적으로 계산합니다.

 

 

 

All-pole filter는 재귀적으로 $M$차에서 $M-1$, $M-2$, ..., $0$차로 계산하며, 최종적으로 $f_0(n) = u(n)$을 구합니다. All-pass filter는 $f_M(n)$에서 delayed $b_M(n)$을 output으로 반환합니다. All-zero filter는 입력 $u(n)$에서 시작하여 재귀적으로 $f_M(n)$을 예측하는 필터입니다.

GIST 신종원 교수님 '적응신호처리' 수업 자료를 바탕으로 쓴 글입니다.