ShanXue CHEN FangWei LI WeiLe ZHU TianQi ZHANG
A fast algorithm to speed up the search process of vector quantization encoding is presented. Using the sum and the partial norms of a vector, some eliminating inequalities are constructeded. First the inequality based on the sum is used for determining the bounds of searching candidate codeword. Then, using an inequality based on subvector norm and another inequality combining the partial distance with subvector norm, more unnecessary codewords are eliminated without the full distance calculation. The proposed algorithm can reject a lot of codewords, while introducing no extra distortion compared to the conventional full search algorithm. Experimental results show that the proposed algorithm outperforms the existing state-of-the-art search algorithms in reducing the computational complexity and the number of distortion calculation.
Multi-user MIMO (Multiple Input Multiple Output) systems, in which multiple Mobile Stations (MSs) equipped with multiple antennas simultaneously communicate with a Base Station (BS) equipped with multiple antennas, at the same frequency, are attracting attention because of their potential for improved transmission performance in wireless communications. In the uplink of Space Division Multiplexing based multi-user MIMO (multi-user MIMO/SDM) systems that do not require full Channel State Information (CSI) at the transmitters, selecting active MS antennas, which corresponds to scheduling transmit antennas, is an effective technique. The Full search Selection Algorithm based on exhaustive search (FSA) has been studied as an optimal active MS antenna selection algorithm for multi-user MIMO systems. Unfortunately, FSA suffers from extreme computational complexity given large numbers of MSs. To solve this problem, this paper introduces the Gram-Schmidt orthogonalization based Selection Algorithm (GSSA) to uplink multi-user MIMO/SDM systems. GSSA is a suboptimal active MS antenna selection algorithm that offers lower computational complexity than the optimal algorithm. This paper evaluates the transmission performance improvement of GSSA in uplink multi-user MIMO/SDM systems under realistic propagation conditions such as spatially correlated BS antennas and clarifies the effectiveness of GSSA.
Junya MATSUNO Hiroki SATO Akira HYOGO Keitaro SEKINE
A three-phase complex filter for a balanced three-phase analog signal processing is proposed. The proposed three-phase active-RC Tow-Thomas biquad complex filter can reduce total resistance by 10 percent, total capacitance by 25 percent, and power consumption by 22 percent compared to a conventional fully differential quadrature complex one.
Wei GUAN Hanwen LUO Haibin ZHANG
In this letter, we develop a two-step receive antenna selection method to maximize channel capacity. Different from previous work, we first derive a lower bound on capacity based on Hadamard inequality and arithmetic-geometric mean inequality, which is then used to iteratively drop the worst-performing antennas according to their measure. The recursive nature of this method helps to largely reduce the computational complexity.
Code acquisition performance in the Direct-Sequence Code-Division Multiple-Access (DS/CDMA) communication system is strongly related to the quality of the communication systems. The performance is assessed by (i) code acquisition time; (ii) precision; and (iii) complexity for implementation. This paper applies the method of maximum likelihood (ML) to estimation of propagation delay in DS/CDMA communications, and proposes a low-complexity method for code acquisition. First, a DS/CDMA system model and properties of outputs with a passive matched-filter receiver are reviewed, and a statistical problem in code acquisition is mentioned. Second, an error-controllable code acquisition method based on the maximum likelihood is discussed. Third, a low-complexity ML code acquisition method is proposed. It is shown that the code acquisition time with the low-complexity method is about 1.5 times longer than that with the original ML method, e.g. 13 data periods under 4.96 dB.
We characterize the gap between time and space complexity of functions by operators and completeness. First, we introduce a new notion of operators for function complexity classes based on recursive function theory and construct an operator which generates FPSPACE from FP. Then, we introduce new function classes composed of functions whose output lengths are bounded by the input length plus some constant. We characterize FP and FPSPACE by using these classes and operators. Finally, we define a new notion of completeness for FPSPACE and show a FPSPACE-complete function.
Keiichi FUNAKI Tatsuhiko KINJO
Complex speech analysis for an analytic speech signal can accurately estimate the spectrum in low frequencies since the analytic signal provides spectrum only over positive frequencies. The remarkable feature makes it possible to realize more accurate F0 estimation using complex residual signal extracted by complex-valued speech analysis. We have already proposed F0 estimation using complex LPC residual, in which the autocorrelation function weighted by AMDF was adopted as the criterion. The method adopted MMSE-based complex LPC analysis and it has been reported that it can estimate more accurate F0 for IRS filtered speech corrupted by white Gauss noise although it can not work better for the IRS filtered speech corrupted by pink noise. In this paper, robust complex speech analysis based on ELS (Extended Least Square) method is introduced in order to overcome the drawback. The experimental results for additive white Gauss or pink noise demonstrate that the proposed algorithm based on robust ELS-based complex AR analysis can perform better than other methods.
Masao NAGANO Toshio ONODERA Mototaka SONE
A sweep spectrum analyzer has been improved over the years, but the fundamental method has not been changed before the 'Super Sweep' method appeared. The 'Super Sweep' method has been expected to break the limitation of the conventional sweep spectrum analyzer, a limit of the maximum sweep rate which is in inverse proportion to the square of the frequency resolution. The superior performance of the 'Super Sweep' method, however, has not been experimentally proved yet. This paper gives the experimental evaluation on the 'Super Sweep' spectrum analyzer, of which theoretical concepts have already been presented by the authors of this paper. Before giving the experimental results, we give complete analysis for a sweep spectrum analyzer and express the principle of the super-sweep operation with a complete set of equations. We developed an experimental system whose components operated in an optimum condition as the spectrum analyzer. Then we investigated its properties, a peak level reduction and broadening of the frequency resolution of the measured spectrum, by changing the sweep rate. We also confirmed that the experimental system satisfactorily detected the spectrum at least 30 times faster than the conventional method and the sweep rate was in proportion to the bandwidth of the base band signal to be analyzed. We proved that the 'Super Sweep' method broke the restriction of the sweep rate put on a conventional sweep spectrum analyzer.
Masatsugu HIGASHINAKA Katsuyuki MOTOYOSHI Akihiro OKAZAKI Takayuki NAGAYASU Hiroshi KUBO Akihiro SHIBUYA
This paper proposes a likelihood estimation method for reduced-complexity maximum-likelihood (ML) detectors in a multiple-input multiple-output (MIMO) spatial-multiplexing (SM) system. Reduced-complexity ML detectors, e.g., Sphere Decoder (SD) and QR decomposition (QRD)-M algorithm, are very promising as MIMO detectors because they can estimate the ML or a quasi-ML symbol with very low computational complexity. However, they may lose likelihood information about signal vectors having the opposite bit to the hard decision and bit error rate performance of the reduced-complexity ML detectors are inferior to that of the ML detector when soft-decision decoding is employed. This paper proposes a simple estimation method of the lost likelihood information suitable for the reduced-complexity ML detectors. The proposed likelihood estimation method is applicable to any reduced-complexity ML detectors and produces accurate soft-decision bits. Computer simulation confirms that the proposed method provides excellent decoding performance, keeping the advantage of low computational cost of the reduced-complexity ML detectors.
In this paper, a frequency transformation for designing polyphase transfer functions is proposed. A modification to the bilinear LP-LP transformation, which assigns both stopband edges on negative frequency range whereas passband edges are on positive one, results polyphase transfer functions. Design examples show validity of the proposed method.
This paper introduces an adaptive low complexity pre-processing filter to improve the coding performance of seriously degraded video sequences that is caused by the additive noise. The additive noise leads to a decrease in coding performance due to the high frequency components. By incorporating local statistics and quantization parameter into filtering process, the spurious noise is significantly attenuated and coding efficiency is improved for given quantization step size. In order to reduce the complexity of the pre-processing filter, the simplified local statistics and quantization parameter are introduced. The simulation results show the capability of the proposed algorithm.
Xiaoni DU Yu ZHOU Rong SUN Guozhen XIAO
In this letter, we examine the linear complexity of some 3-ary sequences, proposed by No, of period 3n-1(n=3ek, e, k integer) with the ideal autocorrelation property. The exact value of linear complexity k(6e)w is determined when the parameter r =. Furthermore, the upper bound of the linear complexity is given when the other forms of the value r is taken. Finally, a Maple program is designed to illustrate the validity of the results.
Energy-efficiency is one of the main concerns in the wireless information dissemination system. This paper presents a wireless broadcast stream organization scheme which enables complex queries (e.g., aggregation queries) to be processed in an energy-efficient way. For efficient processing of complex queries, we propose an approach of broadcasting their pre-computed results with the data stream, wherein the way of replication of index and pre-computation results are investigated. Through analysis and experiments, we show that the new approach can achieve significant performance enhancement for complex queries with respect to the access time and tuning time.
We focus on the relationship between the linearization method and linear complexity and show that the linearization method is another effective technique for calculating linear complexity. We analyze its effectiveness by comparing with the logic circuit method. We compare the relevant conditions and necessary computational cost with those of the Berlekamp-Massey algorithm and the Games-Chan algorithm. The significant property of a linearization method is that it needs no output sequence from a pseudo-random number generator (PRNG) because it calculates linear complexity using the algebraic expression of its algorithm. When a PRNG has n [bit] stages (registers or internal states), the necessary computational cost is smaller than O(2n). On the other hand, the Berlekamp-Massey algorithm needs O(N2) where N ( 2n) denotes period. Since existing methods calculate using the output sequence, an initial value of PRNG influences a resultant value of linear complexity. Therefore, a linear complexity is generally given as an estimate value. On the other hand, a linearization method calculates from an algorithm of PRNG, it can determine the lower bound of linear complexity.
Microwave measurement methods necessary to characterize copper-clad dielectric laminate substrates are reviewed to realize more precise design of planar circuits: that is, the balanced-type circular disk resonator method for the relative complex permittivity in the normal direction εrn and tan δn, the cavity resonator method and the cut-off waveguide method for one in the tangential direction εrt and tan δt, and the dielectric resonator method for the surface and interface conductivity of copper foil σs and σi. The measured results of the frequency and temperature dependences of these parameters are presented for a PTFE substrate and a copper-clad glass cloth PTFE laminate substrate.
Masato TAJIMA Koji OKINO Takashi MIYAGOSHI
Yamada, Harashima, and Miyakawa proposed to use a trellis constructed based on a syndrome former for the purpose of Viterbi decoding of rate-(n-1)/n convolutional codes. In this paper, we extend their code-trellis construction to general rate-k/n convolutional codes. We show that the extended construction is equivalent to the one proposed by Sidorenko and Zyablov. Moreover, we show that the proposed method can also be applied to an error-trellis construction with minor modification.
Wenjie JIANG Yusuke ASAI Takeshi ONIZAWA Satoru AIKAWA
In rich scattering environments, multiple antenna systems designed to accomplish spatial multiplexing have enormous potential of lifting the capacity of corresponding multiple input multiple output channels. In this paper, we present a new low complexity algorithm for decision feedback equalization detector in the SM scheme. The basic idea is to reduce the joint optimization problem to separate optimization problems to achieve better performance-complexity tradeoffs. Concretely, we separately optimize the detection order and the detector filters so that the complexity of the entire signal detection task is reduced. The new order search rule approximates the optimal Bell Labs layered space time (BLAST) approach from a geometrical perspective, and the detector filters are derived using a Cholesky based QR decomposition. The new algorithm is able to switch from zero forcing to minimum mean square error without additional operations and the computational effort is a small fraction of that in the optimal BLAST algorithm. Despite its low complexity, the error performance of new detector closely approximates that of the standard BLAST.
Takanori KOMATSU Akira NAMATAME
It has been widely observed that high-bandwidth traffic aggregates often occur by flooding-based distributed denial-of-service (DDoS) attacks. Several congestion control methods have been proposed for bandwidth controls. These methods are also considered to be important in order to avoid collapse of network services by DDoS attacks. We perform simulation studies of these well-known crowd management methods in order to minimize the damage caused by DDoS attacks with bandwidth control. Internet topologies have many facets in terms of the focus of the observation. Therefore, we need to conduct simulation of DDoS attacks in different Internet topologies, including the tiers model, the transit-stub model, and the Barabasi-Albert model. Using RED, CHOKe, and pushback with ACC as congestion control methods, we evaluate network resistance against DDoS attacks and similar overflow problems.
Shengqiang LI Zhixiong CHEN Rong SUN Guozhen XIAO
In this letter we introduce new generalized cyclotomic sequences of order two and length pq firstly, then we determine the linear complexity and autocorrelation values of these sequences. Our results show that these sequences are rather good from the linear complexity viewpoint.
Hideyuki FURUHASHI Yoshinobu KAJIKAWA Yasuo NOMURA
In this paper, we propose a low complexity realization method for compensating for nonlinear distortion. Generally, nonlinear distortion is compensated for by a linearization system using a Volterra kernel. However, this method has a problem of requiring a huge computational complexity for the convolution needed between an input signal and the 2nd-order Volterra kernel. The Simplified Volterra Filter (SVF), which removes the lines along the main diagonal of the 2nd-order Volterra kernel, has been previously proposed as a way to reduce the computational complexity while maintaining the compensation performance for the nonlinear distortion. However, this method cannot greatly reduce the computational complexity. Hence, we propose a subband linearization system which consists of a subband parallel cascade realization method for the 2nd-order Volterra kernel and subband linear inverse filter. Experimental results show that this proposed linearization system can produce the same compensation ability as the conventional method while reducing the computational complexity.