The aim of the paper is to design efficient bit-parallel algorithms for translating regular expressions into nondeterministic finite automata (NFAs). Let r be a regular expression over an alphabet Σ, and let n be the length of r and let m be the number of symbols of Σ occurring in r. Then we present bit-parallel algorithms for translating regular expressions into Glushkov automata (position automata) and follow automata using Thompson automata. For Glushkov automata, we will give an algorithm which runs in O(n+mm/W) time and space. For follow automata, we will give a randomized algorithm which runs in O(n+mm/W) expected time and O(n+mm/W) space. We rely on a W-bit uniform RAM for estimating the complexities of algorithms. Since the best known algorithms for these automata runs in O(n+m2) time and space, our algorithms achieve an almost W-fold speed-up.

Sequences with good correlation properties are widely used in engineering applications, especially in the area of communications. Among the known sequences, cyclotomic families have the optimal autocorrelation property. In this paper, we decide the cross-correlation function of the known cyclotomic sequences completely. Moreover, to get our results, the relations between the multiplier group and the decimations of the characteristic sequence are also established for an arbitrary difference set.

A historical overview of microoptomechatronics technologies is presented for positioning of microoptomechatronics, accompanied with a future view based on the current state of art nanotechnologies. How the technologies have been developed for realizing practical precision and information devices based on optics or photonics is also mentioned, citing a few examples.

Automatic detection of normal mammograms, as a "first look" for breast cancer, is a new approach to computer-aided diagnosis. This approach may be limited, however, by two main causes. The first problem is the presence of poorly separable "crossed-distributions" in which the correct classification depends upon the value of each feature. The second problem is overlap of the feature distributions that are extracted from digitized mammograms of normal and abnormal patients. Here we introduce a new Support Vector Machine (SVM) based method utilizing with the proposed uncrossing mapping and Local Probability Difference (LPD). Crossed-distribution feature pairs are identified and mapped into a new features that can be separated by a zero-hyperplane of the new axis. The probability density functions of the features of normal and abnormal mammograms are then sampled and the local probability difference functions are estimated to enhance the features. From 1,000 ground-truth-known mammograms, 250 normal and 250 abnormal cases, including spiculated lesions, circumscribed masses or microcalcifications, are used for training a support vector machine. The classification results tested with another 250 normal and 250 abnormal sets show improved testing performances with 90% sensitivity and 89% specificity.

Under the broadband-ubiquitous environment, digital content creation/distribution will be the key factor to activating new industries. This paper first describes the impact of a broadband-ubiquitous environment on digital content creation/distribution; then it proposes new models for digital content creation/distribution businesses. In a broadband-ubiquitous environment, the key is creation of moving picture content; thus the paper describes a system that allows non-CG experts to make CG movies easily.

We propose and demonstrate wavelength-selectable filters available for 32 WDM channels using a micro-mechanically movable mechanism with miniaturized voice-coil motors (VCMs). A simple straight geometry with a staggered configuration is used to densely pack 32 in/out moving elements into a small space of 452411 mm. The elements are precisely arranged along a collimated beam between fiber facets to provide flat-top passbands centered at ITU-T grids while maintaining small total insertion losses of less than 2.5 dB for all elements. The driving condition of the VCMs is also optimized for quick dynamic response with typical settling time of less than 10 ms. A repetition test 106 repetitions per element showed good wavelength reproducibility to an accuracy of below 0.1 nm, indicating the switches are feasible for practical system equipped with reconfigurable functionality for the next generation of optical networks.

Concurrency is one of the most important issues in system-level design. Interleaving among parallel processes can cause an extremely large number of different behaviors, making design and verification difficult tasks. In this work, we propose a synchronization verification method for system-level designs described in the SpecC language. Instead of modeling the design with timed FSMs and using a model checker for timed automata (such as UPPAAL or KRONOS), we formulate the timing constraints with equalities/inequalities that can be solved by integer linear programming (ILP) tools. Verification is conducted in two steps. First, similar to other software model checkers, we compute the reachability of an error state in the absence of timing constraints. Then, if a path to an error state exists, its feasibility is checked by using the ILP solver to evaluate the timing constraints along the path. This approach can drastically increase the sizes of the designs that can be verified. Abstraction and abstraction refinement techniques based on the Counterexample-Guided Abstraction Refinement (CEGAR) paradigm are applied.

We demonstrate single electron counting on an alkanethiol-protected Au nanodot in a double-barrier tunneling structure by noncontact atomic-force spectroscopy (nc-AFS). The Coulomb step width dependence on the Au nanodot diameter is observed. Evaluation of fractional charge Q0 and contact potential difference by nc-AFS reveals a Vd-independent voltage shift due to Q0.

This paper describes a new method for the simulation environment for a custom processor. It is generally very hard to develop an accurate simulator for a custom processor rapidly, even if simple instruction-set-level simulator (ISS). The proposed method uses a field-programmable-gate-array emulator with a PCI interface and debugging GUI software on a PC. Since the emulator implements the processor design at the register-transfer or net-list level, the emulation results are almost the same as the results obtained with the actual processor. To support rich debugging functions like those provided by the conventional software simulator, we use a debugging buffer and break-control circuits. Experimental results show that a simulator constructed by the proposed method can be constructed within several hours and that it can break the processor operation at any specified point and observe the internal signals when the emulated system is running at 1-30 MHz. The accuracy of the constructed simulator is the same as that of RTL simulation and much higher than that of software ISS simulation. We show that we can provide a fast, accurate, and useful simulator for any processor design specified at the register-transfer level.

This paper presents an architecture and a synthesis method for compact numerical function generators (NFGs) for trigonometric, logarithmic, square root, reciprocal, and combinations of these functions. Our NFG partitions a given domain of the function into non-uniform segments using an LUT cascade, and approximates the given function by a quadratic polynomial for each segment. Thus, we can implement fast and compact NFGs for a wide range of functions. Experimental results show that: 1) our NFGs require, on average, only 4% of the memory needed by NFGs based on the linear approximation with non-uniform segmentation; 2) our NFG for 2x-1 requires only 22% of the memory needed by the NFG based on a 5th-order approximation with uniform segmentation; and 3) our NFGs achieve about 70% of the throughput of the existing table-based NFGs using only a few percent of the memory. Thus, our NFGs can be implemented with more compact FPGAs than needed for the existing NFGs. Our automatic synthesis system generates such compact NFGs quickly.

This paper presents an automated design of analog circuits starting with idealized elements. Our system first synthesizes circuits using idealized elements by a genetic algorithm (GA). GA evolves circuit topologies and transconductances of idealized elements to achieve the given specifications. The use of idealized elements effectively reduces search space and make the synthesis efficient. Second, idealized elements in a generated circuit are replaced by MOSFETs. Through the two processes, a circuit satisfying the given specifications can be obtained. The capability of this method was demonstrated through experiments of synthesis of a trans-impedance amplifier and a cubing circuit and benchmark tests. The results of the benchmark tests show the proposed CAD is more than 10 times faster than the CAD which does not use idealized elements.

Stability analysis is one of the most important problems in analysis of hybrid dynamical systems. In this paper, a computational method of Lyapunov functions is proposed for stability analysis of hybrid automata that have set-valued vector fields. For this purpose, a formulation of matrix-valued sums of squares is provided and applied to derive an LMI/LME problem whose solution yields a Lyapunov function.

This paper presents a design method to minimize energy of both functional units (FUs) and an interconnection network between FUs. To reduce complexity of the interconnection network, data transfers between FUs are classified according to FU types of operations in a data flow graph. The basic idea behind reducing the complexity of the interconnection network is that the interconnection resource can be shared among data transfers with the same FU type of a source node and the same FU type of a destination node. Moreover, an efficient method based on a genetic algorithm is presented.

A dynamically reconfigurable device is a device that can change its hardware configuration arbitrarily often in order to achieve the desired performance and functions. Since several tasks are executed on the device concurrently, scheduling of both task execution and reconfiguration is an important problem. In our model, the dynamically reconfigurable device is represented by a two-level hierarchical automaton, and execution of each periodic task is represented by a timed discrete event system. We propose a composition rule to get an automaton, which represents non-preemptive execution of periodic tasks on the dynamically reconfigurable device. We introduce a method to get a feasible execution sequence of tasks by using state feedback control.

Rapid eye motion, or so called saccade, is a very quick eye motion which always occurs regardless of our intention. Although the line of sight (LOS) with saccade tracking is expected to be used for a new type of computer-human interface, it is impossible to track it using the conventional video camera, because of its speed which is often up to 600 degrees per second. Vision Chip is an intelligent image sensor which has the photo receptor and the image processing circuitry on a single chip, which can process the acquired image information by keeping its spatial parallelism. It has also the ability of implementing the very compact integrated vision system. In this paper, we describe the vision chip architecture which has the capability of detecting the line of sight from infrared eye image, with the processing speed supporting the saccade tracking. The vision chip described here has the pixel parallel processing architecture, with the node automata for each pixel as image processing. The acquired image is digitized to two flags indicating the Purkinje's image and the pupil by comparators at first. The digitized images are then shrunk, followed by several steps of expanding by node automata located at each pixel. The shrinking process is kept executed until all the pixels disappear, and the pixel disappearing at last indicates the center of the Purkinje's image and the pupil. This disappearing step is detected by the projection circuitry in pixel circuit for fast operation, and the coordinates of the center of the Purkinje's image and the pupil are generated by the simple encoders. We describe the whole architecture of this vision chip, as well as the pixel architecture. We also describe the evaluation of proposed algorithm with numerical simulation, as well as processing speed using FPGA, and improvement in resolution using column parallel architecture.

Watson-Crick automata were introduced as a new computer model and have been intensively investigated regarding their computational power. In this paper, aiming to establish the relations among language families defined by Watson-Crick automata and the family of context-free languages completely, we obtain the following results. (1) F1WK = FSWK = FWK, (2) FWK = AWK, (3) there exists a language which is not context-free but belongs to NWK, and (4) there exists a context-free language which does not belong to AWK.

It is known that any chordal graph can be uniquely decomposed into simplicial components. Based on this fact, it is shown that for a given chordal graph, its automorphism group can be computed in O((c!n)O(1)) time, where c denotes the maximum size of simplicial components and n denotes the number of nodes. It is also shown that isomorphism of those chordal graphs can be decided within the same time bound. From the viewpoint of polynomial-time computability, our result strictly strengthens the previous ones respecting the clique number.

This paper describes a method for the classification of bank-notes. The algorithm has three stages, and classifies bank-notes with very low error rates and at high speeds. To achieve the very low error rates, the result of classification is checked in the final stage by using different features to those used in the first two. High-speed processing is mainly achieved by the hierarchical structure, which leads to low computational costs. In evaluation on 32,850 samples of US bank-notes, with the same number used for training, the algorithm classified all samples precisely with no error sample. We estimate that the worst error rate is 3.1E-9 for the classification statistically.

We performed numerical analyses on structure sensitive field emission properties of our proposing plasmon resonant photomixer (PRX) in the terahertz range. The photomixer incorporates doubly interdigitated grating strips for gate electrodes and a vertical resonator structure for realizing highly efficient terahertz emission even at room temperature. We investigated the dependence of total field emission properties of PRX's on their material and dimension parameters. Introduction of low-conductive gate electrodes and ac-coupled 2D periodic plasmon gratings with depleted connecting portions are effective for expanding its lower cutoff frequency. The cutoff frequency, which is around 1.0 THz in standard metal-gates configuration, is expanded to less than 500 GHz. The output intensity could also be amplified more than double. On the other hand, a shorter vertical cavity is effective for expanding its upper cutoff frequency, which is expanded close to vertical resonant frequency, while maintaining the lower cutoff frequency. The combination of these design rules can realize much broader bandwidth operation.

A second-order CMOS continuous-time bandpass filter with a tuneable 4-12 MHz center frequency (fc) is presented. The Design has been done by using a new second-order block which is based on Gm-C method. This Gm-C filter achieves a dynamic range of 30 dB for 1% IM3, and Q equal to 58 at 12 MHz, while dissipating only 10.5 mW from 3.3 V power supply in 0.35 µm CMOS process. The on-chip indirect automatic tuning circuit uses a phase-locked loop which sets filter center frequency to an external reference clock.