It is an important problem in signal processing, system realization and system identification to find linear discrete-time systems which are consistent with given covariance parameters. This problem is formulated as a problem of finding discrete-time positive real functions which interpolate given covariance parameters. Among various solutions to the problem, a recent remarkable one is a parameterization of all the discrete-time strictly positive real functions that interpolate the covariance parameters and have a limited McMillan degree. In this paper, we use more general input-output characteristics than covariance parameters and consider finding discrete-time positive real functions which interpolate such characteristics. The input-output characteristics are given by the coefficients of the Taylor series at some complex points in the open unit disk. Based on our previous work, we present an algorithm to generate all the discrete-time positive real functions that interpolate the input-output characteristics and have a limited McMillan degree. The algorithm is more general and simpler than the previous one, and is an important practical supplement to the previous work. Moreover, the interpolation of the general input-output characteristics can be effectively applied to the frequency-weighted model reduction. Hence, the algorithm makes a contribution to the problem from the practical viewpoint as well as the theoretical viewpoint.
We first describe fundamental results about submodular functions and submodular flows, which lay a basis for devising efficient algorithms for submodular flows. We then give a comprehensive survey on algorithms for submodular flows and show some possible future research directions.
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.
There are no efficient algorithms for almost of all scheduling problems, especially when practical scheduling models are considered. Further there may be none for multi-objective scheduling problems. So we should take efforts to develope efficient approximate algorithms for multi-objective scheduling problems. The main purpose of this paper is to survey approaches to some scheduling problems from the algorithmic view points till now and investigate some hopeful approximate approaches to multiobjective scheduling problems.
Seon-Ho LEE Ji-Myong NHO Jong-Tae LIM
This letter proposes a congestion control scheme for the ABR service of ATM networks which have non-responding connections. The control scheme is robust with respect to both the round trip delay and the loss of control information caused by non-responding connections. Thus, it is shown that the proposed control scheme guarantees the QoS of the network.
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.
We review public-key cryptosystems from lattice problems, which are inspired by Ajtai's remarkable result, and consider their security from the point of view of both theory and practice. We also survey recent results on the power of the lattice reduction algorithm in cryptanalysis.
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.
Makiko ITOH Yoshinori TAKEUCHI Masaharu IMAI Akichika SHIOMI
A synthesizable HDL generation method for pipelined processors is proposed. By using the proposed method, data-path and control logic descriptions of a target processor is generated from a clock based instruction set specification. From the experimental results, feasibility of the proposed method is evaluated and the amount of processor design time was drastically reduced than that of conventional RT level manual design in HDL.
Recently, digital contents are copied easily because of the development of digital technology. So digital watermark technique which aims at copyright protection of digital contents becomes more and more important, and various watermarking methods have been proposed. In this paper, we proposed a method of digital watermark for still image by using wavelet packets, and examine the robustness of the watermarking method against several image processings. This method can be easily applied to the watermark for video because in this method, embedded data are detected without original image. Therefore, we extend the wavelet-based watermarking method to the case of watermark for video.
Yifei HE Brian W. SHELDON Theodore F. MORSE
A novel technique has been developed for in situ sensing of thin film growth. In this method, a fiber optic probe is placed at an appropriate position in a deposition chamber, and the thin film builds up on the end of the fiber. This film is either the same as on the wafer where deposition occurs, or it bears a fixed relationship to the film on the wafer. By an analysis of the intensity of the light reflected from the film and guided by the fiber, information on the film may be obtained. With interference causing maxima, minima and a point of inflection as the film grows, it is possible to obtain near real time information on the following quantities: the real and imaginary parts of the refractive index of the film, a Gaussian parameter characterizing surface roughness, and the film thickness itself. To demonstrate this technique, we have studied the deposition of silicon nitride films in a CVD reactor and how reactor temperature and reactant flow rates influence film growth. This technique may be applied to measure in situ reflectivity of multi layer films, so that reflectance as a function of temperature and time may be obtained. Because the measurement is simple and direct and the information is optical, we believe that this technique has the potential to supplant quartz oscillators in the measurement of thin film growth.
Lev GOLDFELD Vladimir LYANDRES
Closed-loop power control providing maximum capacity of the multicarrier channel with frequency selective Nakagami fading is investigated. Use of the famous Gallager channel capacity (water-filling) theorem with the assumption of limited transmitter power and independent fading in partial channels leads to the algorithm for their optimal power loading. Analytical expressions for the capacity of the multicarrier channel as a function of the number of its subchannels and the fading parameters are derived for the cases of Optimal Power Distribution (OPD) and Equal Power Distribution (EPD). The dependence of the capacity gain on the OPD system order, the fading depth and the average SNR due the optimal power control is obtained. Comparison of the power efficiencies of the systems with OPD and EPD is presented.
The connectivity augmentation problem asks to add to a given graph the smallest number of new edges so that the edge- (or vertex-) connectivity of the graph increases up to a specified value k. The problem has been extensively studied, and several efficient algorithm have been discovered. We survey the recent development of the algorithms for this problem. In particular, we show how the minimum cut algorithm due to Nagamochi and Ibaraki is effectively applied to solve the edge-connectivity augmentation problem.
The features of the method of moment (MoM) and the finite difference time domain (FDTD) method for numerical analysis of the electromagnetic scattering problem are presented. First, the integral equations for the conducting wire, conducting plane and the dielectric materials are described. Importance to ensure the condition of the continuity of the current of the scatterers is emphasized and numerical examples for a conducting structure involving a junction of wire segment and planar segment is presented. Finally, the advantages and the disadvantages of the FDTD method are discussed.
Kazuhiro WATANABE Kaori TAJIMA Yuzuru KUBOTA
Macrobending characteristics of a newly developed hetero-core splicing sensor is investigated from the viewpoint of the practical use intended both for relatively large distortion monitoring and for liquid adhesion detection. The hetero-core sensor can be simply fabricated by fusion splicing of a hetero-core fiber portion as short as approximately 5 mm in length, which is inserted in a typical low-transmission-loss single mode fiber with a 9-µm core diameter for the wavelength of 1.3 µm as a fiber network line. Two types of the sensor are typically realized in terms of the core diameters of 3 and 5 µm for the inserted hetero-core portion which are referred to as 9-3-9 and 9-5-9 types, respectively , with showing their distinct bending loss characteristics. This paper deals with the explorative applications of the two types of hetero-core sensors in which a bending-to-linear displacement converter and a liquid adhesion sensor are successfully examined using a 9-5-9 structure with its low insertion loss and a cladding interactive 9-3-9 structure with its high sensitivity, respectively. The low-insertion loss 9-5-9 sensor has shown the capability of monitoring millimeters-order distortion in low transmission loss fiber networks. On the other hand, the 9-3-9 type has found to be a prospective sensor for liquid adhesion detection. Operational mechanisms for these two sensors are also discussed in terms both of optical leaks occurring at the hetero-core interfaces and of the build-up of cladding modes which might interrogate the outer cladding boundary conditions of the hetero-core sensor.
Masanori ISHII Takashi IWASAKI
In this paper, a method for finding the direction of arrival (DOA) of a single short pulse is proposed. The method is based on a waveform reconstruction technique using complex antenna factors (CAF). Since the frequency characteristics of CAF has angle dependency, the DOA of an electromagnetic pulse can be determined by the waveforms reconstructed with CAF. The results of a simulation and an experiment show the possibility to apply the two-dimensional DOA finding.
Radu G. CUCU Adrian Gh. PODOLEANU David A. JACKSON
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.
Kohji SASABE Kazuhisa YOSHIDA Osamu FUJIWARA
A simple method for diagnosing noise immunity of printed circuit boards (PCBs) by the bulk current injection (BCI) test was proposed, which can contribute to the PCB trace designs for common-mode noise. A grading index, which is defined as the ratio of the stray capacitances with and without critical IC of malfunction, was introduced to distinguish the PCB susceptible to the common-mode noise. This proposed method was validated experimentally using four PCBs with the same circuit but different trace design. It was observed that the noise immunity of PCBs had a good correlation with the values of these grading indices.
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.
We sketch two algorithms that solve the undirected st-connectivity problem in a small amount of space. One is due to Nisan, Szemeredy and Wigderson, and takes space O(log3/2n), where n denotes the number of nodes in a give undirected graph. This is the first algorithm that overcame the Savitch barrier on the space complexity of the problem. The other is due to Tarui and this author, and takes space O(sw(G)2 log2 n), where sw(G) denotes the separation-width of a given graph G. Their result implies that the st-connectivity problem can be solved in logarithmic space for any class of graphs with separation-width bounded above by a predetermined constant. This class is one of few nontrivial classes for which the st-connectivity problem can be solved in logarithmic space.