Polar codes have promising error-correction capabilities. Yet, decoding polar codes is often challenging, particularly with large blocks, with recently proposed decoders based on list-decoding or neural-decoding. The former applies multiple decoders, while the latter family learns to decode from data. In this work we introduce a novel polar decoder that combines list-decoding with neural-decoding, by forming an ensemble of multiple weighted belief-propagation (BP) decoders trained with different data. We employ the cyclic-redundancy check code as a proxy for combining the ensemble decoders and selecting the most-likely decoded word after inference, while facilitating real-time decoding. We evaluate our decoder over a wide range of polar codes lengths, empirically showing gains of around 0.25dB in frame-error rate. Our complexity and latency analysis shows that the number of operations approaches that of a single BP decoder at high SNR.

Error correction codes are an integral part of communication applications, boosting the reliability of transmission. The optimal decoding of transmitted codewords is the maximum likelihood rule, which is NP-hard due to the curse of dimensionality. For practical realizations, sub-optimal decoding algorithms are employed; yet limited theoretical insights prevent one from exploiting the full potential of these algorithms. One such insight is the choice of permutation in permutation decoding. We present a data-driven framework for permutation selection, combining domain knowledge with machine learning concepts such as node embedding and self-attention. Significant and consistent improvements in the bit error rate are introduced for all simulated codes, over the baseline decoders. To the best of the authors' knowledge, this work is the first to leverage the benefits of the neural Transformer networks in physical layer communication systems.

Ensemble models are widely used to solve complex tasks by their decomposition into multiple simpler tasks, each one solved locally by a single member of the ensemble. Decoding of error-correction codes is a hard problem due to the curse of dimensionality, leading one to consider ensembles-of-decoders as a possible solution. Nonetheless, one must take complexity into account, especially in decoding. We suggest a low-complexity scheme where a single member participates in the decoding of each word. First, the distribution of feasible words is partitioned into non-overlapping regions. Thereafter, specialized experts are formed by independently training each member on a single region. A classical hard-decision decoder (HDD) is employed to map every word to a single expert in an injective manner. FER gains of up to 0.4dB at the waterfall region, and of 1.25dB at the error floor region are achieved for two BCH(63,36) and (63,45) codes with cycle-reduced parity-check matrices, compared to the previous best result of [1].

Tail-biting convolutional codes extend the classical zero-termination convolutional codes: Both encoding schemes force the equality of start and end states, but under the tail-biting each state is a valid termination. This paper proposes a machine-learning approach to improve the state-of-the-art decoding of tail-biting codes, focusing on the widely employed short length regime as in the LTE standard. This standard also includes a CRC code.First, we parameterize the circular Viterbi algorithm, a baseline decoder that exploits the circular nature of the underlying trellis. An ensemble combines multiple such weighted decoders, each decoder specializes in decoding words from a specific region of the channel words’ distribution. A region corresponds to a subset of termination states; the ensemble covers the entire states space. A non-learnable gating satisfies two goals: it filters easily decoded words and mitigates the overhead of executing multiple weighted decoders. The CRC criterion is employed to choose only a subset of experts for decoding purpose. Our method achieves FER improvement of up to 0.75dB over the CVA in the waterfall region for multiple code lengths, adding negligible computational complexity compared to the circular Viterbi algorithm in high SNRs.

High quality data is essential in deep learning to train a robust model. While in other fields data is sparse and costly to collect, in error decoding it is free to query and label thus allowing potential data exploitation. Utilizing this fact and inspired by active learning, two novel methods are introduced to improve Weighted Belief Propagation (WBP) decoding. These methods incorporate machine-learning concepts with error decoding measures. For BCH(63,36), (63,45) and (127,64) codes, with cycle-reduced parity-check matrices, improvement of up to 0.4dB at the waterfall region, and of up to 1.5dB at the error-floor region in FER, over the original WBP, is demonstrated by smartly sampling the data, without increasing inference (decoding) complexity. The proposed methods constitutes an example guidelines for model enhancement by incorporation of domain knowledge from error-correcting field into a deep learning model. These guidelines can be adapted to any other deep learning based communication block.

In this paper, we present an improved union bound on the Linear Programming (LP) decoding performance of binary linear codes transmitted over an additive white Gaussian noise channel. The bounding technique is based on the Hunter bound, which is a second-order upper bound in probability theory, and it is minimized by Prim's minimum spanning tree algorithm. The bound calculation needs the fundamental cone generators of a given parity-check matrix rather than only their weight distribution, but involves relatively low computational complexity. It is targeted to high-density parity-check codes, where the number of their generators is extremely large and these generators are densely distributed in the Euclidean space. We explore the generator density and make a comparison between different parity-check matrix representations. That density affects the improvement of the proposed bound over the conventional LP union bound. This paper also presents a complete pseudo-weight distribution of the fundamental cone generators for the BCH[31,21,5] code.

In this paper we explore the decision regions of Linear Programming (LP) decoding. We compare the decision regions of an LP decoder, a Belief Propagation (BP) decoder and the optimal Maximum Likelihood (ML) decoder. We study the effect of minimal-weight pseudocodewords on LP decoding. We present global optimization as a method for finding the minimal pseudoweight of a given code as well as the number of minimal-weight generators. We present a complete pseudoweight distribution for the [24, 12, 8] extended Golay code, and provide justifications of why the pseudoweight distribution alone cannot be used for obtaining a tight upper bound on the error probability.

We propose several improvements for Linear Programming (LP) decoding algorithms for High Density Parity Check (HDPC) codes. First, we use the automorphism groups of a code to create parity check matrix diversity and to generate valid cuts from redundant parity checks. Second, we propose an efficient mixed integer decoder utilizing the branch and bound method. We further enhance the proposed decoders by removing inactive constraints and by adapting the parity check matrix prior to decoding according to the channel observations. Based on simulation results the proposed decoders achieve near-ML performance with reasonable complexity.

An iterative algorithm for soft-input soft-output (SISO) decoding of classical algebraic cyclic block codes is presented below. Inspired by other approaches for high performance belief propagation (BP) decoding, this algorithm requires up to 10 times less computational complexity than other methods that achieve similar performance. By utilizing multiple BP decoders, and using random permutation taken from the permutation group of the code, this algorithm reaches near maximum likelihood performance. A computational complexity comparison of the proposed algorithm versus other methods is presented as well. This includes complexity versus performance analysis, allowing one to trade between the former and the latter, according to ones needs.

Nonlinear Xing codes are considered. It is shown that Xing codes of length p-1 (where p is a prime) are subcodes of cosets of Reed-Solomon codes whose minimum distance equals Xing's lower bound on the minimum distance. This provides a straightforward proof for the lower bound on the minimum distance of the codes. The alphabet size of Xing codes is restricted not to be larger than the characteristic of the relevant finite field F/sub r/. It is shown that codes with the same length and the same lower bounds on the size and minimum distance as Xing codes exist for any alphabet size not exceeding the size r of the relevant finite field, thus extending Xing's results.

Lower bounds on the state complexity of linear tail-biting trellises are presented. One bound generalizes the total-span bound, while another bound can be regarded as a generalization of the cut-set bound. It is shown by examples that the new bounds may be tighter than any of the existing lower bounds.

A projection of binary Reed-Muller codes R(r,m) onto GF(4)/sup m-2/ is presented. For an R(r,m) code, this operation yields a linear quaternary code with the same length, dimension, and minimum distance as the Reed-Muller R(r-1, m-2) code. Based upon this projection, multilevel construction is given for R(r,m), where the constituent codes applied to the different levels are themselves the Reed-Muller codes R(r-2, m-2) and R(r, m-2), as well as the aforementioned quaternary code. This construction of Reed-Muller codes is readily applicable for their efficient decoding.

Geometric interpretation of turbo decoding has founded an analytical basis, and provided tools for the analysis of this algorithm. We focus on turbo decoding of product codes, and based on the geometric framework, we extend the analytical results and show how analysis tools can be practically adapted for this case. Specifically, we investigate the algorithm's stability and its convergence rate. We present new results concerning the structure and properties of stability matrices of the algorithm, and develop upper bounds on the algorithm's convergence rate. We prove that for any 2/spl times/2 (information bits) product codes, there is a unique and stable fixed point. For the general case, we present sufficient conditions for stability. The interpretation of these conditions provides an insight to the behavior of the decoding algorithm. Simulation results, which support and extend the theoretical analysis, are presented for Hamming [(7,4,3)]/sup 2/ and Golay [(24,12,8)]/sup 2/ product codes.

Linear tail-biting trellises for block codes are considered. By introducing the notions of subtrellis, merging interval, and sub-tail-biting trellis, some structural properties of linear tail-biting trellises are proved. It is shown that a linear tail-biting trellis always has a certain simple structure, the parallel-merged-cosets structure. A necessary condition required from a linear code in order to have a linear tail-biting trellis representation that achieves the square root bound is presented. Finally, the above condition is used to show that for r/spl ges/2 and m/spl ges/4r-1 or r/spl ges/4 and r+3/spl les/m/spl les/[(4r+5)/3] the Reed-Muller code RM(r, m) under any bit order cannot be represented by a linear tail-biting trellis whose state complexity is half of that of the minimal (conventional) trellis for the code under the standard bit order.

An upper bound on the minimal state complexity of codes from the Hermitian function field and some of its subfields is derived. Coordinate orderings under which the state complexity of the codes is not above the bound are specified. For the self-dual Hermitian code it is proved that the bound coincides with the minimal state complexity of the code. Finally, it is shown that Hermitian codes over fields of characteristic 2 admit a recursive twisted squaring construction.

The overall number of nearest neighbors in bounded distance decoding (BDD) algorithms is given by N/sub 0,eff/=N/sub 0/+N/sub BDD/. Where NBDD denotes the number of additional, non-codeword, neighbors that are generated during the (suboptimal) decoding process. We identify and enumerate the nearest neighbors associated with the original generalized minimum distance (GMD) and Chase (1972) decoding algorithms. After careful examination of the decision regions of these algorithms, we derive an approximated probability ratio between the error contribution of a noncodeword neighbor (one of N/sub BDD/ points) and a codeword nearest neighbor. For Chase algorithm 1 it is shown that the contribution to the error probability of a noncodeword nearest neighbor is a factor of 2/sup d-1/ less than the contribution of a codeword, while for Chase algorithm 2 the factor is 2/sup [d/2]-1/, d being the minimum Hamming distance of the code. For Chase algorithm 3 and GMD, a recursive procedure for calculating this ratio, which turns out to be nonexponential in d, is presented. This procedure can also be used for specifically identifying the error patterns associated with Chase algorithm 3 and GMD. Utilizing the probability ratio, we propose an improved approximated upper bound on the probability of error based on the union bound approach. Simulation results are given to demonstrate and support the analytical derivations.

We give a new definition of generalized Hamming weights of nonlinear codes and a new interpretation connected with it. These generalized weights are determined by the entropy/length profile of the code. We show that this definition characterizes the performance of nonlinear codes on the wire-tap channel of type II. The new definition is invariant under translates of the code, it satisfies the property of strict monotonicity and the generalized Singleton bound. We check the relations between the generalized weight hierarchies of Z/sub 4/-linear codes and their binary image under the Gray map. We also show that the binary image of a Z/sub 4/-linear code is a symmetric, not necessarily rectangular code. Moreover, if this binary image is a linear code then it admits a twisted squaring construction.

Weighted entropy profiles and a new bound, the weighted coordinates bound, on the state complexity profile of block codes are presented. These profiles and bound generalize the notion of dimension/length profile (DLP) and entropy/length profile (ELF) to block codes whose symbols are not drawn from a common alphabet set, and in particular, group codes. Likewise, the new bound may improve upon the DLP and ELF bounds fur linear and nonlinear block codes over fields. However, it seems that the major contribution of the proposed bound is to the study of trellis complexity of block codes whose different coordinates are drawn from different alphabet sets. The label code of lattice and nonlattice periodic packings usually has this property. The construction of a trellis diagram for a lattice and some related bounds are generalized to periodic packings by introducing the fundamental module of the packing, and using the new bound on the state complexity profile. This generalization is limited to a given coordinate system. We show that any bounds on the trellis structure of block codes, and in particular, the bound presented in this work, are applicable to periodic packings.

The trellis complexity of the Preparata and Goethals codes is examined. It is shown that at least for a given set of permutations these codes are rectangular. Upper bounds on the state complexity profiles of the Preparata and Goethals codes are given. The upper bounds on the state complexity of the Preparata and Goethals codes are determined by the dimension/length profiles (DLP) of the extended primitive double- and triple-error-correcting BCH codes, respectively. A twisted squaring construction for the Preparata and Goethals codes is given, based on the double- and triple-error-correcting extended primitive BCH codes, respectively.

For a code C, bounded distance decoding algorithms perform as optimal algorithms within the balls B(c), centered at the codewords c/spl isin/C, with radius equal to half the minimum Euclidean distance of the code. Thus distinct bounded-distance algorithms vary in performance due to their different behavior outside the balls B(c). We investigate this issue by analyzing the decision regions of some known (e.g., GMD) and some new bounded-distance algorithms presented in this work. In particular, we show that there are three distinct types of nearest neighbors and classify them according to their influence on the decision region. Simulation results and computer-generated images of the decision regions are provided to illustrate the analytical results for block and lattice codes on additive white Gaussian noise (AWGN) channels.

The trellis representation of nonlinear codes is studied from a new perspective. We introduce the new concept of entropy/length profile (ELP). This profile can be considered as an extension of the dimension/length profile (DLP) to nonlinear codes. This elaboration of the DLP, the entropy/length profiles, appears to be suitable to the analysis of nonlinear codes. Additionally and independently, we use well-known information-theoretic measures to derive novel bounds on the minimal covering of a bipartite graph by complete subgraphs. We use these bounds in conjunction with the ELP notion to derive both lower and upper bounds on the state complexity and branch complexity profiles of (nonlinear) block codes represented by any trellis diagram. We lay down no restrictions on the trellis structure, and we do not confine the scope of our results to proper or one-to-one trellises only. The basic lower bound on the state complexity profile implies that the state complexity at any given level cannot be smaller than the mutual information between the past and the future portions of the code at this level under a uniform distribution of the codewords. We also devise a different probabilistic model to prove that the minimum achievable state complexity over all possible trellises is not larger than the maximum value of the above mutual information over all possible probability distributions of the codewords. This approach is pursued further to derive similar bounds on the branch complexity profile. To the best of our knowledge, the proposed upper bounds are the only upper bounds that address nonlinear codes. The novel lower bounds are tighter than the existing bounds. The new quantities and bounds reduce to well-known results when applied to linear codes.

In this correspondence, the trellis representation of the Kerdock and Delsarte-Goethals codes is addressed. It is shown that the states of a trellis representation of DG(m,/spl delta/) under any bit-order are either strict-sense nonmerging or strict-sense nonexpanding, except, maybe, at indices within the code's distance set. For /spl delta//spl ges/3 and for m/spl ges/6, the state complexity, s/sub max/[DG(m,/spl delta/)], is found. For all values of m and /spl delta/, a formula for the number of states and branches of the biproper trellis diagram of DG(m, /spl delta/) is given for some of the indices, and upper and lower bounds are given for the remaining indices. The formula and the bounds refer to the Delsarte-Goethals codes when arranged in the standard bit-order.

Two soft-decision decoding algorithms for the (6, 3, 4) quaternary code hexacode are presented. Both algorithms realize half the minimum Euclidean distance of the code. The proposed algorithms are most practical. In using them, bounded-distance decoding of the Golay code and the Leech lattice are performed with at most 187 and 519 real-number operations respectively. Compare this to 651, respectively 3595, operations required by the best known maximum likelihood decoders (Vardy and Be'ery, 1991, 1993), and 431, respectively 1007, operations required by the bounded-distance decoders (Amrani et al., 1994). We present some simulation results for the proposed Leech lattice decoders revealing near-optimal performance. A comparison to known trellis codes is also provided.

The structure of the twisted squaring construction, a generalization of the squaring construction, is studied with respect to trellis diagrams and complexity. We show that binary affine-invariant codes, which include the extended primitive BCH codes, and the extended binary quadratic-residue codes, are equivalent to twisted squaring construction codes. In particular, a recursive symmetric reversible design of the BCH codes is derived. Using these constructions, the parameters of the minimal trellis diagram of the BCH codes are determined, including the componentwise state-space profile and trellis complexity. New designs and permutations that yield low trellis complexity for the quadratic-residue codes are presented. Generalized Hamming weights are derived from these constructions. As an example, the (48, 24, 12) quadratic-residue code is analyzed, a strictly componentwise optimal permutation is derived, and the corresponding state-space profile and complete generalized Hamming weight hierarchy are obtained.

The trellis complexity of composite-length cyclic codes (CLCC's) is addressed. We first investigate the trellis properties of concatenated and product codes in general. Known factoring of CLCC's into concatenated subcodes is thereby employed to derive upper bounds on the minimal trellis size and state-space profile. New decomposition of CLCC's into product subcodes is established and utilized to derive further upper hounds on the trellis parameters. The coordinate permutations that correspond to these bounds are exhibited. Additionally, new results on the generalized Hamming weights of CLCC's are obtained. The reduction in trellis complexity of many CLCC's leads to soft-decision decoders with relatively low complexity.>

Multilevel constructions of the binary Golay code and the Leech lattice are described. Both constructions are based upon the projection of the Golay code and the Leech lattice onto the (6,3,4) hexacode over GF(4). However, unlike the previously reported constructions, the new multilevel constructions make the three levels independent by way of using a different set of coset representatives for one of the quaternary coordinates. Based upon the multilevel structure of the Golay code and the Leech lattice, efficient bounded-distance decoding algorithms are devised. The bounded-distance decoder for the binary Golay code requires at most 431 operations. As compared to 651 operations for the best known maximum-likelihood decoder. Efficient bounded-distance decoding of the Leech lattice is achieved by means of partitioning it into four cosets of Q/sub 24/, beyond the conventional partition into two H/sub 24/ cosets. The complexity of the resulting decoder is only 953 real operations on the average and 1007 operations in the worst case, as compared to about 3600 operations for the best known in maximum-likelihood decoder. It is shown that the proposed algorithms decode correctly at least up to the guaranteed error-correction radius of the maximum-likelihood decoder. Thus, the loss in coding-gain is due primarily to an increase in the effective error-coefficient, which is calculated exactly for both algorithms. Furthermore, the performance of the Leech lattice decoder on the AWGN channel is evaluated experimentally by means of a comprehensive computer simulation. The results show a loss in coding-gain of less than 0.1 dB relative to the maximum-likelihood decoder for BER ranging from 10/sup -1/ to 10/sup -7/.>

A systematic design of a trellis-based maximum-likelihood soft-decision decoder for linear block codes is presented. The essence of the decoder is to apply an efficient search algorithm for the error pattern on a reduced trellis representation of a certain coset. Rather than other efficient decoding algorithms, the proposed decoder is systematically designed for long codes, as well as for short codes. Computational gain of up to 6 is achieved for long high-rate codes over the well-known trellis decoder of Wolf (1978). Efficient decoders are also obtained for short and moderate length codes.>

The problem of efficient maximum-likelihood soft decision decoding of binary BCH codes is considered. It is known that those primitive BCH codes whose designed distance is one less than a power of two, contain subcodes of high dimension which consist of a direct-sum of several identical codes. The authors show that the same kind of direct-sum structure exists in all the primitive BCH codes, as well as in the BCH codes of composite block length. They also introduce a related structure termed the "concurring-sum", and then establish its existence in the primitive binary BCH codes. Both structures are employed to upper bound the number of states in the minimal trellis of BCH codes, and develop efficient algorithms for maximum-likelihood soft decision decoding of these codes.>

Encoding and decoding schemes for concatenated multilevel block codes are presented. By one of these structures, a real coding gain of 5.6-7.4 dB for the bit error range of 10/sup -6/ to 10/sup -9/ is achieved for transmission through the additive white Gaussian noise channel. Also, a rather large asymptotic coding gain is obtained. The new coding schemes have very low decoding complexity and increased coding gain in comparison with the conventional block and trellis coded modulation structures. A few design rules for concatenated (single and) multilevel block codes with large coding gain are also provided.>

The size of minimal trellis representation of linear block codes is addressed. Two general upper bounds on the trellis size, based on the zero-concurring codewords and the contraction index of the subcodes, are presented. The related permutations for attaining the bounds are exhibited. These bounds evidently improve the previously published general bound. Additional bounds based on certain code constructions are derived. The focus is on the squaring construction, and specific constructive bounds for Reed-Muller and repeated-root cyclic codes are obtained. In particular, the recursive squaring construction of Reed-Muller codes is explored and the exact minimal trellis size of this design is obtained. Efficient permutations, in the sense of the trellis size, are also demonstrated by using shortening and puncturing methods. The corresponding bounds are specified.>

An algorithm for maximum likelihood decoding of the Leech lattice is presented. The algorithm involves projecting the points of the Leech lattice directly onto the codewords of the (6,3,4) quaternary code-the hexacode. Projection on the hexacode induces a partition of the Leech lattice into four cosets of a certain sublattice 24. Such a partition into cosets enables maximum likelihood decoding of the Leech lattice with 3595 real operations in the worst case and only 2955 operations on the average. This is about half the worst case and the average complexity of the best previously known algorithm.>

A Reed-Solomon decoder that makes use of bit-level soft-decision information is presented. A Reed-Solomon generator matrix that possesses a certain inherent structure in GF(2) is derived. This structure allows the code to be represented as a union of cosets, each coset being an interleaver of several binary BCH codes. Such partition into cosets provides a clue for efficient bit-level soft-decision decoding. Two decoding algorithms are derived. In the development of the first algorithm a memoryless channel is assumed, making the value of this algorithm more conceptual than practical. The second algorithm, which is obtained as a modification of the first, does account for channel memory and thus accommodates a bursty channel. Both decoding algorithms are, in many cases, orders of magnitude more efficient than conventional techniques.>

Zero-concurring codewords disclose a certain structure of the code that may be used for efficient soft-decision decoding and for designing DC-free codes. Methods for constructing sets of zero-concurring codewords are presented for several families of codes. For the general case an algorithm solution of the problem is offered. A table of results obtained using the proposed techniques is supplied for all the primitive narrow-sense binary BCH codes of length up to 127.>

An algorithm for maximum-likelihood soft-decision decoding of the binary (24,12,8) Golay code is presented. The algorithm involves projecting the codewords of the binary Golay code onto the codewords of the (6,3,4) code over GF(4)-the hexacode. The complexity of the proposed algorithm is at most 651 real operations. Along similar lines, the tetracode may be employed for decoding the ternary (12,6,6) Golay code with only 530 real operations. The proposed algorithm also implies a reduction in the number of computations required for decoding the Leech lattice.>

The main results are presented of an analysis of the convergence and the steady-state behavior of the DLMS (delayed least mean square) algorithm, with the aim of providing useful insight which may be helpful in the design of such filters. The problem is defined, and some basic definitions are presented. Conditions for convergence, convergence rate, and limits are discussed. Remarks are presented. The implications of the results for the design of DLMS adaptive filters are addressed.>

An efficient algorithm is presented for maximum-likelihood soft-decision decoding of the Leech lattice. The superiority of this decoder with respect to both computational and memory complexities is demonstrated in comparison with previously published decoding methods. Gain factors in the range of 2-10 are achieved. The authors conclude with some more advanced ideas for achieving a further reduction of the algorithm complexity based on a generalization of the Wagner decoding method to two parity constraints. A comparison with the complexity of some trellis-coded modulation schemes is discussed. The decoding algorithm presented seems to achieve a computational complexity comparable to that of the equivalent trellis codes.>

Maximum-likelihood soft-decision decoding of linear block codes is addressed. A binary multiple-check generalization of the Wagner rule is presented, and two methods for its implementation, one of which resembles the suboptimal Forney-Chase algorithms, are described. Besides efficient soft decoding of small codes, the generalized rule enables utilization of subspaces of a wide variety, thereby yielding maximum-likelihood decoders with substantially reduced computational complexity for some larger binary codes. More sophisticated choice and exploitation of the structure of both a subspace and the coset representatives are demonstrated for the (24, 12) Golay code, yielding a computational gain factor of about 2 with respect to previous methods. A ternary single-check version of the Wagner rule is applied for efficient soft decoding of the (12, 6) ternary Golay code.>

An approach for efficient utilization of fast Hadamard transform in decoding binary linear block codes is presented. Computational gain is obtained by employing various types of concurring codewords, and memory reduction is also achieved by appropriately selecting rows for the generator matrix. The availability of these codewords in general, and particularly in some of the most frequently encountered codes, is discussed.