Simply-typed term rewriting systems (STRSs) are an extension of term rewriting systems. STRSs can be naturally handle higher order functions, which are widely used in existing functional programming languages. In this paper we design recursive and lexicographic path orders, which can efficiently prove the termination of STRSs. Moreover we discuss an application to the dependency pair and the argument filtering methods, which are very effective and efficient support methods for proving termination.

In this paper, a fragment-processing solution in 3D graphics rendering algorithms based on fragment lists (i.e. A-buffer) for minimizing loss of image quality is described. While all fragment information should be preserved for exact hidden surface removal, this places additional strain on hardware in terms of silicon gates and clock cycles. Therefore, we propose a fragment processing technique that can effectively merge fragments in order to decrease the depth of fragment lists. It renders scenes quite accurately even in the case when three fragments intersect each other. This algorithm improves hardware acceleration without deteriorating image quality.

In this paper, we describe a technique for optimizing the algebraic method that is applied to higher order differential attack. The higher order differential attack is a well-known attack on block ciphers, in which we derive an attack equation to determine a round key from a property of a higher order differential of a target block cipher. The algebraic method is a linearization of the attack equation and determines the true key by a method such as Gaussian elimination. Our technique is based on linear dependency and can reduce the complexity of that method. We also describe a technique that allows the algebraic method to be used as an attack equation that holds probabilistically. We demonstrate this method by attacking a five-round MISTY1 and show that it needs 221.6 chosen plaintexts and 228.0 encryption times. The computer simulation took about two minutes to complete.

This paper describes a sparse realization of passive reduced-order interconnect models via PRIMA to provide the SPICE compatible models. It is demonstrated that, if the SPICE models are directly realized so that the reduced-order equations obtained via PRIMA are stamped into the MNA matrix, the simulations of networks containing the macromodels become computationally inefficient when size of the reduced-order equations is relatively large. This is due to dense coefficient matrices of the reduced-order equations resulting from congruent transformations in PRIMA. To overcome this disadvantage, we propose a sparse realization of the reduced-order models. Since the expression is equivalent to the reduced-order equations, the passivity of the SPICE models generated is also guaranteed. Computational efficiency on SPICE is demonstrated in performing the transient analysis of circuits containing the proposed macromodels.

The traditional way of approaching device-level placement problems for analog layout is to explore a huge search space of absolute placement representations, where cells are allowed to illegally overlap during their moves. This paper presents a novel exploration technique for analog placement, operating on a subset of tree representations of the layout, where the typical presence of an arbitrary number of symmetry groups of devices is directly taken into account during the search of the solution space. The efficiency of the novel approach is due to the use of red-black interval trees, data structures employed to support operations on dynamic sets of intervals.

In this paper, we present the results of a comparative analysis of Atomic Broadcast algorithms. The analysis was done by using an analytical method to compare the performance of five different classes of Atomic Broadcast algorithms. The five classes of Atomic Broadcast algorithms are determined by the mechanisms used by the algorithms to define the delivery order. To evaluate the performance of algorithms, the analysis relies on contention-aware metrics to provide a measure for both their latency and their throughput. The results thus obtained yield interesting insight into the performance tradeoffs of different Atomic Broadcast algorithms, thus providing helpful information to algorithms and systems designers.

Ordered successive MMSE detection (OSD) can achieve a good tradeoff between performance and complexity for multiple-input multiple-output (MIMO) wireless systems where different data streams are transmitted and received simultaneously over several equal number of transmit and receive antennas. However, over time-varying MIMO channels, the performance of OSD is degraded with realistic channel estimation. In this paper, we introduce two different approaches in order to improve the performance of OSD. First, we propose to improve the accuracy of the generated nulling weights by using a modified noise variance that takes into consideration the weights update lag error besides to the noise and channel estimation errors. Second, we introduce a new iteration approach in order to improve the decisions made by OSD on transmitted streams. The proposed iterative scheme, named as backward iterative detection, exploits the tentative decisions on lately detected streams in order to mainly improve the decision on the firstly detected stream that limits the overall performance. Simulation results of combining both approaches show significant performance improvements of OSD.

An ultra-high-sensitivity HDTV color camcorder (camera with VTR) has been developed featuring image intensifiers with GaAsP photocathodes, which provide very high quantum efficiency. To achieve superior performance and a compact camera body, we combined three 1-inch image intensifiers with a 2/3-inch taking lens and three 2/3-inch CCDs by means of a new optical system capable of enlarging and reducing images. The camcorder provides excellent color reproducibility even under low light level conditions (0.2 lx) at an iris setting of f/2, with a signal-to-noise ratio of 55 dB at pedestal level. Its sensitivity is about 400 times greater than that of current HDTV CCD camcorders, making it particularly well suited for capturing images of faint objects in space, aurora, etc., filming the nocturnal activities of animals in their natural settings, and reporting breaking news at night.

A reduced complexity multiple-input multiple-output (MIMO) equalizer with ordered successive interference cancellation (OSIC) is proposed for combating intersymbol interference (ISI) and cochannel interference (CCI) over frequency-selective multipath channels. It is developed as a reduced-rank realization of the conventional MMSE decision feedback equalizer (DFE). In particular, the MMSE weight vectors at each stage of OSIC are computed based on the generalized sidelobe canceller (GSC) technique and reduced-rank processing is incorporated by using the conjugate gradient (CG) algorithm for reduced complexity implementation. The CG algorithm leads to a best low-rank representation of the GSC blocking matrix via an iterative procedure, which in turn gives a reduced-rank equalizer weight vector achieving the best compromise between ISI and CCI suppression. With the dominating interference successfully cancelled at each stage of OSIC, the number of iterations required for the convergence of the CG algorithm decreases accordingly for the desired signal. Computer simulations demonstrate that the proposed reduced-rank MIMO DFE can achieve nearly the same performance as the full-rank MIMO MMSE DFE with an effective rank much lower than the dimension of the signal-plus-interference subspace.

An adaptive backstepping and high order sliding modes control algorithm is proposed for output tracking of mobile robots. The controller can greatly reduce the chattering due to conventional sliding modes technique. The proposed algorithm has certain robustness with respect to the external random disturbances and good adaptability with respect to the parametric uncertainty. The effectiveness of the proposed control strategy is demonstrated by simulations studies.

This paper proposes a technique for indexing, clustering and retrieving images based on their edge features. In this technique, images are decomposed into several frequency bands using the Haar wavelet transform. From the one-level decomposition sub-bands an edge image is formed. Next, the higher order auto-correlation function is applied on the edge image to extract the edge features. These higher order autocorrelation features are normalized to generate a compact feature vector, which is invariant to shift, image size. We used direction cosine as measure of distance not to be influenced by difference of each image's luminance. Then, these feature vectors are clustered by a self-organizing map (SOM) based on their edge feature similarity. The performed experiments show higher precision and recall of this technique than traditional ways in clustering and retrieving images in a large image database environment.

In this paper, design of a new analog CMOS rank-order extractor with input expandable capability is described. An rth rank-order extraction is defined that identifies the rth largest magnitude of input variables, which is useful for fuzzy controller and artificial neural networks. The architecture is realized by using maximum circuit, winner-take-all circuit, and some auxiliary circuits. The limitations and design considerations of these circuits are analyzed in this paper. An experimental chip with seven inputs is fabricated using a 0.5 µm CMOS double-poly double-metal technology. The results of measurement show the extractor with 2 µA precision, and each rank-order extraction has about 2 µs response time. The power dissipation of the experiment chip under test includes input/output pads that has 7.2 mW for 3.3 V supply voltage. The chip area of the extractor is 600 µm 700 µm.

A robust adaptive filtering algorithm was established recently (I. Yamada, K. Slavakis, K. Yamada 2002) based on the interactive use of statistical noise information and the ideas developed originally for efficient algorithmic solutions to the convex feasibility problems. The algorithm is computationally efficient and robust to noise because it requires only an iterative parallel projection onto a series of closed half spaces highly expected to contain the unknown system to be identified and is free from the computational load of solving a system of linear equations. In this letter, we show the potential applicability of the adaptive algorithm to the identification problem for the second order Volterra systems. The numerical examples demonstrate that a straightforward application of the algorithm to the problem soundly realizes fast and stable convergence for highly colored excited speech like input signals in possibly noisy environments.

A three-mode switched-LNA has been developed using a 0.25 µm SiGe BiCMOS technology. The LNA features low noise figure (NF) performance, while achieving both low dissipation power and low distortion characteristics. The proposed MOSFET switch incorporating a newly developed switch circuit with a triple-well structure, which changes the LNA's mode, provides a parasitic capacitance of just 0.52 times that of a conventional MOSFET switch. This results in a significant NF improvement, by 0.16-0.33 dB, for the three-mode switched-LNA compared to a conventional LNA. Extensive studies of the MOSFET switch with regard to the structural parameters and the doping profiles are reported. Experimental results and the overall performance of a trial IC incorporating the three-mode switched-LNA are also given.

Least-squares second-order polynomial filter and fixed-point smoother are derived in systems with uncertain observations, when the variables describing the uncertainty are non-independent. The proposed estimators do not require the knowledge of the state-space model of the signal. The available information is only the moments, up to the fourth one, of the involved processes, the probability that the signal exists in the observations and the (2,2) element of the conditional probability matrices of the sequence describing the uncertainty.

The certified discrete logarithm problem modulo p prime is a discrete logarithm problem under the conditions that the complete factorization of p-1 is given and by which the base g is certified to be a primitive root mod p. For the cryptosystems based on the intractability of certified discrete logarithm problem, Sakurai-Shizuya showed that breaking the Diffie-Hellman key exchange scheme reduces to breaking the Shamir 3-pass key transmission scheme with respect to the expected polynomial-time Turing reducibility. In this paper, we show that we can remove randomness from the reduction above, and replace the reducibility with the polynomial-time many-one. Since the converse reduction is known to hold with respect to the polynomial-time many-one reducibility, our result gives a stronger evidence for that the two schemes are completely equivalent as certified discrete log cryptosystems.

Ordered attribute grammars (OAGs for short) are a useful class of attribute grammars (AGs). For some attribute grammars, even though they are not circular, OAG circularity test reports that they are not ordered and fails to generate attribute evaluators because some approximation introduces circularities (called type 3 circularities in this paper). First we discuss that it is sometimes difficult for programmers to eliminate type 3 circularities by hand. Second, to reduce this difficulty, we propose a new AG class called OAG* that produces less type 3 circularities than OAG while preserving the positive characteristic of OAG. OAG* uses a global dependency graph GDS that provides a new approximation algorithm. We obtained good results with our experimental implementation of OAG*. It is shown that OAG* is different from the existing GAG and Eli/Liga systems. Finally, two combinations of Eli/Liga and OAG* are provided.

This paper proposes a gesture recognition method which uses higher order local autocorrelation (HLAC) features extracted from PARCOR images. To extract dominant information from a sequence of images, we apply linear prediction coding technique to the sequence of pixel intensities and PARCOR images are constructed from the PARCOR coefficients of the sequences of the pixel values. From the PARCOR images, HLAC features are extracted and the sequences of the features are used as the input vectors of the Hidden Markov Model (HMM) based recognizer. Since HLAC features are inherently shift-invariant and computationally inexpensive, the proposed method becomes robust to changes in the person's position and makes real-time gesture recognition possible. Experimental results of gesture recognition are shown to evaluate the performance of the proposed method.

The present paper deals with the blind deconvolution of a Multiple-Input Multiple-Output Finite Impulse Response (MIMO-FIR) system. To deal with the blind deconvolution problem using the second-order statistics (SOS) of the outputs, Hua and Tugnait considered it under the conditions that a) the FIR system is irreducible and b) the input signals are spatially uncorrelated and have distinct power spectra. In the present paper, the problem is considered under a weaker condition than the condition a). Namely, we assume that c) the FIR system is equalizable by means of the SOS of the outputs. Under b) and c), we show that the system can be blindly identified up to a permutation, a scaling, and a delay using the SOS of the outputs. Moreover, based on this identifiability, we show a novel necessary and sufficiently condition for solving the blind deconvolution problem, and then, based on the condition, we propose a new algorithm for finding an equalizer using the SOS of the outputs, while Hua and Tugnait have not proposed any algorithm for solving the blind deconvolution under the conditions a) and b).

A high power dissipation density in today's miniature electronic/mechanical systems makes on-chip thermal management very important. In order to achieve quick to evaluate, yet accurate electro-thermal models, needed for the thermal management of microsystems, a model order reduction is necessary. In this paper, we present an automatic, Krylov-subspace-based order reduction of a electro-thermal model, which we illustrate by a novel type of micropropulsion device. Numerical simulation results of the full finite element model and the reduced order model, that describes the transient electro-thermal behavior, are presented. A comparison between Krylov-subspace-based order reduction, order reduction using control theoretical approaches and commercially available reduced order modeling has been performed. A Single-Input-Single-Output setup for the Arnoldi reduction algorithm was proved to be sufficient to accurately represent the complete time-dependent temperature distribution of the device.