張嘉韋 馮 浩 高 勇

(四川大學(xué)電子信息學(xué)院 成都 610065)

?

單通道混合信號粒子濾波盲分離算法的快速實現(xiàn)

張嘉韋 馮 浩 高 勇

(四川大學(xué)電子信息學(xué)院 成都 610065)

粒子濾波可以處理非線性非高斯問題,可以應(yīng)用于混合信號的盲分離中,是一種有效的盲分離算法。但是粒子濾波算法存在一個很大的缺陷,其復(fù)雜度太大,為了減少粒子濾波運算時間、提高運算效率,通過對粒子濾波實現(xiàn)過程中的符號向量進行前置擴維,從而改進了粒子濾波實現(xiàn)方法。仿真結(jié)果表明:改進后的算法在運算速度上相比之前有了比較明顯的提升。

粒子濾波; 盲分離; 復(fù)雜度; 擴維; 運算速度

Class Number TP301

1 引言

通信混合信號盲分離是信號處理領(lǐng)域近年來的熱點問題,在語音信號處理、信號去噪、無線通信、目標(biāo)跟蹤等領(lǐng)域有廣泛的應(yīng)用前景[1～2]。隨著通信技術(shù)的發(fā)展,產(chǎn)生了大量的非線性信號處理問題,傳統(tǒng)的數(shù)字信號處理技術(shù)已經(jīng)不能完全滿足信號處理的需求。粒子濾波[3]算法是近幾年發(fā)展起來的一種以一組隨機粒子來模擬估計信號的分布為核心思想的濾波算法,它提供了一種解決非線性非高斯模型問題的便利、有效的途徑[4]。粒子濾波算法由Liu和Li于2006年首次應(yīng)用到混合信號的單通道盲分離中[5],這是盲分離領(lǐng)域研究的一大進步。但是在混合信號盲分離算法實現(xiàn)的過程中,隨著調(diào)制信號復(fù)雜程度的增加和粒子數(shù)的增加,整個程序的運算量會大幅度增加[6],有的甚至已經(jīng)超出個人計算機的計算能力。針對這一問題,我們對粒子濾波部分的實現(xiàn)進行了分析與改進,對粒子濾波實現(xiàn)過程中的符號向量進行前置擴維,加快了粒子濾波程序的運算速度,提升了運算效率。

2 粒子濾波算法基本原理

粒子濾波算法步驟如下[7]:

粒子濾波用于信號的盲分離算法時,其基本思想是[8]:將兩路信號的符號序列和調(diào)制參數(shù)作為狀態(tài)變量進行建模,用粒子濾波算法估計出這些變量的后驗概率分布,則符號序列后驗概率分布的期望就是最終的分離結(jié)果。

首先建立狀態(tài)轉(zhuǎn)移模型,狀態(tài)方程如下:

Φk=ΩΦk-1+dk

(1)

Θk=f(Θk-1,uk)

(2)

式中

是L×L移位矩陣,L為串?dāng)_長度;Φk=[Φk-L1+1,…,Φk+L2]是符號對向量,該向量中的元素Φk=(a1,k,a2,k)為k時刻符號對;dk=[0,…,0,Φk+L2]是包含最新到達符號對Φk+L2的更新向量;Θk={h1,k,h2,k,τ1,k,τ2,k,Δω1,Δω2,θ1,θ2}是信號參數(shù)集,uk是參數(shù)擾動。

(3)

其中,SD+1Φk+L2-D:k+L2,S′DΦk+L2-D:k-1+L2。

直接計算式(3)中分子、分母的求和式比較復(fù)雜,以式(3)中分子為例做如下近似計算以減小運算量:

(4)

對式(4)利用近似式exp(x)+exp(y)≈exp(max(x,y))可化簡如下[8]:

(5)

以分離信號為BPSK調(diào)制的兩路信號構(gòu)成的混合信號盲分離算法為例,實現(xiàn)過程中,采用兩倍采樣[9],對應(yīng)的粒子濾波部分的Matlab程序偽代碼如下:

初始化;

構(gòu)造根升余弦匹配濾波下的碼元波形gself;

生成長度為D的所有序列組合dk,用于構(gòu)造等效于式(5)中a1,k-j、a2,k-j的a_dk、b_dk;

fori=1:N

將高斯噪聲抖動模型進行修正;

for ii=1:2^(D+1)

構(gòu)造a_dk,a_dk = [ak, dk(ii, :)];

for jj=1:2^(D+1)

構(gòu)造b_dk,b_dk = [bk, dk(ii, :)];

for ki = D:-1:0

構(gòu)造式(5)中相減部分dify,該過程會調(diào)用多項式估值函數(shù)polyval:

dify(2*ki+2)= f1(ki, a_dk, b_dk, gself)

dify(2*ki+1)= f2(ki, a_dk, b_dk, gself)

end for

取sum(abs(dify).^2)對應(yīng)的高斯分布值,用于計算組合下y(k-D)到y(tǒng)(k)的概率,為權(quán)值更新的分子、分母做準(zhǔn)備;

end for

end for

權(quán)值更新;

end for

權(quán)值歸一化;

進行參數(shù)估計;

進行重采樣;

其中,N是粒子數(shù);D為平滑長度,是折中復(fù)雜度與性能的參數(shù),這里取D=2。

3 快速實現(xiàn)

經(jīng)過在Matlab中的測試分析發(fā)現(xiàn):由于在構(gòu)造式(5)中相減部分dify過程中的符號向量對其運算量影響較大,使用的多項式估值函數(shù)polyval被調(diào)用多次,導(dǎo)致該部分占用了整個粒子濾波程序的很大一部分時間,故利用Matlab對矩陣操作的優(yōu)勢來減少該部分的運算時間以達到提高整個程序的運算速度的目的。

在上述粒子濾波算法中,每進行一次dify的構(gòu)造,就要使用一次a_dk和b_dk,根據(jù)前文中提到a_dk和b_dk的構(gòu)造方法可知二者都是行向量?，F(xiàn)改進該算法,每進行一次dify的構(gòu)造時,將符號向量進行前置擴維,使其使用的是根據(jù)a_dk和b_dk構(gòu)造的三維矩陣形式。這樣,可以把dify的構(gòu)造過程從ii和jj的循環(huán)中獨立出來,從而可以大大減少多項式估值函數(shù)polyval的調(diào)用次數(shù)并充分利用Matlab對矩陣的操作優(yōu)勢,最終提高整個粒子濾波程序的運算速度。改進后的粒子濾波部分的程序偽代碼如下:

初始化;

構(gòu)造根升余弦匹配濾波下的碼元波形gself;

生成長度為D的所有序列組合dk,用于構(gòu)造等效于式(5)中a1,k-j、a2,k-j的a_dk、b_dk;

fori=1:N

將高斯噪聲抖動模型進行修正;

for ii=1:2^(D+1)

構(gòu)造a_dk,a_dk(ii, :) = [ak, dk(ii,:)];

for ki = D:-1:0

構(gòu)造a_dk2,a_dk2(D-ki+1, :)=a_dk(ii, (k-ki-L1:k-ki+L2));

end for

構(gòu)造a_dk3,a_dk3(:, :, ii) = a_dk2;

end for

for jj=1:2^(D+1)

構(gòu)造b_dk,b_dk(ii, :) = [bk, dk(jj,:)];

for kj = D:-1:0

構(gòu)造b_dk2,b_dk2(D-ki+1, :)=b_dk(jj, (k-ki-L1:k-ki+L2));

end for

構(gòu)造b_dk3,b_dk3(:, :, jj) = b_dk2;

end for

構(gòu)造式(5)中相減部分dify,該過程會調(diào)用多項式估值函數(shù)polyval:

dify_even= f1(a_dk3, b_dk3, gself)

dify_odd= f2(a_dk3, b_dk3, gself)

利用dify_even和dify_odd構(gòu)造之前方法中對應(yīng)的dify,并取sum(abs(dify).^2)對應(yīng)的高斯分布值,用于計算組合下y(k-D)到y(tǒng)(k)的概率,為權(quán)值更新的分子、分母做準(zhǔn)備;

權(quán)值更新;

end for

權(quán)值歸一化;

進行參數(shù)估計;

進行重采樣;

其中,N是粒子數(shù);D為平滑長度,是折中復(fù)雜度與性能的參數(shù),這里取D=2。

在上述改進算法中,dify的構(gòu)造過程中使用了a_dk3和b_dk3這兩個矩陣,它們分別是根據(jù)a_dk和b_dk構(gòu)造的三維矩陣,這樣做相比于未改進算法,多項式估值函數(shù)polyval的調(diào)用次數(shù)大大減少,以粒子數(shù)N=200,平滑長度D=2為例,改進前的粒子濾波算法,每一個符號的粒子濾波需要調(diào)用768次polyval函數(shù),而改進后的粒子濾波算法中,每一個符號的粒子濾波僅需要調(diào)用4次polyval函數(shù),從而大幅度減少了信號盲分離算法中粒子濾波程序的運行時間。

4 實驗仿真及結(jié)果

實驗通過Matlab 8.0平臺進行仿真,實現(xiàn)兩路信號盲分離,分離信號為BPSK調(diào)制,進行兩倍采樣,取粒子數(shù)N=200,符號個數(shù)M=300。運行信號盲分離程序并計算盲分離算法中每個符號進行粒子濾波所需的時間,為了對比清楚,截取了從第50個符號到第100個符號的數(shù)據(jù)繪制成圖,如圖1所示。

圖1 改進前后盲分離算法中的粒子濾波程序運算時間

從圖中可以清楚看到,改進之前的粒子濾波算法一個符號的粒子濾波所需的時間在8.5s左右,而改進之后的粒子濾波算法一個符號的粒子濾波所需的時間僅僅為0.25s左右,加速比達到了約34。

利用同樣的方法,還仿真了輸入信號為QPSK調(diào)制的兩個信號構(gòu)成的混合信號的盲分離算法以及輸入信號為8PSK調(diào)制的兩個信號構(gòu)成的混合信號的盲分離算法,同樣進行兩倍采樣,取粒子數(shù)N=300,符號個數(shù)M=300,計算其粒子濾波算法一個符號所需的時間。其中改進前8PSK調(diào)制的盲分離算法復(fù)雜程度已經(jīng)超出個人計算機的計算能力,程序運行一整天仍沒有算出一個符號的結(jié)果,而改進后8PSK調(diào)制的盲分離算法中一個符號經(jīng)過粒子濾波所需的時間已經(jīng)縮短為4min20s左右。這里為了更加形象地顯示實驗結(jié)果,將BPSK與QPSK調(diào)制的盲分離算法運算時間繪制成表,如表1所示。

表1 粒子濾波算法運算時間對比

從表1中可以發(fā)現(xiàn),改進后的粒子濾波算法的運算時間明顯比改進前的粒子濾波算法更少,而且隨著輸入信號的調(diào)制復(fù)雜度增加,加速程度更加顯著。

5 結(jié)語

粒子濾波方法提供了一種解決非線性非高斯模型問題的便利、有效的途徑,可以有效利用信號的盲分離算法,但是粒子濾波算法的復(fù)雜度太高,特別是在為了保證粒子濾波算法的性能而增加粒子數(shù)的情況下,運算量很大,這是它的一個很大的缺陷。本文介紹了將粒子濾波方法應(yīng)用于混合信號的盲分離中,在編程實現(xiàn)過程中,針對運算量很大這個問題進行分析與改進,通過對粒子濾波實現(xiàn)過程中的符號向量進行前置擴維來提升粒子濾波程序的運算效率。仿真結(jié)果顯示,改進后的粒子濾波算法運算時間比改進前明顯減少,運算效率有較大程度的提高。

[1] VALYRAKIS A, TSAKONAS E E, SIDIROPOULOS N D, et al. Stochastic modeling and particle filtering algorithms for tracking a frequency-hopped signal[J]. IEEE Transactions on Signal Processing,2009,57(8):3108-3118.

[2] 周尚波,何革,柳玉炯.一種改進的粒子濾波目標(biāo)跟蹤算法[J].計算機應(yīng)用研究,2010,27(7):2757-2759.

[3] DJURIC P M, KOTECHA J H, ZHANG J, et al. Particle filtering[J]. IEEE Transactions on Signal Processing,2003,20(5):19-38.

[4] DOUCET A, DE FREITAS N, GORDON N. Sequential Monte Carlo methods in practice[M]. New York: Springer,2001:17-41.

[5] LIU Kai, LI Hui, DAI Xuchu, et al. Single channel blind separation of cofrequency MPSK signals[C]//Proceedings of International Conference on Communication, Internet and Information Technology,2006:42-46.

[6] TU Shilong, CHEN Shaohe, ZHENG Hui, et al. Particle filtering based single-channel blind separation of co-frequency MPSK signals[C]//Proceedings of 2007 International Symposium on Intelligent Signal Processing and Communication Systems,2007:582-585.

[7] 劉凱.粒子濾波在單通道信號分離中的應(yīng)用研究[D].合肥:中國科學(xué)技術(shù)大學(xué),2007.

[8] 萬堅,涂世龍,廖燦輝,等.通信混合信號盲分離理論與技術(shù)[M].北京:國防工業(yè)出版社,2012:227-240.

[9] 崔榮濤,李輝,萬堅,等.一種基于過采樣的單通道MPSK信號盲分離算法[J].電子與信息學(xué)報,2009,31(3):566-569.

[10] 廖燦輝,黃淵凌,周世東.衛(wèi)星成對載波多址信號的一種聯(lián)合分離解調(diào)算法[J].通信學(xué)報,2010,31(6):99-105.

[11] TU Shilong, CHEN Shaohe, ZHENG Hui, et al. On the performance of single-channel blind separation of two co-frequency MPSK signals[C]//2007 IEEE Region 10 Conference TENCON,2007:1-4.

[12] 蔡權(quán)偉,魏平,肖先賜.基于模型擬合的重疊信號盲分離方法[J].電子學(xué)報,2005(10):1794-1798.

High Speed Implementation for Particle Filtering Based Single-channel Blind Separation Algorithm

ZHANG Jiawei FENG Hao GAO Yong

(College of Electronics and Information Engineering, Sichuan University, Chengdu 610065)

Particle filtering can deal with nonlinear and non-Gaussian problem. It’s an effective blind separation algorithm and can be applied to the blind separation of mixed-signal. But high computational complexity is a great flaw of particle filtering. The implementation method of particle filtering is analyzed and improved, based on preposing and dimension expansion of symbol vector, so that particle filtering algorithm’s operation time can be reduced and computation efficiency can be improved. Simulation results show that compared with the traditional algorithm, the improved algorithm has a significant improvement in speed.

particle filter, blind separation, complexity, dimension expansion, computation speed

2015年1月7日,

2015年2月12日 作者簡介:張嘉韋,男,碩士研究生,研究方向:移動通信、混合信號處理。馮浩,男,碩士研究生,研究方向:移動通信。高勇,男,博士,教授,研究方向:電子偵察、通信抗干擾技術(shù)、聲信號處理、陣列信號處理。

TP301

10.3969/j.issn1672-9730.2015.07.025