FPGA Implementation of a Real-Time Direction Finding System

Abstract

Bluetooth Direction Finding (BDF) ble introdusert av Bluetooth Special Interest Group (SIG) med Bluetooth 5.1-kjernespesifikasjonen. Den nye funksjonen gir forbedret retningssøk, noe som gjør det mulig for smarte enheter å lokalisere fysiske steder ned til en nøyaktighet målt i centimeter. Samtidig kan enhetene opprettholde prisnivået og strømkravet knyttet til slike enheter. BDF har flere fordeler sammenlignet med tradisjonelle posisjonssporingsteknologier som Global Navigation Satellite System (GNSS), Received Signal Strength Indication (RSSI) og Time of Flight (ToF), som bare er i stand til å estimere nærheten til andre enheter og derfor ikke finne retningen.

Denne avhandlingen tar sikte på å utvikle og undersøke muligheten for å bruke en Field Programmable Gate Array (FPGA) for å øke hastigheten på beregningene som kreves for å bestemme Angle of Arrival (AoA) til en Bluetooth-tag og sammenligne den med en tradisjonell programvareimplementering. En programvaremodell av systemet er implementert i MATLAB og Python, mens maskinvaredesignet er skrevet i VHDL. Designet er syntetisert og implementert på en Zynq Z2 FPGA ved hjelp av Vivavdo-2022.2. Hovedfokus i oppgaven er å implementere MUltiple SIgnal Classification (MUSIC) algoritmen i maskinvare. MUSIC er en type retningssøkingsalgoritme med svært høy oppløsning, og den består av de følgende delene: utfør Covariance Matrix Calculation (CMC) på de innkommende målingene og deretter utføre Eigenvalue Decomposition (EVD) for å finne egenvektorene. Egenvektorene brukes deretter til å estimere retningen til det innkommende signalet ved hjelp av Spectral Peak Search (SPS). En Real-valued Transformation (RVT)-metode er implementert for å øke hastigheten og redusere den nødvendige maskinvaren for beregning av egenvektorene ved å transformere komplekse verdier til reelle verdier uten en reduksjon i nøyaktighet. Denne metoden reduserer arealet og kjøretiden med omtrent 50%. Egenvektorene beregnes ved hjelp av en state-of-the-art parallell metode for å løse egenverdiproblemet, noe som reduserer beregningstiden fra 190 µs til 2.88 µs sammenlignet med en seriell metode.

Implementeringen av MUSIC algoritmen i maskinvare kan beregne asimut og høyde av en innkomende Bluetooth pakke i løpet av 6 µs ved en klokkefrekvens på 100 MHz. Et tilsvarende Python- og MATLAB-program har en gjennomsnittlig kjøretid på henholdsvis 112 ms og 22 ms. Algoritmen implementert i maskinvare er omtrent fire størrelsesordener raskere, og den kan finne retningen med en nøyaktighet på 1 grad i to dimensjoner. Designet benytter henholdsvis 61%, 15%, 89%, 90% og 1% av de tilgjengelige oppslagstabellene, registrene, Digital Signal Processing (DSP)-skiver, blokkminne og F7 multiplekserere. Maskinvare implementasjonen bruker totalt 1.4 W med strøm i motseting til en personlig datamaskin som bruker 60 W.

Bluetooth Direction Finding (BDF) was introduced by the Bluetooth Special Interest Group (SIG) with the Bluetooth 5.1 core specification. This new feature brings enhanced direction-finding capabilities that allow smart devices to pinpoint physical locations down to centimeter accuracy while maintaining the low cost and power requirements associated with such devices. BDF has several advantages over traditional location tracking technologies such as Global Navigation Satellite System (GNSS), Received Signal Strength Indication (RSSI), and Time of Flight (ToF), which are only capable of estimating the proximity of other devices and therefore unable to find the direction.

This thesis aims to develop and research the feasibility of using a Field Programmable Gate Array (FPGA) to accelerate the calculations required to determine the Angle of Arrival (AoA) of a Bluetooth tag and compare it to a traditional software implementation. A software model of the system has been implemented in MATLAB and Python, while the hardware design is written in VHDL. The design is synthesized and implemented on the Zynq Z2 FPGA using Vivavdo-2022.2. The main focus of the thesis is to implement the MUltiple SIgnal Classification (MUSIC) algorithm in hardware. MUSIC is a type of super-resolution direction-finding algorithm, and it consists of the following: perform Covariance Matrix Calculation (CMC) on the incoming samples and then conduct Eigenvalue Decomposition (EVD) to obtain the eigenvectors. The eigenvectors are, in turn, used to estimate the direction of the incoming signal using Spectral Peak Search (SPS). A Real-valued Transformation (RVT) method has been implemented to speed up and reduce the required hardware for calculating the eigenvectors by transforming complex values into real values without reducing accuracy. This method reduces the area and computational time by approximately 50%. The eigenvectors are computed using a state-of-the-art parallel method for solving the eigenvalue problem, which reduces the calculation time from 190 µs to 2.88 µs compared to the serial method.

The hardware implementation of the MUSIC algorithm can compute the azimuth and elevation of an incoming Bluetooth package in 6 µs at a clock frequency of 100 MHz. An equivalent Python and MATLAB program has an average run time of 112 ms and 22 ms, respectively. The algorithm implemented in hardware is approximately four orders of magnitude faster, and it can find the direction with an accuracy of 1 degree in two dimensions. The design utilizes 61%, 15%, 89%, 90%, and 1.35% of the available look-up tables, registers, Digital Signal Processing (DSP) slices, block ram, and F7 multiplexers, respectively. The hardware implementation draws 1.4 W of power compared to 60 W when running on a general-purpose computer.