This paper reviews two topics of nonlinear system analysis done in Japan. The first half of this paper concerns with nonlinear system analysis through the nondeterministic operator theory. The nondeterministic operator is a set-valued or fuzzy set valued operator by K. Horiuchi. From 1975 Horiuchi has developed fixed point theorems for nondeterministic operators. Using such fixed point theorems, he developed a unique theory for nonlinear system analysis. Horiuchi's theory provides a fundamental view point for analysis of fluctuations in nonlinear systems. In this paper, it is pointed out that Horiuchi's theory can be viewed as an extension of the interval analysis. Next, Urabe's theory for nonlinear boundary value problems is discussed. From 1965 Urabe has developed a method of computer assisted existence proof for solutions of nonlinear boundary value problems. Urabe has presented a convergence theorem for a certain simplified Newton method. Urabe's theorem is essentially based on Banach's contraction mapping theorem. In this paper, reformulation of Urabe's theory using the interval analysis is presented. It is shown that sharp error estimation can be obtained by this reformulation. Both works discussed in this paper have been done independently with the interval analysis. This paper points out that they have deep relationship with the interval analysis. Moreover, it is also pointed out that these two works suggest future directions of the interval analysis.

It is of significantly importance in relation to the problem of diagnosis of deviation faults in linear analog circuits to check whether or not it is possible to uniquely determine the element-values in a given linear analog circuit from the node-voltage measurements at its accessible nodes and then of giving a method for actual computation of the element-values if it is possible, under the assumption that i) the circuit is of known topology (and of known element-kinds if possible) and ii) the actual value of each element-value of the circuit almost always deviates from the design value and is not known exactly. In this paper, the problem of checking the unique determinability of the element-values is called the element-value determinability problem, and its solutions which have been obtained until now are reviewed in perspectives to designing a publicly available user-oriented analog circuit diagnosis system.

The demand for mobile communication services is rapidly increasing, because the mobile communication service is synonymy of an ideal communication style realizing communication in anytime, anywhere and with anyone. The development of economic and social activities is a primary factor of the increasing demand for mobile communication services. The demand stimulates the development of technology in mobile communication including personal communication services. Thus mobile communication has been one of the most active research in communications in the last several years. There exist various problems to which graph & network theory is applicable in mobile communication services (for example, channel assignment algorithm in cellular system, protocol in modile communication networks and traffic control in mobile communication ). A model of a cellular system has been formulated using a graph and it is known that the channel assignment problem is equivalent to the coloring problem of graph theory. Recently, two types of coloring problems on graphs or networks related to the channel assignment problem were proposed. Mainly, we introduce these coloring problems and show some results on these problems in this paper.

It is demonstrated that the enhancement in the functional capability of an elemental transistor is quite essential in developing human-like intelligent electronic systems. For this purpose we have introduced the concept of four-terminal devices. Four-terminal devices have an additional dimension in the degree of freedom in controlling currents as compared to the three-terminal devices like bipolar and MOS transistors. The importance of the four-terminal device concept is demonstrated taking the neuron MOS transistor (abbreviated as neuMOS or νMOS) and its circuit applications as examples. We have found that any Boolean functin can be realized by a two-stage configuratin of νMOS inverters. In addition, the variable threshold nature of the device allows us to build real-time reconfigurable logic circuits (no floating gate charging effect is involved in varying the threshold). Based on the principle, we have developed Soft-Hardware Logic Circuits and Real-Time Rule-Variable Data Matching Circuits. A winner-take-all circuit which finds the largest signal by hardware parallel processing has been also developed. The circuit is applied to building an associative memory which is different from Hopfield network in both principle and operation. The hardware algorithm in which binary, multivalue, and analog operations are merged at a very device level is quite essential to establish intelligent information processing systems based on highly flexible, real-time programmable hardwares realized by four-terminal devices.

In this paper, symbols and numerals in topographic maps are recognized by the multi-angled parallelism (MAP) matching method, and small dots and lines are extracted by the MAP operation method. These results are then combined to determine the value, position, and attributes of elevation marks. Also, we reconstruct three dimensional surfaces described by contours, which is difficult even for humans since the elevation symbols are sparse. In reconstruction of the surface, we define an energy function that enfores three constraints: smoothness, fit, and contour. This energy function is minimized by solving a large linear system of simultaneous equations. We describe experiments on 25,000:1 scale topographic maps of the Tsukuba area.

This paper discusses the role of knowledge in document image understanding from the viewpoints of representation, utilization and acquisition. For the representation of knowledge, we propose two models, a layout model and a content model, which represent knowledge about the layout structure and content of a document, respectively. For the utilization of knowledge, we implement layout analysis and content analysis which utilize a layout model and a content model, respectively. The strategy of hypothesis generation and verification is introduced in order to integrate these two kinds of analysis. For the acquisition of knowledge, we propose a method of incremental acquisition of a layout model from a stream of example documents. From the experimental results of document image understanding and knowledge acquisition using 50 samples of visiting cards, we verified the effectiveness of the proposed method.

An integrated pen interface system was developed to allow effective Japanese text entry. It consists of sub-systems for handwriting recognition, contextual post-processing, and enhanced Kana-to-Kanji conversion. The recognition sub-system uses a hybrid algorithm consisting of a pattern matcher and a neural network discriminator. Special care was taken to improve the recognition of non-Kanji and simple Kanji characters frequently used in fast data entry. The post-processor predicts consecutive characters on the basis of bigrams modified by the addition of parts of speech and substitution of macro characters for Kanji characters. A Kana-to Kanji conversion method designed for ease of use with a pen interface has also been integrated into the system. In an experiment in which 2,900 samples of Kanji and non-Kanji characters were obtained from 20 subjects, it was observed that the original recognition accuracy of 83.7% (the result obtained by using the pattern matching recognizer) was improved to 90.7% by adding the neural network discriminator, and that it was further improved to 94.4% by adding the post-processor. The improved recognition accuracy for non-Kanji characters was particularly marked.

This paper proposes a new, high-speed method of filling in the contours of alpha-numeric characters to produce correct binary image patterns. We call this method the improved edge-fill method because it improves on a previously developed edge-fill method. Ambiguity of the conventional edge-fill method on binary images are eliminated by selecting fill pixels from combinations of Freeman's chain code, which expresses contour lines. Consequently, the areas inside the contour lines are filled in rapidly and correctly. With the new method, the processing time for character image generation is reduced by ten to tewnty percent over the conventional method. The effectiveness of the new method is examined in experiments using both Arabic numerals and letters from the Roman alphabet. Results show that this fill method is able to produce correct image patterns and that it can be applied to alpha-numeric-character contour filling.

This paper presents an overview of the SDC-I (Super Database Computer I) developed at the University of Tokyo, Japan. The purpose of the project was to build a high performance SQL server which emphasizes query processing over transaction processing. Recently relational database systems tend to be used for heavy decision support queries, which include many join, aggregation, and order-by operations. At present high-end mainframes are used for these applications requiring several hours in some cases. While the system architecture for high traffic transaction processing systems is well established, that for adhoc query processing has not yet adequately understood. SDC-I proved that a parallel machine could attain significant performance improvements over a coventional sequential machine through the exploitation of the high degree of parallelism present in relational query processing. A unique bucket spreading parallel hash join algorithm is employed in SDC, which makes the system very robust in the presense of data skew and allows SDC to attain almost linear performance scalability. SDC adopts a hybrid parallel architecture, where globally it is a shared nothing architecture, that is, modules are connected through the multistage network, but each module itself is a symmetric multiprocessor system. Although most of the hardware elements use commodity microprocessors for improved performance to cost, only the interconnection network incorporates the special function to support our parallel relational algorithm. Data movement over the memory and the network, rather than computation, is heavy for I/O intensive database processing. A dedicated software system was carefully designed for efficient data movement. The implemented prototype consists of two modules. Its hardware and software organization is described. The performance monitoring tool was developed to visualize the system activities, which showed that SDC-I works very efficiently.

The Institute for Posts and Telecommunications Policy (IPTP) held its first character recognition competition in 1992 to ascertain the present status of ongoing research in character recognition and to find promising algorithms for handwritten numerals. In this paper, we report and analyze the results of this competition. In the competition, we adopted 3-digit handwritten postal code images gathered from live mail as recognition objects. Prior to the competition, 2,500 samples (7,500 characters) were distributed to the participants as traning data. By using about 10,000 different samples (29,883 characters), we tested 13 recognition programs submitted by five universities and eight manufacturing companies. According to the four kinds of evaluation criteria: recognition accuracy, recognition speed, robustness against degradation, and theroretical originality, we selected the best three recognition algorithms as the Prize of Highest Excellence. Interestingly enough, the best three recognition algorithms showed considerable diversity in their methodologies and had very few commonly substituted or rejected patterns. We analyzed the causes for these commonly substituted or rejected patterns and, moreover, examined the human ability to discriminate between these patterns. Next, by considering the complementary characteristics of each recognition algorithm, we studied a multi-expert recognition strategy using the best three recognition algorithms. Three kinds of combination rules: voting on the first candidate rule, minimal sum of candidate order rule, and minimal sum of dissimilarities rule were examined, and the latter two rules decreased the substitution rate to one third of that obtained by one-expert in the competition. Furthermore, we proposed a candidate appearance likelihood method which utilizes the conditional probability of each of ten digits given the candidate combination obtained by each algorithm. From the experiments, this method achieved surprisingly low values of both substitution and rejection rates. By taking account of its learning ability, the candidate appearance likelihood method is considered one of the most promising multi-expert systems.

This paper discusses a digital neuroprocessor named Quantizer Neuron Chip (QNC) employing the Quantizer Neuron model and two newly developed schemes; "concurrent processing of quantizer neuron" and "removal of ineffective calculations". QNC simulates neural networks named the Multi-Functional Layered Network (MFLN) with 64 output neurons, 4672 quantizer neurons and two million synaptic weights and can be used for character or image recognition and learning. The processing speed of the chip achieved 1.6 µseconds per output neuron for recognition and 20 million connections updated per second (MCUPS) for learning. In addition, QNC can execute multichip operation for increasing the size of networks. We applied QNC to handwritten numeral recognition and realized high speed recognition and learning. QNC is implemented in a 1.2 µm double metal CMOS with sea of gates' technology and contains 27,000 gates on a 10.9910.93 mm2 chip.

The ultimate minimum energy of switching mechanism for MOS integrated circuits have been studied. This report elucidates the evaluation methods for minimum switching energy of instantaneous discharged mechanism after charging one, namely, recycled energy of the MOS device. Two approaches are implemented to capture this concept. One is a switching energy by the time-dependent gate capacitance (TDGC) model ; the other one by results developed by transient device simulation, which was implemented using Finite Element Method (FEM). It is understood that the non-recycled minimum swhiching energies by both approaches show a good agreement. The recycled energies are then calculated at various sub-micron gate MOS/SOI devices and can be ultra-low power of the MOS integrated circuits, which may be possible to build recycled power circuitry for super energy-saving in the future new MOS LSI. From those results, (1) the TDGC is simultaneously verified by consistent match of the non-recycled minimum switching energies; (2) the recycled switching energy is found to be the ultimate lower bound of power for MOS device; (3) the recycled switching energy can be saved up to around 80% of that of current MOS LSI.

This paper gives field experimental results on 16-ary quadrature amplitude modulation/time division multiple access (16QAM/TDMA) and trellis coded 16QAM/TDMA systems for land mobile communications in order to evaluate its capability of achieving large capacity and high quality data transmission. Pilot symbol aided space diversity and symbol timing synchronization based on maximum likelihood (ML) estimation are applied to both 16QAM/TDMA and trellis coded 16QAM/TDMA to improve transmission quality. For the trellis coded 16QAM/TDMA, trellis coding with Viterbi decoding and 2-frame symbol interleaving are further employed. The field experiments were conducted in the Tokyo metropolitan area of Japan. The results show that 16QAM/TDMA and trellis coded 16QAM/TDMA are practical modulation/access schemes for land mobile communication systems.

An integrator using UGB (unity-gain buffer) is proposed. The UGB has gain error. To improve the gain error of UGB in the integrator, a compensation technique of the gain error of UGB is proposed. Next, second-order ΣΔ A/D converter using UGB integrator with gain-error compensator is proposed. In the proposed circuit, the influence of input-output characteristic is simulated. In the simulation results, the improvement is confirmed. In addition, performance limiting factors due to non ideal effects, e.g., parasitic capacitance and offset voltage, are considered. Validity of the proposed compensation technique for each factor is confirmed in the simulation results.

The issue about document structure recognition and document understanding is today one of interesting subjects from a viewpoint of practical applications. The research objective is to extract the meaningful data from document images interpretatively and also classify them as the predefined item data automatically. In comparison with the traditional image-processing-based approaches, the knowledge-based approaches, which make use of various knowledge in order to interpret structural/constructive features of documents, have been currently investigated as more flexible and applicable methods. In this paper, we propose a totally integrated paradigm for understanding table-form documents from a viewpoint of the architectural framework.

This paper presents a discrete Fourier analyzer using analog VLSI technology. An analog current-mode technique is employed for implementing it by a regular array structure based on the straight-forward discrete Fourier transform (DFT) algorithm. The basic components are 1-dimensional (1-D) analog current-mode multiplier array for fixed coefficient multiplication, two-dimensional (2-D) analog switch array and wired summations. The proposed scheme can process speedily N-point DFT in a time proportional to N. Possibility of the realization of the analog DFT VLSI based on 1 µm technology is discussed from the viewpoints of precision, speed, area, and power dissipation. In the case of 1024-point DFT, the standard deviation of the total error is estimated to be about 2%, the latency, or processing time is about 110 µs, and the signal sample rate based on a pipeline manner is about 4.7 MHz. A prototype MOS integrated circuit of the 16-point multiplier array has been implemented and a typical operation using the multiplier array has been confirmed.

A fast Newton/LMS algorithm is proposed which uses an efficient inversion technique of input autocorrelation matrix when the periodic pseudo random sequence is used as the reference signal. The number of operations is greatly reduced and the computational results show fast convergence rate and low misadjustment error. And the application of the algorithm to the case of nonperiodic reference signal is described.

A system for segmentation of document image and ordering text areas is described, and applied to complex printed page layouts of both Japanese and English. There is no need to make any assumptions about the shape of blocks, hence the segmentation technique can handle not only skewed images without skew-correction but also documents where columns are not rectangular. In this technique, based on the bottom-up strategy, the connected components are extracted from the reduced image, and classiferd according to their local information. The connected components calssified as characters are then merged into lines, and the lines are merged into areas. Extracted text areas are classified as body, caption, header or footer. A tree graph of the layout of the body texts is made, and the texts ordered by preorder traversal on the graph. We introduce the concept of an influence range of each node, a procedure for handling titles, thus obtaining good results on various documents. The total system is fast and compact.