Mohammadali KHOSRAVIFARD Dariush FOOLADIVANDA T. Aaron GULLIVER
We prove that the Variational distance (and its positive multiples) is the only f-divergence that satisfies both the identity of indiscernibles and the triangle inequality. Therefore it is the unique f-divergence which serves as a metric. This point is interpreted as a fundamental confliction of the convexity for f(x) with the metric properties for its associated f-divergence. Therefore, we relax the convexity of f(x) and replace it with other constraints to create new metrics.
Liangwei GE Song CHEN Kazutoshi WAKABAYASHI Takashi TAKENAKA Takeshi YOSHIMURA
Scheduling, an essential step in high-level synthesis, is an intractable process. Traditional heuristic scheduling methods usually search schedules directly in the entire solution space. In this paper, we propose the idea of searching within an intermediate solution space (ISS). We put forward a max-flow scheduling method that heuristically prunes the solution space into a specific ISS and finds the optimum of ISS in polynomial time. The proposed scheduling algorithm has some unique features, such as the correction of previous scheduling decisions in a later stage, the simultaneous scheduling of all the operations, and the optimization of more complicated objectives. Aided by the max-flow scheduling method, we implement the optimization of the IC power-ground integrity problem at the behavior level conveniently. Experiments on well-known benchmarks show that without requiring additional resources or prolonging schedule latency, the proposed scheduling method can find a schedule that draws current more stably from a supply, which mitigates the voltage fluctuation in the on-chip power distribution network.
Xiaoqing WEN Seiji KAJIHARA Kohei MIYASE Tatsuya SUZUKI Kewal K. SALUJA Laung-Terng WANG Kozo KINOSHITA
High power dissipation can occur when the response to a test vector is captured by flip-flops in scan testing, resulting in excessive IR drop, which may cause significant capture-induced yield loss in the DSM era. This paper addresses this serious problem with a novel test generation method, featuring a unique algorithm that deterministically generates test cubes not only for fault detection but also for capture power reduction. Compared with previous methods that passively conduct X-filling for unspecified bits in test cubes generated only for fault detection, the new method achieves more capture power reduction with less test set inflation. Experimental results show its effectiveness.
Hongkui SHI Mengtian RONG Ping LI
Due to the discontinuity of packet based traffic, the user terminals in next generation mobile telecommunications systems will be equipped with sleep mode operation functions for power saving purpose. The sleep mode parameters should be appropriately configured so that power consumption can be sufficiently decreased while packet queue length and packet delay are restricted within a demanded level. This paper proposes an adaptive sleep mode parameter configuration scheme which is able to jointly optimize the inactivity timer and sleep period in response to the variation of user traffic arrival pattern. The optimization target of this scheme is to minimize mobile terminal power consumption while ensuring that the mean downlink packet queue length do not exceed a certain threshold. Results of computer simulations prove that, the presented approach perfectly manages packet queue length restriction, packet delay control and power saving in a wide range of user packet inter-arrival rates both in single- and dual-service scenarios.
Tadashi TSUBONE Noriyoshi KAMBAYASHI
In this paper, we consider a simple nonlinear system which consists of a chaotic system and multirate sample-hold controllers. The proposed system exhibits some stabilized Unstable Periodic Orbits which are embedded on the chaos attractor of the original chaotic system. We provide a condition to stabilize Unstable Periodic Orbits and its domain of attraction. Some theoretical results are verified in the experimental circuit.
Hongkui SHI Mengtian RONG Ping LI
Based on the mutuality between arrival moments of uplink and downlink messages, this paper proposes a scheme that assigns different time-out thresholds for mobile terminal sleep mode operation according to the direction of the message just processed. Simulation results prove that, this approach can increase the power saving factor of a mobile terminal without degrading QoS.
Kazumi KUMAZOE Masato TSURU Yuji OIE
The performance of a real-time networked application can be drastically affected by delays in packets traversing the network. Some real-time applications impose limits for acceptable network delay, and so a packet which is delayed longer than the limit before arriving at its destination is worthless to the flow to which the packet belongs. Not only that, but the rejected packet is also damaging to the quality of other flows in the network, because it may increase the queuing delay for other packets. Therefore, this paper proposes an adaptive scheme using two mechanisms, in which packets experiencing too great a delay are discarded at intermediate nodes based on the delay limit for the application and the delay experienced by each packet. This earlier discarding of packets is expected to improve the overall delay performance of real-time flows competing for network resources when the network is congested. An extensive simulation is conducted, and the results show that the scheme has great potential in improving the delay performance of real-time traffic in both homogeneous and heterogeneous environments in terms of traffic volume and application delay requirements.
Somboon THEERAWISITPONG Toshitatsu SUZUKI Tadahiro NEGISHI Yasuo WATANABE
Near-field imaging has been intensively investigated to observe the shape and the physical properties of objects, aiming at wide applications in the areas of science and engineering. In this research, by using 60 GHz band waveguide-type microscopic aperture probe, the characteristics of the near-field imaging in transmission mode have been studied by simulation and experiment. The probe is made of a WR-15 rectangular waveguide with end-shielded metal plate and a 0.5 mm-diameter aperture. In the simulation, at first, the electric field distribution at the aperture, at the rear (waveguide) and the front positions (free space) are presented. Second, the transmitted electric fields are presented for three cases: (a) scanning of a dielectric slit, (b) by varying the distance between the aperture and a dielectric sample, and (c) scanning of a dielectric groove. In the experiment, the lateral resolution with a two-slit and the depth resolution with grooves having various depths in rectangular format are described and the results show both resolutions to be much shorter than the wavelength. Finally, the scanned images of the letter N punched through a dielectric material and a leaf are demonstrated.
Minoru NAGATA Hideaki MASUOKA Shin-ichi FUKASE Makoto KIKUTA Makoto MORITA Nobuyuki ITOH
A fully integrated 5.8 GHz ETC transceiver LSI has been developed. The transceiver consists of LNA, down-conversion MIX, ASK detector, ASK modulator, DA VCO, and ΔΣ-fractional-N PLL. The features of the transceiver are integrated matching circuitry for LNA input and for DA output, ASK modulator with VGA for local signal control to avoid local leakage and to keep suitable modulation index, and LO circuitry consisting of ΔΣ-fractional-N PLL and interference-robust ∞-shape inductor VCO to diminish magnetic coupling from any other circuitry. Use of these techniques enabled realization of the input and output VSWR of less than 1.25, modulation index of over 95%, and enough qualified TX signals. This transceiver was manufactured by 1P3M SiGe-BiCMOS process with 47 GHz cut-off frequency.
There are three well-known identification schemes: the Fiat-Shamir, GQ and Schnorr identification schemes. All of them are proven secure against the passive or active attacks under some number-theoretic assumptions. However, efficiencies of the reductions in those proofs of security are not tight, because they require "rewinding" a cheating prover. We show an identification scheme IDKEA1, which is an enhanced version of the Schnorr scheme. Although it needs the four exchanges of messages and slightly more exponentiations, the IDKEA1 is proved to be secure under the KEA1 and DLA assumptions with tight reduction. The idea underlying the IDKEA1 is to use an extractable commitment for prover's commitment. In the proof of security, the simulator can open the commitment in two different ways: one by the non-black-box extractor of the KEA1 assumption and the other through the simulated transcript. This means that we don't need to rewind a cheating prover and can prove the security without loss of the efficiency of reduction.
Self-Clocked Fair Queueing (SCFQ) and Credit-Based Fair Queueing (CBFQ) are well-known fair scheduling schemes for packet-switched network. In this paper, it is shown that SCFQ and CBFQ are equivalent in selecting packets to transmit. For this, we modified the per-packet service tag based SCFQ algorithm to an equivalent per-session service tag based algorithm, SCFQ+, and showed that the service tags for SCFQ+ and CBFQ evolve identically.
We present a parallel multilevel fast multipole algorithm aimed at low cost parallel computers such as GRID computer environments and clusters of workstations. The algorithm is a scheduling algorithm where work packets are handled in a certain order to ensure minimal idle time of the processors and to avoid simultaneous bursts of communication between the processors. The algorithm is implemented on a method of moment discretization of a two-dimensional TM electromagnetic scattering problem. Examples of several optical devices with a size up to 28 500 wavelengths are presented.
Hotaka TAKIZAWA Shinji YAMAMOTO Tsuyoshi SHIINA
This paper describes a novel discrimination method of pulmonary nodules based on statistical analysis of thoracic computed tomography (CT) scans. Our previous Computer-Aided Diagnosis (CAD) system can detect pulmonary nodules from CT scans, but, at the same time, yields many false positives. In order to reduce the false positives, the method proposed in the present paper uses a relationship between pulmonary nodules, false positives and image features in CT scans. The trend of variation of the relationships is acquired through statistical analysis of a set of CT scans prepared for training. In testing, by use of the trend, the method predicts the appearances of pulmonary nodules and false positives in a CT scan, and improves the accuracy of the previous CAD system by modifying the system's output based on the prediction. The method is applied to 218 actual thoracic CT scans with 386 actual pulmonary nodules. The receiver operating characteristic (ROC) analysis is used to evaluate the results. The area under the ROC curve (Az) is statistically significantly improved from 0.918 to 0.931.
Shinichiro OMACHI Masako OMACHI Hirotomo ASO
In statistical pattern recognition, it is important to estimate the distribution of patterns precisely to achieve high recognition accuracy. In general, precise estimation of the parameters of the distribution requires a great number of sample patterns, especially when the feature vector obtained from the pattern is high-dimensional. For some pattern recognition problems, such as face recognition or character recognition, very high-dimensional feature vectors are necessary and there are always not enough sample patterns for estimating the parameters. In this paper, we focus on estimating the distribution of high-dimensional feature vectors with small number of sample patterns. First, we define a function, called simplified quadratic discriminant function (SQDF). SQDF can be estimated with small number of sample patterns and approximates the quadratic discriminant function (QDF). SQDF has fewer parameters and requires less computational time than QDF. The effectiveness of SQDF is confirmed by three types of experiments. Next, as an application of SQDF, we propose an algorithm for estimating the parameters of the normal mixture. The proposed algorithm is applied to face recognition and character recognition problems which require high-dimensional feature vectors.
Toshitaka KOJIMA Takanori KAWAI
In order to realize a higher density version of the conventional optical disk, shorter wavelength laser and narrower track pitch have been put to practical use. However, using narrow track pitch can cause the increase of the crosstalk from the adjacent tracks. Moreover, the use of narrow pitch and short wavelength can also give rise to the increase of deterioration of the detected signal characteristics due to the microscopic roughness of disk surface. In this paper, in order to estimate the effect of surface roughness theoretically, we try to analyze the light-beam scattering and detected signal characteristics of a blue laser optical disk model with random rough surfaces by the Finite Difference Time Domain (FDTD) method.
Hideyuki FURUHASHI Yoshinobu KAJIKAWA Yasuo NOMURA
In this paper, we propose a low complexity realization method for compensating for nonlinear distortion. Generally, nonlinear distortion is compensated for by a linearization system using a Volterra kernel. However, this method has a problem of requiring a huge computational complexity for the convolution needed between an input signal and the 2nd-order Volterra kernel. The Simplified Volterra Filter (SVF), which removes the lines along the main diagonal of the 2nd-order Volterra kernel, has been previously proposed as a way to reduce the computational complexity while maintaining the compensation performance for the nonlinear distortion. However, this method cannot greatly reduce the computational complexity. Hence, we propose a subband linearization system which consists of a subband parallel cascade realization method for the 2nd-order Volterra kernel and subband linear inverse filter. Experimental results show that this proposed linearization system can produce the same compensation ability as the conventional method while reducing the computational complexity.
Hyunseuk YOO Chang Hui CHOE Moon Ho LEE
The key weakness of Low-Density Parity Check codes is the complexity of the encoding scheme. The generator matrices can be made by Gaussian elimination of parity check matrices for normal block codes. Richardson succeeded in making parity bits from parity check matrices by the low density computation. In this letter, we focus on the execution of numerical experiments which show that even if the matrix D, which is the part of the Richardson's LDPC matrix, is restricted, proposed LDPC codes is lower complexity than Richardson's LDPC codes. The constraint of D results in reducing complexity from O(n + g2) to O(n) due to the omission of computing inverse matrices of φ and T in Richardson's encoding scheme. All the sub-matrices in parity check matrix are composed of Circulant Permutation Matrices based on Galois Fields.
An explicit expression for the impulse response coefficients of the predictive FIR digital filters is derived. The formula specifies a four-parameter family of smoothing FIR digital filters containing the Savitsky-Goaly filters, the Heinonen-Neuvo polynomial predictors, and the smoothing differentiators of arbitrary integer orders. The Hahn polynomials, which are orthogonal with respect to a discrete variable, are the main tool employed in the derivation of the formula. A recursive formula for the computation of the transfer function of the filters, which is the z-transform of a terminated sequence of polynomial ordinates, is also introduced. The formula can be used to design structures with low computational complexity for filters of any order.
Min-Cheol HWANG Seung-Kyun KIM Sung-Jea KO
Existing methods for inverse motion compensation (IMC) in the DCT domain have not considered the unrestricted motion vector (UMV). In the existing methods, IMC is performed to deal with the UMV in the spatial domain after the inverse DCT (IDCT). We propose an IMC method which can deal with the UMV directly in the DCT domain without the use of the IDCT/DCT required by the existing methods. The computational complexity of the proposed method can be reduced by about half of that of the brute-force method operating in the spatial domain. Experimental results show that the proposed method can efficiently reduce the processing time with similar visual quality.
Sang-Min KWAK Jae-Gon KIM Jong-Ki HAN
When the bit rate of a compressed video sequence is reduced by a frequency domain transcoder system, the rate control scheme plays a very important role in maintaining consistent video quality. In this paper, we propose an efficient rate control scheme based on the complexity of MB (Macro Block) while conventional transcoding schemes use that of a picture. Since the frequency domain transcoder has to calculate the spatial activity of MB to adjust the quantization step, a process of converting the DCT (Discrete Cosine Transform) data into spatial one is required. The proposed scheme calculates the spatial activity from DCT data without converting them to pixel domain.