Computationally attractive reconstruction of bandlimited imagesfrom irregular samples

An efficient method for the reconstruction of bandlimited images and the approximation of arbitrary images from nonuniform sampling values is developed. The novel method is based on the observation that the reconstruction problem can be formulated as linear system of equations using two-dimensional (2-D) trigonometric polynomials, where the matrix is of block-Toeplitz type with Toeplitz blocks. This system is solved iteratively by the conjugate gradient (CG) method. We show that the use of so-called adaptive weights in the establishment of the block Toeplitz matrix can be seen as efficient preconditioning. The superiority of the new method over conventional approaches is demonstrated by numerical experiments.     

Efficient calculation of finite Gabor transforms

The Gabor transform may be viewed as a collection of localized Fourier transforms and as such is useful for analysis of nonstationary signals and images. We present a new approach to analyzing the Gabor transform and use it to study the various critically sampled discretizations that form the infinite-discrete, periodic finite-discrete, and nonperiodic finite-discrete versions of the transform. In particular, we distinguish between the analysis and synthesis forms of the transform, and introduce an intermediate operation that decomposes both forms into collections of independent Toeplitz operators. In the continuous, the infinite-discrete, and the periodic finite-discrete cases, this decomposition allows us to show that, for appropriate windows, the analysis and synthesis transforms are inverses of each other. In the nonperiodic finite-discrete case this relation no longer holds, but we are still able to use the decomposition and results on Toeplitz matrices to show that both the transform and the inverse transform of P discrete samples are computable in O(P log P) operations (after a setup cost of O(Plog²P)). Furthermore, we use the decomposition to study in detail the differences between the periodic and nonperiodic versions of the transform and to compare their conditioning     

Some results on discrete Gabor transforms for finite periodicsequences

In this correspondence, using linear system theory and frame theory, we address computation methods for analysis and synthesis sequences of the discrete Gabor transform (DGT), where all sequences are periodic with the same period L, and show that the minimum energy solution to the Wexler and Raz (1990) biorthogonal condition and the solution to the frame operator are the same via linear system theory and frame theory     

Efficient real data filtering using complex-input discrete Fourier transforms

A new algorithm for efficient linear convolution of real signals using discrete Fourier transforms is presented. The traditional method uses a considerable amount of pre-processing and post-processing of both the input and output signals. We show that plenty of this processing can be shifted to the impulse response of the system, whose operations can be precomputed and therefore have no computational cost. This method results in computational savings, reducing the total arithmetic operations and particularly the execution time with regard to previously proposed techniques.     

A comparative review of real and complex Fourier-related transforms

Major continuous-time, discrete-time, and discrete Fourier-related transforms as well as Fourier-related series are discussed both with real and complex kernels. The complex Fourier transforms, Fourier series, cosine, sine, Hartley, Mellin, Laplace transforms, and z-transforms are covered on a comparative basis. Generalizations of the Fourier transform kernel lead to a number of novel transforms, in particular, special discrete cosine, discrete sine, and real discrete Fourier transforms, which have already found use in a number of applications. The fast algorithms for the real discrete Fourier transform provide a unified approach for the optimal fast computation of all discrete Fourier-related transforms. The short-time Fourier-related transforms are discussed for applications involving nonstationary signals. The one-dimensional transforms discussed are also extended to the two-dimensional transforms     

A VLSI architecture for the real time computation of discrete trigonometric transforms

The Discrete Trigonometric Transforms are defined as a class of transforms. An algorithm for calculating the Discrete Fourier Transform is extended to cover all members of the defined class. A VLSI architecture which provides for real time calculation of these transforms is presented. This architecture provides simple interconnections, identical processing elements and minimal control complexity.     

Computationally efficient digital filters

A method for designing high-performance digital filters using only a relatively small number of shift-and-add operations per signal sample is demonstrated.     

Computationally Secure Oblivious Transfer

We describe new computationally secure protocols of 1-out-of-N oblivious transfer, k-out-of-N oblivious transfer, and oblivious transfer with adaptive queries. The protocols are very efficient compared with solutions based on generic two-party computation or on information-theoretic security. The 1-out-of-N oblivious transfer protocol requires only log N executions of a 1-out-of-2 oblivious transfer protocol. The k-out-of-N protocol is considerably more efficient than k repetitions of 1-out-of-N oblivious transfer, as is the construction for oblivious transfer with adaptive queries. The efficiency of the new oblivious transfer protocols makes them useful for many applications. A direct corollary of the 1-out-of-N oblivious transfer protocol is an efficient transformation of any Private Information Retrieval protocol to a Symmetric PIR protocol.     

A review of the discrete Fourier transform. 2. Non-radixalgorithms, real transforms and noise

For pt.1 see ibid., vol.7, no.4, p.169-77 (1995). Since fast algorithms for the discrete Fourier transform (DFT) were first introduced thirty years ago, they have had a major impact on signal processing and are now a basic part of every electrical engineer's education. However, some of the options, and particularly the recent advances, are not as widely known as they deserve. This article, the second of two which review the fast algorithms for the DFT, looks at algorithms for transforms whose orders are not a power of two. Also discussed are ways of adapting algorithms for purely real data, the problems of fixed-point noise, and implementation options with existing hardware     

Computationally efficient electronic-circuit noise calculations

The interreciprocal adjoint network concept is applied to the computer simulation of electronic-circuit noise performance. The method described is extremely efficient, allowing consideration of an arbitrarily large number of uncorrelated noise sources with less effort than for the original small signal a.c. analysis. Because all noise sources may be considered, no a priori assumption need be made as to which noise sources are dominant in a complicated circuit. The method is illustrated with an operational- amplifier example.     

Computationally Efficient Predictive Robot Control

Conventional linear controllers (PID) are not really suitable for the control of robot manipulators due to the highly nonlinear behavior of the latter. Over the last decades, several control methods have been proposed to circumvent this limitation. This paper presents an approach to the control of manipulators using a computationally-efficient-model-based predictive control scheme. First, a general predictive control law is derived for position tracking and velocity control, taking into account the dynamic model of the robot, the prediction and control horizons, and also the constraints. However, the main contribution of this paper is the derivation of an analytical expression for the optimal control to be applied that does not involve a numerical procedure, as opposed to most predictive control schemes. In the last part of the paper, the effectiveness of the approach for the control of a nonlinear plant is illustrated using a direct-drive pendulum, and then, the approach is validated and compared to a PID controller using an experimental implementation on a 6-DOF cable-driven parallel manipulator.     

The integer transforms analogous to discrete trigonometric transforms

The integer transform (such as the Walsh transform) is the discrete transform that all the entries of the transform matrix are integer. It is much easier to implement because the real number multiplication operations can be avoided, but the performance is usually worse. On the other hand, the noninteger transform, such as the DFT and DCT, has a good performance, but real number multiplication is required. W derive the integer transforms analogous to some popular noninteger transforms. These integer transforms retain most of the performance quality of the original transform, but the implementation is much simpler. Especially, for the two-dimensional (2-D) block transform in image/video, the saving can be huge using integer operations. In 1989, Cham had derived the integer cosine transform. Here, we will derive the integer sine, Hartley, and Fourier transforms. We also introduce the general method to derive the integer transform from some noninteger transform. Besides, the integer transform derived by Cham still requires real number multiplication for the inverse transform. We modify the integer transform introduced by Cham and introduce the complete integer transform. It requires no real number multiplication operation, no matter what the forward or inverse transform. The integer transform we derive would be more efficient than the original transform. For example, for the 8-point DFT and IDFT, there are in total four real numbers and eight fixed-point multiplication operations required, but for the forward and inverse 8-point complete integer Fourier transforms, there are totally 20 fixed-point multiplication operations required. However, for the integer transform, the implementation is simpler, and many of the properties of the original transform are kept.     

p-adic transforms

Two clarifications are made on the uniqueness of representation of rational numbers in a finite segmented p-adic field, and on orthogonality asserted in a recent article on p-adic transforms. One clarification also reveals a slight generalisation on dynamic range. In addition, an extension of this transform to finite-dimensional cases is also given.     

Periodicity transforms

This paper presents a method of detecting periodicities in data that exploits a series of projections onto “periodic subspaces”. The algorithm finds its own set of nonorthogonal basis elements (based on the data), rather than assuming a fixed predetermined basis as in the Fourier, Gabor, and wavelet transforms. A major strength of the approach is that it is linear-in-period rather than linear-in-frequency or linear-in-scale. The algorithm is derived and analyzed, and its output is compared to that of the Fourier transform in a number of examples. One application is the finding and grouping of rhythms in a musical score, another is the separation of periodic waveforms with overlapping spectra, and a third is the finding of patterns in astronomical data. Examples demonstrate both the strengths and weaknesses of the method     

Recursive Gabor filtering

We present a stable, recursive algorithm for the Gabor (1946) filter that achieves-to within a multiplicative constant-the fastest possible implementation. For a signal consisting of N samples, our implementation requires O(N) multiply-and-add (MADD) operations, that is, the number of computations per input sample is constant. Further, the complexity is independent of the values of /spl sigma/, and /spl omega/ in the Gabor kernel, and the coefficients of the recursive equation have a simple, closed-form solution given /spl sigma/ and /spl omega/. Our implementation admits not only a "forward" Gabor filter but an inverse filter that is also O(N) complexity.     

Computationally efficient discrete cosine transform algorithm

An algorithm is developed for evaluating the discrete cosine transform using DFT and polynomial transforms. It is shown to be computationally more efficient than existing algorithms.     

Computationally efficient decoding of LDPC codes

A computationally efficient algorithm for the decoding of low-density parity check codes is introduced. Instead of updating all bit and check nodes at each decoding iteration, the developed algorithm only updates unreliable check and bit nodes. A simple reliability criteria is developed to determine the active bit and check nodes per decoding iteration. Based on the developed technique, significant computation reductions are achieved with very little or no loss in the BER performance of the LDPC codes. The proposed method can be implemented with a slight modification to the sum-product algorithm with negligible additional hardware complexity.     

Message Authentication in Computationally Constrained Environments

RFID and Wireless Sensor Networks exemplify computationally constrained environments, where the compact nature of the components cannot support complex computations or high communication overhead. On the other hand, such components should support security applications such as message integrity, authentication, and time stamping. The latter are efficiently implemented by Hash Message Authentication Codes (HMAC). As clearly stated in the literature, current approved implementations of HMAC require resources that cannot be supported in constrained components. An approach to implement a compact HMAC by the use of stream ciphering is presented in this paper.     

Computationally complete operations on magnetic bubbles

The operations of transfer, generation and annihilation on magnetic bubbles constitute a computationally complete binary algebra, if one of these operations is used conditionally.     

Computationally efficient two-dimensional Capon spectrum analysis

We present a computationally efficient algorithm for computing the 2-D Capon (1969) spectral estimator. The implementation is based on the fact that the 2-D data covariance matrix will have a Toeplitz-block-Toeplitz structure, with the result that the inverse covariance matrix can be expressed in closed form by using a special case of the Gohberg-Heinig (1974) formula that is a function of strictly the forward 2-D prediction matrix polynomials. Furthermore, we present a novel method, based on a 2-D lattice algorithm, to compute the needed forward prediction matrix polynomials and discuss the difference in the so-obtained 2-D spectral estimate as compared with the one obtained by using the prediction matrix polynomials given by the Whittle-Wiggins-Robinson (1963, 1965) algorithm. Numerical simulations illustrate the improved resolution as well as the clear computational gain in comparison to both the well-known classical implementation and the method published by Liu et al.(see IEEE Trans. Aerosp. Electron. Syst., vol.34, p.1314-19, 1998)