王奉帥,劉聰鋒

(1.中國(guó)電子科技集團(tuán)公司第五十四研究所，河北 石家莊050081；2.西安電子科技大學(xué)，陜西 西安710071)

0 引言

全球定位系統(tǒng)具有全天候、全球性、實(shí)時(shí)連續(xù)性和高精度等特點(diǎn)，因此受到了廣泛的應(yīng)用，例如飛機(jī)導(dǎo)航、導(dǎo)彈制導(dǎo)、地球變形監(jiān)測(cè)、汽車(chē)防盜跟蹤和手機(jī)定位等等。

傳統(tǒng)的衛(wèi)星導(dǎo)航定位解算采用的是最小二乘算法，對(duì)觀測(cè)矩陣進(jìn)行求逆來(lái)獲取未知向量，其中求逆過(guò)程包含了大量復(fù)雜的乘除運(yùn)算,增加了系統(tǒng)功耗。坐標(biāo)旋轉(zhuǎn)數(shù)字計(jì)算方法 (Coordinate Rotation Digital Computer,CORDIC)的應(yīng)用越來(lái)越廣泛，該算法能夠減少硬件對(duì)時(shí)間和空間資源的需求。MR Mosavi等人結(jié)合偽距和載波相位，利用傳統(tǒng)最小二乘確定接收機(jī)坐標(biāo)，定位精度有所提升[1]。Yuheng He等人處理定位解算時(shí)，每次旋轉(zhuǎn)選擇合適的CORDIC角度，可以簡(jiǎn)化最小二乘運(yùn)算[2]。N.Rahemi等人根據(jù)偽距方差對(duì)觀測(cè)矩陣加權(quán)，再用最小二乘求解，可以提高定位精度[3]。李春華等人提出了一種基于互差中值理論的加權(quán)最小二乘算法,該算法的定位精度較最小二乘算法和直接解算方法的定位精度有較大提高,并能有效地減少問(wèn)題衛(wèi)星的影響[4]。徐飛采用了CORDIC算法對(duì)旋轉(zhuǎn)矩陣中的三角函數(shù)計(jì)算,實(shí)現(xiàn)了硬件加速[5]。

本文給出了基于CORDIC算法實(shí)現(xiàn)近似正交三角(Orthogonal-Triangular，QR)分解[6-9]的迭代最小二乘算法(以下簡(jiǎn)稱(chēng)迭代最小二乘算法)，利用該算法進(jìn)行定位解算，沒(méi)有損失定位精度，而且運(yùn)行穩(wěn)定可靠。

1 GPS定位原理

最小二乘算法是導(dǎo)航設(shè)備最常用到的定位解算算法，該算法根據(jù)4顆或更多衛(wèi)星的偽距解算出接收機(jī)位置[10]。衛(wèi)星觀測(cè)偽距及星地幾何距離如圖1所示。

圖1 衛(wèi)星觀測(cè)偽距及星地幾何距離

接收機(jī)接收到衛(wèi)星k的偽距ρ(k)，具有下述表達(dá)式：

ρ(k)=r(k)+c(dt-dt(k))+T(k)+I(k)+ε(k)，
k=1,2,...,n。

(1)

r(k)表示衛(wèi)星k到接收機(jī)的幾何距離：

(2)

式(1)中包含了4個(gè)未知數(shù)x，y，z和dt，其他參數(shù)均能通過(guò)先驗(yàn)信息獲得。顯然該方程是非線性的，對(duì)r(k)在(x0,y0,z0)處展開(kāi)泰勒級(jí)數(shù)，舍棄二階及更高階項(xiàng)可以得到：

(3)

將式(1)在(x0,y0,z0,dt0)處展開(kāi)泰勒級(jí)數(shù),并舍棄二階及更高階項(xiàng)可以得到

Ax=b，

(4)

其中，

其中，

未知向量x是Ax=b的最小二乘解

minx‖Ax-b‖2。

(5)

可以得出x=(ATA)-1b，為了求出未知向量，需要對(duì)矩陣ATA求逆，這其中包含了復(fù)雜的運(yùn)算，QR分解將矩陣ATA分解為Q和R矩陣，其中Q為正交矩陣，R為上三角矩陣。

2 基于CORDIC的近似QR分解算法

如果將式(4)左乘矩陣AT,可以得到

ΑTΑx=ΑTb;

(6)

若矩陣ATA能夠進(jìn)行QR分解，即

ΑTΑ=QR;

(7)

將式(7)兩端左乘矩陣QT可得

QTΑTΑ=R;

(8)

因此式(6)兩端左乘矩陣QT可以表示為

Rx=QTΑTb。

(9)

利用Givens變換可以實(shí)現(xiàn)矩陣A的QR分解，而Givens變換又可以利用CORDIC近似旋轉(zhuǎn)算法實(shí)現(xiàn)。Volder 提出的CORDIC方法以其運(yùn)算及硬件結(jié)構(gòu)簡(jiǎn)單和多能性而倍受關(guān)注，并已廣泛應(yīng)用于信號(hào)處理領(lǐng)域[11-15]。典型的Givens變換矩陣為:

G為n×n的矩陣，令x=[x1…xi…xj…xn]T，向量x左乘矩陣G，表示將x的xi，xj旋轉(zhuǎn)角度φ，轉(zhuǎn)換完的向量為y=[y1…yi…yj…yn]T,可以得到

(10)

其他元素保持不變,選擇合適的角度φ可以使yj=0。同樣選擇合適的G，可以將矩陣A轉(zhuǎn)換成上三角矩陣。為了方便計(jì)算機(jī)計(jì)算，可以令 tanφ=2-k，k為整數(shù)。利用CORDIC算法近似實(shí)現(xiàn)矩陣的QR分解就是通過(guò)迭代不同的旋轉(zhuǎn)角度，每次迭代旋轉(zhuǎn)的角度為2的整數(shù)冪，最終可將yj轉(zhuǎn)換為0。CORDIC 算法的收斂性滿(mǎn)足收斂定理,其中第k次迭代為[16]：

(11)

(12)

變換過(guò)程如圖2所示。

圖2 基于CORDIC近似旋轉(zhuǎn)算法的Givens變換示意

通過(guò)一系列變換，式(6)最終可以變成：

(13)

最終可以求解出未知向量

(14)

3 實(shí)驗(yàn)結(jié)果與分析

將接收機(jī)天線放置在基準(zhǔn)點(diǎn)上收取GPS信號(hào),接收到的可見(jiàn)衛(wèi)星為7顆，分別將接收到的衛(wèi)星偽距和電文存儲(chǔ)下來(lái)，利用Matlab軟件處理存儲(chǔ)的數(shù)據(jù)。

對(duì)存儲(chǔ)數(shù)據(jù)分別用求逆最小二乘算法和基于CORDIC近似QR分解的迭代最小二乘算法進(jìn)行定位解算。在利用CORDIC近似QR分解的最小二乘算法時(shí),迭代次數(shù)大于7得到的定位精度與求逆最小二乘算法基本一致。圖3和圖4給出了CORDIC近似旋轉(zhuǎn)最小二乘算法在迭代次數(shù)為6和7時(shí)的定位精度與求逆最小二乘算法的定位精度對(duì)比，其中迭代初始點(diǎn)都為坐標(biāo)原點(diǎn)?？梢钥闯鲈诘螖?shù)為7時(shí)，基于CORDIC近似旋轉(zhuǎn)最小二乘算法定位精度很接近。迭代次數(shù)為6時(shí)，基于CORDIC近似旋轉(zhuǎn)最小二乘算法定位精度雖然也很高，但沒(méi)有特別穩(wěn)定。

圖3 垂直定位誤差絕對(duì)值

圖4 水平定位誤差絕對(duì)值

在單次定位解算中，最小二乘求逆算法和迭代最小二乘算法的運(yùn)算量是不一樣的，如果矩陣求逆采用常用的初等變換方法實(shí)現(xiàn)，迭代最小二乘算法采用本文給出的方法，可以得到每種算法的運(yùn)算量，具體如表1所示。根據(jù)計(jì)算機(jī)原理可知，計(jì)算機(jī)操作的運(yùn)算復(fù)雜度排序?yàn)椋阂莆贿\(yùn)算<加法運(yùn)算<乘法運(yùn)算<除法運(yùn)算。

表1 不同算法運(yùn)算量對(duì)比

運(yùn)算初等變換求逆迭代QR分解(itg=6)迭代QR分解(itg=7)移位運(yùn)算(次數(shù))加運(yùn)算(次數(shù))乘運(yùn)算(次數(shù))除運(yùn)算(次數(shù))0969616727864849064

4 結(jié)束語(yǔ)

利用迭代最小二乘算法進(jìn)行定位解算時(shí)，迭代次數(shù)越多，達(dá)到的精度越高，同時(shí)運(yùn)算量也會(huì)相應(yīng)增加。但在不影響定位精度的前提下，迭代最小二乘算法的運(yùn)算量不管是在數(shù)量還是復(fù)雜度上都要優(yōu)于傳統(tǒng)最小二乘算法，從而有效地提高了數(shù)據(jù)處理器的運(yùn)算效率。另外，利用CORDIC算法對(duì)觀測(cè)矩陣進(jìn)行QR分解代替求逆運(yùn)算，能夠減少大量運(yùn)算，這對(duì)載波相位差分以及定向解算也具有很大的參考意義。

[1] Mosavi M R,Azarshahi S,Emamgholipour I,et al.Least Squares Techniques for GPS Receivers Positioning Filter using Pseudo-Range and Carrier Phase Measurements[J].Iranian Journal of Electrical & Electronic Engineering,2014,10(1):18-26.

[2] He Yuheng,Martin R,Bilgic A M.Approximate Iterative Least Squares Algorithms for GPS Positioning[C]∥ IEEE International Symposium on Signal Processing and Information Technology，2011:231-236.

[3] Rahemi N,Mosavi M R,Abedi A A,et al.Accurate Solution of Navigation Equations in GPS Receivers for Very High Velocities Using Pseudorange Measurements[J].Advances in Aerospace Engineering,2014(2):1-8.

[4] 李春華,蔡成林,梁愈高,等.一種高精度的北斗偽距單點(diǎn)定位加權(quán)算法[J].測(cè)繪科學(xué),2015,40(9):33-38.

[5] 徐飛,肖鐵軍,華純,等.基于FPGA的視頻圖像旋轉(zhuǎn)硬件加速器的設(shè)計(jì)與實(shí)現(xiàn)[J].傳感器與微系統(tǒng),2010,29(10):100-102.

[6] Meher P K,Sang Y P.CORDIC Designs for Fixed Angle of Rotation[J].IEEE Transactions on Very Large Scale Integration Systems,2013,21(2):217-228.

[8] 張朝柱,韓吉南,燕慧智.高速高精度固定角度旋轉(zhuǎn)CORDIC算法的設(shè)計(jì)與實(shí)現(xiàn)[J].電子學(xué)報(bào),2016,44(2):485-490.

[9] Ramadoss R,Kermani M M,Azarderakhsh R.Reliable Hardware Architectures of the CORDIC Algorithm With a Fixed Angle of Rotations[J].IEEE Transactions on Circuits and Systems II:Express Briefs,2017,64(8):972-976.

[10] He Y,Bilgic A.Iterative Least Squares Method for Global Positioning System[J].Advances in Radio Science,2011,9(1):203-208.

[11] Biswas D,Maharatna K.A CORDIC-Based Low-Power Statistical Feature Computation Engine for WSN Applications[J].Circuits Systems & Signal Processing,2015,34(12):4011-4028.

[12] Torres V,Valls J,Canet M J.Optimised CORDIC-based Atan2 Computation for FPGA Implementations[J].Electronics Letters,2017,53(19):1296-1298.

[13] Aggarwal S,Meher P K,Khare K.Concept,Design,and Implementation of Reconfigurable CORDIC[J].IEEE Transactions on Very Large Scale Integration Systems,2016,24(4):1588-1592.

[14] Chen Jiyang,Lei Yuanwu,Peng Yuanxi,et al.Configurable Floating-Point FFT Accelerator on FPGA Based Multiple-Rotation CORDIC[J].Chinese Journal of Electronics,2016,25(6):1063-1070.

[15] Heidarpour M,Ahmadi A,Rashidzadeh R.A CORDIC Based Digital Hardware For Adaptive Exponential Integrate and Fire Neuron[J].IEEE Transactions on Circuits & Systems.Part I:Regular Papers,2016,63(11):1986-1996.

[16] Nawandar N K,Garg B,Sharma G K.RICO:A Low Power Repetitive Iteration CORDIC for DSP Applications in Portable Devices[J].Journal of Systems Architecture,2016,70:82-92.

[17] 史方顯,曾立,陳昱,等.改進(jìn)型高速高精度CORDIC算法及其在DDFS中的應(yīng)用[J].電子學(xué)報(bào),2017,45(2):446-451.