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.     

On the Scalability of 2-D Discrete Wavelet Transform Algorithms

The ability of a parallel algorithm to make efficient use of increasing computational resources is known as its scalability. In this paper, we develop four parallel algorithms for the 2-dimensional Discrete Wavelet Transform algorithm (2-D DWT), and derive their scalability properties on Mesh and Hypercube interconnection networks. We consider two versions of the 2-D DWT algorithm, known as the Standard (S) and Non-standard (NS) forms, mapped onto P processors under two data partitioning schemes, namely checkerboard (CP) and stripped (SP) partitioning. The two checkerboard partitioned algorithms (Non-standard form, NS-CP), and as (Standard form, S-CP); while on the store-and-forward-routed (SF-routed) Mesh and Hypercube they are scalable as (NS-CP), and as (S-CP), respectively, where M ² is the number of elements in the input matrix, and (0,1) is a parameter relating M to the number of desired octaves J as . On the CT-routed Hypercube, scalability of the NS-form algorithms shows similar behavior as on the CT-routed Mesh. The Standard form algorithm with stripped partitioning (S-SP) is scalable on the CT-routed Hypercube as M ² = (P ²), and it is unscalable on the CT-routed Mesh. Although asymptotically the stripped partitioned algorithm S-SP on the CT-routed Hypercube would appear to be inferior to its checkerboard counterpart S-CP, detailed analysis based on the proportionality constants of the isoefficiency function shows that S-SP is actually more efficient than S-CP over a realistic range of machine and problem sizes. A milder form of this result holds on the CT- and SF-routed Mesh, where S-SP would, asymptotically, appear to be altogether unscalable.     

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 .     

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].     

Finite-Memory Systems

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

Planar defects and double-domain epitaxy in epitaxial YSi<Subscript>2−x</Subscript> and ErSi<Subscript>2−x</Subscript> thin films on Si substrates

Interfacial reactions of Y and Er thin films on both (111)Si and (001)Si have been studied by transmission electron microscopy (TEM). Epitaxial rare-earth (RE) silicide films were grown on (111)Si. Planar defects, identified to be stacking faults on planes with 1/6 displacement vectors, were formed as a result of the coalescence of epitaxial silicide islands. Double-domain epitaxy was found to form in RE silicides on (001)Si samples resulting from a large lattice mismatch along one direction and symmetry conditions at the silicide/(001)Si interfaces. The orientation relationships are [0001]RESi_2−x// Si, RESi_2−x//(001)Si and [0001]RESi_2−x/ Si, RESi_2−x//(001)Si. The density of staking faults in (111) samples and the domain size in (001) samples were found to decrease and increase with annealing temperature, respectively.     

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.     

Linear phase FIR approximation of magnitude response |1/ω| for maximal flatness at an arbitrary frequency ω0, 0<ω0<π*

In many signal processing situations, the desired (ideal) magnitude response of the filter is a rational function: (a digital integrator). The requirements of a linear phase response and guaranteed stable performance limit the design to a finite impulse response (FIR) structure. In many applications we require the FIR filter to yield a highly accurate magnitude response for a narrow band of frequencies with maximal flatness at an arbitrary frequency ₀ in the spectrum (0, ). No techniques for meeting such requirements with respect to approximation of are known in the literature. This paper suggests a design by which the linear phase magnitude response can be approximated by an FIR configuration giving a maximally flat (in the Butterworth sense) response at an arbitrary frequency ₀, 0<₀<^*. A technique to compute exact weights for the design has also been given.     

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.     

Effect of off-orientation of seed crystal on silicon carbide (SiC) single-crystal growth on the (11 $$\bar 2$$ 0) surface0) surface

The effect of off-orientation growth has been investigated in terms of stacking fault formation during physical vapor transport (PVT) growth of silicon carbide (SiC) single crystals on the (11 0) seed crystal surface. Occurrence of stacking fault formation is largely dependent on the direction of off-orientation, and basal plane stacking fault density is significantly reduced by growing the crystals on a (11 0) seed crystal off-oriented toward 〈0001〉. The density of the basal plane stacking faults rapidly decreases from 100–150 cm⁻¹ to ∼10 cm⁻¹ as the degree of off-orientation is increased from 0 to 10 deg. The results are interpreted in the framework of microscopic facet formation during PVT growth, and the introduction of off-orientation of seed crystal is assumed to prevent (01 0) and (10 0) microfacet formation on the (11 0) growing surface through modification of the surface growth kinetics and to suppress the stacking fault formation. An erratum to this article is available at .     

A Small Area Charge Sensitive Readout Chain with a Dual Mode of Operation

A charge sensitive readout chain has been designed and fabricated in acommercially available 0.8 m CMOS technology. The readout chain is optimizedfor pixel detectors measuring soft X-ray energies up to 20 KeV. In the first modean analog signal proportional to input charge is generated and processed in realtime. In the second mode a peak-and-hold operation is enabled and therelevant signal is processed in later time. This dual mode of operation iscontrolled by an external digital signal. The readout chain consists of a chargeamplifier, a shaper, an operational amplifier which can either operate as avoltage amplifier or a peak detector and an output buffer. Its area is . The gain at the shaper output is 378 mv/fC, theENC is 16 rms at 160 nsec shaping time. The overall gainis 557 mV/fC, the ENC is rms with 240 nsec peaking timeand 1.4 sec recovery time. The overall power dissipation is 1.5 mWatt with aload capacitance of 25 pF.     

A Symbolic Circuit Analysis-Oriented Algorithm for Finding a Common Tree of the Current and Voltage Graphs

A fundamental problem of symbolic analysis of electric networks when using the signal-flow (SFG) graph method is to find the common tree of the current and voltage graph ( and , respectively). In this paper we introduce a novel method in order to determine a common tree of both graphs, which may be used to obtain the symbolic network transfer function when carrying out the small-signal analysis of linear(ised) circuits.     

A kinetic study of structured surface relief patterning of GaP (\bar 1\bar 1\bar 1)

Orientation dependent etching of photolithographically patterned GaP was investigated using solutions of HCl:CH₃COOH:H₂O₂. The pattern was prepared using standard ultraviolet lithography and was a two-dimensional grid with an 18 μm repeat, consisting of 15 μm squares separated by 3 μm spaces. The mask sides were aligned along the and directions. Under appropriate etching conditions, high quality arrays of pyramids were prepared. These pyramids were defined by , and facets. It was shown that the etching process depended on the degree of solution aging after initial mixing. For a freshly prepared solution, the etching rate showed an inverse dependence on time. For short etching times (below 5 min), an intermediate etching profile was followed, while for long times (greater than 5 min) etching was kinetically controlled. We demonstrated that controlled etching at extremely low rates (0.1–0.5 μm/min) is feasible with this new approach.     

Use of TCP Decoupling in Improving TCP Performance over Wireless Networks

We propose using the TCP decoupling approach to improve a TCP connection's goodput over wireless networks. The performance improvement can be analytically shown to be proportional to , where MTU is the maximum transmission unit of participating wireless links and HP_Sz is the size of a packet containing only a TCP/IP header. For example, on a WaveLAN [32] wireless network, where MTU is 1500 bytes and HP_Sz is 40 bytes, the achieved goodput improvement is about 350%. We present experimental results demonstrating that TCP decoupling outperforms TCP reno and TCP SACK. These results confirm the analysis of performance improvement.     

Simulation of continuous sample paths of random fields using trigonometric series

The problem of simulating random fields on a digital computer using random trigonometric series is considered. Convergence in distribution of the sample paths as continuous functions is demonstrated when the structure function is bounded by . Methods for simulating homogeneous and homogeneous increment random fields are presented. As an example, random index of refraction fluctuations are simulated using both a fractal model and a homogeneous random field model.     

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.     

Can One Control the Vibrations of a Drum?

This paper considers the problem of constructing feedback stabilizing controllers for the wave operator on ⁿ (more generally AR systems determined by a hyperbolic operator). In order to accomplish this, it must first clarify the notion of an input-output structure on a distributed system, as well as what it means to interconnect two such systems. Both these notions are shown to be consequences of a structure which generalizes the standard causal structure of lumped systems determined by the flow of time. Given this apparatus, the paper then constructs feedback controllers which stabilize the wave equation along directions given by a proper cone in ⁿ.     

Identification of prismatic slip bands in 4H SiC boules grown by physical vapor transport

Transmission electron microscopy (TEM) and KOH etching have been used to study the dislocation structure of 4H SiC wafers grown by physical vapor transport. A new type of threading dislocation arrays was observed. Rows of etch pits corresponding to dislocation arrays were observed in vicinity of micropipes, misoriented grains and polytypic inclusions at the periphery of the boules and extended along the directions. Plan view conventional and high resolution TEM showed that the arrays consisted of dislocations threading along the c-axis with Burgers vectors having edge components of the a/3 type. The Burgers vectors were parallel to the corresponding arrays. The dislocation arrays were interpreted as slip bands formed by dislocation glide in the prismatic slip system of hexagonal SiC during post-growth cooling.