WO2008087042A1

WO2008087042A1 - Multiple-bases belief-propagation and permutation decoding for block codes

Info

Publication number: WO2008087042A1
Application number: PCT/EP2008/000388
Authority: WO
Inventors: Thorsten Hehn; Stefan Laendner; Johannes B. Huber; Olgica Milenkovic
Original assignee: Friedrich-Alexander-Universität Erlangen-Nürnberg
Priority date: 2007-01-19
Filing date: 2008-01-18
Publication date: 2008-07-24

Abstract

A decoder (100) for decoding a noisy received word to obtain an estimate of a transmitted word, the noisy received word being based on an encoding rule enabling at least a first and a second parity-check criterion. The decoder (100) comprises the first decoder (110) for decoding the noisy received word based on the first parity-check criterion and to obtain a first estimate of the transmitted code and a second decoder (120) for decoding the noisy transmitted word based on the second parity-check criterion and to obtain a second estimate of the transmitted word or for modifying a noisy received word according to an automorphism of the encoding rule to obtain a modified received word and for decoding the modified received word based on the first parity-check criterion and to obtain the second estimate of the transmitted word. The decoder (100) further comprises a selector (130) for selecting the first or the second estimate of the transmitted word as the estimate of the transmitted word based on the noisy received word.

Description

Multiple-Bases Belief-Propagation and Permutation Decoding for Block Codes

Description

The present invention is in the field of error or control coding, as it is used in many areas for enabling more robust transmission or storage of digital data.

In many applications coding is used to associate redundancy data with information data, in order to provide a more robust or reliable data transmission respectively storage. Additional redundancy allows to detect respectively correct errors or to prevent errors in the presence of noise, that may for example occur during data transmission. Multiple categories of codes are known, as for example, convolutional codes, block codes, etc. The decoding constraints of some codes can be represented by so-called Tanner graphs which determine how redundancy is represented within several symbols of a code word.

Stopping sets are configurations of variable nodes in Tanner graphs of codes on which iterative decoders designed for the binary erasure channel (BEC) fail [C. Di, D. Proletti, I. Telatar, T. Richardson, and R. Urbanke. Finite length analysis of low-density parity-check codes. IEEE Trans, on Inform. Theory, 48 ( 6) : 1570-1579, June 2002]. The size and number of stopping sets depends on the particular choice of the parity-check matrix used for decoding.

Since a large number of rows in the parity-check matrix of a code ensures increased flexibility in terms of meeting predefined constraints on the structure of stopping sets, several authors recently proposed using redundant parity- check matrices to improve the performance of iterative decoders [M. Schwartz and A. Vardy. On the stopping distance and stopping redundancy of codes, submitted to IEEE Trans, on Inform. Theory, March 2005] [J. H. Weber and K.A. S. Abdel-Ghaffar. Stopping and dead-end set enumerators for binary Hamming codes. In Proceedings of the Twenty- sixth Symp. on Inform. Theory in the Benelux, pages 165- 172, Brussels, Belgium, May 2005] [J. Han and P. Siegel. Improved upper bounds on stopping redundancy, submitted to IEEE Trans, on Inform. Theory, November 2005] [T. Hehn, S. Laendner, 0. Milenkovic, and J. B. Huber. The stopping redundancy hierarchy of cyclic codes. In Proceedings of the 44th Annual Allerton Conference on Communication, Control and Computing, 2006] . Adding judiciously chosen redundant rows into a parity-check matrix improves the performance of the code but also increases the overall complexity of decoding. This motivates the study of possible trade-offs between the number of redundant rows and the size of the smallest stopping set in a parity-check matrix of the code. In this context, Schwartz and Vardy [M. Schwartz and A. Vardy. On the stopping distance and stopping redundancy of codes, submitted to IEEE Trans, on Inform. Theory, March 2005] introduced the stopping redundancy of an [n, k, d] , wherein n corresponds to the codelength, k corresponds to the code dimension and d corresponds to a minimum distance linear block code C to represent the smallest number of codewords that span the dual code C- and constitute a matrix with no stopping sets of size smaller than d.

The same authors also provided lower and upper bounds on the stopping redundancy, the latter growing exponentially with the co-dimension of the code for most examples considered. This finding raised the question if there exist codes for which one could significantly decrease the number of redundant rows in the parity-check matrix by slightly decreasing the size of its smallest stopping set. Several results regarding this problem were derived by Weber and Abdel-Ghaffar [J. H. Weber and K. A. S. Abdel-Ghaffar. Stopping and dead-end set enumerators for binary Hamming codes. In Proceedings of the Twenty-sixth Symp. on Inform. Theory in the Benelux, pages 165-172, Brussels, Belgium, May 2005.], Hehn et . al. [T. Hehn, S. Laendner, O. Milenkovic, and J. B. Huber. The stopping redundancy hierarchy of cyclic codes. In Proceedings of the 44th Annual Allerton Conference on Communication, Control and Computing, 2006], as well as by Hollman and Tolhuizen [H. Hollman and L. Tolhuizen. On parity check collections for iterative erasure decoding that correct all correctable erasure patterns of a given size, submitted to IEEE Trans, on Inform. Theory, July 2005.], who addressed the question of determining the smallest redundancy of a parity-check matrix of a code that allows for decoding all correctable erasure patterns.

Classical algebraic codes such as BCH Codes [S. Lin and D.J. Costello. Error Control Coding. Pearson Education, Inc., Second edition, 2004.] are used in current transmission systems because of their good minimum distance properties, often as an outer code in concatenated coding schemes. Many of these systems such as the one defined in the DVB-S2 (DVB-S = Digital Video Broadcast Satellite) standard [M. Eroz, F. W. Sun, and L. N. Lee. DVB-S2 low density parity check codes with near Shannon limit performance. Int. J. Satell. Commun. Network, 22:269-279, May 2004.] use a powerful low-density parity-check code (LDPC = Low-Density Parity-Check) and a BP decoder (BP = Belief-Propagation) [J. Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann Publishers, 1986] for the inner coding scheme but require an outer algebraic code to overcome the error-floor problem [T. Richardson. Error-floors of LDPC codes. In Proceedings of the 41st Annual Allerton Conference on Communication, Control and Computing, pages 1426-1435, Sept. 2003] .

It is desirable to decode both codes with the same decoder, but algebraic codes are not suitable for BP decoding. Even parity-check matrices composed of minimum-weight codewords of the dual code only tend to have densities of one-entries that exceed 20% and the corresponding Tanner graphs have girth 4 [T. R. Halford, K. M. Chugg, and A.J. Grant. Which codes have 4-cycle-free Tanner graphs? In Proceedings of Int. Symp. on Inform. Theory (ISIT), pages 871-875, Seattle, WA, July 2006.]. In [M. P. C. Fossorier and S. Lin. Soft-decision decoding of linear block codes based on orderd statistics. IEEE Trans. Inform. Theory, 41:1379- 1396, September 1995] an adaptive approach based on ordered statistics decoding is presented, but it is not designed for BP decoding. The random redundant algorithm in [T. R. Halford and K. M. Chugg. Random redundant soft-in soft-out decoding of linear block codes. In Proceedings of Int. Symp. on Inform. Theory (ISIT), pages 2230-2234, Seattle, WA, July 2006.] uses multiple parity-check matrix representations but imposes a high decoding delay and requires scaling by an adaptive damping factor. Several authors [A. Kothiyal, O. Y. Takeshita, W. Jin, and M. P. C. Fossorier. Iterative reliability-based decoding of linear block codes with adaptive belief propagation. IEEE Communications Letters, 9 ( 12 ): 1067-1069, December 2005], [J. Jiang and K. R. Narayanan. Iterative soft decision decoding, of reed solomon codes based on adaptive parity check matrices. In Proc. IEEE Int. Symp. on Inform. Theory, page 261, 2004] proposed other adaptive BP algorithms, which require an additional reduction of the parity-check matrix after each decoding iteration and hence increase the delay of the data stream caused by channel decoding.

It is the object of the present invention to provide a concept for improving the decoding performance.

The object is achieved by a decoder according to claim 1, a method for decoding according to claim 16, a decoder according to claim 18 and the method for decoding according to claim 30.

It is one finding of the present invention that the problem of improving the decoding performance of codes can be addressed by adding redundant parity-check equations from a different perspective. First the notion of the stopping redundancy hierarchy of a linear block code can be introduced and second, it can be demonstrated how the stopping redundancy hierarchy can be studied in the context of permutation decoding, for example used for decoding of cyclic codes over the binary symmetric channel according to [F.J. MacWilliams and N.J. Sloane. The Theory of Error- Correcting Codes. North-Holland Publishing Company, 1977].

Embodiments can enable a new decoding strategy that can represent a combination of iterative message passing and permutation decoding. Embodiments can operate on properly designed non-redundant parity-check matrices, and may sequentially move collections of erasures confined to stopping sets into positions that do not correspond to stopping sets. Furthermore, embodiments may introduce a new class of code invariants related to the structure of their automorphism group, termed s-SAD (s-SAD = s-Stopping Automorphism Group Decoding) sets.

With respect to transmission over the binary erasure channel (BEC = Binary Erasure Channel), cf. [M. Schwartz and A. Vardy. On the stopping distance and stopping redundancy of codes, submitted to IEEE Trans, on Inform. Theory, March 2005] , embodiments may take advantage of redundant BP (BP = Belief-Propagation) decoding. Embodiments may also be applied to the AWGN (AWGN = Additive White Gaussian Noise) channel even as the number of cycles in a Tanner graph increases when additional parity-checks are appended to an existing decoding matrix. Embodiments may overcome this issue by using multiple parallel BP decoders. These decoders use parity-check matrices of cyclic form which contain the lowest number of check equations possible such that all bits are still protected equally. Embodiments show that this new parallel decoding approach compares favourably in terms of data delay imposed by the decoder and decoding performance when compared to standard BP decoding and other decoding schemes. For selected codes embodiments can provide near maximum likelihood (ML = Maximum Likelihood) performance.

Embodiments can therewith provide an improved decoding performance, e.g. improved error prevention, respectively decreased complexity.

In the following embodiments of the present invention will be detailed using the accompanying figures, in which

Fig. Ia shows an embodiment of a decoder;

Fig. Ib shows a flow chart of a method for decoding according to an embodiment;

Fig. Ic shows another embodiment of a decoder;

Fig. Id shows a flowchart of a method for decoding according to an embodiment;

Fig. Ie shows a flow chart of a method for decoding according to an embodiment;

Fig. 2a shows an illustration of a binary erasure channel;

Fig. 2b shows an illustration of a permutation for an extended cyclic code;

Fig. 2c shows another permutation for an extended cyclic code;

Fig. 3 shows bit error rate (BER = Bit Error Rate) performance comparisons for the [24, 12, 8]-Golay code, transmission over BEC; Fig. 4 shows frame error rate (FER = Frame Error Rate) performance comparison for the [24, 12, 8]-Golay code, transmission over BEC;

Fig. 5 shows a comparison on the number of required iterations for the [24, 12, 8]-Golay code, transmission over BEC;

Fig. 6 shows BER-performance comparisons for the [31, 16, 7] -BCH code, transmission over BEC;

Fig. 7 shows FER-performance comparisons the [31, 16, I]- BCH code, transmission over BEC;

Fig. 8 shows a comparison on the number of required iterations for the [31, 16, 7] -BCH code, transmission over BEC;

Fig. 9 shows a block diagram of the AWGN channel transmission scheme;

Fig. 10 shows a block diagram of an embodiment of a decoder;

Fig. 11 shows required SNR to obtain FER=IO^"3 for the [31, 16, 7] -BCH code, transmission over AWGN channel,

Fig. 12 shows required SNR to obtain FER = 10^"3 for the [24, 12, 8]-Golay code, transmission over the AWGN channel;

Fig. 13. shows the required SNR to obtain FER=IO^"3 for varying 1 when I = i x 1 = 100 is fixed, for the [31, 16, 7] -BCH code, AWGN channel;

Fig. 14 shows the required SNR to obtain FER = 10^"3 for varying 1, when I = i x 1 = 100 is fixed for the [24, 12, 8]-Golay code, AWGN channel; Fig. 15 shows BER-performance comparisons for the [31, 16, 7] -BCH code, transmission over the AWGN channel;

Fig. 16 shows FER-performance comparisons for the [31, 16, 7 ] -BCH code, transmission over the AWGN channel;

Fig. 17 shows BER-performance comparisons for the [63, 45, 7] -BCH code, transmission over the AWGN channel;

Fig. 18 shows FER-performance comparisons for the [63, 45, 7] BCH code, transmission over the AWGN channel;

Fig. 19 shows BER-performance comparisons for the [127,

113, 115] -BCH code, transmission over the AWGN channel;

Fig. 20 shows FER-performance comparisons for the [127,

113, 5] -BCH code, transmission over the AWGN channel;

Fig. 21 shows BER-performance comparisons for the [24, 12, 8]-Golay code, transmission over the AWGN channel;

Fig. 22 shows FER-performance comparisons for the [24, 12, 8]-Golay code, transmission over the AWGN channel.

Fig. Ia shows a decoder 100 for decoding a noisy received word to obtain an estimate of a transmitted word, the noisy received word being based on an encoding rule enabling at least a first and a second parity-check criteria. The decoder 100 comprises a first decoder 110 for decoding the noisy received word based on the first parity-check criterion to obtain a first estimate of the transmitted word. The decoder 100 further comprises a second decoder 120 for decoding the noisy received word based on the second parity-check criterion to obtain a second estimate of the transmitted word, or for modifying the noisy received word according to an automorphism of the encoding rule to obtain a modified received word and for decoding the modified received word based on the first parity-check criterion to obtain the second estimate of the transmitted word. The decoder 100 further comprises a selector 130 for selecting the first or the second estimate of the transmitted word as the estimate of the transmitted word based on the noisy received word.

In embodiments the decoder can be adapted for using an encoding rule corresponding to any linear block code. In other embodiments the encoding rule may correspond to a binary linear block code. In other embodiments, one of which will be detailed in the following, the encoding rule will correspond to an LDPC code (LDFC = Low-Density Parity Check) .

In embodiments the noisy received word transmitted over the AWGN channel can be represented by reliability information for individual symbols. Each individual symbol may be represented by a number of digits or a number of bits. The noisy received word may be comprised of a posteriori probabilities or log-likelihood ratios. In embodiments the first decoder 110 can be adapted to obtain the first estimate of the transmitted word using a belief-propagation algorithm, and/or the second decoder 120 can be adapted to obtain the second estimated transmitted word using a belief-propagation algorithm.

In embodiments the first parity-check criterion can correspond to a parity-check equation. Accordingly, the second parity-check criterion may correspond to a parity- check equation. The first parity-check criterion may correspond to a first parity-check matrix operation on the noisy received word, a row of the first parity-check matrix can represent a co-efficient of a parity-check equation. Accordingly, the second parity-check criterion may correspond to a second parity-check matrix operation on the noisy received word, a row of the second parity-check matrix can represent coefficients of a parity-check equation . In embodiments, a row of the first parity-check matrix may not be derivable through a cyclical shift of a row of the second parity-check matrix. The rows of the first parity- check matrix may be cyclically shifted versions of each other, accordingly, the rows of the second parity-check matrix may be cyclically shifted versions of each other.

In embodiments a selector 130 can be adapted for selecting based on the lower of a metric being dependent on the first estimate of the transmitted word and the noisy received word or a metric being dependent on the second estimate of the transmitted word and the noisy received word.

In embodiments, the metric may correspond for example to a least mean square comparison, i.e. the selector 130 can be adapted for selecting based on a least mean square comparison of the noisy received word and the first estimate of the transmitted word respectively the second estimate of the transmitted word.

In other embodiments the decoder may comprise a multiplicity of decoders for decoding the noisy received word based on different parity-check criteria, i.e. embodiments may utilise more than two decoders to provide different estimates of the transmitted word, from which the selector 130 may select.

Fig. Ib shows a flow chart of a method for decoding according to an embodiment. The flow chart illustrates a method for decoding a noisy received word to obtain an estimate of a transmitted word, the noisy received word being based on an encoding rule enabling at least a first and a second parity-check criterion. The method comprises a step 140 of decoding the noisy received word based on the first parity check criterion to obtain a first estimate of the transmitted word. Moreover, the method comprises a step 142 of decoding the noisy received word based on the second parity-check criterion to obtain a second estimate of the transmitted word, or modifying the noisy received word according to an automorphism of the encoding rule to obtain a modified received word and decoding the modified received word based on the first parity-check criterion to obtain the second estimate of the transmitted word. Moreover, the method comprises a step 144 of selecting the first or the second estimate of the transmitted word as the estimate of the transmitted word based on the noisy received word.

Fig. Ic shows an embodiment of a decoder 200 for correcting a corrupted received word for obtaining an estimate of a transmitted word, the corrupted received word being received from an erasure channel comprising one or more erased symbols, the corrupted received word being further based on an encoding rule enabling at least a first and a second parity-check criterion. The decoder 200 comprises a decoder 210 for applying the first parity-check criterion to the corrupted received word to obtain an updated received word. Furthermore, the decoder 200 comprises a processor 220 for, in case the updated received word still comprises any of the one or more erased symbols, mapping the updated received word or the corrupted received word onto a modified received word according to an automorphism of the encoding rule and wherein the decoder 210 is further adapted for applying the first parity-check criterion to the modified received word to obtain the estimate of the transmitted word or providing the second parity-check criterion according to an automorphism of the encoding rule and wherein the decoder 210 is further adapted for applying the second parity-check criterion to the updated received word or the corrupted received word to obtain the estimate of the transmitted word.

In embodiments the erasure channel may correspond to a binary erasure channel (BEC = Binary Erasure Channel) . The encoding rule may correspond to a linear block code, respectively to a binary linear block code. In embodiments the encoding rule can also correspond to an LPDC-code. As already mentioned above, the corrupted received word may be represented by binary and erased symbols, by several digits, by bits, etc.

In embodiments, the decoder 210 can be adapted for obtaining the updated received word by applying a belief- propagation algorithm to the corrupted received word based on the first parity-check criterion. The first parity- check criterion may correspond to a first parity-check matrix operation. The first parity-check matrix may comprise at least two rows which are cyclically shifted versions of each other. Accordingly, the second parity- check criterion may provide at least another row for the first parity-check matrix, wherein the other row is not a cyclically shifted version of any row of the first parity- check matrix. In embodiments the second parity-check criterion may provide a second parity-check matrix of which no row is derivable by a cyclic shift of a row of the first parity-check matrix.

In embodiments the processor 220 can be adapted for providing new modified received words according to automorphisms of the encoding rule and the decoder 210 can be adapted for applying the first parity-check criterion to the new modified received words to obtain the estimate of the transmitted word. In another embodiments the processor 220 can be adapted for providing new parity-check criteria according to automorphisms of the encoding rule and the decoder 210 may be adapted for applying the new parity- check criteria to the updated received word or the corrupted received word to obtain the estimates of the transmitted word. In other words, in embodiments iterations may be implemented, where the decoder 210 and the processor 220 may be adapted for repeating the process as it was described above multiple times. Fig. Id shows a flow chart of a method according to an embodiment. Fig. Id illustrates a method for decoding a corrupted received word to obtain an estimate of a transmitted word, the corrupted received word being received from an erasure channel and comprising one or more erased symbols, the corrupted received word being further based on an encoding rule enabling at least a first and a next parity-check criterion. Fig. Id shows a step 240 of applying the first parity-check criterion to the corrupted received word to obtain an updated received word. In step 242 it is checked whether the updated received word still comprises any of the one or more erased symbols. In case the updated received word still comprises any of the one or more symbols, step 244 shows the mapping of the updated received word or the corrupted received word onto a modified received word according to an automorphism of the encoding rule and step 246 shows applying the first parity- check criterion to the modified received word to obtain the estimate of the transmitted word. According to Fig. Id after applying the first parity-check criterion to the modified received code word the method may repeat step 242 in which the result of step 246 is checked for erased digits. According to the flow chart embodiments may also carry out iterations or loops, where multiple updates according to automorphisms may take place. Therefore, in step 244 it is already indicated by the term "next", that throughout the iterations different automorphisms of the encoding rule may be utilised.

Fig. Ie shows an alternative embodiment of a method for decoding a corrupted received word to obtain an estimate of a transmitted word. Similar to what was described above the corrupted received word being received from an erasure channel and comprising one or more erased symbols, the corrupted received word being further based on an encoding rule enabling at least a first and a next parity-check criterion. Similar to the flow chart which was described in Fig. Id, the method comprises a step 240 of applying the first parity-check criterion to the corrupted received word to obtain an updated received word. Similar to the above description in step 242 it is checked, whether the updated received word still comprises any of the one or more erased symbols.

In case the updated received word still comprises any of the one or more erased symbols a step 248 of providing the next parity-check criterion according to an automorphism of the encoding rule followed by a step 250 of applying the next parity-check criterion on the updated received word or the corrupted received word to obtain the estimate of the transmitted word is carried out. According to what was said above, an iteration may be carried out, wherein the result of step 250 is checked for erased symbols according to step 242.

In the following two detailed embodiments will be introduced. At first, the stopping redundancy hierarchy of a linear block code will be introduced and investigated and its connection to permutation decoding technigues. An element in the ordered list of stopping redundancy values represents the smallest number of possible linearly dependent rows and any parity-check matrix of a code that avoids stopping sets of a given size. Redundant parity- check equations can be shown to have a similar effect on decoding performance as permuting the coordinates of the received code word according to a selected set of automorphisms of the code. Based on this finding embodiments can comprise new decoding strategies for data transmission over, for example, a binary erasure channel that combines iterative message passing and permutation decoding in order to avoid errors confined to stopping sets. Moreover, s-SAD sets will be introduced , containing the smallest number of automorphisms of a code with the property that they move any set of not more than s erasures into positions that do not correspond to stopping sets within an judiciously chosen parity-check matrix. In the following, definitions and the terminology are introduced. Although embodiments can apply to all kinds of codes, in the following, the focus will be on binary linear [n, k, d] block codes C used for signalling over the binary erasure channel (BEC) with erasure rate 0 < ER < 1. Fig 2a illustrates a BEC. On the left hand side is the input word X being transmitted over the BEC yielding an output word Y. In the example depicted in Fig. 2a the input word X is composed of binary digits "0" and "1". The output word Y however comprises binary digits "0" and "1" plus unknown digits "?". According to the illustration the probability that an input "0" is correctly transmitted to an output "0" is 1-ER. Similar assumptions hold for the probability that an input "1" is transmitted to an output "1". First, the erasure rate ER is the probability that either an input "0" or an input "1" is transmitted to an unknown symbol "?" at the output of the BEC.

For decoding, an iterative belief-propagation algorithm is used on a suitably chosen parity check matrix H of C. It can be shown that for this combination of transmission channel and message recovery procedure, all decoding errors are confined to collections of variable nodes containing stopping sets [C. Di, D. Proletti, I. Telatar, T. Richardson, and R. Urbanke. Finite length analysis of low- density parity-check codes. IEEE Trans, on Inform. Theory, 48 (6) : 1570-1579, June 2002]. Stopping sets can be formally defined as follows. Let the columns of H be indexed by J = {0, . . . , n - 1} . For a set I e J, the restriction of B to I is the set of columns of H indexed by I. Here, it is tacitly assumed that rows of zero weight in the restriction are removed from the underlying array.

Definition 1.1 For a given parity-check matrix S of C₁ a stopping set Sσ(n) (H) of size σ is a set of σ columns for which the restriction of H does not contain rows of Hamming weight one. The stopping distance of a parity-check matrix H is the size of the smallest stopping set in H.

Note that the size and the number of stopping sets in the decoder graph depends on the particular choice of the parity-check matrix. It is straightforward to see that adding rows to a fixed parity-check matrix H may only increase its stopping distance. The added rows represent linear combinations of the basis vectors in H₁ and are referred to as redundant rows fredundant parity-checJcs,) . A parity-check matrix H containing redundant parity-check equations is henceforth referred to as a redundant parity- check matrix. The term parity-check matrix is consequently reserved for matrices of smallest possible dimension, i.e. for matrices with dimension (n - k) * n.

In order to quantify the relationship between the size of the smallest stopping set in a redundant parity-check matrix and its number of rows, the stopping redundancy hierarchy of a code is studied. The related notion of the stopping redundancy of a code was first described in [M. Schwartz and A. Vardy. On the stopping distance and stopping redundancy of codes, submitted to IEEE Trans, on Inform. Theory, March 2005] , while the latter set of parameters was introduced by the authors in [T. Hehn, S. Laendner, 0. Milenkovic, and J. B. Huber. The stopping redundancy hierarchy of cyclic codes. In Proceedings of the 44th Annual Allerton Conference on Communication, Control and Computing, 2006] .

Definition 1.2 Let C be a linear code with minimum distance d. For 1 < d, the 1-th stopping redundancy of C is the smallest integer pi{C) such that there exists a (possibly redundant) parity-check matrix H of C with pi{C) rows and stopping distance at least 1. The ordered set of integers

(P2(C) , p3(C) , . . . , Pd(C)) is called the stopping redundancy hierarchy of C. The integer pd(C) is the stopping redundancy of C.

Example 1.1 Consider the class of cyclic and extended cyclic codes studied in [T. Hehn, S. Laendner, 0. Milenkovic, and J. B. Huber. The stopping redundancy Hierarchy of cyclic codes. In Proceedings of the 44th Annual Allerton Conference on Communication, Control and Computing, 2006] . There, it was shown that redundant cyclic parity-check matrices, consisting of m cyclic shifts of a generator codeword of the dual code, n — k ≤ m ≤ n, have excellent stopping distance properties. As an illustration, such matrices were used to find the following constructive bounds on the stopping redundancy hierarchy of the Golay [23, 11, 7] code G23

P4(G23) = 11, P5(G23) ≤ 15, p6(&3) < 18, p7(G23) < 23. (1)

A closer look at the properties of decoders operating on cyclic redundant parity-check matrices will now be taken. Using a collection of cyclically shifted rows in H has the same effect as using only one of these rows and cyclically shifting the received codeword. In general , the same claim is true when one uses a collection of redundant rows that represent the images of one given row in the parity-check matrix under a set of coordinate permutations. Such coordinate permutations must necessarily preserve the codeword structure, i.e. they must correspond to automorphisms of the code. Furthermore, such automorphisms have to be chosen in a way that they relocate the positions of the erasures in the received codeword to coordinates that do not correspond to stopping sets in the parity-check matrix of the code.

To put the described observations in a rigorous mathematical framework, the definition of the automorphism group of a code is recalled first. Definition 1.3 [F.J. MacWilliams and N.J. Sloane. The Theory of Error-Correcting Codes. North-Holland Publishing Company, 1977] The permutations which send C into itself, i.e. codewords go into (possibly different) codewords, form the automorphism group of C, denoted by Aut(C) . If C is a linear code and Ci is its dual code, then Aut(C) = Aut(Cα).

Decoding procedures that use information about the automorphism group of a code have a long history [F.J. MacWilliams and N.J. Sloane. The Theory of Error-Correcting Codes. North-Holland Publishing Company, 1977]. Such procedures are known as permutation decoding algorithms and they were traditionally restricted to decoding of messages transmitted over binary symmetric channels (BSCs) . Recently, permutation decoders were also used for decoding of messages transmitted over the AWGN channel, cf. [T. R. Halford and K. M. Chugg . Random redundant soft-in soft-out decoding of linear block codes. In Proceedings of Int. Symp. on Inform. Theory (ISIT), pages 2230-2234, Seattle, WA, July 2006.]. Although not for the purpose of finding error-free information sets nor for the purpose of eliminating pseudocodewords such as stopping sets.

Within the framework of permutation decoding, a codeword c e C₁ corrupted by an error vector e = [eo, eι, . . . , en-i] of weight less than or equal to t, 2t+l < d, is subject to the following procedure. First, a parity-check matrix of the code of the form [A| I] , where I is the identity matrix of order n— k is chosen. Then, the syndrome of the received vector y = c + β, z = By^? is computed. If the weight of z is greater than t, the vector y is permuted according to a randomly chosen automorphism. This process is repeated until either all automorphisms are tested or until the syndrome has weight less than or equal to t. In the former case, the decoder declares an error. In the latter case, all decoding errors are provably confined to parity-check positions so that decoding terminates by recovering the information symbols. For the purpose of permutation decoding, one would like to identify the smallest set of automorphisms that moves any set of Ji < t positions in [0, n - 1] into the parity- check positions k, k + 1, . . . , n - 1 of [A| I] .

Definition 1.4 [J. D. Keyand, P. Seneviratne. Codes from the line graphs of complete multipartite graphs and PD sets, preprint , 2006] If C is a t-error correcting code with information set I and parity-check set P₁ then a PD(C) set (permutation decoding set of C) is a set S of automorphisms of C such that every t-set of coordinate positions is moved by at least one member of S into the check-positions P. For s < t, an s-PD(C) set is a set S of automorphisms of C such that every s-set of coordinate positions is moved by at least one member of S into P.

Throughout the remainder of the paper, PD sets of smallest possible size will be concerned and simply referred to as PD sets. Clearly, PD and s-PD sets may not exist for a given code and complete or partial information about PD sets is known in very few cases [J. D. Keyand P. Seneviratne. Codes from the line graphs of complete multipartite graphs and PD sets. preprint, 2006]. Nevertheless, even this partial information can be used to derive useful results regarding the analogues of PD sets for iterative decoders operating on stopping sets.

In the next section, the connection between the automorphism group of a code and its stopping redundancy hierarchy is studied. In order to distinguish between iterative decoders that use automorphisms to reduce errors due to stopping sets and standard permutation decoders, the former are referred to as automorphism group decoders . Automorphism group decoders offer one significant advantage over iterative decoders operating on redundant parity-check matrices: they have very low storage complexity and at the same time excellent decoding performance. This is, to a certain degree, offset by the slightly increased computational complexity of automorphism group decoders.

A sampling of results regarding a generalization of the notion of PD sets termed stopping automorphism group decoding (SAD) sets is provided next. Then SAD sets are related to the stopping redundancy hierarchy of a code.

Definition 1.5 Let H be a parity-check matrix of an error- correcting code C with minimum distance d. A SAD(H) set of H is the smallest set S of automorphisms of C such that every b-set of coordinate positions, 1 < b ≤ d - 1, is moved by at least one member of S into positions that do not correspond to a stopping set of B. Similarly, for s < d - 1, an B-SAD(H) set is the smallest set of automorphisms of C such that every b-set of coordinate positions, b < s, is moved by at least one member of S into positions that do not correspond to a stopping set in H. For a given code C, define

and refer to S^*s (C) and S^* (C) as to the s-automorphism redundancy and automorphism redundancy of C.

For a given code, s-SAD sets may not exist. This is a consequence of the fact that there may be no automorphisms that move all arbitrary collections of not more than s coordinates into positions that do not correspond to a stopping set in any given parity-check matrix. But whenever such sets exist, they can be related to the stopping redundancy hierarchy and PD sets of the code. First, it is d-\ straightforward to show that for all 1 < s < one has S^*s (C) < Is-PD(C)I, whenever such sets exist. This follows from considering parity check matrices in systematic form, and from the Singleton bound, which asserts that for any code, one must have d - 1 < n — k. Furthermore, it is

5 straightforward to see that for a restricted set of parity- check matrices, automorphism group decoders trade redundant rows with automorphisms. This is formally described by the following lemma, the proof of which is straightforward and hence omitted.

-L U

Lemma 1.2 Let C be an [n, k, d] code . Then

15 d-\ for all 1 <s < provided that an a-SAD(C) set exists.

One class of codes for which it is straightforward to prove the existence of certain SAD sets is the class of codes with transitive automorphism groups, described below.

20 Definition 1.6 A group G of permutations of the symbols [0 , n - 1] = {1, 2, . . . , n - 1} is transitive if for any two symbols i, j there exists a permutation π e G such that in = j . A group is said to be t-fold transitive if for any two collections of distinct numbers ii , . . . , it e [0,

25 n - 1] and

. . . , jt e [0 , n - 1] , there exists a π e G such that ii π = j\ , . . . , it π = jt.

Lemma 1.3 Let C be a code with an s-transitive automorphism group. Then there exist Jb-SAD sets of C for all b ≤ s. 30

Proof: Let H be of the form [A|I]. Clearly, the positions k+1 to n of H are free of stopping sets of size s≤n-k. Since the automorphism group of C is s-transitive, any collection of not more than s coordinates in [0, n - 1] is moved by some element of Aut(C) into the parity positions. Consequently, the automorphism group itself represents a (possibly non-minimal) s-SAD set.

Finding SAD sets of codes is a very complicated task, so that attention is focussed on deriving bounds on the size of such sets for specific examples of codes. In this direction, the following upper bound for S^* of the [24, 12, 8]-Golay code is obtained. First, since the automorphism group of the Golay code is 5-fold transitive, 5-SAD sets exist, and S^* ₅ ≤

, where | M241 denotes the order of the Mathieu group M24. which equals 244823040. The next result shows that S^* is actually much smaller.

Theorem 1.4 Let G24 be the unique [24, 12, S]-Golay code. Then S^* _s{G2i)≤ 14.

Proof: The proof is constructive and based on a collection of results regarding the stopping redundancy hierarchy of the Golay code [T. Hehn, S. Laendner, 0. Milenkovic, and J. B. Huber. The stopping redundancy hierarchy of cyclic codes. In Proceedings of the 44th Annual Allerton Conference on Communication, Control and Computing, 2006] and PD sets [J. Wolfmann. A permutation decoding of the (24,12,8) Golay code. IEEE Trans. On Inform. Theory, 29(5) :748-750, September 1983]. Due to space limitations, the details of the proof are omitted here. Below, the particular form of H used to meet the claimed results are listed, as well as the set of corresponding automorphisms. The matrix in question is B{G2i) = [I12IM], where

I₃ A A² A^A

1 1 1

A I₃ A^A A²

M = A = 1 0 0

A² A⁴ I₃ A 1 0 1

A⁴ A² A I₃ I_r denotes the r*r identity matrix.

The automorphisms are of the form θ^Xχ n^, i = 0, 1, J = O,

1, . . . , 5, 6, where

θ = (0, 12) (1, 13) (2, 14) (3, 15) . . . (10, 22) (11, 23); π = (3, 6, 15, 9, 21, 18, 12) (4, 7, 16, 10, 22, 19, 13) (5, 8, 17, 11, 23, 20, 14);

(4) in the standard cycle form.

The cardinality of a PD set for the Golay code is also known, and a PD set can be shown to consist of the same set of 14 permutations described in the above theorem (see [J. Wolfmann. A permutation decoding of the (24,12,8) Golay code. IEEE Trans. on Inform. Theory, 29 (5) : 748-750, September 1983] ) .

This leads to a bound on ps(G24) < 14*12 = 168 which is significantly larger than the constructive bound of value 24 found by the authors in [T. Hehn, S. Laendner, O. Milenkovic, and J. B. Huber. The stopping redundancy hierarchy of cyclic codes. In Proceedings of the 44th Annual Allerton Conference on Communication, Control and Computing, 2006] , but also significantly better than the general bound obtained from Lovasz Local Lemma described in [T. Hehn, S. Laendner, 0. Milenkovic, and J. B. Huber. The stopping redundancy hierarchy of cyclic codes. In Proceedings of the 44th Annual Allerton Conference on Communication, Control and Computing, 2006] . The parity- check matrix meeting this bound will be denoted by BJ as Eq. (3) and Eq. (4) were introduced in [J. Wolfmann. A permutation decoding of the (24,12,8) Golay code. IEEE Trans, on Inform. Theory, 29 (5) : 748-750, September 1983].

For the Golay code, one can show an even stronger result. Assume that the underlying parity-check matrix of Gn is of the form below, denoted by H^*, and that a set of 23 automorphisms of the form e, τ, τ , ..., τ ,2"2, where e denotes the identity element of S24 (the symmetric group of order 24), and τ = (0 1 2 . . . 21 22) (23), is used. Then up to weight 11, all undecodable erasure patterns, i.e. erasure patterns that contain the support of a codeword of G₂₄, for an automorphism group decoder of G24 are exactly the undecodable erasure patterns of a ML decoder of the code.

The number of undecodable erasure patterns of each weight for the described decoder and a ML decoder are shown in Table 1 further below.

'1 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1>

1 1 0 0 0 0 1 0 0 0 0 1 0 0 r 1H 1 1 0 0 0 0 0 0 1

1 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1

1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1

1 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 1

H* = 1 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1

0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 1

1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1

1 1 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1

1 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1

0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1

, 0 0 1 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 O J

This brief overview is concluded by pointing out that there exists a strong connection between the problem of set coverings [J. Schoenheim. On coverings. Pacific J. Math, 14 (4) -.1405-1411, 1964] and the problem of finding PD and SAD sets. This relationship can be used to develop simple heuristic search strategies for parity-check matrices amenable for automorphism group decoding. In the following the performance of automorphism group decoders (AGD) on cyclic and extended cyclic codes is studied. Attention is restricted to these classes of codes since large subgroups of the automorphism group of such codes are known and since the implementation complexity of AGD decoders in this case is very small. Nevertheless, the described decoding techniques can be applied to other classes of codes for which some information about the automorphism group is available. For the case of extended cyclic codes, it is tacitly assumed that the overall parity-check bit is confined to the last position of the codewords and that its index is n — 1.

Throughout this section, the following result is used.

Theorem 1.5 [7] Let c = (co, c\, . . . , cn-i) be a codeword of an [n, k, d] cyclic code. The automorphism group of the code contains the following two sets of permutations, denoted by Ci and Cz.

Ci; Cyclic permutations γ, γ², . . . , γ"^'1 : γ c = (c _n-i, Co,

C₁, ... , c_n-₂) ;

C2: Permutations ζ, ζ2 , . . . , ζm, where ζ : i → 2 ^• i mod n, and where m denotes the cardinality of the cyclotomic coset (of the n-th roots of unity) that contains one: ζ c= (C0C2... C2(_n-u ) • Note that all subscripts in the vectors described above are taken modulo n.

For extended cyclic codes, the same notation Ci and C2 to describe permutations that fix c_n_i and act on the remaining coordinates as described in the theorem above is used. All automorphisms can be decomposed into products of disjoint cycles. Permutations in Ci have one single cycle (or two cycles, for the case of extended cyclic codes) , while permutations in Ci have a number of cycles that equals the number of cyclotomic cosets r of the n-roots of unity (or r+1 cycles, for the case of extended cyclic codes). Definition 1.7 A parity-check matrix H resolves a set of coordinates if those coordinates do not correspond to a stopping set in H.

In order to describe the parity-check matrices used for automorphism group decoding of cyclic codes, the notion of the cyclic orbit generator is introduced [T. Hehn, S. Laendner, 0. Milenkovic, and J. B. Huber. The stopping redundancy hierarchy of cyclic codes. In Proceedings of the 44th Annual Allerton Conference on Communication, Control and Computing, 2006] .

Definition 1.8 Let C be an [n, k, d] binary linear cyclic code. Partition the set of codewords in the dual code Ci of minimum weight into sets consisting of cyclic shifts of one given codeword. Alternatively, partition the set of minimum weight codewords into orbits of the cyclic group. One chosen representative from each orbit is referred to as the cyclic orbit generator (cog) .

AGDA Decoders: These decoders only employ permutations from the set Ci, which reduces the permutation architecture to one shift register. The decoder uses a standard BP algorithm until the presence of a stopping set is detected. In that case, AGDA applies a cyclic shift to the current word. If the iterative decoder encounters another stopping set, the whole process is repeated with a (different) cyclic permutation. The decoding process terminates if either all permutations in Ci are tested on the received word or if the decode successfully recovers the codeword.

Assume that the number of cogs of a cyclic code is at least n-k. In this case, the parity-check matrix used for decoding consists of n- k different cogs, provided that such a matrix has full rank. A redundant parity-check matrix consisting of the collection of all vectors in the orbits of the cogs will be denoted by HAGD. AGDB Decoders: These decoders use permutations drawn from both Ci and C^. If a stopping set is encountered, the decoder first tries to resolve this set by applying a permutation from Cj. Only after the whole set Ci is exhausted, a permutation from C_∑ is applied to the current decoder word.

Fig. 2b and 2c show graphical illustrations of permutations chosen from Ci and C₂, respectively. Both illustrations show circular shaped variable nodes on the left hand side and rectangular shaped check nodes on the right hand side. The connections between the variable nodes and the check nodes indicate the parity equations.

In the following, simulation results will be presented for two particular codes, namely the [24, 12, 8]-Golay code and the cyclic [31, 16, 7] -BCH code. Before, the notion of undecodable erasure patterns will be introduced.

Definition 1.9 An undecodable erasure pattern of size σ is either a stopping set of size σ or a set that properly contains a stopping set.

Table 1: Undecodable erasure patterns of the [24, 12,8] Golay code.

In Table 1 the number of undecodable erasure patterns of size up to σ = 12 encountered in several parity-check matrices of the Golay [24, 12, 8] code is listed; H* and Bw are specified in the section above, while the matrix referenced by [4] and [12] correspond to matrices described in the papers [J. Han and P. Siegel. Improved upper bounds on stopping redundancy, submitted to IEEE Trans, on Inform. Theory, November 2005] and [M. Schwartz and A. Vardy. On the stopping distance and stopping redundancy of codes. In Proc. IEEE International Symposium on Information Theory, pages 975-979, Adelaide, Australia, September 2005.], respectively.

ML refers to the erasure patterns that cannot be recovered by an ML decoder, while HAGDΛ corresponds to the matrix described in this section. Figure 3, Figure 4, and Figure 5 show the performance results and required number of iterations of iterative decoders operating on the parity- check matrices in Table 1.

Fig. 3 shows a bit error rate (BER = Bit Error Rate) performance comparison for the [24, 12, 8] -Golay code, considering a transmission over a BEC. Fig. 3 and also all BER performance comparisons in the following show the BER on the ordinate. Fig. 3 shows the erasure rate ER of the BEC on the abscissa. Fig. 4 shows the frame error rate (FER = Frame Error Rate) on the ordinate and the erasure rate ER on the abscissa. Fig. 5 shows the number of used iterations on the ordinate and the erasure rate ER of the BEC on the abscissa.

As can be noted, there is a significant performance gain of AGDA or AGDB decoders when compared to standard belief- propagation decoders operating on the redundant parity- check matrix described in [J. Han and P. Siegel . Improved upper bounds on stopping redundancy, submitted to IEEE Trans, on Inform. Theory, November 2005] or on any other form of standard Tanner graphs. For ER<0.15, all approaches require an almost equal number of iterations while AGDA and AGDs compare favourably in terms of decoding performance. This is indicated by the vertical bar in Fig. 3, Fig. 4, and Fig. 5.

In the following the results for a BCH code will be presented. The dual of the [31, 16, 7] -BCH code contains 465 codewords of weight 7. These codewords can be partitioned into 15 cyclic orbits. Figs. 6, 7, and 8 illustrate performance results using similar view graphs as Figs. 4, 5 and 6.

Fig. 6, Fig. 7, and Fig. 8 show the performance results and decoding complexity of various types of iterative decoders for the given BCH code. The AGDA decoder operated on a parity-check matrix that consists of all 15 cogs, and for comparison, standard iterative decoding is performed on the same matrix. In addition, the performance of standard iterative decoders on three different cyclic parity-check matrices with m=n— k=15, m=21, and m=31 rows are shown. The generator codeword for these matrices is cog₃i,i₆,_A = [14140500022], given in octal form and with the most significant bit on the left hand side. In the following embodiments carrying out soft decoding for algebraic block codes are presented. Embodiments may carry out an algorithm for decoding code words transmitted over an AWGN channel. Embodiments can make use of multiple-bases belief-propagation decoding defined below. Compared to other approaches for high performance BP-decoding, embodiments are conceptually simple and do not change at each stage of the decoding process. Embodiments can utilise multiple BP decoders and can achieve the performance of a standard BP algorithm with a significantly lower number of iterations per decoder realization. Embodiments may therewith have the advantage that the data delay introduced by decoding is reduced. Moreover, embodiments may achieve significant improvements and decoding performance by keeping the data delay small. It will be shown in the following that embodiments utilizing multiple-bases belief- propagation decoding on selected codes can approach near maximum likelihood performance for very small data processing delays (ML = Maximum Likelihood) .

Fig. 9 illustrates a block diagram of the scheme considered in the following. An input signal u is encoded in a general encoder and mapped to a code word c. When travelling through the AWGN channel, additive noise n is superimposed yielding the received signal y, based on which a channel decoder estimates the input signal u with ύ.

Let C be a linear [n, k, d] block code of length n, dimension k and minimum distance d, and let u denote the vector of information symbols m e {0, 1 } , i = 0 , . . . , k- 1 of length k. c, a s {- 1, I)₁ i = 1, . . . , n, is used to denote antipodal codewords, and the real-valued vector y = (yi, , yn) to denote the noisy received word. The channel decoder determines an estimate ύ of the information vector.

Using redundant parity-check equations for decoding codewords transmitted over the BEC channel is a new technique investigated in [M. Schwartz and A. Vardy. On the stopping distance and stopping redundancy of codes, submitted to IEEE Trans, on Inform. Theory, March 2005], [J. Han and P. Siegel. Improved upper bounds on stopping redundancy, submitted to IEEE Trans, on Inform. Theory, November 2005], [T. Hehn, S. Laendner, O. Milenkovic, and J. B. Huber. The stopping redundancy hierarchy of cyclic codes. In Proceedings of the 44th Annual Allerton Conference on Communication, Control and Computing, 2006] .

For this scenario, significant performance improvements are possible as BP decoding is not affected by the introduction of new cycles into the extended Tanner graph of the code. Consequently, one can improve the decoding performance in a straightforward way by presenting redundant parity-check equations to the decoder. This simple approach is not applicable for the case of signalling over the AWGN channel as will be shown by simulations in the following section. Therefore an idea which relies on using a large number of redundant parity-check equations which are partitioned among a set of BP decoders processing the received data simultaneously is presented. The approach is referred to as Multiple-Bases Belief-Propagation (MBBP) decoding and is introduced next along with the parity-check matrices employed by the decoders.

MBBP decoding runs multiple BP decoders in parallel. Each of the decoders uses a different parity-check matrix representation of the code. Let the parity-check matrix representation used by the Λ-th decoder be denoted by Hχ, _ = 1, . . . , 1 and the decoded vector after at most i iterations by c_λ ,_λ = 1, . . . , 1. A set S £ (\ , . . . , 1} which contains the indices λ of the decoders that converged to a valid codeword is defined. If no decoder finds a valid codeword, let S = {1, . . . , 1} . The received vectors c_s , s e S are passed on to a least metric selector (LMS) which determines the best representative using the decision rule c = argmax Pr {Y = y \ C = c_s} . (5) s€S

It is well known that this equation can be rewritten [S. Lin and D.J. Costello. Error Control Coding. Pearson Education, Inc., Second edition, 2004] as

n-l c = argmin ^ \y_t - c_S;i\²

if the channel is assumed to be the AWGN channel. For all other channels, the more general rule in Equation (5) can be used to obtain c . Another idea to find c would be to determine each symbol Ci separately. To this aim choose C₁ from the vector Cs', s'eS which shows the highest reliability for symbol C₁. When conducting this choice it may additionally be considered whether the resulting vector c is a valid codeword or not. The estimated information vector ύ can be obtained from c in a straightforward manner. Algorithm 1 lists the pseudocode of the described algorithm, while Fig. 10 visualizes MBBP decoding.

Algorithm 1 MBBP decoding

S := 0 for / := 1 / do cc := OPdcc(y. Hc) if Ce Hj = 0 then S := S u f end if end for }

I/A - «?_s.,- |-

Fig . 10 illustrates an embodiment of a multiple-bases belief-propagation decoder . A noisy received word y is input at the upper left corner in Fig. 10. The belief- propagation decoders are displayed by the boxes 1010, 1020 and 1030. According to the figure there could be multiple decoders. Furthermore, Fig. 10 displays a selector 1040, which realises a least mean square evaluation between the outcomes of the decoders 1010, 1020 and 1030 and the noisy received word y in order to obtain an estimate of a transmitted word u. For the sake of generality, Fig. 10 shows parallel decoding using 1 different parity-check matrix representation Ux₁ λ = 1,...,1.

For a linear [n, k, d] code C, each set of n- k linearly independent codewords of the dual code Ci constitutes a base for Ci, i.e. can be used to generate all codewords of the dual code. Hence, each of these sets can be used to form a valid parity-check matrix of C, although most of these matrices are not appropriate for BP decoding. In general it is advisable to use (whenever possible) only minimum-weight codewords of the dual code to construct parity check matrices of full rank for MBBP decoding. By this the low-density property is achieved which may help to keep the number of short cycles in the Tanner graph small. Henceforth, the focus is on cyclic and extended cyclic codes .

Let G be the set of cyclic orbit generators with a Hamming weight equal to the minimum distance of the dual code di . The cyclic orbit generator cog^ G, A=I,..., J is used to construct the parity-check matrix Hχ_t λ- 1 ,..,,1 of size n*n by defining the i-th row of Hx as the (i- l)-th cyclic shift of cog^. As matrices of cyclic form are used and equal error protection of symbols is aspired, n parity checks are necessary. Simulation results have shown that for all cyclic codes considered in this paper the use of redundant rows is advantageous until equal error protection for all symbols is reached. Exemplary results for the [31, 16, 7]- BCH are presented in the following section. For extended cyclic codes like the [24, 12, 8]-Golay code little technical modifications are required to construct the parity-check matrices.

The benefits of using MBBP decoders will be illustrated in the following with the help of Fig. 11 and 12. Fig. 11 shows the required SNR (SNR = Signal-to-Noise-Ratio) as lOlogio (E_b/No) to obtain FER = 10^"3 for the [31, 16, 7] -BCH code considering an AWGN channel. Fig. 12 shows the required SNR as lOlogio (E_b/N₀) to obtain FER = 10^~3 for the [24, 12, 8]-Golay code considering an AWGN channel. Furthermore, Fig. 13 shows the required SNR to obtain FER = 10^~3 for 1 when I = i x 1 = 100. For Fig. 13 the [31, 16, 7] -BCH code was used, considering an AWGN channel.

Benefits from using MBBP decoders are twofold. On one hand, a significant performance gain can be obtained when one allows the overall decoding complexity of the set of MBBP decoders to exceed the complexity of one general purpose BP decoder. On the other hand, it will also be shown that MBBP uses a limited decoding complexity more efficiently compared to standard BP. For this purpose, let i be the number of iterations performed by each of the 1 decoders. The overall complexity in terms of total number of iterations performed is given by I=I' 1. The performance obtained with the [31, 16, 7] -BCH code and the [24, 12, 8]- Golay code will be considered as representative examples.

In order to obtain the results required for the study on the [31, 16, 7] -BCH code, MBBP decoding with 1< l≤ 15 decoders and Ie flOO, 200, . . . , 150Oj overall iterations are simulated. The upper restriction on 1 is due to the maximum number of cogs of minimum weight, cf . the following section. Fig. 11 shows the signal-to-noise ratio (SNR, measured as lOlogio (Eb/No) ) which is required to obtain a frame error rate (FER) of 10^~3 when the number of decoders 1 and the number of iterations per decoder i is varied. It is to be observed that classical BP decoding (1 = 1) performs noticeable worse than MBBP decoding with 1 > 1. Note that a very significant reduction of the required SNR can already be obtained when allowing for 1 = 2 decoders.

Fig. 11 also shows that the performance gain increases more by increasing 1, rather than by increasing i. A low required SNR is achievable when one allows for 1> 5 decoders and i> 50 iterations per decoder. As the required SNR is almost constant within this operational region, one has the freedom to trade-off between the number of parallel decoders and the data delay. For example, the performance obtained by 1=5, i=73 (4.5735 dB) could also be obtained by 1=6, i=60 (4.5570 dB) or 1=9, i=40 (4.5515 dB) . MBBP decoding of the [31, 16, 7 ] -BCH code for limited overall complexity is considered. 1=100 is choosen as this is a reasonable setting for standard BP decoding. The markers in Fig. 11 and Fig. 13 show the required SNR to obtain FER = 10^"3 for 1<1<15 when I=i- 1=100 is fixed. It is to observe that the required SNR reaches a minimum for a certain choice of 1 and i, which is 1 * 5 and i & 20 for the considered case of I = 100. Similar results are obtained for the [24, 12, 8] -Golay code, cf. Fig. 12 and Fig. 14.

However it is to mention that a higher overall complexity is required to obtain the desired FER at a low SNR. For the case of limiting the overall complexity described by I = 100, a choice of 1 «^■ 7 leads to an as efficient as possible use of the given complexity.

Fig. 14 shows the required SNR as lOlogio (E_b/N₀) to obtain FER = 10^"3 for varying 1 when I is fixed as I = i x L = 100, for the [24, 12, 8] -Golay code considering an AWGN channel. All results are presented for block codes of high rate and rates close to 1/2, n ≤ 127. In order to evaluate the proposed approach MBBP performance simulation results are compared to the performance of a maximum likelihood (ML) decoder performing a full search on all codewords, where the bit error rate (BER) as well as the FER as performance measures are considered. However since it is not possible to present the ML results for all considered codes, the union bound which requires the knowledge of the weight distribution of the code is utilized. Based on comprehensive studies, this bound is known to be tight for the low error rates of interest. The union bound is of the form

Where A₅ denotes the number of codewords of weight δ. If the considered code C is a high rate code, the weight distribution of Ci and use the MacWilliams identities are determined [F.J. MacWilliams and N.J. Sloane. The Theory of Error-Correcting Codes. North-Holland Publishing Company, 1977] to yield the weight distribution of C.

The evaluated codes include the [31, 16, 7] -BCH, [63, 45, 7J-BCH, and [127, 113, 5]-BCH codes, as well as the [24, 12, 8] extended Golay code.

Fig. 15 shows BER performance comparisons for the [31, 16, 7] -BCH code considering an AWGN channel. Fig. 16 shows FER performance comparisons for the [31, 16, 7] BCH code considering transmission over an AWGN channel. There exist 15 cyclic orbit generators of minimum weight 8 in the dual of the [31, 16, 7] BCH code which can be used to create the parity-check matrices Ex₁ λ ≤ 15. Based on the results from the section above, 1 = 6 decoders are choosen, each of them performing at most i = 60 iterations. Fig. 15 and Fig. 16 show the decoding performance in terms of BER and FER, respectively. For comparison with standard BP decoding, the performance of standard BP decoders using the matrices HΛ, λ=l,...,l is depicted. These decoders perform not more than i = 60 and i = 100 iterations, respectively. It is to be observed that all parity-check matrix representations yield equal performance results for fixed i and are significantly out performed by MBBP decoding. To exemplify the decoding performance of matrices of size (n- k) *n, results obtained by decoding with Hχ_r λ=l,...,l with B'χ(j, :) = H_x (j, :), J=I,... ,n-k, 1=1,..., 1 are shown. Results for the stacked matrices Hsi = [H'_l! ...; If₁] and Hs2= [H₁; ...;Hχ] demonstrate that a straightforward adaptation of the approach applicable in the BEC case does not lead to good decoding performance.

For comparison, simulation results using the Chase decoding algorithm-2 [S. Lin and D.J. Costello. Error Control Coding. Pearson Education, Inc., Second edition, 2004] are given as well. This algorithm is frequently used for soft- decision decoding of algebraic codes and performs about 0.5 dB worse compared to MBBP decoding, measured at BER = 10^"5 and FER = 10^~4, respectively. To assess the performance of MBBP decoding more generally, the union bound on ML decoding as well as simulated results for full search ML decoding are shown. It is worth mentioning that MBBP decoding almost meets the ML decoding performance. For a BER of 10^"5 or a FER of 10^~4, MBBP performs only O.OβdB worse than ML decoding.

Fig. 17 shows BER performance comparisons for the [63, 45, 7] BCH code considering transmission over an AWGN channel. Fig. 18 shows FER performance comparisons for the same code also considering transmission over an AWGN channel. The dual code of the [63, 45, 7] -BCH contains only 3 cyclic orbit generators of minimum weight 16. In this case, 1 = 3 and i = 66 is a good choice for MBBP decoding. Fig. 17 and Fig. 18 show simulation results in terms of BER and FER. Again, for comparison, the performance results obtained by standard BP decoding with 100 and 66 iterations, as well as the union bound for ML decoding are given. It is to be observed that with a total number of only I = 198 iterations, MBBP decoding performs very close to the bound for ML decoding. To be precise, MBBP decoding allows to decode this short code of rate 0.71 at 5 dB with a residual BER of ICT⁵. The [63, 45, 7] -BCH code is not decodable by full search.

Due to the presence of 18 parity symbols it is also not straightforward to apply ML decoding using the trellis of the dual code [J. L. Wolf. Efficient maximum likelihood decoding of linear block codes using a trellis. IEEE Trans. on Inform. Theory, 24:76-80, 1978]. For comparison, simulation results for Chase algorithm-2 are also included.

Fig. 19 shows BER performance comparisons for the [127, 113, 5] -BCH code considering transmission over an AWGN channel. The minimum-weight codewords of the dual of the [127, 113, 5] -BCH code have weight 56 and can be partitioned into 36 cyclic groups. The resulting large check node degrees result in a poor decoding performance when using standard BP decoding which allows to demonstrate the decoding performance advantage of MBBP decoding. Fig. 19 shows that MBBP decoding leads to an IdB performance improvement compared to standard BP decoding.

Note that at the same time, MBBP decoding reduces the decoder delay from 100 to 30 iterations. Moreover, MBBP decoding almost meets the bound on ML decoding. Fig. 20 shows FER performance comparisons for the [127, 113, 5] BCH code considering transmission over an AWGN channel. Fig. 21 shows BER performance comparisons for the [24, 12, 8] Golay code considering transmission over an AWGN channel. Fig. 22 shows FER performance comparisons for the [24, 12, 8] Golay code considering transmission over an AWGN channel. The [24, 12, 8] -Golay code is an extended cyclic code. In this case, the codewords of the dual code with minimum weight 8 are partitioned into 33 sets. Each of these sets consists of codewords that are cyclic shifts of each other when restricted to the first 23 positions. Note that it is assumed that the overall parity bit is at position 24 in the codewords. In this case, 1 = 15, i = 70 leads to good decoding results that are about 0.25 dB away from the union bound on ML decoding. This result allows to compare MBBP to the approach introduced in [T. R. Halford and K. M. Chugg. Random redundant soft-in soft-out decoding of linear block codes. In Proceedings of Int. Symp. on Inform. Theory (ISIT), pages 2230-2234, Seattle, WA, July200β.], which shows equal decoding performance. Yet MBBP decoding does not require a damping factor and needs a little less iterations allowed (1050 compared to 1200 [T. R. Halford and K. M. Chugg. Random redundant soft-in soft-out decoding of linear block codes. In Proceedings of Int. Symp. on Inform. Theory (ISIT), pages 2230-2234, Seattle, WA, July2006.]). Furthermore, MBBP has a completely parallel structure, i.e. one can keep the data delay caused by the decoder low as each decoder has to perform only i = 70 iterations.

A novel soft-decoding method for block codes termed MBBP decoding has been introduced. The method makes use of multiple parity-check matrix representations Hi, 1=1,...,! for the code C. MBBP decoding can either be used to improve decoding significantly while keeping the data delay constant or lowering the data delay while keeping the decoding performance. To a certain extend, both improvements are possible at the same time if one allows for a higher total complexity. Furthermore it is pointed out that it makes sense to use MBBP even if the total complexity is limited to a value usually required for standard BP. For several examples, MBBP decoding almost meets the performance of a full search ML decoding algorithm which is not usable in practice due to complexity reasons.

Depending on certain implementation requirements of the inventive methods, the inventive methods can be implemented in hardware or in software. The implementation can be performed using a digital storage medium, in particular a flash memory, disc, DVD or a CD having electronically readable control signals stored thereon, which cooperate with the programmable computer system such that the inventive methods are performed. Generally, the present invention is, therefore, a computer program product with a program code stored on a machine readable carrier, the program code being operative for performing the inventive methods where the computer program product runs on a computer. In other words, the inventive methods are, therefore, a computer program having a program code for performing at least one of the inventive methods when the computer program runs on a computer.

Claims

1. A decoder (100) for decoding a noisy received word to obtain an estimate of a transmitted word, the noisy received word being based on an encoding rule enabling at least a first and a second parity-check criterion, comprising:

a first decoder (110) for decoding the noisy received word based on the first parity-check criterion to obtain a first estimate of the transmitted word;

a second decoder (120) for decoding the noisy received word based on the second parity-check criterion to obtain a second estimate of the transmitted word, or

for modifying the noisy received word according to an automorphism of the encoding rule to obtain a modified received word and for decoding the modified received word based on the first parity-check criterion to obtain the second estimate of the transmitted word; and

a selector (130) for selecting the first or the second estimate of the transmitted word as the estimate of the transmitted word based on the noisy received word.

2. The decoder (100) of claim 1, wherein the encoding rule corresponds to a linear block code.

3. The decoder (100) of claim 2, wherein the encoding rule corresponds to a binary linear block code.

4. The decoder (100) of claim 2 or 3, wherein the encoding rule corresponds to an LDPC code (LDPC = Low- Density Parity-Check) .

5. The decoder (100) of one of the claims 1 to 4, wherein the noisy received word is represented by reliability information for individual symbols.

6. The decoder (100) of one of the claims 1 to 5, wherein the first decoder (110) is adapted to obtain the first estimate of the transmitted word using a belief- propagation algorithm or wherein the second decoder (120) is adapted to obtain the second estimate of the transmitted word using a belief-propagation algorithm.

7. The decoder (100) of one of the claims 1 to 6, wherein the first parity-check criterion corresponds to a parity-check equation.

8. The decoder (100) of one of the claims 1 to 7, wherein the second parity-check criterion corresponds to a parity-check equation.

9. The decoder (100) of one of the claims 1 to 8, wherein the first parity-check criterion corresponds to a first parity-check matrix operation on the noisy received word, wherein a row of the first parity-check matrix represents coefficients of a parity-check equation.

10. The decoder (100) of claim 9, wherein the second parity-check criterion corresponds to a second parity- check matrix operation on the noisy received word, wherein a row of the second parity-check matrix represents coefficients of a parity-check equation.

11. The decoder (100) of claim 10, wherein a row of the first parity-check matrix is not derivable through a cyclical shift of a row of the second parity-check matrix.

12. The decoder (100) of one of the claims 9 to 11, wherein the rows of the first parity-check matrix are cyclically shifted versions of each other or the rows of the second parity-check matrix are cyclically shifted versions of each other.

13. The decoder (100) of one of the claims 1 to 12, wherein the selector (130) is adapted for selecting based on the lower of a metric being dependent on the first estimate of the transmitted word and the noisy received word or a metric being dependent on the second estimate of the transmitted word and the noisy received word.

14. The decoder (100) of claim 13, wherein the selector (130) is adapted for selecting based on a least mean square comparison of the noisy received word and the first estimate of the transmitted word respectively the second estimate of the transmitted word.

15. The decoder (100) of one of the claims 1 to 14, comprising a multiplicity of decoders for decoding the noisy received word based on different parity check criteria .

16. A method for decoding a noisy received word to obtain an estimate of a transmitted word, the noisy received word being based on an encoding rule enabling at least a first and a second parity-check criterion, comprising the steps of

decoding the noisy received word based on the first parity-check criterion to obtain a first estimate of the transmitted word;

decoding the noisy received word based on the second parity-check criterion to obtain a second estimate of the transmitted word, or modifying the noisy received word according to an automorphism of the encoding rule to obtain a modified received word and decoding the modified received word based on the first parity-check criterion to obtain the second estimate of the transmitted word; and

selecting the first or the second estimate of the transmitted word as the estimate of the transmitted word based on the noisy received word.

17. A computer program having a program for performing the method of claim 16 when the computer program runs on a processor.

18. A decoder (200) for correcting a noisy received word to obtain an estimate of a transmitted word, the corrupted received word being received from an erasure channel and comprising one or more erased symbols, the corrupted received word being further based on an encoding rule enabling at least a first and a second parity-check criterion, comprising

a decoder (210) for applying the first parity-check criterion to the corrupted received word to obtain an updated received word;

a processor (220) for, in case the updated received word still comprises any of the one or more erased symbols,

mapping the updated received word or the corrupted received word onto a modified received word according to an automorphism of the encoding rule and wherein the decoder (210) is further adapted for applying the first parity-check criterion to the modified received word to obtain the estimate of the transmitted word or providing the second parity-check criterion according to an automorphism of the encoding rule and wherein the decoder (210) is further adapted for applying the second parity-check criterion to the updated received word or the corrupted received word to obtain the estimate of the transmitted word.

19. The decoder (200) of claim 18, wherein the erasure channel corresponds to a binary erasure channel.

20. The decoder (200) of one of the claims 18 or 19, wherein the encoding rule corresponds to a linear block code.

21. The decoder (200) of one of the claims 18 to 20, wherein the encoding rule corresponds to a binary linear block code.

22. The decoder (200) of claim 21, wherein the encoding rule corresponds to an LDPC-code.

23. The decoder (200) of one of the claims 18 to 22, wherein the corrupted received word is represented by binary and erased symbols.

24. The decoder (200) of one of the claims 18 to 23, wherein the decoder (210) is adapted for obtaining the updated received word by applying a belief-propagation algorithm to the corrupted received word based on the first parity-check criterion.

25. The decoder (200) of one of the claims 18 to 24, wherein the first parity-check criterion corresponds to a first parity-check matrix operation.

26. The decoder (200) of claim 25, wherein the first parity-check matrix comprises at least two rows which are cyclically shifted versions of each other.

27. The decoder (200) of claim 25 or 26, wherein the second parity-check criterion provides at least another row for the first parity-check matrix, wherein the other row is not a cyclically shifted version of any row of the first parity-check matrix.

28. The decoder (200) of one of the claims 25 to 27, wherein the second parity-check criterion provides a second parity-check matrix of which no row is derivable by a cyclic shift of a row of the first parity-check matrix.

29. The decoder (200) of one of the claims 18 to 28, wherein the processor (220) is adapted for providing new modified received words according to automorphisms of the encoding rule and wherein the decoder (210) is further adapted for applying the first parity-check criterion to the new modified received words to obtain the estimate of the transmitted word or wherein the processor (220) is adapted for providing new parity- check criteria according to automorphisms of the encoding rule and wherein the decoder (210) is further adapted for applying the new parity-check criteria to the updated received word or the corrupted received word to obtain the estimate of the transmitted word.

30. Method for decoding a corrupted received word to obtain an estimate of a transmitted word, the corrupted received word being received from an erasure channel and comprising one or more erased symbols, the corrupted received word being further based on an encoding rule enabling at least a first and a next parity-check criterion, comprising the steps of applying the first parity-check criterion to the corrupted received word to obtain an updated received word;

in case the updated received word still comprises any of the one or more erased symbols

mapping the updated received word or the corrupted received word onto a modified received word according to an automorphism of the encoding rule, and applying the first parity-check criterion to the modified received word to obtain the estimate of the transmitted word, or

providing the next parity-check criterion according to an automorphism of the encoding rule, and applying the next parity-check criterion on the updated received word or the corrupted received word to obtain the estimate of the transmitted word.

31. Computer program having a program code for performing the method of claim 30, when the program code runs on a processor.