Search

The combined effects of multi-user interference and correlated fading on the interference-unaware transceiver (IUT), which performs transformations in both the transmitter and the receiver without the interference knowledge, are studied. We show that for IUT under multi-user interference, receive correlated fading can have no impact on the achievable rate and the achievable rate can be increased with the increase in the correlations of the interference's transmit correlated fading. Furthermore, we show that even if there is transmit correlated fading, the achievable rate of IURT can converge to the interference-free MIMO channel capacity as the number of receive antennas increases and the required number of receive antennas for becoming interference free can be decreased by transmit correlated fading. [ABSTRACT FROM AUTHOR]

The maximum likelihood decoding problem (MLD) is known to be NP-hard and its complexity is strictly related to the security of some post-quantum cryptosystems, that is, the so-called code-based primitives. Analogously, the multivariate quadratic system problem (MQ) is NP-hard and its complexity is necessary for the security of the so-called multivariate-based primitives. In this paper we present a closed formula for a polynomial-time reduction from any instance of MLD to an instance of MQ, and viceversa. We also show a polynomial-time isomorphism between MQ and MLD, thus demonstrating the direct link between the two post-quantum cryptographic families. [ABSTRACT FROM AUTHOR]

A novel permuted fast successive-cancellation list decoding algorithm with fast Hadamard transform (FHT-FSCL) is presented. The proposed decoder initializes $L$ $(L\geq 1)$ active decoding paths with $L$ random codeword permutations sampled from the full symmetry group of the codes. The path extension in the permutation domain is carried out until the first constituent RM code of order 1 is visited. Conventional path extension of the successive-cancellation list decoder is then utilized in the information bit domain. The simulation results show that for a RM code of length 512 with 46 information bits, by running 20 parallel permuted FHT-FSCL decoders with $L=4$ , we reduce 72% of the computational complexity, 22% of the decoding latency, and 84% of the memory consumption of the state-of-the-art simplified successive-cancellation decoder that uses 512 permutations sampled from the full symmetry group of the code, with similar error-correction performance at the target frame error rate of $10^{-4}$. [ABSTRACT FROM AUTHOR]

A novel recursive list decoding (RLD) algorithm for Reed-Muller (RM) codes based on successive permutations (SP) of the codeword is presented. A low-complexity SP scheme applied to a subset of the symmetry group of RM codes is first proposed to carefully select a good codeword permutation on the fly. Then, the proposed SP technique is integrated into an improved RLD algorithm that initializes different decoding paths with random codeword permutations, which are sampled from the full symmetry group of RM codes. Finally, efficient latency and complexity reduction schemes are introduced that virtually preserve the error-correction performance of the proposed decoder. Simulation results demonstrate that at the target frame error rate of 10−3 for the RM code of length 256 with 163 information bits, the proposed decoder reduces 6% of the computational complexity and 22% of the decoding latency of the state-of-the-art semi-parallel simplified successive-cancellation decoder with fast Hadamard transform (SSC-FHT) that uses 96 permutations from the full symmetry group of RM codes, while relatively maintaining the error-correction performance and memory consumption of the semi-parallel permuted SSC-FHT decoder. [ABSTRACT FROM AUTHOR]

The successive cancellation (SC) process in which symbols are decoded sequentially by processing some intermediate information is an essential component of various decoding algorithms used for polar codes and their variants. In some decoding schemes, we may need to redo this process from some specific symbol or from the first symbol. This operation is called rewinding. Rewinding the SC process seems trivial if we have access to all intermediate log-likelihood ratios (LLRs) and partial sums. However, as the block length increases, retaining all of the intermediate information becomes inefficient and impractical. Rewinding the SC process in a memory-efficient way is a problem that we address in this paper. As we store a fraction of all the intermediate information in the memory-efficient scheme, we may not be able to rewind the SC process to the target symbol index. The reason is that some of the stored intermediate information needed to decode the target symbol may have been overwritten. To recompute the lost information, we may need to rewind the process further. Before proposing the formal scheme for the rewinding process, we explore the known properties of the SC process based on the binary representation of the bit indices. Then, we introduce a new operator used for grouping the bit indices. This special grouping helps us in finding the closest bit index to the target index for rewinding. We also analytically prove that this approach gives access to the untouched intermediate information stored in the memory which is essential in resuming the SC process. Finally, we adapt the proposed approach to multiple rewinds and apply it to SC-flip decoding and shifted-pruning-based list decoding. The numerical evaluation of the proposed solution shows a significant reduction of ≥50% in the complexity of the additional decoding attempts at medium and high SNR regimes for SC-flip decoding and less for shifted-pruning based list decoding. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new linear-equation ordered-statistics decoding (LE-OSD). Unlike the OSD, LE-OSD uses high reliable parity bits rather than information bits to recover codeword estimates, which is equivalent to solving a system of linear equations (SLE). Only test error patterns (TEPs) that create feasible SLEs, referred to as the valid TEPs, are used to obtain codeword estimates. We introduce several constraints on the Hamming weight of TEPs to limit the overall decoding complexity. Furthermore, we analyze the block error rate (BLER) and the computational complexity of the proposed approach. It is shown that LE-OSD has a similar performance to OSD in terms of BLER, which can asymptotically approach Maximum-likelihood (ML) performance with proper parameter selections. Simulation results demonstrate that the LE-OSD has a significantly reduced complexity compared to OSD, especially for low-rate codes, that usually require high decoding order in OSD. Nevertheless, the complexity reduction can also be observed for high-rate codes. In addition, we further improve LE-OSD by applying the decoding stopping condition and the TEP discarding condition. As shown by simulations, the improved LE-OSD has a considerably reduced complexity while maintaining the BLER performance, compared to the latest OSD approaches from literature. [ABSTRACT FROM AUTHOR]

The binary primitive BCH codes are cyclic and are constructed by choosing a subset of the cyclotomic cosets. Which subset is chosen determines the dimension, the minimum distance and the weight distribution of the BCH code. We construct possible BCH codes and determine their coderate, true minimum distance and the non-equivalent codes. A particular choice of cyclotomic cosets gives BCH codes which are, extended by one bit, equivalent to Reed-Muller codes, which is a known result from the sixties. We show that BCH codes have possibly better parameters than Reed-Muller codes, which are related in recent publications to polar codes. We study the decoding performance of these different BCH codes using information set decoding based on minimal weight codewords of the dual code. We show that information set decoding is possible even in case of a channel without reliability information since the decoding algorithm inherently calculates reliability information. Different BCH codes of the same rate are compared and different decoding performances and complexity are observed. Some examples of hard decision decoding of BCH codes have the same decoding performance as maximum likelihood decoding. All presented decoding methods can possibly be extended to include reliability information of a Gaussian channel for soft decision decoding. We show simulation results for soft decision list information set decoding and compare the performance to other methods. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of relaying a single bit of information across a series of binary symmetric channels, and the associated trade-off between the number of hops $m$ , the transmission time $n$ , and the error probability. We introduce a simple, efficient, and deterministic protocol that attains positive information velocity (i.e., a non-vanishing ratio $\frac {m}{n}$ and small error probability) and is significantly simpler than existing protocols that do so. In addition, we characterize the optimal low-noise and high-noise scaling laws of the information velocity, and we adapt our 1-bit protocol to transmit $k$ bits over $m$ hops with $\mathcal {O}(m+k)$ transmission time. [ABSTRACT FROM AUTHOR]

The problem of maximum likelihood decoding with a neural decoder for error-correcting code is considered. It is shown that the neural decoder can be improved with two novel loss terms on the node’s activations. The first loss term imposes a sparse constraint on the node’s activations. Whereas, the second loss term tried to mimic the node’s activations from a teacher decoder which has better performance. The proposed method has the same run time complexity and model size as the neural Belief Propagation decoder, while improving the decoding performance by up to $1.1dB$ on BCH codes. [ABSTRACT FROM AUTHOR]

In this letter, we introduce a class of improved DC-free 4B6B codes in terms of error correction capabilities for a serially concatenated architecture. There are billions of different codebooks that can be derived from the 16 codewords contained in the traditional 4B6B code as per the IEEE 802.15.7 standard for visible light communication (VLC). These codebooks can be classified based on distances properties which determine their error correction performances. The traditional 4B6B code is suitable for hard-decision decoding, however, when a soft decoder is used like in a serially concatenated architecture, that code becomes obsolete. Simulations show that the proposed 4B6B code concatenated with forward error correction (FEC) codes, has better performance compared to state-of-the-art schemes such as the original 4B6B code, the enhanced Miller code, the Manchester code, the 5B10B code and the (0,4) 2/3 RLL code.

In this letter we propose a novel framework for designing decoders, for Low-Density Parity Check (LDPC) codes, that surpasses the frame error rate performance of Belief-Propagation (BP) decoding on binary symmetric channels. Its key component is the adaptation method, based on the genetic optimization algorithm, that is incorporated into the recently proposed Gradient Descent Bit-Flipping Decoding with Momentum (GDBF-w/M). We show that the resulting decoder outperforms all state-of-the-art probabilistic bit-flipping decoders and, additionally, it can be trained to perform beyond BP decoding, which is verified by numerical examples that include codes used in IEEE 802.3an and 5GNR standards. The proposed framework provides a systematic method for decoder optimization without requiring knowledge of trapping sets. Moreover, it is applicable to both regular and irregular LDPC codes. [ABSTRACT FROM AUTHOR]

Model complexity plays an essential role in its selection, namely, by choosing a model that fits the data and is also succinct. Two-part codes and the minimum description length have been successful in delivering procedures to single out the best models, avoiding overfitting. In this work, we pursue this approach and complement it by performing further assumptions in the parameter space. Concretely, we assume that the parameter space is a smooth manifold, and by using tools of Riemannian geometry, we derive a sharper expression than the standard one given by the stochastic complexity, where the scalar curvature of the Fisher information metric plays a dominant role. Furthermore, we compute a sharper approximation to the capacity for exponential families and apply our results to derive optimal dimensional reduction in the context of principal component analysis. [ABSTRACT FROM AUTHOR]

This work identifies information-theoretic quantities that are closely related to the required list size on average for successive cancellation list (SCL) decoding to implement maximum-likelihood decoding over general binary memoryless symmetric (BMS) channels. It also provides upper and lower bounds for these quantities that can be computed efficiently for very long codes. For the binary erasure channel (BEC), we provide a simple method to estimate the mean accurately via density evolution. The analysis shows how to modify, e.g., Reed-Muller codes, to improve the performance when practical list sizes, e.g., $L\in {[{8, 1024}]}$ , are adopted. Exemplary constructions with block lengths $N\in \{128,512\}$ outperform polar codes of 5G over the binary-input additive white Gaussian noise channel. It is further shown that there is a concentration around the mean of the logarithm of the required list size for sufficiently large block lengths, over discrete-output BMS channels. We provide the probability mass functions (p.m.f.s) of this logarithm, over the BEC, for a sequence of the modified RM codes with an increasing block length via simulations, which illustrate that the p.m.f.s concentrate around the estimated mean. [ABSTRACT FROM AUTHOR]

It is well known that for Gaussian channels, a nearest neighbor decoding rule, which seeks the minimum Euclidean distance between a codeword and the received channel output vector, is the maximum likelihood solution and hence capacity-achieving. Nearest neighbor decoding remains a convenient and yet mismatched solution for general channels, and the key message of this paper is that the performance of nearest neighbor decoding can be improved by generalizing its decoding metric to incorporate channel state dependent output processing and codeword scaling. Using generalized mutual information, which is a lower bound to the mismatched capacity under independent and identically distributed codebook ensemble, as the performance measure, this paper establishes the optimal generalized nearest neighbor decoding rule, under Gaussian channel input. Several restricted forms of the generalized nearest neighbor decoding rule are also derived and compared with existing solutions. The results are illustrated through several case studies for fading channels with imperfect receiver channel state information and for channels with quantization effects. [ABSTRACT FROM AUTHOR]

In this paper, we focus on decoding nonbinary low-density parity-check (LDPC) codes in Galois fields of characteristic two via the proximal alternating direction method of multipliers (proximal-ADMM). By exploiting Flanagan/Constant-Weighting embedding techniques and the decomposition technique based on three-variables parity-check equations, two efficient proximal-ADMM decoders for nonbinary LDPC codes are proposed. We show that both of them are theoretically guaranteed convergent to some stationary point of the decoding model and either of their computational complexities in each proximal-ADMM iteration scales linearly with LDPC code’s length and the size of the considered Galois field. Moreover, the decoder based on the Constant-Weight embedding technique satisfies the favorable property of codeword symmetry. Simulation results demonstrate their effectiveness in comparison with state-of-the-art LDPC decoders. [ABSTRACT FROM AUTHOR]

A quadrature spatial modulation with the fourth order transmit diversity (FO-QSM) scheme is presented in this paper. In this scheme, two dispersion-matrix (DM) sets are assigned at the transmitter, and $P$ out of $Q$ DMs are activated in each set to extend the real and imaginary parts of $P$ QSM signals respectively, to large number of transmit antennas. The two DM sets are constructed by performing Kronecker product between two simple extension matrices and the DMs of Sezginer-Sari-Biglieri (SSB) code. The framework designs of FO-QSM and the two DM sets make FO-QSM possess the properties: 1) it guarantees the fourth order transmit diversity without requiring any parameter optimization; 2) it has higher spectral efficiency than the newly proposed generalized space-time block coded spatial modulation (GSTBC-SM) scheme. Furthermore, a repeated computation reduced sphere decoding (RCR-SD) is proposed. RCR-SD is very suitable for the schemes constructed by a large number of DMs, including FO-QSM. By sorting the index vectors, the RCR-SD detector can efficiently reduce the repeated computations in the SD searching, which significantly reduces the decoding complexity without sacrificing optimal decoding performance. Simulation results show that FO-QSM has obvious better bit error rate (BER) performance than GSTBC-SM. [ABSTRACT FROM AUTHOR]

This paper presents an alternative approach to real-valued signal representation and proposes an improved successive interference cancellation (SIC)-based detection scheme using the alternative signal representation for non-uniform constellations (NUCs) in Advanced Television Systems Committee (ATSC) 3.0. Since I/Q polarization interleaving in ATSC 3.0 multiple-input multiple-output (MIMO) precoding performs a non-linear operation, it makes it difficult to use conventional suboptimal detection schemes based on interference cancellation. Therefore, the alternative signal representation is designed to easily apply various suboptimal detection schemes. Further, to obtain more robustness and lower complexity, a suboptimal detection scheme based on the alternative signal representation and interference cancellation with QR decomposition is proposed. The proposed detection scheme exploits the structural properties of NUCs and jointly detects the real and imaginary parts as a block. In addition, by considering one or more candidate symbols in the interference cancellation for the proposed detection scheme, the performance and the complexity are trade-offs according to the number of the considering candidate symbols. Simulation results show that the proposed detection scheme with a slight increase of the complexity significantly outperforms a linear detection under fixed and mobile channels. [ABSTRACT FROM AUTHOR]

Massive multiple-input multiple-output (mMIMO) is a promising technique to realize the ever-increasing demand for high-speed data, quality of service (QoS), and energy efficiency for 5G and beyond wireless systems. However, the increased number of users in mMIMO systems significantly affects performance of the existing approximate matrix inversion based and matrix inversion less iterative symbol detection techniques. Conventional detection algorithms cannot learn the inter-relations of input-output parameters based on available data without having specific mathematical models of communication scenarios. Moreover, existing deep learning (DL) based symbol detection models lack in-network compression, resulting in large training time and high computational load while expected to be deployed in a low latency communication system. In this article, a sparse refinement architecture is proposed for symbol detection in uplink mMIMO. The proposed DL architecture requires less trainable parameters as compared to a conventional fully connected detection network and refines the estimated symbol vector in each layer. Convergence of the proposed symbol detection technique is analytically justified. An expression for the approximate upper bound on the BER is derived which is supported by simulations. The obtained results prove viability of the proposed symbol detection model as compared to the several existing state-of-art uplink mMIMO detection techniques, in terms of superior the error performance and low computational complexity. [ABSTRACT FROM AUTHOR]

Spinal codes are a new family of rateless codes which have been proved to be capacity-achieving over both the additive white Gaussian noise (AWGN) channel and the binary symmetric channel (BSC). However, over the Rayleigh fading channel between the vehicle nodes, the error performance of Spinal codes is not satisfactory since the tail message blocks of Spinal codes are prone to error. To solve this issue, this paper proposes a new practical partial self-concatenation coding structure of Spinal codes, named $N$ tail-protected Spinal codes, to pointedly protect tail message blocks of Spinal codes over the flat Rayleigh fading channel. Theoretical performance analysis and simulation results are also provided to validate and verify the effectiveness of the proposed $N$ tail-protected Spinal codes. [ABSTRACT FROM AUTHOR]

While many communications media, such as wireless and certain classes of wireline channels, typically lead to bursty errors, most decoders are designed assuming memoryless channels. Consequently, communication systems generally rely on interleaving over tens of thousands of bits to match decoder assumptions. Even for short high rate codes, awaiting sufficient data in interleaving and de-interleaving is a significant source of unwanted latency. We construct an extension to the recently proposed Guessing Random Additive Noise Decoding (GRAND) algorithm, which we call GRAND-MO for GRAND Markov Order. By foregoing interleaving and instead making use of the bursty nature of noise, low-latency communication is possible with block error rates outperforming their interleaved counterparts by a substantial margin. We establish that certain well-known binary codes with structured code-word patterns are ill-suited for use in bursty channels, but Random Linear Codes (RLCs) prove robust to correlated noise. We further demonstrate that by operating directly on modulated symbols rather than de-mapped bits, GRAND-MO achieves further performance and complexity gains by exploiting information that is lost in demodulation. As a result, GRAND-MO provides one potential solution for applications that require ultra-reliable low latency communication. [ABSTRACT FROM AUTHOR]

We consider the concatenation of a convolutional code (CC) with an optimized cyclic redundancy check (CRC) code as a promising paradigm for good short blocklength codes. The resulting CRC-aided convolutional code naturally permits the use of serial list Viterbi decoding (SLVD) to achieve maximum-likelihood decoding. The convolutional encoder of interest is of rate- $1/\omega $ and the convolutional code is either zero-terminated (ZT) or tail-biting (TB). The resulting CRC-aided convolutional code is called a CRC-ZTCC or a CRC-TBCC. To design a good CRC-aided convolutional code, we propose the distance-spectrum optimal (DSO) CRC polynomial. A DSO CRC search algorithm for the TBCC is provided. Our analysis reveals that the complexity of SLVD is governed by the expected list rank which converges to 1 at high SNR. This allows a good performance to be achieved with a small increase in complexity. In this paper, we focus on transmitting 64 information bits with a rate-1/2 convolutional encoder. For a target error probability $10^{-4}$ , simulations show that the best CRC-ZTCC approaches the random-coding union (RCU) bound within 0.4 dB. Several CRC-TBCCs outperform the RCU bound at moderate SNR values. [ABSTRACT FROM AUTHOR]

The generalized Poor-Verdú error lower bound established by Chang et al. (2020) for multihypothesis testing is studied in the classical channel coding context. It is proved that for any sequence of block codes sent over the memoryless binary symmetric channel (BSC), the minimum probability of error (under maximum likelihood decoding) has a relative deviation from the generalized bound that grows at most linearly in blocklength. This result directly implies that for arbitrary codes used over the BSC, decoder ties can only affect the subexponential behavior of the minimum probability of error. [ABSTRACT FROM AUTHOR]

Ultrareliable low-latency communication (URLLC), a major 5G new-radio (NR) use case, is the key enabler for applications with strict reliability and latency requirements. These applications necessitate the use of short-length and high-rate channel codes. Guessing random additive noise decoding (GRAND) is a recently proposed maximum likelihood (ML) decoding technique for these short-length and high-rate codes. Rather than decoding the received vector, GRAND tries to infer the noise that corrupted the transmitted codeword during transmission through the communication channel. As a result, GRAND can decode any code, structured or unstructured. GRAND has hard-input as well as soft-input variants. Among these variants, ordered reliability bits GRAND (ORBGRAND) is a soft-input variant that outperforms hard-input GRAND and is suitable for parallel hardware implementation. This work reports the first hardware architecture for ORBGRAND, which achieves an average throughput of up to 42.5 Gb/s for a code length of 128 at a target frame error rate (FER) of 10−7. Furthermore, the proposed hardware can be used to decode any code as long as the length and rate constraints are met. In comparison to the GRAND with ABandonment (GRANDAB), a hard-input variant of GRAND, the proposed architecture enhances decoding performance by at least 2 dB. When compared to the state-of-the-art fast dynamic successive cancellation flip decoder (Fast-DSCF) using a 5G polar code (PC) (128, 105), the proposed ORBGRAND VLSI implementation has $49\times $ higher average throughput, $32\times $ times more energy efficiency, and $5\times $ more area efficiency while maintaining similar decoding performance. [ABSTRACT FROM AUTHOR]

The collapsed projection-aggregation (CPA) decoder reduces the computational complexity of the recursive projection-aggregation (RPA) decoder by removing the recursive structure. From simulations, the CPA decoder has similar error-correction performance as the RPA decoder, when decoding Reed-Muller (RM) (7, 3) and (8, 2) codes. The computational complexity can be further reduced by only selecting a subset of sub-spaces, which is achieved by pruning CPA decoders. In this work, optimization methods are proposed to find the pruned CPA (PCPA) decoder with small performance loss. Furthermore, the min-sum approximation is used to replace non-linear projection and aggregation functions, and a simplified list decoder based on the syndrome check is proposed. Under the same complexity, the optimized PCPA decoder has less performance loss than randomly constructed PCPA decoders in most case. The min-sum approximation incurs less than 0.15 dB performance loss at a target frame error rate of 10−4, and the simplified list decoder does not have noticeable performance loss. [ABSTRACT FROM AUTHOR]

In this letter, we analyze the performance of covert communications under faster-than-Nyquist (FTN) signaling in the Rayleigh block fading channel. Both maximum likelihood criterion- and Kullback-Leibler (KL) divergence-based covertness constraints are considered. Especially, for KL divergence-based one, we prove that both the maximum transmit power and covert rate under FTN signaling are higher than those under Nyquist signaling. Numerical results coincide with our analysis and validate the advantages of FTN signaling to realize covert data transmission. [ABSTRACT FROM AUTHOR]

In this paper, we study the interference-unaware receiver (IUR), which does not need the knowledge of interference or the process for precoding at the transmitter, for the interference-limited multiple-input-multiple-output (MIMO) system. We show that if the number of receive antennas is smaller than a threshold, then the interference terms dominate the MIMO channel capacity and the achievable rates of IUR so that the achievable rates of IUR can be significantly degraded by the interferences. We further show that if the number of receive antennas is larger than the threshold, then increasing the number of receive antennas can let the interference terms be negligible so that the MIMO channel capacity and the achievable rates of IUR all can reach M times the channel capacity of 1 by N single-input-multiple-output (SIMO) channel, where M denotes the number of transmit antennas and N denotes the number of receive antennas. This implies that in addition to completely eliminating cochannel interference, increasing the number of receive antennas in IUR can also make the MIMO system transmit M parallel substreams without inter-substream interference. [ABSTRACT FROM AUTHOR]

This work considers quantize–forward (QF) relay channels with $M$ -ary phase shift keying at the source and $q$ -bit uniform phase quantization at the relay. A cooperative linear combining (CLC) detection which linearly combines the received signals at the destination is proposed in the QF relay channel by deriving an equivalent signal-to-noise ratio for the source-relay-destination link. Furthermore, the proposed detection is simplified by approximating $Q$ function in two directions: small $q$ and large $q$. The CLC detection and its simplified version are also extended to multi-relay channels. Simulation results verify that the CLC and simplified CLC detections achieve reasonable performance with less complexity than the maximum-likelihood detection. It demonstrates that applying $(\log _{2} M+2)$ -bit uniform phase quantization at the relay and the simplified CLC detection at the destination can be an appropriate choice in terms of performance, complexity, and memory. [ABSTRACT FROM AUTHOR]

We propose a novel approach to optimization of irregular nonbinary (NB) quasi-cyclic (QC)-LDPC codes over small alphabets. In this approach, first, the base parity-check matrices are constructed by a simulated annealing method, and then these matrices are labeled by the field elements while maximizing the so- called generalized girth of the Tanner graph. In order to analyze the performance of the constructed irregular NB LDPC codes, a new ensemble of irregular NB LDPC codes over the extensions of the binary Galois field is introduced. A finite-length random coding bound on the error probability of the maximum-likelihood (ML) decoding over the binary phase shift keying (BPSK) input AWGN channel for the new code ensemble is derived. The frame error rate (FER) performance of the sum-product belief-propagation (BP) decoding of the constructed NB QC-LDPC block codes is compared to that of both the optimized binary QC-LDPC block codes in the 5G standard and the best known NB QC-LDPC codes as well as to the derived random coding bound on the ML decoding error probability. It is shown that the obtained bound predicts the behavior of BP decoding performance of practical NB QC-LDPC codes more accurately than the BP decoding thresholds do. [ABSTRACT FROM AUTHOR]

Reed-Muller (RM) codes have recently regained some interest in the context of low latency communications and due to their relation to polar codes. RM codes can be constructed based on the Plotkin construction. In this work, we consider concatenated codes based on the Plotkin construction, where extended Bose-Chaudhuri-Hocquenghem (BCH) codes are used as component codes. This leads to improved code parameters compared to RM codes. Moreover, this construction is more flexible concerning the attainable code rates. Additionally, new soft-input decoding algorithms are proposed that exploit the recursive structure of the concatenation and the cyclic structure of the component codes. First, we consider the decoding of the cyclic component codes and propose a low complexity hybrid ordered statistics decoding algorithm. Next, this algorithm is applied to list decoding of the Plotkin construction. The proposed list decoding approach achieves near-maximum-likelihood performance for codes with medium lengths. The performance is comparable to state-of-the-art decoders, whereas the complexity is reduced. [ABSTRACT FROM AUTHOR]

This paper investigates the decoding of a remarkable set of lattices: We treat in a unified framework the Leech lattice in dimension 24, the Nebe lattice in dimension 72, and the Barnes-Wall lattices. A new interesting lattice, named $L_{3\cdot 24}$ , is constructed as a simple application of the single parity check on the Leech lattice. The common aspect of these lattices is that they can be obtained via a single parity check or via the $k$ -ing construction. We exploit these constructions to introduce a new efficient paradigm for decoding. This leads to efficient list decoders and quasi-optimal decoders on the Gaussian channel. Both theoretical and practical performance (point error probability and complexity) of the new decoders are provided. [ABSTRACT FROM AUTHOR]

We introduce two notions of discrepancy between binary vectors, which are not metric functions in general but nonetheless capture the mathematical structure of the binary asymmetric channel. These lead to two new fundamental parameters of binary error-correcting codes, both of which measure the probability that the maximum likelihood decoder fails. We then derive various bounds for the cardinality and weight distribution of a binary code in terms of these new parameters, giving examples of codes meeting the bounds with equality. [ABSTRACT FROM AUTHOR]

In this paper we consider the diversity-multiplexing gain tradeoff (DMT) of so-called minimum delay asymmetric space-time codes for the $n \times m$ MIMO channel. Such codes correspond to lattices in $M_{n}(\mathbb {C})$ with dimension smaller than $2n^{2}$. Currently, very little is known about their DMT, except in the case $m=1$ , corresponding to the multiple input single output (MISO) channel. Further, apart from the MISO case, no DMT optimal asymmetric codes are known. We first discuss previous criteria used to analyze the DMT of space-time codes and comment on why these methods fail when applied to asymmetric codes. We then consider two special classes of asymmetric codes where the code-words are restricted to either real or quaternion matrices. We prove two separate diversity-multiplexing gain trade-off (DMT) upper bounds for such codes and provide a criterion for a lattice code to achieve these upper bounds. We also show that lattice codes based on $\mathbb {Q}$ -central division algebras satisfy this optimality criterion. As a corollary this result provides a DMT classification for all $\mathbb {Q}$ -central division algebra codes that are based on standard embeddings. While the $\mathbb {Q}$ -central division algebra based codes achieve the largest possible DMT of a code restricted to either real or quaternion space, they still fall short of the optimal DMT apart from the MISO case. [ABSTRACT FROM AUTHOR]

We revise the proof of low-rate upper bounds on the reliability function of discrete memoryless channels for ordinary and list-decoding schemes, in particular Berlekamp and Blinovsky’s zero-rate bound, as well as Blahut’s bound for low rates. The available proofs of the zero-rate bound devised by Berlekamp and Blinovsky are somehow complicated in that they contain in one form or another some “non-standard” procedures or computations. Here we follow Blinovsky’s idea of using a Ramsey-theoretic result by Komlós, and we complement it with some missing steps to present a proof which is rigorous and easier to inspect. Furthermore, we show how these techniques can be used to fix an error that invalidated the proof of Blahut’s low-rate bound, which is here presented in an extended form for list decoding and for general channels. [ABSTRACT FROM AUTHOR]

Quantum LDPC codes are a promising direction for low overhead quantum computing. In this paper, we propose a generalization of the Union-Find decoder as a decoder for quantum LDPC codes. We prove that this decoder corrects all errors with weight up to $An^\alpha $ for some $A, \alpha > 0$ , where $n$ is the code length, for different classes of quantum LDPC codes such as toric codes and hyperbolic codes in any dimension $D \geq 3$ and quantum expander codes. To prove this result, we introduce a notion of covering radius which measures the spread of an error from its syndrome. We believe this notion could find application beyond the decoding problem. We also perform numerical simulations, which show that our Union-Find decoder outperforms the belief propagation decoder in the low error rate regime in the case of a quantum LDPC code with length 3600. [ABSTRACT FROM AUTHOR]

Detection for high-dimensional multiple-input multiple-output (MIMO) and massive MIMO (MMIMO) systems is an active field of research in wireless communications. While most works consider spatially uncorrelated channels, practical MMIMO channels are correlated. This paper investigates the impact of correlation on Sphere Decoder (SD), for both single-user and multi-user scenarios. The complexity of SD is mainly determined by the initial radius method and the number of visited nodes during detection. This paper introduces a new constraint on the evaluation process of the partial distance thus modifying the conventional tree searching algorithm. This significantly decreases the number of visited nodes and renders SD feasible for large-scale systems. In addition, a proposed hardware implementation featured with a one-node-per-cycle architecture, minimizes the latency of the detection process. Trade-offs between bit error rate performance and computational complexity are presented. The trade-offs are achieved by either modifying the backtracking mechanism or limiting the number of radius updates. Simulation results prove that the proposed optimizations are effective for both correlated and uncorrelated channels, regardless of the level of noise. The decoding gain of SD compared to the low-complexity linear detectors is higher in the presence of correlation than in the uncorrelated case. However, as expected, spatial correlation adversely affects the performance and the complexity of SD. Simulation results reported here also confirm that correlation at the side equipped with more antennas is less detrimental. Hardware implementation aspects are examined for both a Virtex-7 field-programmable gate array device and a 28-nm application-specific integrated circuit technology.

To cope with the explosive traffic growth expected in next-generation wireless networks, it is necessary to design next-generation multiple access techniques that can provide higher spectral efficiency as well as larger-scale connectivity. As a promising candidate, power-domain non-orthogonal multiple access (NOMA) has been widely studied. In conventional power-domain NOMA, multiple users are multiplexed in the same time and frequency band with different preset power levels, which, however, may limit the spectral efficiency under practical finite alphabet inputs. Inspired by the concept of spatial modulation, we propose to solve this problem by encoding extra information bits into the power levels, and exploiting different signal constellations to help the receiver distinguish between them. To convey this idea, termed power selection (PS)-NOMA, clearly, we consider a simple downlink two-user NOMA system with finite input constellations. Assuming maximum-likelihood detection, we derive closed-form approximate bit error rate (BER) expressions for both users. Moreover, the two-user achievable rate region is also characterized. Simulation results verify the analysis and show that the proposed PS-NOMA can outperform conventional NOMA in terms of BER and achievable rate. [ABSTRACT FROM AUTHOR]

Guessing random additive noise decoding (GRAND) is a capacity-approaching universal algorithm. The GRAND Markov order (GRAND-MO) variant is effective to correct burst errors in a Markov chain modeled memory channel, and the core of GRAND-MO is to generate putative noise error patterns in MO effectively. For purpose of a uniform noise error pattern generation scheme of GRAND-MO, this letter proposes a successive addition-subtraction scheme to generate noise/zero error permutations for predefined MO parameters. Detailed procedures of the proposed scheme are presented, and its correctness is also proofed through theoretical derivation. By embedding the “1” and “0” bursts alternately, the proposed scheme can generate all noise error patterns in MO, which is helpful to improve the error correction capability of GRAND-MO decoders for flexible applications. [ABSTRACT FROM AUTHOR]

Conventional design methods of polar-coded modulation schemes aim to minimize the block error rate (BLER) under successive cancellation (SC) decoding. However, codes designed by conventional methods are not competitive under successive cancellation list (SCL) decoding. This paper presents a new design method based on the BLER upper bound under maximum-likelihood (ML) decoding (ML-BLER upper bound). The ML-BLER upper bound depends on the weight enumerating function (WEF) of the polar-coded modulation scheme over the squared Euclidean distance. In this paper, the polar-coded modulation is randomized by the concept of interleaved polar (i-polar) codes, and the WEF averaged over the ensemble of the polar-coded modulation schemes can be derived. Three polar-coded modulation schemes are considered, i.e., the bit-interleaved polar-coded modulation with a single interleaver (BIPCM-SI), the bit-interleaved polar-coded modulation with multiple interleavers (BIPCM-MI), and the multi-level polar-coded modulation (MLPCM). A new bit channel selection algorithm for polar-coded modulation schemes is proposed, which takes the polarization effect and the ML-BLER upper bound as design criteria. Design examples show that, under SCL decoding, the polar-coded modulation schemes (without CRC) with the proposed channel selection algorithm outperform those with conventional algorithms and are competitive as compared to the state-of-the-art 5G LDPC codes. [ABSTRACT FROM AUTHOR]

Some nonlinear codes, such as Kerdock and Preparata codes, can be represented as binary images under the Gray map of linear codes over rings. This paper introduces MAP decoding of Kerdock and Preparata codes by working with their quaternary representation (linear codes over $\mathbb {Z}_{4}$) with the complexity of $\mathcal {O}(N^{2}\log _{2} N)$ , where N is the code length in $\mathbb {Z}_{4}$. A sub-optimal bitwise APP decoder with good error-correcting performance and complexity of $\mathcal {O}(N\log _{2} N)$ that is constructed using the decoder lifting technique is also introduced. This APP decoder extends upon the original lifting decoder by working with likelihoods instead of hard decisions and is not limited to Kerdock and Preparata code families. Simulations show that our novel decoders significantly outperform several popular decoders in terms of error rate. [ABSTRACT FROM AUTHOR]

Just as rank-metric or Gabidulin codes may be used to construct rate–diversity tradeoff optimal space–time codes, a recently introduced generalization for the sum-rank metric—linearized Reed–Solomon codes—accomplishes the same in the case of multiple fading blocks. In this paper, we provide the first explicit construction of minimal delay rate–diversity optimal multiblock space–time codes as an application of linearized Reed–Solomon codes. We also provide sequential decoders for these codes and, more generally, space–time codes constructed from finite field codes. Simulation results show that the proposed codes can outperform full diversity codes based on cyclic division algebras at low SNRs as well as utilize significantly smaller constellations. [ABSTRACT FROM AUTHOR]

We present a novel iterative decoding algorithm for Reed-Muller (RM) codes, which takes advantage of a graph representation of the code. Vertices of the considered graph correspond to codewords, with two vertices being connected by an edge if and only if the Hamming distance between the corresponding codewords equals the minimum distance of the code. The algorithm uses a greedy local search to find a node optimizing a metric, e.g. the correlation between the received vector and the corresponding codeword. In addition, the cyclic redundancy check can be used to terminate the search as soon as a valid codeword is found, leading to an improvement in the average computational complexity of the algorithm. Simulation results for both binary symmetric channel and additive white Gaussian noise channel show that the presented decoder approaches the performance of maximum likelihood decoding for RM codes of length less than 1024 and for the second-order RM codes of length less than 4096. Moreover, it is demonstrated that the considered decoding approach outperforms state-of-the-art decoding algorithms of RM codes with similar computational complexity for a wide range of block lengths and rates. [ABSTRACT FROM AUTHOR]

The recently introduced polar codes constitute a breakthrough in coding theory due to their capacity-achieving property. This goes hand in hand with a quasilinear construction, encoding, and successive cancellation list decoding procedures based on the Plotkin construction. The decoding algorithm can be applied with slight modifications to Reed-Muller or eBCH codes, that both achieve the capacity of erasure channels, although the list size needed for good performance grows too fast to make the decoding practical even for moderate block lengths. The key ingredient for proving the capacity-achieving property of Reed-Muller and eBCH codes is their group of symmetries. It can be plugged into the concept of Plotkin decomposition to design various permutation decoding algorithms. Although such techniques allow to outperform the straightforward polar-like decoding, the complexity stays impractical. In this paper, we show that although invariance under a large automorphism group is valuable in a theoretical sense, it also ensures that the list size needed for good performance grows exponentially. We further establish the bounds that arise if we sacrifice some of the symmetries. Although the theoretical analysis of the list decoding algorithm remains an open problem, our result provides an insight into the factors that impact the decoding complexity. [ABSTRACT FROM AUTHOR]

The design and implementation of error correcting codes has long been informed by two fundamental results: Shannon’s 1948 capacity theorem, which established that long codes use noisy channels most efficiently; and Berlekamp, McEliece, and Van Tilborg’s 1978 theorem on the NP-completeness of decoding linear codes. These results shifted focus away from creating code-independent decoders, but recent low-latency communication applications necessitate relatively short codes, providing motivation to reconsider the development of universal decoders. We introduce a scheme for employing binarized symbol soft information within Guessing Random Additive Noise Decoding, a universal hard detection decoder. We incorporate codebook-independent quantization of soft information to indicate demodulated symbols to be reliable or unreliable. We introduce two decoding algorithms: one identifies a conditional Maximum Likelihood (ML) decoding; the other either reports a conditional ML decoding or an error. For random codebooks, we present error exponents and asymptotic complexity, and show benefits over hard detection. As empirical illustrations, we compare performance with majority logic decoding of Reed-Muller codes, with Berlekamp-Massey decoding of Bose-Chaudhuri-Hocquenghem codes, with CA-SCL decoding of CA-Polar codes, and establish the performance of Random Linear Codes, which require a universal decoder and offer a broader palette of code sizes and rates than traditional codes. [ABSTRACT FROM AUTHOR]