應用於即時定位追蹤之低複雜度濾波演算法與晶片設計

Low-Complexity Filtering Algorithm and Chip Design for Real-Time Location Tracking

陳威廷(Wei-Ting Chen)

指導教授 ： 陳世綸 ； 邱奕世

中原大學/電機資訊學院/電子工程研究所/碩士(2020年)

https://doi.org/10.6840/cycu202000390

摘要

本論文提出一種應用於即時定位追蹤低複雜度的濾波演算法，並實現晶片設計。為了達到低複雜度和即時的需求，因此提出了以卡爾曼濾波器(Kalman Filter, KF)為基礎設計出來的低複雜的即時定位追蹤演算法，卡爾曼濾波器本身具有追蹤、預測等功能，可以將定位修正為更精準的結果。但在卡爾曼濾波器演算法的計算過程中，每次的迭代往往需要進行卡爾曼增益(Kalman Gain, KG)繁瑣且複雜的計算，不管是對於軟體或是硬體都十分的佔用資源，因此我們利用alpha-beta (α-β)濾波演算法中卡爾曼增益在經過數次迭代(iteration)後會逐漸平衡的這項特性，提出了一種以低成本、高效率為基礎設計的降低複雜度的濾波演算法，此演算法利用依據環境變異而決定使用DKF (Difference Kalman Filter)或PKF (Percentage Kalman Filter) ，DKF和PKF即是根據不同條件判斷而產生的演算法，不僅僅能夠大幅降低運算時間和複雜度，也能將原本演算法的電路面積進行大幅縮減。此演算法有大量矩陣運算，在硬體計算過程中，將矩陣拆解後進行晶片設計，係數皆使用2的倍數來進行運算，即可使用移位器取代乘法器和除法器，大幅的降低複雜度和電路面積，且同時處理浮點數(floating-point number)問題，並實現在現場可程式設計閘陣列(field programmable gate array, FPGA)上進行電路功能驗證後，最後進行晶片下線(tape-out)。本論文所提出演算法使用台灣半導體研究中心(Taiwan Semiconductor Research Institute, TSRI)所提供的TSMC 0.18μm CMOS元件庫，於SYNOPSYS的Design Vision中使用電子設計自動化(Electronic design automation, EDA)來實現超大型積體電路設計(very large scale integration circuit, VLSI )，電路運作頻率83.33MHz、邏輯閘數(gate count) 22.84k和功率消耗為3.86mW，晶片面積為582.63 μm × 580.23 μm。

關鍵字

百分比卡爾曼濾波器 ； 差值卡爾曼濾波器 ； α-β卡爾曼濾波器 ； 晶片設計 ； 卡爾曼濾波器 ； 位置追蹤

並列摘要

This thesis puts forward a low-complexity filtering algorithm, to achieve low-complexity filtering chip design for real-time location tracking. In order to meet the need for low-complexity and real-time, the positioning tracking algorithm based on Kalman Filter (KF) is proposed. The KF itself has the functions of tracking, predicting, etc., which can correct the positioning into more accurate results. However, in the calculation of KF algorithms, each iteration often requires tedious and complex calculations of Kalman Gain (KG). Both software and hardware are very resource-intensive. Therefore, use the feature of KG in alpha-beta (α-β) filtering algorithm which can gradually balance in each iteration. Proposed a filtering algorithm that based on low-complexity, low cost and high efficiency. This algorithm uses DKF (Difference Kalman Filter) and PKF (Percentage Kalman Filter) depending on different environments. In other words, DKF and PKF are the algorithm which is generated based on different judging conditions. This algorithm can not only significantly reduce the time and the complexity of computing, but also greatly shorten the circuit area of the original algorithm. This algorithm has a large number of matrix operation. In the hardware calculation process, it solves matrix problems about hardware and then developed chip design. Coefficients are used by a multiple of 2 for operation. Use shifters instead of multipliers and dividers, significantly reduce complexity and circuit area. At the same time, deal with the problem of floating-point number, achieve circuit function verification on the FPGA, and finally tape-out. The design uses the TSMC 0.18μm CMOS cell library provided by the TSRI, and uses EDA to implement the VLSI with Design Vision of SYNOPSYS, the operating frequency of the circuit is 83.33MHz, the value of gate counts is 22.84K, and the power consumption is 3.86mW, and chip area is 582.63 μm × 580.23 μm.

並列關鍵字

PKF ； DKF ； Alpha-Beta (α-β) filter ； chip design ； Kalman filter ； location tracking.

參考文獻

[1] K. Jung, P. B. V. Bermudez, H. Hwang, and Y. Oh; J. Kwak, “Passenger's location estimation using Kalman filter for Beacon fare collection in a wireless low floor tram”, in Proc. 2018 International Conference on Electronics, Information, and Communication (ICEIC 2018), Apr. 2018, pp. 1368-1373.

[2] Y.-S. Chiou, F. Tsai, and S.-C Yeh, “A dead-reckoning positioning scheme using inertial sensing for location estimation” in Proc. 2014 IEEE The Tenth International Conference on Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP 2014), Aug. 2014, pp. 377-380.

[3] Q. Li, R. Li, K. Ji, and W. Dai, “Kalman filter and its application,” in Proc. 2015 8th International Conference on Intelligent Networks and Intelligent Systems (ICINIS 2015), Nov. 2015, pp. 74-77.

[4] S. Wang, J. Feng, and C. K. Tse, “Analysis of the characteristic of the kalman gain for 1-D chaotic maps in cubature kalman filter,” IEEE Signal Process. Lett., vol. 20, no. 3, pp. 229-232, Mar. 2013.

[5] A. Jain and P. Krishnamurthy, “Phase noise tracking and compensation in coherent optical systems using Kalman filter,” IEEE Commun. Lett., vol. 20, no. 6, pp. 1072-1075, Jun. 2016.