Parallel algorithms and architectures for near-far resistant CDMA acquisition
Cavallaro, Joseph R.
Doctor of Philosophy
Subspace-based algorithms are a class of algorithms for estimation problems in array signal processing and more recently near-far resistant Code Division Multiple Access (CDMA) acquisition problems. Subspace-based algorithms are based on estimating signal or noise subspaces from the received data vectors and then performing some form of optimization to estimate the desired parameters. This thesis presents two new parallel algorithms applicable in the estimation of signal or noise subspaces from the received data vectors. The first algorithm is a pipelined SVD algorithm which allows pipelining of multiple independent singular value decomposition (SVD) problems on a single processor array. The resultant algorithm uses the flexibility provided by the Jacobi algorithm by defining a new parallel ordering to result in a simple uniform array in which all communication including the initial load and the final unload operations are pipelined. The second algorithm described in this thesis is a sliding window SVD updating algorithm where the signal or noise subspace is updated whenever a new observation vector is received by applying a fixed-length window over the data. An important result shown in this thesis is that an important property of downdating problems, known as relational stability, extends to a hybrid fixed-point and floating-point algorithm. By performing most of the computation in fixed-point, significant gains in implementation complexity may be realized. This thesis also extends an SVD algorithm originally developed for an exponential window to the sliding window problem through the use of carefully implemented hyperbolic rotations. A second major topic of this thesis is demonstrating the applicability of a number of algorithms and architectures developed in the array signal processing area to the near-far resistant acquisition problem in CDMA communication systems. This thesis classifies the available literature in this area and performs a qualitative analysis of the different algorithms from the view of applicability towards the CDMA problem. The third contribution of this thesis is a unified parallel architecture to implement the backend portions of the CDMA problem. Through the combination of a matrix vector multiplication array, an inner product computation array and an array of processors to perform second-order or third-order polynomial optimization a parallel architecture to implement the backend processing in the CDMA problem is realized.
Electronics; Electrical engineering