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

張嘉韋 馮 浩 高 勇

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

?

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

張嘉韋 馮 浩 高 勇

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

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

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

Class Number TP301

1 引言

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

2 粒子濾波算法基本原理

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

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

首先建立狀態轉移模型,狀態方程如下:

Φk=ΩΦk-1+dk

(1)

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

(2)

式中

是L×L移位矩陣,L為串擾長度;Φ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}是信號參數集,uk是參數擾動。

(3)

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

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

(4)

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

(5)

以分離信號為BPSK調制的兩路信號構成的混合信號盲分離算法為例,實現過程中,采用兩倍采樣[9],對應的粒子濾波部分的Matlab程序偽代碼如下:

初始化;

構造根升余弦匹配濾波下的碼元波形gself;

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

fori=1:N

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

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

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

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

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

for ki = D:-1:0

構造式(5)中相減部分dify,該過程會調用多項式估值函數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(k-D)到y(k)的概率,為權值更新的分子、分母做準備;

end for

end for

權值更新;

end for

權值歸一化;

進行參數估計;

進行重采樣;

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

3 快速實現

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

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

初始化;

構造根升余弦匹配濾波下的碼元波形gself;

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

fori=1:N

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

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

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

for ki = D:-1:0

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

end for

構造a_dk3,a_dk3(:, :, ii) = a_dk2;

end for

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

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

for kj = D:-1:0

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

end for

構造b_dk3,b_dk3(:, :, jj) = b_dk2;

end for

構造式(5)中相減部分dify,該過程會調用多項式估值函數polyval:

dify_even= f1(a_dk3, b_dk3, gself)

dify_odd= f2(a_dk3, b_dk3, gself)

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

權值更新;

end for

權值歸一化;

進行參數估計;

進行重采樣;

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

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

4 實驗仿真及結果

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

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

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

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

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

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

5 結語

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

[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] 周尚波,何革,柳玉炯.一種改進的粒子濾波目標跟蹤算法[J].計算機應用研究,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] 劉凱.粒子濾波在單通道信號分離中的應用研究[D].合肥:中國科學技術大學,2007.

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

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

[10] 廖燦輝,黃淵凌,周世東.衛星成對載波多址信號的一種聯合分離解調算法[J].通信學報,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] 蔡權偉,魏平,肖先賜.基于模型擬合的重疊信號盲分離方法[J].電子學報,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日 作者簡介:張嘉韋,男,碩士研究生,研究方向:移動通信、混合信號處理。馮浩,男,碩士研究生,研究方向:移動通信。高勇,男,博士,教授,研究方向:電子偵察、通信抗干擾技術、聲信號處理、陣列信號處理。

TP301

10.3969/j.issn1672-9730.2015.07.025