Time domain synchronous orthogonal frequency division multiplexing (TDS-OFDM) has higher spectral efficiency than the standard cyclic prefix OFDM (CP-OFDM) OFDM by replacing the random CP with the known training sequence (TS), which could be also used for synchronization and channel estimation. However, TDS-OFDM requires suffers from performance loss over fading channels due to the iterative interference cancellation has to be used to remove the mutual interferences between the TS and the useful data. To solve this problem, the novel TS based OFDM transmission scheme, referred to as the unified time-frequency OFDM (UTF-OFDM), is proposed in which the time-domain TS and the frequency-domain pilots are carefully designed to naturally avoid the interference from the TS to the data without any reconstruction. The proposed UTF-OFDM based flexible frame structure supports effective channel estimation and reliable channel equalization, while imposing a significantly lower complexity than the TDS-OFDM system at the cost of a slightly reduced spectral efficiency. Simulation results demonstrate that the proposed UTF-OFDM substantially outperforms the existing TDS-OFDM, in terms of the system's achievable bit error rate.

We study the computational complexity of the following two-player game. The instance is a graph G = (V,E), an initial vertex s ∈ V, and a target set T ⊆ V. A “cat” is initially placed on s. Player 1 chooses a vertex in the graph and removes it and its incident edges from the graph. Player 2 moves the cat from the current vertex to one of the adjacent vertices. Players 1 and 2 alternate removing a vertex and moving the cat, respectively. The game continues until either the cat reaches a vertex of T or the cat cannot be moved. Player 1 wins if and only if the cat cannot be moved before it reaches a vertex of T. It is shown that deciding whether player 1 has a forced win on the game on G is PSPACE-complete.

In complex network analysis, there are various measures to characterize the centrality of each node within a graph, which determines the relative importance of each node. The more centrality a node has in a network, the more significance it has in the spread of infection. As one of the important extensions to shortest-path based betweenness centrality, the flow betweenness centrality is defined as the degree to which each node contributes to the sum of maximum flows between all pairs of nodes. One of the drawbacks of the flow betweenness centrality is that its time complexity is somewhat high. This Letter proposes an approximate method to calculate the flow betweenness centrality and provides experimental results as evidence.

We show a phase transition of the first eigenvalue of random (c,d)-regular graphs, whose instance of them consists of one vertex with degree c and the other vertices with degree d for c > d. We investigate a reduction from the first eigenvalue analysis of a general (c,d)-regular graph to that of a tree, and prove that, for any fixed c and d, and for a graph G chosen from the set of all (c,d)-regular graphs with n vertices uniformly at random, the first eigenvalue of G is approximately with high probability.

In the construction of a no-linear key-stream generator, self-shrinking is an established way of getting the binary pseudo-random periodic sequences in cryptography design. In this paper, using the theoretical analysis, we mainly study the self-shrinking sequence based on the l-sequence, and the theoretical results reflect its good cryptography properties accurately, such that it has the last period T = pe(p-1)/2 when T is an odd number, and the expected value of its autocorrelation belongs to {0,1/T and the variance is O(T/ln4T). Furthermore, we find that the 2-adic complexity of the self-shrinking sequence based on the l-sequence is large enough to resist the Rational Approximation attack.

Blocking artifacts are introduced in many block-based coding systems, and its reduction can significantly improve the subjective quality of compressed video. The H.264/AVC uses an in-loop deblocking filter to remove the blocking artifacts. The filter considers some coding conditions in its adaptive deblocking filtering such as coded block pattern (CBP), motion vector, macroblock type, etc. for inter-predicted blocks, however, it does not consider much for intra-coded blocks. In this paper, we utilize the human visual system (HVS) characteristic and the local characteristic of image blocks to modify the boundary strength (BS) of the intra-deblocking filter in order to gain improvement in the subjective quality and also to reduce the complexity in filtering intra coded slices. In addition, we propose a low-complexity deblocking method which utilizes the correlation between vertical and horizontal boundaries of a block in inter coded slices. Experimental results show that our proposed method achieves not only significant gain in the subjective quality but also some PSNR gain, and reduces the computational complexity of the deblocking filter by 36.23% on average.

A LNA, an RF front-end and a 6th–order complex BPF for reconfigurable low-IF receivers are demonstrated in this work. Due to the noise cancellation, the two-stage LNA presents a low NF of 2.8 to 3.3 dB from 0.8 to 6 GHz. Moreover, the LNA delivers two kinds of gain curves with IIP3 of -2.6 dBm by employing the capacitive degeneration and the resistive gain-curve shaping in the second stage. The flicker noise corner frequency of the down-converter has been considered and the measured fC of the RF front-end is 200 kHz. The RF front-end also provides two kinds of gain curves. For the low-frequency mode, the conversion gain is 28.831.1 dB from 800 MHz to 2.4 GHz. For the high-frequency mode, the conversion gain is 26.827.4 dB from 3 to 5 GHz. The complex BPF is realized with gm-C LPFs by shifting the low-pass frequency response. With variable transconductances and capacitors, a fixed ratio of the centre frequency to the bandwidth (2) is achieved by varying the bandwidth and the centre frequency of the LPF simultaneously. The complex BPF has a variable bandwidth from 200 kHz to 6.4 MHz while achieving an image rejection of 44 dB.

In this paper we study quantum nondeterminism in multiparty communication. There are three (possibly) different types of nondeterminism in quantum computation: i) strong, ii) weak with classical proofs, and iii) weak with quantum proofs. Here we focus on the first one. A strong quantum nondeterministic protocol accepts a correct input with positive probability and rejects an incorrect input with probability 1. In this work we relate strong quantum nondeterministic multiparty communication complexity to the rank of the communication tensor in the Number-On-Forehead and Number-In-Hand models. In particular, by extending the definition proposed by de Wolf to nondeterministic tensor-rank (nrank), we show that for any boolean function f when there is no prior shared entanglement between the players, 1) in the Number-On-Forehead model the cost is upper-bounded by the logarithm of nrank(f); 2) in the Number-In-Hand model the cost is lower-bounded by the logarithm of nrank(f). Furthermore, we show that when the number of players is o(log log n), we have NQP BQP for Number-On-Forehead communication.

We proposed a method for constructing constant-weight and multi-valued sequences from the cyclic difference sets by generalization of the method in binary case proposed by N. Li, X. Zeng and L. Hu in 2008. In this paper we give some properties about sets of such sequences and it is shown that a set of non-constant-weight sequences over Z4 with length 13 from the (13,4,1)-cyclic difference set, and a set of constant-weight sequences over Z5 with length 21 from the (21,5,1)-cyclic difference set have almost highest linear complexities and good profiles of all sequences' linear complexities. Moreover we investigate the value distribution, the linear complexity and correlation properties of a set of sequences with length 57 over GF(8) from the (57,8,1)-cyclic difference set. It is pointed out that this set also has good value distributions and almost highest linear complexities in similar to previous two sets over Z4 with length 13 and Z5 with length 21.

In this letter we propose a new Whiteman generalized cyclotomic sequence of order 4. Meanwhile, we determine its linear complexity and minimal polynomial. The results show that this sequence possesses both high linear complexity and optimal balance on 1 s and 0 s, which may be attractive for cryptographic applications.

We propose a family of algorithms for efficiently merging on contemporary GPUs, so that each algorithm requires O(m log (+1)) element comparisons, where m and n are the sizes of the input sequences with m ≤ n. According to the lower bounds for merging all proposed algorithms are asymptotically optimal regarding the number of necessary comparisons. First we introduce a parallely structured algorithm that splits a merging problem of size 2l into 2i subproblems of size 2l-i, for some arbitrary i with (0 ≤ i ≤ l). This algorithm represents a merger for i=l but it is rather inefficient in this case. The efficiency is boosted by moving to a two stage approach where the splitting process stops at some predetermined level and transfers control to several parallely operating block-mergers. We formally prove the asymptotic optimality of the splitting process and show that for symmetrically sized inputs our approach delivers up to 4 times faster runtimes than the thrust::merge function that is part of the Thrust library. For assessing the value of our merging technique in the context of sorting we construct and evaluate a MergeSort on top of it. In the context of our benchmarking the resulting MergeSort clearly outperforms the MergeSort implementation provided by the Thrust library as well as Cederman's GPU optimized variant of QuickSort.

Blind source separation (BSS) techniques are required for various signal decomposing issues. Independent component analysis (ICA), assuming only a statistical independence among stochastic source signals, is one of the most useful BSS tools because it does not need a priori information on each source. However, there are many requirements for decomposing multiple deterministic signals such as complex sinusoidal signals with different frequencies. These requirements may include pulse compression or clutter rejection. It has been theoretically shown that an ICA algorithm based on maximizing non-Gaussianity successfully decomposes such deterministic signals. However, this ICA algorithm does not maintain a sufficient separation performance when the frequency difference of the sinusoidal waves becomes less than a nominal frequency resolution. To solve this problem, this paper proposes a super-resolution algorithm for complex sinusoidal signals by extending the maximum likelihood ICA, where the probability density function (PDF) of a complex sinusoidal signal is exploited as a priori knowledge, in which the PDF of the signal amplitude is approximated as a Gaussian distribution with an extremely small standard deviation. Furthermore, we introduce an optimization process for this standard deviation to avoid divergence in updating the reconstruction matrix. Numerical simulations verify that our proposed algorithm remarkably enhances the separation performance compared to the conventional one, and accomplishes a super-resolution separation even in noisy situations.

This letter addresses antenna ordering to improve the performance of the MIMO detectors in [4], where two low complexity MIMO detectors have been proposed based on either fully-connected or ring type pair-wise Markov random field (MRF). The former was shown to be better than the latter, while being more complex. The objective of this letter is to make the performance of the detector based on ring-type MRF (with complexity of O(2M 22m)) close to or better than that of fully-connected MRF (with complexity of O(M (M-1)22m)), by applying appropriate antenna ordering. The simulation results validate the proposed antenna ordering methods.

In time-varying frequency selective channels, to obtain high-rate joint time-frequency diversity, linear dispersion coded orthogonal frequency division multiplexing (LDC-OFDM), has recently been proposed. Compared with OFDM systems, single-carrier systems may retain the advantages of lower PAPR and lower sensitivity to carrier frequency offset (CFO) effects, which motivates this paper to investigate how to achieve joint frequency and time diversity for high-rate single-carrier block transmission systems. Two systems are proposed: linear dispersion coded cyclic-prefix single-carrier modulation (LDC-CP-SCM) and linear dispersion coded zero-padded single-carrier modulation (LDC-ZP-SCM) across either multiple CP-SCM or ZP-SCM blocks, respectively. LDC-SCM may use a layered two-stage LDC decoding with lower complexity. This paper analyzes the diversity properties of LDC-CP-SCM, and provides a sufficient condition for LDC-CP-SCM to maximize all available joint frequency and time diversity gain and coding gain. This paper shows that LDC-ZP-SCM may be effectively equipped with low-complexity minimum mean-squared error (MMSE) equalizers. A lower complexity scheme, linear transformation coded SCM (LTC-SCM), is also proposed with good diversity performance.

Linear complexity profile and correlation measure of order k are important pseudorandomness measures for sequences used in cryptography. We study both measures for a class of binary sequences called Legendre-Sidelnikov sequences. The proofs involve character sums.

Shisen-Sho is a tile-based one-player game. The instance is a set of 136 tiles embedded on 817 rectangular grids. Two tiles can be removed if they are labeled by the same number and if they are adjacent or can be connected with at most three orthogonal line segments. Here, line segments must not cross tiles. The aim of the game is to remove all of the 136 tiles. In this paper, we consider the generalized version of Shisen-Sho, which uses an arbitrary number of tiles embedded on rectangular grids. It is shown that deciding whether the player can remove all of the tiles is NP-complete.

In this letter we design a new family of space-time block codes (STBC) for multi-input multi-output (MIMO) systems. The complex orthogonal STBC achieves full diversity and full transmission rate with fast maximum-likelihood decoding when only two transmit antennas are employed. By combining the Alamouti STBC and the multidimensional signal constellation rotation based on the cyclotomic number field, we construct cyclotomic orthogonal space-time block codes (COSTBCs) which can achieve full diversity and full rate for multiple transmit antennas. Theoretical analysis and simulation results demonstrate excellent performance of the proposed codes, while the decoding complexity is further reduced.

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).

This paper evaluates the delay of the issue queue in a superscalar processor to aid microarchitectural design, where quick quantification of the complexity of the issue queue is needed to consider the tradeoff between clock cycle time and instructions per cycle. Our study covers two aspects. First, we introduce banking tag RAM, which comprises the issue queue, to reduce the delay. Unlike normal RAM, this is not straightforward, because of the uniqueness of the issue queue organization. Second, we explore and identify the correct critical path in the issue queue. In a previous study, the critical path of each component in the issue queue was summed to obtain the issue queue delay, but this does not give the correct delay of the issue queue, because the critical paths of the components are not connected logically. In the evaluation assuming 32-nm LSI technology, we obtained the delays of issue queues with eight to 128 entries. The process of banking tag RAM and identifying the correct critical path reduces the delay by up to 20% and 23% for 4- and 8-issue widths, respectively, compared with not banking tag RAM and simply summing the critical path delay of each component.

A conical area evolutionary algorithm (CAEA) is presented to further improve computational efficiencies of evolutionary algorithms for bi-objective optimization. CAEA partitions the objective space into a number of conical subregions and then solves a scalar subproblem in each subregion that uses a conical area indicator as its scalar objective. The local Pareto optimality of the solution with the minimal conical area in each subregion is proved. Experimental results on bi-objective problems have shown that CAEA offers a significantly higher computational efficiency than the multi-objective evolutionary algorithm based on decomposition (MOEA/D) while CAEA competes well with MOEA/D in terms of solution quality.