-An algorithm for construction of binary 16 × 16 polarization kernels with polarization rate 0.51828 which admit low complexity processing is proposed. The considered processing algorithm exploits linear relationship of the considered kernels and Arikan transform. The proposed approach relies on restricted application of elementary row operations to Arikan transform matrix, which are chosen to have minimal impact on complexity of the window processing algorithm. The proposed construction resulted in relatively low number of kernels, which can be easily checked by computer-based search. Moreover, simulation results show that polar (sub)codes with obtained kernels can outperform polar codes with Arikan kernel, while having lower decoding complexity.
I. INTRODUCTION
Polar codes are a novel class of error-correcting codes,
which achieve the symmetric capacity of a binary-input
discrete memoryless channel W , have low complexity
construction, encoding and decoding algorithms [
Polarization is a general phenomenon, and is not restricted
to the case of Arikan matrix [
The window processing algorithm for some 16 × 16
polarization kernels was introduced in [
In this paper we present a construction method for polarization kernels, which admit efficient decoding by window based approach. The proposed method construct a class of polarization kernels, which are expected to be suitable for given processing method. The kernels are constructed by performing elementary row operations over Arikan transform matrix.
We show that with obtained kernels increasing list size in the SCL decoder provides much more significant performance gain compared to the case of Arikan kernel, and ultimately the proposed approach results in lower decoding complexity compared to the case of polar codes with Arikan kernel with the same performance.
Consider a binary-input memoryless channel with transition probabilities W {y|c}, c ∈ F2, y ∈ Y, where Y is output alphabet. For a positive integer n, denote by [n] the set of n integers {0, 1, . . . n − 1}. A polarization kernel K is a binary invertible l × l matrix, which is not upper-triangular under any column permutation. The Arikan kernel is given by Fm = where ⊗m is m-fold Kronecker product of matrix with itself.
An (n = lm, k) polar code is a linear block code generated by k rows of matrix Gm = M (m)K⊗m, where M (m) is a digit-reversal permutation matrix, corresponding to mapping Pim=−01 tili → Pim=−01nt−m1−G1m−i,liw,thie∈re[ul]i., Tih∈e Fenacroedisnegt tsochsoemmee is given by c0n−1 = u0 pre-defined values, e.g. zero (frozen symbols), |F | = n − k, and the remaining values ui are set to the payload data.
It is possible to show that a binary input memoryless
channel W together with matrix Gm gives rise to bit subchannels
W m(i,)K (y0n−1, ui0−1|ui) with capacities approaching 0 or 1,
and fraction of noiseless subchannels approaching I(W ) [
W m(i,)K (ui0|y0n−1) =
W m(i,)K (y0n−1, ui0−1|ui) 2W (y0n−1) n−1 = X Y W ((u0n−1Gm)i|yi).
uin+−11 i=0
(1)
Let us further define W(mj)(uj0|y0n−1) = W m(j,)K (uj0|y0n−1),
where kernel K will be clear from the context. We also need
where θK [u(0s+1)l−1, j]r = (ull(rr+1)−1Gm)j , r ∈ [s + 1].
A trellis-based algorithm for computing these values was
presented in [
At the receiver side, one can successively estimate ui = b
the frozen value of ui (arg maxui∈F2 W(mi)(ubi0−1.ui|y0n−1), i ∈/ F , i ∈ F .
(3) This is known as the successive cancellation (SC) decoding algorithm.
Let W : {0, 1} → Y be a symmetric binary-input discrete memoryless channel (B-DMC) with capacity I(W ). By definition,
I(W ) = X
Also, let Z(W ) ∈ [
Consider polarizing transform K⊗m, where K is an l×l
polarization kernel, and bit subchannels W m(i,)K (y0n−1, ui0−1|ui),
induced by it. Let Zm(i) = Z(W m(i,)K (y0n−1, ui0−1|ui)) be a
Bhattacharyya parameter of i-th subchannel, where i is uniformly
distributed on the set [lm]. Then, for any B-DMC W with
0 < I(W ) < 1, we will say that an ℓ × ℓ matrix K has
polarization rate E(K) if [
n→∞ (ii) For any fixed β > E(K), lim inf Pr[Zn ≥ 2−ℓnβ ] = 1.
n→∞
That is, the rate of polarization shows how fast bit subchannels of K⊗m approach neither almost noiseless or noisy channel with n = lm.
Suppose we constructed (n, k) polar code C with kernel K.
Let Pe(n) be a block error probability of C under transmission
over W and decoding by SC algorithm. It was proven [
Pe(n) ≤ 2−nβ
Di = dH (K[i], hK[i + 1], . . . , K[l − 1]i), i = 0, . . . , l − 2,
The vector D will be referred to as a partial distances
profile. In work [
l i=0 (4)
The Arikan kernel F1 has rate of polarization E(F1) = 0.5, whereas random codes achieve E = 1. For polarization kernels of size 16 and 32 the kernels with rate of polarization 0.51828 and 0.53656 respectively can be obtained.
Let us fix a B-DMC W of capacity I(W ) and a desired
block error probability Pe. Given W and Pe, suppose we wish
to communicate at rate I(W )−Δ using a family of (n, k) polar
codes with kernel K. It has been shown that this value of n
scales as O(Δ−µ (K)), where the constant µ (K) is known as
the scaling exponent [
The scaling exponent depends on channel. Unfortunately,
the algorithm of its computing is only known for the case on
binary erasure channel (BEC) [
The Arikan kernel F1 has µ (K) = 3.627, whereas random
codes achieve optimal µ = 2. The best known scaling
exponent for 16 × 16 polarization kernel is 3.346 [
1) General case: Our goal is to compute probabilities W(mi)(ui0|y0n−1) for a given polarization transform K⊗m. Let us assume for the sake of simplicity that m = 1. The corresponding task will be referred to as kernel processing.
We propose to introduce approximate probabilities W(j) f 1 (uj0|y0l−1) = max W(l−1)(ul0−1|y0l−1) ulj−+11 1
l−1 = max Y W ((ul0−1K)i|yi).
ulj−+11 i=0 (5) probabilities Wt(j)(uj0|y0l−1) = W1(,jF)t (uj0|y0l−1) for Arikan matrix Ft. Due to the recursive structure of Gm, one has The partial distances Di, i = 0, . . . , l − 1, l × l of the matrix K are defined as follows:
It turns out that the rate of polarization is independent of
channel W . Namely, let hg1, g2, . . . , gki be a linear code,
generated by vectors g1, g2, . . . , gk. Let dH (a, b) be the Hamming
distance between a and b. Let dH (b, C) = minc∈C dH (b, c) be
a minimal distance between vector b and linear block code C.
We denote the i-th row of an l × l matrix M as M [i], i ∈ [l].
This is the probability of the most likely continuation of path
uj0 in the code tree, without taking into account possible
freezing constraints on symbols ui, i > j. Note that the
same probabilities were introduced in [
Decoding can be implemented using the log-likelihood ratios S¯m,i = S¯(mi)(ui−1|y0n−1) = ln WW((mmii))((uuii−−11..01||yy00nn−−11)) . Hence, 0 00 kernel output LLRs S¯1,i, i ∈ [l] can be approximated by
W(i) S¯1,i ≈ S1,i = ln f 1 (ui0−1.0|y0l−1)
W(i) f 1 (ui0−1.1|y0l−1) = muli−a+x11 ln W(l−1)(u(0)i|y0l−1) − muli−a+x11 ln W(l−1)(u(1)i|y0l−1), 1 1 where u(a)i = (ui0−1.a.uli−+11). The above expression means that S1,i can be computed by performing ML decoding of the code, generated by last l−i+1 rows of the kernel K, assuming that all uj, i < j < l, are equiprobable.
2) Window processing: Straightforward evaluation of (6) for arbitrary kernel has complexity O(2ll). However, we have a simple explicit recursive procedure for computing these values for the case of the Arikan transform Ft.
Let l = 2t. Consider encoding scheme cl−1 = v0l−1Ft.
0 Similarly to (5), define approximate probabilities and modified log-likelihood ratios
Wft(i)(v0i|y0l−1) = max Wt(l−1)(v0l−1|y0l−1)
vil+−11 St(i)(v0i−1, y0l−1) = log Wft(i)(v0i−1.0|y0l−1) .
Wft(i)(v0i−1.1|y0l−1)
S(2i)(v02i−1, y0N−1) = sgn(a) sgn(b) min(|a|, |b|)
λ S(2i+1)(v02i, y0N−1) =(−1)v2i a + b,
λ where N
= 2λ, a = Sλ(i−) 1(v02,ie−1 ⊕ v02,io−1, y0N,e−1), b = Sλ(i−) 1(v02,io−1, y0,o
N−1). Then the log-likelihood of a path v0i can
be obtained as [
R(v0i|y0l−1) = log Wft(i)(v0i|y0l−1)
= R(v0i−1|y0l−1) + τ St(i)(v0i−1, y0l−1), vi , (10) where R(ǫ|y0l−1) can be set to 0, ǫ is an empty sequence, and τ (S, v) = (0,
sgn(S) = (−1)v −|S|, otherwise.
It was suggested in [
0 0 0
Observe, that it is possible to reconstruct ui0 from v0τi , where
τi is the position of the last non-zero symbol in the i-th column
of T . For the sake of simplicity we assume that all τi, i ∈ [l]
are distinct. The general case is considered in [
Indeed, vectors ul0−1 and v0l−1 satisfy the equation ui = where Zj is the set of vectors v0hj , such that (11) holds for i ∈ [j]. Similarly we can rewrite the above expression for the case of the approximate probabilities
Observe that computing these values requires considering multiple vectors v0hi of input symbols of the Arikan transform Ft. Let
Di = [hi + 1]\{τ0, τ1, . . . , τi} (15) be a decoding window, i.e. the set of indices of independent (from ui0−1) components of v0hi . Note that |Di| = |[hi + 1]| − |{τ0, τ1, . . . , τi}| = hi + 1 − (i + 1) = hi − i since all τi are distinct and {τ0, τ1, . . . , τi} ⊆ [hi + 1]. The calculation of LLRs S1,i via (14) will be referred to as the window processing algorithm.
The number of path scores to be computed in (14), which determines the processing complexity, is equal to 2|Di|+1. Let M(K) denotes the maxi∈[l] |Di|. In general, one has M(K) = O(l) for an arbitrary kernel K.
3) Complexity: The complexity of LLR S1,i computation via the straightforward implementation of the window processing algorithm (14) consist of the several components. In this work we count the arithmetical complexity as a number summation and comparison operations, which is considered to be equal.
At first, to compute S1,i, one should obtain path scores R(v0hi |y0l−1), v0hi ∈ Zi. According to the expression (10), the path score R(v0hi |y0l−1) is equal to
R(v0hi−1|y0l−1) + τ S(hi)(v0hi−1, y0l−1), vi .
t
If one stores the intermediate results of (8) and (9), then
the complexity of computing S(hi) = S(hi)(v0hi−1, y0l−1) is
t t
1The method given in [
Totally, 2|Di| LLRs S(hi) should be computed. Then, for
t
LLR S(hi) and vi ∈ [
In total, the complexity of path scores R(v0hi |y0l−1), v0hi ∈ Zi, calculation is given by Λ(i) = (2h−i(2B(h) − 1) + 2h−i) = 2h+B(h)−i hi
X hi−1+1 hi
X hi−1+1 and h−1 is assumed to be −1.
To complete the LLR S1,i computation, the corresponding maximum of path scores should be computed, which requires 2|Di|+1 comparisons.
Note that in the case of hi = hi−1 we assume that all path scores are stored together with corresponding partial maximums, thus, one substraction needed only.
In sum, the complexity of the straightforward implementation of the window processing algorithm for kernel K can be estimated as l−1 Ψ(K ) = X Φ(i),
i=0 (2hi−i+1 + Λ(i), where
III. CONSTRUCTION OF POLARIZATION KERNELS
Our goal is to construct polarization kernels with
polarization rate greater that 0.5, which admit low complexity
processing. Such rate of polarization rate can be achieved for
kernels of size l = 16 and l ≥ 23 [
The maximum rate of polarization among 16 × 16 kernels is equal to 0.51828, which can be achieved by the kernel with the partial distances profile
D(∗) = [
There are polarization kernels with partial distance profile which corresponds to some permutation of D(∗), what will be demonstrated later, but the complete list of such permutations is unknown. Therefore, it is convenient to begin our investigation with kernels with monotonic increasing partial distances.
The minimization of the complexity (16) by the exhaustive search among all polarization kernels K of size 16 × 16 and partial distances D(∗) is intractable. Therefore, we are going to significantly reduce the search space to some restricted class of polarization kernels, which are expected to have moderate Ψ(K ).
Recall that τi is the position of the last non-zero symbol in the i-th column of T = FtK −1, hi = maxi′∈[i+1] τi′ and |Di| = hi − i.
It can be seen, that the value of hi − i increases once τi > i appears in T , therefore the heuristic minimization of Ψ(K ) can be done with minimization of |τi − i|, i ∈ [l].
The minimal value of |τi − i| = 0 is achieved by Arikan transform Ft. The kernel with partial distances D(∗) can be derived by performing elementary operations over rows space of F4, since F4 is invertible.
The partial distance profile of the Arikan transform F4 is given by
D(F4) = [
Hence, we can begin construction procedure with row permutation of the matrix F4 .
Let Pρ be a permutation matrix, which corresponds to the permutation ρ =
0 ρ(0)
1 ρ(1) . . . . . .
14 ρ(14) ρ(1155) . (16)
For convenience, we enumerate elements of ρ from zero unlike standard notation. For brevity we will write ρ as [ρ(1), ρ(2), . . . , ρ(16)]. Consider the kernel Kρ = PρF4, consequently,
T = F4Kρ−1 = F4(PρF4)−1 = PρT .
Thus, τi, i ∈ [l] are given by ρ(i). Therefore, the processing complexity for Kρ directly depends on the permutation ρ.
We start our construction with permuted Arikan kernels Kβ given by permutations
β = [0, 1, 2, 4, 8, w0, w1, w2, w3, w4, w5, 7, 11, 13, 14, 15],
where w is an arbitrary permutation of the vector
[
D(4) = [
For instance, the permutation
σ = [
To transform the kernel Kβ into the kernel with partial
distance D(∗), one should sum rows of Kβ. It is proven [
The addition of two rows can also increase the maximal size of the decoding windows. Indeed, let Xi,j be an elementary matrix which corresponds to addition of row i to row j. In other words, Xi,j is an identity matrix with Xi,j [j, i] = 1. Then
K = Xi,j PρF4 ⇒ T = PρT Xi,j , which means that the column j has been added to the column i of the matrix PρT Xi,j . After row addition in K, τi = max(τi, τj ), which can increase the τi − i. It can lead to increasing of the size of the corresponding decoding window. It means that one should use addition matrices Xi,j with as small as possible values |j − i|.
To keep the processing complexity as small as possible, we suggest to sum only rows Kβ[i], i ∈ {5, 6, 7, 8, 9, 10} to each other. These rows have a Hamming weight 4. It was shown that sum x of these rows can produce vectors of weight ≥ 6 and, furthermore, there exist several x such as
dH (x, hKβ [
Let M = {3, 5, 6, 9, 10, 12}. We propose to minimize the
decoding window processing complexity over set K of 16×16
kernels, which is given by following constraints on kernel K:
• K[i] = Kβ[i], i ∈ {0, 1, 2, 3, 4, 11, 12, 13, 14, 15},
• K[
It is easy to observe, that the proposed construction can produce kernels with partial distances distinct from D(∗) and even to singular matrices. However, one does not need to compute the complete partial distance profile D for K ∈ K, because the kernel K can be dropped once its partial distance does not match the D(∗). Of course, there are a lot of possible methods for reduction of K, however, there is no need for them since computer-based search over K runs in several minutes.
IV. NUMERIC RESULTS
results in set K∗ of 60480 16 × 16 polarization kernels K with E(K) = 0.51828. For each K in K∗ we compute its complexity Ψ(K). Moreover, we also computed the BEC scaling exponent µ (K) for each kernel. The scaling exponent K1, E = 0.51828, µ = 3.346 K2, E = 0.51828, µ = 3.45 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 also affects on the error correction performance, so we write the minimal processing complexity for kernel with different scaling exponent.
Table I demonstrates all occurred scaling exponents of kernels from the set K∗ together with minimal processing complexity. Furthermore, for each presented scaling exponent the kernel K with M(K) = 4 is provided. It can be seen that the minimal complexity of 660 operations is provided by kernels with µ (K) = 3.363 and kernels with the lowest µ (K) = 3.346 requires the maximal complexity among other scaling exponents.
It turns out, that the complexity of window processing
can be significantly reduced. For instance, the kernel K1,
illustrated in Figure 1, K1 ∈ K∗, µ (K1) = 3.346, was reported
in [
For comparison, the general trellis-based algorithm [
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 KBCH = 11 00 00 10 11 01 00 10 01 00 00 00 00 00 00 00 , 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 1 1 0 0 1 0 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 1 0 1 1 0 0 1 0 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
with E(KBCH ) = 0.51828 and µ (KBCH = 3.396),
which consist of the sequence of nested generator matrices
of extended BCH codes, has M(KBCH ) = 12 and the
processing complexity Ψ(KBCH ) = 72563. Whereas the
algorithm [
we showed how to find kernels of size 16 with monotonic partial distance profile D(∗). It resulted in kernels with the M(K ) = 4. For further complexity reduction we are going to perform row permutations over row space of the obtained kernels, which preserves the polarization rate.
Given kernel K , the value M(K ) can be reduced by row permutation of K . By step-by-step exchange of the kernel rows, we performed an heuristic search of row permutation, which preserve the polarization rate of K1.
Table II demonstrates the properties of kernels which we obtained by permutations of the kernel K1. It can be observed, that higher scaling exponent requires lower processing complexity, furthermore, the maximal size of the decoding windows can be also reduced for kernels with polarization rate 0.51828. For instance, the kernel K2, illustrated in Figure 1, has E(K2) = 0.51828, µ (K ) = 3.45 and M(K ) = 3. The kernel K2 is given by ρ¯K1, where
ρ¯ = [
D¯ = [
Unfortunately, we do not have a proof that the kernel K2 admits minimum possible complexity of window processing algorithm among all 16 × 16 polarization kernels with polarization rate 0.51828.
We constructed (4096, 2048) polar codes with kernels K1 and K2, obtained by the proposed construction, and investigated their performance for the case of AWGN channel with BPSK modulation. The sets of frozen symbols were obtained by Monte-Karlo simulations.
Figure 2 illustrates the performance of plain polar codes
and polar subcodes [
Eb/N0, dB 1.2 1.4 1.8 2 2.2 E(K1) = E(K2) = 0.51828 provide significant performance gain compared to polar codes with Arikan kernel. Moreover, polar subcodes with kernels K1, K2 under SCL with L = 8 have almost the same performance as polar subcodes with Arikan kernel under SCL with L = 32. Observe also that the codes based on kernels with lower scaling exponent exhibit better performance despite of the fact that scaling exponent is computed for the BEC.
Figure 3 presents simulation results for (4096, 2048) polar
subcodes with different kernels under SCL with different L
at Eb/N0 = 1.25 dB. It can be seen that the kernels with
polarization rate 0.51828 require significantly lower list size
L to achieve the same performance as the code with the
Arikan kernel. Moreover, this gap grows with L. This is due to
improved rate of polarization, which results in smaller number
of unfrozen imperfectly polarized bit subchannels. The size of
the list needed to correct possible errors in these subchannels
grows exponentially with their number (at least for the
genieaided decoder considered in [
1x106 Number of arithmetical operations 1x107 scaling exponent gives better performance with the same list L, but the slope of the curve remains the same for both kernels K1, K2.
Figure 4 presents the same results in terms of the actual
decoding complexity. Recall that proposed kernel processing
algorithm uses only summations and comparisons. The SCL
algorithm was implemented using the randomized order
statistic algorithm for selection of the paths to be killed at each
phase, which has complexity O(L). Observe that the polar
subcode based on kernel K2 can provide better performance
with the same decoding complexity for FER ≤ 8 · 10−3. This
is due to higher slope of the corresponding curve in Figure
3, which eventually enables one to compensate relatively high
complexity of the LLR computation algorithm presented in
[
Unfortunately, K1 kernel, which provides lower scaling exponent, has greater processing complexity than K2, so that its curve intersects the one for the Arikan kernel only at FER= 2 · 10−3.
V. CONCLUSIONS
In this paper the construction method for 16 × 16 polarization kernels with polarization rate 0.51828 were proposed. These kernels admits low complexity decoding by window processing algorithm. The construction method performs elementary operations over row space of the Arikan transform matrix. These elementary operations are chosen to have minimal impact on the complexity of the window processing algorithm.
It was shown that in the case of SCL decoding with sufficiently large list size, the constructed kernels results in lower decoding complexity compared to the case of polar (sub)codes with Arikan kernel with the same performance.
Extension of the proposed construction to the case of kernels with larger size remains an open problem.