Nonuniform sampling and antialiasing in image representation

A unified approach to the representation and processing of a class of images which are not bandlimited but belong to the space of locally bandlimited signals is presented. A nonuniform sampling theorem (Clark et al, 1985) for functions belonging to this space is extended, and a class of nonstationary stochastic processes is considered. The space of locally bandlimited signals is shown to be a reproducing-kernel space. A generalized projection theorem can therefore be applied, yielding either a continuous or a discrete projection filter. The former can be used for image conditioning prior to nonuniform sampling, while the latter provides a general tool for image representation by nonuniform sampling schemes. The problem of finding the local bandwidth of a given signal, in order to generate an optimal sampling scheme, is addressed in the context of signal representation in the combined position-frequency space. The stochastic estimation of parameters which characterize the local bandwidth is discussed. Bounds on the error resulting from the utilization of nonexact position-varying signal parameters are derived     

Recovery of Bandlimited Signals in Linear Canonical Transform Domain from Noisy Samples

The linear canonical transform (LCT) has been shown to be a useful and powerful tool for signal processing and optics. Many reconstruction strategies for bandlimited signals in LCT domain have been proposed. However, these reconstruction strategies can work well only if there are no errors associated with the numerical implementation of samples. Unfortunately, this requirement is almost never satisfied in the real world. To the best of the author’s knowledge, the statistical problem of LCTed bandlimited signal recovery in the presence of random noise still remains unresolved. In this paper, the problem of recovery of bandlimited signals in LCT domain from discrete and noisy samples is studied. First, it is shown that the generalized Shannon-type reconstruction scheme for bandlimited signals in LCT domain cannot be directly applied in the presence of noise since it leads to an infinite mean integrated square error. Then an orthogonal and complete set for the class of bandlimited signals in LCT domain is proposed; and further, an oversampled version of the generalized Shannon-type sampling theorem is derived. Based on the oversampling theorem and without adding too much complexity, a reconstruction algorithm for bandlimited signals in LCT domain from discrete and noisy observations is set up. Moreover, the convergence of the proposed reconstruction scheme is also proved. Finally, numerical results and potential applications of the proposed reconstruction algorithm are given.     

Sampling of Bandlimited Signals in Fractional Fourier Transform Domain

Fractional Fourier transformed bandlimited signals are shown to form a reproducing kernel Hilbert space. Basic properties of the kernel function are applied to the study of a sampling problem in the fractional Fourier transform (FRFT) domain. An orthogonal sampling basis for the class of bandlimited signals in the FRFT domain is then given. A nonuniform sampling theorem for bandlimited signals in the FRFT domain is also presented. Numerical experiments are given to demonstrate the effectiveness of the proposed nonuniform sampling theorem.     

Sampling and Reconstruction of Sparse Signals in Fractional Fourier Domain

Sampling theory for continuous time signals which have a bandlimited representation in fractional Fourier transform (FrFT) domain-a transformation which generalizes the conventional Fourier transform-has blossomed in the recent past. The mechanistic principles behind Shannon's sampling theorem for fractional bandlimited (or fractional Fourier bandlimited) signals are the same as for the Fourier domain case i.e. sampling (and reconstruction) in FrFT domain can be seen as an orthogonal projection of a signal onto a subspace of fractional bandlimited signals. As neat as this extension of Shannon's framework is, it inherits the same fundamental limitation that is prevalent in the Fourier regime-what happens if the signals have singularities in the time domain (or the signal has a nonbandlimited spectrum)? In this paper, we propose a uniform sampling and reconstruction scheme for a class of signals which are nonbandlimited in FrFT sense. Specifically, we assume that samples of a smoothed version of a periodic stream of Diracs (which is sparse in time-domain) are accessible. In its parametric form, this signal has a finite number of degrees of freedom per unit time. Based on the representation of this signal in FrFT domain, we derive conditions under which exact recovery of parameters of the signal is possible. Knowledge of these parameters leads to exact reconstruction of the original signal.     

Concerning the Recovery of a Bandlimited Signal or Its Spectrum from a Finite Segment

The relationship between the iterative techniques of Sandberg and Papoulis is clarified. The conditions of Sandberg's theorem are not satisfied in general when the problem is that of extrapolating a bandlimited signal outside of a known segment (a problem that is "illposed"). For an interesting special case, the iteration may be applied and the signal recovered exactly.     

Quasi-bandlimited properties of Radon transforms and theirimplications for increasing angular sampling densities

The n-dimensional (n-D) radon transform, which forms the mathematical basis for a broad variety of tomographic imaging applications, can be viewed as an n-D function in n-D sinogram space. Accurate reconstruction of continuous or discrete tomographic images requires full knowledge of the Radon transform in the corresponding n-D sinogram space. In practice, however, one can have only a finite set of discrete samples of the Radon transform in the sinogram space. One often derives the desired full knowledge of the Radon transform from its discrete samples by invoking various interpolation algorithms. According to the Wittaker-Shannon sampling theorem, a necessary condition for a full and unique recovery of the Radon transform from its discrete samples is that the Radon transform itself be bandlimited. Therefore, it is necessary to analyze the bandlimited properties of the Radon transform. In this work, the authors analyze explicitly the bandlimited properties of the Radon transform and show that the Radon transform is mathematically quasi-bandlimited [or essentially bandlimited] in two quantitative senses and can essentially be treated as bandlimited in practice. The quasi-bandlimited properties can be used for increasing the angular sampling density of the Radon transform     

On completeness and multi-channel sampling

A bandlimited input x is applied as a common input to m linear time-invariant filters (channels) which are ‘independent’ in a certain sense. We investigate, from a unified point of view using the concept of completeness, the problem of uniquely reconstructing the input x for all time values from samples of the m outputs, each output being sampled at the uniform rate of σ/gqm samples/second, where σ is the positive frequency bandwidth of the input signal.For the lowpass input case and independent channels, perfect reconstruction is always possible; similarly for the case of a bandpass input and an even number of channels, recovery of the input can also be accomplished at a rate of σ/mπ samples/second. However, for an odd number m of channels and a bandpass input, it is shown that the rate σ/mπ samples/second at the outputs no longer suffices to determine the input uniquely unless 2ω₀m/σ is an odd integer, a constraint on the relation between the center frequency of the band, ω₀, and the bandwidth σ. To obtain a sampling theorem when the number of channels is odd and in the absence of such a positioning constraint, a higher sampling rate per channel must be employed.In those cases which permit a unique determination of the input from samples of the output channels, it is shown that a linear scheme involving m linear time-invariant post-filters can be used to effect the input reconstruction.     

一种基于FIR滤波器的非均匀小波周期采样方法

针对Shannon采样定理只能处理带限信号和要求采样率不低于Nyquist率的缺陷,研究了小波空间中的一种非均匀周期采样理论,给出了定理成立的条件及其突破Nyquist率限制的理论依据,将采样理论扩展到了非带限信号领域。对于紧支尺度函数张成的子波空间中的任意信号,可以利用非均匀周期采样所得的样本以及正交镜像滤波器理论求出其小波系数的估计值,进而得到信号的重建表达式。该方法在信号重建的过程中用到的全是有限冲击响应滤波器,避免了无限冲击响应滤波器的出现,降低了实际物理实现的难度。计算机仿真结果表明该方法是切实有效的,信号重建的相对误差小于1%。     

Sampling, data transmission, and the Nyquist rate

The sampling theorem for bandlimited signals of finite energy can be interpreted in two ways, associated with the names of Nyquist and Shannon. 1) Every signal of finite energy and bandwidth W Hz may be completely recovered, in a simple way, from a knowledge of its samples taken at the rate of 2W per second (Nyquist rate). Moreover, the recovery is stable, in the sense that a small error in reading sample values produces only a correspondingly small error in the recovered signal. 2) Every square-summable sequence of numbers may be transmitted at the rate of 2W per second over an ideal channel of bandwidth W Hz, by being represented as the samples of an easily constructed band-limited signal of finite energy. The practical importance of these results, together with the restrictions implicit in the sampling theorem, make it natural to ask whether the above rates cannot be improved, by passing to differently chosen sampling instants, or to bandpass or multiband (rather than bandlimited) signals, or to more elaborate computations. In this paper we draw a distinction between reconstructing a signal from its samples, and doing so in a stable way, and we argue that only stable sampling is meaningful in practice. We then prove that: 1) stable sampling cannot be performed at a rate lower than the Nyquist, 2) data cannot be transmitted as samples at a rate higher than the Nyquist, regardless of the location of sampling instants, the nature of the set of frequencies which the signals occupy, or the method of construction. These conclusions apply not merely to finite-energy, but also to bounded, signals.     

Peak value estimation of bandlimited signals from their samples, noise enhancement, and a local characterization in the neighborhood of an extremum

The paper addresses the problem of estimating the peak value of bandlimited signals from their samples with and without oversampling. This problem has significant relevance to orthogonal frequency-division multiplexing (OFDM) signal processing and system design. In particular, an upper bound on the peak value is established given the peak value of the samples and the oversampling rate. Moreover, it is shown that the bounds are sharp for all practical rates by constructing bandlimited signals taking on this bound. The proof also provides a local characterization of bandlimited signals in the neighborhood of an extremum. A different analysis examines the effect of small errors in the samples. It is shown that oversampling can provide robust recovery in the sense that small errors in the samples lead to small errors in the reconstructed signal. Again, an upper bound is derived relating the peak error in the samples and the peak error in the signals. Furthermore, both problems are shown to be coupled and put in a unifying context. The bounds are compared and applied to problems concerning OFDM.     

A variational method for designing adaptive bandlimited wavelets

This paper proposes a new method of estimating an orthogonal bounded spectrum wavelet from a given signal. The method is based on minimizing the distance of the wavelet and the given signal in the sense of the metric of the L ² space. In this method, the amplitude and phase of the mother wavelet are optimized simultaneously. The Lagrange multipliers technique is applied to consider the constraints due to the bounded spectrum wavelet and orthogonality conditions. The variational method reduced the optimal matching problem to the solution of a set of functional equations for the amplitude and phase of the optimal-matched bandlimited wavelet spectrum. Continuous functional equations are written with respect to Fourier coefficients of phase of transfer function of the quadrate low-pass filter at the sampled frequencies, and asset of discrete algebraic equations allows us to design the wavelet directly from the signal of interest. To demonstrate the performance of the presented method in this paper, it is employed to determine the matched wavelets of some specified signals.     

A note on the PQ theorem and the extrapolation of signals

The problem of determining a bandlimited function from its values on a finite interval is ill-conditioned in the sense that although the pertinent inverse map exists, it is discontinuous at every point. Whenever certain closely related general problems are well conditioned in the sense that the inverse operator is continuous, they can be solved using a special case of a known algorithm. In particular, attention is directed to the relation between the PQ theorem, its Hilbert space projection-operator setting, and later work     

Sampling of bandlimited signals in the linear canonical transform domain

The linear canonical transform (LCT) has been shown to be a powerful tool for optics and signal processing. This paper investigates the sampling of bandlimited signals in LCT domain. First, we propose the linear canonical series (LCS) based on the LCT, which is a generalized pattern of Fourier series. Moreover, the LCS inherits all the nice properties from the LCT. Especially, the Parseval’s relation is presented for the LCS, which is used to derive the sampling theorem of LCT. Then, utilizing the generalized form of Parseval’s relation for the complex LCS, we obtain the sampling expansion for bandlimited signals in LCT domain. The advantage of this reconstruction method is that the sampling expansion can be deduced directly not based on the Shannon theorem.     

Lower bounds on memory requirements for statically scheduled DSP programs

This paper presents novel techniques for computing the minimum number of memory locations in statically scheduled digital signal processing (DSP) programs. Two related problems are considered. In the first problem, we compute the minimum number of memory locations required for a scheduled program assuming that no circuit transformations (such as pipelining and retiming) are to be performed after scheduling. For this problem, we consider memory minimization for theoperation-constrained, processor-constrained andunconstrained memory models which represent various restrictions on how data can be allocated to memory. Then we consider the second problem, where memory minimization for a scheduled program is considered simultaneously with retiming using a variation of the retiming problem referred to as theminimum physical storage location (MPSL) retiming. While both problems consider memory minimization for scheduled programs, the second problem minimizes memory using retiming whereas the first problem performs no retiming. The scheduling results obtained from the MARS design system are used to compare memory requirements in the context of both of these problems. Our experiments show that MARS performs an optimal retiming for the schedule it generates. These memory requirements are then compared with an integer linear programming solution to the scheduling problem which is optimal under the unconstrained memory model. It is concluded that the schedule obtained by the MARS system achieves optimality or near-optimality with respect to register minimization.     

Fitting a bandlimited signal to given points

One of the fundamental problems in communications is the transmission of a signal through a bandlimited channel. It should, therefore, be of great interest to find a general method of transmitting an arbitrarily close approximation to any finite signal through a channel which is arbitrarily bandlimited. The present paper develops such a method and evaluates the cost in time and energy to accomplish this feat. The problem of fitting an arbitrarily bandlimited signal to a finite number of arbitrary points is solved, and the minimum energy signal, fitting the points and having a spectrum confined to the given pass band, is found. The behavior of this signal, with shrinking bandwidth, is investigated.     

Resolution limits in signal recovery

Resolution analysis for the problem of signal recovery from finitely many linear measurements is the subject of this paper. The classical Rayleigh limit serves only as a lower bound on resolution since it does not assume any recovery strategy and is based only on observed data. We show that details finer than the Rayleigh limit can be recovered by simple linear processing that incorporates prior information. We first define a measure of resolution based on allowable levels of error that is more appropriate for current signal recovery strategies than the Rayleigh definition. In the practical situation in which only finitely many noisy observations are available, we have to restrict the class of signals in order to make the resolution measure meaningful. We consider the set of bandlimited and essentially timelimited signals since it describes most signals encountered in practice. For this set, we show how to precompute resolution limits from knowledge of measurement functionals, signal-to-noise ratio, passband, energy concentration regions, energy concentration factor, and a prescribed level of error tolerance. In the process, we also derive an algorithm for high-resolution signal recovery. We illustrate the results with examples in one and two dimensions     

Perfect recovery and sensitivity analysis of time encoded bandlimited signals

A time encoding machine is a real-time asynchronous mechanism for encoding amplitude information into a time sequence. We investigate the operating characteristics of a machine consisting of a feedback loop containing an adder, a linear filter, and a noninverting Schmitt trigger. We show that the amplitude information of a bandlimited signal can be perfectly recovered if the difference between any two consecutive values of the time sequence is bounded by the inverse of the Nyquist rate. We also show how to build a nonlinear inverse time decoding machine (TDM) that perfectly recovers the amplitude information from the time sequence. We demonstrate the close relationship between the recovery algorithms for time encoding and irregular sampling. We also show the close relationship between time encoding and a number of nonlinear modulation schemes including FM and asynchronous sigma-delta modulation. We analyze the sensitivity of the time encoding recovery algorithm and demonstrate how to construct a TDM that perfectly recovers the amplitude information from the time sequence and is trigger parameter insensitive. We derive bounds on the error in signal recovery introduced by the quantization of the time sequence. We compare these with the recovery error introduced by the quantization of the amplitude of the bandlimited signal when irregular sampling is employed. Under Nyquist-type rate conditions, quantization of a bandlimited signal in the time and amplitude domains are shown to be largely equivalent methods of information representation.     

分数阶傅里叶变换域上带通信号的采样定理

傅里叶变换和采样定理是信号处理领域的两大基本问题,采样定理研究了傅里叶变换域上带限信号的采样和重构理论.分数阶傅里叶变换(FRFT)是傅里叶变换的一种推广,与之相应的采样理论目前还不十分完备,所以有必要从FRFT域上重新研究采样定理.本文首先得到了均匀冲激串采样信号的FRFT,然后在此基础上导出了FRFT域上带通信号和低通信号的采样定理和重构公式.这些结果是经典理论的推广,将丰富分数阶傅里叶变换的理论体系.     

Sampling random signals in a fractional Fourier domain

In this paper, we consider the sampling and reconstruction schemes for random signals in the fractional Fourier domain. We define the bandlimited random signal in the fractional Fourier domain, and then propose the uniform sampling and multi-channel sampling theorems for the bandlimited random signal in the fractional Fourier domain by analyzing statistical properties of the input and the output signals for the fractional Fourier filters. Our formulation and results are general and include derivative sampling and periodic nonuniform sampling in the fractional Fourier domain for random signals as special cases.     

Rate-optimal schedule for multi-rate DSP computations

In this paper we present a novel framework ofmulti-rate scheduling of signal processing programs represented by regular stream flow graphs (RSFGs). The main contribution of this paper is translating the scheduling problem of RSFGs into an equivalent problem in the domain of Karp-Miller computation graphs. A distinct feature of our scheduling framework—called themulti-rate software pipelining—is to allow maximum overlapping of operations from successive iterations, subject only to precedence constraints caused by data dependences. p ]We demonstrate that the scheduling of regular stream flow graphs can be formulated as a mathematical problem by capturing data dependences between two actors as a precedence relation between the firing of these actors. Using linear schedules, the problem is further translated into a linear program formulation. An efficient solution for the linear programming problem is obtained by first constructing what is called theprecedence graph. A polynomial-time solution is obtained by observing that the optimal computation rate is theminimum cost-to-time ratio cycle (MCTRC) in the precedence graph and using the well-established solution methods for the MCTRC problem. Finally, to minimize the buffer requirement for the obtained rate-optimal schedule, a graph coloring method based on thecyclic interval graph representation has been proposed.