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.

This letter proposes a new shaping algorithm (CRSA: CDV Reduction Shaping Algorithm) that can freely reduce the maximum CDV value of a cell stream to any predetermined value. There is a trade off between shaping delay and the maximum CDV value reduction achieved when using CRSA. The shaper using CRSA (CR-shaper) output satisfies the Peak Cell Rate Reference Algorithm set with the CR-shaper parameters.

This paper proposes a method to predict and control noise voltage caused by electrostatic discharge (ESD) to electronic equipment. The relationship of grounding system configurations for a typical set of equipment to ESD immunity has been derived using a mechanism of ground potential variations. The equivalent circuit representing ground elements as lumped constants enables us to predict the transient ground potential differences between PCB (Printed Circuit Board) ground planes connected via signal cables and induced noise voltage at the receiving end. The calculation shows that the contribution of ground potential differences to noise voltage is comparable to that of the electromagnetic coupling between the discharge current on the enclosure and the circuit loops. The calculation also shows some characteristic results, such as; the induced noise voltage is remarkably dependent on the unbalance in ground cable lengths and on the impedance of ground conductors connecting PCBs, especially when the equipment uses a single-point grounding system. These characteristics were confirmed by measurements of induced ground potential differences, noise voltage and immunity levels. Thus the proposed method is shown to be very effective to analyze the dependency of grounding conditions on ESD immunity and to improve ESD immunity in equipment design.

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.

A novel method of multichannel surface EMG processing has been developed to compensate for the distortion in bipolar surface EMG signals due to the movement of innervation zones. The distortion of bipolar surface EMG signals was mathematically described as a filtering function. A compensating technique for such distorted bipolar surface EMG signals was developed for the brachial biceps during dynamic contractions in which the muscle length and tension change. The technique is based on multichannel surface EMG measurement, a method for estimating the movement of an innervation zone, and the inverse filtering technique. As a result, the distorted EMG signals were compensated and transformed into nearly identical waveforms, independent of the movement of the innervation zone.

It is known that the problem of determining, given a planar graph G with maximum vertex degree at most 4 and integers m and n, whether G is embeddable in an m n grid with unit congestion is NP-hard. In this paper, we show that it is also NP-complete to determine whether G is embeddable in ak n grid with unit congestion for any fixed integer k 3. In addition, we show a necessary and sufficient condition for G to be embeddable in a 2 grid with unit congestion, and show that G satisfying the condition is embeddable in a 2 |V(G)| grid. Based on the characterization, we suggest a linear time algorithm for recognizing graphs embeddable in a 2 grid with unit congestion.

A simple and convenient approach for a radial symmetrical point detection is proposed. In this paper the real part-only synthesis is utilized in order to make an origin symmetric pattern of the original image and to perform automatically the calculation of its autocorrelation for the detection of the symmetry center of the image.

A new superresolution technique is proposed for high-resolution estimation of the scattering analysis. For complicated multipath propagation environment, it is not enough to estimate only the delay-times of the signals. Some other information should be required to identify the signal path. The proposed method can estimate the frequency characteristic of each signal in addition to its delay-time. One method called modified (Root) MUSIC algorithm is known as a technique that can treat both of the parameters (frequency characteristic and delay-time). However, the method is based on some approximations in the signal decorrelation, that sometimes make problems. Therefore, further modification should be needed to apply the method to the complicated scattering analysis. In this paper, we propose to apply a time-domain null filtering scheme to reduce some of the dominant signal components. It can be shown by a simple experiment that the new technique can enhance estimation accuracy of the frequency characteristic in the Root-MUSIC algorithm.

It is demonstrated with the Berlekamp-Massey shift-register synthesis algorithm that the linear complexity value of binary complementary sequences is at least 3/4 of the sequence length. For some sequence pairs the linear complexity value can be even 0.98 times the sequence length. In the light of these results strongly non-linear complementary sequences are considered suitable for information security applications employing the spread-spectrum (SS) technique.

It is well recognized that the electromagnetic interference due to indirect electrostatic discharge (ESD) is not always proportional to the ESD voltage and also that the lower voltage ESD sometimes causes the more serious failure to high-tech information equipment. In order to theoretically examine the peculiar phenomenon, we propose an analytical approach to model the indirect ESD effect. A source ESD model is given here using the spark resistance presented by Rompe and Weizel. Transient electromagnetic fields due to the ESD event are analyzed, which are compared with the experimental data carefully given by Wilson and Ma. A model experiment for indirect ESD is also conducted to confirm the validity of the ESD model presented here.

In the business systems design learning environment, there may be more than one solution to any given problem. For instance, the data model will be different depending on each learner's perspective. Accordingly, group learning systems are very effective in this domain. We have developed CAMELOT (Collaborative and Multimedia Environment for Learners on Teams) [18] using the Nominal Group Technique for group problem solving. In this paper, the basic framework of the collaborative learning system and the effectiveness of collaborative learning in designing the Data Model are described. By using CAMELOT, each learner learns how to analyze through case studies and how to cooperate with his or her group in problem solving. Learners come to a deeper understanding from using CAMELOT than from studying independently because they are enabled to reach better solutions through discussion, tips from other learners, and examination of one another's works.

This paper describes the design of a high-speed 4-2 compressor for fast multipliers. Through the survey of the six kinds of representative conventional 4-2 compressor (RBA 1-3 and NBA 1-3) in both the redundant binary (RB) and the normal binary (NB) scheme, we extracted two problems that degrades the operating speed. The first is the use of multi-input complex gates and the second is the existence of transmission gates (TG) at the input and/or output stages. To solve these problems, we propose high-speed 4-2 compressors using the RB scheme, which we call the high-speed redundant binary adders (HSRBAs). Six kinds of HSRBAs, HSRBA 1-6, were derived by making the Boolean equations suitable for high-speed CMOS circuits. Among them, HSRBA2, HSRBA4 and HSRBA6 have no multi-input complex gate and input/output TG, and perform at a delay time of 0.89 ns which is the fastest of all 4-2 compressors. We investigated the logical relation between HSRBAs and conventional 4-2 compressors by analyzing the Boolean equations for each circuit. This investigation shows that all the conventional redundant binary adders RBA1-3 have the same logic structures as HSRBA2. We also showed the conventional normal binary adders NBA1-3 have the same logic structures as HSRBA1, HSRBA3 and HSRBA5, respectively. This implies all 4-2 compressors can be derived from the same equation regardless of RB or NB. We applied the HSRBA2 to a 5454-bit multiplier using 0.5-µm CMOS technology. The multiplication time at the supply voltage of 3.3 V was 8.8 ns. This is the fastest 5454-bit multiplier with 0.5-µm CMOS so far, and 83% of the speed improvement is due to the high speed 4-2 compressor.

It has become very important to study the lightning surges that flow into telecommunications equipment because of the increased use of circuits susceptible to excess voltage. This paper reports for the first time simultaneous measurements of distributed lightning current at many positions in a mountain-top radio relay station caused by natural direct lightning strikes. More than 90% of the direct lightning current flowed from the lightning rod to the ground through building structural components such as antenna tower legs, waveguides, and so on, with the high frequency components of the lightning current tending to flow into the outside parts of those structural components. And then, 25 to 43 % of the lightning current flowed out again to outside telecommunications cables and power lines because the lightning current raised the station's ground potential. Based on these measurements, to help predict lightning current which is dangerous to telecommunications equipment, lightning current occurrence probabilities at the waveguide and cables were estimated by analyzing the distribution ratios between the current in those components.

Polynomials are called permutation polynomials if they induce bijective functions. This paper investigates algebraic properties of permutation polynomials over a finite field, especially properties associated with permutation cycles. A permutation polynomial has a simple structure but good randomness properties suitable for applications. The cycle structure of permutations are considered to be related to randomness. We investigate the algebraic structure from the viewpoint of randomness. First we show the relationship between polynomials and permutations using a matrix equation. Then, we give a general form of a permutation polynomial corresponding to a product C1C2Ck of pairwise disjoint cycles. Finally, permutation polynomials with fixed points -or with 2, 3 and 4-cycles -and their compositions are given together with distribution of degree of the permutation polynomials.

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.

This letter describes the collector-short technique for improving the blocking capability of the lateral IGBT (LIGBT) on the SOI film. The concept of our proposed techniques is to prevent the injection of the minority carrier from the collector region to the high electric field area. This can be done by replacing the p+-collector layer at the sharp corner of the collector region, where the potential distribution in the device is subject to the diffusion curvature effect of the n-buffer layer, with the n+-collector-short layer. By only introducing the collector-short region to the sharp corner of the collector region, an increase of about 40 V in the breakdown voltage over the LIGBT without the collector-short region can be achieved.

Various kinds of new architectures have been proposed to enhance operating performance of the DRAM. This paper reviews these architectures including EDO, SDRAM, RDRAM, EDRAM, and CDRAM. The EDO slightly modifies the output control of the conventional DRAM architecture. Other innovative architectures try to enhance the performance by taking advantage of DRAM's internal multiple bits architecture with internal pipeline, parallel-serial conversion, or static buffers/on-chip cache. A quantitative analysis based on an assumption of wait cycles was made to compare PC system performance with some architectures. The calculation indicated the effectiveness of external or on-chip cache. Future trends cover high-speed I/O interface, unified memory architecture, and system integrated memory. The interface includes limited I/O swing such as HSTL and SSTL to realize more than 100MHz operation. Also, Ramlink and SyncLink are briefly reviewed as candidates for next generation interface. Unified memory architecture attempts to save total memory capacity by combining graphics and main memory. Advanced device technology enables system integration which combine system logic and memory. It suggests one potential direction towards system on a chip in the future.

The base transit time of an Aluminum-graded-base PNp AlGaAs/GaAs heterojunction bipolar transistor (HBT) was studied in order to clarify the effect of aluminum grading in the base. Theoretical analysis using a classical drift diffusion model with velocity saturation at the base-collector junction and a high base quasielectric field (58 keV/cm) created by 20%-aluminum linear grading in a 400 base, leads to a base transit time (τb) of 0.9 ps. The base transit time is reduced by four times, compared to the base transit time of 3.6 ps without aluminum grading in the base. In order to demonstrate this advantage, we fabricated aluminum-graded-base PNp AlGaAs/GaAs heterojunction transistor which employs a 20%-aluminum linear graded 400 -wide base. The device with a 2 µm 10 µm emitter showed high RF performance with a cut-off frequency (ft) of 37 GHz and a maximum oscillation frequency (fmax) of 30 GHz at a collector current density of 3.4 104 A/cm2. Further analysis using direct parameter extraction of a small signal circuit model under the collector current density of 1.1-9.9104 A/cm2 indicated the intrinsic transit time, which is the sum of the base transit time and the collector depletion layer transit time (τSC), was as low as 2.3 ps under lowinjection level. Subtracting the collector depletion-layer transit time from the intrinsic time leads to a base transit time of 1.1 ps, which is close to the theoretical base transit time and is the shortest value ever reported. The structure is very attractive for pnp-type AlGaAs HBTs combined with Npn HBTs for complementary applications.

Using fundamental device and circuits, we have realized three functions required for synaptic connections in self-organizing neural networks: long term memory of synaptic weights, fixed total amount of synaptic weights in a neuron, and lateral inhibition. The first two functions have been condensed into an optical adaptive device and circuits with floating gates. Lateral inhibition has been realized by a winner-take-all circuit and a following lateral excitatory connection circuit. We have fabricated these devices and circuits using CMOS technology and confirmed the three functions. In addition, topological mapping, which is essential for feature extraction, has been formed in a primitive network constructed with the fundamental device and circuits.

For the purpose of automatic speech recognition, language models (LMs) are used to predict possible succeeding words for a given partial word sequence and thereby to reduce the search space. In this paper several kinds of stochastic language models (SLMs) are evaluated-bigram, trigram, hidden Markov model (HMM), bigram-HMM, stochastic context-free grammar (SCFG) and hand-written Bunsetsu Grammar. To compare the predictive power of these SLMs, the evaluation was conducted from two points of views: (1) relationship between the number of model parameters and entropy, (2) predictive rate of succeeding part of speech (POS) and succeeding word. We propose a new type of bigram-HMM and compare it with the other models. Two kinds of approximations are tried and examined through experiments. Results based on both of English Brown-Corpus and Japanese ATR dialog database showed that the extended bigram-HMM had better performance than the others and was more suitable to be a language model.