A parameterization of perfect sequences over composition algebras over the real number field is presented. According to the proposed parameterization theorem, a perfect sequence can be represented as a sum of trigonometric functions and points on a unit sphere of the algebra. Because of the non-commutativity of the multiplication, there are two definitions of perfect sequences, but the equivalence of the definitions is easily shown using the theorem. A composition sequence of sequences is introduced. Despite the non-associativity, the proposed theorem reveals that the composition sequence from perfect sequences is perfect.
Yanling ZHI Wai-Shing LUK Yi WANG Changhao YAN Xuan ZENG
Yield-driven clock skew scheduling was previously formulated as a minimum cost-to-time ratio cycle problem, by assuming that variational path delays are in Gaussian distributions. However in today's nanometer technology, process variations show growing impacts on this assumption, as variational delays with non-Gaussian distributions have been observed on these paths. In this paper, we propose a novel yield-driven clock skew scheduling method for arbitrary distributions of critical path delays. Firstly, a general problem formulation is proposed. By integrating the cumulative distribution function (CDF) of critical path delays, the formulation is able to handle path delays with any distributions. It also generalizes the previous formulations on yield-driven clock skew scheduling and indicates their statistical interpretations. Generalized Howard algorithm is derived for finding the critical cycles of the underlying timing constraint graphs. Moreover, an effective algorithm based on minimum balancing is proposed for the overall yield improvement. Experimental results on ISCAS89 benchmarks show that, compared with two representative existing methods, our method remarkably improves the yield by 10.25% on average (up to 14.66%).
Kazuya MATSUMOTO Naohito NAKASATO Stanislav G. SEDUKHIN
This paper presents a blocked united algorithm for the all-pairs shortest paths (APSP) problem. This algorithm simultaneously computes both the shortest-path distance matrix and the shortest-path construction matrix for a graph. It is designed for a high-speed APSP solution on hybrid CPU-GPU systems. In our implementation, two most compute intensive parts of the algorithm are performed on the GPU. The first part is to solve the APSP sub-problem for a block of sub-matrices, and the other part is a matrix-matrix “multiplication” for the APSP problem. Moreover, the amount of data communication between CPU (host) memory and GPU memory is reduced by reusing blocks once sent to the GPU. When a problem size (the number of vertices in a graph) is large enough compared to a block size, our implementation of the blocked algorithm requires CPU
Permutation polynomial based interleavers over integer rings, in particular quadratic permutation polynomials have been widely studied. In this letter, higher degree permutation polynomials for interleavers are considered for interleavers and permutation polynomials superior to quadratic permutation polynomials are found for some lengths.
In this paper, we propose a method for designing genetically optimized Linguistic Models (LM) with the aid of fuzzy granulation. The fundamental idea of LM introduced by Pedrycz is followed and their design framework based on Genetic Algorithm (GA) is enhanced. A LM is designed by the use of information granulation realized via Context-based Fuzzy C-Means (CFCM) clustering. This clustering technique builds information granules represented as a fuzzy set. However, it is difficult to optimize the number of linguistic contexts, the number of clusters generated by each context, and the weighting exponent. Thus, we perform simultaneous optimization of design parameters linking information granules in the input and output spaces based on GA. Experiments on the coagulant dosing process in a water purification plant reveal that the proposed method shows better performance than the previous works and LM itself.
Juinn-Horng DENG Sheng-Yang HUANG
The single carrier block transmission (SCBT) system has become one of the most popular modulation systems because of its low peak to average power ratio (PAPR). This work proposes precoding design on the transmitter side to retain low PAPR, improve performance, and reduce computational complexity on the receiver side. The system is designed according to the following procedure. First, upper-triangular dirty paper coding (UDPC) is utilized to pre-cancel the interference among multiple streams and provide a one-tap time-domain equalizer for the SCBT system. Next, to solve the problem of the high PAPR of the UDPC precoding system, Tomlinson-Harashima precoding (THP) is developed. Finally, since the UDPC-THP system is degraded by the deep fading channels, the dynamic channel on/off assignment by the maximum capacity algorithm (MCA) and minimum BER algorithm (MBA) is proposed to enhance the bit error rate (BER) performance. Simulation results reveal that the proposed precoding transceiver can provide excellent BER and low PAPR performances for the SCBT system over a multipath fading channel.
In this paper, a block-constrained trellis coded vector quantization (BC-TCVQ) algorithm is combined with an algebraic codebook to produce an algebraic trellis vector code (ATVC) to be used in ACELP coding. ATVC expands the set of allowed algebraic codebook pulse position, and the trellis branches are labeled with these subsets. The Viterbi algorithm is used to select the excitation codevector. A fast codebook search method using an efficient non-exhaustive search technique is also proposed to reduce the complexity of the ATVC search procedure while maintaining the quality of the reconstructed speech. The ATVC block code is used as the fixed codebook of AMR-NB (12.2 kbps), which reduces the computational complexity compared to the conventional algebraic codebook.
Yuki MISHIMA Yoshinobu KAJIKAWA
In this paper, we propose an automatic parameter adjustment method for audio equalizers using an interactive genetic algorithm (IGA). It is very difficult for ordinary users who are not familiar with audio devices to appropriately adjust the parameters of audio equalizers. We therefore propose a system that can automatically adjust the parameters of audio equalizers on the basis of user's evaluation of the reproduced sound. The proposed system utilizes an IGA to adjust the gains and Q values of the peaking filters included in audio equalizers. Listening test results demonstrate that the proposed system can appropriately adjust the parameters on the basis of the user's evaluation.
Yosuke SUGIURA Arata KAWAMURA Youji IIGUNI
This paper proposes an adaptive comb filter with flexible notch gain. It can appropriately remove a periodic noise from an observed signal. The proposed adaptive comb filter uses a simple LMS algorithm to update the notch gain coefficient for removing the noise and preserving a desired signal, simultaneously. Simulation results show the effectiveness of the proposed comb filter.
Jaehyun PARK Yunju PARK Sunghyun HWANG Byung Jang JEONG
In this paper, low-complexity generalized singular value decomposition (GSVD) based beamforming schemes are proposed for a cognitive radio (CR) network in which multiple secondary users (SUs) with multiple antennas coexist with multiple primary users (PUs). In general, optimal beamforming, which suppresses the interference caused at PUs to below a certain threshold and maximizes the signal-to-interference-plus-noise ratios (SINRs) of multiple SUs simultaneously, requires a complicated iterative optimization process. To overcome the computational complexity, we introduce a signal-to-leakage-plus-noise ratio (SLNR) maximizing beamforming scheme in which the weight can be obtained by using the GSVD algorithm, and does not require any iterations or matrix squaring operations. Here, to satisfy the leakage constraints at PUs, two linear methods, zero forcing (ZF) preprocessing and power allocation, are proposed.
Nagao OGINO Takuya OMI Hajime NAKAMURA
Secret sharing schemes have been proposed to protect content by dividing it into many pieces securely and distributing them over different locations. Secret sharing schemes can also be used for the secure delivery of content. The original content cannot be reconstructed by the attacker if the attacker cannot eavesdrop on all the pieces delivered from multiple content servers. This paper aims to obtain secure delivery routes for the pieces, which minimizes the probability that all the pieces can be stolen on the links composing the delivery routes. Although such a route optimization problem can be formulated using an ILP (Integer Linear Programming) model, optimum route computation based on the ILP model requires large amounts of computational resources. Thus, this paper proposes a lightweight route computation method for obtaining suboptimum delivery routes that achieve a sufficiently small probability of all the pieces being stolen. The proposed method computes the delivery routes successively by using the conventional shortest route algorithm repeatedly. The distance of the links accommodating the routes that have already been calculated is adjusted iteratively and utilized for calculation of the new shortest route. The results of a performance evaluation clarify that sufficiently optimum routes can be computed instantly even in practical large-scale networks by the proposed method, which adjusts the link distance strictly based on the risk level at the considered link.
Yusuke KUWAHARA Yusuke IWAMATSU Kensaku FUJII Mitsuji MUNEYASU Masakazu MORIMOTO
In this paper, we propose a normalization method dividing the gradient vector by the sum of the diagonal and two adjoining elements of the matrix expressing the correlation between the components of the discrete Fourier transform (DFT) of the reference signal used for the identification of unknown system. The proposed method can thereby improve the estimation speed of coefficients of adaptive filter.
Dongpei LIU Hengzhu LIU Botao ZHANG Jianfeng ZHANG Shixian WANG Zhengfa LIANG
High-performance FFT processor is indispensable for real-time OFDM communication systems. This paper presents a CORDIC based design of variable-length FFT processor which can perform various FFT lengths of 64/128/256/512/1024/2048/4096/8192-point. The proposed FFT processor employs memory based architecture in which mixed radix 4/2 algorithm, pipelined CORDIC, and conflict-free parallel memory access scheme are exploited. Besides, the CORDIC rotation angles are generated internally based on the transform of butterfly counter, which eliminates the need of ROM making it memory-efficient. The proposed architecture has a lower hardware complexity because it is ROM-free and with no dedicated complex multiplier. We implemented the proposed FFT processor and verified it on FPGA development platform. Additionally, the processor is also synthesized in 0.18 µm technology, the core area of the processor is 3.47 mm2 and the maximum operating frequency can be up to 500 MHz. The proposed FFT processor is better trade off performance and hardware overhead, and it can meet the speed requirement of most modern OFDM system, such as IEEE 802.11n, WiMax, 3GPP-LTE and DVB-T/H.
Compressing a JPEG image twice will greatly decrease the values of some of its DCT coefficients. This effect can be easily detected by statistics methods. To defend this forensic method, we establish a model to evaluate the security and image quality influenced by the re-compression. Base on the model, an optimized adjustment of the DCT coefficients is achieved by Genetic Algorithm. Results show that the traces of double compression are removed while preserving image quality.
Shunsuke YOSHIMURA Hiroshi HIRAYAMA Nobuyoshi KIKUMA Kunio SAKAKIBARA
A novel method for automatically creating an optimum direction-of-arrival (DOA) estimation algorithm for a given radio environment using a genetic algorithm (GA) is proposed. DOA estimation algorithms are generally described by parameters and operators. The performance of a DOA estimation algorithm is evaluated using root mean square error (RMSE) through computer simulations. A GA searches for the combination of parameters and operators that gives the lowest RMSE. Because a GA can treat only bit strings, Polish notation is used to convert bit strings into a DOA estimation algorithm. A computer simulation showed that the proposed method can create a new angle spectrum function. The created angle spectrum function has higher resolution than the Capon method.
Aroba KHAN Hernan AGUIRRE Kiyoshi TANAKA
This paper presents two halftoning methods to improve efficiency in generating structurally similar halftone images using Structure Similarity Index Measurement (SSIM). Proposed Method I reduces the pixel evaluation area by applying pixel-swapping algorithm within inter-correlated blocks followed by phase block-shifting. The effect of various initial pixel arrangements is also investigated. Proposed Method II further improves efficiency by applying bit-climbing algorithm within inter-correlated blocks of the image. Simulation results show that proposed Method I improves efficiency as well as image quality by using an appropriate initial pixel arrangement. Proposed Method II reaches a better image quality with fewer evaluations than pixel-swapping algorithm used in Method I and the conventional structure aware halftone methods.
Yuki SATOMI Arata KAWAMURA Youji IIGUNI
For an adaptive system identification filter with a stochastic input signal, a coefficient vector updated with an NLMS algorithm converges in the sense of ensemble average and the expected convergence vector has been revealed. When the input signal is periodic, the convergence of the adaptive filter coefficients has also been proved. However, its convergence vector has not been revealed. In this paper, we derive the convergence vector of adaptive filter coefficients updated with the NLMS algorithm in system identification for deterministic sinusoidal inputs. Firstly, we derive the convergence vector when a disturbance does not exist. We show that the derived convergence vector depends only on the initial vector and the sinusoidal frequencies, and it is independent of the step-size for adaptation, sinusoidal amplitudes, and phases. Next, we derive the expected convergence vector when the disturbance exists. Simulation results support the validity of the derived convergence vectors.
Zhihua NIU Zhe LI Zhixiong CHEN Tongjiang YAN
The linear complexity and its stability of periodic sequences are of fundamental importance as measure indexes on the security of stream ciphers and the k-error linear complexity reveals the stability of the linear complexity properly. Recently, Zhou designed an algorithm for computing the k-error linear complexity of 2pn periodic sequences over GF(q). In this paper, we develop a genetic algorithm to confirm that one can't get the real k-error linear complexity for some sequenes by the Zhou's algorithm. Analysis indicates that the Zhou's algorithm is unreasonable in some steps. The corrected algorithm is presented. Such algorithm will increase the amount of computation, but is necessary to get the real k-error linear complexity. Here p and q are odd prime, and q is a primitive root (mod p2).
Min ZHU Huigang WANG Guoyue CHEN Kenji MUTO
It is shown that simple preprocessing on the reference signals in multichannel feedforward ANC system can improve the convergence performance of the adaptive ANC algorithm. A fast and efficient blind preprocessing algorithm in frequency domain is proposed to reduce the computational complexity even that the reference sensors are located far from the noise sources. The permutation problem at different frequency bin is also addressed and solved by an independent vector analysis algorithm. The basic principle and performance comparison are given to verify our conclusion.
This study proposes an improved per-survivor-processing (PSP) scheme to tackle the phase error issue in the convolutionally coded OFDM systems. The proposed approach takes advantage of the trellis structure of the convolutional codes to compensate the symbol-time-offset (STO) caused phase error in frequency domain. Unlike the traditional PSP scheme which simply estimates the phase error by using a state-based horizontal process, the proposed approach develops an extra state-wise vertical process which selects the most likely phase estimate as the survival phase in each trellis stage and then accordingly align the phase of all states to this survival phase before moving to next trellis stage of the PSP scheme. With the vertical process, the resultant phase estimate is more reliable than that of the conventional PSP scheme and hence improve the accuracy in data decoding. Computer simulations confirm the validity of the proposed approach.