적응 필터
호남대학교 전자광공학과
최 성 율
필요성
•
-
시스템에 요구하는 특성을 완전히 규정
할 수 없는 경우
•
-
입력의 통계적 특성이 변하는 경우
•
-
입력이외에도 시스템의 변화에 의해 출
력이 결정되는 경우
용어
•
적응알고리즘 ( adaptive
algo-rithm ):
시스템을 변화시키는 방
법
•
적응필터 ( Adaptive filter ) :
적응 신호처리를 적용한 시스템
•
적응신호처리 ( adaptive signal
process-ing ) :
신호처리 과정에서 필요에 따라 시스
Adaptive System
의 구성도
적응 알고리즘 ( 파라메타경신 알고리즘 )+
가변 시스템 파라메타 C+
참조신호d(n) 응답 y(n) 오차 e(n) 입력 x(n)예 1 equalizer( 등화기 )
적응 알고리즘 ( 파라메타 갱신 알고리즘 )+
파형등화기+
수신데이터 d’(n) 데이터 d(n) 판정 tthdtls vlfxj ㅈ 송신필터 전송로 잡음 수신필터 ) ( T G () R G ) ( T 표본화 t=nT x(n) x(n) 표본화 t=nT 전송계 a) 데이터 전송계 b) 파형등화기equalizer( 등화기 )
k n n n n k h n d h k d n k h n d k x( ) ( ) ( ) ( ) (0) ( ) ( ) 1. 표본시점 t=nT 에서 d(n) 을 정확하게 검출 하기 위해서 제 1 항만을 골라내야 한다 2. 제 2 항은 간섭성분 : 이는 전송로 특성에 의 해 값이 변화된다 . 3. 전송계 변동에 따라 등화기 특성을 변화시켜 방해를 억제한다 .예 2 echo canceller
Echo canceller hybrid+
+ hybrid 수신기 S1 S2+E S1 S2+E a) Hybrid : echo 발생기 b) Echo canceller ) (n u ) (n y ) (n y ) (n h ) (n e 송신기Echo canceller
Hybrid : echo 가 발생하는 주위 환경 ( 소리의 전파 경로 ) ) (n u ) (nh
) (n y ) (n e ) (ny
) (n h : echo 를 포함한 귀환 신호 : echo 가 발생하는 회로 : A 로부터의 입력신호
) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( 0 0 n y n y n e k n u n h n y n v k n u n h n y k k ) (nx
는 추정치 이를 통하여 의 계수들 을 상황에 맞게 정한다 . ) (nh
: echo caceller 에서 찾아낸 출력분 : y(n) 과y
(n) 의 차이 : 찾아낸 잡음 제거용 시스템 함수예 3
시스템 동정
(system Identification )
주어진 입출력으로 부터 미지의 시스템을 추정하는 문제 적응 알고리즘 ( 파라메타경신 알고리즘 ) + 미지의 시스템 + 오차 e(n) 입력 u(n) 적응필터 적응필터의 계수 제어 d(n) U(n) 을 인가했을 때 응답이 d(n) 이면 적응필터에도 같은 입력을 인가하여 그 응답 y(n) 이 d(n) 과 비슷해지도록 적응필터의 계수를 조정한다 .MSE performance Criteria
MSE : mean square error
)} ( { ) ( ) ( ) ( ) ( 2 n e E n n d n d n e ) (n 을 최소로 하는 알고리즘
Linear MSE filtering
-Adaptive filter 를 선형형태로 나타냄 - filter 계수가 wi(n)라고 하면
1 0 ) ( ) ( ) ( ) ( ) ( N i N T N i n x n i W n X n w n d 여기서
( ) ( ) ... ( )
) ( ) ( ... ) ( ) ( ) ( 1 1 0 1 1 0 n x n x n x n X n w n w n w n W N T N N T N } )] ( ) ( {[ )} ( { ) (w E e2 n E d n W X n 2 N T N N (w ) E{e2(n)} E{[d(n) W X (n)]2} N T N N N T N N T N N T N E d n X n W E X n X n W W n d E{ 2( )}2 { ( ) ( )} { ( ) ( )} Linear MSE filtering
) 1 ( : ) 1 ( ) 0 ( )} 1 ( ) ( { : )} 1 ( ) ( { )} ( ) ( { N N n x n d E n x n d E n x n d E p xd xd xd N 여기서 여기서 x(n) 과 d(n) 이 stationary 하고 ergodic 하다면
| | 1 0 ) 1 | | ( ) ( 1 ) ( m K i xd x n i d n m K m
( ) ( 1) ... ( 1) ) 1 ( : ) 1 ( ) ( N n x n x n x N n x n x n x E RNN 마찬가지로 여기서 x(n) 이 stationary 하고 ergodic 하다면
| | 1 0 ) 1 | | ( ) ( 1 ) ( m K i x x n i x n m K m Linear MSE filtering
즉 RNN 은 ) 0 ( .. ) 2 ( ) 1 ( : : : : ) 2 ( .. ) 0 ( ) 1 ( ) 1 ( .. ) 1 ( ) 0 ( x x x x x x x x x NN N N N N R Symmetry matrix } )] ( ) ( {[ )} ( { ) (w E e2 n E d n W X n 2 N T N N (w ) E{e2(n)} E{[d(n) W X (n)]2} N T N N N NN T N N T N d N T N N T N N T N W R W p W W n X n X E W n X n d E W n d E 2 )} ( ) ( { )} ( ) ( { 2 )} ( { 2 2 (1)Linear MSE filtering
(
필터 계수가 2
개일 때의 예 )
1 w 2 w axis axis * 2 w * 1 w min axis<Mean square error surface> 가 이 되도록 필터의 계수를 결정하면 차이가 최소가 되므로 1 w w2 * 1 w * 2 w 적절한 필터가 된다 .
Property of the MSE surface
0 )] , ( [ 0 )] , ( [ * 2 * 1 2 1 * 2 * 1 2 1 , 2 1 2 2 2 , 2 1 2 w w w w w w w w w w w w w w 이면 w1 축 상에서 이 최소가 된다 마찬가지로 0 )] , ( [ 0 )] , ( [ * 2 * 1 2 1 * 2 * 1 2 1 , 2 1 2 1 2 , 2 1 1 w w w w w w w w w w w w w w 이면 w2 축 상에서 이 최소가 된다 (2) (3)Property of the MSE surface
min * 1 w 0 1 w w2 axis min * 2 w 0 2 w w1 axis 0 ) 0 ( 2 )] , ( [ 0 ) 0 ( 2 )] , ( [ * 2 * 1 2 1 * 2 * 1 2 1 , 2 1 2 2 2 , 2 1 2 1 2 x w w w w x w w w w w w w w w w Concave up graph 2 2 2( )} { ( )} { ) 0 ( x x E x n j x n 이므로 그리고 2 * min N T N d p W Property of the MSE surface
(1) 식에 의해 2 2 1 2 2 2 1 2 1 2 1, ) (0) 2 (1) (0) 2 (0) 2 (1) ( ) (WN w w w w w x w wxd w xd d (2) 와 (3) 식을 적용하면 0 ) 1 ( 2 ) 1 ( 2 ) 0 ( 2 0 ) 0 ( 2 ) 1 ( 2 ) 0 ( 2 * 1 * 2 * 2 * 1 xd x x xd x x w w w w 이는 matrix 형태로 쓰면 N NN N N N NN p R W p W R 1 * * Impact of signal correlation
d(n) 과 x(n) 사이에 cross correlation 은 0 이 아니어야 한다 .)
2
(
)
(
n
ax
n
d
라 가정하면 ...] 0 , , 0 , 0 [ )} ( ) ( { 2 2 x N NN x T N N NN a p I n x n x E R 0 ,....] 0 , , 0 , 0 [ 2 2 2 min 1 * x d T N NN N a a p R W 1 2. x(n)dl 과거 값의 linear sum 으로 이루어진 경우 0 )} 1 ( ) ( { )} 1 ( ) 1 ( { ) 1 ( ) ( 2 n X n x E p I n X n X E R n X W n x N N NN x T N N NN N T N Normal Equation
-data and prediction erroe orthogonality
) ( )] ( ) ( [ ) ( 0 )} ( ) ( 2 { )} ( { )} ( { 2 2 n x n x w n d w n e w n e w n e E n e w E n e E w N N T N N N N N N 밑의 식을 위 식에 대입하면
0
)}
(
)
(
{
0
)}
(
)
(
{
i
n
x
n
e
E
n
x
n
e
E
N orthogonalityNormal Equation
-data and prediction erroe orthogonality
N N NN N N T N N N w w N T N N w w N T N N p w R n d n x E w n x n x E n d n x E w n x n x E w n x n d n x E N N N N * * { ( ) ( )} )} ( ) ( { )} ( ) ( { ]}] ) ( ) ( { [ 0 ]}] ) ( ) ( )[ ( { [ * *
Autocorrelation Matrix
의 고유치 및 고유
벡터
) ( 2 0 2 2 2 d N T N N NN T N N NN T N N T N d p W W R W W R W p W * N N N w w v 로 놓으면 N NN N N v R p w 1 min * 2 min 2 0 N NN T N N T N d N NN T N v R v w p v R v N T NN N N NN N v A v v A v ' 'ANN은 orthogonal transformation matrix
min ' ' min ' ' ) ( ) ( ) ( N NN NN T NN T N N NN NN T N NN v A R A v v A R v
A 은 symmetric and real 이므
로
NN
R
Linear Predictive
– Durbin algorithm
N N NNw p R * 을 계산하는 방법 중 하나 Autocorrelation 은 다음과 같이 주어진다 .
1 1 ) ( ) ( 1 ) ( K m n x x n x n m K m 여기서 K 는 estimation 에 사용되는 data 의 갯수 P-1 번째 predictor 는 1 * 1 1 , 1 p p p p w p R ) 1 ( : ) 2 ( ) 1 ( 1 p p xd xd xd p ) 0 ( .. ) 3 ( ) 2 ( : : : : ) 3 ( .. ) 0 ( ) 1 ( ) 2 ( .. ) 1 ( ) 0 ( 1 , 1 x x x x x x x x x p p p p p p R 여기서 T p p p p pw
w
w
w
[
,
,....,
( 1)]
1 ) 1 ( 2 ) 1 ( 1 1
Linear Predictive
– Durbin algorithm
를 의 reverse element vector 라면
_
x
x T p p p p p pw
w
w
w
1
[
( 11),
( 21),....,
1( 1)]
) 1 ( : ) 2 ( ) 1 ( 1 xd xd xd p p p p 1 * 1 1 , 1 p p p p w p R 1 1 , 1 1 * 1 p p p p R p w 이들로부터 다음의 식을 얻을 수 있다 .
)
(
)
0
(
1 ) ( 1 1 1 1 , 1p
p
k
w
p
p
R
x p p p p x T p p p p
여기서 ) ( p p pw
k
P 번째 reflection coefficientLinear Predictive
– Durbin algorithm
이 알고리즘은 반사계수를 결정하는 것이 가장 중요하다 . p k 와 ( ) 를 얻기 위해서 다음과 같이 식을 쓴다 . 1 p p w Initialize
0
x(0) For 0<p<N 1 [ ( ) ( )] 1 1 ) 1 ( 1 j p w p k x p j p j x p p
여기서 ) ( p p pw
k
For 0<j<p 1 2 ) 1 ( ) 1 ( ) ( ) 1 ( p p p p j p p p j p j k w k w w P=N 일 때에는 w*j w(jN)Linear Predictive
- Steepest method: iteration solution
N N NNw p R * N w w [] 여기서 첫 position 과 다음 position 의 관계는 (0) )] 0 ( [ ) 0 ( ) 1 ( ) 1 ( N w N w w 계속하면
)]
(
[
)
(
)
1
(
n
w
n
n
Linear Predictive
- Steepest method: iteration solution
또 ) ( 2 2 )] ( [ ) ( ) ( ) ( 2 ) ( 2 ) ( 2 2 n w R p n n w R n w p n w n w R w p w w N NN N w N NN T N N T N d N NN T N N T N d N 이를 전 page 식에 대입 N N XX NN N N XX N N N w N N
p
n
w
R
I
n
w
n
w
R
p
n
w
n
w
n
n
w
n
w
2
)
(
]
2
[
)
1
(
)]
(
[
2
)
(
)
1
(
)]
(
[
)
(
)
1
(
이 식을 0 부터 N 까지 실행한다 .Linear Predictive
- Steepest method: iteration solution
Weight vector 2 구하기
]
)
2
(
)
2
(
[
2
)
0
(
]
2
[
)
(
]
2
[
2
)
0
(
]
2
[
)
(
:
2
)
1
(
]
2
[
)
2
(
2
)
0
(
]
2
[
)
1
(
2
)
(
]
2
[
)
1
(
1 0 XX n XX N N n XX NN N n j j XX NN N N n XX NN N N N XX NN N N N XX NN N N N XX NN NR
I
I
R
I
I
p
w
R
I
n
w
R
I
p
w
R
I
n
w
p
w
R
I
w
p
w
R
I
w
p
n
w
R
I
n
w
절대치가 1 보다 작으면 수렴 ir
로 표현Linear Predictive
- Steepest method: iteration solution
Autocorrelation RXX 의 고유백터가 일 경우 다음의 관계를 가진다 . i max 2 2 0 i i i n p n w ( ) lim
LMS ( least mean square) algorithm
)
(
2
2
)]
(
[
n
p
NR
NNw
Nn
w
적응 알고리즘
1. FIR 필터
z1 z
z
z1z
z1 …..z
z1+
+ ) 0 ( h h(1) h(2) h(3) h(M 1) x(n) e(n) d(n) ) (n y 파라메타 갱신 알고리즘 그림 FIR 필터를 이용한 적응필터적응 알고리즘
1. FIR 필터
M i i i M i i i M i i i z a z a z A z a z H 1 0 0 1 ) ( , 1 ) ()
(
1
)
(
)
(
)
(
)
(
z
A
z
E
z
H
z
E
z
S
Total squared error 는
M j i M j j ij i n n n M j i M j j i n n n M i i n n n a c a a j n s i n s a i n s a n e 0 0 0 2 2 1 0 1 0 1 0 ) ( ) ( )] ( [ ) (
여기서
1 0 ) ( ) ( n n n ij s n i s n j c적응 알고리즘
1. FIR 필터
를 최소화 하려면
k M i ik i M i ik i k c c a c a a 0 1 0 2 0
여기서|)
(|
|)
|
(
)
(
|)
|
(
)
(
)
(
)
(
| | 1 0j
i
r
j
i
n
s
n
s
j
i
n
s
n
s
j
n
s
i
n
s
c
j i N n n n ij
적응 알고리즘
1. FIR 필터 -covariance 방법
k M i ik ic c a 0 1
N 1(
)
(
|
|)
M n ijs
n
s
n
i
j
c
M i is
n
i
a
n
e
0)
(
)
(
e(n) 은 무한의 구간이지만 s(n) 이 n=0-N 까지 존재한다면 여기서 n=M,M+1,…..N-1 k M i ik ic c a 0 1
) 0 , ( : ) 0 , 2 ( ) 0 , 1 ( : ) , ( .. ) 2 , ( ) 1 , ( : : : : ) , 2 ( .. ) 2 , 2 ( ) 1 . 2 ( ) . 1 ( .. ) 2 , 1 ( ) 1 , 1 ( 2 1 p c c c p p c p c p c p c c c p c c c n n n p n n n n n n n n n 적응 알고리즘
1. FIR 필터 -autocorrelation 방법
) ( |) (| 1 j r j i r a M i i
N i nl
n
s
n
s
l
r
1 0)
(
)
(
)
(
M i is
n
i
a
n
e
0)
(
)
(
여기서 n=0,1,…..N+M-1 ) ( |) (| 1 i R k i r n k n k
) ( : ) 2 ( ) 1 ( : ) 0 ( .. ) 2 ( ) 1 ( : : : : ) 2 ( .. ) 0 ( ) 1 ( ) 1 ( .. ) 1 ( ) 0 ( 2 1 p r r r r p r p r p r r r p r r r n n n p n n n n n n n n n Topliz Matrix적응 알고리즘
2. FIR
필터를 이용한 알고리즘
)]
(
[
)]
(
[
min
min
)
(
)
(
)
(
)
(
)
(
)
(
2 2 1 0n
e
E
MSE
n
e
E
MSE
n
y
n
d
n
e
k
n
x
k
h
n
y
M k
1 0 1 0 1 0 1 0 1 0 1 0 2 2 2 ) ( ) ( ) ( ) ( ) ( 2 )] ( ) ( [ ) ( ) ( )] ( ) ( [ ) ( 2 )] ( [ )] ( [ )] ( ) ( [ 2 )] ( [ M k M k M m xx dx M k M k M m m k R m h k h k R k h Pd m n x k n x E m h k h k n x n d E k h n d E n y E n y n d E n d E적응 알고리즘
2. FIR
필터를 이용한 알고리즘
E[e2(n)]가 최소가 되려면 이를 h(k) 로 편미분값이 0 이 되도록 한다 . ) (k h MSE
1 0 1 0 0 ) ( ) ( 2 ) ( 2M k M m xx dx k h m R m k R 즉
1 1 0 1 0 1 2 0 1 1 1 0 1 1 0 0 1 2 0 1 1 1 0 1 0 1 0 : .... .... : : : : .... .... ) 1 ( : ) 1 ( ) 0 ( : ) 1 ( : ) 1 ( ) 0 ( .... .... : : : : .... .... ) ( ) ( ) ( M M M M M M M M M k M m xx dx R R R R R R R R R R R M h h h R R R M h h h R R R R R R R R k m R m h k R적응 알고리즘
2. FIR
필터를 이용한 알고리즘
) 1 ( 2 2 ] ) 1 ( ,.... ) 1 ( , ) 1 ( , ) 0 ( [ RH P M h MSE h MSE h MSE h MSE 즉 H* R1P 로 설정하면 MSE 는 최소가 된다 . 이를 (1) 에 대입하면 * 1 2 1 R H H 값을 정확하게 알지 못하므로 추정을 해야 할 필요가 있다 . k k k H R H 1 1 로 반복 계산하는 것을 생각해 보면 P RHk k 2 2 를 대입하면 * * 0 * 1 1 ] ) 2 1 ( 1 [ ) 2 1 ( 2 ) 2 1 ( ) 2 2 ( H H H H H H P RH R H H k k k k k k k 이 식의 수렴 범위는 0 1/2 로 설정해야 한다 .적응 알고리즘
2. FIR
필터를 이용한 알고리즘
1 0 1 2 0 1 1 1 0 .... .... : : : : .... .... R R R R R R R R M M M 는 계산량이 많아서 실시간 계산에 문제가 많음 따라서 이를 하드웨어로 구현하는 방법을 소개한다 .전에는 실시간 계산이 어려워서 bit slice system 을 사용하였으나
지금은 DSP (discrete signal processor) 를 사용한다 . 그러나 지금도 더 빠른 processor 가 요구된다면 bit slice system 을 적용해야 한다 .
Bit slice system1
-Microprocessor 가 내부 구성도가 register, ALU, control unit 로 나눠져 있는데 반해
- bit slice processor 는 register 와 ALU 로만 이루어져 있다 . - 따라서 bit slice processor 에 적합한 control unit 를 설계하여 적절한 Microprocessor 를 구성하는 것이다 .
-즉 이렇게 설계된 Microprocessor 는 special purpose Microprocessor 가 되며 control unit 가 어떻게 설계되는가가
special purpose Microprocessor 의 목적을 달성하는 것이며
-이 시스템에서는 correlatio 값과 메트릭스 역변환 , 즉 곱하기를 빨리 하는 processor 로 구현함을 목적으로 하는 것이다 .
Bit slice system2
ALU register Cont rol unit a) 일반적인 Microproces-sorBit slice system3
ALU register Cont rol unitb) Bit slice system
Bit slice system4
-Bit slice system 은 일반적으로 설계된 control unit 를
사용하여 하나의 instruction 을 micro instruction 으로 구현하는 것이다 - micro instruction 은 bit slice processor 를 선택함으로서 결정된다 .
적응 알고리즘
하드웨어 구현
1. CCL ( correlation cancellation loop ) : 이 회로는 잡음제거에 많이 사용되는 회로 주 입력은 신호와 잡음 , 보조 입력에는 잡음만 ( 혹은 작은 신호 ) 입력됨 - 신호는 적당한 correlation 을 가짐 - 잡음은 강한 correlation 혹은 매우 약한 correlation
+
+
+
주입력 보조입력 e(n) ) (t x ) (t x 적응 알고리즘
하드웨어 구현
+
+
+
주입력 보조입력 e(t) ) (t x ) (t h - 이 회로는 잡음제거에 많이 쓰이는 회로로서 주입력과 보조입력을 비교하여 서로 correlation 이 있는 부분만을 제거하면 잡음이 나타날 것이다 . - 이 신호에 correlation 이 곧 없어지게 된다면 보조입력 없이도 가능 ) (t x적응 알고리즘
하드웨어 구현
이 회로는 다음과 같은 식이 나타난다 . dt t d t x t x t h( )
[ ( )( )] ( ) 이를 정리하면 r R r R h e t h( ) Rt[ (0) 1 ] 1 h(t) R1r t 따라서 h(t) 가 stationary 하다면h (t) R1r 로 구현이 가능하다 . 여기서 값을 어떻게 설정하느냐에 따라 얼마나 빨리 0 으로 가느냐가 결정되며 이에 따라 h(t) 의 값의 정확도가 판명된다 . 적응 알고리즘
하드웨어 구현
LPF
ADC
Shift register
8bit data bus
) (t
x
i