VLSI architecture for fast 2D discrete orthonormal wavelet transform

The discrete wavelet transform (DWT) provides a new method for signal/image analysis where high frequency components are studied with finer time resolution and low frequency components with coarser time resolution. It decomposes a signal or an image into localized contributions for multiscale analysis. In this paper, we present a parallel pipelined VLSI array architecture for 2D dyadic separable DWT. The 2D data array is partitioned into non-overlapping groups of rows. All rows in a partition are processed in parallel, and consecutive partitions are pipelined. Moreover, multiple wavelet levels are computed in the same pipeline, and multiple DWT problems can be pipelined also. The whole computation requires a single scan of the image data array. Thus, it is suitable for on-line real-time applications. For anN×N image, anm-level DWT can be computed in time units on a processor costing no more than , whereq is the partition size,p is the length of corresponding 1D DWT filters,C _m andC _a are the costs of a parallel multiplier and a parallel adder respectively, and a time unit is the time for a multiplication and an addition. Forq=N m, the computing time reduces to . When a large number of DWT problems are pipelined, the computing time is about per problem.     

Orthogonal cycle transforms of stochastic matrices

In this paper we investigate new Fourier series with respect to orthonormal families of directed cycles , which occur in the graph of a recurrent stochastic matrixP. Specifically, it is proved thatP may be approximated in a suitable Hilbert space by the Fourier series . This approach provides a proof in terms of Hilbert space of the cycle decomposition formula for finite stochastic matricesP.     

Finite-Memory Systems

Let K be a field, k and n positive integers and let matrices with coefficients in K. For any function

2D grid architectures for the DFT and the 2D DFT

New algorithms for the DFT and the 2-dimensional DFT are presented. The DFT and the 2-dimensional DFT matrices can be expressed as the Kronecker product of DFT matrices of smaller dimension. These algorithms are synthesized by combining the efficient factorization of the Kronecker product of matrices with the highly hardware efficient recursive implementation of the smaller DFT matrices, to yield these algorithms. The architectures of the processors implementing these algorithms consist of 2-dimensional grid of processing elements, have temporal and spatial locality of connections. For computing the DFT of sizeN or for the 2D DFT of sizeN=N ₁ byN ₁, these algorithms require 2N multipliers and adders, take approximately computational steps for computing a transform vector, and take approximately computation steps between the computation of two successive transform vectors.     

Potentials on the hexagonal grid

The aim of this paper is to give an explicit computation for the potential generated by a dipole on a hexagonal grid. Such a computation will be expressed as the Fourier transform of a distribution on the bidimensional torus .     

How to construct constant-round zero-knowledge proof systems for NP

Constant-round zero-knowledge proof systems for every language in are presented, assuming the existence of a collection of claw-free functions. In particular, it follows that such proof systems exist assuming the intractability of either the Discrete Logarithm Problem or the Factoring Problem for Blum integers.     

A Fully Integrated, Low Noise and Low Power BiCMOS Front-end Readout System for Capacitive Detectors

Bipolar transistors are interesting for low noise front-end readout systems when high speed and low power consumption are required. This paper presents a fully integrated, low noise front-end design for the future Large Hadron Collider (LHC) experiments using the radiation hard SOI BiCMOS process. In the present prototype, the input-referred Equivalent Noise Charge (ENC) of 990 electrons (rms) for 12 pF detector capacitance with a shaping time of 25 ns and power consumption of 1.4 mW/channel has been measured. The gain of this front-end is 90 mV/MIP (Minimum Ionisation Particle: 1 fC) with non-linearity of less than 3% and linear input dynamic range is MIP. These results are obtained at room temperature and before irradiation. The measurements after irradiations by high intensity pion beam with an integrated flux of pions/cm² are also presented in this paper.     

BIBO Stability of D-Dimensional Filters

Consider the class of d-dimensional causal filters characterized by a d-variate rational function analytic on the polydisk . The BIBO stability of such filters has been the subject of much research over the past two decades. In this paper we analyze the BIBO stability of such functions and prove necessary and sufficient conditions for BIBO stability of a d-dimensional filter. In particular, we prove if a d-variate filter H(z) analytic on has a Fourier expansion that converges uniformly on the closure of , then H(z) is BIBO stable. This result proves a long standing conjecture set forth by Bose in [3].     

CORDIC-Based Computation of ArcCos

CORDIC-based algorithms to compute cos and are proposed. The implementation requires a standard CORDIC module plus a module to compute the direction of rotation, this being the same hardware required for the extended CORDIC vectoring, recently proposed by the authors [T. Lang and E. Antelo, IEEE Transactions on Computers, vol. 47, no. 7, 1998, pp. 736–749.]. Although these functions can be obtained as a special case of this extended vectoring, the specific algorithm we propose here presents two significant improvements: (1) it uses the same datapath width as the standard CORDIC, even when t has 2n bits (to achieve a granularity of 2^–n for the whole range). In contrast, the extended vectoring unit requires about 2n bits. (2) no repetitions of iterations are needed (the extended vectoring needs some repetitions). The proposed algorithm is compatible with the extended vectoring and, in contrast with previous implementations, the number of iterations and the delay of each iteration are the same as for the conventional CORDIC algorithm.