This paper clarifies the adequacy of the linear channel coding approach for Slepian-Wolf coding of individual sequences. A sufficient condition for ensembles of linear codes from which a universal Slepian-Wolf code can be constructed is given. Our result reveals that an ensemble of LDPC codes gives a universal code for Slepian-Wolf coding of individual sequences.

View full abstract

We propose an iterative channel decoding scheme for two or more multiple correlated sources. The correlated sources are separately turbo encoded without knowledge of the correlation and transmitted over noisy channels. The proposed decoder exploits the correlation of the multiple sources in an iterative soft decision decoding manner for joint detection of each of the transmitted data. Simulation results show that achieved performance for the more than two sources is also close to the Shannon and Slepian-Wolf limit and large additional SNR gain is obtained in comparison with the case of two sources. We also verify through simulation that no significant penalty results from the estimation of the source correlation in the decoding process and the code with a low error floor achieves good performance for a large number of the correlated sources.

View full abstract

We propose a complexity-reducing algorithm for serial scheduled min-sum decoding that reduces the number of check nodes to process during an iteration. The check nodes to skip are chosen based on the reliability, a syndrome and a log-likelihood-ratio (LLR) value, of the incoming messages. The proposed algorithm is evaluated by computer simulations and shown to reduce the decoding complexity about 20% compared with a conventional serial scheduled min-sum decoding with small fractional decibel degradation in error correction performance.

View full abstract

Two decoding procedures combined with a belief-propagation (BP) decoding algorithm for low-density parity-check codes over the binary erasure channel are presented. These algorithms continue a decoding procedure after the BP decoding algorithm terminates. We derive a condition that our decoding algorithms can correct an erased bit which is uncorrectable by the BP decoding algorithm. We show by simulation results that the performance of our decoding algorithms is enhanced compared with that of the BP decoding algorithm with little increase of the decoding complexity.

View full abstract

In 1999, Gennaro, Halevi and Rabin proposed a signature which achieves provable security without assuming the random oracles, and it is the first RSA-type signature whose security is proved in the standard model. Since that time, several signatures have been proposed to achieve better efficiency or useful property along with the provable security in the standard model. In this paper, we construct a trapdoor hash function, and design an efficient online/offline signature by using the trapdoor hash function. Our signature scheme requires only one non-modular multiplication of two small integers for online signing, and it provides the fastest online signing among all online/offline signatures that achieve provable security in the standard model.

View full abstract

Following the last proposal of the nonlinear Piece in Hand method, which has 3-layer structure, 2-layer nonlinear Piece in Hand method is proposed. Both of them aim at enhancing the security of existing and future multivariate public key cryptosystems. The new nonlinear Piece in Hand is compared with the 3-layer method and PMI+, which was proposed by Ding, et al.

View full abstract

This article discusses the provable security of pseudo-random-function (PRF) modes of an iterated hash function using a block cipher. The iterated hash function uses the Matyas-Meyer-Oseas (MMO) mode for the compression function and the Merkle-Damgård with a permutation (MDP) for the domain extension transform. It is shown that the keyed-via-IV mode and the key-prefix mode of the iterated hash function are pseudorandom functions if the underlying block cipher is a pseudorandom permutation under a related-key attack with respect to the permutation used in MDP. More precisely, the key-prefix mode also requires that E_IV(K) ⊕ K is pseudoramdom, where E is the underlying block cipher, IV is the fixed initial value of the hash function, and K is a secret key. It is also confirmed that the MMO compression function is the best choice with MDP among the block-cipher-based compression functions in the Preneel-Govaerts-Vandewalle model in terms of the provable security.

View full abstract

Several methods have been proposed for compressing the linkage data of a Web graph. Among them, the method proposed by Boldi and Vigna is known as the most efficient one. In the paper, we propose a new method to compress a Web graph. Our method is more efficient than theirs with respect to the size of the compressed data. For example, our method needs only 1.99bits per link to compress a Web graph containing 3, 216, 152 links connecting 325, 557 pages, while the method of Boldi and Vigna needs 2.84bits per link to compress the same Web graph.

View full abstract

This paper proposes a parallelized DVC framework that treats each bitplane independently to reduce the decoding time. Unfortunately, simple parallelization generates inaccurate bit probabilities because additional side information is not available for the decoding of subsequent bitplanes, which degrades encoding efficiency. Our solution is an effective estimation method that can calculate the bit probability as accurately as possible by index assignment without recourse to side information. Moreover, we improve the coding performance of Rate-Adaptive LDPC (RA-LDPC), which is used in the parallelized DVC framework. This proposal selects a fitting sparse matrix for each bitplane according to the syndrome rate estimation results at the encoder side. Simulations show that our parallelization method reduces the decoding time by up to 35[%] and achieves a bit rate reduction of about 10[%].

View full abstract

This paper proposes a novel image inpainting method based on bandelet transform. This technique is based on a multi-resolution layer to perform image restoration, and mainly utilizes the geometrical flow of the neighboring texture of the damaged regions as the basis of restoration. By performing the warp transform with geometrical flows, it transforms the textural variation into the nearing domain axis utilizing the bandelet decomposition method to decompose the non-relative textures into different bands, and then combines them with the affine search method to perform image restoration. The experimental results show that the proposed method can simplify the complexity of the repair decision method and improve the quality of HVS, and thus, repaired results to contain the image of contour of high change, and in addition, offer a texture image of high-frequency variation. These repair results can lead to state-of-the-art results.

View full abstract

We newly design time-varying low-density parity-check convolutional codes (LDPC-CCs) based on parity check polynomials of the convolutional codes with a time period of 3, and show that BER (Bit Error Rate) performance in the time-varying LDPC-CCs with a time period of 3 is better than that in the conventional time-varying LDPC-CCs with a time period of 2 in the same coding rate with the nearly equal constraint length.

View full abstract

For a cyclic code, the BCH Bound and the Hartmann-Tzeng bound are two of well-known lower bounds for its minimum distance. New bounds are proposed by N. Boston in 2001, that depend on defining set of cyclic code. In this paper, we consider the between the Boston bound and these two bounds for non-binary cyclic codes from numerical examples.

View full abstract

The notion of anonymous signatures has recently been formalized by [18], which captures an interesting property that a digital signature can sometimes hide the identity of the signer, if the message is hidden from the verifier. However, in many practical applications, e.g., an anonymous paper review system mentioned in [18], the message for anonymous authentication is actually known to the verifier. This implies that the effectiveness of previous anonymous signatures may be unjustified in these applications. In this paper, we extend the previous models, and develop a related primitive called strong anonymous signatures. For strong anonymous signatures, the identity of the signer remains secret even if the challenge message is chosen by an adversary. We then demonstrate some efficient constructions and prove their security in our model.

View full abstract

We propose the use of an invertible code in cooperative multi-hop relaying networks. The effect of the code on the probability that an information block is undelivered to the destination is analyzed at the link level with a simple network topology. Numerical results indicate that significant improvement is feasible by an incorporation of an invertible code, since an information block can be reproduced by correcting channel errors in the received blocks at a relaying node.

View full abstract

An ISI-free power roll-off pulse, the roll-off characteristic of which is tunable with one power parameter, is proposed. It is shown that the proposed pulse is advantageous in terms of the probability of error for pulse detection in the presence of a timing error among currently known good pulses, among which the raised cosine pulse, “better than” raised cosine pulse, and polynomial pulse are considered.

View full abstract

This paper presents a novel approach for robust impulsive synchronization of uncertain complex dynamical networks, each node of which possesses chaotic dynamics with different parameters perturbation and external disturbances as well as unknown but bounded network coupling effects. A new sufficient condition is proposed that guarantees the global robust synchronizing of such a network. Finally, the effectiveness of the proposed approach is evaluated by performing simulations on two illustrative examples.

View full abstract

We found a new class of stochastic resonance (SR) in a simple neural network that consists of i) photoreceptors generating nonuniform outputs for common inputs with random offsets, ii) an ensemble of noisy McCulloch-Pitts (MP) neurons each of which has random threshold values in the temporal domain, iii) local coupling connections between the photoreceptors and the MP neurons with variable receptive fields (RFs), iv) output cells, and v) local coupling connections between the MP neurons and the output cells. We calculated correlation values between the inputs and the outputs as a function of the RF size and intensities of the random components in photoreceptors and the MP neurons. We show the existence of “optimal noise intensities” of the MP neurons under the nonidentical photoreceptors and “nonzero optimal RF sizes, ” which indicated that optimal correlation values of this SR model were determined by two critical parameters; noise intensities (well-known) and RF sizes as a new parameter.

View full abstract

The single input rule modules connected fuzzy inference method (SIRMs method) by Yubazaki et al. can decrease the number of fuzzy rules drastically in comparison with the conventional fuzzy inference methods. Moreover, Seki et al. have proposed a functional-type SIRMs method which generalizes the consequent part of the SIRMs method to function. However, these SIRMs methods can not be applied to XOR (Exclusive OR). In this paper, we propose a “kernel-type SIRMs method” which uses the kernel trick to the SIRMs method, and show that this method can treat XOR. Further, a learning algorithm of the proposed SIRMs method is derived by using the steepest descent method, and compared with the one of conventional SIRMs method and kernel perceptron by applying to identification of nonlinear functions, medical diagnostic system and discriminant analysis of Iris data.

View full abstract

A method was developed for deriving the control input for a multi-dimensional discrete-time nonlinear system so that a performance index is approximately minimized. First, a moment vector equation (MVE) is derived; it is a multi-dimensional linear equation that approximates a nonlinear system in the whole domain of the system state and control input. Next, the performance index is approximated by using a quadratic form with respect to the moment vector. On the basis of the MVE and the quadratic form, an approximate optimal controller is derived by solving the linear quadratic optimal control problem. A bilinear optimal control problem and a mountain-car problem were solved using this method, and the solutions were nearly optimal.

View full abstract

In deep submicron designs, predicting gate delays with interconnect load is a noteworthy work for Static Timing Analysis (STA). The effective capacitance C_eff concept and the Thevenin model that replaces the gate with a linear resistor and a voltage source are usually used to calculate the delay of gate with interconnect load. In conventional methods, it is not considered that the charges transferred into interconnect load and C_eff in the Thevenin model are not equal. The charge difference between interconnect load and C_eff has the large influence to the accuracy of computing C_eff. In this paper, an advanced effective capacitance model is proposed to consider the above problem in the Thevenin model, where the influence of the charge difference is modeled as one part of the effective capacitance to compute the gate delay. Experimental results show a significant improvement in accuracy when the charge difference between interconnect load and C_eff is considered.

View full abstract

This paper presents the mixed time-frequency steady-state analysis method for efficient simulation of circuits whose excitation frequencies are widely separated. These circuits can be written by multitime partial differential equations. In this paper, an axis of the slow time-scale is formulated in the time domain and another axis of the fast time-scale is formulated in the frequency domain. We show that computational cost, however, is not dependent on the interval of frequencies, whereas for the harmonic balance or transient analysis, it increases as the interval of frequencies increases.

View full abstract

This paper describes the application techniques of the latency insertion method (LIM) to CMOS circuit simulations. Though the existing LIM algorithm to CMOS circuit performs fast transient analysis, CMOS circuits are not modeled accurately. As a result, they do not provide accurate simulations. We propose a more accurate LIM scheme for the CMOS inverter circuit by adopting a more accurate model of the CMOS inverter characteristics. Moreover, we present the way to expand the LIM algorithm to general CMOS circuit simulations. In order to apply LIM to the general CMOS circuits which consist of CMOS NAND and NOR, we derive the updating formulas of the explicit form of the LIM algorithm. By using the explicit form of the LIM scheme, it becomes easy to take in the characteristics of CMOS NAND and NOR into the LIM simulations. As a result, it is confirmed that our techniques are useful and efficient for the simulations of CMOS circuits.

View full abstract

Let us introduce n (≥ 2) mappings f_i(i = 1, …, n ≡ 0) defined on reflexive real Banach spaces X_i-1 and let f_i : X_i-1 → Y_i be completely continuous on bounded convex closed subsets $X_{i-1}^{(0)} \\subset X_{i-1}$. Moreover, let us introduce n set-valued mappings $F_i : X_{i-1} \\ imes Y_i \\ o {\\cal F}_c(X_i)$ (the family of all non-empty compact subsets of X_i), (i=1, …, n ≡ 0). Here, we have a fixed point theorem in weak topology on the successively recurrent system of set-valued mapping equations: x_i ∈ F_i(x_i-1, f_i(x_i-1)), (i=1, …, n ≡ 0). This theorem can be applied immediately to analysis of the availability of system of circular networks of channels undergone by uncertain fluctuations and to evaluation of the tolerability of behaviors of those systems.

View full abstract

In this paper, an image restoration method using the Wiener filter is proposed. In order to bring the theory of the Wiener filter consistent with images that have spatially varying statistics, the proposed method adopts the locally adaptive Wiener filter (AWF) based on the universal Gaussian mixture distribution model (UNI-GMM) previously proposed for denoising. Applying the UNI-GMM-AWF for deconvolution problem, the proposed method employs the stationary Wiener filter (SWF) as a pre-filter. The SWF in the discrete cosine transform domain shrinks the blur point spread function and facilitates the modeling and filtering at the proceeding AWF. The SWF and UNI-GMM are learned using a generic training image set and the proposed method is tuned toward the image set. Simulation results are presented to demonstrate the effectiveness of the proposed method.

View full abstract

This paper proposes a novel reversible image authentication method that does not memorize the parameters for extracting embedded authentication data from an image. The proposed method once distorts an image to hide data for authentication into the image, it recovers the original image from the distorted image unless tamper is applied to the image, i.e., reversible. By comparing extracted data and data generated from the restored image, this method detects image tampering and further localizes tampered regions by the unit of block. The proposed method extracts hidden data without memorization of parameters used in its algorithm. This feature makes the proposed method practical. Whereas any method memorizing parameters faces severe problems with storage and management of parameters, according to the increase in the number of memorized parameters that is caused by serving accurate tamper localization and/or by applying itself to a huge number of image collection, e.g., video sequences. Simulation results show the effectiveness of the proposed method.

View full abstract

Decision diagrams (DDs) are data structures commonly used for representation of discrete functions with large number of variables. Binary DDs (BDDs) are used for representation and manipulation with Boolean functions. Complexity of a BDD is usually measured by its size, that is defined as the number of non-terminal nodes in the BDD. Minimization of the sizes of DDs is a problem greatly considered in literature and many related algorithms (exact and heuristic) have been proposed. However, there are many functions for which BDDs when minimized are still large and can have even an exponential size in the number of variables. An approach to derive compact decision diagram representations for such functions is transformation of BDDs into Multi-valued DDs (MDDs) and Heterogeneous MDDs (HMDDs). Complexity of MDDs and HMDDs is measured by the cost which is a generalization of the notion of the size by taking into account complexity of nodes in MDDs and HMDDs. This paper presents a method for transformation of BDD into HMDD with minimal cost. The proposed method reduces the time for determination of the type of nodes in HMDDs by introducing a matrix expressing dependency (interconnections) among nodes at different levels. Comparing to other methods for conversion of BDDs into HMDDs, the method reduces the number of traverses of a BDD necessary for collecting enough information to construct an equivalent HMDD. For an experimental verification of its efficiency, the method is applied to construction of HMDDs for some benchmark functions and their arithmetic and Walsh spectra.

View full abstract

In this paper, we study low complexity transceiver for double space time transmit diversity (DSTTD) and orthogonal frequency division multiplexing (OFDM) system with antenna shuffling. Firstly, we propose a novel antenna shuffling method based on the criterion of minimizing the condition number of channel correlation matrix. The condition number is an indicator about the quality of the channel. By selecting the minimum of condition number which has better channel quality, consequently, a linear detector with respect to this new channel may achieve better performance results. A low complexity variant of the condition number calculation is also proposed, and it is shown that this criterion can be reduced to the minimum mean square error (MMSE) based criterion. Furthermore, the weighted soft decision Viterbi decoding is applied to mitigate noise enhancement inherent to zero forcing (ZF) and MMSE linear receivers and improve error rate performance. Next, we propose an algorithm to reduce the amount of feedback by exploiting the fact that the channel frequency responses across OFDM subcarriers are correlated. In the proposed algorithm, subcarriers are clustered in blocks, which are allocated the same shuffling pattern with the largest number of the shuffling patterns in the cluster. This way, the signaling overhead can be reduced in comparison with each subcarrier based feedback. Extensive simulations show that the proposed techniques for DSTTD-OFDM system outperform other existing techniques under both uncorrelated and highly spatial correlated frequency selective MIMO fading channels.

View full abstract

In this paper, an error correction scheme suitable for MC-DS-CDMA system with bi-orthogonal modulation is proposed. The input sequence of a bi-orthogonal modulator consists of n - 1 bit code selection bit sequence and 1 bit sign bit sequence. In order to apply an efficient error correction code, the following points should be considered; (1) if the code selection bits can be protected sufficiently, the sign bit error can also be reduced sufficiently, (2) since a code selection bit sequence consists of n - 1 bits, employing a symbol error correcting code is more effective for encoding code selection bits, (3) the complexity of the error correction encoder and decoder implementations should be minimum. Based on these conditions, we propose to employ Reed-Solomon (RS) code for encoding the code selection bits and no error correction code for the sign bit. Additionally, detection algorithm at the bi-orthogonal demodulator is modified for compensating degradations of the sign bit error rate performance. The performance in an Additive White Gaussian Noise (AWGN) channel is evaluated by both theoretical analysis and computer simulations. The performance evaluations by simulations on multi-path fading channels are also shown. It is shown that the proposed scheme has remarkable improvement.

View full abstract

The RFID tag system has received attention as an identification source. Each RFID tag is attached to some object. With the unique ID of the RFID tag, a user identifies the object provided with the RFID tag, and derives appropriate information about the object. One of important applications of the RFID technology is the position estimation of RFID tags. It can be very useful to acquire the location information concerning the RFID tags. It can be applied to navigation systems and positional detection systems for robots etc. In this paper, we propose a new position estimation method of RFID tags by using a probabilistic approach. In this method, mobile objects (person and robot, etc.) with RFID readers estimate the positions of RFID tags with multiple communication ranges. We show the effectiveness of the proposed method by computer simulations.

View full abstract

The multiobjective route selection problem (m-RSP) is a key research topic in the car navigation system (CNS) for ITS (Intelligent Transportation System). In this paper, we propose an interactive multistage weight-based Dijkstra genetic algorithm (mwD-GA) to solve it. The purpose of the proposed approach is to create enough Pareto-optimal routes with good distribution for the car driver depending on his/her preference. At the same time, the routes can be recalculated according to the driver's preferences by the multistage framework proposed. In the solution approach proposed, the accurate route searching ability of the Dijkstra algorithm and the exploration ability of the Genetic algorithm (GA) are effectively combined together for solving the m-RSP problems. Solutions provided by the proposed approach are compared with the current research to show the effectiveness and practicability of the solution approach proposed.

View full abstract

This letter proposes a windowing frequency domain adaptive algorithm, which reuses the filtering error to apply window function in the filter updating symmetrically. By using a proper window function to reduce the negative influence of the spectral leakage, the proposed algorithm can significantly improve the performance of the acoustic echo cancellation for speech signals.

View full abstract

This letter investigates an ADILC (Iterative Learning Control with Advanced Output Data) scheme for nonminimum phase systems using a partially known impulse response. ADILC has a simple learning structure that can be applied to both minimum phase and nonminimum phase systems. However, in the latter case, the overall control time horizon must be considered in the input update law, which makes the dimension of the matrices in the convergence condition very large. Also, this makes it difficult to find a proper learning gain matrix. In this letter, a new sufficient condition is derived from the convergence condition, which can be used to find the learning gain matrix for nonminimum phase systems if we know the first part of the impulse response up to a sufficient order. Based on this, an iterative learning control scheme is proposed using the estimation of the first part of the impulse response for nonminimum phase systems.

View full abstract

It is known that Boolean functions used in stream ciphers should have good cryptographic properties to resist fast algebraic attacks. In this paper, we study a new class of Boolean functions with good cryptographic properties: balancedness, optimum algebraic degree, optimum algebraic immunity and a high nonlinearity.

View full abstract

In PKC 2004, Choi et al. proposed an ID-based authenticated group key agreement (AGKA) protocol using bilinear pairings. Unfortunately, their protocol suffered from an impersonation attack and an insider colluding attack. In 2008, Choi et al. presented an improvement to resist insider attacks. In their modified protocol, they used an ID-based signature scheme on transcripts for binding them in a session to prevent replay of transcripts. In particular, they smartly used the batch verification technique to reduce the computational cost. In this paper, we first show that Choi et al.'s modified AGKA protocol still suffers from an insider colluding attack. Then, we prove that the batch verification of the adopted ID-based signature scheme in their modified protocol suffers from a forgery attack.

View full abstract

Recently, several ID-based key sharing schemes have been proposed, where an initiation phase generates users' secret key associated with identities under the hardness of integer factorization. In this letter, we show that, unfortunately any key sharing scheme with this initiation phase is intrinsically insecure in the sense that the collusion of some users enables them to derive master private keys and hence, generating any user's secret key.

View full abstract

To enable fine-grained delegations for proxy re-encryption systems, in AsiaCCS'09, Weng et al.'s introduced the concept of conditional proxy re-encryption (C-PRE), in which the proxy can convert a ciphertext only if a specified condition is satisfied. Weng et al. also proposed a C-PRE scheme, and claimed that their scheme is secure against chosen-ciphertext attack (CCA). In this paper, we show that their scheme is not CCA-secure under their defined security model.

View full abstract