In this paper, we consider the protein structure alignment problem, which is a very important problem in molecular biology. Since an outline of protein structure is represented by a sequence of points in three-dimensional space, this problem is defined as the following geometric pattern matching problem: given two point sequences P and Q in three-dimensions and a real number δ > 0, find a maximum-cardinality set of point pairs such that the distance between each pair is at most δ under the condition that any translation and rotation can be applied to P. Since it is very difficult to solve this problem exactly, we consider algorithms that solve it approximately. We propose three algorithms: BASICALIGN, RANDALIGN and FRAGALIGN whose worst case time complexities are O(n8), O((n7/k3) polylog(n)) and O(n4) respectively, where n denotes the size of larger input structure and k denotes the minimum size of the alignment to be obtained. All of these have the following common framework: a series of initial superpositions are computed; for each of such superpositions, a rough alignment is first computed using a dynamic programming technique, and then it is refined through an iterative improvement procedure which also uses dynamic programming; the best alignment among them is selected as an output. The difference among three algorithms lies in the methods of finding initial superpositions. BASICALIGN, RANDALIGN and FRAGALIGN use exhaustive search, random sampling technique and fragment-based search, respectively. We prove guaranteed approximation ratios (in the sense of distances between point pairs) for theoretical versions of BASICALIGN and RANDALIGN. Practical versions of RANDALIGN and FRAGALIGN were implemented and compared with a previous algorithm using real protein structure data. The experimental results show that FRAGALIGN is best among them and it outputs good alignments quickly.

In this paper, we introduce a parallel algorithm for parsing context-free languages. Our algorithm can handle arbitrary context-free grammars since it is based on Earley's algorithm. Our algorithm can operate on any loosely coupled multiprocessor which can provide a topology of a one-way ring. Our algorithm uses p processors to parse an input string of length n where 1 p n. It is shown that our algorithm requires O(n3/p) time. The algorithm uses a simple job allocation strategy. However, it achieves high load balancing and uses the processors efficiently.

A current controlled CMOS output driver was designed by using a temperature-insensitive reference current generator. It eliminates the need for overdesign of the driver transistor size to meet the delay specification at high temperature. Comparison with the conventional CMOS output driver with the same transistor size showed that the ground bounce noise was reduced by 2.5 times and the delay time was increased by 1.4 times, at 25 for 50pF load. The temperature variations of the DC pull-up and pull-down currents of the new output driver were 4% within the temperature range from -15 to 125 compared to the variations of 40 and 60% for pull-up and pull-down respectively for the conventional output driver. The temperature insensitivity of the reference current generator was achieved by multiplying two current components. one which is proportional to mobility and the other which is inversely proportional to mobility, by using a CMOS square root circuit. The temperature variation of the DC output current of the reference current generator alone was 0.77% within the entire temperature range from -15 to 125.

To evaluate DRAM memory-cell data retention characteristics, measuring the leakage current of the individual memory-cell is important. However, the leakage current of a DRAM memory-cell cannot be measured directly, because its value is on the order of femtoamperes. This paper describes a Plate Bumping (PB) method that can measure the leakage current of a specific memory-cell using the relationship between the shifted value of memory-cell-plate potential and the retention period. By using the PB method, it can be confirmed that the leakage current of the short-retention cell (bad cell) depends on its storage-node potential. With regards to cells with "0" data stored in them ("0" cells), it appears that the relaxed junction biasing (RJB) scheme which can extend refresh interval increases the number of misread "0" cells due to the lowering of the sense amplifier's sensing threshold.

A mechanism of an integrated switching system architecture where PS, CS, and ATM switching functions are integrated based on a hierarchical memory system concept is discussed. A packet buffering control mechanism, and practical random time-slot assignment mechanism for CS traffic, which are composed of multiple bearer rate data traffic are then described. The feasibility of the random time-slot assignment mechanism is also confirmed by a practical experimental system using VLSI technology, particularly, content addressable memory (CAM) technology. The required queuing delay between the nodes for the corresponding call set up procedure is also shown and its application is clarified. For practical digital networks that provide various types of data communications including voice, data, and video services, it is highly desirable to evaluate the transmission efficiency of integrating packet switching (PS) type non-real time traffic and circuit switching (CS) type real time traffic. Transmission line utilization improvement is expected when the random time-slot assignment and the movable boundary scheme on a TDM (Time Division Multiplexing) data frame are adopted. The corresponding control procedure by signaling between switching nodes is also examined.

In order to highlight a rapid progress attained in the field of millimeter waves in Japan, this paper describes several key topics including transistors, integrated circuits, planar antennas, millimeter wave photonics, and others.

This paper gives an overview of the research and development trends in millimeter-wave short-range application systems, such as communication systems and sensing systems, in Japan and other countries. Frequency management trends are also described. Major research and development efforts in Japan have currently been concentrated on the 59-64 GHz band. The first major achievement resulting from those efforts was the allocation of the 60-61 GHz band to the automotive radar systems. Test productions of automotive radars in this band have already started. Further technological developments to reduce the cost and size of radar products are, however, required in order for such radar systems to be widely used. Development of broadband wireless LAN systems has also been intensively made in the 60 GHz band. In addition, technical issues related to standardization of millimeter-wave wireless LAN systems in the 60 GHz band have been examined at the Association of Radio Industries and Businesses. The application areas of millimeter-waves in the future are expected to become more diverse. Research and development trends of future application systems, such as broadband mobile communication systems and imaging radar systems, are also described. These systems require more advanced millimeter-wave technologies, such as smart antennas, low power-consumption devices, and more sensitive detectors. Efforts to develop these technologies must be strengthened.

In the envisaged Universal Mobile Telecommunications System (UMTS), the satellite component will have to provide services to mobile or, in some cases, hand held terminals with a required grade of user co-operation and link availability in various communication environments. This may require the capability of the satellite link to cope with more severe multipath environments than those for which mobile satellite links are most frequently designed (maritime or open rural applications); unfortunately, when the mobile radio channel is affected by multipath and a coherent demodulation is chosen, the phase synchronisation can be a critical issue. To satisfactorily deal with the arising difficulties, a dual channel demodulation is a viable and efficient strategy for the forward link, since only one common pilot channel is needed in this case. If the same dual channel demodulation is considered for the return link, an unacceptable capacity reduction may result. In this paper, some synchronisation strategies are analysed and an efficient dual channel demodulation scheme is proposed for the return link of a satellite DS-CDMA mobile communication system; furthermore, the impact on the overall system performance or capacity is analysed.

For quasi millimeter-wave and millimeter-wave high-speed wireless communications over wireless LANs and wireless ATMs, narrow beam antennas have been shown to provide high transmission quality by suppressing the troublesome multipath effect. However, the diameter of sector antennas needed to create the narrow beams rapidly increases with the sector number. In addition, the cylindrical shape of typical sector antennas does not suit portable terminals. This paper shows a methodology for designing planar sector antennas that overcomes these problems. The proposed antenna uses two kinds of beams and the antenna gains are equalized in all sectors. The antenna is developed as a 4-beam subarray fed by a planar Butler matrix circuit. The design method of the subarray and an evaluation of its characteristics in the 20 GHz band are discussed.

A requirement specification acquisition method combined with hypothesis-based reasoning and model reasoning is proposed for obtaining service specifications from the ambiguous and/or incomplete requirement specifications of communications services. Errors at an early stage of software development cost more to debug than those at a later stage. Specification acquisition is the most upstream development process. Nevertheless, the system support for specification acquisition is delayed compared with other development phases.' Users do not always have precise requirements. It is therefore inevitable that user requirements contain ambiguities, insufficiencies and even contradictions. Considering this, it is indispensable to support a specification completion method that derives service specifications from such problem requirements. This paper proposes a combined method to obtain consistent and complete specifications from such problem requirements. Communications service specifications can be described by specifying terminal behaviors which can be recognized from outside the communications system(s). Such specifications are described by a rule-based language. Requirement specifications usually have components that are ambiguous, incomplete, or even contradictory. They appear as rule description and/or missing rules. From such requirements, service specifications are obtained by using hypothesis-based reasoning on input requirements and existing service specifications. When existing specifications cannot be used to obtain complementary specifications, a communications service model is used to propose new rules. The proposed methods are implemented as a part of a communications software development system. The system enables non-experts in communications systems to define their own service specifications.

In this paper, we propose a camera calibration method that estimates both intrinsic parameters (perspective and distortion) and extrinsic parameters (rotational and translational). All camera parameters can be determined from one or more images of planar pattern consists of parallelogramatic grid points. As far as the pattern can be visible, the relative relations between camera and patterns are arbitrary. So, we have only to prepare a pattern, and take one or more images changing the relative relation between camera and the pattern, arbitrarily; neither solid object of ground truth nor precise z-stage are required. Moreover, constraint conditions that are imposed on rotational parameters are explicitly satisfied; no intermediate parameter that connected several actual camera parameters are used. Taking account of the conflicting fact that the amount of distortion is small in the neighborhood of the image center, and that small image has poor clues of 3-D information, we adopt iterative procedure. The best parameters are searched changing the size and number of parallelograms selected from grid points. The procedure of the iteration is as follows: The perspective parameters are estimated from the shape of parallelogram by nonlinear optimizations. The rotational parameters are calculated from the shape of parallelogram. The translational parameters are estimated from the size of parallelogram by least squares method. Then, the distortion parameters are estimated using all grid points by least squares method. The computer simulation demonstrates the efficiency of the proposed method. And the results of the implementation using real images are also shown.

It is well known that extracting parallel loops plays a significant role in designing parallelizing compilers. The execution efficiency of a loop is enhanced when the loop can be executed in parallel or partial parallel, like a DOALL or DOACROSS loop. This paper reports on the practical parallelism detector (PPD) that is implemented in PFPC (a portable FORTRAN parallelizing compiler running on OSF/1) at NCTU to concentrate on finding the parallelism available in loops. The PPD can extract the potential DOALL and DOACROSS loops in a program by invoking a combination of the ZIV test and the I test for verifying array subscripts. Furthermore, if DOACROSS loops are available, an optimization of synchronization statement is made. Experimental results show that PPD is more reliable and accurate than previous approaches.

A three-terminal quantum device utilizing photon-assisted tunneling in a multilayer structure is proposed and analyzed in terms of its high frequency amplification characteristics. The operation principle of this device includes photonassisted tunneling at the input, formation of a propagating charge wave due to the beat of tunneling electrons and its acceleration, and radiation of electromagnetic waves at the output. Analysis of these operations, discussion of similarities and dissimilarities to classical klystrons, and estimation of the power gain and its frequency dependence are given. A simple example demonstrates that amplification up to the terahertz frequency range is possible using this device.

This paper proposes a method for deriving protocol specifications in a communicating processes model, in which protocol specifications are modeled by finite automata communicating through the LOTOS multirendezvous mechanism. Message sequence charts (MSCs) are used for the derivation inputs. MSCs are graphical representations of traces of protocols and are suitable for defining requirements. Since an MSC usually covers only partial behavior, several mechanisms for composing a large number of MSCs from element MSCs have been proposed. These mechanisms, however, are not adequate: Either their input language for MSCs is not powerful enough, or they need some information on protocol specifications (i.e., implementation specifications). This paper proposes the use of regular expressions over MSCs to fully define protocols. The proposed language is powerful enough to describe protocols in the communicating processes model. A derivation algorithm based on a finite automata construction algorithm that accept sets expressed by regular expressions is presented. Because the derived protocols sometimes include unrequired behavior, an algorithm for detecting unrequired behavior is also presented.

Analog computation is a processing method that solves problems utilizing an analogy of a physical system to the problem. As it is based on actual physical effects and not on symbolic operations, it is therefore a promising architecture for quantum processors. This paper presents an idea for relating quantum structures with analog computation. As an instance, a method is proposed for solving an NP-complete (nondeterminis-tic polynomial time complete) problem, the three-color-map problem, by using a quantum-cell circuit. The computing process is parallel and instantaneous, so making it possible to obtain the solution in a short time regardless of the size of the problem.

Fairness is one of the important notion for programming language, such as process algebras like CCS, that includes concurrency (or parallelism) and nondeterminism. This ensures that while repeatedly choosing among a set of alternatives, no alternative will be postponed forever. However, the fairness does not mention at what frequency these alternatives are selected. In this paper, we propose a quantitative fairness, which is called economic-oriented fairness, to each alternatives. This fairness ensures that the expected number of selection for each alternatives are same. We give a condition for probability assignment of selection of each alternative to be satisfied for economic-oriented fairness. First we show a simple probability assignment rule. In this assignment, between any two alternatives, if an alternative is selected n times and the other m times then the probability to select the former alternative is (m + 1)/(n + 1) times the probability for the latter. We prove that this assignment satisfies the condition of economic-oriented fairness. For a model of the economic-oriented fairness, we adopt a probabilistic process algebra. Finally, we elaborate with two process models of the economic-oriented fairness. The first one is a server and client model, where each client communicates only with the server, but not among them. In this model, the expected number of communication by each client are equal. The second model considers communication between two processes. In practice, a process has several subprocesses. Each subprocess communicates via a communication port, In the second model, there is economic-oriented fairness where the expected number of communications via each communication port are equal.

For reduction of computational complexity in the IA algorithm, the thinned-out IA algorithm in which only one step size is updated every iteration is proposed and is complementarily switched with the HA algorithm according to the convergence. The switching is determined by using the gradient of the error signal power. These are investigated through the computer simulations.

This paper proposes a novel Doppler frequency shift compensation technique to achieve terrestrial and low earth orbit (LEO) satellite dual mode DS/CDMA terminals robust to high Doppler shift and multipath fading. In order to satisfy the requirements of wide dynamic range and high accuracy simultaneously, the proposed scheme employs two stage compensation scheme, i.e., coarse compensation to keep dynamic range of about 100 kHz and fine compensation to satisfy its resolution of about 30 Hz, using block demodulation technique. Computer simulation results show that the proposed scheme can sufficiently compensate for the offset frequency up to the range of about 100 kHz at the terrestrial and LEO satellite combined mobile communication systems.

The multichannel distortions of direct modulated laser diode were studied from the view point of rate equations. A novel technique for compensating the composite second order distortion (CSO) was proposed. Meanwhile, the related calibration procedures were indicated. After the compensation, 10 dB improvement in CSO was obtained

The printed dipole on a semi-infinite substrate is investigated. The solution is based on the moment method in the Fourier transform domain. We analyze far-field and near-field radiation patterns for a printed dipole. Therefore, we make radiation fields clear.