Successive Cancellation Permutation Decoding of Extended BCH codes Nikolai Iakuba and Peter Trifonov ITMO University {nyakuba, pvtrifonov}@itmo.ru Abstract—BCH codes are used in many applications, including Hence, the check matrix of eBCH(2m , k, d ≥ δ) code is optical transport networks, flash memory and video broadcast- defined as a binary image of the matrix ing. This paper introduces soft decision permutation decoding 1 1 1  1 ... 1 algorithm for extended BCH codes based on it’s representation 01 α α2 ... αn−1 as polar codes with dynamic frozen symbols. The proposed H =  ... ... .. . .. . .. . .. . , (1) algorithm outperforms bounded distance hard decision decoding 0 1 αδ−2 α2(δ−2) ... α(n−1)(δ−2) and provides flexible tradeoff between performance and decoding 0 1 αδ−1 α2(δ−1) ... α(n−1)(δ−1) complexity. where all linearly dependent rows are eliminated. It can be seen that BCH codes are closely related to Reed- I. I NTRODUCTION Muller and polar codes. Polar (n, k) code is defined as a set of vectors Bose-Chaudhuri-Hocquengham (BCH) codes are still ex-  tensively used in many practical applications, such as optical C = u0n−1 A⊗m | u0n−1 ∈ Fn2 , ui = 0, ∀i ∈ F , (2) transport networks, flash memory and video broadcasting. A where A = ( 11 01 ), ⊗m denotes m-times Kronecker product of BCH code with constructive minimum distance δ can be the matrix A with itself, and F, |F| = k denotes set of frozen decoded using bounded distance hard decision decoders, which symbols, which depends on a transmission channel. 2 ⌋ errors. can correct t = ⌊ δ−1 A Reed-Muller code of length 2m and order r can be defined Several one-pass schemes of Chase decoding were proposed as a special case of polar codes: [1], which evaluate error-locator polynomials for all test vec-  tors using a single pass of the Berlekamp’s algorithm. A good RM(r, m) = u0n−1 A⊗m | ui = 0, ∀i : wt(i) < m − r , overview of various soft decision algebraic decoding methods (3) developed for BCH codes is given in [2]. where wt(i) denotes Hamming weight of the index. Other soft decision decoding methods based on Viterbi and Both polar and Reed-Muller codes can be decoded using ordered statictics decoding algorithms can provide maximum- successive cancellation (SC) algorithm. Suppose, that the likelihood decoding at cost of substantial increase in decoding codeword of (n = 2m , k) polar (or Reed-Muller) code complexity [3], [4]. c0n−1 = u0n−1 A⊗m is transmitted through the channel W with In this paper a soft-input decoding algorithm based on transition probabilities W (y|x), and the noisy vector y0n−1 is successive cancellation decoding for primitive extended BCH passed to the decoder. codes is presented. It uses the representation of extended The decoding algorithm is based on recursive computation BCH codes as polar codes with dynamic frozen symbols, of transition probabilities and employs permutation decoding techniques to enhance X n−1 Y 1 performance. 0 |ui ) , Wi (y0n−1 , ui−1 W (yi |ui ). (4) 2n−1 i=0 The proposed decoding algorithm is based on the successive un−1 n−i−1 i+1 ∈F2 cancellation list decoder developed in [5] for polar codes, and At the receiver end symbols ûφ , φ = 0, . . . , n − 1 can be provides a flexible tradeoff between decoding performance estimated one by one: and complexity. Simulations show, that the proposed decoder ( performs better than hard-decision decoder, however it does arg maxuφ ∈F2 Wφ (y0n−1 , ûφ−1 |uφ ), φ 6∈ F 0 not guarantee bounded distance decoding of BCH codes. ûφ = (5) 0, φ ∈ F. II. BCH AND R EED -M ULLER CODES Due to the recursive structure of the matrix A⊗m encoding and decoding can be done in O(n log n) operations. In this paper we consider extended primitive narrow-sense BCH codes (eBCH codes) over F2 . Generator polynomial A. Successive cancellation list decoding algorithm of a BCH code of length n = 2m − 1 with constructive Unfortunately, SC decoding of polar codes of moderate minimum distance δ has roots α, α2 , . . . , αδ−1 , where α lengths leads to rather poor performance, since the estimates denotes primitive element of GF(2m ). ûφ are computed without taking into account frozen symbols Copyright© 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). ui , i > φ, i ∈ F. However, performance of the SC algorithm III. P ROPOSED APPROACH can be enhanced by considering several possible paths û0n−1 Observe, that automorphism group of Reed-Muller codes in the code tree. contains general affine group [8]. In other words, it can This approach is used in the successive cancellation list be shown that any permutation of symbols in a codeword (SCL) decoding algorithm introduced by Tal and Vardy [5]. π(x) = M x + b, where x is a binary representation of a bit Interestingly, the same idea was described earlier by Dumer index (coordinate), and M is non-singular matrix, defines an and Shabunov in their work [6] devoted to the decoding of automorphism of a Reed-Muller code. Reed-Muller codes. Below we revise the min-sum version of It was proposed in [6] to initialize the SCL decoder with the SCL algorithm. several permutations of a codeword to further enhance decod- The SCL decoder successively extends L vectors ûφ0 of ing performance. We propose to apply this idea to the decoding equal length trying to maximize their score of eBCH codes. φ X Let consider a eBCH(n, k, d) code C and its check matrix M (ûφ0 , y0n−1 ) = (i) i−1 n−1 τ (ûi , Sm (û0 , y0 )), (6) H defined as it was shown in equation (1). Consider a permu- i=0 tation taken from automorphism group of the corresponding where ( Reed-Muller supercode R, C ⊆ R. This permutation applied 0, if (−1)u = sgn(S) to H defines an equivalent code C ′ , which may not be equal τ (u, S) = (7) to C, although C ′ ⊆ R. Since C ′ is also included in R, −|S|, otherwise representations of C and C ′ as polar codes will have similar (i) is the penalty function. Sm (û0i−1 , y0n−1 ) denotes the log- sets of frozen symbols F. For instance, Theorem 2 is still likelihood ratio given by valid for equivalent codes obtained that way, and performance of successive cancellation decoding doesn’t differ much. (2φ) Sλ (û02φ−1 , y0n−1 ) = sgn(a) sgn(b) min(|a|, |b|), The algorithm Decode illustrates the proposed method. (8) Sλ (2φ+1) (û2φ n−1 ) = (−1)û2φ a + b, Main parameters of the algorithm are list size L, and the 0 , y0 set of permutations P = {π0 , . . . , πl } of size l. Note that φ 2φ−1 2φ−1 n/2−1 where n = 2m−λ , a = Sλ−1 (û0,e + û0,o , y0 ), each permutation of P also defines permutation on the check (φ) 2φ−1 n−1 b = Sλ−1 (û0,o , yn/2−1 ), and S0 (i) = log W(yi |0) − matrix H of the considered eBCH code. Hence, permutation may share different sets of frozen symbols F and different log W(yi |1). Here ûφ0,o and ûφ0,e denote subvectors of ûφ0 constraint matrices V . consisting of elements on odd end even indices respectively. In line 1 the constraint matrix V (i) and set of frozen symbols The list size L defines the complexity O(Ln log n) of the F are evaluated for each permutation πi as it was described (i) decoding. in section II-B. Permuted input vector of log-likelihood ratios (0) (µn−1) S0 = (S0 , . . . , S0 ) is used to initialize paths with B. Dynamic frozen symbols indices i = 0, . . . , l − 1 in line 4. In line 5 list U is filled with these paths. It was shown in [7], that any (n = 2m , k, d) code with check The list U consists of triplets hM, û0φ−1 , ii, which define matrix H can be represented as a polar code with dynamic paths considered by the decoder on iteration φ. Here M frozen symbols. Let denote Am = A⊗m , where A = ( 11 01 ). denotes a path score, û0φ−1 is a vector of bits estimated on Since A−1m = Am , it is possible to choose matrices V and previous phases, and i is a permutation index. W , such that H = V ATm and cn−1 0 H T = u0n−1 W V T = 0. The main decoding loop starts with line 6. In line 9 values Hence, some symbols ui , i ∈ F can be set to predefined linear (i) Sm (ûi−1 0 , y0 n−1 ) are computed according to (6)–(8), and set functions of previous symbols, i.e. of continuations Ũ is constructed. X Function GetBestPaths(U , L) returns L continuations with uji = Vi,s us , 0 ≤ i < n − k, (9) highest scores from the set U . Selected continuations are s δ) code the number of IV. C HOOSING THE SET OF PERMUTATIONS dynamic frozen symbols of weight t equals to the total number of elements of weight t in cyclotomic classes, containing Decoding performance of the algorithm described in previ- α, α2 , . . . , αδ−1 (see Theorem 2 [7]). This theorem provides ous section highly depends on the initial set of permutations an empiric observation that representation of a eBCH code as a P passed to the decoder. Unfortunately, we have no analytic polar code leads to relatively good set F, therefore successive way to construct P, although one may use greedy approach cancellation decoding may be applied to decode eBCH code. to form P by choosing permutations one by one. Procedure Decode(L, P, S0 ) zero binary vectors. Second row of M is generated such that input : list size L of the decoder, it doesn’t end in the same column as the first row. Third row set of permutations P = {π0 , . . . , πl }, shouldn’t end in the same columns as first and second rows (0) log-likelihood ratios S0 = (S0 , . . . , S0 (µn−1) ) and so on. TheQtotal number of possible permutations therefore m output: estimated bits û0 n−1 is reduced to i=1 2i − 1. We start with a single permutation, which corresponds to 1 for i ← 0 to l − 1 do the standard bit ordering of the check matrix H. That is, the (V (i) , F (i) ) ← GetConstraintMatrix(πi ) binary representation of the second row in (1) corresponds to 2 U ←∅ the vector (0, 1, 2, . . . , 2m − 1). 3 for i ← 0 to l − 1 do Other permutations are chosen iteratively: for a fixed signal 4 InitPath(Permute(S0 , πi ), i) to noise ratio Nmax permutation matrices are generated at ran- 5 U ← U ∪ {h0, ǫ, ii} dom, than the permutation leading to smallest error probability // (score, path, permutation index) of the proposed list decoding algorithm is added to P. Updated set P is used in searching for the next permutation. 6 for φ ← 0 to n − 1 do V. N UMERIC RESULTS 7 Ũ ← ∅ // list to be sorted Performance of the proposed algorithm was measured de- 8 foreach (M, û0φ−1 , i) ∈ U do pending on the list size L and number of initial permutations 9 S ← CalcS(û0φ−1 ) // penalty l. Figures 1, 2 were obtained by simulation of transmitting 10 if φ ∈ F (i) then φ−1 106 codewords of eBCH(256, 155, 28) code through additive 11 b ← GetFrozenBit(û n 0 , V (i) ) o Gaussian (AWGN) channel with binary phase-shift keying 12 Ũ ← Ũ ∪ hM + τ (b, S), (û0φ−1 , b), ii (BPSK) modulation. Permutations for the considered code were obtained by simulation with L = 64, Nmax = 1000 13 else n o and Eb /N0 = 5.5 dB. Curves entitled “hard” and “uncoded” 14 Ũ ← Ũ ∪ hM + τ (0, S), (û0φ−1 , 0), ii illustrate FER of bounded distance hard decision decoding and n o 15 Ũ ← Ũ ∪ hM + τ (1, S), (û0φ−1 , 1), ii transmission of uncoded data respectively. Figure 1 illustrates the dependence of error probability on the list size L. It can be seen, that the proposed algorithm 16 U ← GetBestPaths(Ũ , L) outperforms bounded distance decoder even on the list size 17 hM, û0n−1 , ii ← GetBestPaths(U , 1) L = 64 approximately by 0.125 dB. It can be seen, that performance gain grows almost linearly with increase of the 18 return PermuteInverse(û0 n−1 , πi ) list size: performance curve shifts to the left by ≈ 0.25 dB when L doubles. Figure 2 illustrates the dependence of error probability on The automorphism group of Reed-Muller codes is too large the size of permutation set P. It can be seen, that the most to test all possible permutations. Recall, that we consider significant gain is obtained by employing two permutations, permutations π(x) = M x + b, where M is non-singular. further increase of the set P provides significantly smaller Observe, that some permutations are equivalent in terms of gain. Moreover, large set P may lead even to performance successive cancellation decoding performance. That is, some degradation, since all permutations are processed within a permutations may only permute the order of computation of single list, and in average each permutation “occupies” some (8) and not change values of penalties computed at each fraction of available paths, which is limited. phase of the list decoding algorithm. These permutations were Summing up, permutation techniques can provide substan- described by Bardet et al. in [9] and have form π(x) = T x+b, tial performance gain, although this gain is determined mostly where T is non-singular lower triangular matrix. by the list size L. Performance gain grows linearly, while L increases exponentially. For the purpose of searching good set of permutations for the list decoding algorithm we propose to restrict the set of VI. C ONCLUSION possible permutations to the set of permutations π(x) = M x, To conclude, the proposed soft decision decoding algorithm which are not equivalent in terms of successive cancellation for eBCH codes provides performance gain compared to decoding. Two permutations π1 , π2 we call equivalent if bounded distance decoding. The proposed algorithm is based π1 (x) = T π2 (x), where T is non-singular lower triangular on the representation of eBCH codes as polar codes with matrix. dynamic frozen symbols, and uses SCL decoding with list This number is still too large to brute force every possible size L to jointly decode several permutations of an input noisy permutation, therefore we propose to pick permutations at vector. Decoding complexity is defined by the list size L and random. Each permutation is generated in the following way. equals to O(Ln log n). Appropriate choice of permutations can Let start with the zero permutation matrix M of size m. First sufficiently improve decoding performance, and can be done row of M is generated at random out of 2m − 1 possible non- using greedy algorithm. 10 0 L 64, l 6 [4] T. L. Tapp, A. A. Luna, X.-A. Wang, and S. B. Wicker, L 128, l 6 L 256, l 6 “Extended hamming and bch soft decision decoders for -1 L 512, l 6 L 1024, l 6 mobile data applications”, IEEE Transactions on Com- hard munications, vol. 47, pp. 333–337, 3 1999. 10 uncoded [5] I. Tal and A. Vardy, “List Decoding of Polar Codes”, 10-2 IEEE Transactions on Information Theory, vol. 61, pp. 2213–2226, 5 2015. FER [6] I. Dumer and K. Shabunov, “Soft-decision decoding of -3 10 Reed-Muller codes: Recursive lists”, IEEE Transactions on Information Theory, vol. 52, pp. 1260–1266, 3 2006. 10 -4 [7] P. Trifonov and V. Miloslavskaya, “Polar Subcodes”, IEEE Journal on Selected Areas in Communications, vol. 34, pp. 254–266, 2 2016, ISSN: 1558-0008. 10-5 3 3.5 4 4.5 5 5.5 6 [8] F. J. MacWilliams and N. J. A. Sloane, The Theory of Eb/N0, dB Error-Correcting Codes. North Holland, 1983, p. 782, ISBN : 9780444851932. Figure 1: Performance of the SCL permutation decoding with [9] M. Bardet, V. Dragoi, A. Otmani, and J. Tillich, “Alge- different list size L braic properties of polar codes from a new polynomial formalism”, 2016 IEEE International Symposium on In- 100 L 256, l 1 formation Theory (ISIT), pp. 230–234, 2016. L 256, l 2 L 256, l 3 L 256, l 4 L 256, l 5 -1 L 256, l 6 10 hard uncoded 10-2 FER 10-3 10-4 -5 10 3 3.5 4 4.5 5 5.5 6 Eb/N0, dB Figure 2: Performance of the SCL permutation decoding with different number of permutations l ACKNOWLEDGMENTS This work was supported by the Ministry of Science and Higher Education of Russian Federation, project (Goszadanie) no. 2019-0898. R EFERENCES [1] Y. Wu, “Fast chase decoding algorithms and architectures for reedsolomon codes”, IEEE Transactions on Informa- tion Theory, vol. 58, pp. 109–129, 1 2012. [2] N. Kamiya, “On algebraic soft-decision decoding algo- rithms for BCH codes”, IEEE Transactions on Informa- tion Theory, vol. 47, pp. 45–58, 1 2001, ISSN: 1557-9654. [3] C. Choi and J. Jeong, “Fast and scalable soft decision decoding of linear block codes”, IEEE Communications Letters, vol. 23, pp. 1753–1756, 10 2019.