Naotoshi ADACHI Shoji KASAHARA Yutaka TAKAHASHI
The ATM-ABR service category provides minimum cell rate (MCR) guarantees and robust connections even with insufficient network resources. Recently proposed rate-management algorithms for supporting multimedia applications over ABR mainly aim at minimizing the cell loss and delay. However, jitter is also an important element of QoS for multimedia applications. In this paper, we focus our attention on the arrival point of the critical cell corresponding to the end of data packet and propose a simple cell scheduling scheme for source node to reduce the jitter on application level over the ATM-ABR service class. In our proposed method, critical cells are delayed intentionally and the packet stream at application level becomes smooth. We verify the effectiveness of our proposed algorithm by an analytical model and simulation. From those results, we find that our proposed scheduling algorithm is effective in reducing the application level jitter even when the tagged cell stream is transmitted along the path with multiple nodes.
Mitsuyoshi KISHIHARA Isao OHTA Tadashi KAWAI Kuniyoshi YAMANE
Directional couplers with flat coupling are designed by using an asymmetrical coupled-HNRD-guide consisting of two HNRD guides of different cross sections arranged closely. First, propagation characteristics of the asymmetrical coupled-HNRD-guide are analyzed by the transverse resonance technique. Next, the whole directional couplers including tapered sections are designed from the S-parameters of the coupled HNRD guides derived from a superposition of the even-like and odd-like modes. Finally, the validity of the design procedure is confirmed by an em-simulator (HFSS).
Akiyoshi SHIMADA Hiroshi NARUSE Kiyoshi UZAWA Gaku KIMURA Hideaki MURAYAMA Kazuro KAGEYAMA
This paper describes a method for assessing the structural integrity of International America's Cup Class (IACC) yachts using a fiber optic distributed strain sensor. IACC yachts are made of advanced composite materials designed for high stiffness and lightness, however, a number of critical accidents have occurred during sailing. So we developed a health monitoring system and applied it to two Japanese IACC yachts to measure the distributed strain by using an optical fiber sensor installed in their hulls. We then estimated the three-dimensional distributed strain and compared the results with simulated data obtained by finite element analysis (FEA) to confirm the designed strength of these yachts.
Takeshi OHNO Koichi OGAWA Toshihiro TERAOKA Jiro HIROKAWA
A slot pair array using a post-wall waveguide is a promising candidate for a Fixed Wireless Access (FWA) sector antenna to be used in a base station. This array is formed by a traveling wave antenna, and therefore its main beam direction varies with frequency. To overcome this difficulty, we propose a new structure that comprises of a cosecant array and an additional Talor array. This structure can fix the main beam in a constant direction whilst maintaining a cosecant radiation pattern. We conducted an investigation based on an array factor, and the validity of the method was confirmed by experiment.
Javad HADDADNIA Karim FAEZ Majid AHMADI Payman MOALLEM
This paper presents an efficient Hybrid Learning Algorithm (HLA) for Radial Basis Function Neural Network (RBFNN). The HLA combines the gradient method and the linear least squared method for adjusting the RBF parameters and connection weights. The number of hidden neurons and their characteristics are determined using an unsupervised clustering procedure, and are used as input parameters to the learning algorithm. We demonstrate that the HLA, while providing faster convergence in training phase, is also less sensitive to training and testing patterns. The proposed HLA in conjunction with RBFNN is used as a classifier in a face recognition system to show the usefulness of the learning algorithm. The inputs to the RBFNN are the feature vectors obtained by combining shape information and Pseudo Zernike Moment (PZM). Simulation results on the Olivetti Research Laboratory (ORL) database and comparison with other algorithms indicate that the HLA yields excellent recognition rate with less hidden neurons in human face recognition.
Hanmin JUNG Gary Geunbae LEE Won Seug CHOI KyungKoo MIN Jungyun SEO
This paper describes a highly-portable multilingual question answering system on multiple relational databases. We apply techniques which were verified on open-domain text-based question answering, such as semantic category and pattern-based grammars, into natural language interfaces to relational databases. Lexico-semantic pattern (LSP) and multi-level grammars achieve portability of languages, domains, and DB management systems. The LSP-based linguistic processing does not require deep analysis that sacrifices robustness and flexibility, but can handle delicate natural language questions. To maximize portability, we drive three dependency factors into the following two parts: language-dependent part into front linguistic analysis, and domain-dependent and database-dependent parts into backend SQL query generation. We also support session-based dialog by preserving SQL queries created from previous user's question, and then re-generating new SQL query for the successive questions. Experiments with 779 queries generate only constraint-missing errors, which can be easily corrected by adding new terms, of 2.25% for English and 5.67% for Korean.
Hiroshi NAGAMOCHI Shuji NAKAMURA Toshimasa ISHII
It is known that all minimum cuts in an edge-weighted undirected graph with n vertices and m edges can be represented by a cactus with O(n) vertices and edges, a connected graph in which each edge is contained in an exactly one cycle. In this paper, we show that such a cactus representation can be computed in O(mn+n2log n) time and O(m) space. This improves the previously best complexity of deterministic cactus construction algorithms, and matches with the time bound of the fastest deterministic algorithm for computing a single minimum cut.
Tomoya FUJINO Shuji ISOBE Xiao ZHOU Takao NISHIZEKI
Assume that each edge e of a graph G is assigned a list (set) L(e) of colors. Then an edge-coloring of G is called an L-edge-coloring if each edge e of G is colored with a color contained in L(e). It is known that any series-parallel simple graph G has an L-edge-coloring if either (i) |L(e)| max{4,d(v),d(w)} for each edge e=vw or (ii) the maximum degree of G is at most three and |L(e)| 3 for each edge e, where d(v) and d(w) are the degrees of the ends v and w of e, respectively. In this paper we give a linear-time algorithm for finding such an L-edge-coloring of a series-parallel graph G.
Takehiro ITO Takao NISHIZEKI Xiao ZHOU
Let each vertex v of a graph G have a positive integer weight ω(v). Then a multicoloring of G is to assign each vertex v a set of ω(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. A partial k-tree is a graph with tree-width bounded by a fixed constant k. This paper presents an algorithm which finds a multicoloring of any given partial k-tree G with the minimum number of colors. The computation time of the algorithm is bounded by a polynomial in the number of vertices and the maximum weight of vertices in G.
Masatoshi MORITA Katsushi INOUE Akira ITO Yue WANG
This paper investigates properties of space-bounded "two-dimensional Turing machines (2-tm's)," whose input tapes are restricted to square ones, with bounded input head reversals in vertical direction. We first investigate a relationship between determinism and nondeterminism for space-bounded and input head reversal-bounded 2-tm's. We then investigate how the number of input head reversals affects the accepting power of sublinearly space-bounded 2-tm's. Finally, we investigate necessary and sufficient spaces for three-way 2-tm's to simulate four-way two-dimensional finite automata with constant input head reversals.
Eiju HIROWATARI Kouichi HIRATA Tetsuhiro MIYAHARA Setsuo ARIKAWA
This paper investigates the interaction of mind changes and anomalies for inductive inference of recursive real-valued functions. We show that the criteria for inductive inference of recursive real-valued functions by bounding the number of mind changes and anomalies preserve the same hierarchy as that of recursive functions, if the length of each anomaly as an interval is bounded. However, we also show that, without bounding it, the hierarchy of some criteria collapses. More precisely, while the class of recursive real-valued functions inferable in the limit allowing no more than one anomaly is properly contained in the class allowing just two anomalies, the latter class coincides with the class allowing arbitrary and bounded number of anomalies.
This paper defines the distributed arrangement selection problem in a line network in a distributed context and describes the design of a strictly-time-optimal algorithm which solves the problem with a limited local memory space. The problem is regarded as a combined distributed sorting and k-selection problem, namely a problem of sorting elements that are not larger than the kth minimum element in predetermined processes. The algorithm also provides a solution to a resource allocation problem in a line network in a strictly-optimal time.
In this paper, we consider the problem of multicasting a message in k-ary n-cubes under the store-and-forward model. The objective of the problem is to minimize the size of the resultant multicast tree by keeping the distance to each destination over the tree the same as the distance in the original graph. In the following, we first propose an algorithm that grows a multicast tree in a greedy manner, in the sense that for each intermediate vertex of the tree, the outgoing edges of the vertex are selected in a non-increasing order of the number of destinations that can use the edge in a shortest path to the destination. We then evaluate the goodness of the algorithm in terms of the worst case ratio of the size of the generated tree to the size of an optimal tree. It is proved that for any k 5 and n 6, the performnance ratio of the greedy algorithm is c kn - o(n) for some constant 1/12 c 1/2.
Masataka TAKAMURA Yoshihide IGARASHI
We propose two simple algorithms based on bounded tickets for the mutual exclusion problem on the asynchronous single-writer/multi-reader shared memory model. These algorithms are modifications of the Bakery algorithm. An unattractive property of the Bakery algorithm is that the size of its shared memory is unbounded. Initially we design a provisional algorithm based on bounded tickets. It guarantees mutual exclusion in the case where a certain condition is satisfied. To remove the condition, we use an additional process that does not correspond to any user. The algorithm with the additional process is a lockout-free mutual exclusion algorithm on the asynchronous single-writer/multi-reader shared memory model. We then modify this algorithm to reduce the shared memory size with the cost of using another additional process. The maximum waiting time using each of the algorithms proposed in this paper is bounded by (n-1)c+O(nl), where n is the number of users, l is an upper bound on the time between two successive atomic steps, and c is an upper bound on the time that any user spends using the resource. The shared memory size needed by the first algorithm and the second algorithm are (n+1)(1+log (4n)) bits and n(1+log (4n-4))+2 bits, respectively.
In this paper, parallelization methods for quantum circuits are studied, where parallelization of quantum circuits means to reconstruct a given quantum circuit to one which realizes the same quantum computation with a smaller depth, and it is based on using additional bits, called ancillae, each of which is initialized to be in a certain state. We propose parallelization methods in terms of the number of available ancillae, for three types of quantum circuits. The proposed parallelization methods are more general than previous one in the sense that the methods are applicable when the number of available ancillae is fixed arbitrarily. As consequences, for the three types of n-bit quantum circuits, we show new upper bounds of the number of ancillae for parallelizing to logarithmic depth, which are 1/log n of previous upper bounds.
Yoshinori TAKEI Toshinori YOSHIKAWA Xi ZHANG
As pseudorandom number generators for Monte Carlo simulations, inversive linear congruential generators (ICG) have some advantages compared with traditional linear congruential generators. It has been shown that a sequence generated by an ICG has a low discrepancy even if the length of the sequence is far shorter than its period. In this paper, we formulate fractional linear congruential generators (FCG), a generalized concept of the inversive linear congruential generators. It is shown that the sequence generated by an FCG is a geometrical shift of a sequence from an ICG and satisfies the same upper bounds of discrepancy. As an application of the general formulation, we show that under certain condition, "Leap-Frog technique," a way of splitting a random number sequence to parallel sequences, can be applied to the ICG or FCG with no extra cost on discrepancy.
Mahmoud MERIBOUT Masato MOTOMURA
The aim of this paper is to present a new cost estimation technique to synthesis hardware from high level circuit description. The scheduling and allocation processes are performed in alternative manner, while using realistic cost measurements models that account for Functional Unit (FU), registers, and multiplexers. This is an improvement over previous works, were most of them use very simple cost models that primarily focus on FU resources alone. These latest, however, are not accurate enough to allow effective design space exploration since the effects of storage and interconnect resources can indeed dominates the cost function. We tested our technique on several high-level synthesis benchmarks. The results indicate that the tool can generate near-optimal bus-based and multiplexer-based architectural models with lower number of registers and buses, while presenting high throughput.
Hajime SHIBATA Soji MORI Nobuo FUJII
An automated synthesis for analog computational circuits in transistor-level configuration is presented. A cell-based structure is introduced to place moderate constraints on the MOSFET circuit topology. Even though each cell has a simple structure that consists of one current path with four transistors, common analog building blocks can be implemented using combinations of the cells. A genetic algorithm is applied to search circuit topologies and transistor sizes that satisfy given specifications. Synthesis capabilities are demonstrated through examples of three types of computational circuits; absolute value, squaring, and cubing functions by using computer simulations and real hardware.
Junho JEONG Jitae SHIN Doug Young SUH
In the past, enhancement techniques for the end-to-end quality of a networked application were studied by looking at each individual layer. Examples of such techniques include the error resilience/concealment methods in the application layer, the FEC/ARQ in the transport layer, and the Quality of Service (QoS) techniques in the network layers. However, an integrated approach that would look across all related layers had yet to be investigated. This paper proposes an approach that combines priority-aware video packetization, adaptively used layered FEC, and QoS controlled networks such as IntServ and DiffServ in order to provide an efficient end-to-end quality in layered streaming video. The combination is more efficient in terms of a simple network price mechanism, that is, in getting the best end-to-end quality under a given total cost constraint. Our proposed approach in DiffServ with video packet (VP) data-splitting and layered FEC guarantees minimal service quality in a scalable and cost effective manner without introducing resource reservation. For video, we also propose performance metrics such as corrupted/frozen frame ratio (CFR, FFR). These provide objective metrics like PSNR as well as a measurement for subjective perceptions. Our approach, which combines related layers such as video coding, transport, and network, has yielded results that have proven to be more cost-effective and practical than the supporting network QoS.
Muneo KUSHIMA Koichi TANNO Okihiko ISHIZUKA
In this paper, a voltage-controlled linear variable resistor (VCLVR) using a floating-gate MOSFET (FG-MOSFET) is proposed. First, the grounded VCLVR realization is discussed. The proposed circuit consists of only an ordinary MOSFET and an FG-MOSFET. The advantages of the proposed VCLVR are low-power and wide-input range and also the power consumption of the proposed VCLVR is the same as an ordinary passive resistor. The performance of the proposed circuits are confirmed by HSPICE simulations with a standard 0.6 µm CMOS process parameters. Simulations of the proposed VCLVR demonstrate a resistance value of 40 kΩ to 338 kΩ and an input range of 4.34 V within THD of less than 1.1%. Next, we proposed a new floating node linear variable resistor using the proposed VCLVR. The performance of the circuit is also evaluated through HSPICE.