This paper deals with the random number generation problem under the framework of a separate coding system for correlated memoryless sources posed and investigated by Slepian and Wolf. Two correlated data sequences with length n are separately encoded to nR1, nR2 bit messages at each location and those are sent to the information processing center where the encoder wish to generate an approximation of the sequence of independent uniformly distributed random variables with length nR3 from two received random messages. The admissible rate region is defined by the set of all the triples (R1,R2,R3) for which the approximation error goes to zero as n tends to infinity. In this paper we examine the asymptotic behavior of the approximation error inside and outside the admissible rate region. We derive an explicit lower bound of the optimal exponent for the approximation error to vanish and show that it can be attained by the universal codes. Furthermore, we derive an explicit lower bound of the optimal exponent for the approximation error to tend to 2 as n goes to infinity outside the admissible rate region.
Yukinobu MAKIHARA Masayuki IKEBE Eiichi SANO
For a digitally controlled phase-locked loop (PLL), we evaluate the use of a clock-period comparator (CPC). In this PLL, only the frequency lock operation should be performed; however, the phase lock operation is also simultaneously achieved by performing the clock-period comparison when the phases of the reference signal and the output signal approach each other. Theoretically a lock-up operation was conducted. In addition, we succeeded in digitizing a voltage controlled oscillator (VCO) with a linear characteristic. We confirmed a phase lock operation with a slight loop characteristic through SPICE simulation.
Md. Anwarul ABEDIN Yuki TANAKA Ali AHMADI Shogo SAKAKIBARA Tetsushi KOIDE Hans Jurgen MATTAUSCH
The realization of k-nearest-matches search capability in fully-parallel mixed digital-analog associative memories by a sequential autonomous search mode is reported. The proposed concept and circuit implementation can be applied with all types of distance measures such as Hamming, Manhattan or Euclidean distance search, and the k value can be freely selected during operation. A test chip for concept verification has been designed in 0.35 µm CMOS technology with two-poly, three-metal layers, realizes k-nearest-matches Euclidean distance search and consumes 5.12 mm2 of the chip area for 64 reference patterns each with 16 units of 5-bit.
Hui CAO Noboru OHNISHI Yoshinori TAKEUCHI Tetsuya MATSUMOTO Hiroaki KUDO
The extened Kalman filter (EKF) and unscented Kalman filter (UKF) have been successively applied in particle filter framework to generate proposal distributions, and shown significantly improving performance of the generic particle filter that uses transition prior, i.e., the system state transition prior distribution, as the proposal distribution. In this paper we propose to use the Gauss-Newton EKF/UKF to replace EKF/UKF for generating proposal distribution in a particle filter. The Gauss-Newton EKF/UKF that uses iterated measurement update can approximate the optimal proposal distribution more closer than EKF/UKF, especially in the case of significant nonlinearity in the measurement function. As a result, the Gauss-Newton EKF/UKF is able to generate and propagate the proposal distribution for each particle much better than EKF/UKF, thus further improving the performance of state estimation. Simulation results for a nonlinear/non-Gaussian time-series demonstrate the superior estimation accuracy of our method compared with state-of-the-art filters.
Yuki ISHIKAWA Toshimichi SAITO
This paper studies nonlinear dynamics of a simplified model of multiple-input parallel buck converters. The dynamic winner-take-all switching is used to achieve N-phase synchronization automatically, however, as parameters vary, the synchronization bifurcates to a variety of periodic/chaotic phenomena. In order to analyze system dynamics we adopt a simple piecewise constant modeling, extract essential parameters in a dimensionless circuit equation and derive a hybrid return map. We then investigate typical bifurcation phenomena relating to N-phase synchronization, hyperchaos, complicated superstable behavior and so on. Ripple characteristics are also investigated.
Miodrag J. MIHALJEVI Marc P.C. FOSSORIER Hideki IMAI
This letter yields a security evaluation of certain broadcast encryption (BE) schemes regarding the generic vulnerability of the textbook BE schemes. The considered vulnerability can be effectively explored assuming known plaintext attacks which in a realistic scenario, corresponding to a legitimate user being the attacker, appears as a ciphertext only attack. Employing the birthday paradox, a dedicated time-data trade-off based algorithm for cryptanalysis is proposed. The developed algorithm is applied to cryptanalysis of particular recently reported class of BE schemes, implying additional insights regarding motivations for their security improvements.
A de-embedding technique for the measurement of very small parasitic capacitances of package or small module interconnects is presented. At high frequencies small parasitic capacitances become important, and measurement probes can strongly affect measurement results. The present technique is based on additional measurements with only one tip of the probe touching one conductor, while the second tip is kept floating on the substrate. A necessary condition for its application is that the measured capacitance does not depend on the position of the floating probe tip. Measurements with inverted probe tip polarities are also used. In this way, the capacitances between probe tips and DUT can be estimated together with the parasitic capacitances of interest. Depending on the required accuracy, de-embedding of different orders have been introduced, which consider capacitance configurations of increasing complexity. The technique requires the solution of one or more systems of non-linear equations. In the present example the minimization of the norm of the residual of the system has been treated as a least squares problem, and has been solved numerically with MATLAB. The accuracy of the measurement can be also approximately estimated with the residual. As application example, a small module with power and ground planes has been considered. Two different probes have been used. Even though the stray capacitances of the probes are very different, the values of the extracted parasitic capacitances are in agreement with each other. The accuracy has been verified also with simulation results. To this purpose, a combination of known formulas from the literature, a 2D Finite Element Method (FEM) tool and a 3D Boundary Element Method (BEM) tool have been used. A high accuracy can be obtained, even when a strong capacitive coupling between probe ground and DUT is present. The technique can be applied also when only a subset of measurement results are available.
Sang Wook PARK Fengchao XIAO Dong Chul PARK Yoshio KAMI
We propose a method of crosstalk analysis for two bent transmission lines with vias at both ends on a PCB using a circuit-concept approach in the quasi-static condition. In this condition, the electromagnetic fields can be approximately estimated by the quasi-static terms of the accurate Green's function in an inhomogeneous medium. Thus we obtain a circuit model in an ABCD matrix by taking account of the fields generated by a longitudinal line and a vertical via on a PCB. To verify the proposed approach, we conducted some experiments and compared our approach's results with measured results and a commercial electromagnetic solver's results.
Avishek ADHIKARI Mausumi BOSE Dewesh KUMAR Bimal ROY
The aim of our paper is to show how Partially Balanced Incomplete Block Designs (PBIBD) may be used to construct (2,n) visual cryptographic schemes for black and white images with small pixel expansion. In situations where uniformity of the participants with respect to the relative contrast is not important, our schemes work well since by allowing the relative contrast to vary depending on which two participants are recovering the image, they can keep the pixel expansion quite small. Thus our schemes have considerably smaller pixel expansion than many of the existing schemes. For some n and some pairs of participants recovering the image, our schemes have larger relative contrast than some existing schemes.
Erik DAHMEN Katsuyuki OKEYA Tsuyoshi TAKAGI
The most time consuming operation to verify a signature with the Elliptic Curve Digital Signature Algorithm is a multi-scalar multiplication with two scalars. Efficient methods for its computation are the Shamir method and the Interleave method, whereas the performance of those methods can be improved by using general base-2 representations of the scalars. In exchange for the speed-up, those representations require the precomputation of several points that must be stored. In the case of two precomputed points, the Interleave method and the Shamir method provide the same, optimal efficiency. In the case of more precomputed points, only the Interleave method can be sped-up in an optimal way and is currently more efficient than the Shamir method. This paper proposes a new general base-2 representation of the scalars that can be used to speed up the Shamir method. It requires the precomputation of ten points and is more efficient than any other representation that also requires ten precomputed points. Therefore, the proposed method is the first to improve the Shamir method such that it is faster than the Interleave method.
Keuntae PARK Jaesub KIM Yongjin CHOI Daeyeon PARK
Transmission schemes that gain content from multiple servers concurrently have been highlighted due to their ability to provide bandwidth aggregation, stability on dynamic server departure, and load balancing. Previous approaches employ parallel downloading in the transport layer to minimize the receiver buffer size and maximize bandwidth utilization. However, they only focus on the receiver operations and induce considerable overhead at the senders in contradiction to the main goal of a multi-provider environment, offloading popular servers through replication. In the present work, the authors propose MTCP, a novel transport layer protocol that focuses on reduction of the sender overhead through the elimination of unnecessary disk I/Os and efficient buffer cache utilization. MTCP also balances trade-off objectives to minimize buffering at receivers and maximize the request locality at senders.
This paper describes a novel parameter generation algorithm for an HMM-based speech synthesis technique. The conventional algorithm generates a parameter trajectory of static features that maximizes the likelihood of a given HMM for the parameter sequence consisting of the static and dynamic features under an explicit constraint between those two features. The generated trajectory is often excessively smoothed due to the statistical processing. Using the over-smoothed speech parameters usually causes muffled sounds. In order to alleviate the over-smoothing effect, we propose a generation algorithm considering not only the HMM likelihood maximized in the conventional algorithm but also a likelihood for a global variance (GV) of the generated trajectory. The latter likelihood works as a penalty for the over-smoothing, i.e., a reduction of the GV of the generated trajectory. The result of a perceptual evaluation demonstrates that the proposed algorithm causes considerably large improvements in the naturalness of synthetic speech.
Yuki MATSUO Xiao ZHOU Takao NISHIZEKI
A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring for given L. In this paper, we give a sufficient condition for a series-parallel graph to have a list total coloring, and we present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G and L satisfy the sufficient condition.
We propose constant-round protocols for interval tests, equality tests, and comparisons where shared secret inputs are not given bitwise. In [9]. Damgård et al. presented a novel protocol called the bit-decomposition, which can convert a polynomial sharing of an element in prime field Zp into sharings of bits. Though, by using the bit-decomposition protocol, those protocols can be constructed with constant round complexities theoretically, it involves expensive computation, leading to relatively high round and communication complexities. In this paper, we construct more efficient protocols for those protocols without relying on the bit-decomposition protocol. In the interval test protocol, checking whether a shared secret exists in the known interval is reduced to checking whether a bitwise-shared random secret exists in the appropriate interval. In the comparison protocol, comparing two shared secrets is reduced to comparing the two secrets viaindirectly where p is an odd prime for an underlying linear secret sharing scheme. In the equality test protocol, checking whether two shared secrets are equal is reduced to checking whether the difference of the two secrets is zero and furthermore checking whether the difference is a zero is reduced to checking quadratice residuosity of a random secret in a probabilistic way.
For an integer d > 0, a d-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into d sets of non-nested edges with respect to the vertex ordering. Recently V. Dujmovi
This paper presents a method for lossy compression of digital video data by parametric line and Natural cubic spline approximation. The method estimates the variation of pixel values in the temporal dimension by taking group of pixels together as keyblocks and interpolating them in Euclidean space. Break and fit criterion is used to minimize the number of keyblocks required for encoding and decoding of approximated data. Each group of pixels at fixed spatial location is encoded/decoded independently. The proposed method can easily be incorporated in the existing video data compression techniques based on Discrete Cosine Transform or Wavelet Transform.
Katsuhisa YAMANAKA Shin-ichiro KAWANO Yosuke KIKUCHI Shin-ichi NAKANO
In this paper we give a simple algorithm to generate all partitions of a positive integer n. The problem is one of the basic problems in combinatorics, and has been extensively studied for a long time. Our algorithm generates each partition of a given integer in constant time for each without repetition, while best known algorithm generates each partition in constant time on "average." Also, we propose some algorithms to generate all partitions of an integer with some additional property in constant time.
Masato INAGI Yasuhiro TAKASHIMA Yuichi NAKAMURA Yoji KAJITANI
Lately, time-multiplexed I/Os for multi-device implementations (e.g., multi-FPGA systems), have come into practical use. They realize multiple I/O signal transmissions between two devices in one system clock cycle using one I/O wire between the devices and multiple I/O clock cycles. Though they ease the limitation of the number of I/O-pins of each device, the system clock period becomes much longer approximately in proprotion to the maximum number of multiplexed I/Os on a signal path. There is no conventional partitioning algorithm considering the effect of time-multiplexed I/Os directly. We introduce a new cost function for evaluating the suitability of a bipartition for multi-device implementations with time-multiplexed I/Os. We propose a performance-driven bipartitioning method VIOP which minimizes the value of the cost function. Our method VIOP combines three algorithms, such that i) min-cut partitioning, ii) coarse performance-driven partitioning, iii) fine performance-driven partitioning. For min-cut partitioning and coarse performance-driven partitioning, we employ a well-known conventional bipartitioning algorithms CLIP-FM and DUBA, respectively. For fine performance-driven partitioning for the final improvement of a partition, we propose a partitioning algorithm CAVP. By our method VIOP, the average cost was improved by 10.4% compared with the well-known algorithms.
A new block coded modulation scheme with inter-level memory is proposed. The proposed code construction is based on the use of single parity check codes to concatenate a set of coded blocks. Simulation results show that the proposed scheme can achieve considerable coding gains while the decoding complexity is not too large.
A precoding scheme is described for multiple-input and multiple-output orthogonal frequency-division multiplexing systems with a QR-decomposition maximum likelihood detector (MLD) incorporated with a parallel interference canceller (PIC) at a receiver. Transmit antenna ranking based on received substream signal power or per-substream minimum Euclidean distances is fed back to a transmitter. Based on the ranking information, precoding matrices are determined as permutation matrices such that specific packets are transmitted from transmit antennas with higher channel quality over the whole subcarriers. The simulation results demonstrated that precoding effectively utilizes PIC by reducing the possibility that all substreams are incorrectly decoded and thus improves the transmission performance of a QR-decomposition MLD with PIC.