In this letter, a low-cost weighted interpolation scheme (WIS) for deinterlacing within a single frame is discussed. Three useful weights measurements are introduced within the operation window to reduce false decisions on the basis of the LCID algorithm. The WIS algorithm has a simple weight-evaluating structure with low complexity, which therefore makes it easy to implement in hardware. Experimental results demonstrated that the WIS algorithm performs better than previous techniques.

Trust negotiation is an authorizing technique based on digital credentials, in which both a user and a server gradually establish trust in each other by repeatedly exchanging their credentials. A trust negotiation strategy is a function that answers a set of credentials to disclose to the other party, depending on policies and the set of already disclosed credentials. The disclosure tree strategy (DTS), proposed by Yu et al., is one of the strategies that satisfies preferable properties. DTS in a simple implementation requires exponential time and space; however, neither an efficient algorithm nor the lower-bound of its complexity was known. In this paper, we investigate the computational complexity of DTS. We formulate subproblems of DTS as problems on derivation trees of a context-free grammar (CFG), and analyze the computational complexity of the subproblems using the concepts of CFGs. As a result, we show that two subproblems EVL and MSET of DTS are NP-complete and NP-hard, respectively, while both are solvable in polynomial time if we modify EVL not to require non-redundancy and MSET not to answer any subset useless for leading the negotiation to success.

This paper describes a general quantum lower bounding technique for the communication complexity of a function that depends on the inputs given to two parties connected via paths, which may be shared with other parties, on a network of any topology. The technique can also be employed to obtain a lower-bound of the quantum communication complexity of some functions that depend on the inputs distributed over all parties on the network. As a typical application, we apply our technique to the distinctness problem of deciding whether there are a pair of parties with identical inputs, on a k-party ring; almost matching upper bounds are also given.

This paper introduces a new timetabling problem on universities, called interview timetabling. In this problem, some constant number, say three, of referees are assigned to each of 2n graduate students. Our task is to construct a presentation timetable of these 2n students using n timeslots and two rooms, so that two students evaluated by the same referee must be assigned to different timeslots. The optimization goal is to minimize the total number of movements of all referees between two rooms. This problem comes from the real world in the interview timetabling in Kyoto University. We propose two restricted models of this problem, and investigate their time complexities.

In multiple antenna systems that use spatial multiplexing to raise transmission rates, it is preferable to use maximum likelihood (ML) detection to exploit the full receive diversity and minimize the error probability. In this paper, we present two tree based approximate ML detectors that use new two ordering criteria in conjunction with efficient search strategies. Unlike conventional tree detectors, the new detectors closely approximate the error performance of the exact ML detector while achieving a dramatic reduction in complexity. Moreover, they ensure a fixed detection delay and high level of parallelization in the tree search.

In this letter, we propose a novel singular value decomposition zero-forcing beamforming (SVD-ZFBF) relaying scheme in the multiuser downlink MIMO broadcasting channel with fixed relays. Based on the processing scheme, we apply SUS [5] to select users at the relay station (RS) and develop a joint power allocation strategy at the base station (BS) and RS. By increasing the power at RS or selecting active users to obtain more multiuser diversity, SVD-ZFBF can approach an upper bound and outperform SVD-ZFDPC [1] with much lower complexity. Moreover, we show that the noise power ratio of RS to users significantly impacts the performance.

The wireless systems that establish multiple input multiple output (MIMO) channels through multiple antennas at both ends of the communication link, have been proved to have tremendous potential to linearly lift the capacity of conventional scalar channel. In this paper, we present two efficient decision feedback equalization algorithms that achieve optimal and suboptimal detection order in MIMO spatial multiplexing systems. The new algorithms combine the recursive matrix inversion and ordered QR decomposition approaches, which are developed for nulling cancellation interaface Bell Labs layered space time (BLAST) and back substitution interface BLAST. As a result, new algorithms achieve total reduced complexities in frame based transmission with various payload lengths compared with the earlier methods. In addition, they enable shorter detection delay by carrying out a fast hybrid preprocessing. Moreover, the operation precision insensitivity of order optimization greatly relaxes the word length of matrix inversion, which is the most computational intensive part within the MIMO detection task.

A new class of sextic residue sequences of period prime p=4u2+27=6f+1 ≡ 3 ( mod 8) are presented. Their trace function representations are determined. And the exact value of the linear complexity is derived from the trace function representations. The result indicates that the new sextic sequences are quite good from the linear complexity viewpoint.

This paper proposes Twin Turbo (T2) MIMO-OFDM (Multiple Input Multiple Output-Orthogonal Frequency Division Multiplexing). The advanced iterative decoder, called the T2 decoder, decreases the transmission error rate compared to conventional turbo decoders because it uses the correlation information among the bits mapped on an identical symbol of multi-level modulation and updates the channel reliability. When T2 is applied to a MIMO-OFDM, the required symbol energy to noise power density ratio (Es/N0) can be reduced more effectively than when T2 is applied to SISO (Single Input Single Output). This is because T2 can use the correlation among the bits not only mapped on an identical symbol but also transmitted from different antennas. Moreover, T2 achieves good performance in a correlated MIMO channel because the average minimum squared Euclidean distances between symbol replica candidates consisting of signals transmitted from multiple transmitter antennas are reduced. Computer simulations verify that the required Es/N0 of T2 MIMO-OFDM using 16QAM is 1.9 dB lower than that of a conventional turbo decoder when the correlation coefficients of transmitter and receiver antennas are 0.8. A computational complexity analysis clarifies the relation between the increase in computational complexity and the reduction in the required Es/N0.

Linear complexity can be used to detect predictable nonrandom sequences, and hence it is included in the NIST randomness test suite. But, as shown in this paper, the NIST test suite cannot detect nonrandom sequences that are generated, for instance, by concatenating two different M-sequences with low linear complexity. This defect comes from the fact that the NIST linear complexity test uses deviation from the ideal value only in the last part of the whole linear complexity profile. In this paper, a new faithful linear complexity test is proposed, which uses deviations in all parts of the linear complexity profile and hence can detect even the above nonrandom sequences. An efficient formula is derived to compute the exact area distribution needed for the proposed test. Furthermore, a simple procedure is given to compute the proposed test statistic from linear complexity profile, which requires only O(M) time complexity for a sequence of length M.

This paper presents an easy and efficient modification of simplified 2D ray-launching method, by approximately including multiple reflection effect inside walls for indoor environment. In order to precisely carry out the ray-launching procedure inside lossy wall, a simple modification using a true real refraction angle is first introduced, instead of complex one. Furthermore, an efficient approximation is carried out to collect the internal multiple reflected rays into the primary one. We here call it collective ray approach. Consequently, it is confirmed from the detailed considerations that the present ray representations obtained by introducing the real refraction angle are well suitable for indoor propagation analysis, and in particular the collective ray solution can be utilized confidently even when the internal reflections strongly contribute to the propagation feature of the considered indoor environment.

Because of the fact that mobile communication channel changes by time, it is necessary to employ adaptive channel equalizers in order to combat the distorting effects of the channel. Least Mean Squares (LMS) algorithm is one of the most popular channel equalization algorithms and is preferred over other algorithms such as the Recursive Least Squares (RLS) and Maximum Likelihood Sequence Estimation (MLSE) when simplicity is the dominant decision factor. However, LMS algorithm suffers from poor performance and convergence speed within the training period specified by most of the standards. The aim of this study is to improve the convergence speed and performance of the LMS algorithm by adjusting the step size using fuzzy logic. The proposed method is compared with the Channel Matched Filter-Decision Feedback Equalizer (CMF-DFE) [1] which provides multi path propagation diversity by collecting the energy in the channel, Minimum Mean Square Error-Decision Feedback Equalizer (MMSE-DFE) [2] which is one of the most successful equalizers for the data packet transmission, normalized LMS-DFE (N-LMS-DFE) [3] , variable step size (VSS) LMS-DFE [4] , fuzzy LMS-DFE [5],[6] and RLS-DFE [7] . The obtained simulation results using HIPERLAN/1 standards have demonstrated that the proposed LMS-DFE algorithm based on fuzzy logic has considerably better performance than others.

Recently, a data-selective method has been proposed to achieve low misalignment in affine projection algorithm (APA) by keeping the condition number of an input data matrix small. We present an improved method, and a complexity reduction algorithm for the APA with the data-selective method. Experimental results show that the proposed algorithm has lower misalignment and a lower condition number for an input data matrix than both the conventional APA and the APA with the previous data-selective method.

Reversal complexity has been studied as a fundamental computational resource along with time and space complexity. We revisit it by contrasting with access complexity which we introduce in this study. First, we study the structure of space bounded reversal and access complexity classes. We characterize the complexity classes L, P and PSPACE in terms of space bounded reversal and access complexity classes. We also show that the difference between polynomial space bounded reversal and access complexity is related with the L versus P problem. Moreover, we introduce a theory of memory access patterns, which is an abstracted structure of the order of memory accesses during a random access computation, and extend the notion of reversal and access complexity for general random access computational models. Then, we give probabilistic analyses of reversal and access complexity for almost all memory access patterns. In particular, we prove that almost all memory access patterns have ω(log n) reversal complexity while all languages in L are computable within O(log n) reversal complexity.

The complexity of Finite Impulse Response (FIR) filters is mainly dominated by the number of adders (subtractors) used to implement the coefficient multipliers. It is well known that Common Subexpression Elimination (CSE) method based on Canonic Signed Digit (CSD) representation considerably reduces the number of adders in coefficient multipliers. Recently, a binary-based CSE (BSE) technique was proposed, which produced better reduction of adders compared to the CSD-based CSE. In this paper, we propose a new 4-bit binary representation-based CSE (BCSE-4) method which employs 4-bit Common Subexpressions (CSs) for implementing higher order low-power FIR filters. The proposed BCSE-4 offers better reduction of adders by eliminating the redundant 4-bit CSs that exist in the binary representation of filter coefficients. The reduction of adders is achieved with a small increase in critical path length of filter coefficient multipliers. Design examples show that our BCSE-4 gives an average power consumption reduction of 5.2% and 6.1% over the best known CSE method (BSE, NR-SCSE) respectively, when synthesized with TSMC-0.18 µm technology. We show that our BCSE-4 offers an overall adder reduction of 6.5% compared to BSE without any increase in critical path length of filter coefficient multipliers.

To understand the structural and functional properties of large-scale complex networks, it is crucial to efficiently extract a set of cohesive subnetworks as communities. There have been proposed several such community extraction methods in the literature, including the classical k-core decomposition method and, more recently, the k-clique based community extraction method. The k-core method, although computationally efficient, is often not powerful enough for uncovering a detailed community structure and it produces only coarse-grained and loosely connected communities. The k-clique method, on the other hand, can extract fine-grained and tightly connected communities but requires a substantial amount of computational load for large-scale complex networks. In this paper, we present a new notion of a subnetwork called k-dense, and propose an efficient algorithm for extracting k-dense communities. We applied our method to the three different types of networks assembled from real data, namely, from blog trackbacks, word associations and Wikipedia references, and demonstrated that the k-dense method could extract communities almost as efficiently as the k-core method, while the qualities of the extracted communities are comparable to those obtained by the k-clique method.

The C-oscillation due to Martin-Löf shows that {α| ∀ n [C(α n)≥ n-O(1)]=, which also follows {α| ∀ n [K(α n)≥ n+K(n)-O(1)]=. By generalizing them, we show that there does not exist a real α such that ∀ n (K(α n)≥ n+λ K(n)-O(1)) for any λ>0.

We present a tight time-hierarchy theorem for nondeterministic cellular automata by using a recursive padding argument. It is shown that, if t2(n) is a time-constructible function and t2(n) grows faster than t1(n+1), then there exists a language which can be accepted by a t2(n)-time nondeterministic cellular automaton but not by any t1(n)-time nondeterministic cellular automaton.

A simple and successful design of initial codebook of vector quantization (VQ) is presented. For existing initial codebook algorithms, such as random method, the initial codebook is strongly influenced by selection of initial codewords and difficult to match with the features of the training vectors. In the proposed method, training vectors are sorted according to the norm of training vectors. Then, the ordered vectors are partitioned into N groups where N is the size of codebook. The initial codewords are obtained from calculating the centroid of each group. This initializtion method has a robust performance and can be combined with the VQ algorithm to further improve the quality of codebook.

In this letter, a new estimation filtering is proposed when a delay between signal generation and signal estimation exists. The estimation filter is developed under a maximum likelihood criterion using only the finite observations on the delay interval. The proposed estimation filter is represented in both matrix form and iterative form. It is shown that the filtered estimate has good inherent properties such as time-invariance, unbiasedness and deadbeat. Via numerical simulations, the performance of the proposed estimation filtering is evaluated by the comparison with that of the existing fixed-lag smoothing, which shows that the proposed approach could be appropriate for fast estimation of signals that vary relatively quickly. Moreover, the on-line computational complexity of the proposed estimation filter is shown to be maintained at a lower level than the existing one.