Recently some attempts have been made in the literature to give simple proofs of Jury test for real polynomials. This letter presents a similar result for complex polynomials. A simple proof of Jury test for complex polynomials is provided based on the Rouche's Theorem and a single-parameter characterization of Schur stability property for complex polynomials.
An inverter is a circuit which outputs ¬ x1, ¬ x2, ..., ¬ xn for any Boolean inputs x1, x2, ..., xn. We consider constructing an inverter with AND gates and OR gates and a few NOT gates. Beals, Nishino and Tanaka have given a construction of an inverter which has size O(nlog n) and depth O(log n) and uses ⌈ log (n+1) ⌉ NOT gates. In this paper we give a construction of an inverter which has size O(n) and depth log 1+o(1)n and uses log 1+o(1)n NOT gates. This is the first negation-limited inverter of linear size using only o(n) NOT gates. We also discuss implications of our construction for negation-limited circuit complexity.
Osamu SHIMADA Akihiko SUGIYAMA Toshiyuki NOMURA
This paper proposes a low complexity noise suppressor with hybrid filterbanks and adaptive time-frequency tiling. An analysis hybrid filterbank provides efficient transformation by further decomposing low-frequency bins after a coarse transformation with a short frame size. A synthesis hybrid filterbank also reduces computational complexity in a similar fashion to the analysis hybrid filterbank. Adaptive time-frequency tiling reduces the number of spectral gain calculations. It adaptively generates tiling information in the time-frequency plane based on the signal characteristics. The average number of instructions on a typical DSP chip has been reduced by 30% to 7.5 MIPS in case of mono signals sampled at 44.1 kHz. A Subjective test result shows that the sound quality of the proposed method is comparable to that of the conventional one.
Jingwei ZHANG Chang-An ZHAO Xiao MA
In this paper, we compare two generalized cyclotomic binary sequences with length 2p2 in terms of the linear complexity. One classical sequence is defined using the method introduced by Ding and Helleseth, while the other modified sequence is defined in a slightly different manner. We show that the modified sequence has linear complexity of 2p2, which is higher than that of the classical one.
Meiling ZHANG Weiguo ZHANG Jingmei LIU Xinmei WANG
Impossible differential attack (IDA) uses impossible differential characteristics extracted from enough plaintext pairs to retrieve subkeys of the first and the last several rounds of AES. In this paper, a general IDA on 7-round AES is proposed. Such attack takes the number of all-zero columns of the 7th and the 6th round as parameters (α,β). And a trade-off relation between the number of plaintexts and times of encryptions in the process of the attack is derived, which makes only some values of (α,β) allowed in the attack for different key length.
Cong-Nguyen BUI Hae-Yeoun LEE Jeong-Chun JOO Heung-Kyu LEE
A secure method for steganography is proposed. Pixel-value differencing (PVD) steganography and bit-plane complexity segmentation (BPCS) steganography have the weakness of generating blocky effects and noise in smooth areas and being detectable with steganalysis. To overcome these weaknesses, a secure bit-plane based steganography method on the spatial domain is presented, which uses a robust measure to select noisy blocks for embedding messages. A matrix embedding technique is also applied to reduce the change of cover images. Given that the statistical property of cover images is well preserved in stego-images, the proposed method is undetectable by steganalysis that uses RS analysis or histogram-based analysis. The proposed method is compared with the PVD and BPCS steganography methods. Experimental results confirm that the proposed method is secure against potential attacks.
A performance of the complex chaotic spreading sequences with constant power is investigated in a chip-synchronous complex CDMA with a complex scrambling. We estimate a signal-to-interference ratio (SIR) and a bit error rate (BER). An exact invariant measure of the complex chaotic spreading sequence can be obtained. Therefore, the SIR can be calculated analytically. The result can be used as one of the criteria for evaluating the performance of the complex CDMA using the chaotic spreading sequences.
Thi Huong TRAN Yuanfeng SHE Jiro HIROKAWA Kimio SAKURAI Yoshinori KOGAMI Makoto ANDO
This paper presents a measurement method for determining effective conductivity of copper-clad dielectric laminate substrates in the millimeter-wave region. The conductivity is indirectly evaluated from measured resonant frequencies and unloaded Q values of a number of Whispering Gallery modes excited in a circular disk sample, which consists of a copper-clad dielectric substrate with a large diameter of 20-30 wavelengths. We can, therefore, obtain easily the frequency dependence of the effective conductivity of the sample under test in a wide range of frequency at once. Almost identical conductivity is predicted for two kinds of WG resonators (the copper-clad type and the sandwich type) with different field distribution; it is self-consistent and provides the important foundation for the method if not for the alternative method at this moment. We measure three kinds of copper foils in 55-65 GHz band, where the conductivity of electrodeposited copper foil is smaller than that of rolled copper foil and shiny-both-sides copper foil. The measured conductivity for the electrodeposited copper foil decreases with an increase in the frequency. The transmission losses measured for microstrip lines which are fabricated from these substrates are accurately predicted with the conductivity evaluated by this method.
Nasour BAGHERI Lars R. KNUDSEN Majid NADERI Sφren S. THOMSEN
Information theoretic security is an important security notion in cryptography as it provides a true lower bound for attack complexities. However, in practice attacks often have a higher cost than the information theoretic bound. In this paper we study the relationship between information theoretic attack costs and real costs. We show that in the information theoretic model, many well-known and commonly used hash functions such as MD5 and SHA-256 fail to be preimage resistant.
This paper focuses on fusion estimation algorithms weighted by matrices and scalars, and relationship between them is considered. We present new algorithms that address the computation of matrix weights arising from multidimensional estimation problems. The first algorithm is based on the Cholesky factorization of a cross-covariance block-matrix. This algorithm is equivalent to the standard composite fusion estimation algorithm however it is low-complexity. The second fusion algorithm is based on an approximation scheme which uses special steady-state approximation for local cross-covariances. Such approximation is useful for computing matrix weights in real-time. Subsequent analysis of the proposed fusion algorithms is presented, in which examples demonstrate the low-computational complexity of the new fusion estimation algorithms.
Petri net is a powerful modeling tool for concurrent systems. Liveness, which is a problem to verify there exists no local deadlock, is one of the most important properties of Petri net to analyze. Computational complexity of liveness of a general Petri net is deterministic exponential space. Liveness is studied for subclasses of Petri nets to obtain necessary and sufficient conditions that need less computational cost. These are mainly done using a subset of places called siphons. CS-property, which denotes that every siphon has token(s) in every reachable marking, in one of key properties in liveness analysis. On the other hand, normal Petri net is a subclass of Petri net whose reachability set can be effectively calculated. This paper studies computational complexity of liveness problem of normal Petri nets. First, it is shown that liveness of a normal Petri net is equivalent to cs-property. Then we show this problem is co-NP complete by deriving a nondeterministic algorithm for non-liveness which is similar to the algorithm for liveness suggested by Howell et al. Lastly, we study structural feature of bounded Petri net where liveness and cs-property are equivalent. From this consideration, liveness problem of bounded normal Petri net is shown to be deterministic polynomial time complexity.
Nariman MAHDAVI MAZDEH Mohammad Bagher MENHAJ Heidar Ali TALEBI
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.
Kouhei SUGIYAMA Hiroyuki OHSAKI Makoto IMASE
In this paper, for systematically evaluating estimation methods of node characteristics, we first propose a social network generation model called LRE (Linkage with Relative Evaluation). LRE is a network generation model, which aims to reproduce the characteristics of a social network. LRE utilizes the fact that people generally build relationships with others based on relative evaluation, rather than absolute evaluation. We then extensively evaluate the accuracy of the estimation method called SSI (Structural Superiority Index). We reveal that SSI is effective for finding good nodes (e.g., top 10% nodes), but cannot be used for finding excellent nodes (e.g., top 1% nodes). For alleviating the problems of SSI, we propose a novel scheme for enhancing existing estimation methods called RENC (Recursive Estimation of Node Characteristic). RENC reduces the effect of noise by recursively estimating node characteristics. By investigating the estimation accuracy with RENC, we show that RENC is quite effective for improving the estimation accuracy in practical situations.
Hironori UCHIKAWA Kohsuke HARADA
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.
Masato TAJIMA Koji OKINO Takashi MIYAGOSHI
In this paper, we extend the conventional error-trellis construction for convolutional codes to the case where a given check matrix H(D) has a factor Dl in some column (row). In the first case, there is a possibility that the size of the state space can be reduced using shifted error-subsequences, whereas in the second case, the size of the state space can be reduced using shifted syndrome-subsequences. The construction presented in this paper is based on the adjoint-obvious realization of the corresponding syndrome former HT(D). In the case where all the columns and rows of H(D) are delay free, the proposed construction is reduced to the conventional one of Schalkwijk et al. We also show that the proposed construction can equally realize the state-space reduction shown by Ariel et al. Moreover, we clarify the difference between their construction and that of ours using examples.
Coding complexity is a crucial parameter in rate control scheme. Traditional measures for coding complexity are based on statistic and estimation. This way may cause the imprecise coding complexity and finally bring inaccurate output bit rate more or less. To resolve this problem, we propose a hypothetical virtual coding complexity to imitate the real coding complexity. Based on the proposed coding complexity measure, a novel rate control algorithm is proposed either. Experimental results and analysis show that the proposed mearsure for coding complexity is effective, and our scheme outperforms the JVT-W042 solution by providing more accurate QP prediction, reducing frame skipping, and improving visual quality.
An equalizer initialization technique for least mean squares (LMS) algorithm, which can equalize frequency selective multiple input multiple output (MIMO) channels, is presented and analyzed. The proposed method conducts an initial convergence step for superior training prior to running the LMS algorithm. This approach raises the training performance while the complexity of the LMS algorithm, which is known as the simplest training algorithm, is almost the same. The proposed technique is analyzed for the initial convergence and simulated for a possible single carrier MIMO application in single carrier (SC) IEEE802.16-2004 standards. The obtained performance after coding approximates the performance of the recursive least squares (RLS) algorithm as it is presented for 33 and 55 MIMO for comparisons.
Cognitive radio (CR) is an adaptive spectrum sharing paradigm targeted to provide opportunistic spectrum access to secondary users for whom the frequency bands have not been licensed. The key tasks in a CR are to sense the spectral environment over a wide frequency band and allow unlicensed secondary users (CR users) to dynamically transmit/receive data over frequency bands unutilized by licensed primary users. Thus the CR transceiver should dynamically adapt its channel (frequency band) in response to the time-varying frequencies of wideband signal for seamless communication. In this paper, we present a low complexity reconfigurable filter architecture based on multi-band filtering and frequency masking techniques for dynamic channel adaptation in CR terminal. The proposed multi-standard architecture is capable of adapting to channels having different bandwidths corresponding to the channel spacing of time-varying channels. Design examples show that proposed architecture offers 12.2% power reduction and 26.5% average gate count reduction over conventional Per-Channel based architecture.
Harumichi NISHIMURA Rudy RAYMOND
Quantum random access coding (QRAC) is one of the basic tools in quantum computing. It uses a quantum state for encoding the sender's bit string so that the receiver can recover any single bit of the bit string with high probability. This article surveys recent developments of QRAC, with some concrete examples of QRAC using one quantum bit, and its applications, focusing on communication complexity and locally decodable codes.
Complex bandpass ΔΣAD modulators can provide superior performance to a pair of real bandpass ΔΣAD modulators of the same order. They process just input I and Q signals, not image signals, and AD conversion can be realized with low power dissipation, so that they are desirable for such low-IF receiver applications. This paper proposes a new architecture for complex bandpass Δ ΣAD modulators with cross-noise-coupled topology, which effectively raises the order of the complex modulator and achieves higher SQNDR (Signal to Quantization Noise and Distortion Ratio) with low power dissipation. By providing the cross-coupled quantization noise injection to internal I and Q paths, noise coupling between two quantizers can be realized in complex form, which enhances the order of noise shaping in complex domain, and provides a higher-order NTF using a lower-order loop filter in the complex ΔΣAD modulator. Proposed higher-order modulator can be realized just by adding some passive capacitors and switches, the additional integrator circuit composed of an operational amplifier is not necessary, and the performance of the complex modulator can be effectively raised without more power dissipation. We have performed simulation with MATLAB to verify the effectiveness of the proposed architecture. The simulation results show that the proposed architecture can achieve the realization of higher-order enhancement, and improve SQNDR of the complex bandpass ΔΣAD modulator.