-BCH codes are used in many applications, including optical transport networks, flash memory and video broadcasting. This paper introduces soft decision permutation decoding algorithm for extended BCH codes based on its' representation as polar codes with dynamic frozen symbols. The proposed algorithm outperforms bounded distance hard decision decoding and provides flexible tradeoff between performance and decoding complexity.
Bose-Chaudhuri-Hocquengham ( BCH) codes are still extensively used in many practical applications, such as optical transport networks, flash memory and video broadcasting. A BCH code with constructive minimum distance δ can be decoded using bounded distance hard decision decoders, which can correct t = ⌊ δ−1
2 ⌋ errors.
Several one-pass schemes of Chase decoding were proposed [1], which evaluate error-locator polynomials for all test vectors using a single pass of the Berlekamps’ algorithm. A good overview of various soft decision algebraic decoding methods developed for BCH codes is given in [2].
Other soft decision decoding methods based on Viterbi and ordered statictics decoding algorithms can provide maximumlikelihood decoding at cost of substantial increase in decoding complexity [3], [4].
In this paper a soft-input decoding algorithm based on successive cancellation decoding for primitive extended BCH codes is presented. It uses the representation of extended BCH codes as polar codes with dynamic frozen symbols, and employs permutation decoding techniques to enhance performance.
The proposed decoding algorithm is based on the successive cancellation list decoder developed in [5] for polar codes, and provides a flexible tradeoff between decoding performance and complexity. Simulations show, that the proposed decoder performs better than hard-decision decoder, however it does not guarantee bounded distance decoding of BCH codes.
In this paper we consider extended primitive narrow-sense BCH codes (eBCH codes) over F2. Generator polynomial of a BCH code of length n = 2m − 1 with constructive minimum distance δ has roots α, α2, . . . , αδ−1, where α denotes primitive element of GF(2m).
Hence, the check matrix of eBCH(2m, k, d ≥ δ) code is defined as a binary image of the matrix
H = 10... 11... α1... α1...2 ......... αn1...−1 0 1 αδ−2 α2(δ−2) ... α(n−1)(δ−2) , 0 1 αδ−1 α2(δ−1) ... α(n−1)(δ−1) (1) where all linearly dependent rows are eliminated.
It can be seen that BCH codes are closely related to ReedMuller and polar codes. Polar (n, k) code is defined as a set of vectors
C = u0n−1A⊗m | u0n−1 ∈ F2n, ui = 0, ∀i ∈ F , (2) where A = ( 11 01 ), ⊗m denotes m-times Kronecker product of the matrix A with itself, and F , |F | = k denotes set of frozen symbols, which depends on a transmission channel.
A Reed-Muller code of length 2m and order r can be defined as a special case of polar codes:
RM(r, m) = u0n−1A⊗m | ui = 0, ∀i : wt(i) < m − r , (3) where wt(i) denotes Hamming weight of the index.
Both polar and Reed-Muller codes can be decoded using successive cancellation (SC) algorithm. Suppose, that the codeword of (n = 2m, k) polar (or Reed-Muller) code c0n−1 = u0n−1A⊗m is transmitted through the channel W with transition probabilities W (y| x), and the noisy vector y0n−1 is passed to the decoder.
The decoding algorithm is based on recursive computation of transition probabilities
Wi(y0n−1, ui0−1| ui) ,
X uin+−11∈F2n−i−1 uˆφ =
0, φ ∈ F .
At the receiver end symbols uˆφ, φ = 0, . . . , n − 1 can be estimated one by one: (arg maxuφ∈F2 Wφ(y0n−1, uˆ0φ−1| uφ), φ 6∈ F (5)
Due to the recursive structure of the matrix A⊗m encoding and decoding can be done in O(n log n) operations. A. Successive cancellation list decoding algorithm
Unfortunately, SC decoding of polar codes of moderate lengths leads to rather poor performance, since the estimates uˆφ are computed without taking into account frozen symbols ui, i > φ, i ∈ F . However, performance of the SC algorithm can be enhanced by considering several possible paths uˆ0n−1 in the code tree.
This approach is used in the successive cancellation list (SCL) decoding algorithm introduced by Tal and Vardy [5]. Interestingly, the same idea was described earlier by Dumer and Shabunov in their work [6] devoted to the decoding of Reed-Muller codes. Below we revise the min-sum version of the SCL algorithm.
The SCL decoder successively extends L vectors uˆ0φ of equal length trying to maximize their score where
M (uˆ0φ, y0n−1) = φ X τ (uˆi, Sm(i)(uˆi0−1, y0n−1)), i=0 τ (u, S) = (0, if (−1)u = sgn(S)
−| S| , otherwise is the penalty function. Sm(i)(uˆi0−1, y0n−1) denotes the loglikelihood ratio given by
S(2φ)(uˆ02φ−1, y0n−1) = sgn(a) sgn(b) min(| a| , | b| ), λ S(2φ+1)(uˆ02φ, y0n−1) = (−1)uˆ2φ a + b,
λ where n = 2m−λ, a = Sλφ−S1((uiˆ)02,φe−1 + uˆ02,φo−1, y0n/2−1), b = Sλ(φ−)1(uˆ02,φo−1, ynn/−21−1), and 0 = log W(yi| 0) − log W(yi| 1). Here uˆ0φ,o and uˆ0φ,e denote subvectors of uˆ0φ consisting of elements on odd end even indices respectively. The list size L defines the complexity O(Ln log n) of the decoding. (6) (7) (8) (9)
Observe, that automorphism group of Reed-Muller codes contains general affine group [8]. In other words, it can be shown that any permutation of symbols in a codeword π(x) = M x + b, where x is a binary representation of a bit index (coordinate), and M is non-singular matrix, defines an automorphism of a Reed-Muller code.
It was proposed in [6] to initialize the SCL decoder with several permutations of a codeword to further enhance decoding performance. We propose to apply this idea to the decoding of eBCH codes.
Let consider a eBCH(n, k, d) code C and its check matrix H defined as it was shown in equation (1). Consider a permutation taken from automorphism group of the corresponding Reed-Muller supercode R, C ⊆ R. This permutation applied to H defines an equivalent code C′, which may not be equal to C, although C′ ⊆ R. Since C′ is also included in R, representations of C and C′ as polar codes will have similar sets of frozen symbols F . For instance, Theorem 2 is still valid for equivalent codes obtained that way, and performance of successive cancellation decoding doesnt’ differ much.
The algorithm Decode illustrates the proposed method.
Main parameters of the algorithm are list size L, and the set of permutations P = { π0, . . . , πl} of size l. Note that each permutation of P also defines permutation on the check matrix H of the considered eBCH code. Hence, permutation may share different sets of frozen symbols F and different constraint matrices V .
In line 1 the constraint matrix V (i) and set of frozen symbols F (i) are evaluated for each permutation πi as it was described in section II-B. Permuted input vector of log-likelihood ratios S0 = (S0(0), . . . , S0(μn −1)) is used to initialize paths with indices i = 0, . . . , l − 1 in line 4. In line 5 list U is filled with these paths.
The list U consists of triplets hM, uˆ0φ−1, ii, which define paths considered by the decoder on iteration φ. Here M denotes a path score, uˆ0φ−1 is a vector of bits estimated on previous phases, and i is a permutation index.
The main decoding loop starts with line 6. In line 9 values Sm(i)(uˆi0−1, y0n−1) are computed according to (6)–(8), and set of continuations U˜ is constructed.
Function GetBestPaths(U , L) returns L continuations with highest scores from the set U . Selected continuations are passed to the next decoding iteration.
The decoder terminates when phase φ = n is reached, and path uˆ0n−1 ∈ U with the highest score is returned.
The complexity of the proposed algorithm is determined by SCL decoding and equals to O(Ln log n).
B. Dynamic frozen symbols
It was shown in [7], that any (n = 2m, k, d) code with check matrix H can be represented as a polar code with dynamic frozen symbols. Let denote Am = A⊗m, where A = ( 11 01 ).
Since A−m1 = Am, it is possible to choose matrices V and W , such that H = V ATm and cn−1HT = un−1W V T = 0.
0 0 Hence, some symbols ui, i ∈ F can be set to predefined linear functions of previous symbols, i.e.
uji =
X Vi,sus, 0 ≤ i < n − k, s<ji where V ∈ F2n−k× n is a constraint matrix and ji is the maximal index of the non-zero element of the row Vi,−.
Encoding can be done by evaluation of c0n−1 = un−1W Am,
0 where W ∈ F2n× n, W V T = 0 is a precoding matrix.
Note, that for eBCH(2m, k, d > δ) code the number of dynamic frozen symbols of weight t equals to the total number IV. CHOOSING THE SET OF PERMUTATIONS 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. 13 14 15 16
U ← GetBestPaths( U˜ , L) 17 hM, uˆ0n−1, ii ← GetBestPaths(U , 1) 18 return PermuteInverse(uˆ0n−1, πi)
Procedure Decode(L, P, S0) input : list size L of the decoder, set of permutations P = { π0, . . . , πl} , log-likelihood ratios S0 = (S0(0), . . . , S0(μn −1)) output: estimated bits uˆ0n−1 1 for i ← 0 to l − 1 do
(V (i), F (i)) ← GetConstraintMatrix(πi) 2 U ← ∅ 3 for i ← 0 to l − 1 do 4 InitPath(Permute(S0, πi), i) 5 U ← U ∪ {h 0, ǫ, ii}
// (score, path, permutation index)
U˜ ← U˜ ∪ nhM + τ (0, S), (uˆ0φ−1, 0), ii U˜ ← U˜ ∪ nhM + τ (1, S), (uˆ0φ−1, 1), ii o o
The automorphism group of Reed-Muller codes is too large to test all possible permutations. Recall, that we consider permutations π(x) = M x + b, where M is non-singular.
Observe, that some permutations are equivalent in terms of successive cancellation decoding performance. That is, some permutations may only permute the order of computation of (8) and not change values of penalties computed at each phase of the list decoding algorithm. These permutations were described by Bardet et al. in [9] and have form π(x) = T x+b, where T is non-singular lower triangular matrix.
For the purpose of searching good set of permutations for the list decoding algorithm we propose to restrict the set of possible permutations to the set of permutations π(x) = M x, which are not equivalent in terms of successive cancellation decoding. Two permutations π1, π2 we call equivalent if π1(x) = T π2(x), where T is non-singular lower triangular matrix.
This number is still too large to brute force every possible permutation, therefore we propose to pick permutations at random. Each permutation is generated in the following way.
Let start with the zero permutation matrix M of size m. First row of M is generated at random out of 2m − 1 possible nonzero binary vectors. Second row of M is generated such that it doesnt’ end in the same column as the first row. Third row shouldnt’ end in the same columns as first and second rows and so on. The total number of possible permutations therefore is reduced to Qim=1 2i − 1.
We start with a single permutation, which corresponds to the standard bit ordering of the check matrix H. That is, the binary representation of the second row in (1) corresponds to the vector (0, 1, 2, . . . , 2m − 1).
Other permutations are chosen iteratively: for a fixed signal to noise ratio Nmax permutation matrices are generated at random, than the permutation leading to smallest error probability of the proposed list decoding algorithm is added to P. Updated set P is used in searching for the next permutation.
Performance of the proposed algorithm was measured depending on the list size L and number of initial permutations l. Figures 1, 2 were obtained by simulation of transmitting 106 codewords of eBCH(256, 155, 28) code through additive Gaussian (AWGN) channel with binary phase-shift keying (BPSK) modulation. Permutations for the considered code were obtained by simulation with L = 64, Nmax = 1000 and Eb/N0 = 5.5 dB. Curves entitled “hard” and “uncoded” illustrate FER of bounded distance hard decision decoding and 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 outperforms bounded distance decoder even on the list size L = 64 approximately by 0.125 dB. It can be seen, that performance gain grows almost linearly with increase of the 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 size of permutation set P. It can be seen, that the most significant gain is obtained by employing two permutations, further increase of the set P provides significantly smaller gain. Moreover, large set P may lead even to performance degradation, since all permutations are processed within a single list, and in average each permutation “occupies” some fraction of available paths, which is limited.
Summing up, permutation techniques can provide substantial performance gain, although this gain is determined mostly by the list size L. Performance gain grows linearly, while L increases exponentially.
To conclude, the proposed soft decision decoding algorithm for eBCH codes provides performance gain compared to bounded distance decoding. The proposed algorithm is based on the representation of eBCH codes as polar codes with dynamic frozen symbols, and uses SCL decoding with list size L to jointly decode several permutations of an input noisy vector. Decoding complexity is defined by the list size L and equals to O(Ln log n). Appropriate choice of permutations can sufficiently improve decoding performance, and can be done using greedy algorithm. 10-5 3 100 10-1 10-2 R E F 10-3 10-4 10-5 3
Y. Wu, “Fast chase decoding algorithms and architectures for reedsolomon codes”, IEEE Transactions on Information Theory, vol. 58, pp. 109–129, 1 2012.
N. Kamiya, “On algebraic soft-decision decoding algorithms for BCH codes”, IEEE Transactions on Information Theory, vol. 47, pp. 45–58, 1 2001, ISSN: 1557-9654. 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.