In this letter, we suggest two new efficient hardware structures of correlators for packet and frame synchronization of MB-OFDM UWB. In the proposed structure 1, we suggest a hierarchical structure composed of 8 and 16 tap sub-correlators instead of ordinary 128 tap correlators. In the proposed structure 2, we suggest a structure which uses quantized coefficients and simplified multipliers. Results of simulations indicates that the hardware complexities of proposed structures are reduced to about 54% and 31% with minor performance loss, compared with a conventional method.

This paper describes a numerical design procedure of element values of RC polyphase filters with equal minima in stopband and equal ripple in passband. Determination of element values of RC polyphase filters with equal-ripple characteristic have not been solved to the best knowledge of the authors. There found a paper tackling with the problem; however, it can only give sub-optimal solutions via numerical calculation [3]. We propose a numerical element value design procedure for RC polyphase filters with equi-ripple gain in both stopband and passband by using the coefficient matching method. Some design examples are given.

The paper presents an adaptive algorithm named adaptive threshold nonlinear algorithm for use in adaptive filters in the complex-number domain (c-ATNA) in applications to digital QAM systems. Although the c-ATNA is very simple to implement, it makes adaptive filters highly robust against impulse noise and at the same time it ensures filter convergence as fast as that of the well-known LMS algorithm. Analysis is developed to derive a set of difference equations for calculating transient behavior as well as steady-state performance. Experiment with simulations and theoretical calculations for some examples of filter convergence in the presence of Contaminated Gaussian Noise demonstrates that the c-ATNA is effective in combating impulse noise. Good agreement between simulated and theoretical convergence proves the validity of the analysis.

This paper introduces τk notation to be used to assess test generation complexity of classes of sequential circuits. Using τk notation, we reconsider and restate the time complexity of test generation for existing classes of acyclic sequential circuits. We also introduce a new DFT method called feedback shift register (FSR) scan design technique, which is extended from the scan design technique. Therefore, for a given sequential circuit, the corresponding FSR scan designed circuit has always equal or lower area overhead and test application time than the corresponding scan designed circuit. Furthermore, we identify some new classes of sequential circuits that contain some cyclic sequential circuits, which are τ-equivalent and τ2-bounded. These classes are the l-length-bounded testable circuits, l-length-bounded validity-identifiable circuits, t-time-bounded testable circuits and t-time-bounded validity-identifiable circuits. In addition, we provide two examples of circuits belonging to these classes, namely counter-cycle finite state machine realizations and state-shiftable finite state machine realizations. Instead of using a DFT method, a given sequential circuit described at the finite state machine (FSM) level can be synthesized using another test methodology called synthesis for testability (SFT) into a circuit that belongs to one of the easily testable classes of cyclic sequential circuits.

We propose an adaptive plastic-landmine visualizing radar system employing a complex-valued self-organizing map (CSOM) dealing with a feature vector that focuses on variance of spatial- and frequency-domain inner products (V-CSOM) in combination with aperture synthesis. The dimension of the new feature vector is greatly reduced in comparison with that of our previous texture feature-vector CSOM (T-CSOM). In experiments, we first examine the effect of aperture synthesis on the complex-amplitude texture in space and frequency domains. We also compare the calculation cost and the visualization performance of V- and T-CSOMs. Then we discuss merits and drawbacks of the two types of CSOMs with/without the aperture synthesis in the adaptive plastic-landmine visualization task. The V-CSOM with aperture synthesis is found promising to realize a useful plastic-landmine detection system.

To take intercarrier interference (ICI) attributed to time variations of the channel into consideration, the time- and frequency-selective (doubly-selective) channel is parameterized by a finite parameter model. By capitalizing on the finite parameter model to approximate the doubly-selective channel, a Kalman filter is developed for channel estimation. The ICI suppressing, reduced-complexity Viterbi-type Maximum Likelihood (RML) equalizer is incorporated into the Kalman filter for recursive channel tracking and equalization to improve the system performance. An enhancement in the channel tracking ability is validated by theoretical analysis, and a significant improvement in BER performance using the channel estimates obtained by the recursive channel estimation method is verified by Monte-Carlo simulations.

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. The k-error linear complexity of periodic sequences is defined to be the smallest linear complexity that can be obtained by changing k or fewer bits of the sequence per period. For 2pn-periodic binary sequences, where p is an odd prime and 2 is a primitive root modulo p2, we present and prove the unique expression of the linear complexity. Moreover we show a relationship between the linear complexity and the minimum value k for which the k-error linear complexity is strictly less than the linear complexity.

We study the complexity of the reachability problem for a new subclass of Petri nets called simple-circuit Petri nets, which properly contains several well known subclasses such as conflict-free, BPP, normal Petri nets and more. A new decomposition approach is applied to developing an integer linear programming formulation for characterizing the reachability sets of such Petri nets. Consequently, the reachability problem is shown to be NP-complete. The model checking problem for some temporal logics is also investigated for simple-circuit Petri nets.

In this paper, we introduce and describe the computational environment that we have developed for cellular automata (CA). CA are powerful methods to understand and simulate the behavior of complex systems such as traffic jams, fluid crosscurrents, and natural disasters. In CA method, modeling of such a system or a phenomenon is to define a transition function, which determines local interactions, so-called "CA rules." However, no systematic method for design of CA rules has been established. We require a CA simulator for "trial and error" in study of modeling based on CA. Furthermore, the CA simulation environment that does not require special knowledge of a user for parallel processing is desired. The purpose of this study is to develop a comprehensive system that enables us to expedite the design of local rules and to accelerate simulations. We have implemented two kinds of simulators differing in their characteristics to improve both design efficiency and execution speed. The major difference between the two simulators is whether a source code is compiled or not. The source code is described in DORA language the authors have designed for the system. DORA language is designed for describing CA rules simply.

In this paper, we evaluate the computational complexity and the performance of the RAKE receivers for the Direct Sequence--Ultra Wideband (DS-UWB) with considering the accuracy of channel estimation in a multipath channel. As RAKE receivers for DS-UWB, we consider the maximal-ratio combining (MRC)-RAKE, the minimum mean square error (MMSE)-RAKE, and the MRC-RAKE-Equalizer that is the MRC-RAKE followed by a liner equalizer. Generally, if the channel estimation is perfect, as the number of fingers or taps increases, the performance of each receiver is improved, however the computational complexity of each receiver increases. In practice, the channel estimation is not perfect. The channel estimation error makes their performances degraded. Therefore, the performances of the RAKE receivers depend on the accuracy of channel estimation. Consequently, we evaluate the computational complexities and the Bit Error Rates (BERs) of MRC-RAKE, MMSE-RAKE, and MRC-RAKE-Equalizer with considering the accuracy of channel estimation for DS-UWB. We show that the accuracy of channel estimation affects the BER of each receiver significantly. We also show that when the accuracy of channel estimation is high, MRC-RAKE-Equalizer can achieve the better BER than MMSE-RAKE with less computational complexity, while MMSE-RAKE can achieve the better BER than MRC-RAKE-Equalizer when the accuracy of channel estimation is low.

The optimal design of complex infinite impulse response (IIR) two-channel quadrature mirror filter (QMF) banks with equiripple frequency response is considered. The design problem is appropriately formulated to result in a simple optimization problem. Therefore, based on a variant of Karmarkar's algorithm, we can efficiently solve the optimization problem through a frequency sampling and iterative approximation method to find the complex coefficients for the IIR QMFs. The effectiveness of the proposed technique is to form an appropriate Chebyshev approximation of a desired response and then find its solution from a linear subspace in several iterations. Finally, simulation results are presented for illustration and comparison.

In this letter, we propose a simplified step-by-step decoding algorithm for t-error-correcting binary Bose-Chaudhuri- Hocquenghem (BCH) codes based on logical analysis. Compared to the conventional step-by-step decoding algorithm, the computation complexity of this decoder is much less, since it significantly reduces the matrix calculation and the operations of multiplication.

We have proposed in [5] a practical blind channel identification algorithm for the white observation noise. In this paper, we examine the effectiveness of the algorithm given in [5] for the colored observation noise. The proposed algorithm utilizes Gram-Schmidt orthogonalization procedure and estimates (1) the channel order, (2) the noise variance and then (3) the channel impulse response with less computational complexity compared to the conventional algorithms using eigenvalue decomposition. It can be shown through numerical examples that the algorithm proposed in [5] is quite effective in the colored noise case.

This paper describes an estimation of the computational and memory complexities of Greengard-Rokhlin's Fast Multipole Algorithm (GRFMA). GRFMA takes a quad tree structure and six calculation processes. We consider a perfect a-ary tree structure and the number of floating-point operations for each calculation process. The estimation for both complexities shows that the perfect quad tree is the best and the perfect binary tree is the worst. When we apply GRFMA to the computation of realistic problems, volume scattering are the best case and surface scattering are the worst case. In the worst case, the computational and memory complexities of GRFMA are O(Llog2 L) and O(Llog L), respectively. The computational complexity of GRFMA is higher than that of the multilevel fast multipole algorithm.

In this letter, we propose a complexity-scalable DCT-based video encoder which works for the highly resource-limited terminals, such as cellular phone, PDA, handheld terminals, etc. The basic concept in the proposed method is for DCT operations to be adaptively changing the complexity like buffer control algorithm in the CBR (Constant Bit-Rate) video encoder.

This paper presents a reduced-complexity maximum likelihood detection (MLD) scheme for orthogonal frequency division multiplexing with space division multiplexing (OFDM-SDM) systems. Original MLD is known to be an optimal scheme for detecting the spatially multiplexed signals. However, MLD suffers from an exponentially computational complexity because it involves an exhaustive search for the optimal result. In this paper, we propose a novel detection scheme, which drastically reduce the complexity of MLD while keeping performance losses small. The proposed scheme decouples the spatially multiplexed signals in two stages. In stage one, the estimated symbols obtained from zero-forcing (ZF) are used to limit the candidate symbol vectors. In stage two, to form a final estimate of the transmitted symbol vector, the Euclidean or original defined likelihood metric is examined over all symbol vectors obtained from stage 1. Both the bit error rate (BER) and packet error rate (PER) performances are evaluated over a temporally and spatially uncorrelated frequency selective channel through the computer simulations. For a four-transmit and four-receive OFDM-SDM system transmitting data at 144 Mbit/s and 216 Mbit/ss i.e., employing 16 Quadrature Amplitude Modulation (16QAM) and 64QAM subcarrier modulation over 16.6 MHz bandwidth channel, the degradation in required SNR from MLD for PER = 1% are about 0.6 dB and 1.5 dB, respectively. However, the complexity of MLD is reduced to 0.51000% and 0.01562%.

Generalized Tsume-Shogi (GTS) is Tsume-Shogi on the board of size n n for arbitrary n. The problem to decide the existence of a winning sequence of moves (where the attacker must always check) on an instance of GTS was proved to be exptime-complete by Yokota et al. (2000). This paper considers the complexity of yozume problem of GTS, which is, roughly speaking, the problem whether a given position of GTS has a winning sequence other than given sequences (though the actual rule of yozume is more complicated). The detection of yozume is an important issue in designing Tsume-Shogi problems, since the modern designing rule strongly prohibits it. We define a function problem of GTS appropriately to formulate yozume problem as its Another Solution Problem (ASP; the problem to decide the existence of solutions other than given ones). Moreover, we extend the existing framework for investigating ASPs so that it can be applied to exptime-complete problems. In particular, since the decision of correctness of given winning sequences is not easy, we establish a framework to treat ASP of function problems with promises. On the basis of these results, we prove that the decision version of yozume problem of GTS is exptime-complete as a promise problem using the existing reduction which was constructed by Yokota et al. to prove the exptime-completeness of GTS.

The aim of this work is to investigate the possibility of designing zero-knowledge identification schemes based on hard-on-average problems. It includes a new two-party identification protocol whose security relies on a discrete mathematics problem classified as DistNP-Complete under the average-case analysis, the so-called Distributional Matrix Representability Problem. Thanks to the use of the search version of the mentioned problem, the zero-knowledge property is formally proved by black-box simulation, and consequently the security of the proposed scheme is actually guaranteed. Furthermore, with the proposal of a new zero-knowledge proof based on a problem never used before for this purpose, the set of tools for designing cryptographic applications is enlarged.

An efficient computational Zero-Knowledge Proof of Knowledge whose security relies on the NP-completeness of the Independent Set Problem is presented here. The proposed algorithm is constructed from a bit commitment scheme based on the hardness of the Discrete Logarithm Problem, which guarantees the fulfillment of soundness, completeness and computational zero-knowledge properties, and allows avoiding the use of the Graph Isomorphism Problem, which is present in every known Zero-Knowledge Proofs for the Independent Set Problem.

In this paper two algorithms for the synthesis and minimization of a CA (cellular array architecture) are proposed. Starting from a completely specified single-output switching function, our methods produce rectangularly shaped arrays of cells, interconnected in chains, with an effort to minimize the number of the produced chains (cascades). This kind of cellular topology is known throughout the bibliography as Maitra cellular arrays. The significance of those algorithms is underlined by the fact that this particular type of cellular architecture can be mapped to reversible circuits and gates (generalized Toffoli gates), which are the type of logic used in quantum circuits. The proposed methodologies include use of ETDDs (EXOR ternary decision diagrams), and switching function decompositions (including new types of boolean expansions).