Browsing by Author "Liu, K.J. Ray"
Results Per Page
Sort Options
Item Adaptive Blind Multi-Channel Equalization for Multiple Signals Separation(1995) Li, Ye; Liu, K.J. Ray; ISRThis paper investigates adaptive blind equalization for multiple- input and multiple-output (MIMO) channels and its application to blind separation of multiple signals received by antenna arrays in communication systems. The performance analysis is presented for the CMA equalizer used in MIMO channels. Our analysis results indicate that a double infinite-length MIMO-CMA equalizer can recover one of the input signals, remove the intersymbol interference (ISI), and suppress the rest signals. In particular, for the MIMO FIR channels satisfying certain conditions, the MIMO-CMA FIR equalizer is able to remove the ISI and co-channel interference regardless of the initial setting of the blind equalizer. To recover all input signals simultaneously, a novel MIMO channel blind equalization algorithm is developed in this paper. The global convergence of the new algorithm for MIMO channels is proved. Hence, the new blind equalization algorithm for MIMO channels can be applied to separate and equalize the signals received by antenna arrays in communication systems. Finally, computer simulations are presented to confirm our analysis and illustrate the performance of the new algorithm.Item Algorithm-Based Low-Power Transform Coding Architectures- Part I: The multirate Approach(1995) Wu, A-Y.; Liu, K.J. Ray; ISRIn most low-power VLSI designs, the supply voltage is usually reduced to lower the total power consumption. However, the device speed will be degraded as the supply voltage goes down. In this paper, we propose new algorithmic-level techniques for compensating the increased delays based on the multirate approach. We present two methods, the Chebyshev polynomial approach and the polyphase decomposition approach, to design low- power but high-speed transform coding architectures. We will show how to compute the discrete cosine transform (DCT) and its inverse (IDCT) through the decimated low-speed sequences with reasonable linear hardware overhead. For the case the decimation factor equal to two, the overall power consumption can be reduced to about one-third of the original design at the architectural level. Extension of our design to higher decimation rate is also achievable and can result in even lower power consumption. The resulting multirate low-power architectures are regular, modular, and free of global communications. Also, the compensation capability is achieved at the expense of locally increased hardware and data paths. As a consequence, they are very suitable for VLSI implementation. The proposed architectures can also be applied to very high-speed block transforms where only low-speed operators are required. The extensions of the algorithm-based low-power design, such as the unified transform architecture and finite-wordlength effect of the design, will be discussed in the companion paper.Item Algorithm-Based Low-Power Transform Coding Architectures- Part II: Logarithmic Complexity, Unified Architecture, and Finite- Precision Analysis(1995) Wu, A-Y.; Liu, K.J. Ray; ISRIn the companion paper, we addressed the low-power DCT/IDCT VLSI architectures of linear complexity increase based on the multirate approach. In this paper, we will discuss other aspects of the low-power design. Firstly, we consider the design of low- power architectures that can lower the power consumption at only O(logM) increase in hardware complexity. Next, we will extend the low-power DCT design to other orthogonal transforms such as Modulated Lapped Transform (MLT) and Extended Lapped Transform (ELT). A unified programmable IIR low-power transform module, which can perform most of the existing discrete sinusoidal transforms, is also proposed. Finally, we perform the finite- precision analysis of the DCT architecture under the normal and multirate operations. In VLSI design, the assignment of the system wordlength will directly affect the total switching events and routing capacities, hence the power consumption. Using the analytical results, we can choose the optimal wordlength for each DCT channel under required signal-to-noise ratio (SNR) constraint. The material presented in this paper, together with the multirate architectures in the companion paper, provides a framework for the algorithm-based low-power transform coding kernel design.Item Anti-Collusion Fingerprinting for Multimedia(2002) Trappe, Wade; Wu, Min; Liu, K.J. Ray; ISRDigital fingerprinting is a technique for identifyingusers who might try to use multimedia content for unintendedpurposes, such as redistribution. These fingerprints are typicallyembedded into the content using watermarking techniques that aredesigned to be robust to a variety of attacks. A cost-effectiveattack against such digital fingerprints is collusion, whereseveral differently marked copies of the same content are combinedto disrupt the underlying fingerprints. In this paper, weinvestigate the problem of designing fingerprints that canwithstand collusion and allow for the identification of colluders.We begin by introducing the collusion problem for additiveembedding. We then study the effect that averaging collusion hasupon orthogonal modulation. We introduce an efficient detectionalgorithm for identifying the fingerprints associated with Kcolluders that requires O(K log(n/K)) correlations for agroup of n users. We next develop a fingerprinting scheme basedupon code modulation that does not require as many basis signalsas orthogonal modulation. We propose a new class of codes, calledanti-collusion codes (ACC), which have the property that thecomposition of any subset of K or fewer codevectors is unique.Using this property, we can therefore identify groups of K orfewer colluders. We present a construction of binary-valued ACCunder the logical AND operation that uses the theory ofcombinatorial designs and is suitable for both the on-off keyingand antipodal form of binary code modulation. In order toaccommodate n users, our code construction requires onlyO(sqrt{n}) orthogonal signals for a given number of colluders.We introduce four different detection strategies that can be usedwith our ACC for identifying a suspect set of colluders. Wedemonstrate the performance of our ACC for fingerprintingmultimedia and identifying colluders through experiments usingGaussian signals and real images.This paper has been submitted to IEEE Transactions on Signal Processing Item Blind Adaptive Equalization of SIMO Channels Based on Second- Order Statistics(1996) Li, Ye; Liu, K.J. Ray; ISRThis article investigates blind adaptive equalization for single- input/multiple-output (SIMO) channels. A second-order statistics based algorithm (SOSA) and a modified second-order statistics based algorithm (MSOSA) for equalization of SIMO channels are presented. Computer simulation demonstrates that the new algorithms converge faster than fractionally spaced constant- modulus algorithm (FS-CMA). The proposed algorithms can be applied in wireless communication systems with antenna arrays to combat the multipath fading.Item Blind MIMO FIR Channel Identification Based on Second-Order Statistics with Multiple Signals Recovery(1996) Li, Ye; Liu, K.J. Ray; ISRTo separate and recover multiple signals in data communications, antenna arrays and acoustic sensor arrays, the impulse responses of multiple-input/multiple-output (MIMO) channels have to be identified explicitly or implicitly. This paper deals with the blind identification of MIMO FIR channels based on second-order statistics of the channel outputs. We first investigate the identifiability of MIMO FIR channels, and obtain a necessary and sufficient condition for MIMO FIR channels to be identifiable up to a unitary matrix using second-order statistics. Then, we extend the identification algorithms for single-input/multiple- output (SIMO) FIR channels, such as the algebraic algorithm and the subspace algorithm to the identification of MIMO FIR channels. We also present the application of the above blind identification algorithms to the separation of multiple signals in digital communication systems. Finally, we demonstrate the effectiveness of the algorithms presented in this paper by computer simulationsItem A Class of Square Root and Division Free Algorithms and Architectures for QRD-Based Adaptive Signal Processing(1993) Frantzeskakis, Emmanuel N.; Liu, K.J. Ray; ISRThe least squares (LS) minimization problem constitutes the cores of many real-time signal processing problems, such as adaptive filtering, system identification and adaptive beamforming. Recently efficient implementations of the recursive least squares (RLS) algorithm and the constrained recursive least squares (CRLS) algorithm based on the numerically stable QR decomposition (QRD) have been of great interest. Several papers have proposed modifications to the rotation algorithm that circumvent the square root operations and minimize the number of divisions that are involved in the Givens rotation. It has also been shown that all the known square root free algorithms are instances of one parametric algorithm. Recently, a square root free and division free algorithm has been proposed [4].In this paper, we propose a family of square root and division free algorithms and examine its relationship with the square root free parametric family. We choose a specific instance for each one of the two parametric algorithms and make a comparative study of the systolic structures based on these two instances, as well as the standard Givens rotation. We consider the architectures for both the optimal residual computation and the optimal weight vector extraction.
The dynamic range of the newly proposed algorithm for QRD-RLS optimal residual computation and the wordlength lower bounds that guarantee no overflow are presented. The numberical stability of the algorithm is also considered. A number of obscure points relevant to the realization of the QRD-RLS and QRD-CRLS algorithms are clarified. Some systolic structures that are described in this paper are very promising, since they require less computational complexity ( in various aspects) than the structures known to date and they make the VLSI implementation easier.
Item Coherent Signal Processing Using Arrays of Arbitrary Geometry(1994) Wang, H.; Liu, K.J. Ray; ISRThe existing spatial smoothing (SS) technique, although it is effective in decorrelating coherent signals, can only be applied to uniformly spaced linear arrays which are very sensitive to the directions-of-arrival (DOA's) and can be used to estimate arimuth angles only. To significantly improve the robustness of DOA estimation and of beamforming and to estimate both arimuth and elevation angles, we developed techniques for applying SS to arrays of arbitrary geometry. We found that an array must have an orientational invariance structure with an ambiguity free center array for applying SS. We also study the cause of ambiguities in a multiple signal environment and find the necessary and sufficient conditions for an array manifold to be ambiguity free. If an array is also central symmetric, the forward/backward spatial smoothing can be used to improve the resolution. Finally, we expand the application of our technique not only to MUSIC and adaptive beamforming algorithms but also to ESPRIT algorithm. All the predicted results are verified by simulations.Item DCT-Based Motion Estimation(1995) Koc, Ut-Va; Liu, K.J. Ray; ISRA new motion estimation approach, the DCT-Based Motion Estimation Scheme (DXT-ME) utilizing the sinusoidal orthogonal principles to estimate displacements of moving objects in the transform domain, based upon the concept of pseudo phases, is presented in this paper. The computational complexity of this method is only O(N2) for an N x N block in comparison to the O(N4) complexity of Full Search Block Matching Approach (BMA-ME). In addition, the DXT-ME algorithm has solely highly parallel local operations and this property makes parallel implementation feasible. Furthermore, incorporation of DXT-ME with a video coder using DCT can combine the DCT and motion estimation algorithm to achieve further saving in overall system complexity and increase the system throughput. Unlike the pel-recursive algorithm, this scheme is robust for even very noisy images. Due to its feature matching property, we can employ simple preprocessing in images of complicated scenery to extract the features of moving objects for DXT-ME to further improve its performance. Finally simulation on a number of video sequences is presented to compare DXT-ME with BMA-ME.Item Dual-State Systolic Architectures for Adaptive Filtering Using Up/Downdating RLS(1991) Hsieh, S.F.; Liu, K.J. Ray; Yao, K.; ISRWe propose a dual-state systolic structure to perform joint up/down-dating operations encountered in windowed recursive least squares (RLS) estimation problems. It is derived by successively performing Givens rotations for updating and hyperbolic rotations for down-dating. Due to the data independency, a series of Givens and hyperbolic rotations can be interleaved and parallel processing can be achieved by alternatively performing updating and downdating both in time and space. This flip-flop nature of up/down-dating characterizes the feature of dual-state systolic triarray. To further reduce the complexity and increase the throughput rate, Cordic cells can be used to mimic the operations of rowbroadcasting and only one control bit is required along each row of processors. Efficient implementation to obtain optimal residuals and a transformation of the hyperbolic rotation to an algebraically equivalent orthogonal operation to provide a more stable implementation are also considered. This systolic architecture is very promising in VLSI implementation of the sliding-window recursive least squares estimations.Item Dynamic Range, Stability, and Fault-tolerant Capability of Finite-precision RLS Systolic Array Based on Givens Rotations(1990) Liu, K.J. Ray; Hsieh, S.F.; Yao, K.; Chiu, Ching-Te; ISRThe QRD RLS algorithm is generally recognized as having good numerical properties under finite-precision implementation. Also, it is very suitable for VLSI implementation since it can be easily mapped onto a systolic array. However, it is still unclear how to obtain the dynamic range of the algorithm such that a wordlength can be chosen to ensure correct operations of the algorithm. In this paper, we first propose a quasi-steady state model by observing the rotation parameters generated by boundary cells will eventually reach quasi steady-state regardless of the input data statistics if l is close to one. With this model, we can obtain upper bounds of the dynamic range of processing cells. Thus, the wordlength can be obtained from upper bounds of the dynamic range to prevent overflow and to ensure correct operations of the QRD RLS algorithm. Then we reconsider the stability problem under quantization effects with more general analysis and obtain tighter bounds than given in a previous work [13]. Finally, two fault-tolerant problems, the missing error detection and the false alarm effect, the arise under finite- precision implementation are considered. Detail analysis on preventing missing error detection with a false alarm free condition is presented.Item An ESPRIT Algorithm for Tracking Time-Varying Signals(1992) Liu, K.J. Ray; O'Leary, D.P.; Stewart, G.W.; Wu, Y-J.; ISRESPRIT is a successful algorithm for determining the constant directions of arrival of a set of narrowband signals on an array of sensors. Unfortunately, its computational burden makes it unsuitable for real time processing of signals with time-varying directions of arrival. In this work we develop a new implementation of ESPRIT that has potential for real time processing. It is based on a rank-revealing URV decomposition, rather than the eigendecomposition or singular value decomposition used in previous ESPRIT algorithms. We demonstrate its performance on simulated data representing both constant and time-varying signals. We find that the URV-based ESPRIT algorithm (total least squares variant) is effective for time- varying directions-of-arrival using either rectangular or exponential windowing techniques to diminish the effects of old information.Item Estimation of Multiple Sinusoidal Frequencies Using Truncated Least-Squares Methods(1991) Hsieh, S.F.; Liu, K.J. Ray; Yao, K.; ISRTufts and Kumaresan (1982) first proposed using a SVD-based method to solve the forward-backward linear prediction (FBLP) least-squares problem for resolving closely spaced frequencies of multiple sinusoids from limited amount of data samples. By imposing an excessive order in the FBLP model and then truncating small singular values to zero, this truncated SVD (TSVD) method yields a low SNR threshold and greatly suppresses spurious frequencies. However, the massive computation required by SVD makes it unsuitable for real time super-resolution applications. We propose to use truncated QR methods which are amenable to VLSI implementations, such as systolic arrays, with slightly degraded performances as compared to the TSVD method. Three truncated QR methods for sinusoidal frequency estimation will be considered: (1) truncated QR without column pivoting (TQR); (2) truncated QR with re-ordered columns (TQRR); and (3) truncated QR with column pivoting (TQRP). It is demonstrated that the benefit of the TSVD method for high frequency resolution is achievable under the truncated QR methods with much lower computational cost. Other attractive features of the proposed methods include the ease of updating which is difficult for the SVD method, and numerical stability. Thus, the TQR methods offer efficient ways for identifying sinusoids closedly clustered in frequencies under stationary and nonstationary conditions. Some results based on the truncated normal equation approach as well as on sufficient conditions for perfect truncations based on truncated QR and SVD methods are considered. Based on the FBLP model, computer simulations and comparisons are provided for different truncation methods under various SNR's. Comparisons of asymptotic performance with large data samples are also given.Item Exact Subpixel Motion Estimation in DCT Domain(1996) Koc, Ut-Va; Liu, K.J. Ray; ISRCurrently existing subpixel motion estimation algorithms require interpolation of inter-pixel values which undesirably increases the overall complexity and data flow and deteriorates estimation accuracy. In this paper, we develop DCT-based techniques to estimate subpel motion at different desired subpel levels of accuracy in DCT domain without interpolation. We show that subpixel motion information is preserved in the DCT of a shifted signal under some condition in the form of pseudo phases and establish subpel sinusoidal orthogonal principles to extract this information. Though applicable to other areas as well, the resulted algorithm from these techniques for video coding are flexible and scalable in terms of estimation accuracy with very low computational complexity O(N2) compared to O(N4) for Full Search Block Matching Approach and its subpixel versions. Above all, motion estimation in DCT domain instead of spatial domain simplifies the conventional hybrid DCT-based video coder, especially the heavily loaded feedback loop in the conventional design, resulting in a fully DCT-based high-throughput video codec. In addition, the computation of pseudo phases is local and thus a highly parallel architecture is feasible for the DCT- based algorithms. Finally simulation on video sequences of different characteristics shows comparable performance of the proposed algorithms to block matching approaches.Item Fast Algorithms for 2-D Circular Convolutions and Number Theoretic Transforms Based on Polynomial Transforms over Finite Rings(1992) Ran, X.; Liu, K.J. Ray; ISRIn this paper, we develop new fast algorithms for 2-D integer circular convolutions and 2-D Number Theoretic Transforms (NTT). These new algorithms, which offers improved computational complexity, are constructed based on polynomial transforms over Zp; these transforms are Fourier-like transforms over Zp [x ] which is the integral domain of polynomial forms over Zp. Having defined such polynomial transforms over Zp, we prove several necessary and sufficient conditions for their existence. We then apply the existence conditions to recognize two applicable polynomial transforms over Zp: One is for p equal to Mersenne numbers and the other for Fermat numbers. Based on these two transforms, referred to as Mersenne Number Polynomial Transforms (MNPT) and Fermat Number Polynomial Transforms (FNPT), we develop fast algorithms for 2-D integer circular convolutions, 2-D Mersenne Number Transforms, and 2-D Fermat Number Transforms. As compared to the conventional row-column computation of 2-D NTT for 2-D integer circular convolutions and 2-D NTTs, the new algorithms give rise to reduced computational complexities by saving more than 25% or 42% in numbers of operations for multiplying 2i, i 1; these percentages of savings also grow with the size of the 2-D integer circular convolutions or the 2-D NTTs.Item Fast Blind Adaptive Algorithms for Equalization and Diversity Reception in Wireless Communications Using Antenna Arrays(1996) Li, Ye; Liu, K.J. Ray; ISRTo combat the multipath and time-variant fading of wireless communication channels, antenna arrays are usually used to improve the quality and increase the capacity of communication service. This paper investigates the fast blind adaptive algorithms for the equalization and diversity combining in wireless communication systems using antenna arrays. Two second- order statistics based algorithms, SOSA and MSOS, for equalization and diversity combining are proposed and their convergence in noiseless and noisy channels is analyzed. Since the proposed algorithms use only second-order statistics or correlation of the channel outputs, they converge faster than the higher-order statistics based algorithms, which is also confirmed by computer simulations examples.Item A Fast Minimal-Symbol Subspace Approach to Blind Identification and Equalization(1995) Sampath, B.; Li, Ye; Liu, K.J. Ray; ISRA subspace-based blind channel identification algorithm using only the fact that the received signal can be oversampled is proposed. No direct use is made of the statistics of the input sequence or even of the fact that the symbols are from a finite set and therefore this algorithm can be used to identify even channels in which arbitrary symbols are sent. A modification of this algorithm which uses the extra information in the more common case when the symbols are from a finite set is also presented. This LS-Subspace algorithm operates directly on the data domain and therefore avoids the problems associated with other algorithms which use the statistical information contained in the received signal. In the noiseless case, it is possible for the proposed Basic Subspace algorithm to identify the channel exactly using the least number of symbols that can possibly be used. Thus, if the length of the impulse response of a channel is JT, T being the symbol interval, then it is possible to use this algorithm to identify the channel using an observation interval of just (J + 3)T. In the noisy case, simulations have shown that almost exact identification can be obtained by using a few more symbols than the theoretical minimum. This is orders of magnitude better than the other blind algorithms. Moreover, this algorithm is computationally very efficient and has no convergence problems.Item Fast Orthogonalization Algorithm and Parallel Implementation for AR Spectral Estimation Based on Forward-Backward Linear Prediction(1991) Liu, K.J. Ray; Hsieh, S.F.; ISRHigh-resolution spectral estimation is an important subject in many applications of modern signal processing. The fundamental problem in applying various high-resolution spectral estimation algorithms is the computational complexity. Recently, the truncated QR methods have been shown to be comparable to the SVD- based methods for the sinusoidal frequency estimation based on the forward-backward linear prediction (FBLP) model. However, without exploiting the special structure of the FBLP matrix, the QR decomposition (QRD) of the FBLP matrix has the computational complexity on the order of n cubic for a 2m x n FBLP matrix. Here we propose a fast algorithm to perform the QRD of the FBLP matrix. It is based on exploiting the special Toeplitz-Hankel form of the FBLP matrix. The computational complexity is then reduced to the order of n square. The fast algorithm can also be easily implemented onto a linear systolic array. The number of time steps required is further reduced to 2m + 5n - 4 by using the parallel implementation. The geometric transformation, which improves the numerical stability, for the downdating of the Cholesky factors is also considered.Item Fractal Modeling and Segmentation for the Enhancement of Microcalcifications in Digital Mammograms(1996) Li, Huai; Liu, K.J. Ray; Lo, Shih-Chung B.; ISRThe objective of this research is to model the mammographic parenchymal, ductal patterns and enhance the microcalcifications using deterministic fractal approach. According to the theory of deterministic fractal geometry, images can be modeled by deterministic fractal objects which are attractors of sets of two dimensional affine transformations. The Iterated Functions Systems and the Collage Theorem are the mathematical foundations of fractal image modeling. In this paper, a methodology based on fractal image modeling is developed to analyze and extract various mammographic textures. We show that general mammographic parenchymal and ductal patterns can be well modeled by a set of parameters of affine transformations. Therefore, microcalcifications can be enhanced by taking the difference between the original image and the modeled image. Our results are compared with those of the partial wavelet reconstruction and morphological operation approaches. The results demonstrate that the fractal modeling method is an effective way to enhance microcalcifications, and thereby facilitate the radiologists' diagnosis. It may also be able to improve detection and classification of microcalcifications in a computer system.Item A Fully Parallel and Pipelined Systolic Array for MVDR Beamforming(1991) Tang, C.F.T.; Liu, K.J. Ray; ISRA fully-pipelined systolic array for computing the minimum variance distortionless response (MVDR) was first proposed by McWhirter and Shepherd. The fundamental concept is to fit the MVDR beamforming to the non-contrainted recursive least-squares (RLS) minimization. Until now, their systolic array processor is well-recognized as the most efficient design for MVDR beamforming. In this paper, we first point out the mistake by relating the MVRD beamforming and RLS minimization and then propose a new algorithm for the MVDR beamforming. Moreover, a fully parallel and pipelined systolic array for the newly proposed algorithm is presented and the square-root free implementation is also considered.
- «
- 1 (current)
- 2
- 3
- »