Sebastian Cammerer

Abstract

LDPC code design tools typically rely on asymptotic code behavior and are affected by an unavoidable performance degradation due to model imperfections in the short length regime. We propose an LDPC code design scheme based on an evolutionary algorithm, the Genetic Algorithm (GenAlg), implementing a “decoder-in-the-loop” concept. It inherently takes into consideration the channel, code length and the number of iterations while optimizing the error-rate of the actual decoder hardware architecture. We construct short length LDPC codes (i.e., the parity-check matrix) with error-rate performance comparable to, or even outperforming that of well-designed standardized short length LDPC codes over both AWGN and Rayleigh fading channels. Our proposed algorithm can be used to design LDPC codes with special graph structures (e.g., accumulator-based codes) to facilitate the encoding step, or to satisfy any other practical requirement. Moreover, GenAlg can be used to design LDPC codes with the aim of reducing decoding latency and complexity, leading to coding gains of up to 0.325 dB and 0.8 dB at BLER of 10-5 for both AWGN and Rayleigh fading channels, respectively, when compared to state-of-the-art short LDPC codes. Also, we analyze what can be learned from the resulting codes and, as such, the GenAlg particularly highlights design paradigms of short length LDPC codes (e.g., codes with degree-1 variable nodes obtain very good results).

Abstract

We present a new framework for constructing polar codes (i.e., selecting the frozen bit positions) for arbitrary channels, tailored to a given decoding algorithm rather than assuming the (not necessarily optimal) successive cancellation (SC) decoding. The proposed framework is based on the genetic algorithm (GenAlg), where populations (i.e., collections) of information sets evolve via evolutionary transformations based on their individual error-rate performance. These populations converge toward an information set that fits both the decoding behavior and the defined channel. We construct polar codes, without the CRC-aid, tailored to plain successive cancellation list (SCL) decoding, achieving the same error-rate performance as the CRC-aided SCL decoding over both the AWGN channel and the Rayleigh channel, respectively. Furthermore, a proposed belief propagation (BP)-tailored construction approaches the SCL error-rate performance without any modifications in the decoding algorithm itself. The performance gains can be attributed to the significant reduction in the number of low-weight codewords. We show that, when required, the GenAlg can also be set up to find codes that reduce the decoding complexity. This way, the SCL list size or the number of BP iterations can be reduced while maintaining the same error-rate performance.

Abstract

In this work, we introduce a deep learning-based polar code construction algorithm. The core idea is to represent the information/frozen bit indices of a polar code as a binary vector which can be interpreted as trainable weights of a neural network (NN). For this, we demonstrate how this binary vector can be relaxed to a soft-valued vector, facilitating the learning process through gradient descent and enabling an efficient code construction. We further show how different polar code design constraints (e.g., code rate) can be taken into account by means of careful binary-to-soft and soft-to-binary conversions, along with rate-adjustment after each learning iteration. Besides its conceptual simplicity, this approach benefits from having the “decoder-in-the-toop”, i.e., the nature of the decoder is inherently taken into consideration while learning (designing) the polar code. We show results for belief propagation (BP) decoding over both AWGN and Rayleigh fading channels with considerable performance gains over state-of-the-art construction schemes.

Abstract

We propose a new polar code construction framework (i.e., selecting the frozen bit positions) for the additive white Gaussian noise (AWGN) channel, tailored to a given decoding algorithm, rather than based on the (not necessarily optimal) assumption of successive cancellation (SC) decoding. The proposed framework is based on the Genetic Algorithm (GenAlg), where populations (i.e., collections) of information sets evolve successively via evolutionary transformations based on their individual error-rate performance. These populations converge towards an information set that fits the decoding behavior. Using our proposed algorithm, we construct a polar code of length 2048 with code rate 0.5, without the CRC-aid, tailored to plain successive cancellation list (SCL) decoding, achieving the same error-rate performance as the CRC-aided SCL decoding, and leading to a coding gain of 1dB at BER of 10(exp6). Further, a belief propagation (BP)-tailored polar code approaches the SCL error-rate performance without any modifications in the decoding algorithm itself.

Abstract

This paper considers the forward error correction (FEC) code design for approaching the capacity of a dynamic multiple access channel (MAC) where both the number of users and their respective signal powers keep constantly changing, resembling the scenario of an actual wireless cellular system. To obtain a low-complexity non-orthogonal multiple access (NOMA) scheme, we propose a serial concatenation of a low-density parity-check (LDPC) code and a repetition code (REP), this way achieving near Gaussian MAC (GMAC) capacity performance while coping with the dynamics of the MAC system. The joint optimization of the LDPC and REP codes is addressed by matching the analytical extrinsic information transfer (EXIT) functions of the sub-optimal multi-user detector (MUD) and the channel code for a specific and static MAC system, achieving near-GMAC capacity. We show that the near-capacity performance can be flexibly maintained with the same LDPC code regardless of the variations in the number of users and power levels. This flexibility (or elasticity) is provided by the REP code, acting as “user-load and power equalizer”, dramatically simplifying the practical implementation of NOMA schemes, as only a single LDPC code is needed to cope with the dynamics of the MAC system.

Abstract

We consider spatially coupled low-density parity-check (SC-LDPC) codes within a non-orthogonal interleave division multiple access (IDMA) scheme to avoid cumbersome degree profile matching of the LDPC code components to the iterative multi-user detector (MUD). Besides excellent decoding thresholds, the approach benefits from the possibility of using rather simple and regular underlying block LDPC codes owing to the universal behavior of the resulting coupled code with respect to the channel front-end, i.e., the iterative MUD. Furthermore, an additional outer repetition code makes the scheme flexible to cope with a varying number of users and user rates, as the SC-LDPC itself can be kept constant for a wide range of different user loads. The decoding thresholds are obtained via density evolution (DE) and verified by bit error rate (BER) simulations. To keep decoding complexity and latency small, we introduce a joint iterative windowed detector/decoder imposing carefully adjusted sub-block interleavers. Finally, we show that the proposed coding scheme also works for Rayleigh channels using the same code with tolerable performance loss compared to the additive white Gaussian noise (AWGN) channel.

Abstract

We showcase the practicability of an indoor positioning system (IPS) solely based on neural networks (NNs) and the channel state information (CSI) of a (Massive) multiple-input multiple-output (MIMO) communication system, i.e., only build on the basis of data that is already existent in today's systems. As such our IPS system promises both, a good accuracy without the need of any additional protocol/signaling overhead for the user localization task. In particular, we propose a tailored NN structure with an additional phase branch as feature extractor and (compared to previous results) a significantly reduced amount of trainable parameters, leading to a minimization of the amount of required training data. We provide actual measurements for indoor scenarios with up to 64 antennas covering a large area of 80m2. In the second part, several robustness investigations for real-measurements are conducted, i.e., once trained, we analyze the recall accuracy over a period of several days. Further, we analyze the impact of pedestrians walking in-between the measurements and show that finetuning and pre-training of the NN helps to mitigate effects of hardware drifts and alterations in the propagation environment over time. This reduces the amount of required training samples at equal precision and, thereby, decreases the effort of the costly training data acquisition.

Abstract

In this work, we analyze efficient window shift schemes for windowed decoding of spatially coupled low-density parity-check (SC-LDPC) codes, which is known to yield close-to-optimal decoding results when compared to full belief propagation (BP) decoding. However, a drawback of windowed decoding is that either a significant amount of window updates are required leading to unnecessary high decoding complexity or the decoder suffers from sporadic burst-like error patterns, causing a decoder stall. To tackle this effect and, thus, to reduce the average decoding complexity, the basic idea is to enable adaptive window shifts based on a bit error rate (BER) prediction, which reduces the amount of unnecessary updates. As the decoder stall does not occur in analytical investigations such as the density evolution (DE), we examine different schemes on a fixed test-set and exhaustive monte-carlo simulations based on our graphic processing unit (GPU) simulation framework. As a result, we can reduce the average decoding complexity of the naive windowed decoder while improving the BER performance when compared to a non-adaptive windowed decoding scheme. Furthermore, we show that a foresightful stall prediction does not significantly outperform a retrospective stall detection which is much easier to implement in practice.

Abstract

We propose a belief propagation list (BPL) decoder with comparable performance to the successive cancellation list (SCL) decoder of polar codes, which already achieves the maximum likelihood (ML) bound of polar codes for sufficiently large list size L. The proposed decoder is composed of multiple parallel independent belief propagation (BP) decoders based on differently permuted polar code factor graphs. A list of possible transmitted codewords is generated and the one closest to the received vector, in terms of Euclidean distance, is picked. To the best of our knowledge, the proposed BPL decoder provides the best performance of plain polar codes under iterative decoding known so far. The proposed algorithm does not require any changes in the polar code structure itself, rendering the BPL into an alternative to the SCL decoder, equipped with a soft output capability enabling, e.g., iterative detection and decoding to further improve performance. Further benefits are the lower decoding latency than the SCL decoder and the possibility of high throughput implementations. Additionally, we show that a different selection strategy of frozen bit positions can further enhance the error-rate performance of the proposed decoder.

Abstract

End-to-end learning of communications systems is a fascinating novel concept that has so far only been validated by simulations for block-based transmissions. It allows learning of transmitter and receiver implementations as deep neural networks (NNs) that are optimized for an arbitrary differentiable end-to-end performance metric, e.g., block error rate (BLER). In this paper, we demonstrate that over-the-air transmissions are possible: We build, train, and run a complete communications system solely composed of NNs using unsynchronized off-the-shelf software-defined radios and open-source deep learning software libraries. We extend the existing ideas toward continuous data transmission, which eases their current restriction to short block lengths but also entails the issue of receiver synchronization. We overcome this problem by introducing a frame synchronization module based on another NN. A comparison of the BLER performance of the “learned” system with that of a practical baseline shows competitive performance close to 1 dB, even without extensive hyperparameter tuning. We identify several practical challenges of training such a system over actual channels, in particular, the missing channel gradient, and propose a two-step learning procedure based on the idea of transfer learning that circumvents this issue.

Abstract

We extend the idea of end-to-end learning of communications systems through deep neural network (NN)-based autoencoders to orthogonal frequency division multiplexing (OFDM) with cyclic prefix (CP). Our implementation has the same benefits as a conventional OFDM system, namely single-tap equalization and robustness against sampling synchronization errors, which turned out to be one of the major challenges in previous single-carrier implementations. This enables reliable communication over multipath channels and makes the communication scheme suitable for commodity hardware with imprecise oscillators. We show that the proposed scheme can be realized with state-of-the-art deep learning software libraries as transmitter and receiver solely consist of differentiable layers required for gradient-based training. We compare the performance of the autoencoder-based system against that of a state-of-the-art OFDM baseline over frequency-selective fading channels. Finally, the impact of a non-linear amplifier is investigated and we show that the autoencoder inherently learns how to deal with such hardware impairments.

Abstract

We demonstrate that error correcting codes (ECCs) can be used to construct a labeled data set for finetuning of “trainable” communication systems without sacrificing resources for the transmission of known symbols. This enables adaptive systems, which can be trained on-the-fly to compensate for slow fluctuations in channel conditions or varying hardware impairments. We examine the influence of corrupted training data and show that it is crucial to train based on correct labels. The proposed method can be applied to fully end-to-end trained communication systems (autoencoders) as well as systems with only some trainable components. This is exemplified by extending a conventional OFDM system with a trainable pre-equalizer neural network (NN) that can be optimized at run time.

Abstract

We describe a novel approach to interpret a polar code as a low-density parity-check (LDPC)-like code with an underlying sparse decoding graph. This sparse graph is based on the encoding factor graph of polar codes and is suitable for conventional belief propagation (BP) decoding. We discuss several pruning techniques based on the check node decoder (CND) and variable node decoder (VND) update equations, significantly reducing the size (i.e., decoding complexity) of the parity-check matrix. As a result, iterative polar decoding can then be conducted on a sparse graph, akin to the traditional well-established LDPC decoding, e.g., using a fully parallel sum-product algorithm (SPA). This facilitates the systematic analysis and design of polar codes using the well-established tools known from analyzing LDPC codes. We show that the proposed iterative polar decoder has a negligible performance loss for short-to-intermediate codelengths compared to Arikan's original BP decoder. Finally, the proposed decoder is shown to benefit from both reduced complexity and reduced memory requirements and, thus, is more suitable for hardware implementations.

Abstract

In this work, we show that polar belief propagation (BP) decoding exhibits an error floor behavior which is caused by clipping of the log-likelihood ratios (LLR). The error floor becomes more pronounced for clipping to smaller LLR-values. We introduce a single-value measure quantifying a “relative error floor”, showing, by exhaustive simulations for different lengths, that the error floor is mainly caused by inadequate clipping values. We propose four modifications to the conventional BP decoding algorithm to mitigate this error floor behavior, demonstrating that the error floor is a decoder property, and not a code property. The results agree with the fact that polar codes are theoretically proven to not suffer from error floors. Finally, we show that another cause of error floors can be an improper selection of frozen bit positions.

Abstract

We revisit the idea of using deep neural networks for one-shot decoding of random and structured codes, such as polar codes. Although it is possible to achieve maximum a posteriori (MAP) bit error rate (BER) performance for both code families and for short codeword lengths, we observe that (i) structured codes are easier to learn and (ii) the neural network is able to generalize to codewords that it has never seen during training for structured, but not for random codes. These results provide some evidence that neural networks can learn a form of decoding algorithm, rather than only a simple classifier. We introduce the metric normalized validation error (NVE) in order to further investigate the potential and limitations of deep learning-based decoding with respect to performance and complexity.

Abstract

In this work, we demonstrate an over-the-air communications system which is solely based on deep neural networks and has, thus far, only been validated by computer simulations for block-based transmissions. Transmitter and receiver can be jointly trained end-to-end for an arbitrary differentiable end-to-end performance metric, e.g., block error rate (BLER). We demonstrate that it is possible to build and train such a system using off-the-shelf software-defined radios (SDRs) and open-source deep learning software libraries. A comparison of the BLER performance of the "learned" system against that of a practical baseline shows competitive performance. We identify several practical challenges of training such a system over-the-air, in particular the missing channel gradient, and propose a learning procedure that circumvents this issue.

Abstract

The training complexity of deep learning-based channel decoders scales exponentially with the codebook size and therefore with the number of information bits. Thus, neural network decoding (NND) is currently only feasible for very short block lengths. In this work, we show that the conventional iterative decoding algorithm for polar codes can be enhanced when sub-blocks of the decoder are replaced by neural network (NN) based components. Thus, we partition the encoding graph into smaller sub-blocks and train them individually, closely approaching maximum a posteriori (MAP) performance per sub-block. These blocks are then connected via the remaining conventional belief propagation decoding stage(s). The resulting decoding algorithm is non-iterative and inherently enables a highlevel of parallelization, while showing a competitive bit error rate (BER) performance. We examine the degradation through partitioning and compare the resulting decoder to state-of-the art polar decoders such as successive cancellation list and belief propagation decoding.

Abstract

For finite length polar codes, channel polarization leaves a significant number of channels not fully polarized. Adding a Cyclic Redundancy Check (CRC) to better protect information on the semi-polarized channels has already been successfully applied in the literature, and is straightforward to be used in combination with Successive Cancellation List (SCL) decoding. Belief Propagation (BP) decoding, however, offers more potential for exploiting parallelism in hardware implementation, and thus, we focus our attention on improving the BP decoder. Specifically, similar to the CRC strategy in the SCL-case, we use a short-length “auxiliary” LDPC code together with the polar code to provide a significant improvement in terms of BER. We present the novel concept of “scattered” EXIT charts to design such auxiliary LDPC codes, and achieve net coding gains (i.e. for the same total rate) of 0.4dB at BER of 10-5 compared to the conventional BP decoder.

Abstract

Spatially coupled low-density parity-check (SC-LDPC) codes can achieve the channel capacity under low-complexity belief propagation (BP) decoding, however, there is a non-negligible rate-loss because of termination effects for practical finite coupling lengths. In this paper, we study how we can approach the performance of terminated SC-LDPC codes by random shortening of tail-biting SC-LDPC codes. We find the minimum required rate-loss in order to achieve the same performance than terminated codes. We additionally study the use of tail-biting SC-LDPC codes for transmission over parallel channels (e.g., bit-interleaved-coded-modulation (BICM)) and investigate how the distribution of the coded bits between two parallel channels can change the performance of the code. We show that a tail-biting SC-LDPC code can be used with BP decoding almost anywhere within the achievable region of MAP decoding. The optimization comes with a mandatory buffer at the encoder side. We evaluate different distributions of coded bits in order to reduce this buffer length.

Abstract

For finite coupling lengths, terminated spatially coupled low-density parity-check (SC-LDPC) codes show a non-negligible rate-loss. In this paper, we investigate if this rate loss can be mitigated by tail-biting SC-LDPC codes in conjunction with iterative demapping of higher order modulation formats. Therefore, we examine the BP threshold of different coupled and uncoupled ensembles. A comparison between the decoding thresholds approximated by EXIT charts and the density evolution results of the coupled and uncoupled ensemble is given. We investigate the effect and potential of different labelings for such a set-up using per-bit EXIT curves, and exemplify the method for a 16-QAM system, e.g., using set partitioning labelings. A hybrid mapping is proposed, where different sub-blocks use different labelings in order to further optimize the decoding thresholds of tail-biting codes, while the computational complexity overhead through iterative demapping remains small.