Search

Known for their capacity-achieving abilities and low complexity for both encoding and decoding, polar codes have been selected as the control channel coding scheme for 5G communications. To satisfy the needs of high throughput and low latency, belief propagation (BP) is chosen as the decoding algorithm. However, it suffers from worse error performance than that of cyclic redundancy check (CRC)-aided successive cancellation list (CA-SCL). Recently, convolutional neural network-aided bit-flipping (CNN-BF) is applied to BP decoding, which can accurately identify the erroneous bits to achieve a better error rate and lower decoding latency than prior critical-set bit-flipping (CS-BF) mechanism. However, successive BF, having better error correction capability, has not been explored in CNN-BF since the more complicated flipping strategy is out of the scope of supervised learning. In this work, by using imitation learning, a convolutional neural network-aided tree-based multiple-bits BF (CNN-Tree-MBF) mechanism is proposed to explore the benefits of multiple-bits BF. With the CRC information as additional input data, the proposed CNN-BF model can further reduce 5 flipping attempts. Besides, a tree-based flipping strategy is proposed to avoid useless flipping attempts caused by wrongly flipped bits. From the simulation results, our approach can outperform CS-BF and reduce flipping attempts by 89% when code length is 64, code rate is 0.5 and SNR is 1 dB. It also achieves a comparable block error rate (BLER) as CA-SCL. [ABSTRACT FROM AUTHOR]

The conventional model of disjunctive group testing assumes that there are several defective elements (or defectives) among a large population, and a group test yields the positive response if and only if the testing group contains at least one defective element. The basic problem is to find all defectives using a minimal possible number of group tests. However, when the number of defectives is unknown there arises an additional problem, namely: how to estimate the random number of defective elements. In this paper, we concentrate on testing the hypothesis $H_0$ : the number of defectives $\leq s_1$ against the alternative hypothesis $H_1$ : the number of defectives $\geq s_2$. We introduce a new decoding algorithm based on the comparison of the number of tests having positive responses with an appropriate fixed threshold. For some asymptotic regimes on $s_1$ and $s_2$ , the proposed algorithm is shown to be order-optimal. Additionally, our simulation results verify the advantages of the proposed algorithm such as low complexity and a small error probability compared with known algorithms. [ABSTRACT FROM AUTHOR]

Vector perturbation (VP) precoding is a promising technique for multiuser communication systems operating in the downlink. In this work, we introduce a hybrid framework to improve the performance of lattice reduction (LR) aided precoding in VP. First, we perform a simple precoding using zero forcing (ZF) or successive interference cancellation (SIC) based on a reduced lattice basis. Since the signal space after LR-ZF or LR-SIC precoding can be shown to be bounded to a small range, then along with sufficient orthogonality of the lattice basis guaranteed by LR, they collectively pave the way for the subsequent application of an approximate message passing (AMP) algorithm, which further boosts the performance of any suboptimal precoder. Our work shows that the AMP algorithm can be beneficial for a lattice decoding problem whose data symbols lie in integers $\mathbb {Z}$ and entries of the lattice basis may not be i.i.d. Gaussian. Numerical results confirm that the low-complexity AMP algorithm can improve the symbol error rate performance of LR-aided precoding significantly. Finally, the hybrid scheme is also proven effective when solving the data detection problem of massive MIMO systems without using LR. [ABSTRACT FROM AUTHOR]

We consider a problem of localizing a temporal path signal that evolves over time on a graph. A path signal represents the trajectory of a moving agent on a graph in a series of consecutive time stamps. Through combining dynamic programing and graph partitioning, we propose a path-localization algorithm with significantly reduced computational complexity. To analyze the localization performance, we use two evaluation metrics to quantify the localization error: the Hamming distance and the destination's distance between the ground-truth path and the estimated path. In random geometric graphs, we provide a closed-form expression for the localization error bound, and a tradeoff between localization error and the computational complexity. Finally, we compare the proposed technique with the maximum likelihood estimate in terms of computational complexity and localization error, and show significant speedup (100×) with comparable localization error (4×) on a graph from real data. [ABSTRACT FROM AUTHOR]

The successive cancellation list (SCL) decoding is the most powerful decoding algorithm for polar codes. However, the long latency makes it unsuitable for practical applications, and thus many algorithms have been presented to resolve the problem. While most of the previous algorithms have reduced the latency by pruning unnecessary operations in the middle of the process, this paper proposes an early stopping criterion. The proposed method can determine the minimum metric path without having to traverse the tree to the end if a special condition is satisfied at a certain point. The remaining bits located after the stopped bit position are decoded directly from the soft information. The simulation results show that the criterion reduces the decoding latency effectively for various code rates and list sizes without any performance loss. We also propose a hardware architecture that is efficient in realizing the proposed method. Compared to previous SCL decoding algorithms, the proposed decoder achieves 16% higher throughput and 12% improved area efficiency at an SNR of 5.0 dB when the list size is 4. [ABSTRACT FROM AUTHOR]

This contribution considers the non-Bayesian Cramér-Rao bound (CRB) related to parameter estimation from a linearly modulated signal observed in additive white Gaussian noise. We compare the exact CRB expression for coded modulation with two ad hoc CRB (ACRB) expressions; the first ACRB is obtained by substituting in the exact CRB expression for uncoded modulation the a priori symbol probabilities by the extrinsic symbol probabilities; the second ACRB, which has received some attention in recent scientific publications, additionally assumes that the real and imaginary parts of the symbols are independent. Our exposition focuses on the particular case of phase shift estimation. By means of examples we show that although for some coded modulation schemes the exact and ACRBs yield virtually the same numerical result, for other coded modulation schemes the ACRBs differ considerably among themselves and from the exact CRB. We provide some explanations for this behavior. We also argue that both ACRBs are expected to virtually coincide with the exact CRB in the case of bit-interleaved coded modulation combined with a rectangular constellations with independent in-phase and quadrature mapping and a binary code for which the factor graph does not contain short cycles. [ABSTRACT FROM AUTHOR]

As a branch of sphere decoding, the K-best method has played an important role in detection in large-scale multipleinput- multiple-output (MIMO) systems. However, as the numbers of users and antennas grow, the preprocessing complexity increases significantly, which is one of the major issues with the K-best method. To address this problem, this paper proposes a preprocessing algorithm combining Cholesky sorted QR decomposition and partial iterative lattice reduction (CHOSLAR) for K-best detection in a 64-quadrature amplitude modulation (QAM) 16 × 16 MIMO system. First, Cholesky decomposition is conducted to perform sorted QR decomposition. Compared with conventional sorted QR decomposition, this method reduces the number of multiplications by 25.1% and increases parallelism. Then, a constant-throughput partial iterative lattice reduction method is adopted to achieve near-optimal detection accuracy. This method further increases parallelism, reduces the number of matrix swaps by 45.5%, and reduces the number of multiplications by 67.3%. Finally, a sortingreduced K-best strategy is used for vector estimation, thereby, reducing the number of comparators by 84.7%. This method suffers an accuracy loss of only approximately 1.44 dB compared with maximum likelihood detection. Based on CHOSLAR, this paper proposes a fully pipelined very-large-scale-integration architecture. A series of different systolic arrays and parallel processing units achieves an optimal tradeoff among throughput, area consumption, and power consumption. This architectural layout is obtained via TSMC 65-nm 1P9M CMOS technology, and throughput metrics of 1.40 Gbps/W (throughput/power) and 0.62 Mbps/kG (throughput/area) are achieved, demonstrating that the proposed system is much more efficient than state-of-the-art designs. [ABSTRACT FROM AUTHOR]

We consider a distributed parameter estimation problem, in which multiple terminals send messages related to their local observations using limited rates to a fusion center which obtains an estimate of a parameter related to the observations of all terminals. It is well known that if the transmission rates are in the Slepian–Wolf region, the fusion center can fully recover all observations and hence can construct an estimator having the same performance as that of the centralized case. One natural question is whether Slepian–Wolf rates are necessary to achieve the same estimation performance as that of the centralized case. In this paper, we show that the answer to this question is negative. We establish our result by explicitly constructing an asymptotically minimum variance unbiased estimator that has the same performance as that of the optimal estimator in the centralized case while using information rates less than the conditions required in the Slepian–Wolf rate region. The key idea is that, instead of aiming to recover the observations at the fusion center, we design universal schemes enabling the fusion center to compute a sufficient statistic using rates outside of the Selpian–Wolf region. [ABSTRACT FROM PUBLISHER]

Polar codes are of great interests because they provably achieve the symmetric capacity of discrete memoryless channels with arbitrary input alphabet sizes while having an explicit construction. Most existing decoding algorithms of polar codes are based on bit-wise hard or soft decisions. In this paper, we propose symbol-decision successive cancellation (SC) and successive cancellation list (SCL) decoders for polar codes, which use symbol-wise hard or soft decisions for higher throughput or better error performance. First, we propose to use a recursive channel combination to calculate symbol-wise channel transition probabilities, which lead to symbol decisions. Our proposed recursive channel combination has lower complexity than simply combining bit-wise channel transition probabilities. The similarity between our proposed method and Arıkan's channel transformations also helps to share hardware resources between calculating bit- and symbol-wise channel transition probabilities. Second, a two-stage list pruning network is proposed to provide a trade-off between the error performance and the complexity of the symbol-decision SCL decoder. Third, since memory is a significant part of SCL decoders, we propose a pre-computation memory-saving technique to reduce memory requirement of an SCL decoder. Finally, to evaluate the throughput advantage of our symbol-decision decoders, we design an architecture based on a semi-parallel successive cancellation list decoder. In this architecture, different symbol sizes, sorting implementations, and message scheduling schemes are considered. Our synthesis results show that in terms of area efficiency, our symbol-decision SCL decoders outperform existing bit-decision and multi-bit SCL decoders. [ABSTRACT FROM PUBLISHER]

This paper studies and analyzes a multi-pair MIMO two-way relay (TWR) system from a principal-angle perspective. In this system, users are grouped into pairs and two users in each pair exchange information through a common relay. The transmission scheme consists of two phases. In the uplink phase, the relay’s receive signal space is divided into two subspaces for each pair: in one subspace, the signals of the two users are near-parallel, and physical-layer network coding (PNC) decoding is applied to retrieve network-coded messages; in the other subspace, the two user signals are near-orthogonal, and complete decoding (CD) is applied to retrieve individual user messages. In the downlink phase, the relay’s transmit signal space is split into orthogonal subspaces for each pair, and in each subspace a common message is broadcasted to the two users. Our main contribution is to establish a critical link between the transmission scheme and the concept of principal angle in linear algebra. In particular, principal angle quantizes the degree of orthogonality between the user signals and helps determining how to partition the relay’s receive signal space into PNC decoding subspace and CD decoding subspace. Building on that, we discuss the optimal design of user/relay precoders for both uplink and downlink phases to maximize the asymptotic sum-rate of the proposed scheme at high signal-to-noise ratio (SNR). The analysis and numerical results indicate that our scheme performs close to the cut-set outer bound and significantly outperforms the existing schemes in the literature. [ABSTRACT FROM AUTHOR]

For Gaussian multiple-input multiple-output (MIMO) relay channels with partial decode-and-forward, the optimal type of input distribution is still an open question in general. Recent research has revealed that in some other scenarios with unknown optimal input distributions (e.g., interference channels), improper (i.e., noncircular) Gaussian distributions can outperform proper (circular) Gaussian distributions. In this paper, we show that this is not the case for partial decode-and-forward in the Gaussian MIMO relay channel with Gaussian transmit signals, i.e., we show that a proper Gaussian input distribution is the optimal one among all Gaussian distributions. In order to prove this property, an innovation covariance matrix is introduced, and a decomposition is performed by considering the optimization over this matrix as an outer problem. A key point for showing optimality of proper signals then is a reformulation that reveals that one of the subproblems is equivalent to a sum rate maximization in a two-user MIMO broadcast channel under a sum covariance constraint, for which the optimality of proper signals can be shown. [ABSTRACT FROM PUBLISHER]

Polar codes have recently received a lot of attention because of their capacity-achieving performance and low encoding and decoding complexity. The performance of the successive cancellation decoder (SCD) of the polar codes highly depends on that of the partial-sum network (PSN) implementation. Hence, in this work, an efficient PSN architecture is proposed, based on the properties of polar codes. First, a new partial-sum updating algorithm and the corresponding PSN architecture are introduced which achieve a delay performance independent of the code length. Moreover, the area complexity is also reduced. Second, for a high-performance and area-efficient semi-parallel SCD implementation, a folded PSN architecture is presented to integrate seamlessly with the folded processing element architecture. This is achieved by using a novel folded decoding schedule. As a result, both the critical path delay and the area (excluding the memory for folding) of the semi-parallel SCD are approximately constant for a large range of code lengths. The proposed designs are implemented in both FPGA and ASIC and compared with the existing designs. Experimental result shows that for polar codes with large code length, the decoding throughput is improved by more than 1.05 times and the area is reduced by as much as 50.4%, compared with the state-of-the-art designs. [ABSTRACT FROM PUBLISHER]

Delta-sigma (\Delta \Sigma) A/D conversion is a popular technique used to achieve high resolution data conversion for low to moderate bandwidth applications. It is commonly accepted that the digital circuitry of the \Delta \Sigma A/D converters should perform a linear time-invariant (LTI) filtering on the output of the \Delta \Sigma modulator in order to reconstruct the input signal. However, it has been shown that, when higher order \Delta \Sigma A/D converters are operated at higher oversampling ratios (OSRs), non-linear reconstruction algorithms extract more information about the input signal than LTI methods. Still, use of non-linear algorithms has been limited due to their complexity and stability issues. Two practical non-linear methods presented in the literature are fast projection onto convex sets (POCS) and direct projection (DP). In this work, we show that the non-linear reconstruction process for \Delta \Sigma modulated sequences can be treated as a linear feasibility problem (LFP). We then show that if the reconstruction process is defined as an LFP, its implementation is less complex than in the case of the DP method. We further describe how the LFP can be well-conditioned and demonstrate the reconstruction process by using the surrogate constraint algorithm with random constraint selection. The described algorithm considers a small number of constraints at a time, which makes it suitable for serial implementation. [ABSTRACT FROM AUTHOR]

In this paper, we investigate a relay-assisted resource sharing scenario, namely, multi-operator two-way relaying with a MIMO amplify-and-forward (AF) relay. Here, the spectrum and the relay (infrastructure) are shared among multiple operators. We develop the projection based separation of multiple operators (ProBaSeMo) relay transmit strategy, which is inspired by the block diagonalization (BD) and regularized block diagonalization (RBD) schemes that are space-division multiple access (SDMA) approaches for multi-user MIMO systems. If the user terminals are equipped with multiple antennas, appropriate precoding and decoding matrix designs are also proposed. Compared to the time-shared approach where the relay is used by different operators in a time division multiple access (TDMA) manner, we demonstrate that the ProBaSeMO algorithms can provide a significant sharing gain in terms of the sum rate with many antennas at the relay or in the high SNR regime in a two-operator case. For a fixed number of antennas at the relay, an even higher sharing gain can be obtained if the number of operators increases. [ABSTRACT FROM PUBLISHER]

Maximum likelihood soft-decision decoding of linear block codes is addressed in this correspondence. A novel algorithm based on Chase-2 algorithm for the decoding of systematic binary block codes is detailed. A double re-encoding technique in place of the classical algebraic decoding for the computation of the candidate codeword list is the major innovation of the proposed algorithm. This approach has been successfully applied to systematic block codes that have a code rate equal to 1/2 and a parity check matrix composed of an invertible submatrix for the redundancy part. Simulation results show performance close to the optimum maximum likelihood decoding for an excellent tradeoff between BER performance and computational complexity. Then, the challenging issue of designing a decoder for a specific family of short binary block codes, called Cortex codes is also described. Three soft decoders for Cortex codes with lengths equal to 32, 64, and 128 and a code rate equal to 1/2 have been designed. Then, all the decoders were successively implemented onto an field-programmable gate array (FPGA) device. To our knowledge, they are the first efficient digital implementations of Cortex codes. [ABSTRACT FROM PUBLISHER]

The finite rate of innovation (FRI) principle is developed for sampling a class of non-bandlimited signals that have a finite number of degrees of freedom per unit of time, i.e., signals with FRI. This sampling scheme is later extended to three classes of sampling kernels with compact support and applied to the step edge reconstruction problem by treating the image row by row. In this paper, we regard step edges as 2D FRI signals and reconstruct them block by block. The step edge parameters are obtained from the 2D moments of a given image block. Experimentally, our technique can reconstruct the edge more precisely and track the Cramér–Rao bounds (CRBs) closely with a signal-to-noise ratio (SNR) larger than 4 dB on synthetic step edge images. Experiments on real images show that our proposed method can reconstruct the step edges under practical conditions, i.e., in the presence of various types of noise and using a real sampling kernel. The results on locating the corners of data matrix barcodes using our method also outperform some state-of-the-art barcode decoders. [ABSTRACT FROM AUTHOR]

We consider the problem of training a discriminative classifier given a set of labelled multivariate time series (a.k.a. multichannel signals or vector processes). We propose a novel kernel function that exploits the spectral information of tensors of fourth-order cross-cumulants associated to each multichannel signal. Contrary to existing approaches the arising procedure does not require an (often nontrivial) blind identification step. Nonetheless, insightful connections with the dynamics of the generating systems can be drawn under specific modeling assumptions. The method is illustrated on both synthetic examples as well as on a brain decoding task where the direction, either left of right, towards where the subject modulates attention is predicted from magnetoencephalography (MEG) signals. Kernel functions for unstructured data do not leverage the underlying dynamics of multichannel signals. A comparison with these kernels as well as with state-of-the-art approaches, including generative methods, shows the merits of the proposed technique. [ABSTRACT FROM AUTHOR]

We describe the channel equalization problem, and its prior estimate of the channel state information (CSI), as a joint Bayesian estimation problem to improve each symbol posterior estimates at the input of the channel decoder. Our approach takes into consideration not only the uncertainty due to the noise in the channel, but also the uncertainty in the CSI estimate. However, this solution cannot be computed in linear time, because it depends on all the transmitted symbols. Hence, we also put forward an approximation for each symbol's posterior, using the expectation propagation algorithm, which is optimal from the Kullback–Leibler divergence viewpoint and yields an equalization with a complexity identical to the BCJR algorithm. We also use a graphical model representation of the full posterior, in which the proposed approximation can be readily understood. The proposed posterior estimates are more accurate than those computed using the ML estimate for the CSI. In order to illustrate this point, we measure the error rate at the output of a low-density parity-check decoder, which needs the exact posterior for each symbol to detect the incoming word and it is sensitive to a mismatch in those posterior estimates. For example, for QPSK modulation and a channel with three taps, we can expect gains over 0.5 dB with same computational complexity as the ML receiver. [ABSTRACT FROM AUTHOR]

In this paper, for robust and efficient transmission of multiple correlated sources over noisy channels with packet loss, a channel optimized distributed multiple description vector quantization (CDMD) scheme is presented. The proposed CDMD scheme enjoys low-complexity encoding and delay and a scalable CDMD decoder, which jointly reconstructs the symbols of an arbitrary number of correlated sources. This, for example, suits data-gathering applications in wireless sensor networks. The CDMD encoder is designed using a deterministic annealing approach based on a minimum mean squared error asymmetric CDMD. A CDMD decoder for asymmetric distributed source coding is presented, which takes into account the side information, as well as channel noise and packet loss. Two types of iterative symmetric CDMD decoders, namely the estimated-SI and the soft-SI decoders, are presented, which respectively exploit the reconstructed symbols and a posteriori probabilities of other sources as SI in iterations. In a multiple-source CDMD setting, for reconstruction of a source, three methods are proposed to select another source as its SI during the decoding. The methods operate based on minimum physical distance, maximum mutual information, and minimum end-to-end distortion. The performance of the proposed systems and algorithms are evaluated and compared in detail. [ABSTRACT FROM AUTHOR]

In this paper, we propose and analyze a generalized construction of distributed network codes for a network consisting of M users sending independent information to a common base station through independent block fading channels. The aim is to increase the diversity order of the system without reducing its throughput. The proposed scheme, called generalized dynamic-network codes (GDNC), is a generalization of the dynamic-network codes (DNC) recently proposed by Xiao and Skoglund. The design of the network codes that maximize the diversity order is recognized as equivalent to the design of linear block codes over a nonbinary finite field under the Hamming metric. We prove that adopting a systematic generator matrix of a maximum distance separable block code over a sufficiently large finite field as the network transfer matrix is a sufficient condition for full diversity order under link failure model. The proposed generalization offers a much better tradeoff between rate and diversity order compared to the DNC. An outage probability analysis showing the improved performance is carried out, and computer simulations results are shown to agree with the analytical results. [ABSTRACT FROM PUBLISHER]