Toshinori MORI Masakatsu SENDA
Magnetic tape incorporating a soft magnetic alloy film has been developed to reduce the electromagnetic interference (EMI) noise current in an electrical cable. The advantage of the magnetic film compared to a ferrite core is shown using an eddy current loss model. The magnetic film exhibited the expected high-loss characteristics above 30 MHz. Laminated resin gives the tape sufficient strength to be wound inside a cable sheath. The fabricated 60- and 90-µm-thick tape wound along the whole cable length exhibited noise reduction ratios of 4 to 5 dB for both radiated emission in the range from 30 to 300 MHz, and surge immunity with a magnetic substance whose volume was one-sixth that of a conventional ferrite core. The tape also exhibited no significant degradation in the mechanical and environmental tests and showed the practical durability.
Coding scheme for a noisy multiple-access adder channel is proposed. When a T-user δ-decodable affine code C is given a priori, a qT-user λ δ-decodable affine code C* is produced by using a q q matrix B satisfying BA=λ Iq q, e. g. , a Hadamard matrix or a conference matrix. In particular, the case of δ=1 is considered for the practical purposes. A (2n-1)-user uniquely decodable (δ=1) affine code Cn with arbitrary code length n is recursively constructed. When Cn plays a role of C, a q(2n-1)-user λ-decodable affine code C* is obtained. The code length and the number of users of C* are more flexible than those of the Wilson's code. The total rate of the λ-decodable code in this paper tends to be higher than that of the λ-decodable code by Wilson as the number of users increases.
Christophe MARTINEZ Paul JOUGLA Sylvain MAGNE Pierre FERDINAND
A new manufacturing process for advanced Fiber Bragg Gratings which uses phase plates is described. Its high versatility allows to achieve many type of filters in optical fibers (phase-shifted, apodised, Fabry-Perot).
Masahiko SHIMOMURA Mikio KUDO Hiroaki MOHRI
The vehicle routing and facility location fields are well-developed areas in management science and operations research application. There is an increasing recognition that effective decision-making in these fields requires the adoption of optimization software that can be embedded into a decision support system. In this paper, we describe the implementation details of our software components for solving the vehicle routing and facility location problems.
Given a combinatorial problem on a set of weighted elements, if we change the weight using a parameter, we obtain a parametric version of the problem, which is often used as a tool for solving mathematical programming problems. One interesting question is how to describe and analyze the trajectory of the solution. If we consider the trajectory of each weight function as a curve in a plane, we have a set of curves from the problem instance. The curves induces a cell complex called an arrangement, which is a popular research target in computational geometry. Especially, for the parametric version of the problem of computing the minimum weight base of a matroid or polymatroid, the trajectory of the solution becomes a subcomplex in an arrangement. We introduce the interaction between the two research areas, combinatorial optimization and computational geometry, through this bridge.
This paper surveys two methods for designing numerically robust geometric algorithms. The first method is the exact-arithmetic method, in which numerical computations are done in sufficiently high precision so that all the topological judgements can be done correctly. This method is usually accompanied with lazy evaluation and symbolic perturbation in order to reduce the computational cost and the implementation cost. The second method is the topology-oriented method, in which the consistency of the topological structure is considered as higher-priority information than numerical computation, and thus inconsistency is avoided. Both of the methods are described with the implementation examples.
This paper surveys how geometric information can be effectively used for efficient algorithms with focus on clustering problems. Given a complete weighted graph G of n vertices, is there a partition of the vertex set into k disjoint subsets so that the maximum weight of an innercluster edge (whose two endpoints both belong to the same subset) is minimized? This problem is known to be NP-complete even for k = 3. The case of k=2, that is, bipartition problem is solvable in polynomial time. On the other hand, in geometric setting where vertices are points in the plane and weights of edges equal the distances between corresponding points, the same problem is solvable in polynomial time even for k 3 as far as k is a fixed constant. For the case k=2, effective use of geometric property of an optimal solution leads to considerable improvement on the computational complexity. Other related topics are also discussed.
We survey recent developments in the study of approximation algorithms for NP-hard geometric optimization problems. We focus on those problems which, given a set of points, ask for a graph of a specified type on those points with the minimum total edge length, such as the traveling salesman problem, the Steiner minimum tree problem, and the k-minimum spanning tree problem. In a recent few years, several polynomial time approximation schemes are discovered for these problems. All of them are dynamic programming algorithms based on some geometric theorems that assert the existence of a good approximate solution with a simple recursive decomposition structure. Our emphasis is on these geometric theorems, which have potential uses in the design and analysis of heuristic algorithms.
The main problem considered is submodular set cover, the problem of minimizing a linear function under a nondecreasing submodular constraint, which generalizes both well-known set cover and minimum matroid base problems. The problem is NP-hard, and two natural greedy heuristics are introduced along with analysis of their performance. As applications of these heuristics we consider various special cases of submodular set cover, including partial cover variants of set cover and vertex cover, and node-deletion problems for hereditary and matroidal properties. An approximation bound derived for each of them is either matching or generalizing the best existing bounds.
The two dimensional mesh is widely considered to be a promising parallel architecture in its scalability. In this architecture, processors are naturally placed at intersections of horizontal and vertical grids, while there can be three different types of communication links: (i) The first type is the most popular model, called a mesh-connected computer: Each processor is connected to its four neighbours by local connections. (ii) Each processor of the second type is connected to a couple of (row and column) buses. The system is then called a mesh of buses. (iii) The third model is equipped with both buses and local connections, which is called a mesh-connected computer with buses. Mesh routing has received considerable attention for the last two decades, and a variety of algorithms have been proposed. This paper provides an overview of lower and upper bounds for algorithms, with pointers to the literature, and suggests further research directions for mesh routing.
Shiro AOKI Hiro ITO Hideyuki UEHARA Mitsuo YOKOYAMA Tsuyoshi HORINOUCHI
In this paper, a puzzle called Cell-Maze is analyzed. In this puzzle, cells are arranged in checker board squares. Each cell is rotated when a player arrives at the cell. Cell-Maze asks whether or not a player started from a start cell can reach a goal cell. The reachability problem for ordinary graphs can be easily solved in linear time, however a reachability problem for the network such as Cell-Maze may be extremely difficult. In this paper, NP-hardness of this puzzle is proved. It is proved by reducing Hamiltonian Circuit Problem of directed planar graph G such that each vertex involved in just three arcs. Furthermore, we consider subproblems, which can be solved in polynomial time.
Takao ASANO Kenichiro IWAMA Hideyuki TAKADA Yoshiko YAMASHITA
For NP-hard combinatorial optimization problems, approximation algorithms with high performances have been proposed. In many of these algorithms, mathematical programming techniques have been used and proved to be very useful. In this survey, we present recent mathematical programming techniques as well as classic fundamental techniques, by showing how these techniques are used in designing high-quality approximation algorithms for NP-hard combinatorial optimization problems.
Wei CHEN Koji NAKANO Koichi WADA
A convex hull is one of the most fundamental and interesting geometric constructs in computational geometry. Considerable research effort has focused on developing algorithms, both in serial and in parallel, for computing convex hulls. In particular, there are few problems whose parallel algorithms are so thoroughly studied as convex hull problems. In this paper, we review the convex hull parallel algorithms and their paradigm. We provide a summary of results and introduce several interesting topics including typical techniques, output-size sensitive methods, randomized approaches, and robust algorithms for convex hull problems, with which we may see the highlights of the whole research for parallel algorithms. Most of our discussion uses the PRAM (Parallel Random Access Machine) computational model, but still we give a glance at the results of the other parallel computational models such as mesh, mesh-of-trees, hypercube, recofigurable array, and models of coarse grained multicomputers like BSP and LogP.
Tomohiro OTANI Toshio KAWAZAWA Koji GOTO
The wavelength demultiplexer, using cascaded optical fiber gratings and circulators, was proposed and developed for application to optically amplified wavelength-division multiplexing (WDM) submarine cable systems with 100 GHz channel spacing. Our proposed demultiplexer cannot only achieve high wavelength selectivity, small excess loss and effective allocation of dispersion compensation fibers for each channel, but also be upgraded without affecting other existing channels. By using this demultiplexer, it has been successfully confirmed that 8 WDM channels were demultiplexed even after 6,000 km transmission including separate compensation of accumulated chromatic dispersion in each channel.
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.
Tadashi ICHIKAWA Manabu KAGAMI Hiroshi ITO
This paper reports the performance of an AC-voltage sensor with a LiNbO3 integrated retroreflective structure based on the Y-junction Mach-Zehnder interferometer. This structure is capable of realizing a low-cost sensor chip because of the small chip size and single optical-fiber connection. In the sensitivity and frequency response evaluation, detection sensitivities of 6.3 µ V / Hz have been measured with a frequency response from 6 Hz to 2 GHz. These measurement limitations were also analyzed theoretically and compared with the experimental results. This unique sensor enables precise voltage measurement in an EMI environment, even inside a computer.
Takashi HARADA Hideki SASAKI Yoshio KAMI
This paper describes the mechanisms of power-distribution-plane resonance in multilayer printed circuit boards and the techniques to control the resonance. The power-distribution-plane resonance is responsible for high-level emissions and circuit malfunctions. Controlling the resonance is an effective technique, so adequate characterization of the resonance is necessary to achieve control. The resonance characteristics of four-layer printed circuit boards are investigated experimentally and theoretically by treating the power-distribution planes as a parallel-plate transmission line with decoupling circuits. Analysis of the forward traveling wave shows that the resonance frequency is determined by the phase delay due to wave propagation and by the phase progress of interconnect inductance in the decoupling circuit. Techniques to control the resonance characteristics are investigated. The resonance can be shifted to a higher frequency by adding several decoupling circuits adjacent to the existing decoupling capacitor or by increasing the number of via holes connecting the capacitor mounting pads to the power-distribution planes.
Eiji TOBA Junji KAZAMA Hidekazu TANAKA Toyonori NISHIMATSU Hiroaki AIZAWA Hiroaki ISHIZAWA
In this paper, we will report on a fiber optic oxygen sensor using fluorescence and its application to clinical examinations. It is based on fluorescence quenching. The quenching ratio of fluorescence is proportional to oxygen partial pressure by Stern-Volmer's formula in which oxygen concentration is estimated from measured emission intensity. We fabricated a microscopic luminous probe using a Solvent Green 5 doped plastic optical fiber coupler. The probes were demonstrated to have certain advantages for example they can be operated in both liquid and gas phases. And also, they are stable to pH and flow velocities. As a clinical application, the probe can reliably measure oxygen concentrations of whole blood in vivo. Moreover, we have clarified various characteristics of this probe.
Vladimir A. SVIRID Victor de LEON Sergei N. KHOTIAINTSEV
This paper describes a fiber-optic level sensor designed to measure the level of liquid propane-butane in a relatively short range (60 cm) in the top part of storage tanks at oil refineries with the purpose of monitoring the level of this product in the filled or slightly underfilled or overfilled tanks during various measuring operations. A discrete multi-element device employing novel refractometric transducers was selected because it yields both a large measurement range and high resolution. Several innovations offer a competitive advantage to industrial users: 1) Special micro-optical refractometric transducer; 2) Efficient and economical sensor multiplexing scheme; 3) Fast level-tracking operational algorithm. The vertical resolution of the sensor -1 cm, the maximum excess pressure in the tank -40 atm (4 MPa). The sensor has the spark-proof and explosion-proof design and optical fiber interface for the transmission of the output data. The sensor successfully measured liquid propane-butane level in storage tanks during numerous cycles of measuring operations.
The technique used is based on thermal optical activity measurement of temperature combined with electric-field-induced polarization modulation of the input light. Quartz is used as the sensing element. A 1/4 wave plate is placed behind the quartz so that a single sensing head can simultaneously output two signals: one includes the Pockels effect for voltage measurement; the other optical activity for the temperature measurement. The operating principle of the sensor which detects voltage and temperature is presented theoretically and experimentally. The technique for separating voltage and temperature from the signals is analyzed theoretically and experimentally. It was found that the sensitivity of the voltage sensor to temperature depends on the magnitudes of voltage applied to it. To realize temperature compensation over a full range, two key parameters must be obtained: one is the response of the voltage sensor to temperature when the applied voltage is zero; another is the response of the sensing material to temperature when a certain voltage is applied. In the absence of electrogyration the effect of voltage on the temperature sensor may be neglected. The technique was demonstrated using a fiber-optic voltage sensor with temperature compensation. The sensor offered a voltage measurement range of 0-10 kV, and a temperature stability of 0.4% within the temperature range of 20-70.