This paper considers Quasi-Reduced ordered Multi-valued Decision Diagrams with k bits (QRMDD(k)s) to represent binary logic functions. Experimental results show relations between the values of k and the numbers of nodes, the memory sizes, the numbers of memory accesses, and area-time complexity for QRMDD(k). For many benchmark functions, the numbers of nodes and memory accesses for QRMDD(k)s are nearly equal to of the corresponding Quasi-Reduced ordered Binary Decision Diagrams (QRBDDs), and the memory sizes and the area-time complexities for QRMDD(k)s are minimum when k = 2 and k = 3-6, respectively.

This paper presents a technique for improving the SNR and resolution of complex bandpass ΔΣADCs which are used for wireless communication systems such as cellular phone, wireless LAN and Bluetooth. Oversampling and noise-shaping are used to achieve high accuracy of a ΔΣAD modulator. However when a multi-bit internal DAC is used inside a modulator, nonlinearities of the DAC are not noise-shaped and the SNR of the ΔΣADC degrades. For the conversion of complex intermediate frequency (IF) input signals, a complex bandpass ΔΣAD modulator can provide superior performance to a pair of real bandpass ΔΣAD modulators of the same order. This paper proposes a new noise-shaping algorithm--implemented by adding simple digital circuitry--to reduce the effects of nonlinearities in multi-bit DACs of complex bandpass ΔΣAD modulators. We have performed simulation with MATLAB to verify the effectiveness of the algorithm, and the results show that the proposed algorithm can improve the SNR of a complex bandpass ΔΣADC with nonlinear internal multi-bit DACs.

A new algorithm and architecture to eliminate redundant operations in block-matching (BM) motion estimation is proposed. The key step of this work is to use binary-matching to define image regions with the static background content and then exclude these regions from the actual motion estimation. According to experiments, the approach maintains the highest PSNR, while making as half as less computations in comparison to the adaptive BM or 1/8 of the computations required by the full-search BM. An implementation scheme is outlined.

This paper investigates relationships among deterministic, nondeterministic, and alternating complexity classes defined in the hyperbolic space. We show that (i) every t(n)-time nondeterministic cellular automaton in the hyperbolic space (hyperbolic CA) can be simulated by an O(t4(n))-space deterministic hyperbolic CA, and (ii) every t(n)-space nondeterministic hyperbolic CA can be simulated by an O(t2(n))-time deterministic hyperbolic CA. We also show that nr+-time (non)deterministic hyperbolic CAs are strictly more powerful than nr-time (non)deterministic hyperbolic CAs for any rational constants r 1 and > 0. From the above simulation results and a known separation result, we obtain the following relationships of hyperbolic complexity classes: Ph= NPh = PSPACEh EXPTIMEh= NEXPTIMEh = EXPSPACEh , where Ch is the hyperbolic counterpart of a Euclidean complexity class C. Furthermore, we show that (i) NPh APh unless PSPACE = NEXPTIME, and (ii) APh EXPTIME h.

The descriptional complexity of iterative arrays (IAs) is studied. Iterative arrays are a parallel computational model with a sequential processing of the input. It is shown that IAs when compared to deterministic finite automata or pushdown automata may provide savings in size which are not bounded by any recursive function, so-called non-recursive trade-offs. Additional non-recursive trade-offs are proven to exist between IAs working in linear time and IAs working in real time. Furthermore, the descriptional complexity of IAs is compared with cellular automata (CAs) and non-recursive trade-offs are proven between two restricted classes. Finally, it is shown that many decidability questions for IAs are undecidable and not semidecidable.

This paper describes synthesis of a complex RiCR filter with a finite transmission zero except zero frequency. The frequency response of the proposed filter is similar to the conventional elliptic filter. The proposed filter can be composed of fewer elements than the conventional one. A new kernel function is proposed. As an example, a fifth-order RiCR filter is designed. We compare the proposed filter with the conventional complex elliptic filter from the viewpoint of the frequency response and the number of the required elements.

This paper presents a strictly time- and communication-optimal distributed sorting algorithm in a line network. A strictly time-optimal distributed sorting algorithm in a line network has already been designed. However, its communication complexity is not strictly optimal and it seems to be difficult to extend it to other problems, such as that related to multiple elements in a process, and also the dynamic sorting problem where the number of elements each process should have as its solution is not the same as that in the initial state. Therefore, the algorithm in this paper was designed by an alternative approach to make it strictly time- and communication-optimal. Moreover, an extension to the dynamic sorting problem is described.

The safety problem in access matrix models determines whether a given subject can eventually obtain access privilege to a given object. Generally speaking, the safety problem is, unfortunately undecidable. Not much is known about protection systems for which the safety problem is decidable, except for strongly constrained systems (e.g., monotonic systems). Therefore, we propose the Dynamic-Typed Access Matrix (DTAM) Model, which extends the Typed Access Matrix model of Sandhu by allowing the type of an object to change dynamically. The DTAM model has an advantage that it can describe non-monotonic protection systems for which the safety problem is decidable. In particular, with further restrictions, we can show that the problem becomes NP-hard. In this paper, we formally define the DTAM model and then discuss various aspects of it thoroughly.

This paper proposes complex form BandPass Sampling (BPS) that is suitable for the software radio. This BPS utilizes offset frequency sampling and quadrature component interpolation. Three types of BPS techniques are first reviewed, which shows effectiveness of the proposed BPS technique. The major advantages over the conventional BPS techniques are: i) free from the DC offset that is caused by the leak of the sampling clock harmonics into the received signal, and ii) reduction of alias by the complex number processing in the signal detection. Next, detailed description of the BPS operation shows that it requires real-time interpolation for the time alignment of the sampled quadrature component. Finally, computer simulation shows that the misalignment generates distortion, and that effective interpolation techniques can reduce the distortion level less than -60 dB even for wideband signals.

Development of non-invasive techniques to measure blood sugar level is strongly required. The application of millimeter waves has a great potentiality to realize the measuring technique. Nevertheless, the practical method of the technique is not yet reported. In this paper, a new technique is proposed to measure blood sugar level using millimeter waves. The technique proposed here is very rapid and safety way to obtain blood sugar level.

Two operations, polynomial multiplication and modular reduction, are newly induced by the properties of the modified Booth's algorithm and irreducible all one polynomials, respectively. A new and effective methodology is hereby proposed for computing multiplication over a class of fields GF(2m) using the two operations. Then a low complexity multiplexer-based multiplier is presented based on the aforementioned methodology. Our multiplier consists of m 2-input AND gates, an (m2 + 3m - 4)/2 2-input XOR gates, and m(m - 1)/2 4 1 multiplexers. For the detailed estimation of the complexity of our multiplier, we will expand this argument into the transistor count, using a standard CMOS VLSI realization. The compared results show that our work is advantageous in terms of circuit complexity and requires less delay time compared to previously reported multipliers. Moreover, our architecture is very regular, modular and therefore, well-suited for VLSI implementation.

Effects of the sample insertion holes of the TM010 mode cylindrical cavity are analyzed on the basis of rigorous analysis by the Ritz-Galerkin method. The measurement accuracy of complex permittivity is examined by comparing the values by the perturbation method with ones by the rigorous analysis. Charts of relative errors Δ ε/εp and Δ tan δ/tan δp are presented, which are useful to measure the complex permittivity accurately by the perturbation method. The present analysis extends the validity of the conventional perturbation method.

The objective of this paper is to study the relationship between a visual stimulus and the amplitude and phase of the alpha wave as a first step to investigating a change in the background wave after a sensory stimulus and an evoked potential. We examined the effect of a single visual stimulus on the amplitude and phase of alpha waves using the complex demodulation method. The visual stimuli were generated by an LED mounted in goggles with the eyes-closed condition. The amplitude of the alpha wave decreased gradually after the stimulus, until it reached a minimum at around 300 ms after the stimulus. The alpha wave continued to increase, showing some rebound, and returning again to the pre-stimulus level. The phase variation after the stimulus tends to be considerably larger than that before the stimulus. Moreover, the average phase returned to the same slope as the pre-stimulus by 2550 ms after the stimulus. The visual stimulus has an effect on the alpha wave until about 2500 ms after the stimulus. The phase variation difference before and after stimulus is significant from 112 ms to 678 ms after the stimulus. This finding suggests there is a partially pararell time course between the change in VEPs plus ERP complex and the alpha wave.

Recently six conjectures on linear complexities (LC) of some Kronecker sequences of two or three component sequences are proposed by Karkkainen. In, the LC of Kronecker sequences of two component sequences were studied by Uehara and Imamura, their results are true except in the case when eb 2 or when ea = eb = 1. In this paper the LC for Kronecker sequences of two component sequences are determined completely, and it is shown that all the six conjectures are true except in some special cases, which are listed and corrected.

This paper proposes the conditional LZ complexity and analyzes its property. Especially, we show an inequality corresponding to Ziv's inequality concerning a distinct parsing of a pair of sequences. Further, as a byproduct of the result, we show a simple proof of the asymptotical optimality of Ziv's universal source coding algorithm with side information.

This paper introduces a 1-inkdot two-way alternating pushdown automaton which is a two-way alternating pushdown automaton (2apda) with the additional power of marking at most 1 tape-cell on the input (with an inkdot) once. We first investigate a relationship between the accepting powers of sublogarithmically space-bounded 2apda's with and without 1 inkdot, and show, for example, that sublogarithmically space-bounded 2apda's with 1 inkdot are more powerful than those which have no inkdots. We next investigate an alternation hierarchy for sublogarithmically space-bounded 1-inkdot 2apda's, and show that the alternation hierarchy on the first level for 1-inkdot 2apda's holds, and we also show that 1-inkdot two-way nondeterministic pushdown automata using sublogarithmic space are incomparable with 1-inkdot two-way alternating pushdown automata with only universal states using the same space.

Whispering-Gallery mode resonator method has been presented for complex permittivity evaluation of low loss dielectric materials in millimeter wave region. As a problem, it has been found that the evaluation error slightly dependens on the frequency for a sample. It comes from approximated analysis which is used in the procedure. In this paper, a mode-matching method is applied to this evaluation technique to have improvement of the measrued results. It is confirmed experimentally that reliability of the presented method is improved for the millimeter wave permittivity measurement.

The Another Solution Problem (ASP) of a problem is the following problem: for a given instance x of and a solution s to it, find a solution to x other than s. The notion of ASP as a new class of problems was first introduced by Ueda and Nagao. They also pointed out that parsimonious reductions which allow polynomial-time transformation of solutions can derive the NP-completeness of ASP of a certain problem from that of ASP of another. In this paper we consider n-ASP, the problem to find another solution when n solutions are given, and formalize it to investigate its characteristics. In particular we consider ASP-completeness, the completeness with respect to the reductions satisfying the properties mentioned above. The complexity of ASPs has a relation with the difficulty of designing puzzles. We prove the ASP-completeness of three popular puzzles: Slither Link, Cross Sum, and Number Place. Since ASP-completeness implies NP-completeness, these results can be regarded as new results of NP-completeness proof of puzzles.

In this paper, we will show that some families of periodic sequences over Z4 and Z8 with period multiple of 2r-1 generated by r-th degree basic primitive polynomials assorted by the root of each polynomial, and give the exact distribution of sequences for each family. We also point out such an instability as an extreme increase of their linear complexities for the periodic sequences by one-symbol substitution, i.e., from the minimum value to the maximum value, for all the substitutions except one.

This paper discusses a nonlinear function for independent component analysis to process complex-valued signals in frequency-domain blind source separation. Conventionally, nonlinear functions based on the Cartesian coordinates are widely used. However, such functions have a convergence problem. In this paper, we propose a more appropriate nonlinear function that is based on the polar coordinates of a complex number. In addition, we show that the difference between the two types of functions arises from the assumed densities of independent components. Our discussion is supported by several experimental results for separating speech signals, which show that the polar type nonlinear functions behave better than the Cartesian type.