The Hilbert curve is one of the simplest curves which pass through all points in a space. Many researchers have worked on this curve from the engineering point of view, such as for an expression of two-dimensional patterns, for data compression in an image or in color space, for pseudo color image displays, etc. A computation algorithm of this curve is usually based on a look-up table instead of a recursive algorithm. In such algorithm, a large memory is required for the path look-up table, and the memory size becomes proportional to the image size. In this paper, we present an implementation of a fast sequential algorithm that requires little memory for two and three dimensional Hilbert curves. Our method is based on some rules of quad-tree traversal in two dimensional space, and octtree traversal in three dimensional space. The two dimensional Hilbert curve is similar to the scanning of a DF (Depth First) expression, which is a quad-tree expression of an image. The important feature is that it scans continuously from one quadrant, which is obtained by quad tree splitting, to the next adjacent one in two dimensional space. From this point, if we consider run-lengths of black and white pixels during the scan, the run-lengths of the Hilbert scan tend to be longer than those of the raster scan and the DF expression scanning. We discuss the application to data compression using binary images and three dimensional data.

The subject of the paper is to propose an O(|V|+|E|) algorithm for the 3-edge-connectivity augmentation problem (UW-3-ECA) defined by "Given an undirected graph G0=(V,E), find an edge set E of minimum cardinality such that the graph (V,EE ) (denoted as G0+E ) is 3-edge-connected, where each edge of E connects distinct vertices of V." Such a set E is called a solution to the problem. Let UW-3-ECA(S) (UW-3-ECA(M), respectively) denote UW-3-ECA in which G0+E is required to be simple (G0+E may have multiple edges). Note that we can assume that G0 is simple in UW-3-ECA(S). UW-3-ECA(M) is divided into two subproblems (1) and (2) as follows: (1) finding all k-edge-connected components of a given graph for every k3, and (2) determining a minimum set of edges whose addition to G0 result in a 3-edge-connected graph. Concerning the subproblem (1), we use an O(|V|+|E|) algorithm that has already been existing. The paper proposes an O(|V|+|E|) algorithm for the subproblem (2). Combining these algorithms makes an O(|V|+|E|) algorithm for finding a solution to UW-3-ECA(M). Furthermore, it is shown that a solution E to UW-3-ECA(M) is also a solution to UW-3-ECA(S) if |V|4, partly solving an open problem UW-k-ECA(S) that is a generalization of UW-3-ECA(S).

Copper contamination behavior is studied, depending on the pH level, conductivity type P or N of a silicon substrate, and contamination method of copper. If the pH level of a copper containing solution is adjusted by using ammonia, copper atoms and ammonia molecules produce copper ion complexes. Accordingly, the amount of copper adsorption on the substrate surface is decreased. When N-type silicon substrates are contaminated by means of copper containing solutions, copper atoms on the surfaces diffuse into bulk crystal even at room temperature. But for P-type silicon substrates, copper atoms are transferred into bulk crystal only after high temperature annealing. In the case of silicon substrates contaminated by contact with metallic copper, no copper atom diffusion into bulk crystal was observed. The above mentioned copper contamination behavior can be explained by the charge transfer interaction of copper atoms with silicon substrates.

We describe an approach to describe moving pictures in terms of their structural properties for video editing, video indexing, and video coding. The description contains 2D shape, motion, spatial relation, and relative depth of each region. To obtain the description, we develop the incremental segmentation scheme which includes dynamic occlusion analysis to determine relative depths of several objects. The scheme has been designed along the analysis-by-synthesis" approach, and uses a sequence of images to estimate object boundaries and motion information successively/incrementally. The scheme consists of three components: motion estimation, prediction with dynamic occlusion analysis, and update of the segmentation results. By combining the information from extended (longer) image sequences, and also by treating the segmentation and dynamic occlusion analysis simultaneously, the scheme attempts to improve successively over time the accuracy of the object boundary and motion estimation.

In this paper, we propose an algorithm of O(|V|min{k,|V|,|A|}|A|) time complexity for finding all k-edge-connected components of a given digraph D=(V,A) and a positive integer k. When D is symmetric, incorporating a preprocessing reduces this time complexity to O(|A|+|V|2+|V|min{k,|V|}min{k|V|,|A|}), which is at most O(|A|+k2|V|2).

This paper presents an optimal constraint graph generation algorithm for graph-based one-dimensional layout compaction. The first published algorithm for this problem was the shadow-propagation algorithm. However, without sophisticated implementation of a shadow-front, complexity of the algorithm could fall into O(n2), where n is the number of layout objects. Although our algorithm, called the enhanced plane-sweep based graph generation algorithm, is an extension of the shadow-propagation algorithm, such a drawback is resolved by introducing an enhanced plane-sweep technique. The algorithm maintains multiple shadow-fronts simultaneously by storing them in a work-list called previous-boundary. Since a balanced search tree is selected for implementation of the worklist, total complexity of the algorithm is O(n log n) which is optimal. Experimental results show that the enhanced plane-sweep based graph generation algorithm runs in almost linear time with respect to the number of layout objects and is faster than the perpendicular plane-sweep algorithm which is also optimal in terms of time complexity.

In this paper, we discuss secure protocols for shared computation of algorithms associated with digital signature schemes based on discrete logarithms. Generic solutions to the problem of cooperatively computing arbitraty functions, though formally provable according to strict security notions, are inefficient in terms of communication--bits and rounds of interaction--; practical protocols for shared computation of particular functions, on the other hand, are often shown secure according to weaker notions of security. We propose efficient secure protocols to share the generation of keys and signatures in the digital signature schemes introduced by Schnorr (1989) and ElGamal (1985). The protocols are built on a protocol for non-interactive verifiable secret sharing (Feldman, 1987) and a novel construction for non-interactively multiplying secretly shared values. Together with the non-interactive protocols for shared generation of RSA signatures introduced by Desmedt and Frankel (1991), the results presented here show that practical signature schemes can be efficiently shared.

The Memory-Based Reasoning (MBR) is one of the mainstay approaches in massively parallel artificial intelligence research. However, it has not been explored from the viewpoint of hardware implementation. This paper demonstrates high robustness of the MBR, which is suitable for hardware implementation using Wafer Scale Integration (WSI) technology, and proposes a design of WSI-MBR hardware. The robustness is evaluated by a newly developed WSI-MBR simulator in the English pronunciation reasoning task, generally known as MBRTalk. The results show that defects or other fluctuations of device parameters have only minor impacts on the performances of the WSI-MBR. Moreover, it is found that in order to get higher reasoning accuracy, the size of the MBR database is much more crucial than the computation resolution. These features are proved to be caused by the fact that MBR does not rely upon each single data unit but upon a bulk data set. Robustness in the other MBR tasks can be evaluated in the same manner as discussed in this paper. The proposed WSI-MBR processor takes advantage of benefits discovered in the simulation results. The most area-demanding circuits--that is, multipliers and adders--are designed by analog circuits. It is expected that the 1.7 million processors will be integrated onto the 8-inch silicon wafer by the 0.3 µm SRAM technology.

A discrete-time neuron model having a refractory period and containing a binary hysteresis output function is introduced. A detailed mathematical analysis of the output response is carried out and the necessary and sufficient condition which a sequence must satisfy in order to be designated as a periodic response of the neuron model under a constant or periodic stimulation is given.

We have developed a new functional MOS transistor called Neuron MOSFET (abbreviated as neuMOS or νMOS) which simulates the function of biological neurons. The new transistor is capable of executing a weighted sum calculation of multiple input signals and threshold operation based on the result of weighted summation, all in the voltage mode at a single transistor level. By utilizing its neuron-like very powerful functional capability, various circuits essential for multiple-valued logic operation have been designed using quite simple circuit configurations. The circuit designs for data conversion between the multivalued and binary logic systems and for generating universal literal functions are described and their experimental verifications are presented. One of the most important features of νMOS multivalued lagic circuit is that the circuit operates basically in the voltage mode, thus greatly reducing the power dissipation as compared to the conventional current mode circuitry. This is indeed most essential in implementing multivalued logic systems in ultra large scale integration. Another important feature of νMOS design is in its flexibility of implementing logic functions. The functional form of a universal literal function, for instance, can be arbitrarily altered by external signals without any modifications in its hardware configuration. A circuit representing multiple-valued multithreshold functions is also proposed.

Low-sensitivity digital filters are required for accurate signal processing. Among many low-sensitivity digital filters, a method using complex allpass circuits is well-known. In this paper, a new synthesis of complex allpass circuits is proposed. The proposed synthesis can be realized more easily either only in the z-domain or in the s-domain than conventional methods. The key concept for the synthesis is based on the factorization of lossless scattering matrices. Complex allpass circuits are interpreted as lossless digital two-port circuits, whose scattering matrices are factored. Furthermore, in the cases of Butterworth, Chebyshev and inverse Chebyshev responses, the explicit formulae for multiplier coefficients are derived, which enable us to synthesize the objective circuits directly from the specifications in the s-domain. Finally design examples verify the effectiveness of the proposed method.

A further study on a VLSI system compiler, named VEGA (VLSI Embodiment for General Algorithms), is presented. It maps a general digital signal processing algorithm onto a neo-systolic array, which is a VLSI oriented multiprocessor array. Highly complicated mapping problem is divided into subproblems such as modularization, operation grouping, processor placement, scheduling, control logic synthesis, and mask pattern generation. In this paper, the modularization technique is proposed which homogenizes all the operations of the processing algorithm to multiply-add operations. The processor placement algorithm to map processing algorithm onto a neo-systolic array so as to minimize data transfer time is also proposed.

Some problems in formal language theory are considered and are shown to be deterministic exponential time complete. They include the problems for a given context-free grammar G, a nondeterministic finite automaton M, a deterministic pushdown automaton MD, of determining whether L(G)L(M), and whether L(MD)L(M). Polynomial time reductions are presented from the pebble game problem, known to be deterministic exponential time complete, to each of these problems.

This paper describes a mixed mode circuit simulation by the direct and relaxation-based methods with dynamic network partitioning. For the efficient circuit simulation by the direct method, the algorithms with circuit partitioning and latency technique have been studied. Recently, the hierarchical decomposition and latency and their validities have been researched. Network tearing techniques enable independent analysis of each subnetwork except for the local datum nodes. Therefore, if the local datum nodes are also torn, each subnetwork is separated entirely. Since the network separation is based on relaxation approach, the implementation of the separation technique in the circuit simulation by the direct method corresponds to performing the mixed mode simulation by the direct and relaxation-based methods. In this paper, a dynamic "network separation" technique based on the tightness of the coupling between subnetworks is suggested. Then, by the introduction of dynamic network separation into the simulator SPLIT with hierarchical decomposition and latency, the mixed mode circuit simulator, which selects the direct method or the relaxation method and determines the block size of the latent circuit dynamically and suitably, is constructed.

Free choice nets are a class of Petri nets, which can represent the substantial features of systems by modeling both choice and concurrency. And in the modelling and design of a large number of concurrent systems, live and safe free choice nets (LSFC nets) have been explored their structural characteristics. On the other hand, state machine decomposable nets (SMD nets) are a class of Petri nets which can be decomposed by a set of strongly connected state machines (S-decomposition). State machine allocatable nets (SMA nets) are a well-behaved class of SMD nets. Of particular interest is the relation between free choice nets and SMA nets such that a free choice net has a live and safe marking if and only if the net is an SMA net. That is, the structure of an LSFC net is an SMA net. Recently, the structure of SMA net has been completely characterized by the authors based on an S-decomposition. In other words, a necessary and sufficient condition for a net to be an SMA net is obtained in terms of the net structure where synchronization between strongly connected state machine components (S-components) has been clarified. Unfortunately, it requires tremendous amount of time and spaces to decide a given net to be an SMA net by applying the condition directly. Moreover, there exist no efficient algorithm to decide the liveness and safeness of a given SMA net that lessens the usefulness of decomposition techniques. In this paper, we consider efficient polynomial order algorithms to decide whether a given net is a live and safe SHA net.

Two computational-geometric approaches to linear programming are surveyed. One is based on the prune-and-search paradigm and the other utilizes randomization. These two techniques are quite useful to solve geometric problems efficiently, and have many other applications, some of which are also mentioned.

This paper describes an automatic transistor model parameter generation technique for a circuit simulator which can take device geometry into account. An 'area factor' is used to generate model parameters for different transistor shapes; however, the conventional method could not reflect the actual geometry differences other than for the emitter area. This resulted in inaccurate model parameters and such parameters were not acceptable to accurately simulate circuits for RF ICs. The proposed technique uses actually measured parameters and process data for a reference transistor and generates the individual model parameters for different shape transistors. In this technique, the parasitic resistor values are calculated and fitted in place of directly extracting them from the measured data. This ensures a better estimate. The reference transistor is made sufficiently large to neglect measurement errors in generating the parasitic capacitors. Thus, the model parameters for a very small transistor can be generated accurately. The model generating procedure has been implemented as a pre-processor to SPICE. This technique enables a fast turn around for RF IC circuit design which uses various shape transistors.

Let C{c1, , cm} be a family of subsets of a finite set S{1, , n}, a subset S of S is a co-hitting set if S contains no element of C as a subset. By using an O((log n)2) time EREW PRAM algorithm for a maximal independent set problem (MIS), we show that a maximal co-hitting set for S can be computed on an EREW PRAN in time O(αβ(log(nm))2) using O(n2 m) processors, where αmax{|cii1, , n} and βmax{|djj1, , n} with dj{ci|jci}. This implies that if αβO((log(nm))k) then the problem is solvable in NC.

We propose a new type of Graph Rewriting Systems (GRS) that provide a theoretical foundation for using the reduction method which plays an important role on analyze network reliability. By introducing this GRS, several facts were obtained as follows: (1) We clarified the reduction methods of network reliability analysis in the theoretical framework of GRS. (2) In the framework of GRS, we clarified the significance of the completeness in the reduction methods. (3) A procedure of recognizing complete systems from only given rewriting rules was shown. Specially the procedure (3) is given by introducing a boundary graph (B-Graph). Finally an application of GRS to network reliability analysis is shown.

Complex filters are used to synthesize real filters in digital signal processing, but few in analog one. In this paper, we propose a leapfrog synthesis of complex analog filters. By shifting frequency response of an LCR network along the ω-axis, we have a complex filter with imaginary resistances, which is called an "LCRRi filter." The complex resonator is then used to simulate series- or parallel-arms of the LCRRi filter. We analyze nonideal properties of the complex resonator due to finite gain-bandwidth product of operational amplifiers and propose a compensation method to put a pole on correct location. Experimental results show good performance of the proposed method.