This paper proposes the iterative quasi-oldest-cell-first (i-QOCF) scheduling algorithm, a new scheduling algorithm for input-queued ATM switches with virtual output queuing (VOQ). In the i-QOCF scheduling algorithm, each input port and each output port maintains its own list. The length of the list can be N, 2 N, ..., B N, where B is the size of the separate queue for an output port at input ports, and N is the number of output ports. The list maintained by an input port contains the identifiers for those output ports to which that input port will send a cell. The list maintained by an output port contains the identifiers for input ports that have a cell destined for that output port. If we use a list whose length is B N, then the identifiers in the list appear in the oldest order, and i-QOCF gives preference to cells that have been waiting for the longest time. If we use a list whose length is less than B N, then the identifiers in the list appear in the quasi-oldest order, and i-QOCF gives preference to cells that have been waiting for the quasi-longest time. We determine the performance of i-QOCF in a comparison with i-OCF in terms of cell delay time. We find that an input-queued ATM switch with i-QOCF and VOQ can achieve 100% throughput for independent arrival processes. Under uniform traffic, 3-QOCF is enough to achieve convergence during one cell time. If we use 3-QOCF, the list length is 3 N, then its cell delay time is almost the same as that of 4-OCF (Oldest-Cell-First).

It is proposed a novel method that optimizes nonlinear filters by unsupervised learning using a novel definition of morphological pattern spectrum, called "morphological opening/closing spectrum (MOCS)." The MOCS can separate smaller portions of image objects from approximate shapes even if the shapes are degraded by noisy pixels. Our optimization method analogizes the linear low-pass filtering and Fourier spectrum: filter parameters are adjusted to reduce the portions of smaller sizes in MOCS, since they are regarded as the contributions of noises like high-frequency components. This method has an advantage that it uses only target noisy images and requires no example of ideal outputs. Experimental results of applications of this method to optimization of morphological open-closing filter for binary images are presented.

Combined input output queued (CIOQ) architecture such as crossbar with speedup has recently been proposed to build a large capacity switch for broadband integrated services networks. It was shown that, for a speedup factor of 2, a CIOQ switch can achieve 100% throughput with a simple maximal matching algorithm. Achieving 100% throughput, however, is not sufficient for per-connection quality of service (QoS) guarantee. In [2],[3], it is proved that a CIOQ switch with a speedup factor of 2 can exactly emulate an output queued (OQ) switch if stable matching is adopted. Unfortunately, the complexity of currently known algorithms makes stable matching impractical for high-speed switches. In this paper, we propose a new matching algorithm called the least cushion first/most urgent first (LCF/MUF) algorithm and formally prove that a CIOQ switch with a speedup factor of 2 can exactly emulate an OQ switch which adopts any service discipline for cell transmission. A potential implementation of our proposed matching algorithm for strict priority service discipline is also presented.

A new phasor model of neural networks is proposed in which the state of each neuron possibly takes the value at the origin as well as on the unit circle. A stability property of equilibria is studied in association with the energy landscape. It is shown that a simple condition guarantees an equilibrium to be asymptotically stable.

This paper proposes an Iterated Function System (IFS) which can reduce effects of quantization errors of the IFS parameters. The proposed method skips conventional analog-parameter search and directly selects optimum IFS parameters from pools of discrete IFS parameters. In conventional IFS-based image coding the IFS parameters are quantized after their analog optimum values are determined. The image reconstructed from the quantized parameters is degraded with errors that are traced back to quantization errors amplified in the iterated mappings. The effectiveness of this new realistic approach is demonstrated by simulation results over the conventional method.

Future high-speed switches and routers will be expected to support a large number of ports at high line rates carrying traffic with diverse statistical properties. Accordingly, scheduling mechanisms will be required to handle Tbit/sec aggregated capacity while providing quality of service (QoS) guarantees. In this paper a novel high-capacity switching scheme for ATM/WDM networks is presented. The proposed architecture is contention-free, scalable, easy to implement and requires no internal "speedup. " Non-uniform destination distribution and bursty cell arrivals are examined when studying the switching performance. Simulation results show that at an aggregated throughput of 1 Tbit/sec, low latency is achieved, yielding a powerful solution for high-performance packet-switch networks.

The genetic algorithm is used to synthesize the directional circular arc array as a sectored antenna. Then, the performance of this sectored antenna in indoor wireless millimeter wave channel is investigated. Based on the desired pattern and the topography of the antennas, the synthesis problem can be reformulated into an optimization problem and solved by the genetic algorithm. The genetic algorithm will always converge to global extreme instead of local extreme and achieves a good approximation to the desired pattern. Next, the impulse responses of the indoor channel for any transmitter-receiver location are computed by shooting and bouncing ray/image techniques. By using the impulse response of multipath channel, the performance of the sectored antenna on BPSK (binary phase shift keying) system with phase and timing recovery circuits is presented. Numerical results show that the synthesized sectored antenna is effective to combat the multipath fading and can increase the transmission rate of indoor millimeter wave system.

The purpose of this paper is to deal with the problem of recovering a signal from its noisy version. One example is to restore old images degraded by noise. The recovery solution is given within the framework of series expansion and we shall show that for the general case the recovery functions have to be elements of an extended pseudo biorthogonal basis (EPBOB) in order to suppress efficiently the corruption noise. After we discuss the different situations of noise, we provide some methods to construct the optimal EPBOB in order to deal with these situations.

Prefetching is a promising approach to tackle the memory latency problem. Two basic variants of hardware data prefetching methods are sequential prefetching and stride prefetching. The latter based on stride calculation of future references has the potential to out-perform the former which is based on the data locality. In this paper, a typical stride prefetching and its improved version, adaptive stride prefetching, are compared in quantitative way using simulation for some parallel benchmark programs in the context of uniform memory access and non-uniform memory access architectures. The simulation results show that adaptability of stride is essential since the proposed adaptive scheme can reduce pending stall time which is large in the typical scheme.

In this paper, we present two parallel algorithms for computing the all nearest neighbors of an n n binary image on the Bulk-Synchronous Parallel(BSP) model. The BSP model is an asynchronous parallel computing model, where its communication features are abstracted by two parameters L and g: L denotes synchronization periodicity and g denotes a reciprocal of communication bandwidth. We propose two parallel algorithms for the all nearest neighbor problems based on two distance metrics. The first algorithm is for Lp distance, and the second algorithm is for weighted distance. Both two algorithms run in O(n2/p + L) computation time and in O(g(n/p) + L) communication time using p (1 p n) processors and in O(n2/p + (d+L)(log(p/n)/log(d+1))) computation time and in O(g(n/p) + (gd+L)(log(p/n)/log(d+1))) communication time using p (n< p n2) processors on the BSP model, for any integer d(1 dp/n).

This paper describes embeddings of chordal rings and pyramids into mesh-connected computers with multiple buses which have a bus on each row and each column, called MCCMBs. MCCMBs have two types of communication. The one is local communication, provided by local links, and the other is global communication, provided by buses. By efficiently combining the two types of communication, optimal or efficient embeddings are achieved. For a large set of chordal rings, optimal embeddings, whose expansion, load, dilation and congestion are 1, are given. For pyramids, an efficient embedding based on a two phase strategy is presented. The embedding balances dilation and congestion.

Building robots is generally considered difficult, because the designer not only has to predict the interactions between the robot and the environment, but also has to deal with the consequent problems. In recent years, evolutionary algorithms have been proposed to synthesize robot controllers. However, admittedly, it is not satisfactory enough just to evolve the control system, because the performance of the control system depends on other hardware parameters -- the robot body plan -- which might include body size, wheel radius, motor time constant, etc. Therefore, the robot body plan itself should, ideally, also adapt to the task that the evolved robot is expected to accomplish. In this paper, a hybrid GP/GA framework is presented to evolve complete robot systems, including controllers and bodies, to achieve fitness-specified tasks. In order to assess the performance of the developed system, we use it with a fixed robot body plan to evolve controllers for a variety of tasks at first, then to evolve complete robot systems. Experimental results show the promise of our system.

A nonlinear inverse filter is proposed for restoring signals degraded by a linear system and additive Gaussian noise. The proposed filter consists of combination of a linear high pass filter and an ε-filter, which is modified from the cascaded linear filter. The nonlinear property of the ε-filter is utilized to suppress pre-enhanced additive random noise and to restore sharp edges. It is demonstrated that the filter can be reduced to a multi-layered neural network model, and the optimal design is described by using the back propagation algorithm. The nonlinear function is approximated by a piecewise linear function, which results in simple and robust training algorithm. An application to image restoration is also presented, illustrating the effectiveness over the linear filter, especially when the amplitude of additive noise is small.

The operation of a novel all-optical wavelength converter based on directionally-coupled semiconductor optical amplifiers is described. Merits such as extinction enhancement and digital response are expected through a simple analytical model and a sophisticated transfer matrix method developed to take into account the spatial distributions of the optical power, carrier density, refractive index, propagation constant, and coupling coefficient along device. We fabricated devices operating at 1.55 µm band using an InGaAsP/InP material system and demonstrated successfully the static characteristics of wavelength conversion with the expected advantages. Devices are as small as 1.5 mm and do not need any active/passive integration step during fabrication.

This paper investigates some fundamental properties of 2-way alternating multi-counter automata (2amca's) with only existential (universal) states which have sublinear space and 1 inkdot. It is shown that for any function s(n) log n such that log s(n)=o(log n), s(n) space-bounded 1-inkdot 2amca's with only existential states are incomparable with the ones with only universal states, and the ones with only existential (universal) states are not closed under complementation.

An ATMS (Assumption-based Truth Maintenance System) has been widely used for maintaining the truth of an information by detecting and solving the contradictions in rule-based systems. However, the ATMS cannot correctly maintain the truth of the information in case that the generated information is satisfied within a time interval or includes data about temporal relations of events in time varying situations, because it has no mechanism manipulating temporal data. In this paper, we propose the extended ATMS that can maintain the truth of the information in the knowledge-based system using information changing over time or temporal relations of events. To maintain the contexts generated by relations of events, we modify the label representation method, the disjunction and conjunction simplification method in the label-propagation procedure and the nogood handling method of the conventional ATMS.

This paper describes a distributed traffic control scheme for large multi-stage ATM switching systems. When a new virtual circuit is to be added from some source line-interface unit (LU) to a destination LU, the system must find an optimal path through the system to accommodate the new circuit. Conventional systems have a central control processor and control lines to manage the bandwidth of all the links in the systems. The central control processor handles all the virtual circuits, but have trouble doing this when the switching system becomes large because of the limited ability of the central processor to handle the number of virtual circuits. A large switching system with Tbit/s-class throughput requires a distributed traffic control scheme. In our proposed switching system, each port of the basic switches has its own traffic monitor. Operation, administration, and maintenance (OAM) cells that are defined inside the system carry the path-congestion information to the LUs, enabling each LU to route new virtual circuits independently. A central control processor and control lines are not required. The performance of the proposed system depends on the interval between OAM cells. This paper shows how an optimal interval can be determined in order to maximize the bandwidth for user cells. This traffic control scheme will suit future Tbit/s ATM switching systems.

Input buffered switches most efficiently use memory and switch bandwidth. With Virtual Output Queueing (VOQ), head-of-line blocking can be avoided, thus breaking the throughput barrier of 58.6%. In this paper a switch architecture based on VOQ is proposed, which offers deterministic and stochastic delay bounds for prioritized traffic. This is achieved by a hybrid static and dynamic arbitration scheme, which matches ports both by a precalculated schedule and realtime calculations. By using weighted dynamic arbitration algorithms 100% throughput with lowest delays under all admissible traffic can be achieved. An integrated global priority scheme allows the multiplexing of realtime and data traffic. Following the arbitration decision, a cell scheduler decides locally in the input ports upon the next connection from which a cell is forwarded. Cell scheduling based on earliest-deadline-first (EDF) is shown to perform similar to its behaviour in an output-queued switch.

This paper describes a nonblind digital beamformer for SDMA (space division multiple access) systems used when channels are power-limited. An array antenna with many elements is usually required to obtain high antenna gain for the reception of a low-level desired signal and the degree of freedom for the spatial discrimination of many users using the same frequency. The proposed beamformer is designed for such array antennas by employing the combination of a multibeam former and a maximal-ratio-combining (MRC) technique. The MRC technique is extended to a nonblind combiner that uses a training sequence contained in the desired signal. Basic analysis and numerical simulations of its performance, under the power-limited condition and with fixed user terminals, show that the speed and robustness of desired-signal acquisition and undesired-signal suppression may outperform recursive-least-squares (RLS) beamformer with less computation, when it is applied to an array antenna with many elements.

A 24-bit, 96 kHz stereo A/D converter (ADC) for DVD-audio has been developed. The single-chip integrates stereo delta-sigma modulators (Δ ΣM's), a voltage reference, and a decimation filter. A fourth-order cascaded Δ ΣM using a local feedback technique was employed to avoid overload without sacrificing noise performance. Low power switched-capacitor techniques were used for implementation. A two-stage decimation filter architecture that reduces digital switching noise was also developed. A merged multi-stage comb filter was used for the first stage, and a bit-serial finite-impulse-response (FIR) filter was used for the second stage. The 18.0 mm2 chip was fabricated in 0.6-µm CMOS with low threshold devices. Measured results show 117 dB A-weighted dynamic range in the 20 kHz passband, with 470 mW power dissipation at 5 V operation.