Yoshiki KAYANO Motoshi TANAKA Hiroshi INOUE
To provide basic considerations for the realization of methods for predicting the electromagnetic (EM) radiation from a printed circuit board (PCB) with plural signal traces driven in the even-mode, the characteristics of the EM radiation resulting from two signal traces on a PCB are investigated experimentally and by numerical modeling. First, the frequency responses of common-mode (CM) current and far-electric field as electromagnetic interference (EMI) are discussed. As the two traces are moved closer to the PCB edge, CM current and far-electric field increase. The frequency responses in the two signal trace case can be identified using insights gained from the single trace case. Second, to understand the details of the increase in CM current, the distribution of the current density on the ground plane is calculated and discussed. Although crosstalk ensues, the rule for PCB design is to keep two high-speed traces on the interior of the PCB whenever possible, from the point of view of EM radiation. Finally, an empirical formula to quantify the relationship between the positions of two traces and CM current is provided and discussed by comparing four different models. Results calculated with the empirical formula and finite-difference time-domain (FDTD) modeling are in good agreement, which indicates the empirical formula may be useful for developing EMI design guidelines.
Hideyo MAMIYA Atsuko MIYAJI Hiroaki MORIMOTO
In the execution on a smart card, side channel attacks such as the simple power analysis (SPA) and the differential power analysis (DPA) have become serious threat. Side channel attacks monitor the side channel information such as power consumption and even exploit the leakage information related to power consumption to reveal bits of a secret key d although d is hidden inside a smart card. Almost public key cryptosystems including RSA, DLP-based cryptosystems, and elliptic curve cryptosystems execute an exponentiation algorithm with a secret-key exponent, and they thus suffer from both SPA and DPA. In the case of elliptic curve cryptosystems, DPA is improved to the refined power analysis (RPA), which exploits a special point with a zero value and reveals a secret key. RPA is further generalized to zero-value register attack (ZRA). Both RPA and ZRA utilize a special feature of elliptic curves that happens to have a special point or a register used in addition and doubling formulae with a zero value and that the power consumption of 0 is distinguishable from that of a non-zero element. To make the matters worse, some previous efficient countermeasures to DPA are neither resistant to RPA nor ZRA. This paper focuses on elegant countermeasures of elliptic curve exponentiations against RPA, ZRA, DPA and SPA. Our novel countermeasure is easily generalized to be more efficient algorithm with a pre-computed table.
Noriyuki TAKAHASHI Masahiro YUKAWA Isao YAMADA
In this paper, we present an efficient downlink power control scheme, for wireless networks, based on two key ideas: (i) global-local fixed-point-approximation technique (GLOFPAT) and (ii) bottleneck removal criterion (BRC). The proposed scheme copes with all scenarios including infeasible case where no power allocation can provide all multiple accessing users with target quality of service (QoS). For feasible case, the GLOFPAT efficiently computes a desired power allocation which corresponds to the allocation achieved by conventional algorithms. For infeasible case, the GLOFPAT offers valuable information to detect bottleneck users, to be removed based on the BRC, which deteriorate overall QoS. The GLOFPAT is a mathematically-sound distributed algorithm approximating desired power allocation as a unique fixed-point of an isotone mapping. The unique fixed-point of the global mapping is iteratively computed by fixed-point-approximations of multiple distributed local mappings, which can be computed in parallel by base stations respectively. For proper detection of bottleneck users, complete analysis of the GLOFPAT is presented with aid of the Tarski's fixed-point theorem. Extensive simulations demonstrate that the proposed scheme converges faster than the conventional algorithm and successfully increases the number of happy users receiving target QoS.
Masashi SUGIYAMA Keisuke SAKURAI
For obtaining a higher level of generalization capability in supervised learning, model parameters should be optimized, i.e., they should be determined in such a way that the generalization error is minimized. However, since the generalization error is inaccessible in practice, model parameters are usually determined in such a way that an estimate of the generalization error is minimized. A standard procedure for model parameter optimization is to first prepare a finite set of candidates of model parameter values, estimate the generalization error for each candidate, and then choose the best one from the candidates. If the number of candidates is increased in this procedure, the optimization quality may be improved. However, this in turn increases the computational cost. In this paper, we give methods for analytically finding the optimal model parameter value from a set of infinitely many candidates. This maximally enhances the optimization quality while the computational cost is kept reasonable.
Chi-Hui HUANG Shyh-Neng LIN Shiunn-Jang CHERN Jiun-Je JIAN
The convergence speed of the conventional adaptive LMS algorithms for time delay estimation (TDE) is highly dependent on the spectral distribution of the desired random source signals of interest, thus the performance of TDE might be degraded, dramatically. To solve this problem, in this letter, a DCT-transform domain constrained adaptive normalized-LMS filtering scheme, referred to as the adaptive constrained DCT-LMS algorithm, is devised for TDE. Computer simulation results verify that the proposed scheme can be used to achieve desired performance, for input random signals with different spectral distributions; it outperforms the unconstrained DCT-LMS and time-domain constrained adaptive LMS algorithms.
It is known that any chordal graph can be uniquely decomposed into simplicial components. Based on this fact, it is shown that for a given chordal graph, its automorphism group can be computed in O((c!n)O(1)) time, where c denotes the maximum size of simplicial components and n denotes the number of nodes. It is also shown that isomorphism of those chordal graphs can be decided within the same time bound. From the viewpoint of polynomial-time computability, our result strictly strengthens the previous ones respecting the clique number.
Ching-Lung CHR Szu-Lin SU Shao-Wei WU
Similar to algebraic decoding schemes, the (23, 12, 7) Golay code can be decoded by applying the step-by-step decoding algorithm. In this work, a modified step-by-step algorithm for decoding the Golay code is presented. Logical analysis yielded a simple rule for directly determining whether a bit in the received word is correct. The computational complexity can be reduced significantly using this scheme.
Yoshiya MIYAGAKI Mitsuru OHKURA Nobuo TAKAHASHI
A probability density distribution of the envelope of maximal-ratio combiner output in a very generally distributed fading channel is derived. The derived formula has a series expanded form consisting of positive terms of the well-known m-distribution and is practical for numerical calculation, approximation and analysis.
Yan SUN Jianming LU Takashi YAHAGI
Visual criteria for diagnosing liver diseases, such as cirrhosis, from ultrasound images can be assisted by computerized texture classification. This paper proposes a system applying a PNN (Pyramid Neural Network) for classifying the hepatic parenchymal diseases in ultrasonic B-scan texture. In this study, we propose a multifractal-dimensions method to select the patterns for the training set and the validation sets. A modified box-counting algorithm is used to calculate the dimensions of the B-scan images. FDWT (Fast Discrete Wavelet Transform) is applied for feature extraction during the preprocessing. The structure of the proposed neural network is testified by training and validation sets by cross-validation method. The performance of the proposed system and a system based on the conventional multilayer network architecture is compared. The results show that, compared with the conventional 3-layer neural network, the performance of the proposed pyramid neural network is improved by efficiently utilizing the lower layer of the neural network.
Yu-Long QIAO Zhe-Ming LU Sheng-He SUN
This letter proposes a fast k nearest neighbors search algorithm based on the wavelet transform. This technique exploits the important information of the approximation coefficients of the transform coefficient vector, from which we obtain two crucial inequalities that can be used to reject those vectors for which it is impossible to be k nearest neighbors. The computational complexity for searching for k nearest neighbors can be largely reduced. Experimental results on texture classification verify the effectiveness of our algorithm.
Sachio TERAMOTO Tetsuo ASANO Naoki KATOH Benjamin DOERR
Arranging n points as uniformly as possible is a frequently occurring problem. It is equivalent to packing n equal and non-overlapping circles in a unit square. In this paper we generalize this problem in such a way that points are inserted one by one with uniformity preserved at every instance. Our criterion for uniformity is to minimize the gap ratio (which is the maximum gap over the minimum gap) at every point insertion. We present a linear time algorithm for finding an optimal n-point sequence with the maximum gap ratio bounded by in the 1-dimensional case. We describe how hard the same problem is for a point set in the plane and propose a local search heuristics for finding a good solution.
Kazuo IWAMA Shuichi MIYAZAKI Kazuya OKAMOTO
An instance of the classical stable marriage problem requires all participants to submit a strictly ordered preference list containing all members of the opposite sex. However, considering applications in real-world, we can think of two natural relaxations, namely, incomplete preference lists and ties in the lists. Either variation leaves the problem polynomially solvable, but it is known that finding a maximum cardinality stable matching is NP-hard when both variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. A few approximation algorithms have been proposed with approximation ratio better than two, but they are only for restricted instances, such as restricting occurrence of ties and/or lengths of ties. Up to the present, there is no known approximation algorithm with ratio better than two for general inputs. In this paper, we give the first nontrivial result for approximation of factor less than two for general instances. Our algorithm achieves the ratio for an arbitrarily positive constant c, where N denotes the number of men in an input.
Tomokazu IMAMURA Kazuo IWAMA Tatsuie TSUKIJI
Chen and Kanj considered the VERTEX COVER problem for graphs with perfect matchings (VC-PM). They showed that: (i) There is a reduction from general VERTEX COVER to VC-PM, which guarantees that if one can achieve an approximation factor of less than two for VC-PM, then one can do so for general VERTEX COVER as well. (ii) There is an algorithm for VC-PM whose approximation factor is given as 1.069+0.069
Ji LI Chen HE Jie CHEN Dongjian WANG
The recognition vector of the decision-theoretic approach and that of cumulant-based classification are combined to compose a higher dimension hyperspace to get the benefits of both methods. The method proposed in this paper can cover more kinds of signals including signals with order higher than 4 in the AWGN channel even under low SNR values, i.e. those down to -5 dB. The composed vector is input into an RBF neural network to get more reasonable reference points. Eleven kinds of signals, say 2ASK, 4ASK, 8ASK, 2PSK, 4PSK, 8PSK, 2FSK 4FSK, 8FSK, 16QAM and 64QAM, are involved in the discussion.
Hak-Keun KIM Teuk-Seob SONG Yoon-Chul CHOY Soon-Bum LIM
3D virtual environment provides a limited amount of information, mainly focusing on visual information. This is the main cause of users losing the sense of direction in the environment. Many researches for developing a navigation tools that address this problem have been carried out. In this study, a navigation tool is designed by applying topic map, one of the technologies for semantic web construction, to a 3D virtual environment. Topic map constructs a semantic link map by defining the connection relation between topics. According to an experiment done to evaluate the proposed navigation tool, the tool was more helpful in finding detailed object than highly represented objects. Also, it could be seen that providing the surrounding knowledge is effective for object selection by users when that target for searching is not defined.
Hyo Jin CHOI Jinhwan JEON Taehyoun KIM Hyo-Joong SUH Chu Shik JHON
The audio delay is becoming an important factor in audio streaming over short-range wireless network. In this study, we propose an efficient two-level delay control method, called frame sequence adaptation and audio sampling frequency compensation, for achieving stable audio delay with a small variation. To prove the effectiveness of our scheme, we implemented and evaluated the scheme on a Bluetooth network. Experimental results show that our scheme can control audio delay robustly and remove phase shift problem in multi-channel stereophonic audio broadcasting as well.
Localization of a vehicle is a key component for driving assistance or autonomous navigation. In this work, we propose a visual positioning system (VPS) for vehicle or mobile robot navigation. Different from general landmark-based or model-based approaches, which rely on some predefined known landmarks or a priori information about the environment, no assumptions on the prior knowledge of the scene are made. A stereo-based vision system is built for both extracting feature correspondences and recovering 3-D information of the scene from image sequences. Relative positions of the camera motion are then estimated by registering the 3-D feature points from two consecutive image frames. Localization of the mobile platform is finally given by the reference to its initial position.
Yuu TANAKA Atsushi YAMASHITA Toru KANEKO Kenjiro T. MIURA
In this paper, we propose a new method that can remove view-disturbing noises from stereo images. One of the thorny problems in outdoor surveillance by a camera is that adherent noises such as waterdrops on the protecting glass surface lens disturb the view from the camera. Therefore, we propose a method for removing adherent noises from stereo images taken with a stereo camera system. Our method is based on the stereo measurement and utilizes disparities between stereo image pair. Positions of noises in images can be detected by comparing disparities measured from stereo images with the distance between the stereo camera system and the glass surface. True disparities of image regions hidden by noises can be estimated from the property that disparities are generally similar with those around noises. Finally, we can remove noises from images by replacing the above regions with textures of corresponding image regions obtained by the disparity referring. Experimental results show the effectiveness of the proposed method.
Charlene GOUDEMAND Francois-Xavier COUDOUX Marc GAZALET
In this letter, we study the problem of designing an efficient power and bit allocation scheme in the context of a hierarchical image transmission system based on an embedded multi-carrier modulation (EMCM) scheme over digital subscriber line. Authors describe a novel algorithm that performs power minimization under bit rate constraint and QoS requirement. It is based on the Hughes-Hartogs algorithm, and successively allocates the bits of the high, then low priority data streams. Simulations that assess the performance of the proposed algorithm are also provided and discussed; they demonstrate the interest of the proposed scheme.
Haijiang TANG Sei-ichiro KAMATA
Natural, continuous tone images have a very important property of high correlation of adjacent pixels. Images which we wish to compress are usually non-stationary and can be reasonably modeled as smooth and textured areas separated by edges. This property has been successfully exploited in LOCO-I and CALIC by applying gradient based predictive coding as a major de-correlation tool. However, they only examine the horizontal and vertical gradients, and assume the local edge can only occur in these two directions. Their over-simplified assumptions hurt the robustness of the prediction in higher complex areas. In this paper, we propose an accurate gradient selective prediction (AGSP) algorithm which is designed to perform robustly around any type of image texture. Our method measures local texture information by comparison and selection of normalized scalar representation of the gradients in four directions. An adaptive predictor is formed based on the local gradient information and immediate causal pixels. Local texture properties are also exploited in the context modeling of the prediction error. The results we obtained on a test set of several standard images are encouraging. On the average, our method achieves a compression ratio significantly better than CALIC without noticeably increasing of computational complexity.