適用於衛星導航信號擷取之新式相關器演算法與VLSI設計

Chia-Ming Chang; 張家銘

請用此 Handle URI 來引用此文件： http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41718

完整後設資料紀錄

DC 欄位	值	語言
dc.contributor.advisor	曹恆偉
dc.contributor.author	Chia-Ming Chang	en
dc.contributor.author	張家銘	zh_TW
dc.date.accessioned	2021-06-15T00:28:48Z	-
dc.date.issued	2009
dc.date.submitted	2009-01-20
dc.identifier.citation	[1] Elliott D. Kaplan and Christopher J. Hegarty, “Understanding GPS: Principles and Applications,” Artech House, second edition, 2006 [2] James Bao-Yen Tsui, “Fundamentals of Global Positioning System Receivers: A Software Approach,” Wiely Inter-Science, second edition, 2005 [3] Keshab K. Parhi “ VLSI Digital Signal Processing Systems: design and implementation,” Wiely Inter-Science, Chapter 15,1999 [4] “Galileo Navigation Signal In-Space Interference Control Document” http://www.galileoju.com [5] Michael S. Braasch and A. J. Van Dierendonck, “GPS Receiver Architectures and Measurements,” Proceedings of the IEEE Digital Object Identifier, Vol. 87, Issue 1, pp.48 – 64, Jan, 1999 [6] Holmes J.K., Dafesh P.A., “Practical and Theoretical Tradeoffs of Active Parallel Correlator and Passive Matched Filter Acquisition Implementations', in Proceedings of the IAIN World Congress and the 56th Annual Meeting of the Institute of Navigation, pp.26-28, June, 2000 [7] Wai C. Lee, Gary L. Slimak, Gary A. McGraw, and Beth Kaspar, “Fast, Low Energy GPS Navigation With Massively Parallel Correlator Array Technology,” in Proceedings of the 55th Annual Meeting of the Institute of Navigation, pp.443 - 450, June, 1999 [8] Nagaraj C.S., H.S. Jamadagni, Muralikrishna S, Vimala C., “Software-Aided Sequential Multi-Tap Correlator for Fast Acquisition,” in Proceedings of the 17th International Technical Meeting of the Satellite Division of the Institute of Navigation ION GNSS 2004, pp.1547 – 1554, Sept, 2004 [9] Ville Eerola, Samuli Pietila, and Harri Valio, “A Novel Flexible Correlator Architecture for GNSS Receivers,” in Proceedings of the 2007 National Technical Meeting of the Institute of Navigation, pp.681 - 691, Jan, 2007 [10] Lin, Y.-T., Tsai, P.-Y., and Chiueh, T.-D., “Low-power variable-length fast Fourier transform processor,” in IEE Proceedings of Computers and Digital Techniques, Vol.152, Issue 4, pp.499 - 506, July 2005 [11] Chawla, K.K. and Sarwate, D.V. , “Parallel acquisition of PN sequences in DS/SS systems,” in IEEE Transactions on Communications, Vol.42, Issue 5, pp. 2155-2164, May 1994 [12] Zhang Jun and Zhang Qishan, “An approach to realize the parallel real-time correlator based on parallel pipeline from addition network,” in IEEE Region 10 Conference on TENCON '93. Proceedings of Computer, Communication, Control and Power Engineering 1993, Vol.2, Issue 0, Part 20000, pp.849 – 852, Oct 1993 [13] Ledvina, B.M., Psiaki, M.L., Powell, S.P., and Kintner, P.M., “Bit-wise parallel algorithms for efficient software correlation applied to a GPS software receiver,” in IEEE Transactions on Wireless Communications, Vol.3, Issue 5, pp.1469 – 1473, Sept. 2004 [14] Seung Hyuk Ahn, Joon Tae Kim, and Yong Hoon Lee, “Efficient implementation of parallel correlators for code acquisition in DS CDMA systems,” in Proceedings of the 1999 IEEE International Symposium on Circuits and Systems 1999, Vol.4, pp.576-579, Jul 1999 [15] Sang Hyun Park, Il Heung Choi, Sang Jeong Lee, and Young Baek Kim, “A Novel GPS Initial Synchronization Scheme using Decomposed Differential Matched Filter,” in Proceedings of the 2002 National Technical Meeting of the Institute of Navigation, pp. 246 – 253, January 2002 [16] Ville Eerola, Samuli Pietila, and Harri Valio, “A Novel Flexible Correlator Architecture for_GNSS_Receivers” in Proceedings of the 2007 National Technical Meeting of the Institute of Navigation, pp. 681 – 691, January 2007 [17] Hartley, R.I., “Subexpression sharing in filters using canonic signed digit multipliers,” in IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, Vol.43, Issue 10, pp.677-688, Oct 1996 [18] Mahesh, R., Vinod, A.P., “A new algorithm for elimination of common subexpressions,” in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol.27, Issue 2, pp.217 – 229, Feb. 2008 [19] Chia-Yu Yao, Hsin-Horng Chen, Tsuan-Fan Lin, Chiang-Ju Chien, and Chun-Te Hsu, “A novel common-subexpression-elimination method for synthesizing fixed-point FIR filters,” in IEEE Transactions on Circuits and Systems I: Regular Papers, Vol.51, Issue 11, pp.2215- 2221, Nov. 2004 [20] Jongsun Park, Woopyo Jeong, Mahmoodi-Meimand, H., Yongtao Wang, Choo, H., and Roy, K., “Computation sharing programmable FIR filter for low-power and high-performance applications,” in IEEE Journal of Solid-State Circuits, Vol.39, Issue 2, pp.348- 357, Feb. 2004 [21] Fei Xu, Chip-Hong Chang, and Ching-Chuen Jong, “Contention resolution algorithm for common subexpression elimination in digital filter design,” in IEEE International Symposium on Circuits and Systems 2005, Vol.2, pp.1823 – 1826, May 2005 [22] Ming-Luen Lieu and Tzi-Dar Chiueh, “A low-power digital matched filter for direct-sequence spread-spectrum signal acquisition,” in IEEE Journal of Solid-State Circuits, Vol.36, Issue 6, pp.933 – 943, June 2001 [23] Peter C. Ould, and Robert J. VanWechel, “All-Digital GPS Reciver Mechanization,” IEEE Journal of the Institute of Navigation, Vol.28, No.3, pp.178-188, 1981 [24] Matthias Overbeck, Gernot Wistuba, Oihana. Otaegui, Sybille Haas, Bernhard Niemann, Frank Henkel, and Gunter Rohmer, “Highly Integrated GPS/EGNOS Receiver Chipset,” in Proc. of the 19th International Technical Meeting of the Satellite Division of the Institute of Navigation, pp. 251-258, 2006. [25] C. Bürgi, E. De Mey, A. Orzati, and A. Thiel, “Highly-Integrated Solution for Ultra-fast Acquisition and Precise Tracking of Weak GPS and Galileo L1 Signals,” in Proc. of the 19th International Technical Meeting of the Satellite Division of the Institute of Navigation, pp. 226-235, 2006 [26] Iinatti, J.H.J. “On the threshold setting principles in code acquisition of DS-SSsignals,” in IEEE Journal on Selected Areas in Communications, Vol.18, Issue: 1, pp.62 – 72, Jan. 2000 [27] W.-C. Lin, K.-C. Liu and C.-K. Wang,” Differential Matched Filter Architecture for Spread Spectrum Communication Systems,” Electronics Letters, Vol.32, No.17, pp.1539-1540, August 1996.
dc.identifier.uri	http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41718	-
dc.description.abstract	相關器（Correlation Architecture）為一種廣泛使用於各種通訊系統接收端上的裝置，尤其對於展頻系統信號擷取（Signal Acquisition）的模式中，相關器更是扮演著不可或缺的角色。而隨著全球導航衛星系統(Global Navigation Satellite Systems)的成熟發展，包括像是美國的GPS系統，歐盟的Galileo系統，乃至於俄國GLONASS系統，甚至日本，中國等國家都預計於未來數十年內發展出一套可提供多種服務的商用衛星裝置。因此，為了提供商用更快速的導航能力，信號擷取的初始定位時間（Time To First Fix）便成為各種接收裝置效能好壞的重要指標。而在決定信號擷取的初始定位時間中，相關器的設計佔有極為重要的影響能力。由信號擷取中相位搜尋的不同方式，以及相關器的種類，可歸納出現行三種常用的接收端信號擷取架構；分別為循序輸入相關器加上平行相位搜尋，匹配濾波器加上序列相位搜尋，及快速傅利葉轉換等方式。而其中，匹配濾波器加上平行相位搜尋的方式，雖然效能卓越，但是因為架構太複雜且成本太高，所以一般設計很少有人使用這種方法。本篇論文的目標就是在衛星導航的系統下，提出一套有效率的演算法設計流程，透過子運算簡化（subexpression elimination）的方式，設計出有效率的硬體結構，其優點為縮小晶片面積、提高硬體使用率、縮短初始定位時間和低功率的消耗等。另外，若運用在軟體接收機的應用上，演算法的彈性設計更可大幅縮減所要計算的加乘次數。在硬體實作上，透過標準單元的設計流程，利用0.18um的製程來實踐所提出的相關器架構。所實現的架構可支援同時搜索32種GPS L1 C/A碼（Coarse/Acquisition Code）信號，晶片面積約為1.86mm × 1.86mm。	zh_TW
dc.description.abstract	Correlation architectures are widely used in various communication systems’ receiver, especially for the spread spectrum system, and they play an indispensable role in signal acquisition. With the mature development of GNSS (Global Navigation Satellite Systems), such as the GPS of U.S., the Galileo system of European Union, as well as the GLONASS of Russian, and even Japan, China are developing their own commercial satellites system to offer wide range of services. Therefore, in order to provide faster commercial navigation ability, the TTFF (Time To First Fix) of signal acquisition becomes one important indicator to gauge the performance of various kinds of receivers. Among these receivers, the design of correlator has the most important influence on TTFF. From different code phase searching methods of signal acquisition, and different types of correlators, we can conclude three common signal acquisition receiver architectures: sequential-input correlator with parallel code phases search, matched-filter with serial code phase search and fast Fourier transform method. Among these methods, the hardware complexity and the cost are too high for matched-filter with parallel code phases search although its TTFF is shortest. Therefore, only few people adopt this method in practical design. For this reason, this thesis proposed one efficient algorithm design flow for navigation satellites systems. By using subexpression elimination method, we designed an efficient hardware architecture which has advantages of area reduction of die size, enhancement of hardware utilization, reduction of TTFF, and low power consumption, etc. In addition, for software receiver application, the flexible design of the algorithm can tremendously reduce the required number of addition and multiplication. In hardware implementation, the proposed correlator architecture is implemented in 0.18 um CMOS process. The proposed design can provide searching 32 GPS L1 C/A code signals simultaneously and the implemented die size is about 1.86mm × 1.86mm.	en
dc.description.provenance	Made available in DSpace on 2021-06-15T00:28:48Z (GMT). No. of bitstreams: 1 ntu-98-R94943088-1.pdf: 5790486 bytes, checksum: 4ce8ada45a5ce82c988a587c6412d965 (MD5) Previous issue date: 2009	en
dc.description.tableofcontents	致謝 …………………………………………………………..….…...…………..… VII 中文摘要 …………………………………………………………..……..………..… IX Abstract …………………………………………………………………...….……… XI Table of Contents ………………………………..……………………………….... XIII List of Figures …………………………………………………………………..… XVII List of Tables ………………………………………………………………………. XXI Chapter 1: Introduction ……………………………………………………………… 1 1.1 Overview of Global Navigation Satellites System …………………… 1 1.2 Research Topic, Motivation and Main Contributions ………………… 4 1.3 Thesis Organization …………………………………………………... 6 Chapter 2: Global Navigation Satellites System ………………………………..…... 9 2.1 Fundamentals of Satellite Navigation ………………………………… 9 2.2 Satellite Signal Characteristics ……………………………………… 11 2.3.1 Modulation Types …………………………………………… 11 2.3.2 Frequency Plan and Signal Design ………………………….. 13 2.3 Receiver Architectures ………………………………………………. 16 2.3.1 Antenna Consideration ……………………………………… 16 2.3.2 Amplifier Consideration …………………………………….. 17 2.3.3 ADC Consideration ………………………………………….. 17 2.3.4 Acquisition and Tracking Consideration ……………………. 18 2.4 Summary …………………………………………………………….. 19 Chapter 3: Acquisition Algorithms ………………………………………………… 23 3.1 State of the Art ………………………………………………………. 23 3.1.1 Sequential Input Correlator with Parallel Code Phase Search . 26 3.1.2 Matched-filter with Serial Code Phase Search ……………… 27 3.1.3 FFT …………………………………………………………... 29 3.1.4 Comparison of Conventional Correlation Architectures ……. 31 3.2 The Proposed Algorithm …………………………………………….. 34 3.2.1 Subexpression Elimination Concept ………………………… 35 3.2.2 Algorithm Flowchart ………………………………………… 37 3.2.3 Algorithm Applications and Simulation Results ……………. 44 3.3 Permutation Problems of the Proposed Algorithm ………………….. 49 3.3.1 Effect of Random Permutation of 32 PRN Codes …………... 49 3.3.2 Solution ……………………………………………………… 51 3.3.3 Estimation Formula for the Proposed Algorithm ……………. 56 3.4 Comparison of Different Algorithms ………………………………... 59 3.5 Summary …………………………………………………………….. 61 Chapter 4: Architecture Design for Correlation and Acquisition ………………... 65 4.1 The Proposed Correlation Scheme ………………………………….. 65 4.1.1 Postfiltering Technique ……………………………………… 65 4.1.2 Architecture Design for Correlation ………………………… 70 4.2 The Proposed Acquisition Scheme ………………………………….. 72 4.2.1 Architecture Design for Acquisition ………………………… 72 4.2.2 Simulation Results …………………………………………... 76 4.3 Fix-point Analysis …………………………………………………… 79 4.4 Summary …………………………………………………………….. 82 Chapter 5: Chip Implementation …………………………………………………... 83 5.1 Cell-based Design Flow ……………………………………………... 83 5.2 RTL Coding and Simulation ………………………………………… 84 5.3 Synthesis, DFT, ATPG and Gate-level Simulation ………………….. 86 5.4 Place and Route, DRC & LVS, and Post-layout Gate-level Simulation …………………………………………………………… 88 5.5 Comparison ………………………………………………………….. 91 5.6 Summary …………………………………………………………….. 92 Chapter 6: Conclusions ……………………………………………………………... 93 6.1 Conclusions and Main Contributions ……………………………….. 93 6.2 Future Works ………………………………………………………… 95 Abbreviations ………………………………………………………………………….. i References …………………………………………………………………….……… iii
dc.language.iso	en
dc.subject	信號擷取	zh_TW
dc.subject	全球衛星定位系統	zh_TW
dc.subject	平行	zh_TW
dc.subject	相位搜尋	zh_TW
dc.subject	子運算	zh_TW
dc.subject	相關器	zh_TW
dc.subject	acquisition	en
dc.subject	GPS	en
dc.subject	correlator	en
dc.subject	subexpression	en
dc.subject	parallel phase search	en
dc.title	適用於衛星導航信號擷取之新式相關器演算法與VLSI設計	zh_TW
dc.title	Novel Algorithm and VLSI Design of Correlation Architecture for GNSS Signal Acquisition	en
dc.type	Thesis
dc.date.schoolyear	97-1
dc.description.degree	碩士
dc.contributor.oralexamcommittee	張帆人,闕志達,陳坤佐
dc.subject.keyword	全球衛星定位系統,信號擷取,相關器,子運算,平行,相位搜尋,	zh_TW
dc.subject.keyword	GPS,acquisition,correlator,subexpression,parallel phase search,	en
dc.relation.page	96
dc.rights.note	有償授權
dc.date.accepted	2009-01-20
dc.contributor.author-college	電機資訊學院	zh_TW
dc.contributor.author-dept	電子工程學研究所	zh_TW
顯示於系所單位：	電子工程學研究所

文件中的檔案：

檔案	大小	格式
ntu-98-1.pdf 未授權公開取用	5.65 MB	Adobe PDF

顯示文件簡單紀錄

系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。