GPS同步算法的ASIP实现
|
摘要
信号同步算法集中了GPS软件接收机的主要运算量,其完成的主要功能是接收GPS中频输入信号,从中解扩解调出GPS卫星的导航电文用于后续的定位解算。同步算法主要包括捕获和跟踪二个阶段,捕获阶段通过三维搜索得到可见卫星号及其粗略的C/A码码偏和载波多普勒频偏;跟踪阶段通过修正频偏和码偏产生与接收信号同步的本地信号,从而将载波和C/A码从输入信号中剥离,得到最终的导航电文。二个阶段中的相关器是实现实时软件接收机的瓶颈。
作为ASIC和通用处理器之间的折中,专用指令集处理器(Application Specific Instruction Set Processor,ASIP)兼具了专用性和灵活性。本文研究了GPS信号同步算法,并根据其运算特性,基于Nios II嵌入式处理器实现了面向GPS同步算法的ASIP,同时把显式通信指令集结构的TRIPS作为另一ASIP的备选方案,基于其指令集对部分同步算法做了汇编优化。最后对二种方案的ASIP性能进行了分析和比较,探索了基于ASIP的GPS信号同步算法的嵌入式实时解决方案。
本文通过对捕获和跟踪算法的分析,确定了核心运算单元FFT/IFFT和Bit-Wise相关器为主要待优化单元,继而从二个单元中提取出了一组专用指令,进行了基于Nios II的指令扩展,从而完成了ASIP的Nios II实现,并对其做了板级验证。同时,为了在TRIPS上获得更好的性能,对FFT/IFFT和Bit-Wise相关器二个核心运算单元做了TRIPS汇编优化。最后提取二种ASIP的性能参数分别进行了分析,并使用归一化的频率对二者进行了比较。通过分析二种方案的ASIP性能参数,发现虽然基于Nios II的ASIP已经获得了相对较优的性能,但使用显式通信指令集的体系结构(TRIPS)在处理GPS信号同步算法时的优势更加明显。
As the main operation unit of GPS software receiver, signal synchronization arithmetic receives intermediate frequency input signal, and then obtains navigation data from it through dispreading and demodulation for following positioning unit. Signal synchronization arithmetic can be briefly divided into two phases, acquisition and tracking. Acquisition gains visible satellite number、cursory phase of the C/A code and cursory Doppler frequency shift of carrier by three-dimensional search; Tracking generates local signals which synchronized with input signals through adjusting the C/A code and Doppler frequency shift, so that C/A code and the carrier can be removed from input signals and the navigation data can be extracted. The correlators in the two phases are performance bottlenecks in implementing real-time GPS software receiver.
As a trade-off between ASIC and general-purpose processor, Application Specific Instruction Set Processor (ASIP) possesses both specificity and flexibility. Signal synchronization algorithm of GPS is studied in this paper. According to its characteristics, ASIP of GPS signal synchronization algorithm based on Nios II embedded processor is implemented. At the same time, TRIPS with Explicitly Communication ISA architecture is proposed as another option of ASIP, and part of the signal synchronization algorithm is optimized through implementing with TRIPS assembly language based on its instruction set. At last, two ASIPs proposed are evaluated and compared, which explores the embedded real-time solution of ASIP-based GPS signal synchronization algorithm.
Based on the analysis of acquisition and tracking algorithms, FFT/IFFT and Bit-Wise correlator are the key operation units of the GPS software receiver. This paper takes both of them as the main units to optimize, from which a set of specific instructions was extracted, and an exploration of Nios II-based instructions was made, then the ASIP is implemented in the Nios II IDE and verification was completed on a FPGA test-bed. Besides, TRIPS assembly optimization for FFT/IFFT and Bit-Wise correlator was made in order to achieve better performance. Finally, we extracted and analyzed performance parameters of the two realizations of ASIP, and compared them using normalized frequency. By analyzing performance parameters of the two ASIPs, we found that the ASIP based on Nios II had comparatively good performance, but TRIPS with Explicitly Communication ISA architecture put up better performance.
作为ASIC和通用处理器之间的折中,专用指令集处理器(Application Specific Instruction Set Processor,ASIP)兼具了专用性和灵活性。本文研究了GPS信号同步算法,并根据其运算特性,基于Nios II嵌入式处理器实现了面向GPS同步算法的ASIP,同时把显式通信指令集结构的TRIPS作为另一ASIP的备选方案,基于其指令集对部分同步算法做了汇编优化。最后对二种方案的ASIP性能进行了分析和比较,探索了基于ASIP的GPS信号同步算法的嵌入式实时解决方案。
本文通过对捕获和跟踪算法的分析,确定了核心运算单元FFT/IFFT和Bit-Wise相关器为主要待优化单元,继而从二个单元中提取出了一组专用指令,进行了基于Nios II的指令扩展,从而完成了ASIP的Nios II实现,并对其做了板级验证。同时,为了在TRIPS上获得更好的性能,对FFT/IFFT和Bit-Wise相关器二个核心运算单元做了TRIPS汇编优化。最后提取二种ASIP的性能参数分别进行了分析,并使用归一化的频率对二者进行了比较。通过分析二种方案的ASIP性能参数,发现虽然基于Nios II的ASIP已经获得了相对较优的性能,但使用显式通信指令集的体系结构(TRIPS)在处理GPS信号同步算法时的优势更加明显。
As the main operation unit of GPS software receiver, signal synchronization arithmetic receives intermediate frequency input signal, and then obtains navigation data from it through dispreading and demodulation for following positioning unit. Signal synchronization arithmetic can be briefly divided into two phases, acquisition and tracking. Acquisition gains visible satellite number、cursory phase of the C/A code and cursory Doppler frequency shift of carrier by three-dimensional search; Tracking generates local signals which synchronized with input signals through adjusting the C/A code and Doppler frequency shift, so that C/A code and the carrier can be removed from input signals and the navigation data can be extracted. The correlators in the two phases are performance bottlenecks in implementing real-time GPS software receiver.
As a trade-off between ASIC and general-purpose processor, Application Specific Instruction Set Processor (ASIP) possesses both specificity and flexibility. Signal synchronization algorithm of GPS is studied in this paper. According to its characteristics, ASIP of GPS signal synchronization algorithm based on Nios II embedded processor is implemented. At the same time, TRIPS with Explicitly Communication ISA architecture is proposed as another option of ASIP, and part of the signal synchronization algorithm is optimized through implementing with TRIPS assembly language based on its instruction set. At last, two ASIPs proposed are evaluated and compared, which explores the embedded real-time solution of ASIP-based GPS signal synchronization algorithm.
Based on the analysis of acquisition and tracking algorithms, FFT/IFFT and Bit-Wise correlator are the key operation units of the GPS software receiver. This paper takes both of them as the main units to optimize, from which a set of specific instructions was extracted, and an exploration of Nios II-based instructions was made, then the ASIP is implemented in the Nios II IDE and verification was completed on a FPGA test-bed. Besides, TRIPS assembly optimization for FFT/IFFT and Bit-Wise correlator was made in order to achieve better performance. Finally, we extracted and analyzed performance parameters of the two realizations of ASIP, and compared them using normalized frequency. By analyzing performance parameters of the two ASIPs, we found that the ASIP based on Nios II had comparatively good performance, but TRIPS with Explicitly Communication ISA architecture put up better performance.
引文
1 W. Zhuang, J. Tranquilla. Digital Baseband Processor for the GPS Receiver. IEEE Tran, AES. 1993, 29(4):1343-1348
2 D. Akos. A Software Radio Approach to Global Navigation Satellite System Receiver Design. Ph.D. Dissertation, Ohio University. 1997:3-5
3刘钝,曹冲. GPS软件接收机的发展前景.全球定位系统, 2003, (3):23-27
4 J. B. Tsui. Fundamentals of Global Positioning System Receivers: A Software Approach. New York: Wiley, 2000:133-164
5 E. D. Kaplan. Understanding GPS Principles and Applications. 2nd. Boston: Artech House, 1996:75-132
6 Jr J J. Spilker. GPS Signal Structure and Performance Characteristics. Navigation, 1978, 25(2):121-146
7郑君里,应启珩,杨为理.信号与系统.第二版.北京:高等教育出版社, 2000:123-132
8 C. -Y. Lee, F.V.M. Catthoor, H.J. deMan. An Efficient ASIC Architecture for Real-time Edge Detection. Circuits and Systems , IEEE Transactions. 1989:1350-1359
9 K. Compton, S. Hauck. Automatic Design of Area-Efficient Configurable ASIC Cores. IEEE Transactions on Computers. 2007, 56(5): 662-672
10 J.–G. Cousin, M. Denoual, D. Saille, O. Sentieys. Fast ASIP Synthesis and Power Estimation for DSP Application. Signal Processing Systems, Lafayette. 2000: 591-600
11 V. Kalyanaraman, M. Mueller, S. Simon, et al. Power Reduction of ASIPs by Distributing the Workload on Several ASIP-instances. European Conference on Circuit Theory and Design. 2005:457-460
12 K. Kucukcakar. An ASIP Design Methodology of Embedded Systems. Hardware/Software Co-design, Rome. 1999: 17-21
13 M. K. Jain, M. Balakrishnan, A. Kumar. ASIP Design Methodologies: Survey and Issues. ICVD, Bangalore. 2001:76-81
14 K. Kucukcakkar. An ASIP Design Methodology for Embedded Systems. Hardware/Software Codesign. Rome. 1999: 17-21
15 Http://www.tensilica.com
16 R. E. Gonzalez. Xtensa: A Configurable and Extensible Processor. IEEE Micro. 2000, 20(2): 60-70
17 T. Glokler, H. Meyr. Design of Energy-Efficient Application-Specific Instruction Set Processors. Kluwer Academic Publishers, 2004:40-50
18 P. Paulin. What is the Next EDA Driver. Proceedings of the 39th Conference on Design Automation. New York, ACM Press, 2002:652-652
19 T. Vogt, N. Wehn. A Reconfigurable ASIP for Convolutional and Turbo Decoding in an SDR Environment. Very Large Scale Integration Systems, IEEE Transactions on. 2008, 16(10):1309-1320
20 Zhaohui Liu, K. Dickson, J. V. McCanny. Application-Specific Instruction Set Processor for SoC Implementation of Modern Signal Processing Algorithms. Transactions on Circuits and Systems. 2005, 52(4):755-765
21 A. Ferrante, G. Piscopo, S. Scaldaferri. Application Driven Optimization of VLIW Architectures: A Hardware-Software Approach. In Proceedings of Real Time and Embedded Technology and Applications Symposium, San Francisco, 2005: 128-137.
22 K. Keutzer, S. Malik, A. R. Newton. From ASIC to ASIP: The Next Design Discontinuity. Proceedings of the 2002 IEEE International Conference on Computer Design, Washington, 2002: 84-90
23 S. Swanson, A. Putnam, M. Mercaldi, et al. Area-Performance Trade-Offs in Tiled Dataflow Architectures. 33rd International Symposium on Computer Architecture, Boston, 2006:314-326
24 S. Tingting, M. M. K. Martin, A. Roth. Scalable Store-Load Forwarding Via Store Queue Index Prediction. 38th Annual IEEE/ACM International Symposium on Micro-Architecture, Barcelona, 2005:12
25 J. Diamond, B. Robatmili, et al. High Performance Dense Linear Algebra on A Spatially Distributed Pocessor. ACM, Salt Lack City, 2008:4-8
26杨君.专用指令集处理器(ASIP)体系结构设计研究.中国科学技术大学博士学位论文. 2006:2-3
27 P. Rinder, N. Bertelsen. Design of a Single Frequency GPS Software Receiver. Master thesis of Aalborg University. 2004:25-95
28周三文,黄龙,卢满宏. FFT在高动态扩频信号捕获中的应用.飞行器测控学报. 2005, 24(2):61-64
29王明明. GPS软件接收机基带算法研究.山东大学硕士学位论文. 2006:25-29
30 Falin Wu, Kefei Zhang, A. Yasuda. GPS Signal Acquisition and Tracking Using Software GPS Receiver. Proceedings of the Eighth International Symposium on Signal Processing and Its Applications, Sydney, Australia, 2005. New Jersey, Piscataway, 2005:843-846
31 B. M. Ledvina, M. L. Psiaki, S. P. Powell et al. A 12-channel Real-time GPS L1 Software Receiver. Proc. Institute of Navigation Nat. Technical Meeting, Anaheim, CA, Jan. 22-24, 2003:767-782
32 N. Bertelsen, K. Borre, P. Rinder. The GPS Code Software Receiver at Aalborg University. Proceeding of Navitech 2004, Noordwijk, Netherlands, 2004:373-380
33 B. M. Ledvina, M. L. Psiaki, S. P. Powell et al. Bit-Wise Parallel Algorithms for Ef?cient Software Correlation Applied to A GPS Software Receiver. IEEE Transactions on Wireless Communications. 2004, 3(5):1469-1473
34 M. L. Psiaki. Real-Time Generation of Bit-Wise Parallel Representations of Over-Sampled PRN Codes. IEEE Transactions on Wireless Communications. 2006, 5(3): 487-491
35 A. Tilak, C. Siddhartha. Computer Architecture: Challenges and Opportunities for the Next Decade. IEEE Micro. 2005, 25(3): 58-69
36 M. Hill, M. R. Marty. Amdahl's Law in the Multi-core Era, IEEE Computer. 2008, 41(7):33-38
37 S. Karthikeyan, N. Ramadass, L. Haiming, et al. Exploiting Ilp, Tlp, and Dlp with the Polymorphous Trips Architecture. Computer Architecture 30th Annual International Symposium on. San Diego, California. 2003:46-48
38 K. Sankaralingam, R. Nagarajan, R. McDonald, et al. Distributed Micro-architectural Protocols in the Trips Prototype Processor. 39th Annual IEEE/ACM International Symposium on. 2006:480-491
39 A. Smith, J. Gibson, B. Maher, N. Nethercote, B. Yoder, D. Burger, K. S. McKinley, and J. Burrill. Compiling for EDGE Architectures. In International Symposium on Code Generation and Optimization. 2006:185-195
40 S. Samantika, G. H. Loh. Store Vectors for Scalable Memory DependencePrediction and Scheduling. High-Performance Computer Architecture 12th International Symposium on. 2006:65-76
41 A. Gandhi, H. Akkary, R. Rajwar, et al. Scalable Load and Store Processing in Latency Tolerant Processors. Computer Architecture Proceedings. 32nd International Symposium on. 2005:446-457
42 B. Robatmili, K. E. Coons, D. Burger, and K. S. McKinley. Strategies for Mapping Data Flow Blocks to Distributed Hardware. In International Symposium on Micro-architecture, 2008:23-34
43 The University of Texas at Austin. TRIPS Processor Reference Manual. 2005
44李文龙,刘利,汤志忠.软件流水中的循环展开.北京航空航天大学学报. 2004, 30(11): 1112-1113
45李娟,张宇.采用Nios定制指令的嵌入式系统优化设计.单片机与嵌入式系统应用. 2004, (4):1-2
46李莹,艾明晶.基于Nios II的自动指纹识别系统设计.单片机与嵌入式系统应用. 2005, (6):49-51
47 Http://www.altera.com
2 D. Akos. A Software Radio Approach to Global Navigation Satellite System Receiver Design. Ph.D. Dissertation, Ohio University. 1997:3-5
3刘钝,曹冲. GPS软件接收机的发展前景.全球定位系统, 2003, (3):23-27
4 J. B. Tsui. Fundamentals of Global Positioning System Receivers: A Software Approach. New York: Wiley, 2000:133-164
5 E. D. Kaplan. Understanding GPS Principles and Applications. 2nd. Boston: Artech House, 1996:75-132
6 Jr J J. Spilker. GPS Signal Structure and Performance Characteristics. Navigation, 1978, 25(2):121-146
7郑君里,应启珩,杨为理.信号与系统.第二版.北京:高等教育出版社, 2000:123-132
8 C. -Y. Lee, F.V.M. Catthoor, H.J. deMan. An Efficient ASIC Architecture for Real-time Edge Detection. Circuits and Systems , IEEE Transactions. 1989:1350-1359
9 K. Compton, S. Hauck. Automatic Design of Area-Efficient Configurable ASIC Cores. IEEE Transactions on Computers. 2007, 56(5): 662-672
10 J.–G. Cousin, M. Denoual, D. Saille, O. Sentieys. Fast ASIP Synthesis and Power Estimation for DSP Application. Signal Processing Systems, Lafayette. 2000: 591-600
11 V. Kalyanaraman, M. Mueller, S. Simon, et al. Power Reduction of ASIPs by Distributing the Workload on Several ASIP-instances. European Conference on Circuit Theory and Design. 2005:457-460
12 K. Kucukcakar. An ASIP Design Methodology of Embedded Systems. Hardware/Software Co-design, Rome. 1999: 17-21
13 M. K. Jain, M. Balakrishnan, A. Kumar. ASIP Design Methodologies: Survey and Issues. ICVD, Bangalore. 2001:76-81
14 K. Kucukcakkar. An ASIP Design Methodology for Embedded Systems. Hardware/Software Codesign. Rome. 1999: 17-21
15 Http://www.tensilica.com
16 R. E. Gonzalez. Xtensa: A Configurable and Extensible Processor. IEEE Micro. 2000, 20(2): 60-70
17 T. Glokler, H. Meyr. Design of Energy-Efficient Application-Specific Instruction Set Processors. Kluwer Academic Publishers, 2004:40-50
18 P. Paulin. What is the Next EDA Driver. Proceedings of the 39th Conference on Design Automation. New York, ACM Press, 2002:652-652
19 T. Vogt, N. Wehn. A Reconfigurable ASIP for Convolutional and Turbo Decoding in an SDR Environment. Very Large Scale Integration Systems, IEEE Transactions on. 2008, 16(10):1309-1320
20 Zhaohui Liu, K. Dickson, J. V. McCanny. Application-Specific Instruction Set Processor for SoC Implementation of Modern Signal Processing Algorithms. Transactions on Circuits and Systems. 2005, 52(4):755-765
21 A. Ferrante, G. Piscopo, S. Scaldaferri. Application Driven Optimization of VLIW Architectures: A Hardware-Software Approach. In Proceedings of Real Time and Embedded Technology and Applications Symposium, San Francisco, 2005: 128-137.
22 K. Keutzer, S. Malik, A. R. Newton. From ASIC to ASIP: The Next Design Discontinuity. Proceedings of the 2002 IEEE International Conference on Computer Design, Washington, 2002: 84-90
23 S. Swanson, A. Putnam, M. Mercaldi, et al. Area-Performance Trade-Offs in Tiled Dataflow Architectures. 33rd International Symposium on Computer Architecture, Boston, 2006:314-326
24 S. Tingting, M. M. K. Martin, A. Roth. Scalable Store-Load Forwarding Via Store Queue Index Prediction. 38th Annual IEEE/ACM International Symposium on Micro-Architecture, Barcelona, 2005:12
25 J. Diamond, B. Robatmili, et al. High Performance Dense Linear Algebra on A Spatially Distributed Pocessor. ACM, Salt Lack City, 2008:4-8
26杨君.专用指令集处理器(ASIP)体系结构设计研究.中国科学技术大学博士学位论文. 2006:2-3
27 P. Rinder, N. Bertelsen. Design of a Single Frequency GPS Software Receiver. Master thesis of Aalborg University. 2004:25-95
28周三文,黄龙,卢满宏. FFT在高动态扩频信号捕获中的应用.飞行器测控学报. 2005, 24(2):61-64
29王明明. GPS软件接收机基带算法研究.山东大学硕士学位论文. 2006:25-29
30 Falin Wu, Kefei Zhang, A. Yasuda. GPS Signal Acquisition and Tracking Using Software GPS Receiver. Proceedings of the Eighth International Symposium on Signal Processing and Its Applications, Sydney, Australia, 2005. New Jersey, Piscataway, 2005:843-846
31 B. M. Ledvina, M. L. Psiaki, S. P. Powell et al. A 12-channel Real-time GPS L1 Software Receiver. Proc. Institute of Navigation Nat. Technical Meeting, Anaheim, CA, Jan. 22-24, 2003:767-782
32 N. Bertelsen, K. Borre, P. Rinder. The GPS Code Software Receiver at Aalborg University. Proceeding of Navitech 2004, Noordwijk, Netherlands, 2004:373-380
33 B. M. Ledvina, M. L. Psiaki, S. P. Powell et al. Bit-Wise Parallel Algorithms for Ef?cient Software Correlation Applied to A GPS Software Receiver. IEEE Transactions on Wireless Communications. 2004, 3(5):1469-1473
34 M. L. Psiaki. Real-Time Generation of Bit-Wise Parallel Representations of Over-Sampled PRN Codes. IEEE Transactions on Wireless Communications. 2006, 5(3): 487-491
35 A. Tilak, C. Siddhartha. Computer Architecture: Challenges and Opportunities for the Next Decade. IEEE Micro. 2005, 25(3): 58-69
36 M. Hill, M. R. Marty. Amdahl's Law in the Multi-core Era, IEEE Computer. 2008, 41(7):33-38
37 S. Karthikeyan, N. Ramadass, L. Haiming, et al. Exploiting Ilp, Tlp, and Dlp with the Polymorphous Trips Architecture. Computer Architecture 30th Annual International Symposium on. San Diego, California. 2003:46-48
38 K. Sankaralingam, R. Nagarajan, R. McDonald, et al. Distributed Micro-architectural Protocols in the Trips Prototype Processor. 39th Annual IEEE/ACM International Symposium on. 2006:480-491
39 A. Smith, J. Gibson, B. Maher, N. Nethercote, B. Yoder, D. Burger, K. S. McKinley, and J. Burrill. Compiling for EDGE Architectures. In International Symposium on Code Generation and Optimization. 2006:185-195
40 S. Samantika, G. H. Loh. Store Vectors for Scalable Memory DependencePrediction and Scheduling. High-Performance Computer Architecture 12th International Symposium on. 2006:65-76
41 A. Gandhi, H. Akkary, R. Rajwar, et al. Scalable Load and Store Processing in Latency Tolerant Processors. Computer Architecture Proceedings. 32nd International Symposium on. 2005:446-457
42 B. Robatmili, K. E. Coons, D. Burger, and K. S. McKinley. Strategies for Mapping Data Flow Blocks to Distributed Hardware. In International Symposium on Micro-architecture, 2008:23-34
43 The University of Texas at Austin. TRIPS Processor Reference Manual. 2005
44李文龙,刘利,汤志忠.软件流水中的循环展开.北京航空航天大学学报. 2004, 30(11): 1112-1113
45李娟,张宇.采用Nios定制指令的嵌入式系统优化设计.单片机与嵌入式系统应用. 2004, (4):1-2
46李莹,艾明晶.基于Nios II的自动指纹识别系统设计.单片机与嵌入式系统应用. 2005, (6):49-51
47 Http://www.altera.com