Search

With the recent development of semiconductor integration technology, the amount of data that must be handled in the layout design of VLSI is increasing rapidly. Even if the improvement of the processing speed of the computer in the future is considered, it is desired to develop a high-speed layout algorithm compared to the conventional method. This paper discusses the k (> 2)-way graph partitioning problem, which is one of the most basic problems concerning the layout design. A parallel algorithm is proposed. The general method to solve this problem has been to apply hierarchically the two-way graph partitioning algorithm. In this method, the algorithm can easily be executed in parallel by operating a number of processors at each hierarchy. A problem then is the efficiency of the processor and the computation time. This paper considers the k-way graph partitioning and proposes a new method called nonhierarchical k-way graph partitioning, aiming at the education of the computation time by parallel processing. In general, it is considered difficult to improve the speed sufficiently by the parallel processing, while maintaining the same accuracy of the solution as that of the sequential algorithm. In this paper, the effectiveness of the proposed algorithm is shown by a simulation experiment on the sequential computer. [ABSTRACT FROM AUTHOR]

In efforts toward the realization of quantum computers, there have been many proposals to implement controlled NOT gates between quantum bits (qubits). However, the number of quanta in the experimentally realized system has been at most two. Because it is difficult to cope with both the realization of the conditional interaction (e.g., huge nonlinear interaction) between the quanta, and the maintenance of quantum coherence for a sufficient time, the realization of quantum logic gates using several quanta may be difficult in the near future. In this paper, a new method which implements a quantum algorithm using linear optics and single photons is described. This method does not need any huge nonlinearity. Hence, it is practical with today's technology and will be one of the useful physical test beds for the quantum algorithms. The optical implementation of the Deutsch–Jozsa algorithm with a 4-bit input is proposed, and the mechanism is explained. As one instance of the recent progress of our project, an experiment of single-photon interference using parametric fluorescence with highly stabilized interferometer system is reported. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 84(11): 52–60, 2001 [ABSTRACT FROM AUTHOR]

This paper presents a new encoding algorithm based on the face hypercube embedding for satisfying given input constraints. The algorithm works for a constraint relation matrix derived from the sets of the input symbols grouped for each output symbol independently and finds the encoding through row-by-row (group-by-group) cover assignment. A cover is found by the extension of a core cover generated from the magnitude estimations and adjacent relations of the currently known covers. Each cover is formed to be a single cube; and, if it is unsuccessful for specified code length, then the encoding length is extended. The experimental results indicate that this encoding technique has advantages over well-known existing methods in the quality of encoding. [ABSTRACT FROM AUTHOR]

SPICE-type general-purpose circuit simulators are used widely as a support tool for circuit design. It often happens, however, that the dc operating-point analysis does not converge. To cope with such a situation, various approaches have been proposed based on continuation methods with the global convergence property, but these have yet to come to the stage of practical application to large-scale circuits. This paper proposes a practical algorithm which can be implemented on the general-purpose circuit simulators with modified nodal formulation, for determining the dc operating-point of large-scale circuits. As the first step, the concept of "modified cut-set analysis" is introduced and some properties of the modified nodal equation are presented. Then it is shown, in practical circuits, that the convergence of the algorithm is theoretically guaranteed. The proposed algorithm is then implemented on an existing general-purpose circuit simulator and applied to a bipolar analog LSI to demonstrate its effectiveness. For the LSI circuit formulated in 18,553 modified nodal equations, the dc operating point was determined in 270 minutes using an IBM RS6000-550. [ABSTRACT FROM AUTHOR]

Various studies on learning rules for neural networks have been done. However, most of those do not consider the hardware implementation, which is a great drawback in the LSI implementation of neural networks with learning capability. From such a viewpoint, this paper proposes a self-organizing learning rule by modifying the Hebbian learning rule. This rule can be implemented easily on an analog VLSI chip as an on-chip learning rule. The self-organizing ability of the system is verified by simulation experiments. It is shown from the experiment that the learning speed is improved by a factor of 2 to 3, and it is possible to avoid the sudden termination of the learning and the divergence of the synaptic weights. [ABSTRACT FROM AUTHOR]

When two-dimensionally structured teaching materials are rearranged into a one-dimensional sequence according to the teaching strategy, it is called teaching task sequence. The teaching is executed by presenting the tasks in the order in this sequence. This paper considers the situation where a task arises in the teaching task sequence whereby the learner cannot understand and proposes an algorithm to generate the review task sequence so that the learner can understand the task as fast as possible. The review task sequence is derived from learning progress and the structure of the teaching material. The directional connection called influential strength is introduced between the nodes in the teaching material structure graph, and the structure of the teaching material composed of N nodes is described by square influence matrix of N-th order with the influential strength as the element. The review task sequence is a real-valued sort, which is obtained by operating the teaching record matrix to the influence matrix representing the tree structure, not by tracing the directed edges of the graph. [ABSTRACT FROM AUTHOR]