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.

Using Dynamic Programming Decomposition for Revenue Management with Opaque Products

Opaque products enable service providers to hide specific characteristics of their service fulfillment from the customer until after purchase. Prominent examples include internet-based service providers selling airline tickets without defining details, such as departure time or operating airline, until the booking has been made. Owing to the resulting flexibility in resource utilization, the traditional revenue management process needs to be modified. In this paper, we extend dynamic programming decomposition techniques widely used for traditional revenue management to develop an intuitive capacity control approach that allows for the incorporation of opaque products. In a simulation study, we show that the developed approach significantly outperforms other well-known capacity control approaches adapted to the opaque product setting. Based on the approach, we also provide computational examples of how the share of opaque products as well as the degree of opacity can influence the results.

The role of peat decomposition in patterned mires: a case study from the central Swiss Alps

A number of hydrological, botanical, macro- and micro-climatological processes are involved in the formation of patterned peatlands. La Grande Tsa at 2336 m a.s.l. is probably the highest bog in the central Swiss Alps and is unique in its pattern. In two of five pools there is in the contact zone between the basal peat and the overlying gyttja an unconformity in the depth-age models based on radiocarbon dates. Palynostratigraphies of cores from a ridge and a pool confirm the occurrence of an unconformity in the contact zone. We conclude that deepening of the pools results from decomposition of peat. The fact that the dated unconformities in the two pools and the unconformity in the ridge-core all fall within the Bronze Age suggest they were caused by events external to the bog. We hypothesize that early transhumance resulted in anthropogenic lowering of the timberline, which resulted in a reduction in the leaf-area index and evapotranspiration, and in higher water levels and thus pool formation.

Topographic time-frequency decomposition of the EEG

Frequency-transformed EEG resting data has been widely used to describe normal and abnormal brain functional states as function of the spectral power in different frequency bands. This has yielded a series of clinically relevant findings. However, by transforming the EEG into the frequency domain, the initially excellent time resolution of time-domain EEG is lost. The topographic time-frequency decomposition is a novel computerized EEG analysis method that combines previously available techniques from time-domain spatial EEG analysis and time-frequency decomposition of single-channel time series. It yields a new, physiologically and statistically plausible topographic time-frequency representation of human multichannel EEG. The original EEG is accounted by the coefficients of a large set of user defined EEG like time-series, which are optimized for maximal spatial smoothness and minimal norm. These coefficients are then reduced to a small number of model scalp field configurations, which vary in intensity as a function of time and frequency. The result is thus a small number of EEG field configurations, each with a corresponding time-frequency (Wigner) plot. The method has several advantages: It does not assume that the data is composed of orthogonal elements, it does not assume stationarity, it produces topographical maps and it allows to include user-defined, specific EEG elements, such as spike and wave patterns. After a formal introduction of the method, several examples are given, which include artificial data and multichannel EEG during different physiological and pathological conditions.

Litter breakdown and mineralization in a central African rain forest dominated by ectomycorrhizal trees

Based on litter mass and litterfall data, decomposition rates for leaves were found to be fast (k = 3.3) and the turnover times short (3.6 mo) on the low-nutrient sandy soils of Korup. Leaf litter of four ectomycorrhizal tree species (Berlinia bracteosa, Didelotia africana, Microberlinia bisulcata and Tetraberlinia bifoliolata) and of three non-ectomycorrhizal species (Cola verticillata, Oubanguia alata and Strephonema pseudocola) from Korup were left to decompose in 2-mm mesh bags on the forest floor in three plots of each of two forest types forest of low (LEM) and high (HEM) abundance of ectomycorrhizal (caesalp) trees. The litter of the ectomycorrhizal species decayed at a significantly slower rate than that of the non-ectomycorrhizal species, although the former were richer in P and N concentrations of the start. Disappearance rates of the litter layer showed a similar trend. Ectomycorrhizal species immobilized less N, but mineralized more P, than non-ectomycorrhizal species. Differences between species groups in K, Mg and Ca mineralization were negligible. Effect of forest type was clear only for Mg: mineralization of Mg was faster in the HEM than LEM plots, a pattern repeated across all species. This difference was attributed to a much more prolific fine root mat in the HEM than LEM forest. The relatively fast release of P from the litter of the ectomycorrhizal species suggests that the mat must allow an efficient uptake to maintain P in the forest ecosystem.