Using an efficient way to compute the product of a Toeplitz matrix and a vector, a sub-quadratic arithmetic complexity scheme for field multiplication over binary extension fields has recently been proposed by Fan and Hasan. The scheme has been developed using a shifted polynomial basis for the representation of the field elements and has been stated to be applicable to the conventional polynomial basis, although with an increased gate delay for some field defining polynomials. The conventional polynomial basis is widely used in practice and is part of different recommendations and standards for cryptographic applications. In this article, we give additional details of the sub-quadratic complexity algorithm for the case of the polynomial basis by presenting efficient transformation matrices for a class of low weight field defining polynomials, namely trinomials.

The LLL algorithm is widely used to solve the integer least squares problems that arise in many engieering applications. As most practitioners did not understand how the LLL algorithm works, they avoided the issue by referring to the method as an integer Gram Schmidt approach (without explaining what they mean by this term). Luk and Tracy¹ were first to describe the behavior of the LLL algorithm, and they presented a new numerical implementation that should be more robust than the original LLL scheme. In this paper, we compare the numerical properties of the two different LLL implementations.

We consider the problem of recovering signals from noisy indirect observations under the additional a priori information that the signal is believed to be slowly varying except at an unknown number of points where it may have discontinuities of unknown size. The model problem is a linear deconvolution problem. To take advantage of the qualitative prior information available, we use a non-stationary Markov model with the variance of the innovation process also unknown, and apply Bayesian techniques to estimate both the signal and the prior variance. We propose a fast iterative method for computing a MAP estimates and we show that, with a rather standard choices of the hyperpriors, the algorithm produces the fixed point iterative solutions of the total variation and of the Perona-Malik regularization methods. We also demonstrate that, unlike the non-statistical estimation methods, the Bayesian approach leads to a very natural reliability assessment of edge detection by a Markov Chain Monte Carlo (MCMC) based analysis of the posterior.

Recently, spectral information is introduced into face recognition applications to improve the detection performance for different conditions. Besides the changes in scale, orientation, and rotation of facial images, expression, occlusion and lighting conditions change the overall appearance of faces and recognition results. To eliminate these difficulties, we introduced a new face recognition technique by using the spectral signature of facial tissues. Unlike alternate algorithms, the proposed algorithm classifies the hyperspectral imagery corresponding to each face into clusters to automatically recognize the desired face and to eliminate the user intervention in the data set. The K-means clustering algorithm is employed to accomplish the clustering and then Mahalanobis distance is computed between the clusters to identify the closest cluster in the data with respect to the reference cluster. By identifying a cluster in the data, the face that contains that cluster is identified by the proposed algorithm. Test results using real life hyperspectral imagery shows the effectiveness of the proposed algorithm.

We are presenting a new method for super resolution tracking of frequency modulated sinusoids in white noise. The method is specifically designed to handle the rapid transient problem, i.e. the problem of tracking a continuous, rapidly changing instantaneous frequency contour. The proposed method employs two components: 1) an adaptive generalized scale transform ^1,2 which applies a localized change of time-frequency coordinates within the given signal, and 2) an estimation of signal parameters by rotational invariance techniques3 (ESPRIT). With experiments we have shown that the proposed method provides a significantly higher estimation accuracy than conventional methods.³ With an optimal choice of transform parameters the estimation error can be reduced dramatically. Error reductions of over 40% have been observed.

We formulate in a simple fashion the concept of invariance for a linear system. We show that one must define what we call an "associated Hermitian operator" which commutes with the system function. We show that it is this Hermitian operator that defines the invariance and also determines the appropriate transform and other connections between input and output relations.

The conventional cross-ambiguity function (CAF) process assumes that the transmitted signal is a sinusoid having slowly varying complex modulation, and models a received signal as a delayed version of the transmitted signal, doppler shifted by the dominant frequency. For wide-band transmitted signals, it is more accurate to model a received signal as a time-scaled version of the transmitted signal, combined with a time delay, and wide-band cross-ambiguity models are well-known. We provide derivations of time-dependent wide-band cross-ambiguity functions appropriate for estimating radar target range and velocity, and time-difference of arrival (TDOA) and differential receiver velocity (DV) for geolocation. We demonstrate through simulations that for wide-band transmission, these scale CAF (SCAF) models are signficantly more accurate than CAF for estimating target range and velocity, TDOA and DV. In these applications, it is critical that the SCAF surface be evaluated in real-time, and we provide a method for fast computation of the scale correlation in SCAF, using only the discrete Fourier transform (DFT). SCAF estimates of delay and scale are computed on a discrete lattice, which may not provide sufficient resolution. To address this issue we further demonstrate simple methods, based on the DFT and phase differentiation of the time-dependent SCAF surface, by which super resolution of delay and scale, may be achieved.

In the basic correlation process a sequence of time-lag-indexed correlation coefficients are computed as the inner or dot product of segments of two signals. The time-lag(s) for which the magnitude of the correlation coefficient sequence is maximized is the estimated relative time delay of the two signals. For discrete sampled signals, the delay estimated in this manner is quantized with the same relative accuracy as the clock used in sampling the signals. In addition, the correlation coefficients are real if the input signals are real. There have been many methods proposed to estimate signal delay to more accuracy than the sample interval of the digitizer clock, with some success. These methods include interpolation of the correlation coefficients, estimation of the signal delay from the group delay function, and beam forming techniques, such as the MUSIC algorithm. For spectral estimation, techniques based on phase differentiation have been popular, but these techniques have apparently not been applied to the correlation problem . We propose a phase based delay estimation method (PBDEM) based on the phase of the correlation function that provides a significant improvement of the accuracy of time delay estimation. In the process, the standard correlation function is first calculated. A time lag error function is then calculated from the correlation phase and is used to interpolate the correlation function. The signal delay is shown to be accurately estimated as the zero crossing of the correlation phase near the index of the peak correlation magnitude. This process is nearly as fast as the conventional correlation function on which it is based. For real valued signals, a simple modification is provided, which results in the same correlation accuracy as is obtained for complex valued signals.

We discuss the application of time-frequency analysis to biomechanical-type signals, and in particular to signals that would be encountered in the study of rotation rates of bicycle pedaling. We simulate a number of such signals and study how well they are represented by various time-frequency methods. We show that time-frequency representations track very well the instantaneous frequency even when there are very fast changes. In addition, we do a correlation analysis between time-series whose instantaneous frequency is changing and show that the traditional correlation coeficient is insuffcient to characterize the correlations. We instead show that the correlation coeficient should be evaluated directly from the instantaneous frequencies of the time series, which can be easily estimated from their time-frequency distributions.

Given the moments of a time-frequency distribution, one can, in principle, construct the characteristic function from which one then obtains the distribution by Fourier transformation. However, often one can not find a closed form for the characteristic function and hence one can not obtain the distribution in a direct manner. We formulate the problem of constructing time-frequency representations from moments without first constructing the characteristic function. Our method is based on expanding the distribution in terms of a complete set of functions where the expansion coeficients are dependent directly on the moments. We apply the method to a case where the even moments are manifestly positive which is a necessary condition for obtaining a proper time-frequency representation.

Random fluctuations in the index of refraction, caused by differential heating and cooling of the atmosphere, can severely limit the quality of ground-based observations of space objects. Techniques such as adaptive optics can help compensate for the deleterious effects that turbulence has on the images by deforming the telescope mirror and thus correcting the wave-front. However, when imaging through strong turbulence such techniques may not adequately correct the wave-front. In such cases blind restoration techniques - which estimate both the atmospheric turbulence characterized by the atmospheric point-spread-function and the object that is being observed - must be used. We demonstrate high quality blind restorations of object scenes, obtained when observing through strong turbulence, by using a sequence of images obtained simultaneously at different wavelengths and prior information on the distribution of the sources of regions of low spectral power in the data.

This paper utilizes the methodology of SAR2 algorithm, a two dimensional variant of the ω-k algorithm, to refocus out-of-focus images. Refocusing of images may be necessary in machine vision as a preprocessing step before edge detection or image segmentation in the imaging and manipulation of 3D objects. The SAR2 algorithm generates a complex amplitude distribution and the corresponding point spread function in a manner similar to Fraunhofer diffraction distribution model and its point spread function as seen in Fourier optics. The matched filter utilized in the SAR2 algorithm has a focus-in-altitude interpretation and may be varied to increase or decrease the radius of out-of-focus blur associated with a particular point spread function of scatterers of various heights. This paper demonstrates focusing of a line object L={1 : x=y;-≤x≤63; -64≤y≤63}. Although a rectangular aperture is used in the refocusing process, other apertures may also be used such as circular or Gaussian.

Many applications generate digital image sequences using a lens system, a light-transducing pixel array, and sample-and-hold A/D electronics. Non-uniformity Correction (NUC) is an image processing operation that is often required in such systems. The NUC operation subtracts the background from a temporally evolving image on a pixel-by-pixel basis. Background estimation must be robust against image features, electronic glitches, and sudden changes in background. The NUC is often applied in conjunction with a mechanical image dithering that enables separation of the image from the static additive background. In real-time applications with large pixe-count focal planes, the NUC must process large data bandwidths. The NUC algorithm must be operationally efficient to process data in real time. This paper examines a number of NUC algorithms. It defines a set of performance metrics and evaluates algorithm performance in terms of trades between these metrics and processing cost. It provides a guide for selecting an appropriate NUC algorithm based on operating conditions and available compute resources.

We describe a surface compression technique to lossily compress elevation datasets. Our approach first approximates the uncompressed terrain using an over-determined system of linear equations based on the Laplacian partial differential equation. Then the approximation is refined with respect to the uncompressed terrain using an error metric. These two steps work alternately until we find an approximation that is good enough. We then further compress the result to achieve a better overall compression ratio. We present experiments and measurements using different metrics and our method gives convincing results.

We examine a smugglers and border guards scenario. We place observers on a terrain so as to optimize their visible coverage area. Then we compute a path that a smuggler would take so as to avoid detection, while also minimizing the path length. We also examine how our results are affected by using a lossy representation of the terrain instead. We propose three new application-specific error metrics for evaluating terrain compression. Our target terrain applications are the optimal placement of observers on a landscape and the navigation through the terrain by smugglers. Instead of using standard metrics such as average or maximum elevation error, we seek to optimize our compression on the specific real-world application of smugglers and border guards.

In this paper, we consider the use of a seismic sensor array for the localization and tracking of a wideband moving source. The proposed solution consists of two steps: source Direction-Of-Arrival (DOA) estimation and localization via DOA estimates. Three DOA estimation methods are considered. The Covariance Matrix Analysis and the Surface Wave Analysis are previously published DOA estimation algorithms shown to be effective in the localization of a stationary wideband source. This paper investigates their performance on moving wideband sources. A novel DOA estimation algorithm, the Modified Kirlin's Method was also developed for the localization of a moving source. The DOAs estimated by these algorithms are combined using a least-squares optimization for source localization. The application of these algorithms to real-life data show the effectiveness of both the Surface Wave Analysis and the Modified Kirlin's Method in locating and tracking a wideband moving source.

The focus of most direction-of-arrival (DOA) estimation problems has been based mainly on a two-dimensional (2D) scenario where we only need to estimate the azimuth angle. But in various practical situations we have to deal with a three-dimensional scenario. The importance of being able to estimate both azimuth and elevation angles with high accuracy and low complexity is of interest. We present the theoretical and the practical issues of DOA estimation using the Approximate-Maximum-Likelihood (AML) algorithm in a 3D scenario. We show that the performance of the proposed 3D AML algorithm converges to the Cramer-Rao Bound. We use the concept of an isotropic array to reduce the complexity of the proposed algorithm by advocating a decoupled 3D version. We also explore a modified version of the decoupled 3D AML algorithm which can be used for DOA estimation with non-isotropic arrays. Various numerical results are presented. We use two acoustic arrays each consisting of 8 microphones to do some field measurements. The processing of the measured data from the acoustic arrays for different azimuth and elevation angles confirms the effectiveness of the proposed methods.

Due to the broadcast and error prone nature of wireless medium, novel routing mechanisms based on receiver contention have been proposed recently. The intuition of this strategy is, transmitters make routing decisions based on contentions of nodes that have successful reception. A remarkable advantage of receiver contention is the long average advancement of transmissions. To the best our knowledge, existing works utilizing receiver contention schemes are all based on a common assumption. That is, feedback packets sent by contending nodes are all destined to the transmitters. However, probability of reception is a function of distance. The longer the distance is, the lower the reception probability will be⁵. According to this relation, we argue that transmitters may not be the best nodes to taking care of contention packets. In this paper, we consider uniformly distributed sensor networks, and propose the optimal locations, in terms of maximizing the expected advancement of each transmission, to place nodes which are responsible for handling feedback packets. We call these nodes feedback handlers. Based on the simulation results, placing the feedback handlers on the optimal locations can raise expected advancement up to about 30 percent, comparing to existing works.

We consider information retrieval in a wireless sensor network deployed to monitor a spatially correlated random filed. The measured data are sent to an access point through multi-hop transmissions. We address the joint design of sensor scheduling and information routing in each data collection to optimize a performance measure: network lifetime. We first formulate this problem as an integer programming based on the connected coverage in sensor networks. We then derive an upper bound for the network lifetime which provides a measure for the performance of suboptimal methods. After that, we propose a suboptimal method for node scheduling and data routing to maximize the network lifetime. In the proposed method, instead of treating them as two separated optimization problems, the scheduling and routing are integrated into a single algorithm: when scheduling the sensors for area coverage, we consider not only the network geometry but also the energy consumed for the data transmission; when designing the information routing, we consider the role of each sensor in the scheduling since some sensors have crucial importance on the area coverage and should be treated specially in the routing. We study the performance of the proposed method by comparing its result with the lifetime upper bound and the separated design methods. Numerical examples demonstrate the performance of the proposed method.

A model for an infrared (IR) flame detection system using artificial neural networks (ANN) is presented. The joint time-frequency analysis (JTFA) in the form of a Short-Time Fourier Transform (STFT) is used for extracting relevant input features for a set of ANNs. Each ANN is trained using the backpropagation conjugate-gradient (CG) method to distinguish all hydrocarbon flames from a particular type of environmental nuisance and background noise. Signal saturation caused by the increased intensity of IR sources at closer distances is resolved by an adjustable gain control. A classification scheme with trained ANN connection weights was implemented on a digital signal processor for use in an industrial hydrocarbon flame detector.

Newton Raphson Functional Approximation is an attractive division strategy that provides quadratic convergence. With appropriate computational resources, it can be faster than digit recurrence methods if an accurate initial approximation is available. Several table lookup based initial approximation methods have been proposed previously. This paper examines some of these methods and implements a 24 bit divider utilizing a ROM smaller than 1 Kb. A Taylor series based reciprocal approximation method is used that employs a table lookup followed by multiplication. Simulations confirm that the design achieves desired accuracy after one Newton Raphson iteration.

This paper presents the first version of a software library called PACE ("Prototyping Arithmetic in Cryptography Easily"). This is a C++ library under LGPL license. It provides number systems and algorithms for prototyping the arithmetic layer in cryptographic applications. The first version of PACE includes basic support of prime finite fields and ECC (Elliptic Curve Cryptography) basic algorithms for software implementations.

The pairing is a mathematical notion wich appeared in cryptography during the 80'. At the beginning, it was used to build attacks on cryptosystems, transferring the discrete logarithm problem on elliptic curves, to a discrete logarithm problem on finite fields, the first was the MOV³⁶ attack in 1993. Now, pairings are used to construct some cryptographic protocols: Diffie Hellman tripartite, identity based encryption, or short signature. The main two pairings usually used are the Tate and Weil pairings. They use distortions and rationnal functions, and their complexities depends of the curve and the field involved. This study deals with two particular papers: one due to N. Koblitz and A. Menezes²⁷ published in 2005, and a second one written by R Granger, D. Page and N. Smart²⁴ in 2006. These two papers compare Tate andWeil pairings, but they differ in their conclusions. We consider the different arithmetic tricks used, trying to precise each point, in a way to avoid any ambiguity. Thus, the arithmetics proposed take into account the features of the fields and the curves used. We clarify the complexity of the possible implementations. We compare the different approaches, in order to clarify the conclusions of the previous papers.

A numerical method, based on the fast Fourier transform, is proposed that efficiently calculates the 2D (x,y) diffraction pattern formed when an ultrashort pulse of light is incident upon an aperture. Since ultrashort pulses are becoming increasingly important in modern optics from THz generation and spectroscopy to confocal microscopy, a fast numerical technique for calculating typical diffraction patterns is of significant interest. Pulses are not monochromatic but rather have a finite spectral distribution about some central frequency. Under paraxial conditions, the spatial diffraction pattern due to an individual spectral component may be calculated using the Fresnel transform. This is performed for each spectral component giving a spatio-spectral distribution. The diffracted spatio-temporal pulse can then be calculated by performing an inverse Fourier transform (with respect to the temporal frequency) on this spatio-spectral distribution. Numerical implementation raises two questions: (a) for a given distance and temporal frequency what is the minimum number of samples needed to efficiently calculate the corresponding Fresnel diffraction pattern and (b) for a given temporal pulse profile how many spectral components are required to accurately describe the diffraction of the pulse? By examining the distribution of the pulses energy in phase space using Wigner diagrams we identify a simple set of rules for determining these optimal sampling conditions. Then, using these rules we examine the diffraction patterns from both a square and circular aperture. A discussion of the results and potential THz applications follows.

Implementing the sum-product algorithm, in an FPGA with an embedded processor, invites us to consider a tradeoff between computational precision and computational speed. The algorithm, known outside of the signal processing community as Pearl's belief propagation, is used for iterative soft-decision decoding of LDPC codes. We determined the feasibility of a coprocessor that will perform product computations. Our FPGA-based coprocessor (design) performs computer algebra with significantly less precision than the standard (e.g. integer, floating-point) operations of general purpose processors. Using synthesis, targeting a 3,168 LUT Xilinx FPGA, we show that key components of a decoder are feasible and that the full single-precision decoder could be constructed using a larger part. Soft-decision decoding by the iterative belief propagation algorithm is impacted both positively and negatively by a reduction in the precision of the computation. Reducing precision reduces the coding gain, but the limited-precision computation can operate faster. A proposed solution offers custom logic to perform computations with less precision, yet uses the floating-point format to interface with the software. Simulation results show the achievable coding gain. Synthesis results help theorize the the full capacity and performance of an FPGA-based coprocessor.

In this work we present algorithms and schemes for computing several common arithmetic expressions defined in the complex domain as hardware-implemented operators. The operators include Complex Multiply-Add (CMA : ab + c), Complex Sum of Products (CSP : ab + ce + f), Complex Sum of Squares (CSS : a² + b² ), and Complex Integer Powers (CIPk : x², x³, ..., x^k). The proposed approach is to map the expression to a system of linear equations, apply a complex-to-real transform, and compute the solutions to the linear system using a digit-by-digit, the most significant digit first, recurrence method. The components of the solution vector corresponds to the expressions being evaluated. The number of digit cycles is about m for m-digit precision. The basic modules are similar to left-to-right multipliers. The interconnections between the modules are digit-wide.

ISA extensions for DLX type architectures are proposed to perform high radix online floating point addition on fixed point units with extended feature sets. Online arithmetic allows most significant digit first computation of results, allowing overlapped execution of dependent operations and offers greater instruction scheduling opportunities than software implementations of conventional floating point addition. In this paper we seek an ISA formulation to find a middle ground between full hardware floating point addition units and software implementations strictly based on available ALU logic.

Due to the synchronization method employed by most modern digital circuits, the maximum propagation delay through an adder unit is typically used to set the system level delay for addition operations. The actual delay of a binary addition computation is fundamentally tied to the longest carry propagation chain created by certain input operands. Although the probability of lengthy carry propagation chains is quite low, modern synchronous adders devote a large portion of their silicon area and energy consumption to speeding up the propagation of carries through the adder. Therefore, considerable die area and system power must be spent optimizing the improbable worst case delay. Using asynchronous self-timed circuits, similar adder performance can be obtained at a fraction of the hardware cost and energy consumption. This paper shows the inadequacy of characterizing self-timed adder performance using the assumption that typical input operands are uniformly randomly distributed, and presents a new self-timed adder characterization benchmark based on the SpecINT 2000 benchmark suite. The SpecINT 2000 benchmark was selected since there is no published carry propagation chain distribution for this modern benchmark suite and the benchmark is well suited for measuring carry propagation chains due to its code size and the fact that it is a non-synthetic benchmark. All totaled, over 4.7 billion addition/subtraction operations resulting from address and data calculations were tabulated to create the SpecINT 2000 Carry Propagation Distribution. This new carry propagation distribution sheds light on the accuracy of existing distributions based on the Dhrystone integer benchmark and demonstrates how measuring self-timed adder performance with a uniformly random input distribution can overestimate self-timed adder performance by over 50 percent.