Uludağ Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, Cilt 13, Sayı 2, 2008 YENĐ BĐR ADAPTĐF FĐLTRELEME YÖNTEMĐ: HĐBRĐD GS-NLMS ALGORĐTMASI Sedat TĐRYAK * Đ Metin HATUN** Osman Hilmi KOÇAL** Özet: Bu makalede, adaptif filtre katsayılarını ayarlamak için GS (Gauss-Seidel) ve NLMS (Normalized Least Mean Squares) algoritmalarının birlikte kullanıldığı hibrid bir algoritma önerilmiş ve ayrıca önerilen yeni algo- ritmanın yakınsama hızı, kararlılığı ve işlem karmaşıklığı incelenmiştir. Önerilen algoritma yapılan bir benzetim çalışmasıyla yakınsama hızı ve işlem yükü açısından benzer algoritmalarla karşılaştırmalı olarak incelenmiştir. Elde edilen sonuçlara göre, önerilen hibrid algoritmanın bir ara yöntem olarak işlem karmaşıklığı veya yakınsa- ma hızı açısından diğer algoritmalara iyi bir alternatif olduğu görülmüştür. Anahtar Kelimeler: Adaptif filtreler, Gauss-Seidel, NLMS, hibrid algoritma. A New Adaptive Filtering Method: Hybrid GS-NLMS Algorithm Abstract: In this paper, a hybrid algorithm based on the use of Gauss-Seidel and Normalized Least Mean Squares algorithms together is introduced for adjusting of adaptive filter coefficients and also convergence rate, stability and computational complexity of the proposed algorithm is studied. The proposed algorithm is com- pared with similar algorithms by viewpoints of computational complexity and convergence rate by a simulation study. According to the results obtained, it is shown that the proposed hybrid algorithm is a good alternative to the others as an intermediate method by viewpoints of computational complexity or convergence rate. Key Words: Adaptive filters, Gauss-Seidel, NLMS, hybrid algorithm. 1. GĐRĐŞ Adaptif filtre katsayılarının ayarlamasında kullanılan algoritmalar eğim tabanlı algoritmalar ve en küçük kareler tabanlı algoritmalar olmak üzere iki temel grupta ele alınabilirler (Diniz, 1987, Farhang-Boroujeny, 1998, Haykin, 2002). Eğim tabanlı algoritmalar düşük işlem yükü avantajına sahip olup yüksek örnekleme hızlarında ve çoğunlukla adaptif sinyal işleme ve haberleşme uygulama- larında tercih edilmektedir. Bunlar LMS (Least Mean Squares), NLMS (Normalized LMS), ve AP (Affine Projection) algoritmalarıdır (Haykin, 2002, Haykin ve Widrow, 2003). Fakat bu algoritmalar giriş sinyaline ait korelasyon matrisinin özdeğer yayılımına da bağlı olarak yavaş yakınsama hızı de- zavantajına sahiptir. En küçük kareler tabanlı algoritmalar ise yüksek işlem yüküne rağmen yakınsama özelliklerinin eğim tabanlı algoritmalara göre çok iyi olmasından dolayı tercih edilmektedir. RLS (Recursive Least Squares) algoritması bu gruba girmektedir. Fakat yüksek örnekleme hızı gerektiren durumlar yoğun işlem yükünden dolayı bu algoritmaların kullanım alanlarını sınırlamaktadır. Diğer taraftan, bu iki algoritma grubuna alternatif olarak yüksek yakınsama hızı ve en küçük kareler tabanlı algoritmalara oranla daha az işlem yükü olan bazı algoritmalar da önerilmiş ve kulla- nılmıştır (Koçal, 1998, Bose, 2004). Bu algoritmalar normal denklemin GS (Gauss-Seidel) iterasyonlarıyla çözümü üzerine kurulu olup, yakınsama hızı açısından giriş sinyaline ait korelasyon matrisinin özdeğer yayılımına bağımlı olmasına rağmen eğim tabanlı algoritmalara oranla daha yüksek bir yakınsama hızına sahiptir ve korelasyon matrisinin özdeğer yayılımının küçük olması durumunda RLS algoritmasına çok yakın sonuçlar vermektedir (Koçal, 1998). Ayrıca işlem yükü RLS algoritma- sına göre daha azdır, fakat LMS grubu algoritmalardan fazladır. GS algoritması temelde RLS algorit- * Uludağ Üniversitesi, Fen Bilimleri Enstitüsü, Elektronik Mühendisliği Bölümü, 16059, Görükle, Bursa. ** Uludağ Üniversitesi, Mühendislik-Mimarlık Fakültesi, Elektronik Mühendisliği Bölümü, 16059, Görükle, Bursa. 85 Tiryaki, S. ve diğ.: Yeni Bir Adaptif Filtreleme Yöntemi:Hibrid Gs-Nlms Algoritması ması gibi korelasyon matrisinin birikimli değerlerini kullanan tekrarlamalı bir algoritma olup, korelas- yon matrisinin pozitif tanımlılığı sağlandığı sürece kararlılığı garantilenmiş olmaktadır (Hatun ve Koçal, 2005). Bu makalenin amacı, düşük işlem yüküne sahip eğim tabanlı algoritmalar ile bu algo- ritmalara oranla daha hızlı yakınsama ve kararlılık özelliklerine sahip olan GS algoritmasını birlikte kullanarak adaptif filtrelerde istenen özellikleri ön plana çıkaran yeni bir algoritma elde etmektir. Bu makalede, düşük işlem yüküne sahip olan eğim tabanlı NLMS algoritması ile bu algorit- maya göre yakınsama hızı kararlılık özellikleri daha iyi olan GS algoritması birlikte kullanılarak yuka- rıda bahsedilen iki algoritma grubunun istenen özelliklerine sahip olan hibrid bir algoritma elde edil- miştir. Yapılan bir adaptif kanal dengeleyici uygulamasıyla önerilen algoritmanın yakınsama özellikle- ri ve işlem yükü benzer algoritmalarla karşılaştırmalı olarak incelenmiştir. 2. ADAPTĐF FĐLTRELEME ALGORĐTMALARI Adaptif filtreleme algoritmaları aşağıdaki şekilde görüldüğü gibi filtre parametrelerini iteratif olarak ayarlamak için kullanılır. d (n) + x(n) Adaptif y(n) - Filtre e(n) Adaptif Algoritma Şekil 1: Adaptif filtreleme işlemi Burada x(n) adaptif filtrenin ayrık-zamanlı giriş sinyali, y(n) adaptif filtrenin tahmin edilen parametreler kullanılarak hesaplanan çıkış sinyali, d (n) ise adaptif filtrenin takip etmesi istenen sin- yaldir. Parametre ayarlama algoritmalarıyla, tahmin edilen parametreleri kullanarak hesaplanan y(n) sinyali ile adaptif filtrenin izlemesi istenen d (n) sinyali arasında e(n) = d (n) − y(n) olarak tanımla- nan hata sinyalinin karesinin beklenen değerini minimum yapan parametre tahminleri iteratif olarak hesaplanır (Widrow ve Stearns, 1985, Treichler ve diğ., 1987, Diniz, 1997, Farhang-Boroujeny, 1998, Haykin, 2002). 2.1. Eğim Tabanlı Algoritmalar Bilindiği gibi LMS algoritması, azalan adım optimizasyon yönteminin tahmini bir versiyonu- dur. Azalan adım yönteminde optimum parametreleri bulmak için, öncelikle başlangıç değerinden başlanarak bir sonraki parametre değerinin hesaplanmasında bir sonraki adımın yönü ve büyüklüğü belirlenir. Bir sonraki adımın yönü ortalama karesel hata fonksiyonunun türeviyle belirlenir. Ortalama karesel hata fonksiyonunu minimum yapan azalan adım optimizasyon yöntemi w(n +1) = w(n) + µ [p − Rw(n)] (1) olarak verilmektedir (Diniz, 1997, Haykin, 2002, Bose, 2004). Burada µ seçilen yönde gidilecek adım boyutunu, R adaptif filtrenin giriş sinyalinin otokorelasyon matrisini ve p ise adaptif filtrenin takip etmesi gereken sinyal ile giriş sinyali arasındaki karşı-korelasyon vektörünü göstermektedir ve sırasıyla 8 6 Uludağ Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, Cilt 13, Sayı 2, 2008 R = E[x(n)xT (n)] , p = E[x(n)d (n)] (2) olarak tanımlanmaktadır, Burada E beklenen değer operatörüdür. Adaptif filtrenin uzunluğu M ol- mak üzere adaptif FIR (Finite Impulse Response) filtrenin giriş işareti vektörü x(n) ve katsayı vektö- rü w(n) xT (n) = [x(n) x(n −1) L x(n − M +1)] (3) wT (n) = [w (4) 1(n) w2(n) L wM (n)] olarak tanımlanmaktadır. Pratik uygulamalarda, R korelasyon matrisi ve p korelasyon vektörünün tam değeri bilinemediği için tahmin edilmiş değeri kullanılır. Azalan adım optimizasyon algoritmasın- da R ve p matrislerinin anlık tahminleri R(n) ≅ x(n)xT (n) , p(n) ≅ x(n)d (n) (5) şeklinde kullanılarak elde edilen aşağıdaki algoritma LMS algoritması olarak bilinmektedir (Widrow ve Stearns, 1985, Diniz, 1997, Farhang-Boroujeny, 1998, Haykin, 2002, Bose, 2004). w(n +1) = w(n) + µ x(n)e(n) (6) LMS algoritmasının en önemli avantajı algoritmanın gerçeklenmesinde (2M +1) çarpma iş- lemi yapılmasıdır. LMS algoritması tahminlerinin kararlı bir şekilde optimum parametre değerlerine yakınsayabilmesi için µ adım parametresi 0 < µ < 2 / λ (7) max aralığında seçilmelidir. Burada λmax korelasyon matrisinin en büyük özdeğeridir. LMS algoritmasındaki en önemli eksikliklerinden biri algoritmanın kararlı kalmasını sağlaya- cak kadar küçük ve aynı zamanda parametre tahminlerinin kısa zamanda optimum değerine yakınsa- masını sağlayacak kadar da büyük bir µ adım parametresi seçiminin zorluğudur. LMS algoritmasının, giriş işaretinin filtre uzunluğu kadar kısmının gücü ile normalize edilmesiyle NLMS algoritması elde edilir. NLMS algoritması + = + µ x(n)e(n)w(n 1) w(n) α + xT (8) (n)x(n) olarak yazılabilir, burada paydada olası bir sıfıra bölme işlemine engel olması için küçük bir α > 0 katsayısı kullanılır. NLMS algoritması tahminlerinin kararlı bir şekilde optimum parametre değerleri- ne yakınsayabilmesi için µ adım parametresi 0 < µ < 2 (9) 87 Tiryaki, S. ve diğ.: Yeni Bir Adaptif Filtreleme Yöntemi:Hibrid Gs-Nlms Algoritması aralığında seçilmelidir (Treichler ve diğ., 1987, Diniz, 1997, Farhang-Boroujeny, 1998, Haykin, 2002, Haykin ve Widrow, 2003). Her adımda yapılan normalizasyon işlemi µ adım parametresinin λmax özdeğerine olan bağımlılığını ortadan kaldırır. Böylece µ adım parametresinin sayısal değeri algorit- manın daha hızlı yakınsayabilmesi için rahatlıkla büyük seçilebilir. NLMS algoritmasının gerçeklen- mesinde yapılan normalizasyon işleminden dolayı çarpma sayısı ilk bakışta (3M + 2) gibi görünse de, xT (n)x(n) ifadesinin değerinin hesaplanması için gereken işlem sayısı M ’den 1’e düşürülebilir. Burada NLMS algoritmasındaki xT (n)x(n) çarpımı xT (n)x(n) = x2(n) + x2(n −1) +L+ x2(n − M +1) (10) şeklinde yazılabilir. Buradan xT (n +1)x(n +1) çarpımı xT (n +1)x(n +1) = xT (n)x(n) + x2(n +1) − x2(n − M +1) (11) şeklinde, daha önce hafızada saklanan toplama bir sonraki adımda sadece x2(n +1) çarpımı ilave edilip önceden hesaplanmış olan son terim x2 (n − M +1) çıkarılarak elde edilebilir. Yani sadece x2(n +1) çarpımından dolayı çarpma sayısı 1 olur (Treichler ve diğ., 1987). Bu durumda NLMS al- goritmasının gerçeklenmesi için yapılan çarpma sayısı LMS algoritmasına göre 2 artarak (2M + 3) olmaktadır. Đzdüşüm (projection) algoritması olarak da adlandırılan NLMS algoritması aynı zamanda w(n +1) − w(n) parametre değişiminin Euclidean normunun karesini d (n) = wT (n +1)x(n) sınır- lamasına göre minimum yapan w(n +1) parametrelerinin hesaplanmasıyla da elde edilebilmektedir (Goodwin ve Sin, 1984, Haykin, 2002). AP algoritmasında sınırlama sayısı k = 1,2,..., P için d (n − k) = wT (n +1)x(n − k) olmak üzere birden fazla olup, P < M olmak şartıyla algoritmanın izdüşüm sayısını belirlemektedir ve kullanılan izdüşüm sayısına bağlı olarak işlem yükü artmaktadır (Haykin, 2002, Haykin ve Widrow, 2003). 2.2. GS (Gauss-Seidel) Algoritması GS algoritmasındaki orijinal fikir, en küçük kareler tahminlerinin elde edilmesinde, lineer denklem takımlarının çözümünde kullanılan iteratif yöntemlerden yararlanmaktır. GS algoritması, adaptif filtre katsayılarının ayarlamak için Rwopt = p ile verilen normal denklemin çözümünde kulla- nılmaktadır. Burada wopt M adet filtre katsayısını içeren M ×1 boyutlu optimum katsayı vektörü- dür. R matrisi ve p vektörü (2) ile verilmiştir. Bilindiği gibi R korelasyon matrisi simetrik ve pozi- tif tanımlı olan bir matristir (Haykin, 2002). Nümerik olarak, doğrusal denklem takımını oluşturan kare matrisin simetrik ve pozitif tanımlı olması durumunda, GS algoritmasının herhangi bir başlangıç değeri için denklem takımını sağlayan çözüm değerine iteratif olarak yakınsadığı matematiksel olarak Golub ve Van Loan (1996) tarafından gösterilmiştir. GS algoritmasıyla tekrarlamalı parametre tahmin işleminin başlangıç noktası, zaman ortalama- lı normal denklemin GS algoritmasıyla çözümü üzerine kuruludur. Çünkü pratik uygulamalarda R matrisinin ve p vektörünün değerinin bilinmemesi durumunda tahmin edilmiş değerleri kullanılarak bir yaklaşıklık yapılır. GS algoritması R korelasyon matrisinin ve p korelasyon vektörünün birikimli tahmini değerini kullanır. Bu yaklaşık tahmini değerler n adet veri grubu kullanıldığında aşağıdaki gibi yazılabilir, 1 n 1 n R(n) ≅ ∑x(k)xT (k) , p(n) ≅ ∑x(k)d (k) (12) n k =1 n k =1 8 8 Uludağ Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, Cilt 13, Sayı 2, 2008 veya 1/ n çarpanı göz önüne alınmadan veri örnekleri alındıkça iteratif olarak R(n) = R(n −1) + x(n)xT (n) , p(n) = p(n −1) + x(n)d (n) (13) şeklinde güncellenebilir. Daha sonra bir adımlık GS iterasyonu R(n)w(n) = p(n) olarak yazılan zaman ortalamalı normal denklemin çözümünde w(n +1) = −(R (n) + R (n))−1R (n)w(n) + (R (n) + R (n))−1L D U L D p(n) (14) şeklinde kullanılır, yani iterasyon indisi ayrık zaman indisi olarak alınmıştır. Burada RL (n) , RD (n) ve RU (n) sırasıyla korelasyon matrisinin (13) ile verilen tahmini değerinin alt üçgen, köşegen ve üst üçgen kısımlarını içeren kare matrisleri gösterir. Burada (14) ile verilen eşitlikte iki işlem birleştiril- miştir. Bunlar, korelasyon matrisi ile korelasyon vektörünün tahmin edilmesi ve GS algoritması ile zaman ortalamalı normal denklemin çözümüdür (Koçal,1998). Pratik uygulamada filtre katsayıları  i−1 M  wi (n +1) = pi (n) −∑Rij (n)w j (n +1) − ∑Rij (n)w j (n) Rii (n) ,  j =1 j =i+1  (15) ( i = 1,2,K,M ) şeklinde sırayla güncellenir. Burada Rij (n) korelasyon matrisinin i. satırına ve j. sütununa denk düşen elemanını gösterir, pi (n) korelasyon vektörünün i. elemanını gösterir ve wi (n) katsayı vektö- rünün i. elemanını gösterir. Ayrıca, adaptif FIR filtre kullanıldığında ve korelasyon matrisinin simet- rik olduğu göz önüne alındığında aynı iterasyonu giriş işaretinin korelasyon katsayılarına bağlı olarak  i−1 M  wi (n +1) = pi (n) −∑ri− j (n)w j (n +1) − ∑rj −i (n)w j (n) r0(n) ,  j =1 j =i+1  (16) ( i = 1,2,K,M ) şeklinde de yazılabilir. Burada R(k) korelasyon matrisinin elemanlarını oluşturan oto-korelasyon katsayılarını ve p(k) korelasyon vektörünün elemanlarını oluşturan çapraz-korelasyon katsayıları sırasıyla aşağıdaki gibi tanımlanabilir. ri = E[x(n)x(n − i)] , ( i = 0,1,K,M −1) (17) pi = E[d (n)x(n − i)] , ( i = 1,2,K,M ) (18) Pratik uygulamalarda bu katsayıların tahmini değerleri veri örnekleri alındıkça iteratif olarak 1/ n çarpanı göz önüne alınmadan aşağıdaki gibi güncellenebilir. ri (n) = ri (n) + x(n)x(n − i) , ( i = 0,1,K,M −1) (19) pi (n) = pi (n) + d (n)x(n − i) , ( i = 1,2,K,M ) (20) Burada sırasıyla (19) ve (20) ile verilen korelasyon katsayıları tahminlerinin (16) ile birlikte kullanıldığında elde edilen algoritma stokastik GS algoritması olarak adlandırılmıştır (Koçal, 2008). 89 Tiryaki, S. ve diğ.: Yeni Bir Adaptif Filtreleme Yöntemi:Hibrid Gs-Nlms Algoritması Bu algoritmanın gerçeklenmesinde (M 2 + 2M ) adet çarpma işlemi yapılmaktadır. Korelasyon matri- sinin (13) ile verilen tahmin edilmiş değerinin pozitif tanımlı olması durumunda stokastik GS algorit- ması tahminleri optimum değerine yakınsamaktadır (Hatun ve Koçal, 2005). GS algoritması farklı bir bakış açısıyla bir optimizasyon algoritması şeklinde EDS (Euclidean Direction Search) adı ile de önerilmiş ve bazı adaptif sinyal işleme uygulamalarında kullanılmıştır (Xu ve diğ. 1998, 1999a, 1999b, Bose ve Xu, 2002, Mabey ve diğ. 2004, Bose, 2004). Bu çalışmalarda Gauss-Seidel algoritması adaptif FIR filtre katsayılarının ayarlanmasında kullanılmıştır. Önerilen bu GS tabanlı algoritmaların işlem yükü RLS algoritmasından daha az olup, yakınsama hızı RLS algorit- masına yakındır ve korelasyon matrisinin özdeğer yayılımının küçük olması durumunda RLS algorit- masına çok yakın sonuçlar vermektedir (Koçal, 1998, Bose, 2004). 3. HĐBRĐD GS-NLMS ALGORĐTMASI GS algoritmasının yakınsama hızı RLS algoritmasına yakın olmakla birlikte, gerçekleme esna- sında (M 2 + 2M ) adet çarpma işlemi yapılması, algoritmanın yüksek örnekleme hızlarında kullanıl- dığı bazı uygulamalarda dezavantaj oluşturabilmektedir. Bu çalışmada, yakınsama hızı iyi olan GS algoritmasıyla işlem yükü az olan NLMS algoritmaları birlikte kullanılarak işlem yükü GS algoritma- sından daha az olan ve NLMS algoritmasından daha hızlı yakınsayan hibrid bir algoritma elde edilmiş- tir. Önerilen hibrid GS-NLMS algoritmasının adaptif filtreleme işleminde kullanımı Şekil 2’deki blok diyagramda görülmektedir. Önerilen hibrid GS-NLMS algoritmasında, Şekil 2’de de gördüğü gibi, M uzunluklu bir adaptif filtrenin katsayılarının 1 ≤ G < M olmak üzere ilk G tanesi GS algoritması ile güncellen- mekte ve geriye kalan (M − G) tanesi de NLMS algoritması ile güncellenmektedir. Hibrid GS- NLMS algoritmasında bir önceki adımda güncellenmiş katsayı vektörünün ilk G elemanı GS algo- ritması kullanılarak güncellenir. NLMS algoritmasında ise öncelikle ilk G elemanı güncellenmiş kat- sayı vektörü kullanılarak anlık hata bilgisini hesaplanır, sonra hesaplanan anlık hata bilgisi kullanıla- rak katsayı vektörünün geriye kalan (M − G) tane elemanı güncellenir. Elde edilen yeni hibrid algo- ritmanın gerçeklenmesinde G(M −1) + 3M + 2 adet çarpma işlemi yapılmaktadır, yani önerilen hibrid algoritma işlem yükü açısından GS ile NLMS arasında kalmaktadır. Ayrıca, önerilen hibrid GS- NLMS algoritmasının işlem yükü, GS ve NLMS algoritmaları arasında paylaşılan parametre sayısına bağlı olarak değişmektedir. Önerilen hibrid GS-NLMS algoritmasının gerçeklenmesi ve işlem yükü aşağıda detaylı olarak açıklanmaktadır. x(n)  w1(n)  y(n) d (n) A d a p t i f   Filtre  M  − + wM (n) e(n) w1(n)  wG +1(n) GS     M  NLMS  M  wG (n) ↓  [w1 ...wG ]   wM (n)  Şekil 2: Hibrid GS-NLMS algoritması 9 0 Uludağ Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, Cilt 13, Sayı 2, 2008 Önerilen hibrid algoritma iki kısımdan oluşmaktadır. Bu durumda ilk kısımda kullanılan GS algoritmasının kararlı olması için (13) eşitliğindeki gibi hesaplanan korelasyon matrisi tahminlerinin pozitif tanımlı olması durumunda ve aynı zamanda ikinci kısımda kullanılan NLMS algoritmasının kararlı olması için kullanılan adım parametresinin 0 < µ < 2 aralığında algoritma kararlı olacak şe- kilde seçilmesi durumunda hibrid GS-NLMS algoritması da kararlı olacaktır. 3.1. Hibrid GS-NLMS Algoritmasının Gerçeklenmesi ve Đşlem Yükü Bu kısımda, GS ve NLMS algoritmalarında hesaplanan benzer ifadeler arasındaki bağlantılar belirlenerek hibrid GS-NLMS algoritmasının işlem yükünün azaltılması için gerekli çalışmalar yapıl- mıştır. Önce GS algoritmasında kullanılan korelasyon katsayılarıyla NLMS algoritmasında hesapla- nan xT (n)x(n) vektör çarpımı arasında bir ilişki bulunarak hibrid algoritmanın işlem yükünde bir azalma sağlanabilir. NLMS algoritmasındaki xT (n)x(n) çarpımı M −1 xT (n)x(n) = ∑ x2(n − i) (21) i=0 şeklinde yazılabilir. Toplam sembolündeki indisler değiştirilerek aynı çarpım n xT (n)x(n) = ∑ x2(i) (22) i=n−(M −1) olarak da yazılabilir. Diğer taraftan, korelasyon katsayılarının birikimli tahmini değerleri ise 1/ n çar- panı göz önüne alınmadan aşağıdaki gibi yazılabilir. n rk (n) = ∑ x(i)x(i − k) , k = 0,1,K,(M −1) (23) i=1 Burada k = 0 için sıfırıncı korelasyon katsayısı n r0(n) = ∑ x2(i) (24) i=1 olarak yazıldığında iki parçanın toplamı halinde n−M n r0(n) = ∑ x2(i) + ∑ x2 (i) (25) i=1 i=n−(M −1) olarak yazılabilir. Bu eşitlikte (22) ve (24) eşitlikleri kullanıldığında r0 (n) = r0 (n − M ) + x T (n)x(n) (26) sonucuna ulaşılır. Bu sonuca göre xT (n)x(n) çarpımı sıfırıncı korelasyon katsayısına bağlı olarak xT (n)x(n) = r0 (n) − r0 (n − M ) (27) 91 Tiryaki, S. ve diğ.: Yeni Bir Adaptif Filtreleme Yöntemi:Hibrid Gs-Nlms Algoritması şeklinde hesaplanabilir. Görüldüğü gibi NLMS algoritmasında bulunan ve (10) ile verilen xT (n)x(n) çarpımı hibrid algoritmanın gerçeklenmesinde çarpma işlemi yapmadan tek bir çıkarma işlemi kullanı- larak hesaplanabilir. GS algoritmasında r0 (n) korelasyon katsayısı zaten hesaplanmaktadır. Bu du- rumda hibrid GS-NLMS algoritmasının gerçeklenmesinde ikinci aşamada, (M − G) tane filtre katsa- yısını güncellemek için kullanılan NLMS algoritmasında (27) eşitliğinden yararlanıldığında, işlem yükü yapılan 1 adet bölme işlemi ile birlikte 2(M − G) + 2 olmaktadır. Hibrid GS-NLMS algoritmasının gerçeklenmesinde ilk aşamada, G adet filtre katsayısının güncellenmesinde GS algoritmasının kullanılması durumunda, her bir parametrenin güncellenmesi için M adet olmak üzere G adet katsayının güncellenmesi için GM adet çarpma işlemi yapılmaktadır. Ayrıca, M adet oto-korelasyon katsayısının güncellenmesinde M adet çarpma işlemi yapılmaktadır ve G adet çapraz-korelasyon katsayısının güncellenmesinde G adet çarpma işlemi yapılmaktadır. Sonuç olarak hibrid algoritmada ilk aşamada filtre katsayılarının ilk G tanesinin GS algoritmasıyla güncellenmesi durumunda (GM + G + M ) adet çarpma işlemi yapılmaktadır. Hibrid algoritmanın ikinci aşamasında geriye kalan (M − G) tane filtre katsayısının NLMS algoritmasıyla güncellenmesi durumunda ise 2(M − G) + 2 adet çarpma işlemi yapılmaktadır. Sonuç olarak hibrid algoritmanın gerçeklenmesinde toplam G(M −1) + 3M + 2 adet çarpma işlemi yapılmaktadır. Hibrid algoritmanın gerçeklenmesinde, ilk aşamada G tane filtre katsayısını güncellemek için kullanılan GS algoritmasındaki parametrelerin yeri de işlem yükünü bir miktar etkilemektedir. Burada M uzunluklu bir adaptif filtrenin katsayılarını güncellemek için kullanılabilecek olan GS algoritması daha detaylı olarak aşağıdaki gibi verilebilir.   w2 (n)     [ ]  w3(n)  w1(n +1) = p1(n) − ⋅   r1(n) r2(n) L rM −1(n)  r0 (n)   M     wM (n) M (28)   w1(n +1)     + =  w w (n 1) p (n) − [r (n) r  2(n +1) M  M M −1 M −2 (n) L r1(n)]⋅  r0(n)   M     wM −1(n +1) Burada w1(n) ile wM (n) arasında kalan filtre katsayıları, M tek olduğunda j = −M −3 − M −3, , 1,0,1, ,  L L   için  2   2   w1(n+1)   +  (29)    w (n 1) wM+1+2 j (n+1) = pM+1+2 j (n) − 2  r  M−1+2 j (n) L r1(n) r1(n) L rM−1−2 j (n) ⋅  r0(n) 2   M 2  2 2       wM (n)  şeklinde hesaplanabilir, M çift olduğunda ise 9 2 Uludağ Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, Cilt 13, Sayı 2, 2008 j = −M −2, ,− M1,0,1,   L L, −1 için  2   2   w1(n+1)   (30)    w (n+1)  wM (n+1) = pM (n) − rM (n) L r1(n) r1(n) L rM (n) ⋅  2  r (n) + j  + j  + − 0 j 1 − j   2 2 2 2  M      w M (n)  şeklinde hesaplanabilir. Hibrid GS-NLMS algoritmasının ilk aşamasındaki GS algoritmasıyla güncel- lenen sınırlı sayıdaki G adet filtre katsayısı, w(n) katsayı vektörünün ortasından seçilirse, daha az oto-korelasyon katsayısının güncellenmesiyle birlikte hibrid algoritmadaki toplam çarpma işlemi yü- künün bir miktar daha azalacağı görülebilir. Örneğin filtre uzunluğu M ’nin tek olması durumunda ortadaki tek sayıda G tane filtre katsayısının, ve çift olması durumunda ortadaki çift sayıda G tane filtre katsayısının GS algoritmasıyla güncellenmesi durumunda N = (M + G) / 2 adet oto-korelasyon katsayısı kullanılmaktadır. Bu durumda hibrid algoritmanın ilk aşamasında kullanılan GS algoritma- sındaki çarpma işlemi sayısı azalarak (GM + G + N ) olmaktadır. Bu durumda hibrid algoritmanın gerçeklenmesinde toplam çarpma işlemi sayısı da bir miktar azalarak G(M −1) + N + 2M + 2 ol- maktadır. 4. SĐMÜLASYON SONUÇLARI Önerilen hibrid GS-NLMS algoritmasının yakınsama özellikleri yapılan bir simülasyon çalış- masıyla örnek bir adaptif kanal denkleştirme problemi üzerinde test edilmiştir ve benzer algoritmalarla birlikte karşılaştırmalı olarak incelenmiştir. Örnek olarak Haykin (2002) ve Bose (2004) tarafından da kullanılan ve darbe cevabı  1  2π   1+ cos  (n − 2)  , n = 1,2,3h(n) =  2   W  (31)   0 , diğer olan doğrusal kanal modeli kullanılmıştır. Simülasyon çalışmasında kullanılan sistemin blok diyagra- mı Şekil 3’te görülmektedir. Gecikme d (n) Rastgele x(n) Adaptif Kanal + Sinyal Kanal Denkleştirici ? Üreteci (1) u(n) + y(n) + v(n) e(n) Rastgele Sinyal Üreteci (2) Şekil 3: Adaptif kanal denkleştiricinin blok diyagramı 93 Tiryaki, S. ve diğ.: Yeni Bir Adaptif Filtreleme Yöntemi:Hibrid Gs-Nlms Algoritması Blok diyagramda görülen rastgele sayı üreteci (1) kanalı uyarmak için kullanılan u(n) test sinyalini üretmektedir. Burada u(n) sinyali m1 seviyeli ve sıfır ortalamalı rastgele sinyaldir. Rastgele sinyal üreteci (2) ise kanal çıkışını bozan rastgele gürültü kaynağıdır. Simülasyon çalışmasında sıfır ortalamalı ve varyansı σ 2v = 0.001 olan normal dağılıma sahip rastgele gürültü dizisi kullanılmıştır. Bu durumda kanal denkleştiricinin giriş işareti 3 x(n) = ∑h(k)u(n − k) + v(n) (32) k =1 eşitliği kullanılarak hesaplanmıştır. Kanal denkleştirici olarak uzunluğu M = 11 olan adaptif FIR filtre kullanılmıştır. Ayrıca, kanal denkleştiricinin takip etmesi gereken d (n) sinyali olarak 7 adım geciktirilmiş giriş sinyali kullanılmıştır (Haykin, 2002). Kanalın darbe cevabındaki W parametresi giriş işaretine ait korelasyon matrisinin özdeğer yayılımını kontrol etmek için kullanılmaktadır. Burada W değeri arttığında korelasyon matrisinin özdeğer yayılımı da artmaktadır (Haykin, 2002). Bu para- metre, yapılan simülasyon çalışmasında özdeğer yayılımının büyük olması için ve algoritmaların ya- kınsama özellikleri arasındaki farkın belirgin olması için W = 3.7 olarak seçilmiştir. Burada öncelikle GS-NLMS algoritması GS ve NLMS algoritmalarıyla birlikte karşılaştırmalı olarak incelenmiştir. Yapılan simülasyon çalışmasında, NLMS ve önerilen hibrid GS-NLMS algoritmalarında kullanılan adım parametresi µ = 1 olarak seçilmiştir. Birbirinden farklı giriş sinyallerinin ve ölçme gürültüsünün kullanıldığı 500 adet simülasyonun ortalaması alınarak elde edilen ortalama karesel hata grafikleri Şekil 4’te görülmektedir. Burada hibrid GS-NLMS algoritmasındaki GS algoritmasıyla adaptif FIR filtrenin katsayı vektörünün ilk G parametresi güncellenmiştir ve GS algoritmasıyla güncellenen G adet parametre sayısı sırasıyla G = 3,5,7,9 olarak alınmıştır. Elde edilen sonuçlara göre, hibrid GS- NLMS algoritmasının yakınsama hızı GS ve NLMS algoritmalarının arasında kalmaktadır ve GS algo- ritmasıyla güncellenen G adet parametre sayısı arttıkça, önerilen hibrid GS-NLMS algoritmasın ya- kınsama hızının ve hesaplanan ortalama karesel hatanın minimum değerinin GS algoritmasına yaklaş- tığı görülmektedir. 0 10 NLMS Alg. G = 3 (Hibrid Alg.) G = 5 (Hibrid Alg.) G = 7 (Hibrid Alg.) G = 9 (Hibrid Alg.) G = 11 (G-S Alg.) -1 10 -2 10 100 200 300 400 500 600 700 800 900 1000 örnek Şekil 4: Hibrid GS-NLMS algoritmasının performansının farklı G değerlerine bağlı değişimi (Katsayı vektöründeki ilk G tane katsayı GS algoritmasıyla güncellenmiştir) 9 4 Karesel Ortalama Hata [dB] Uludağ Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, Cilt 13, Sayı 2, 2008 Daha sonra, adaptif FIR filtrenin katsayı vektörünün ortasındaki G tane parametrenin GS al- goritmasıyla güncellendiği ikinci simülasyon çalışması yapılmıştır ve GS algoritmasıyla güncellenen G adet parametre sayısı sırasıyla G = 3,5,7,9 olarak alınmıştır. Birbirinden farklı giriş sinyallerinin ve ölçme gürültüsünün kullanıldığı 500 adet simülasyonun ortalaması alınarak elde edilen ortalama karesel hata grafikleri Şekil 5’te görülmektedir. Elde edilen sonuçlara göre, yine hibrid GS-NLMS algoritmasının yakınsama hızı açısından GS ve NLMS algoritmalarının arasında kaldığı görülmüştür ve GS algoritmasıyla güncellenen G adet parametre sayısı arttıkça, önerilen hibrid GS-NLMS algo- ritmasın yakınsama hızının ve hesaplanan ortalama karesel hatanın minimum değerinin GS algoritma- sına yaklaştığı görülmüştür. Yapılan 500 adet simülasyon çalışmasının ortalaması alınarak elde edilen parametre tahminleri, yani adaptif kanal denkleştiricinin darbe cevabı ise Şekil 6’da görülmektedir. Yapılan ikinci simülasyon çalışması sonucunda elde edilen Şekil 5’e bakıldığında, katsayı vektörünün ortasındaki büyük değerli katsayıların GS algoritmasıyla güncellenmesi durumunda, hibrid algoritma- nın yakınsama hızının daha belirgin bir şekilde arttığı gözlenmiştir. 0 10 NLMS Alg. G = 3 (Hibrid Alg.) G = 5 (Hibrid Alg.) G = 7 (Hibrid Alg.) G = 9 (Hibrid Alg.) G = 11 (G-S Alg.) -1 10 -2 10 100 200 300 400 500 600 700 800 900 1000 örnek Şekil 5: Hibrid GS-NLMS algoritmasının performansının farklı G değerlerine bağlı değişimi (Katsayı vektörünün ortasındaki G tane katsayı GS algoritmasıyla güncellenmiştir) 2 1.5 1 0.5 0 -0.5 -1 1 2 3 4 5 6 7 8 9 10 11 örnek ( n ) Şekil 6: Yapılan simülasyon çalışmasında elde edilen parametre tahminleri (Adaptif kanal denkleştiricinin darbe cevabı) 95 Karesel Ortalama Hata [dB] kanal denkleştiricinin darbe cevabı Tiryaki, S. ve diğ.: Yeni Bir Adaptif Filtreleme Yöntemi:Hibrid Gs-Nlms Algoritması Hibrid GS-NLMS algoritmasının işlem yükü açısından diğer algoritmalarla karşılaştırılması durumunda, M = 11 için aşağıdaki Tablo 1’de görülen sonuçlar elde edilir. Bu sonuçlara göre, GS- NLMS algoritmasının işlem yükü, kullanılan G değerine de bağlı olarak GS ve NLMS algoritmaları arasında kalmaktadır. G değeri küçük olduğunda işlem yükü NLMS algoritmasına yakın olmakta, G < M olmak üzere büyük değerler aldığında ise işlem yükü GS algoritmasına yakın olmaktadır. Tablo 1. M = 11 için hibrid GS-NLMS algoritmasının işlem yükü Algoritma: M = 11 için işlem yükü: NLMS Algoritması 25 GS Algoritması 143 Hibrid GS-NLMS ( G = 1 ) 45 Hibrid GS-NLMS ( G = 2 ) 55 Hibrid GS-NLMS ( G = 3 ) 65 Hibrid GS-NLMS ( G = 5 ) 85 Hibrid GS-NLMS ( G = 7 ) 105 Hibrid GS-NLMS ( G = 8 ) 115 Hibrid GS-NLMS ( G = 10 ) 135 Hibrid algoritmanın gerçeklenmesinde, ilk aşamada GS algoritmasıyla güncellenen sınırlı sa- yıdaki G adet filtre katsayısının w(n) filtre katsayı vektörünün ortasından seçilmesi durumunda, daha az oto-korelasyon katsayısının kullanılmasından dolayı işlem yükünün bir miktar daha azaldığı Tablo 2’de görülmektedir. Tablo 2. M = 11 için hibrid GS-NLMS algoritmasının işlem yükünün azaltılması Algoritma: Đlk G adet katsayı için: Ortadaki G adet katsayı için: Hibrid GS-NLMS ( G = 1 ) [w1] → 45 [w6 ] → 40 Hibrid GS-NLMS ( G = 2 ) [w1 w2 ] → 55 [w5 w6 ] → 51 Hibrid GS-NLMS ( G = 3 ) [w1 w2 w3] → 65 [w5 w6 w7 ] → 61 Hibrid GS-NLMS ( G = 5 ) [w1 L w5 ] → 85 [w4 L w8 ] → 82 Hibrid GS-NLMS ( G = 7 ) [w1 L w7 ] → 105 [w3 L w9 ] → 103 Hibrid GS-NLMS ( G = 9 ) [w1 L w9 ] → 125 [w2 L w10 ] → 122 Buradan M = 11 filtre uzunluğu ve farklı G değerleri için GS algoritmasıyla w(n) katsayı vektörünün ortasındaki G adet filtre katsayının güncellenmesi durumunda, hibrid algoritmanın top- lam işlem yükünde bir miktar daha azalma olduğu görülmektedir. Bu azalma miktarı işlem yükü açı- sından küçük G değerleri için daha fazla olmaktadır. Özellikle hibrid GS-NLMS algoritmasında w(n) katsayı vektörünün tam ortasındaki 2 katsayının GS algoritması tarafından güncellenmesi du- rumunda G = 2 için 51 adet, tam ortadaki 1 katsayının GS algoritması tarafından güncellenmesi du- rumunda G = 1 için 40 adet çarpma işlemi yapılmaktadır. 9 6 Uludağ Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, Cilt 13, Sayı 2, 2008 5. SONUÇLAR Bu çalışmada, adaptif filtre katsayılarını ayarlamak için GS ve NLMS algoritmalarının birlikte kullanılmasıyla hibrid bir algoritma oluşturulmuş ve elde edilen yeni algoritmanın yakınsama hızı ve işlem karmaşıklığı benzer algoritmalarla birlikte karşılaştırmalı olarak incelenmiştir. Elde edilen so- nuçlara göre, önerilen hibrid algoritmanın işlem karmaşıklığı veya yakınsama hızı açısından bilinen diğer algoritmaların arasında kaldığı ve bir ara yöntem olarak diğer algoritmalara iyi bir alternatif ol- duğu görülmüştür. 6. KAYNAKLAR 1. Bose, T. and Xu, G. F. (2002) The Euclidean direction search algorithm for adaptive filtering, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E85-A(3), 532-539. 2. Bose, T. (2004) Digital Signal and Image Processing, John Wiley, New Jersey. 3. Diniz, P. S. R. (1997) Adaptive Filtering: Algorithms and Practical Implementation, Kluwer Academic Publishers, Boston. 4. Farhang-Boroujeny, B. (1998) Adaptive Filters: Theory and Applications, John Wiley & Sons, Chicester. 5. Golub, G. H. and Van Loan, C. F. (1996) Matrix Computations, 3rd Ed., John Hopkins University Press, Baltimore and London. 6. Goodwin, G. C. and Sin, K. S. (1984) Adaptive Filtering, Prediction and Control, Prentice-Hall, Englewood Cliffs, New Jersey. 7. Hatun, M. ve Koçal, O. H. (2005) Adaptif filtrelerde Gauss-Seidel algoritmasının stokastik yakınsama anali- zi, Uludağ Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, 10(2), 87-92. 8. Haykin, S. (2002) Adaptive Filter Theory, 4th Ed., Prentice-Hall, Upper Saddle River, New Jersey. 9. Haykin, S., Widrow, B. (editors). (2003) Least-Mean-Square Adaptive Filters, Wiley-Interscience, New Jersey. 10. Koçal, O. H. (1998) A new approach to least squares adaptive filtering, IEEE International Symposium on Circuits and Systems, Monterey, California, 261-264. 11. Mabey, G.W., Gunther, J., Bose, T. (2004) An Euclidean direction based algorithm for blind source separation using a natural gradient, IEEE International Conference on Acoustics, Speech and Signal Processing, 5, 561-564. 12. Treichler, J. R., Johnson, C. R., Larimore, M. G. (1987) Theory and Design of Adaptive Filters, Wiley- Interscience, New York. 13. Widrow, B., Stearns, S. D. (1985) Adaptive Signal Processing, Prentice-Hall, Upper Saddle River, New Jer- sey. 14. Xu, G. F., Bose, T., Schroeder, J. (1998) Channel equalization using an Euclidean direction search based adaptive algorithm, IEEE Global Telecommunication Conference, 6, 3063-3068. 15. Xu, G. F., Bose, T., Schroeder, J. (1999a) The Euclidean direction search algorithm for adaptive filtering, IEEE International Symposium on Circuits and Systems, 3, 146-149. 16. Xu, G. F., Bose, T., Kober, W., Thomas, J. (1999b) A fast adaptive algorithm for image restoration, IEEE Transaction on Circuits and Systems-I, 46(1), 216-220. Makale 12.05.2008 tarihinde alınmış, 13.08.2008 tarihinde kabul edilmiştir. İletişim Yazarı: O. H. Koçal (kocal@uludag.edu.tr). 97