Digital halftoning is a well-known technique in image processing to convert an image having several bits for brightness levels into a binary image consisting only of black and white dots. A great number of algorithms have been presented for this problem, some of which have only been evaluated just by comparison with human eyes. In this paper we formulate the digital halftoning problem as a combinatiorial problem which allows an exact solution with graph-theoretic tools. For this, we consider a d-dimensional grid of n := Nd pixels (d 1). For each pixel, we define a so-called k-neighborhood, k {0,...N - 1}, which is the set of at most (2k + 1)d pixels that can be reached from the current pixel in a distance of k. Now, in order to solve the digital halftoning problem, we are going to minimize the sum of distances of all k-neighborhoods between the original picture and the halftoned one. We show that the problem can be solved in linear time in the one-dimensional case while it looks hopeless to have a polynomial-time algorithm in higher dimension including the usual two-dimensional case. We present an exact algorithm for the one-dimensional case which runs in O(n) time if k is regarded to be a constant. For two-dimensional case we present fast approximation techniques based on space filling curves. An experimental comparison of several implementations of approximate algorithms proves that our algorithms are of practical interest.

A model for the floating point adder/subtractor which can perform rounding and addition/subtraction operations in parallel is presented. The major requirements and structure to achieve this goal are described and algebraically verified. Processing flow of the conventional floating point addition/subtraction operation consists of alignment, addition/subtraction, normalization, and rounding stages. In general, the rounding stage requires a high speed adder for increment, increasing the overall execution time and occupying a large amount of chip area. Furthermore, it accompanies additional execution time and hardware logics for renormalization stage which may occur by an overflow from the rounding operation. A floating adder/subtractor performing addition/subtraction and IEEE rounding in parallel is designed by optimizing the operational flow of floating point addition/subtraction operation. The floating point adder/subtractor presented does not require any additional execution time nor any high speed adder for rounding operation. In addition, the renormalization step is not required because the rounding step is performed prior to the normalization operation. Thus, performance improvement and cost-effective design can be achieved by this approach.

An adaptive decoding scheme for a concatenated code used in the frequency-hopped spread-spectrum communication system in the presence of a pulse-burst jammer is proposed and its performance is analyzed. Concatenated coding schemes employing binary inner-code and Reed-Solomon outer code are investigated and the use of side information is allowed to decode both erasures and errors. The proposed scheme makes the decoder enable to adapt to the jamming level by switching between two decoding modes such that the decoded bit error rate can be reduced. The optimal threshold value for switching in this proposed scheme is derived. It has been shown that the proposed decoding scheme yields a significant performance improvement over a conventional decoding scheme. In addition, performance analysis and its variation of adaptive decoding scheme with the imperfect side information are also presented.

Discussed here is progress achieved in the development of video codec LSIs.First, the amount of computation for various standards, and signal handling capability (throughput) and power dissipation for video codec LSIs are described. Then, general technologies for improving throughtput are briefly summarized. The paper also reviews three approaches (i.e., video signal processor, building block and monolithic codes) for implementing video codes standards. The second half of the paper discusses various high-throughput technologies developed for programmable Video Signal Processor (VSP) LSIs. A number of VSP LSIs are introduced, including the world's first programmable VSP, developed in February 1987 and a monolithic codec ship, built in February 1993 that is sufficient in itself for the construction of a video encoder for encoding full-CIF data at 30 frames per second. Technologies for reduction of power dissipation while keeping maintaining throughput are also discussed.

This paper describes a new active pull-up (APU) interface for high-speed point-to-point transmission. The APU circuit is used to speed up a low-power-consumption open-drain-type interface. It pulls up the output at a fixed duration and this limiting of the pull-up duration prevents the pull-up operation from going into a counter phase at over 1-Gbps operation. Measurements of test chips fabricated with 0.25-µm bulk CMOS show. 1.7-Gbps error-free operation for the APU interface and 1.2-Gbps operation for the open-drain-type interface: The APU interface is 1.4 faster than the open-drain type. The application of a 0.25-µm SIMOX-CMOS device to the APU interface increases the bit rate 1.5 times compared with 0.25-µm bulk CMOS. Altogether the interface covers the bit rate of 2.4 Gbps, which is a layer of the communication hierarchy. The APU interface circuit can be applied to large-pin-count LSIs because of its full-CMOS single-rail structure.

This paper investigates some fundamental properties of alternating one-way (or two-way) pushdown automata (pda's) with sublogarithmic space. We first show that strongly (weakly) sublogarithmic space-bounded two-way alternating pda's are more powerful than one-way alternating pda's with the same space-bound. Then, we show that weakly sublogarithmic space-bounded two-way (one-way) alternating pda's are more powerful than two-way (one-way) nondeterministic pda's and alternating pda's with only universal states using the same space, and we also show that weakly sublogarithmic space-bounded one-way nondeterministic Turing machines are incomparable with one-way alternating Turing machines with only universal states using the same space. Furthermore, we investigate several fundamental closure properties, and show that the class of languages accepted by weakly sublogarithmic space-bounded one-way alternating pda's and the class of languages accepted by sublogarithmic space-bounded two-way deterministic pda's (nondeterministic pda's, alternating pda's with only universal states) are not closed under concatenation, Kleene closure, and length preserving homomorphism. Finally, we briefly investigate a relationship between 'strongly' and 'weakly'.

Among three factors mainly affecting the cache access time, i. e., hit access time, miss rate and miss penalty, previous approaches were focused on reducing the hit access time and miss rate. In this paper, we propose a scheme called MPC (Miss-Predicting Cache) which achives additional reduction of the average instruction cache access time through reducing the miss penalty. The MPC scheme which predicts cache miss and starts cache miss operations in advance, therefore, is supplementary to previous cache schemes targeted for reducing the miss rate and/or hit access time. Performance of the MPC scheme was evaluated using dinero, a trace-driven cache simulator, with the estimation of silicon area using 0.8 µm CMOS standard cell library.

This paper clarified fundamental aspects of both triboelectric processes and electrostatic discharge (ESD) phenomena to the electronic systems. A chance for ESD can occur if a charged metal object (steel piped chair, for example) contacts or collides with another metal objects at moderate speed. At metal-metal ESD event, the metal objects act as a radiation antenna in a very short time (some 100ps, for example) which emanates impulsive electromagnetic fields with unipolarity into the surrounding space. Because of ESD at low-voltage (3kV or less) conditions, the direction of electrons movement at the spark gap is always unidirectional and fixed. The spark gap works as a momentary switch and also as a "diode." The dominant fields radiated from the metal objects are impulsive electric fields or impulsive magnetic fields which depend on the metal object's electrical and geometric conditions. This impulsive electromagnetic fields penetrate electronic systems, causing electromagnetic interference (EMI) such as malfunctions or circuit upset. The difference between EMI actions in high-voltage ESD and low-voltage ESD is experimentally analyzed in terms of energy conversion/consumption. A series of experiments revealed that EMI actions due to the metal-metal ESD are not proportional to the charge voltage nor the discharge current. In order to capture single shot impulsive electromagnetic fields very close to the ESD point (wave source), a short monopole antenna as an ultra broad-band field sensor was devised. As for signal transmissions between the short monopole antenna and the instrument (receiver), micro/millimeter wave techniques were applied. The transmission line's minimum band width DC-18.5GHz is required for time domain measurements of low-voltage ESD.

With increases in the speed of semiconductor devices and integrated circuits, the importance of internal testing with sufficient temporal resolution has been growing. This paper describes recently established electro-optic testing technologies based on pulse lasers and electro-optic crystal probes. Practicability, limitation and future issues are discussed.

This paper presents a parallel move generation of a Chess machine system for achieving the purpose of reducing the number of move generation cycles. The parallel system is composed of five move generation modules which share the move generating cycles to reduce the time of building a game tree. Simulation results show that the proposed parallel move generation architecture takes about half of the number of move generation cycles to build a game tree that is the same as the one built by a sequential move generation module.

A speedup of Lenstra's Elliptic Curve Method of factorization is presented. The speedup works for integers of the form N = PQ2, where P is a prime sufficiently smaller than Q. The result is of interest to cryptographers, since integers with secret factorization of this form are being used in digital signatures. The algorithm makes use of what we call Jacobi signatures. We believe these to be of independent interest.

Over the past few years, many industrial processes have switched to electrical processes from conventional fossil fuel as a primary energy source, since electricity can be transmitted more economically than the transport of fossil fuels, as well as less pollution problems and labour- and spacesaving nature. For the environmental protections, ozone generation for water treatments, and decomposition of pollution gases such as SOx, NOx, COx, etc., by high pressure gas discharge processes become an important research subject. However, due to the early stage of development, the EMC problem is not yet well considered. In this review, we try to address the EMC problem in the various atmospheric pressure gas discharge processing techniques and identify future needs of research.

A fast and stable algorithm for locating a desired eigenvalue and its corresponding eigenvector is presented. Its effectiveness is shown through a numerical simulation. The proposed algorithm is fast and numerically accurate enough to be applied to a real application.

We deal with a fixpoint semantics for normal logic programs by means of an algebraic manipulation of idempotent substitution sets. Because of the negation, the function associated with a given normal logic program, which captures the deductions caused by the program, is in general nonmonotonic, as long as we are concerned with 2-valued logic approach. The demerit of the nonmonotonic function is not to guarantee its fixpoint well, although the fixpoint is regarded as representing the whole behaviour. The stable model as in [6] is fixpoint of nonmonotonic functions, but it is referred to on the assumption of its existences. On the other hand, if we take 3-valued logic approach for normal logic programs as in [5], [9], [11], [14] we have the monotonic function to represent resolutions and negation as failure, and define its fixpoint well, if we permit the fixpoint not to be constructive because of discontinuity. Since the substituitions for variables in the program are essentially significant in the deductions for logic programming, we next focus on the representations by means of substitutions for the deductions, without usual expressions based on atomic formulas. We examine the semantics in terms of abstract interpretations among semantics as surveyed in [9], where an abstraction stands for the capability of representing another semantics. In this paper, in 3-valued logic approach and by means of the substitution manipulation, the semantics is defined to be an abstraction of the semantics in [5], [9]. To construct a semantics based on the idempotent substitution set, the algebraic manipulation of substitutions is significant, whereas the treatment in [10] for the case of definite clause sets is not available because of the restriction of substitutions to some variable domain as most general unifications.

In this paper, we study three-dimensional motion estimation using optical flow. We construct a weighted quotient-form objective function that provides an unbiased estimator. Using this objective function with a certain projection operator as a weight drastically reduces the computational cost for estimation compared with using the maximum likelihood estimator. To reduce the variance of the estimator, we examine the weight, and we show by theoretical evaluations and simulations that, with an appropriate projection function, and when the noise variance is not too small, this objective function provides an estimator whose variance is smaller than that of the maximum likelihood estimator. The use of this projection is based on the knowledge that the depth function has a positive value (i. e., the object is in front of the camera) and that it is generally smooth.

This paper proposes an adaptive modulation system with a punctured convolutional code for land mobile communications to achieve high quality, high bit rate, and high spectral efficient data transmission in multipath fading environments. The proposed system adaptively controls the coding rate of the punctured convolutional code, symbol rate, and modulation level according to the instantaneous fading channel conditions. During good channel conditions, the modulation parameters are selected to increase the transmission rate as much as possible with satisfying a certain transmission quality. As channel conditions become worse, lower rate modulation parameters are applied or transmission is stopped. The performances in fading environments are evaluated theoretically and by computer simulations. The results show that the proposed system can realize higher quality transmission without the degradation in average bit rate compared to conventional adaptive modulation systems.

A new transmit permission control scheme applicable in multi-cell communication systems is proposed. In this scheme, by prohibiting the transmissions from the users with relatively high propagation loss to their connecting hub stations, level of multiple access interference is decreased, and hence throughput characteristics are improved. Moreover, we continue our discussion to propose two adaptive forms of the transmit permission control scheme, in which the prohibition condition becomes more intelligent by considering the level of the offered traffic loads to hub stations. These methods are utilized in a slotted Aloha random transmission of the spread spectrum packets, and on the uplinks of a low earth orbit satellite communication system as an example of the multi-cell systems. It is shown that the adaptive schemes exhibits significantly improved characteristics at all offered traffic loads in these systems.

A new line simulator, SEMALIS has been developed. This simulator can handle complicated lot processings to maintain processing quality and efficient line operations to improve line performance. The current manufacturing line consists of five resource models: lot, process sequence, equipment, lot processing, and line operations. The parameters of these models are defined so as to accurately reflect the state of the line operations. From our simulation results, we confirmed that SEMALIS accurately identifies bottlenecks or starvations where equipment can be added or reduced to optimize equipment utilization through resource planning, and that SEMALIS can also be used to evaluate the long-term effects of line operating methods on the line performance of ASIC manufacturing lines.

In order to establish the advanced and costeffective wet cleaning technology, it is essential to reveal the mechanism of contamination adhesion and removal on Si surfaces in solutions. To reveal the mechanism of noble metal adhesion onto the Si surface in wet processes, the behavior of Cu2+ deposition onto Si surfaces in solutions was investigated. The experimental results reveal the mechanism of electrochemical metallic contamination of noble metals on Si surfaces. Moreover, it was found that, in HF solutions, Si is not directly etched in a form of SiF62- by such an oxidizing agent as Cu2+ but is first turned to oxide and then etched off. For preventing noble metal deposition on Si surfaces, it is necessary not only to keep the noble metals in the solution (i.e. to dissolve noble metals) but also to prevent oxidation/reduction reaction between Si and the noble metal ion. It is found that this oxidation/reduction reaction can be prevented by increasing the redox potential of solutions, injecting surfactants or chelating agents, and making the Si surface covered with oxide. It has been revealed that Cu deposition can be prevented by setting the redox potential of the solution at over 0.75 V vs. NHE. Cu deposition in DHF solutions can be prevented by setting the redox potential at 0.85 V vs. NHE or more. For removing Cu from the Si surface, the same conditions are found to be necessary. Moreover, it is revealed that metallic impurities included in the oxide can be removed only by etching. It is also revealed that chemicals to prevent metal deposition must be used to remove metals such as Cu which easily get redeposited on the bare Si surface. Finally, a new wet cleaning process employing ozonized ultrapure water, NH4OH/H2O2/H2O, and surfactant-injected DHF to replace the conventional RCA cleaning method is proposed.

Understanding unknown objects in images is one of the most important fields of the computer vision. We are confronted with the problem of dealing with the ambiguity of the image information about unknown objects in the scene. The purpose of this paper is to propose a new object recognition method based on the fuzzy relation system and the fuzzy integral. In order to deal with the ambiguity of the image information, we apply the fuzzy theory to object recognition subjects. Firstly, we define the degree of similarity based on the fuzzy relation system among input images and object models. In the next, to avoid the uncertainty of relations between the input image and the 2-D aspects of models, we integrate the degree of similarity obtained from several input images by the fuzzy integral. This proposing method makes it possible to recognize the unknown objects correctly under the ambiguity of the image information. And the validity of our method is confirmed by the experiments with six kinds of chairs.