In this paper, we present the condition for the effective wire addition in Look-Up-Table-based (LUT-based) field programmable gate array (FPGA) circuits, and an optimization procedure utilizing the effective wire addition. Each wire has different characteristics, such as delay and power dissipation. Therefore, the replacement of one critical wire for the circuit performance with many non-critical ones, i.e., many-addition-for-one-removal (m-for-1) is sufficiently useful. However, the conventional logic optimization methods based on sets of pairs of functions to be distinguished (SPFDs) for LUT-based FPGA circuits do not make use of the m-for-1 manipulation, and perform only simple replacement and removal, i.e., the one-addition-for-one-removal (1-for-1) manipulation and the no-addition-for-one-removal (0-for-1) manipulation, respectively. Since each LUT can realize an arbitrary internal function with respect to a specified number of input variables, there is no sufficient condition at the logic design level for simple wire addition. Moreover, in general, simple addition of a wire has no effects for removal of another wire, and it is important to derive the condition for non-simple and effective wire addition. We found the SPFD-based condition that wire addition is likely to make another wire redundant or replaceable, and developed an optimization procedure utilizing this effective wire addition. According to the experimental results, when we focused on the delay reduction of LUT-based FPGA circuits, our method reduced the delay by 24.2% from the initial circuits, while the conventional SPFD-based logic optimization and the enhanced global rewiring reduced it by 14.2% and 18.0%, respectively. Thus, our method presented in this paper is sufficiently practical, and is expected to improve the circuit performance.

A new hybrid method for characterizing the irregular power/ground plane pair is developed in this paper by combining the conventional eigen-mode expansion method with the new-presented inverted composition method and a simple model order reduction. By the approach, the eigen-mode expansion method can be extended to the characteristics research of the power/ground plane pair with holes. In this gridless method, ports and decoupling capacitors can be arbitrarily placed on the plane pair. The numerical example demonstrates its good validity.

This paper explores how to extend the dependency pair technique for proving termination of higher-order rewrite systems. In the first order case, the termination of term rewriting systems are proved by showing the non-existence of an infinite R-chain of the dependency pairs. However, the termination and the non-existence of an infinite R-chain do not coincide in the higher-order case. We introduce a new notion of dependency forest that characterize infinite reductions and infinite R-chains, and show that the termination property of higher-order rewrite systems R can be checked by showing the non-existence of an infinite R-chain, if R is strongly linear or non-nested.

Nonlinear distortions in an anti-series varactor pair (ASVP) are analyzed by a perturbation method. To the authors' knowledge, this paper presents the first derivation of an analytical expression that explicitly shows intermodulation and harmonic distortions of the ASVP. In addition to canceling the expected even-order distortion, the third-order distortion can be suppressed simultaneously when a certain condition is satisfied. We also find that the second- and third-order distortions can be greatly suppressed without dependence on dc bias voltage if the varactors in the ASVP have an ideal abrupt p-n junction. These theoretical predictions are verified by measuring the second- and third-order harmonic distortions of an ASVP. The experimental results show that the second-order harmonic distortion is suppressed by approximately 20 dB. The third-order harmonic distortion is suppressed to the same extent in the theoretically predicted dc bias voltage range.

A challenge to an automated layout of analog ICs starts with the insight into high quality placements crafted by experts. We observe first that matched devices or elemental functions such as input, output, amplifiers, etc are clustered. Second, devices in the same cluster are located faithfully to the drawn schema. Third, these two features are simultaneously fulfilled in a well-compacted placement. This paper proposes a novel device-level placement that simulates the above features based on Sequence-Pair. A slight modification of the meaning, say, of relation "A is left-of B" to relation "A is not right-of B" enlarges the freedom and allows a neater compaction of clusters allowing zigzag border curves. As the consequence, clusters are placed faithfully to relative position in the schema. We tested our algorithm for industrial instances and compared results with those by manual design. The results showed better features in performance figures than the those of manual designs by, on average, 13.5% and 21.2% with respect to the area and total net-length.

We present a built-in self-reconfiguring system for a mesh-connected processor array where faulty processor elements are compensated for by spare processing elements located in one row and one column. It has advantages in that the number of spare processing elements is small and additional control circuits and networks for changing interconnections of processing elements is so simple that hardware overhead for reconfiguration is also small. First, to indicate the motivation to the proposed reconfiguration scheme, we briefly describe other schemes with the same number of spares as that of the proposed scheme where faulty processing elements are replaced using straight shifts toward spares, and compare their reconfiguration probabilities to each other. Then, we show that a variant of the proposed scheme has the highest probability. Next, we present a built-in self-reconfiguring system for the scheme and formally prove that it works correctly. It can automatically replace faulty processors by spare processors on detecting faults of processors.

The AODV (Ad Hoc On-Demand Distance Vector) protocol is one of the typical reactive routing protocols in Ad Hoc networks, in that mobile nodes initiate routing activities only in the presence of data packets in need of a route. In this paper, we focus upon the local repair mechanism of AODV. When a link is broken, the upstream node of the broken link repairs the route to the destination by initiating a local route discovery process. The process involves the flooding of AODV control messages in every node within a radius of the length from the initiating node to the destination. In this paper, we propose an efficient local repair scheme for AODV, called AELR (AODV-based Efficient Local Repair). AELR utilizes the existing routing information in the downstream intermediate nodes which have been on the active route to the destination before a link break occurs. AELR can reduce the flooding range of AODV control messages and the route recovery time for route recovery because it can repair a route through the nearby downstream intermediate nodes. The performance results show that AELR can achieve faster route recovery than the local repair mechanism of AODV.

The proposed DOA (Direction Of Arrival) estimation method by integrating the frequency array data generated from microphone pairs in an equilateral-triangular microphone array is extended here. The method uses four microphones located at the apices of regular tetrahedron to enable to estimate the elevation angle from the array plane as well. Furthermore, we introduce an idea for separate estimation of azimuth and elevation to reduce the computational loads.

This paper presents an efficient LSP quantizer implementation for low bit-rate coders. The major feature of the quantizer is that it uses a truncated cepstral distance criterion for the code selection procedure. This approach has generally been considered too computationally costly. We utilized the quantizer with a moving-average predictor, two-stage-split vector quantizer and delayed decision. We have investigated the optimal parameter settings in this case and incorporated the quantizer thus obtained into an ITU-T 4-kbit/s speech coding candidate algorithm with a bit budget of 21 bits. The objective performance is better than that with a conventional weighted mean-square criterion, while the complexity is still kept to a reasonable level. The paper also describes the codebook design and techniques that were employed to achieve robustness in noisy channel conditions.

This paper provides methods for construction of pairing-based cryptosystems based on non-supersingular elliptic curves.

A new multiple-valued current-mode (MVCM) logic circuit using substrate bias control is proposed for low-power VLSI systems at higher clock frequency. Since a multi-level threshold value is represented as a threshold voltage of an MOS transistor, a voltage comparator is realized by a single MOS transistor. As a result, two basic components, a comparator and an output generator in the MVCM logic circuit can be merged into a single MOS differential-pair circuit where the threshold voltages of MOS transistors are controlled by substrate biasing. Moreover, the leakage current is also reduced using substrate bias control. As a typical example of an arithmetic circuit, a radix-2 signed-digit full adder using the proposed circuit is implemented in a 0.18- µm CMOS technology. Its dynamic and static power dissipations are reduced to about 79 percent and 14 percent, respectively, in comparison with those of the corresponding binary CMOS implementation at the supply voltage of 1.8 V and the clock frequency of 500 MHz.

In this paper, we propose a DOA (Direction Of Arrival) estimation method of speech signal using three microphones. The angular resolution of the method is almost uniform with respect to DOA. Our previous DOA estimation method using the frequency-domain array data for a pair of microphones achieves high precision estimation. However, its resolution degrades as the propagating direction being apart from the array broadside. In the method presented here, we utilize three microphones located at vertices of equilateral triangle and integrate the frequency-domain array data for three pairs of microphones. For the estimation scheme, the subspace analysis for the integrated frequency array data is proposed. Through both computer simulations and experiments in a real acoustical environment, we show the efficiency of the proposed method.

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, using the exact expression for the pairwise error probability derived in terms of the message symbol distance between two message vectors rather than the codeword symbol distance between two transmitted codeword matrices, the exact closed form expressions for the symbol error probability of any linear orthogonal space-time block codes in slow Rayleigh fading channel are derived for QPSK, 16-QAM, 64-QAM, and 2 56-QAM.

This paper presents a blind frequency offset estimation method for Polynomial Cancellation Coded Orthogonal Frequency Division Multiplexing (PCC-OFDM) systems. We have theoretically derived the frequency offset estimator. The estimation exploits the Subcarrier Pair Imbalance (SPI) which is presented in terms of the power difference between two demodulated subcarriers in a PCC-OFDM subcarrier pair. The estimator can be used for high order QAM modulation schemes. In all cases, the estimator has an approximately linear relationship with the frequency offset. The potential application of the estimator in conventional OFDM systems is also investigated in this paper.

In this paper, we propose an alternative method that does not generate a test for each path delay fault directly to generate tests for path delay faults. The proposed method generates an N-propagation test-pair set by using an Ni-detection test set for single stuck-at faults. The N-propagation test-pair set is a set of vector pairs which contains N distinct vector pairs for every transition faults at a check point. Check points consist of primary inputs and fanout branches in a circuit. We do not target the path delay faults for test generation, instead, the N-propagation test-pair set is generated for the transition (both rising and falling) faults of check points in the circuit. After generating tests, tests are simulated to determine their effectiveness for singly testable path delay faults and robust path delay faults. Results of experiments on the ISCAS'85 benchmark circuits show that the N-propagation test-pair sets obtained by our method are effective in testing path delay faults.

In this paper, for convex rectilinear block packing problem, we propose 1) a novel algorithm to obtain a packing based on a given sequence-pair in O(n2) time (conventional method needs O(n3) time), where n is the number of rectangle sub-blocks made from convex blocks, 2) a move operation for Simulated Annealing which is symmetric and can guarantee reachability for the first time, and 3) a method to generate a random adjacent sequence-pair in O(n2) time. By using 1), 2) and 3) together, the time complexity of the inner loop in Simulated Annealing becomes surely O(n2) time. Experimental results show that the proposed algorithm is faster than the conventional ones in practical and the wire length as well as packing area is taken into consideration in the proposed method.

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.

This paper presents an even harmonic mixer using self-biased anti-parallel diode pair (APDP). A proposed self-biased APDP is composed of a pair of diodes and self-bias series resistors. At high LO injection level, rectified current is generated by the diodes and reverse voltage is applied to the diodes by the self-bias resistor. Therefore, rapid degradation of conversion loss at high LO input level can be avoided. The effect of self-bias resistor is explained by using simplified behavior model and harmonic balance method, and is evaluated by the measurements of an L-band even harmonic type direct conversion mixer.

For common-mode noise current reduction, a CMC (Common Mode Choke) is widely used in signal transmission line circuits consisting of a ground and two conductors (a balanced transmission line). However, a common-mode noise current reduction characteristic is not clearly analyzed yet in the case that a CMC is inserted in a balanced transmission line. In this paper we propose the calculation method of CMC insertion losses and derive an equation to analyze the common-mode current characteristics of a balanced transmission line with a CMC inserted. The analyzed frequency range is from 100 kHz to 100 MHz. We conclude that in the frequency range up to 30 MHz: (1) the proposed insertion loss calculation method is useful for analyzing CMC insertion losses in differential-mode and in common-mode; (2) the derived circuit equation can be applied for analyzing the common-mode current characteristics of a balanced transmission line locally unbalanced with conditions of a CMC inserted; (3) the proposed calculation method may give the expected results that a CMC should be placed in a signal source side of an unbalanced point of a pair-cable for reduction of common-mode currents; and (4) if it is placed in a terminal (or load) side of an unbalanced point, there is no effect, or rather common-mode currents are increased by the insertion of a CMC.