This is a survey of algorithmic results in the theory of "discrete convex analysis" for integer-valued functions defined on integer lattice points. The theory parallels the ordinary convex analysis, covering discrete analogues of the fundamental concepts such as conjugacy, the Fenchel min-max duality, and separation theorems. The technical development is based on matroid-theoretic concepts, in particular, submodular functions and exchange axioms.

The robust induced l-norm control problem is considered for uncertain discrete-time systems. We propose a state feedback and an output feedback controller that quadratically stabilize the systems and satisfy a given constraint on the induced l-norm. Both controllers are constructed by solving a set of scalar-dependent linear matrix inequalities (LMI's), and the gain matrices are characterized by the solution to the LMI's.

An optical magnetic field measuring system using diluted magnetic semiconductors (DMS) probes is presented. The attractive features of DMS for building current/ magnetic field sensors are outlined. The system configuration includes a common-mode noise rejection scheme (CMR) to eliminate optic intensity noise induced in the fibre links by environmental vibrations. The CMR scheme relies on a pulse delay method based on the creation of two relatively delayed replicas of the photodetector output signal and their subsequent subtraction (division). Theoretical and experimental analyses of the system operation are developed and noise rejection methods using subtraction and division are presented and compared. Although CMR by division seems to be more appealing from the theoretical viewpoint (due to the rejection of intensity noise caused both by environmental vibrations and laser source output power fluctuations), in practical terms the subtraction is more reliable and easier to implement. The noise rejection figure measured experimentally is about 17 dBV for CMR both by subtraction and by division. A system calibration curve is presented. The minimum magnetic flux density detected with the system is 0.06 mT rms.

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.

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).

The Communications Research Laboratory (CRL), the National Astronomical Observatory (NAO), the Institute of Space and Astronoutical Science (ISAS), and the Telecommunication Network Laboratory Group of Nippon Telegraph and Telephone Corporation (NTT) have developed a very-long-baseline-connected-interferometry array, maximum baseline-length was 208 km, using a high-speed asynchronous transfer mode (ATM) network with an AAL1 that corresponds to the constant bit-rate protocol. The very long baseline interferometry (VLBI) observed data is transmitted through a 2.488-Gbps [STM-16/OC-48] ATM network instead of being recorded onto magnetic tape. By combining antennas via a high-speed ATM network, a highly-sensitive virtual (radio) telescope system was realized. The system was composed of two real-time VLBI networks: the Key-Stone-Project (KSP) network of CRL (which is used for measuring crustal deformation in the Tokyo metropolitan area), and the OLIVE (optically linked VLBI experiment) network of NAO and ISAS which is used for astronomy (space-VLBI). These networks operated in cooperation with NTT. In order to realize a virtual telescope, the acquired VLBI data were corrected via the ATM networks and were synthesized using the VLBI technique. The cross-correlation processing and data observation were done simultaneously in this system and radio flares on the weak radio source (HR1099) were detected.

It is important to establish the technology to accommodate best effort TCP/IP traffic over wide area ATM networks. The UBR (Unspecified Bit Rate) service category is the most typical service category for the best effort traffic, especially in the LAN environment. On the other hand, the VBR (Variable Bit Rate) service category with SCD (Selective Cell Discard) option is considered as the service category which is appropriate for wide area networks due to its fairness and minimum guarantee of the cell transmission using not only PCR (Peak Cell Rate) but SCR (Sustainable Cell Rate) and MBS (Maximum Burst Size). However, there is no actual evaluation for such service. We have, therefore, performed the experimental studies on TCP/IP over VBR with SCD along with UBR and VBR without SCD by VC (Virtual Channel) level policing when each TCP connection is mapped to a different VC. Through these experiments, we measured the link utilization of the effective data and the fairness between each obtained TCP throughput during the congestion of the ATM switch. From the results of the link utilization, the value is over 95% under the various conditions. Therefore, even in the case of the cell losses due to SCD or buffer overflow in ATM switch congestion, average throughput is almost the same as the value which equals the trunk line speed divided by the number of the accommodated TCP connections. From the results of the fairness, VBR with SCD per VC is better than UBR and also obtains better TCP throughput than VBR without SCD. Furthermore, to confirm those characteristics more generally, we adopt the accommodated TCP connections not only with the same TCP send/receive socket buffer size but with different sizes. Finally, we discuss the effectiveness between VBR with SCD and the other service categories, such as UBR and ABR (Available Bit Rate) and GFR (Guaranteed Frame Rate), and conclude that VBR with SCD is one of the most suitable ATM service categories for accommodating best effort traffic.

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.

This paper describes a new design method for multiply-adders able to process a large quantity of multimedia data. I propose a (signed digits)(unsigned digits) fixed-point multiply-add/subtract unit. The unit eliminates the problems caused by the critical one-bit arithmetic precision drop-off peculiar to the conventional (signed digits)(signed digits) fixed-point multiply scheme. By simultaneously counting in the carry-save form, based on 7-3 counters simultaneously inputting the accumulation terms and the add/sub operation terms of multiplication results, carries are propagated faster than in the conventional method.

The mathematical theory of bicomplex electromagnetic waves in two-dimensional scattering and diffraction problems is developed. The Vekua's integral expression for the two-dimensional fields valid only in the closed source-free region is generalized into the radiating field. The boundary-value problems for scattering and diffraction are formulated in the bicomplex space. The complex function of a single variable, which obeys the Cauchy-Riemann relations and thus expresses low-frequency aspects of the near field at a wedge of the scatterer, is connected with the radiating field by an integral operator having a suitable kernel. The behaviors of this complex function in the whole space are discussed together with those of the far-zone field or the amplitude of angular spectrum. The Hilbert's factorization scheme is used to find out a linear transformation from the far-zone field to the bicomplex-valued function of a single variable. This transformation is shown to be unique. The new integral expression for the field scattered by a thin metallic strip is also obtained.

Selective packet dropping policies have been used to reduce congestion and transmission of traffic that would inevitably be retransmitted. For data applications using best-effort services, packet dropping policies (PDPs) are congestion management mechanisms implemented at each intermediate node that decide, reactively or proactively, to drop packets to reduce congestion and free up precious buffer space. While the primary goal of PDPs is to avoid or combat congestion, the individual PDP designs can significantly affect application throughput, network utilization, performance fairness, and synchronization problems with multiple Transmission Control Protocol (TCP) connections. Scalability and simplicity are also important design issues. This article surveys the most important selective packet dropping policies that have been designed for best-effort traffic in ATM and IP networks, providing a comprehensive comparison between the different mechanisms.

This paper proposes a nonlinear oscillator network model for gray-level image segmentation suitable for massively parallel VLSI implementation. The model performs image segmentation in parallel using nonlinear analog dynamics. Because of the limited calculation precision in VLSI implementation, it is important to estimate the calculation precision required for proper operation. By numerical simulation, the necessary precision is estimated to be 5 bits. We propose a nonlinear oscillator network circuit using the pulse modulation approach suitable for an analog-digital merged circuit architecture. The basic operations of the nonlinear oscillator circuit and the connection weight circuit are confirmed by SPICE circuit simulation. The circuit simulation results also demonstrate that image segmentation can be performed within the order of 100 µs.

This paper presents a new distributed scheduling architecture for wireless ATM networks. Usually, in WATM scheduling architectures, a fixed order is defined among the different connections through their ATM service category (CBR VBR ABR UBR). We argue that although this static priority is easier to implement, this type of precedence is not necessarily a good choice for the MAC layer. The MAC layer scheduling should define an order such that it uses efficiently the resources while providing quality of service (QoS) guarantees. In this spirit, our architecture delays (without violating their QoS) the real time connections in order to improve the performance of non real time connections.

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.

There is increasing interest using CMOS circuits for highly integrated high frequency wireless telecommunications systems. This paper reviews recent works in transceiver architectures, circuits and devices technology for CMOS RFIC application. A number of practical problems those must be resolved in CMOS RFIC design are also discussed.

Medium access control (MAC) protocol is one of the key components for providing quality of service (QoS) in wireless ATM (W-ATM) networks. In this paper, we propose a hierarchical scheduling scheme coupled with fair queueing algorithms with adaptive weights. This scheme is intended to be applicable to a TDMA/TDD based MAC protocol. Specifically, the performance of the fair-queueing algorithm using fixed weights and adaptive weights is evaluated and compared. Simulation results show that the proposed hierarchical fair-queueing scheduling with adaptive weights (HAW) can yield a lower cell transfer delay and a higher channel utilization while maintaining fairness among multiple users.

Fuzzy rule-based edge detection using multiscale edge images is proposed. In this method, the edge image is obtained by fuzzy approximate reasoning from multiscale edge images which are obtained by derivative operators with various window sizes. The effect of utilizing multiscale edge images for edge detection is already known, but how to design the rules for deciding edges from multiscale edge images is not clarified yet. In this paper, the rules are represented in a fuzzy style, since edges are usually defined ambiguously, and the fuzzy rules are designed optimally by a training method. Here, the fuzzy approximate reasoning is expressed as a nonlinear function of the multiscale edge image data, and the nonlinear function is optimized so that the mean square error of the edge detection be the minimum. Computer simulations verify its high performance for actual images.

Muscle based face image synthesis is one of the most realistic approaches to the realization of a life-like agent in computers. A facial muscle model is composed of facial tissue elements and simulated muscles. In this model, forces are calculated effecting a facial tissue element by contraction of each muscle string, so the combination of each muscle contracting force decides a specific facial expression. This muscle parameter is determined on a trial and error basis by comparing the sample photograph and a generated image using our Muscle-Editor to generate a specific face image. In this paper, we propose the strategy of automatic estimation of facial muscle parameters from 2D markers'movements located on a face using a neural network. This corresponds to the non-realtime 3D facial motion capturing from 2D camera image under the physics based condition.

This paper presents a robust and nonblocking group membership protocol for large-scale distributed systems. This protocol uses the causal relation between membership-updating messages (i. e. , those specifying the adding and deleting of members) and allows the messages to be executed in a nonblocking manner. It differs from conventional group membership protocols in the following points: (1) neither global locking nor global synchronization is required; (2) membership-updating messages can be issued without being synchronized with each other, and they can be executed immediately after their arrival. The proposed protocol therefore is highly scalable, and is more tolerant to node and network failures and to network partitions than are the conventional protocols. This paper proves that the proposed protocol works properly as long as messages can eventually be received by their destinations. This paper also discusses some design issues, such as multicast communication of the regular messages, fault tolerance and application to reliable communication protocols (e. g. , TCP/IP).

This paper reviews design aspects of computational discovery systems through the analysis of some successful discovery systems. We first review the concept of viewscope/view on data which provides an interpretation of raw data in a specific domain. Then we relate this concept to the KDD process described by Fayyad et al. (1996) and the developer's role in computational discovery due to Langley (1998). We emphasize that integration of human experts and discovery systems is a crucial problem in designing discovery systems and claim together with the analysis of discovery systems that the concept of viewscope/view gives a way for approaching this problem.