HIGH PERFORMANCE, LOW COST SUBSPACE DECOMPOSITION AND POLYNOMIAL ROOTING FOR REAL TIME DIRECTION OF ARRIVAL ESTIMATION: ANALYSIS AND IMPLEMENTATION

This thesis develops high performance real-time signal processing modules for direction of arrival (DOA) estimation for localization systems. It proposes highly parallel algorithms for performing subspace decomposition and polynomial rooting, which are otherwise traditionally implemented using sequential algorithms. The proposed algorithms address the emerging need for real-time localization for a wide range of applications. As the antenna array size increases, the complexity of signal processing algorithms increases, making it increasingly difficult to satisfy the real-time constraints. This thesis addresses real-time implementation by proposing parallel algorithms, that maintain considerable improvement over traditional algorithms, especially for systems with larger number of antenna array elements. Singular value decomposition (SVD) and polynomial rooting are two computationally complex steps and act as the bottleneck to achieving real-time performance. The proposed algorithms are suitable for implementation on field programmable gated arrays (FPGAs), single instruction multiple data (SIMD) hardware or application specific integrated chips (ASICs), which offer large number of processing elements that can be exploited for parallel processing. The designs proposed in this thesis are modular, easily expandable and easy to implement. Firstly, this thesis proposes a fast converging SVD algorithm. The proposed method reduces the number of iterations it takes to converge to correct singular values, thus achieving closer to real-time performance. A general algorithm and a modular system design are provided making it easy for designers to replicate and extend the design to larger matrix sizes. Moreover, the method is highly parallel, which can be exploited in various hardware platforms mentioned earlier. A fixed point implementation of proposed SVD algorithm is presented. The FPGA design is pipelined to the maximum extent to increase the maximum achievable frequency of operation. The system was developed with the objective of achieving high throughput. Various modern cores available in FPGAs were used to maximize the performance and details of these modules are presented in detail. Finally, a parallel polynomial rooting technique based on Newton’s method applicable exclusively to root-MUSIC polynomials is proposed. Unique characteristics of root-MUSIC polynomial’s complex dynamics were exploited to derive this polynomial rooting method. The technique exhibits parallelism and converges to the desired root within fixed number of iterations, making this suitable for polynomial rooting of large degree polynomials. We believe this is the first time that complex dynamics of root-MUSIC polynomial were analyzed to propose an algorithm. In all, the thesis addresses two major bottlenecks in a direction of arrival estimation system, by providing simple, high throughput, parallel algorithms.

Optical Indoor Positioning of Vehicles

Indoor positioning is the backbone of many advanced intra-logistic applications. As opposed to unified outdoor satellite positioning systems, there are many different technical approaches to indoor positioning. Depending on the application, there are different trade-offs between accuracy, range, and costs. In this paper we present a new concept for a 4-degree-of-freedom (4-DOF) positioning system to be used for vehicle tracing in a logistic facility. The system employs optical data transmission between active infrastructure and receiver devices. Compared to existing systems, these optical technologies promise to achieve better accuracy at lower costs. We will introduce the positioning algorithm and an experimental setup of the system.

Approximating method of frames

In this paper, the well-known method of frames approach to the signal decomposition problem is reformulated as a certain bilevel goal-attainment linear least squares problem. As a consequence, a numerically robust variant of the method, named approximating method of frames, is proposed on the basis of a certain minimal Euclidean norm approximating splitting pseudo-iteration-wise method.

Real-Time Passive Capturing of the GSM Radio

This paper addresses the problem of service development based on GSM handset signaling. The aim is to achieve this goal without the participation of the users, which requires the use of a passive GSM receiver on the uplink. Since no tool for GSM uplink capturing was available, we developed a new method that can synchronize to multiple mobile devices by simply overhearing traffic between them and the network. Our work includes the implementation of modules for signal recovery, message reconstruction and parsing. The method has been validated against a benchmark solution on GSM downlink and independently evaluated on uplink channels. Initial evaluations show up to 99% success rate in message decoding, which is a very promising result. Moreover, we conducted measurements that reveal insights on the impact of signal power on the capturing performance and investigate possible reactive measures.

Pathogenesis of AF: impact on intracardiac signals

Atrial fibrillation (AF) is the most common cardiac arrhythmia, and is responsible for the highest number of rhythm-related disorders and cardioembolic strokes worldwide. Intracardiac signal analysis during the onset of paroxysmal AF led to the discovery of pulmonary vein as a triggering source of AF, which has led to the development of pulmonary vein ablation--an established curative therapy for drug-resistant AF. Complex, multicomponent and rapid electrical activity widely involving the atrial substrate characterizes persistent/permanent AF. Widespread nature of the problem and complexity of signals in persistent AF reduce the success rate of ablation therapy. Although signal processing applied to extraction of relevant features from these complex electrograms has helped to improve the efficacy of ablation therapy in persistent/permanent AF, improved understanding of complex signals should help to identify sources of AF and further increase the success rate of ablation therapy.

Highly accurate evaluation of GPS synchronization for TDOA localization

Clock synchronization is critical for the operation of a distributed wireless network system. In this paper we investigate on a method able to evaluate in real time the synchronization offset between devices down to nanoseconds (as needed for positioning). The method is inspired by signal processing algorithms and relies on fine-grain time information obtained during the reconstruction of the signal at the receiver. Applying the method to a GPS-synchronized system show that GPS-based synchronization has high accuracy potential but still suffers from short-term clock drift, which limits the achievable localization error.

Distributed sensor failure detection in sensor networks

We investigate the problem of distributed sensors' failure detection in networks with a small number of defective sensors, whose measurements differ significantly from the neighbor measurements. We build on the sparse nature of the binary sensor failure signals to propose a novel distributed detection algorithm based on gossip mechanisms and on Group Testing (GT), where the latter has been used so far in centralized detection problems. The new distributed GT algorithm estimates the set of scattered defective sensors with a low complexity distance decoder from a small number of linearly independent binary messages exchanged by the sensors. We first consider networks with one defective sensor and determine the minimal number of linearly independent messages needed for its detection with high probability. We then extend our study to the multiple defective sensors detection by modifying appropriately the message exchange protocol and the decoding procedure. We show that, for small and medium sized networks, the number of messages required for successful detection is actually smaller than the minimal number computed theoretically. Finally, simulations demonstrate that the proposed method outperforms methods based on random walks in terms of both detection performance and convergence rate.

Approximate decoding approaches for network coded correlated data

This paper considers a framework where data from correlated sources are transmitted with the help of network coding in ad hoc network topologies. The correlated data are encoded independently at sensors and network coding is employed in the intermediate nodes in order to improve the data delivery performance. In such settings, we focus on the problem of reconstructing the sources at decoder when perfect decoding is not possible due to losses or bandwidth variations. We show that the source data similarity can be used at decoder to permit decoding based on a novel and simple approximate decoding scheme. We analyze the influence of the network coding parameters and in particular the size of finite coding fields on the decoding performance. We further determine the optimal field size that maximizes the expected decoding performance as a trade-off between information loss incurred by limiting the resolution of the source data and the error probability in the reconstructed data. Moreover, we show that the performance of the approximate decoding improves when the accuracy of the source model increases even with simple approximate decoding techniques. We provide illustrative examples showing how the proposed algorithm can be deployed in sensor networks and distributed imaging applications.

Heart rate variability in response to pain stimulus in VLBW infants followed longitudinally during NICU stay.

The objective of this longitudinal study, conducted in a neonatal intensive care unit, was to characterize the response to pain of high-risk very low birth weight infants (<1,500 g) from 23 to 38 weeks post-menstrual age (PMA) by measuring heart rate variability (HRV). Heart period data were recorded before, during, and after a heel lanced or wrist venipunctured blood draw for routine clinical evaluation. Pain response to the blood draw procedure and age-related changes of HRV in low-frequency and high-frequency bands were modeled with linear mixed-effects models. HRV in both bands decreased during pain, followed by a recovery to near-baseline levels. Venipuncture and mechanical ventilation were factors that attenuated the HRV response to pain. HRV at the baseline increased with post-menstrual age but the growth rate of high-frequency power was reduced in mechanically ventilated infants. There was some evidence that low-frequency HRV response to pain improved with advancing PMA.

Intracranial EEG reveals a time- and frequency-specific role for the right inferior frontal gyrus and primary motor cortex in stopping initiated responses.

Inappropriate response tendencies may be stopped via a specific fronto/basal ganglia/primary motor cortical network. We sought to characterize the functional role of two regions in this putative stopping network, the right inferior frontal gyrus (IFG) and the primary motor cortex (M1), using electocorticography from subdural electrodes in four patients while they performed a stop-signal task. On each trial, a motor response was initiated, and on a minority of trials a stop signal instructed the patient to try to stop the response. For each patient, there was a greater right IFG response in the beta frequency band ( approximately 16 Hz) for successful versus unsuccessful stop trials. This finding adds to evidence for a functional network for stopping because changes in beta frequency activity have also been observed in the basal ganglia in association with behavioral stopping. In addition, the right IFG response occurred 100-250 ms after the stop signal, a time range consistent with a putative inhibitory control process rather than with stop-signal processing or feedback regarding success. A downstream target of inhibitory control is M1. In each patient, there was alpha/beta band desynchronization in M1 for stop trials. However, the degree of desynchronization in M1 was less for successfully than unsuccessfully stopped trials. This reduced desynchronization on successful stop trials could relate to increased GABA inhibition in M1. Together with other findings, the results suggest that behavioral stopping is implemented via synchronized activity in the beta frequency band in a right IFG/basal ganglia network, with downstream effects on M1.

Volume and shape in feature space on adaptive FCM in MRI segmentation.

Intensity non-uniformity (bias field) correction, contextual constraints over spatial intensity distribution and non-spherical cluster's shape in the feature space are incorporated into the fuzzy c-means (FCM) for segmentation of three-dimensional multi-spectral MR images. The bias field is modeled by a linear combination of smooth polynomial basis functions for fast computation in the clustering iterations. Regularization terms for the neighborhood continuity of either intensity or membership are added into the FCM cost functions. Since the feature space is not isotropic, distance measures, other than the Euclidean distance, are used to account for the shape and volumetric effects of clusters in the feature space. The performance of segmentation is improved by combining the adaptive FCM scheme with the criteria used in Gustafson-Kessel (G-K) and Gath-Geva (G-G) algorithms through the inclusion of the cluster scatter measure. The performance of this integrated approach is quantitatively evaluated on normal MR brain images using the similarity measures. The improvement in the quality of segmentation obtained with our method is also demonstrated by comparing our results with those produced by FSL (FMRIB Software Library), a software package that is commonly used for tissue classification.