Most communication cables are laid underground. In order to make construction and maintenance works easier, systems to detect buried objects have already been developed using the electromagnetic pulse radar technique. However, existing detection systems are not really practical due to their rather limited processing speed. To achieve sufficient processing speed, two dedicated custom FFT LSI's are designed and realized with 0.8 µm-CMOS technology. The two chips have an equivalent processing capacity of 200 MOPS. An efficietn hardware algorithm for address generation and 2 word parallel processing are introduced. In addition, an enhanced system organization is developed together with an improved pattern recognition scheme and aperture synthesis hardware. The new processor executes a FFT/parameter extraction operation in 4 seconds and aperture synthesis in 1 second. This speed meets the design target, and a real time detection system for underground objects becomes possible.

The paper proposes a combined delay model to manipulate the variance of the delay time of logic elements and a new timing verification method based on the theory of regular expressions. With the delay time of logic elements such as TTL SN7400, the minimum delay time (dm), the maximum delay time (dM), and the typical delay time are specified in the manual, and the delay time of an element is one in the interval between dm and dM. Here we assume a discrete time, and we manipulate the variance of the delay time as a set of output strings corresponding to each delay time. We call the model as the combined delay model. Since many output strings are generated with a single input string, the usual timing simulation method cannot be applied. We propose a timing verification method using a behavior extraction method of logic circuits with respect to a time string set: with respect to the specified input set, the method extracts the output string set of each element in the circuit. We devised (1) a mechanism to keep the correspondence between a primary input string and an output string with respect to the primary input string, (2) a mechanism to manipulate the nondeterminism included in the combined delay model, and (3) an event-driven like data compaction method in representing finite automata. We focused on the hazard detection problem and the verification of asynchronous circuits, and show the effectiveness of our method with medium sized circuit with 100 elements or so. The method includes the state explosion, but the data compaction method and the extraction for only the specified input set are useful to control the state explosion.

In recent VLSI design of digital data paths, significantly more area is occupied by interconnect elements than by functional units and registers. Nevertheless, until recently most work in data path synthesis has been concentrated on trying to reduce the area of functional units and registers, without paying much attention to the interconnect area. Lately, research that addresses reducing the area of interconnection and of functional units and registers is increasing, but in them, most algorithms for assigning interconnect elements are not efficient enough to optimize the interconnect area. In most current research, algorithms for interconnect element assignment are used to calculate the cost functions during the scheduling and/or allocation steps. This makes it impossible to use efficient optimization algorithms that may consume long time. This paper presents some new algorithms used to assign interconnect elements in data paths. The algorithms minimize the number of multiplexer inputs after the scheduling and operator/register allocations have been made. The algorithms have two characteristics. First, we use a branch and bound method for small problems. We confirmed that exact solutions in practical time can be obtained with this method for rather large problems, when the solutions are restricted to a one-level multiplexer model. Second, we use a certain heuristic method for larger problems. The algorithms have been implemented in C on an Apollo Domain Series 10000.

This paper deals with the sub-problems of generating a mask pattern from the logical description of a large-scale CMOS circuit. The large-scale layout can be generated in divide-and-conquer style: divide a given circuit into a set of sub-circuits, generate the layout of each sub-circuit, and merge the resulting layouts to create the whole layout. This paper proposes a layout synthesis algorithm for a sub-circuit with physical constraints for the synthesis scheme above. The physical constraints considered here are the relative placement of logic cells (sets of logic gates) and the routing constraint based on the costs of wiring layers and vias. These constraints will be given by the global optimizer in a two-dimensional layout synthesis routine, and they should be kept at the subsequent one-dimensional layout synthesis for a sub-circuit. The latter is also given for enhancing the circuit performance by limiting the usage of wiring layers and vias for special net such as a clock net. The placement constraint is maintained using PQ-tree, a tree structure representing a set of restricted permutations of elements. One-dimensional layout synthesis determines the placement of transistors by the enhanced pairwise exchanging method under the PQ-tree representation. The routing constraints is considered in the newly developed line-search routing method using a cost-based searching. Experimental results for practical standard cells, including up to 200 transistors, prove that the algorithms can produce the layouts comparable to handcrafted cells. Also on a two-dimensional layout synthesis using the algorithms, the results for benchmark circuits of Physical Design Workshop 1989, i.e., MCNC benchmark circuits, are superior to the best results exhibited at Design Automation Conference 1990.

In this paper we propose a new timing verification technique named coded time-symbolic simulation, CTSS. Our interest is on simulation of logic circuits consisting of gates whose delay is specified only by its minimum and maximum values. Conventional logic simulation based on min/max delay model leads to over-pessimistic results. In our new method, the cases of possible delay values of each gate are encoded by binary vectors. The circuit behavior for all the possible combinations of the delay values are simulated based on symbolic simulation by assigning Boolean variables to the binary vectors. This simulation technique can deal with logic circuits containing feedback loops as well as combinational circuits. We implemented an efficient simulator by using shared binary decision diagrams (SBDD's) as internal representation of Boolean functions. We also propose novel techniques of analyzing the results of CTSS.

A process of mixing viscous fluids, such as oil-based paints is applied to generate marble patterns. It is difficult to get the exact flow function of the viscous fluid, then we express the flow in terms of velocity vectors derived from simplified flow phenomena, in which the viscous liquid is supposed to be a collection of finite liquid elements. The position change of each element is calculated as the function of time and several examples of the obtained marble patterns are illustrated.

An algorithm is presented for selecting the k-th smallest element of a totally ordered (but not sorted) set of n elements, 1kn, in the case that a special-purpose sorter is used as a coprocessor. When the pipeline merge sorter is used as the special-purpose sorter, we analyze the comparison complexity of the algorithm for the given capacity of the sorter. The comparison complexity of the algorithm is 1.4167no(n), provided that the capacity of the sorter is 256 elements. The comparison complexity of the algorithm decreases as the capacity of the sorter increases.

A passive double star (PDS) optical subscriber system which employs a newly proposed flexible access and frequency division duplex transmission system has been reported. For the flexible access and efficient channel usage in subscriber PDS system, a modified pipe-line polling with a call-by-call basis channel assignment has been proposed. This access system has a wide covering range which exceeds 10km or more. A newly proposed pulsed PSK transmission and a baseband transmission are used for a single wavelength bi-directional transmission for to and from the central office. A pulsed FM single subcarrier transmission system is also proposed for the analog CATV distribution system, which is overlaid with wavelength division multiplexing on the bi-directional transmission system. The equipments for the pulsed PSK and the pulsed FM transmission can be realized with all digital circuits. Moreover, the pulsed signal's modulation nature has eased the requirement for the laser diode characteristics, such as linearity and RIN. These features are effective for the compact and cost effective transmission systems.

In the maximum-likelihood decoding under a non-Gaussian noise, the decoding region is bounded by complex curves instead of a perpendicular bisector corresponding to the Gaussian noise. Therefore, the error rate is not evaluated by the Euclidean distance. The Bhattacharyya distance is adopted since it can evaluate the error performance for a noise with an arbitrary distribution. Upper bound formulae of a bit error rate and an event error rate are obtained based on the error-weight-profile method proposed by Zehavi and Wolf. The method is modified for a non-Gaussian channel by using the Bhattacharyya distance instead of the Euclidean distance. To determine the optimum code for an impulsive noise channel, the upper bound of the bit error rate is calculated for each code having an encoder with given shift-register lehgth. The best code is selected as that having the minimum upper bound of the bit error rate. This method needs much computation time especially for a code with a long shift-register. To lighten the computation burden, a suboptimum search is also attempted. For an impulsive noise, modeled from an observation in digital subscriber loops, an optimum or suboptimum code is searched for among codes having encoders with a shift-register of up to 4 bits. By using a code with a 4-bit encoder, a coding gain of 20 dB is obtained at the bit error rate 10-5. It is 11 dB more than that obtained by Ungerboeck's code.

In this paper, a type hybrid ARQ scheme with Adaptive Forward Error Correction (ARQ/AFEC) using BCH codes is proposed and analyzed. The basic idea in the proposed type hybrid ARQ/AFEC scheme is to increase the error-correcting capability of BCH code according to channel state using incremental redundancy. The incremental redundancy is the remainder ai(x) of an information frame f(x) of length n divided by a minimum polynomial mi(x) of α2i-1, where α is a primitive element of finite field GF(2l). Let gi(x) be the product of mj(x) (j=1, 2, , i) and let ci(x) be the remainder of f(x) divided by gi(x). The polynomial ci(x) is obtained from the remainders ai(x) and ci-1(x) since mi(x)and gi-1 (x) are relatively prime. Since f(x) + ci(x) is divided by gi(x), f(x) + ci(x) is the codeword of an i-error-correcting BCH code when n2l-1. So, the errors less than or equal to i bits in f(x) can be corrected if ci(x) has no error.

The purpose of our research is to get further improvement in the performance of order statistic filters. The basic idea found in our research is the use of a robust median estimator to obtain median differential order information which the classes of order statistic filter required in order to sort the input signal in the filter window. In order to give the motivation for using a median estimator in the classes of order statistic filters, we derive theorems characterizing the median filters and prove them theoretically using the characteristic that the order statistic filter has the performance for a monotonic signal equivalent with the FIR linear filter. As an application of median operation, we propose and investigate the Median Differential Order Statistic Filter to reduce impulsive noise as well as Gaussian noise and regard it as a subclass of the Order Statistic Filter. Moreover, we introduce the piecewise linear function in the Median Differential Order Statistic Filter to improve performance in terms of edge preservation. We call it the Piecewise Linear Median Differential Order Statistic Filter. The effectiveness of proposed filters is verified theoretically by computing the output Mean Square Error of the filters in parts of edge signals, impulsive noise, small amplitude noise and their combination. Computer simulations also show that the proposed filter can improve the performance in both noise (small-amplitude Gaussian noise and impulsive noise) reduction and edge preservation for one-dimensional signals.

A novel harmonic retrieval algorithm is proposed in this paper based on Hopfield's neural network. Frequencies can be retrieved with high accuracy and high resolution under low signal to noise ratio (SNR). Amplitudes and phases in harmonic signals can also be estimated roughly by an energy constrained linear projection approach as proposed in the algorithm. Only no less than 2q neurons are necessary in order to detect harmonic siglnals with q different frequencies, where q denotes the number of different frequencies in harmonic signals. Experimental simulations show fast convergence and stable solution in spite of low signal to noise ratio can be obtained using the proposed algorithm.

After the intrinsic pulsed light illumination, a transient negative photoconductivity (TRANP) was observed in silicon doped with gold. The ambient temperature dependence of the TRANP-current was measured and compared with the simulated results obtained by solving rate equations. The temperature dependence of the peak value of the TRANP-current was in agreement with the simulated result. The activation energy of gold acceptor level obtained from the time constant in the recovery process was also consistent with the simulation. It was cleared from this result that the recovery process is dominated by the electron re-emission from gold acceptor level to the conduction band. It was concluded that the occurrence of the TRANP is well explained by using our model proposed before.

It often occurs in an environmental phenomenon in our daily life that a specific signal is partially or completely contaminated by the additional external noise. In this study, a digital filter for estimating a specific signal fluctuating impulsively under the existence of an actual external noise with various kinds of probability distribution forms is proposed in an improved form of already reported digital filter. The effectivenss of the proposed theory is experimentally confirmed by applying it to the estimation of an actual impulsve signal in a room acoustic.

This letter describes one neuron's dynamics. This neuron provides its own feedback input. We call this neuron the recurrent neuron and investigate its nonlinear dynamics.

It is crucial to make Si wafer surfaces ultraclean in order to realize such advanced processes as the low-temperature process and the high-selectivity in the ULSI production. The ultra clean wafer surface must be perfectly free from particles, organic materials, metallic impurities, native oxide, surface microroughness, and adsorbed molecule impurities. Since the metallic contamination on the wafer surface, which is one of the major contaminants to be overcome in order to come up with the ultra clean wafer surface, has the fatal effect on the device characteristics, the metallic impurities in the wafer surface must be suppressed at least below 1010 atoms/cm2. Meanwhile the current dry processes such as reactive ion etching or ion implantation, suffer the metallic contamination of 10121013 atoms/cm2. The wet process becomes increasingly important to remove the metallic impurities introduced in the dry process. Employing a new evaluation method, the metallic impurity segregations at the inrerface between the Si and liquid employed in the wet cleaning process of the Si surface such as ultrapure water and various clemicals were studied. This article clearly indicate that it is important to suppress the metallic impurities, such as Cu, which can exchange electrons with Si to be segregated, at least below the 10 ppt level in ultrapure water and liquid chemical such as HF, H2O2, which are employed in the final step of the wet cleaning. When the ultrapure water rinsing is performed in the ambience containing oxygen, the native oxide grows accompanying an inclusion of metals featuring lower electron negativity than Si. It is revealed that, in order to provent the metallic impurity precipitation, it is require not only to remove metallic impurities from ultrapure water but also to keep the cleaning ambience without oxygen, such as the nitrogen ambience, so as to suppress the native oxide formation.

Logarithmic number systems (LNS) provide a very fast computational method. Their exceptional speed has been demonstrated in signal processing and then in computer graphics. But the precision problem of LNS in computer graphics has not been fully examined. In this paper analysis is made for the problem of LNS in picture generation, in particular for circle drawing. Theoretical error analysis is made for the circle drawing. That is, some expressions are developed for the relative error variances. Then they are examined by simulation experiments. Some comparisons are also done with floating point arithmetic with equivalent word length and dynamic range. The results show that the theory and the experiments agree reasonably well and that the logarithmic arithmetic is superior to or at least comparable to the corresponding floating point arithmetic with equivalent word length and dynamic range. Those results are also verified by visual inspections of actually drawn circles. It also shows that the conversion error (from integer to LNS), which is inherent in computer graphics with LNS, does not make too much influence on the total computational error for circle drawing. But it shows that the square-rooting makes the larger influence.

The effects of changing system parameters on job scheduling policies are studied for load balancing of multi-class jobs in a distributed computer system that consists of heterogeneous host computers connected by a single-channel communications network. A job scheduling policy decides which host should process the arriving jobs. We consider two job scheduling policies. The one is the overall optimal policy whereby jobs are scheduled so as to minimize the overall mean job response time. Tantawi and Towsley obtained the algorithm that gives the solution of the policy in the single class job environment and Kim and Kameda extended it to the multiple job class environment. The other is the individually optimal policy whereby jobs are scheduled so that every job may feel that its own expected response time is minimized. We can consider three important system parameters in a distributed computer system: the communication time of the network, the processing capacity of each node, and the job arrival rate of each node. We examine the effects of these three parameters on the two load balancing policies by numerical experiment.

We investigate the relationship between two different notions of reducibility among prediction (learning) problems within the distribution-free learning model of Valiant (PAC learning model). The notions of reducibility we consider are the analogues for prediction problems of the many-one reducibility and of the Turing reducibility. The former is the notion of prediction preserving reducibility developed by Pitt and Warmuth, and its generalization. Concerning these two notions of reducibility, we show that there exist a pair of prediction problems A and B, whose membership problems are polynomial time solvable, such that A is reducible to B with respect to the Turing reducibility, but not with respect to the prediction preserving reducibility. We show this result by making use of the notion of a class of polynomially sparse variants of a concept representation class. We first show that any class A of polynomially sparse variants of another class B is reducible to B with respect to the Turing reducibility'. We then prove the existence of a prediction problem R and a class R of polynomially sparse variants of R, such that R does not reduce to R with respect to the prediction preserving reducibility.

In the approximate learning model introduced by Valiant, it has been shown by Blumer et al. that an Occam algorithm is immediately a PAC-learning algorithm. An Occam algorithm is a polynomial time algorithm that produces, for any sequence of examples, a simple hypothesis consistent with the examples. So an Occam algorithm is thought of as a procedure that compresses information in the examples. Weakening the compressing ability of Occam algorithms, a notion of weak Occam algorithms is introduced and the relationship between weak Occam algorithms and PAC-learning algorithms is investigated. It is shown that although a weak Occam algorithm is immediately a (probably) consistent PAC-learning algorithm, the converse does not hold. On the other hand, we show how to construct a weak Occam algorithm from a PAC-learning algorithm under some natural conditions. This result implies the equivalence between the existence of a weak Occam algorithm and that of a PAC-learning algorithm. Since the weak Occam algorithms constructed from PAC-learning algorithms are deterministic, our result improves a result of Board and Pitt's that the existence of a PAC-learning algorithm is equivalent to that of a randomized Occam algorithm.