Evaluating the block error rate of a digital communication system is usually done using the Monte Carlo simulation method. The main drawback of the Monte Carlo method is the need of a huge sample size for estimating low error rates. Other methods commonly used are the importance sampling technique and the quasi-analytical method. This paper introduces the metric star domain decoder model and shows that many practical decoders fall into this category. The main result is the introduction of a novel SNR-invariant quasi-analytical technique for estimating the block error rate of a communication link over the geodesic channel model (a generalization of a vast number of commonly used channels, including BSC, BEC and AWGN channel) with a metric star domain decoder used at the receiver. This technique outperforms the Monte Carlo and Importance Sampling methods in both accuracy and speed. It is shown that our QA method is at least 103 times faster than MC and 10 times faster than IS for the same accuracy.

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.

Many families of binary nonlinear codes (e.g., Kerdock, Goethals, Delsarte–Goethals, Preparata) can be very simply constructed from linear codes over the ${\mathbb{Z}}_4$ ring (ring of integers modulo 4), by applying the Gray map to the quaternary symbols. Generalized Kerdock codes represent an extension of classical Kerdock codes to the ${\mathbb{Z}}_{2^S}$ ring. In this paper, we develop two novel soft-input decoders, designed to exploit the unique structure of these codes. We introduce a novel soft-input ML decoding algorithm and a soft-input soft-output MAP decoding algorithm of generalized Kerdock codes, with a complexity of $\mathcal{O}\left(N^S{log}_{2}N\right)$, where N is the length of the ${\mathbb{Z}}_{2^S}$ code, that is, the number of ${\mathbb{Z}}_{2^S}$ symbols in a codeword. Simulations show that our novel decoders outperform the classical lifting decoder in terms of error rate by some 5 dB.

Introduction/purpose: The paper introduces a reduced latency stack decoding algorithm of polar codes, inspired by the bidirectional stack decoding of convolutional codes and based on the folding technique. Methods: The stack decoding algorithm (also known as stack search) that is useful for decoding tree codes, the list decoding technique introduced by Peter Elias and the folding technique for polar codes which is used to reduce the latency of the decoding algorithm. The simulation was done using the Monte Carlo procedure. Results: A new polar code decoding algorithm, suitable for parallel implementation, is developed and the simulation results are presented. Conclusions: Polar codes are a class of capacity achieving codes that have been adopted as the main coding scheme for control channels in 5G New Radio. The main decoding algorithm for polar codes is the successive cancellation decoder. This algorithm performs well at large blocklengths with a low complexity, but has very low reliability at short and medium blocklengths. Several decoding algorithms have been proposed in order to improve the error correcting performance of polar codes. The successive cancellation list decoder, in conjunction with a cyclic redundancy check, provides very good error-correction performance, but at the cost of a high implementation complexity. The successive cancellation stack decoder provides similar error-correction performance at a lower complexity. Future machine-type and ultra reliable low latency communication applications require high-speed low latency decoding algorithms with good error correcting performance. In this paper, we propose a novel decoding algorithm, inspired by the bidirectional stack decoding of classical convolutional codes, with reduced latency that achieves similar performance as the classical successive cancellation list and successive cancellation stack decoding algorithms. The results are presented analytically and verified by simulation.