Low-density parity-check codes together with belief propagation (BP) decoding are known to be well-performing for large block lengths. However, for short block lengths there is still a considerable gap between the performance of BP decoding and maximum likelihood decoding. Different ensemble decoding schemes such as, e.g., automorphism ensemble decoding (AED), can reduce this gap in short block length regime. We propose generalized AED (GAED) that uses automorphisms according to the definition in linear algebra. Here, an automorphism of a vector space is defined as a linear, bijective self-mapping, whereas in coding theory self-mappings that are scaled permutations are commonly used. We show that the more general definition leads to an explicit joint construction of codes and automorphisms, and significantly enlarges the search space for automorphisms of existing linear codes. Furthermore, we prove the concept that generalized automorphisms can indeed be used to improve decoding. Additionally, we propose a code construction of linear codes enabling the construction of codes with suitably designed automorphisms. Finally, we analyze the decoding performances of GAED for some of our constructed codes.
Low-density parity-check codes together with belief propagation (BP) decoding are known to be well-performing for large block lengths. However, for short block lengths there is still a considerable gap between the performance of BP decoding and maximum likelihood decoding. Different ensemble decoding schemes such as, e.g., automorphism ensemble decoding (AED), can reduce this gap in short block length regime. We propose generalized AED (GAED) that uses automorphisms according to the definition in linear algebra. Here, an automorphism of a vector space is defined as a linear, bijective self-mapping, whereas in coding theory self-mappings that are scaled permutations are commonly used. We show that the more general definition leads to an explicit joint construction of codes and automorphisms, and significantly enlarges the search space for automorphisms of existing linear codes. Furthermore, we prove the concept that generalized automorphisms can indeed be used to improve decoding. Additionally, we propose a code construction of linear codes enabling the construction of codes with suitably designed automorphisms. Finally, we analyze the decoding performances of GAED for some of our constructed codes.
With the increasing demands on future wireless systems, new design objectives become eminent. Low-density parity-check codes together with belief propagation (BP) decoding have outstanding performance for large block lengths. Yet, for future wireless systems, good decoding performance for short block lengths is mandatory, a regime in which BP decoding typically shows a significant gap to maximum likelihood decoding. Automorphism ensemble decoding (AED) is known to reduce this gap effectively and, in addition, enables an easy trade-off between latency, throughput, and complexity. Recently, generalized AED (GAED) was proposed to increase the set of feasible automorphisms suitable for ensemble decoding. By construction, GAED requires a preprocessing step within its constituent paths that results in information loss and potentially limits the gains of GAED. In this work, we show that the preprocessing step can be merged with the Tanner graph of BP decoding, thereby improving the performance of the constituent paths. Finally, we show that the improvement of the individual paths also enhances the overall performance of the ensemble.
Low-density parity-check (LDPC) codes together with belief propagation (BP) decoding yield exceptional error correction capabilities in the large block length regime. Yet, there remains a gap between BP decoding and maximum likelihood decoding for short block length LDPC codes. In this context, ensemble decoding schemes yield both reduced latency and good error rates. In this paper, we propose subcode ensemble decoding (SCED), which employs an ensemble of decodings on different subcodes of the code. To ensure that all codewords are decodable, we use the concept of linear coverings and explore approaches for sampling suitable ensembles for short block length LDPC codes. Monte-Carlo simulations conducted for three LDPC codes demonstrate that SCED improves decoding performance compared to stand-alone decoding and automorphism ensemble decoding. In particular, in contrast to existing schemes, e.g., multiple bases belief propagation and automorphism ensemble decoding, SCED does not require the NP-complete search for low-weight dual codewords or knowledge of the automorphism group of the code, which is often unknown.
The automorphism groups of various linear codes are extensively studied yielding insights into the respective code structure. This knowledge is used in, e.g., theoretical analysis and in improving decoding performance, motivating the analyses of endomorphisms of linear codes. In this work, we discuss the structure of the set of transformation matrices of code endomor-phisms, defined as a generalization of code automorphisms, and provide an explicit construction of a bijective mapping between the image of an endomorphism and its canonical quotient space. Furthermore, we introduce a one-to-one mapping between the set of transformation matrices of endomorphisms and a larger linear block code enabling the use of well-known algorithms for the search for suitable endomorphisms. Additionally, we propose an approach to obtain unknown code endomorphisms based on automorphisms of the code. Furthermore, we consider ensemble decoding as a possible use case for endomorphisms by introducing endomorphism ensemble decoding. Interestingly, EED can improve decoding performance when other ensemble decoding schemes are not applicable.
To alleviate the suboptimal performance of belief propagation (BP) decoding of short low-density parity-check (LDPC) codes, a plethora of improved decoding algorithms has been proposed over the last two decades. Many of these methods can be described using the same general framework, which we call ensemble decoding: A set of independent constituent decoders works in parallel on the received sequence, each proposing a code-word candidate. From this list, the maximum likelihood (ML) decision is designated as the decoder output. In this paper, we qualitatively and quantitatively compare different realizations of the ensemble decoder, namely multiple-bases belief propagation (MBBP), automorphism ensemble decoding (AED), scheduling ensemble decoding (SED), noise-aided ensemble decoding (NED) and saturated belief propagation (SBP). While all algorithms can provide gains over traditional BP decoding, ensemble methods that exploit the code structure, such as MBBP and AED, typically show greater performance improvements.
We consider automorphism ensemble decoding (AED) of quasi-cyclic (QC) low-density parity-check (LDPC) codes. Belief propagation (BP) decoding on the conventional factor graph is equivariant to the quasi-cyclic automorphisms and therefore prevents gains by AED. However, by applying small modifications to the parity-check matrix at the receiver side, we can break the symmetry without changing the code at the transmitter. This way, we can leverage a gain in error-correcting performance using an ensemble of identical BP decoders, without increasing the worst-case decoding latency. The proposed method is demonstrated using LDPC codes from the CCSDS, 802.11n and 5G standards and produces gains of 0.2 to 0.3 dB over conventional BP decoding. Compared to the similarly performing saturated BP (SBP), the proposed algorithm reduces the average decoding latency by more than eight times.
In the short block length regime, pre-transformed polar codes together with successive cancellation list (SCL) decoding possess excellent error correction capabilities. However, in practice, the list size is limited due to the suboptimal scaling of the required area in hardware implementations. Automorphism ensemble decoding (AED) can improve performance for a fixed list size by running multiple parallel SCL decodings on permuted received words, yielding a list of estimates from which the final estimate is selected. Yet, AED is limited to appropriately designed polar codes. Subcode ensemble decoding (ScED) was recently proposed for low-density parity-check codes and does not impose such design constraints. It uses multiple decodings in different subcodes, ensuring that the selected subcodes jointly cover the original code. We extend ScED to polar codes by expressing polar subcodes through suitable pre-transformations (PTs). To this end, we describe a framework classifying pre-transformations for pretransformed polar codes based on their role in encoding and decoding. Within this framework, we propose a new type of PT enabling ScED for polar codes, analyze its properties, and discuss how to construct an efficient ensemble.