This paper investigates the accepting powers of deterministic, Las Vegas, self-verifying nondeterministic, and nondeterministic one-way multi-counter automata with time-bounds. We show that (1) for each k1, there is a language accepted by a Las Vegas one-way k-counter automaton operating in real time, but not accepted by any deterministic one-way k-counter automaton operating in linear time, (2) there is a language accepted by a self-verifying nondeterministic one-way 2-counter automaton operating in real time, but not accepted by any Las Vegas one-way multi-counter automaton operating in polynomial time, (3) there is a language accepted by a self-verifying nondeterministic one-way 1-counter automaton operating in real time, but not accepted by any deterministic one-way multi-counter automaton operating in polynomial time, and (4) there is a language accepted by a nondeterministic one-way 1-counter automaton operating in real time, but not accepted by any self-verifying nondeterministic one-way multi-counter automaton operating in polynomial time.

This paper investigates properties of space-bounded "two-dimensional Turing machines (2-tm's)," whose input tapes are restricted to square ones, with bounded input head reversals in vertical direction. We first investigate a relationship between determinism and nondeterminism for space-bounded and input head reversal-bounded 2-tm's. We then investigate how the number of input head reversals affects the accepting power of sublinearly space-bounded 2-tm's. Finally, we investigate necessary and sufficient spaces for three-way 2-tm's to simulate four-way two-dimensional finite automata with constant input head reversals.

A wireless communications system with a transmission speed of 18 Mbit/s is presented using the 2.4 GHz ISM band. This system employs the Carrier Frequency Offset-Spread Spectrum (CFO-SS) scheme and the Dual-Polarization Staggered Transmission (DPST) scheme. The 18 Mbit/s CFO-SS system (named CFO-SS18) was developed and its performance evaluated in fields. In this paper, the detailed operating principle of CFO-SS and DPST schemes, together with the specifications and structures of CFO-SS18, are presented. Results of indoor and field tests obtained by using CFO-SS18 are also presented.

In this paper, we study the following problem: given two graphs G, H and an isomorphism φ between an induced subgraph of G and an induced subgraph of H, compute the number of isomorphisms between G and H that do not contradict φ. We show that this problem can be solved in O(((k+1)(k+1)!)2n3) time when the input graphs are restricted to chordal graphs with clique number at most k+1. To prove this, we first show that the tree model of a chordal graph can be uniquely constructed in O(n3) time except for the ordering of children of each node. Then, we show that the number of φ-isomorphisms between G and H can be efficiently computed by use of the tree model.

This paper presents a refined model for the fuzzy logic implementation of an available bit rate (ABR) flow control switch. This refined model is named fuzzy explicit rate (FUER) switch mechanism. FUER switch mechanism is designed to effectively perform congestion control on ABR traffic in asynchronous transfer mode (ATM) networks. The performance of FUER scheme is evaluated against those of two other explicit rate (ER)-based switch mechanisms using simulation in particular local area network (LAN) and wide area network (WAN) environments. On the whole, FUER scheme performs better than the other schemes. Although it has the smallest control parameter set, it is a more efficient and scalable ER-based switch mechanism.

A time-interleaved ADC system is an effective way to implement a high-sampling-rate ADC with relatively slow circuits. In the system, several channel ADCs operate at interleaved sampling times as if they were effectively a single ADC operating at a much higher sampling rate. Mismatches among channel ADCs degrade SNR and SFDR of the ADC system as a whole, and the effects of offset, gain and bandwidth mismatches as well as timing skew of the clocks distributed to the channels have been well investigated. This paper investigates the channel linearity mismatch effects in the time-interleaved ADC system, which are very important in practice but had not been investigated previously. We consider two cases: differential nonlinearity mismatch and integral nonlinearity mismatch cases. Our numerical simulation shows distinct features of such mismatch especially in frequency domain. The derived results can be useful for deriving calibration algorithms to compensate for the channel mismatch effects.

In computer-aided drafting and design, interactive graphics is used to design components, systems, layouts, and structures. There are several approaches for using automated graphical layout tools currently. Our approach employs a genetic algorithm to implement a tool for automated 3D graphical layout design and presentation. The effective use of a genetic algorithm in automated graphical layout design relies on defining a fitness function that reflects user preferences. In this paper, we describe a method to define fitness functions and chromosome structures of selected objects. A learning mechanism is employed to adjust the fitness values of the objects in the selected layout chosen by the user. In our approach, the fitness functions can be changed adaptively reflecting user preferences. Experimental results revealed good performance of the adaptive fitness functions in our proposed mechanism.

We have proposed an intracell uplink of a spread-spectrum code-division multiple-access (SS-CDMA) flexible wireless network based on approximately synchronized (AS) CDMA. Since the AS-CDMA has no co-channel interference, complicated transmission power control (TPC) is not required. A modem of the AS-CDMA has been designed and implemented for the Japanese 2.4 GHz industrial, scientific and medical (ISM) band. Using the implemented modem, the degradation of Eb/N0 from the theoretical limit is 1.0 dB at a bit error rate (BER) of 10-3. Under 2-user environment, the degradation of carrier-to-noise ratio (CNR) is 0.5 dB at a BER of 10-3 when the desired-to-undesired signal ratio (DUR) is -20.3 dB. We have evaluated BER performances in cases of varying carrier frequency offset and median DUR with computer simulation. Under 8-user environment, at the carrier frequency offset of 0.3 ppm, the BER with the DUR of -16 dB is found to be 10-3. Using the AS-CDMA with a 4-step open-loop TPC technique, the design of intracell uplink is available.

This paper proposes constructive timing-violation (CTV) and evaluates its potential. It can be utilized both for increasing clock frequency and for reducing energy consumption. Increasing clock frequency over that determined by the critical paths causes timing violations. On the other hand, while supply voltage reduction can result in substantial power savings, it also causes larger gate delay and thus clock must be slow down in order not to violate timing constraints of critical paths. However, if any tolerant mechanisms are provided for the timing violations, it is not necessary to keep the constraints. Rather, the violations would be constructive for high clock frequency or for energy savings. From these observations, we propose the CTV, which is supported by the tolerant mechanism based on contemporary speculative execution mechanisms. We evaluate the CTV using a cycle-by-cycle simulator and present its considerably promising potential.

We present a new technique for hierarchical intellectual property (IP) protection using partially-mergeable cores. The proposed core partitioning technique guarantees 100% protection of critical-IP, while simplifying test generation for the logic that is merged with the system. Since critical-IP is tested using BIST, the controllability and observability of internal lines in the core are enhanced, and test application time is reduced. Case studies using the ISIT-DLX and Picojava processor cores demonstrate the applicability of our technique.

A parallel program with a fixed degree of parallelism cannot be executed efficiently, or at all, by a parallel computer with a different degree of parallelism. This will cause a problem in the distribution of software applications in the near future when parallel computers with various degrees of parallelism will be widely used. In this paper we propose a way to make the machine code of the programs parallelism-independent, i.e. executable in minimum time on parallel computers with any degree of parallelism. We propose and evaluate three parallelism-independent scheduling algorithms for direct acyclic graphs (DAGs) of tasks with non-uniform execution times. To prove their efficiency, we performed simulations both with random DAGs and DAGs extracted from real applications. We evaluate them in terms of schedule length, computation time and size of the scheduled program. Their results are compared to those of the traditional CP/MISF algorithm which is used separately for each number of processors.

We have designed a 32-bit RISC microprocessor with 16-/32-bit fixed-point DSP functionality. This processor, called YD-RISC, combines both general-purpose microprocessor and digital signal processor (DSP) functionality using the reduced instruction set computer (RISC) design principles. It has functional units for arithmetic operation, digital signal processing (DSP) and memory access. They operate in parallel in order to remove stall cycles after DSP or load/store instructions, which usually need one or more issue latency cycles in addition to the first issue cycle. High performance was achieved with these parallel functional units while adopting a sophisticated five-stage pipeline structure. The pipelined DSP unit can execute one 32-bit multiply-accumulate (MAC) or 16-bit complex multiply instruction every one or two cycles through two 17-b 17-b multipliers and an operand examination logic circuit. Power-saving techniques such as power-down mode and disabling execution blocks allow low power consumption. In the design of this processor, we use logic synthesis and automatic place-and-route. This top-down approach shortens design time, while a high clock frequency is achieved by refining the processor architecture.

This paper is concerned with a comparative study of the accepting powers of deterministic, Las Vegas, self-verifying nondeterminisic, and nondeterministic (simple) multihead finite automata. We show that (1) for each k 2, one-way deterministic k-head (resp., simple k-head) finite automata are less powerful than one-way Las Vegas k-head (resp., simple k-head) finite automata, (2) there is a language accepted by a one-way self-verifying nondeterministic simple 2-head finite automaton, but not accepted by any one-way deterministic simple multihead finite automaton, (3) there is a language accepted by a one-way nondeterministic 2-head (resp., simple 2-head) finite automaton, but not accepted by any one-way self-verifying nondeterministic multihead (resp., simple multihead) finite automaton, (4) for each k 1, two-way Las Vegas k-head (resp., simple k-head) finite automata have the same accepting powers as two-way self-verifying nondeterministic k-head (resp., simple k-head) finite automata, and (5) two-way Las Vegas simple 2-head finite automata are more powerful than two-way deterministic simple 2-head finite automata.

We propose a mechanism to facilitate the development of component-based mobile applications with adaptive behaviors. The design principles and communication patterns of legacy software systems will greatly change in a forthcoming environment, where a variety of computing devices become embedded in home and office environments, users move around with/without portable computing devices, and all the devices are interconnected through wired/wireless networks. In the proposed mechanism, Improvised Assembly Mechanism (IAM), we realize functionality to compose an application in an ad hoc manner and to achieve the adaptation of applications by adding, replacing, supplementing, and relocating components at system runtime according to various environmental changes such as the locational changes of computing devices and users. The mechanism is implemented as a built-in functionality of the Soul component, which is one of the fundamental elements in the Possession model.

This paper describes an improved multiresolution telescopic search algorithm (MRTlcSA) for block-matching motion estimation. The algorithm uses images with full and reduced bit resolution, and uses motion-track and adaptive-search-window strategies. Simulation results show that the proposed algorithm has low computational complexity and achieves good image quality. We have developed a systolic-architecture-based search engine that has split data paths. In the case of low bit-resolution, the throughput is increased by enhancing the operating parallelism. The new motion estimator works at a low clock frequency and a low supply voltage, and therefore has low power consumption.

In this paper, an architecture of multi-threaded processor for embedded systems is proposed and evaluated comparing with other processors for embedded systems. The experimental results show the trade-off of hardware costs and execution times among processors. Taking proposed multi-threaded processor into account as an embedded processor, design space of embedded systems are enlarged and more suitable architecture can be selected under some design constraints.

In this paper, we propose a mathematical model for one-dimensional finite linear cellular automata and show connections between our model and the classical one. We then demonstrate, through some examples, that our model is a useful tool for analyzing one-dimensional finite linear cellular automata. We also extend this model to the D-dimensional case and give an algebraic characterization for it.

We formalize a model of "demonstration of program result-correctness," and investigate how to prove this fact against possible adversaries, which naturally extends Blum's theory of program checking by adding zero-knowledge requirements. The zero-knowledge requirements are universal for yes and no instances alike.

In this paper we have presented a new method for seismic signal analysis, based on the ARMA modeling and a fuzzy LVQ clustering method. The objective achieved in this work is to sense the changes made naturally or artificially on the seismogram signal, and to detect the sources, which caused these changes (seismic classification). During the study, we have also found out that the model is sometimes capable to alarm the further seismic events just a little time before the onset of those events (seismic prediction). So the application of the proposed method both in seismic classification and seismic prediction are studied through the experimental results. The study is based on the background noise of the teleseismic short period recordings. The ARMA model coefficients are derived for the consecutive overlapped windows. A base model is then generated by clustering the calculated model parameters, using the fuzzy LVQ method proposed by Nassery & Faez in [19]. The time windows, which do not take part in [19] model generation process, are named as the test windows. The model coefficients of the test windows are then compared to the base model coefficients through some pre-defined composition rules. The result of this comparison is a normalized value generated as a measure of similarity. The set of the consecutive similarity measures generate above, produce a curve versus the time windows indices called as the characteristic curves. The numerical results have shown that the characteristic curves often contain much vital seismological information and can be used for source classification and prediction purposes.

This paper describes two competitive learning algorithms from the viewpoint of deleting mechanisms of weight (reference) vectors. The techniques are termed the adaptivity and sensitivity deletions participated in the criteria of partition error and distortion error, respectively. Experimental results show the effectiveness of the proposed approaches in the average distortion.