Minimum-Distance Based Construction of Multi-Kernel Polar Codes
Valerio Bioglio Frederic Gabry Ingmar Land Jean-Claude Belfiore





 

Minimum-Distance Based Construction of Multi-Kernel Polar Codes
    Valerio Bioglio, Frédéric Gabry, Ingmar Land, Jean-Claude Belfiore
Mathematical and Algorithmic Sciences Lab
 France Research Center, Huawei Technologies France SASU

Email: {valerio.bioglio,frederic.gabry,ingmar.land, jean.claude.belfiore}@huawei.com
    January 2017
===============================================================================================================================================================================================================================================================




In this paper, we propose a construction for multi-kernel  polar codes based on the maximization of the minimum distance. 

Compared to the original construction based on density evolution, our new design shows particular advantages for short code lengths, where the polarization effect has less impact on the performance than the distances of the code.  We introduce and compute the minimum-distance profile and provide a simple greedy algorithm for the code design.  Compared to state-of-the-art punctured or shortened Arikan polar codes, multi-kernel polar codes with our new design show significantly improved error-rate performance.








§ INTRODUCTION


Polar codes, introduced by Arikan in <cit.>, are a new class of channel codes which achieve capacity over various classes of channels under low encoding and decoding complexity.  Also for finite-lengths, these codes show remarkable error rate performance under list decoding.  Only seven years after their discovery, polar codes were recently adopted in the standardization for the control channel of the future 5G system, where the focus is on short-length codes. 

In their original construction, polar codes are based on the polarization effect of the Kronecker powers of the 2 × 2 kernel matrix
T_2 = [ 1 0; 1 1 ].
The generator matrix of a polar code is then a sub-matrix of the transformation matrix T_2^⊗ n. 
Arikan conjectured in <cit.> that the polarization effect is not restricted to powers of the kernel T_2, which was verified in <cit.>, where the authors provide necessary and sufficient conditions for binary kernels T_p of size p × p, p>2, to allow for the polarization effect. 
Recently, polar codes based on larger kernels were proposed in <cit.>, while in <cit.> authors propose to use different kernels of the same size to construct the transformation matrix of the code.

Thanks to these ideas, it is now possible to construct polar codes of any code length of the form N = p^n.
However, not all code lengths can be expressed as powers of integers.  To overcome this length matching problem, puncturing <cit.>, <cit.> and shortening <cit.> techniques have been proposed to construct polar codes of arbitrary lengths, at the cost of a loss in terms of polarization speed, and hence worse error rate performance.  

To tackle the code length problem of polar codes, a multi-kernel construction has been proposed in <cit.>. 
By mixing binary kernels of different sizes in the transformation matrix, codes of lengths that are not only powers of integers can be constructed. 
The resulting multi-kernel polar code still benefits from the polarization effect while decoded through successive cancellation <cit.>. 
As a result, the new multi-kernel construction largely increases the number of code lengths that can be achieved without puncturing or shortening, with comparable or even better error-rate performance.

For codes based on the polarization effect, the reliability of the input positions is determined by density evolution or other techniques, and then the least reliable positions are frozen. 
This is the design principle of the original construction of polar codes of infinite length <cit.>, and it is similarly used for the design of multi-kernel polar codes <cit.>.  
Such design by reliability is appropriate for long codes under successive cancellation decoding; for short codes under list decoding <cit.>, however, design principles that give more weight to distance properties may give superior error-rate performance. 
Related to this is the work in <cit.>, where reliability-based design of polar codes for better channels is shown to lead to better distance properties, and ultimately to Reed-Muller codes. 

In this paper, we propose a construction of multi-kernel polar codes that maximizes the minimum distance.    
We show how to find kernels of size larger than 2 that are advantageous in our construction. 
Moreover, we present a simple greedy code design algorithm that maximizes the minimum distance for given kernels. 
Due to the special structure of the kernels of larger size and the resulting flexibility in the code design, our construction of multi-kernel polar codes leads to better distance properties and thus to superior error rate performance under successive cancellation list decoding, compared to the reliability-based construction, and also compared to shortened or punctured codes based on T_2^⊗ n.

This paper is organized as follows. 
In Section <ref>, we review construction, encoding, and decoding of multi-kernel polar codes. 
In Section <ref> we describe explicitly the new distance-based design for multi-kernel polar codes. 
In Section <ref> we illustrate numerically the performance of the codes, and Section <ref> concludes this paper. 






§ MULTI-KERNEL POLAR CODES


In this section, we briefly review the structure, encoding and decoding of multi-kernel polar codes; 
for details, we refer the reader to <cit.>. 
Multi-kernel polar codes are a generalization of the Arikan polar codes <cit.>, simply referred to as polar codes throughout the paper, and therefore we will provide a comparison to the Arikan construction for clarity.




 §.§ Code Structure and Encoding


Polar codes are based on the Kronecker product G_N = T_2^⊗ n, N=2^n, where T_2 denotes the 2 × 2 kernel

    T_2 = [ 1 0; 1 1 ] .

Let us assume an information set ℐ⊂ [N], [N] = {0,1,…,N-1}, of size |ℐ| = K and a corresponding frozen set ℱ = [N] \ℐ of size |ℱ| = N-K. 
An (N,K) polar code of length N and dimension K is then defined by the encoder x = u   G_N, mapping the input vector u ∈2^N to the codeword x ∈2^N, where u_i = 0 for i ∈ℱ, denoting the frozen bits, and u_i, i ∈ℐ, are the information bits.

Multi-kernel polar codes generalize this construction by mixing binary kernels of different sizes in the Kronecker product forming the transformation matrix. 
Examples of such kernels, which are used in this paper, are

    T_3    = [ 1 1 1; 1 0 1; 0 1 1 ],    
      T_5    =    [ 1 1 1 1 1; 1 0 0 0 0; 1 0 0 1 0; 1 1 1 0 0; 0 0 1 1 1 ] .

The transformation matrix of a multi-kernel polar code is given by

    G_N = T_p_1⊗ T_p_2⋯⊗ T_p_s ,

where T_p_i, i=1,2,…,s, denotes the kernel matrix of size p_i × p_i, and kernels of same size can be used multiple times, i.e., it may be that p_i = p_j for some i,j. 
The length of the code is N = p_1 · p_2 ⋯ p_s. 
Note that the ordering of the kernels in the Kronecker product is important for the frozen set design, as the Kronecker product is not commutative. 
An (N,K) multi-kernel polar code is defined by the transformation matrix G_N and the information set ℐ, with corresponding frozen set ℱ = [N] \ℐ. 
Codewords x ∈2^N are generated from the input words u ∈2^N by x = u   G_N, where u_i = 0 for i ∈ℱ and u_i, i ∈ℐ, stores the information bits. 
In <cit.>, ℐ is generated according to the reliabilities of the positions in the input vector u = (u_0,u_1,…,u_N-1), which can be determined e.g. through density evolution <cit.>. 
In this case, the information set is composed by the K most reliable positions.  

Similar to polar codes, the Tanner graph of multi-kernel polar codes can be constructed. 
While the Tanner graph of polar codes consists solely of 2 × 2 blocks, each corresponding to the kernel T_2, the Tanner graph of multi-kernel polar codes consists of various blocks, corresponding to the different kernels used. 
The Tanner graph for the transformation matrix in (<ref>) consists of s stages. 
On stage i, there are N/p_i blocks, each of size p_i × p_i, corresponding to a T_p_i kernel, with p_i edges to the left and to the right. 
The connections and edge permutations follow from the Kronecker product <cit.>. 
An example is given in Fig. <ref>, with edge-permutations indicated by dotted boxes.







 §.§ Decoding of Multi-Kernel Polar Codes


Decoding of multi-kernel polar codes is performed similarly to polar codes, using successive cancellation (SC) decoding on the Tanner graph of the code <cit.>, or enhanced SC-based decoding methods like SC list (SCL) decoding <cit.>.  
Log-likelihood ratios (LLRs) are passed along the Tanner graph from the right to the left, while hard decisions on decoded bits are passed from the left to the right. 
The major difference to decoding of polar codes is given by the computations in the blocks corresponding to the new kernels. 



The notation used for the p × p block corresponding to a T_p kernel is depicted in Fig. <ref>. 
Denote u = (u_0,u_1,…,u_p-1) the binary input vector to this block and x = (x_0,x_1,…,x_p-1) its binary output vector. 
Then we have the relationship u   T_p = x, defining the update rule for the hard-decisions going from left to right. 
Further denote L_i the LLR of output bit x_i and λ_i the LLR of the input bit u_i.  
The general structure of the update rule for LLRs, going from right to left, is  λ_i = f( L_0 , L_1 , … , L_l-1 , û_0 , û_1 , …, û_i-1 ), i.e., all LLRs L_j and only previous hard-decisions (estimates) û_j may be used for the computation, following the SC principle. 
The corresponding LLR calculations for T_2 from <cit.> are

    λ_0    =  L_0 ⊞ L_1  , 
    λ_1    = (-1)^u_0· L_0 + L_1,

for T_3 depicted in (<ref>), from <cit.>, are

    λ_0    =  L_0 ⊞ L_1 ⊞ L_2  , 
    λ_1    =  (-1)^u_0· L_0 + L_1 ⊞ L_2  , 
    λ_2    =  (-1)^u_0· L_1 + (-1)^u_0 ⊕ u_1· L_2 ,

and for T_5 in (<ref>), presented here for the first time, are

    λ_0    = L_1 ⊞ L_2 ⊞ L_4  , 
    λ_1    = (-1)^û_0· ( L_0 ⊞ (L_2 + (L_1 ⊞ L_4)) ⊞ L_3 )  , 
    λ_2    = (-1)^û_1 · ( L_0 ⊞ L_1 )  + ( L_3 ⊞ L_4 )  , 
    λ_3    = (-1)^û_0 ⊕û_1 ⊕û_2· L_0  + (-1)^û_0· L_1  + ( L_2 ⊞ (L_3 + L_4) )  , 
    λ_4    = (-1)^û_0 ⊕û_3· L_2   + (-1)^û_0 ⊕û_2· L_3   + (-1)^û_0· L_4 .
 
The boxplus operator for two LLRs a and b may be evaluated exactly as a ⊞ b = 2 tanh^-1( tanha/2·tanhb/2) or approximately as a ⊞ b ≈ a · b ·min{|a|,|b|}; the extension to multiple LLRs is as usual.  For other kernels similar LLR update equations can be derived <cit.>. 
In the next section, we will show that the presented kernels T_3 and T_5 permit to construct multi-kernel polar codes with good minimum distance. 




§ DESIGN FOR MINIMUM-DISTANCE


In this section, we describe how to design multi-kernel polar codes to increase the minimum distance of the code.
In <cit.>, the information set ℐ is selected according to reliability. 
This approach, which is also commonly followed for polar codes, is optimal for SC decoding when the code length tends to infinity. 
For short codes, however, the distance properties are more crucial than the polarization effect.

In the following, we focus on multi-kernel polar codes with transformation matrix of the form G_N = T_2^⊗ n⊗ T_p, i.e., a polar code composed with a larger kernel at the end.  
This is not a very limiting assumption for the following reasons.
First, the proposed design is to be used for short codes, for which the use of a single larger kernel is usually sufficient. 
Second, the larger kernel can be the composition of multiple smaller kernels. 
And third, changing the order of the kernels in the Kronecker product is equivalent to a row and column permutation of G_N, and thus leads to equivalent codes. 




 §.§ Minimum-Distance Spectrum


In the following, we will determine the minimum distance d achievable by a code generated by  selecting K rows of a transformation matrix G_N. 
More formally, we define the minimum-distance spectrum S_G_N of the transformation matrix G_N to be the mapping from dimension K to the maximal minimum distance d achievable by selecting an information set ℐ of size K, i.e., S_G_N(K) is the largest minimum distance achievable by an (N,K) multi-kernel polar code derived from the transformation matrix G_N.

Finding the minimum-distance spectrum of a code is in general a complex task, which may be accomplished e.g. by an exhaustive search. 
Under certain constraints, however, the minimum-distance spectrum of a multi-kernel polar code can be easily calculated based on the minimum-distance spectra of its building kernels.  
In fact, for polar codes, 

    S_T_2^⊗ n = ([2    1]^⊗ n) ,

where (x) is the vector x sorted in decreasing order, since polar codes have the same transformation matrix as Reed-Muller codes. 
In the following, we prove that a similar property holds for multi-kernel polar codes, allowing one to calculate the minimum-distance spectrum of the transformation matrix G_N using the Kronecker product of the spectra of the kernels composing it. 

 
 1ex0ex

If G_N = T_2^⊗ n⊗ T_p, then S_G_N = (S_T_2^⊗ n⊗ S_T_p).


The proposition is proved by induction on the number n of T_2 kernels employed in the transformation matrix G_N. 
The property obviously holds for n=0, and by inductive hypothesis we suppose that S_G_N/2 = (S_T_2^⊗ n-1⊗ S_T_p) given G_N/2 = T_2^⊗ n-1⊗ T_p.
Given the transformation matrix G_N = T_2^⊗ n⊗ T_p = [ G_N/2     0; G_N/2 G_N/2 ], this matrix can be divided into two parts, an upper matrix G^U = [G_N/2 | 0] and a lower matrix G_L = [G_N/2 |G_N/2 ], for which S_G^U = S_G_N/2 and S_G^L = 2 S_G_N/2. 
Given V = (S_T_2^⊗ n⊗ S_T_p), the goal of the proof is to show that S_G_N = V, i.e., that for every dimension K, there exists a subset of K rows of G_N such that the span of these rows has minimum distance V(K).

To do that, for every K we show how to construct a sub-matrix of G_N for which all the vectors of its span have Hamming weight not smaller than V(K). 
In fact, by construction, for every K there exist two integers K^U and K^L such that K^U + K^L = K, and two sub-matrices G_A^U and G_B^L, formed by K^U rows of G^U and by K^L rows of G^L respectively, such that S_G_A^U(K^U) ≥ V(K) and S_G_B^L(K^L) ≥ V(K). 
To end the proof, it is sufficient to use the distance property of the classical (u | u+v) construction <cit.> to verify that the code generated by G_A,B = [ G_A^U/G_B^L] has minimum distance min(S_G_A^U(K),S_G_B^L(K)) = V(K). 
 


The proposition shows how to exploit the spectra of the building kernels to evaluate the minimum-distance spectrum of the multi-kernel polar code. 
Moreover, the constructive nature of the proof suggests a greedy technique to build multi-kernel polar codes with optimal minimum distance. 
Before describing the algorithm in detail, in the following section we present kernel design principles leading to codes with good minimum distance spectra. 



 §.§ Kernel Design


For polar codes, kernels are usually designed to maximize the polarization effect on the input bits of the transformation G_N, and the information positions are then selected in reliability order. 
For short codes, however, the polarization effect is far less important than distances of the code, and kernels should be designed taking this aspect into account. 
Different kernels have different spectra, while polar codes are limited by the spectrum of the kernel T_2. 
Multi-kernel polar codes permit to create codes of desired minimum distance by changing the kernels composing the transformation matrix. 
If the kernels are designed properly, the information set can then be selected such that a large minimum distance is achieved for the desired length and dimension. 

As an example, consider the T_3 kernel depicted in (<ref>), introduced in <cit.>, and its minimum-distance spectrum.
For the information set of size 1, one row has to be selected: in order to maximize the minimum distance, the first row, (1   1   1), is selected, giving minimum distance 3; any other row selection would result in a smaller minimum distance, namely 2. 
For the information set of size 2, the last two rows, (1   0   1) and (0   1   1), are selected, generating a code of minimum distance 2; any other row selection would result in a smaller minimum distance. 
Finally, for a code of dimension 3, all rows have to be selected, resulting in a code of minimum distance 1. 
T_3 thus has the minimum-distance spectrum S_T_3=(3,2,1). 
As opposed to that, the construction by reliability selects the last row for dimension 1, the last two rows for dimension 2, and all rows for dimension 3; this gives minimum-distance spectrum (2,2,1).  
The proposed T_5 kernel presents a similar behavior, with minimum-distance spectrum S_T_5=(5,3,2,1,1). 



 §.§ Greedy Row-Selection Algorithm


In the previous sections, we described how to calculate the minimum-distance spectrum of the transformation matrix of a certain class of multi-kernel polar codes. 
The scope of this section is to describe how to determine the actual information set that achieves this minimum distance. 
As for the minimum-distance spectrum itself, this may be accomplished by an exhaustive search, which in general will be very complex. 
The proof of Proposition <ref>, however, gives an insight on how to select rows of G_N to achieve the minimum-distance spectrum.  

In the following we describe a greedy algorithm able to accomplish this task; the pseudo code is provided in Algorithm <ref>. 
Since the algorithm is based on Proposition <ref>, it finds an optimal solution if only one kernel of size larger than 2 is used in the construction, and this kernel is the last term in the Kronecker product.
The algorithm may as well be applied in the case of multiple kernels of size larger than 2, also at the end of the Kronecker product, by treating the Kronecker product of these kernels as one large kernel, for which the minimum-distance spectrum has to be determined before the algorithm is applied. 

Given a transformation matrix G_N = T_2^⊗ n⊗ T_p, we assume the kernel T_p to have minimum-distance spectrum S_T_p= (d_p (1), ⋯, d_p (p)), where d_p (k) is the minimum distance of the code of dimension k. 
The list I^k = {i^k_1,…,i^k_k} is associated to every entry d_p (k) of the spectrum, collecting the indices of the k rows of T_p giving the optimal minimum distance of the kernel. 
To begin with, the vector r_N = (2,1)^⊗ n⊗ S_T_p is created. 
This vector is an unsorted version of the minimum-distance spectrum, collecting the minimum achievable distances of each part of G_N. 

For a code of dimension K, at each step the algorithm adds sequentially one row index to the information set ℐ, which is initially empty. 
At each step, the position l, with l = 0,…,N-1, of the last largest entry in r_N is found, and r_N (l) is set to zero.  
After that, the value c = (l  mod  p)+1 and q = l-c+1 are calculated, giving the row position within the kernel and the row index in the transformation matrix where the corresponding kernel starts, respectively. 
In fact, since in S_T_p the distances are sorted in descending order, we know that {i^c_1+q,…,i^c_c+q}⊂ℐ. 
The algorithm deletes these c indices belonging to I^c, substituting them with the c+1 indices given by I^c+1; by the constructive proof of Proposition <ref>, we know that the resulting code has the desired minimum distance. 
Of course, if c=0, no rows of that part of the matrix are already in the information set, and therefore no information indices are deleted. 
In practice, at each step the information set is updated as ℐ = ℐ∖{i^c_1+q,…,i^c_c+q}∪{i^c+1_1+q,…,i^c+1_c+1+q}. 
The algorithm stops when ℐ includes K elements. 
The remaining N-K indices compose the frozen set ℱ. 




 §.§ Construction Example

To illustrate our construction, in the following we describe the minimum distance design of a multi-kernel polar code of length N = 6 depicted in Fig. <ref> with transformation matrix 
  
    G_6 = T_2 ⊗T_3 
      = [ T_3   0; T_3 T_3 ]
        = [ 1 1 1 0 0 0; 1 0 1 0 0 0; 0 1 1 0 0 0; 1 1 1 1 1 1; 1 0 1 1 0 1; 0 1 1 0 1 1;   ]  .
  
For the described kernel of size 3, we have that S_T_3 = (3,2,1) with ℐ_T_3(1) = {0}, ℐ_T_3(2) = {1,2} and obviously ℐ_T_3(3) = {0,1,2}. 
The minimum-distance spectrum is given by S_G_6 = ((2,1) ⊗ S_T_3) = (6,4,3,2,2,1); consequently, r_6 = (3,2,1,6,4,2). 
It is worth noticing that the minimum-distance spectrum of the reliability construction is (4,4,2,2,2,1). 
If a rate 1/2 code has to be designed, the positions of the K=3 information bits are needed. 
The information set ℐ is initially empty. 
At the first step, l=3, hence c=0 and q=3; since c=0, no entries of ℐ have to be deleted, and ℐ = {3}. 
At the second step, l=4, so c=1 and q=3; the information set is calculated as ℐ = ℐ∖{3}∪{4,5} = {4,5}. 
Finally, at the third step l=0, and the resulting information set is ℐ = {4,5}∪{0} = {0,4,5}. 
A comparison of the information sets calculated by the proposed algorithm following the distance criterion and the one resulting from the reliability order is presented in Table <ref> for various dimensions K. 
We observe that the proposed design always outperforms the reliability-based designs in terms of minimum distance, or performs identically when the reliability-based construction is equivalent to the minimum-distance based construction.





§ NUMERICAL ILLUSTRATIONS


In the following, we show the performance of the proposed minimum distance construction of multi-kernel polar codes. 
In particular, in Figures <ref>, <ref>, <ref> and <ref>, we show the BLER performance of the codes designed according to the proposed minimum distance  construction under list decoding <cit.> with list size L=8 for BPSK transmission over an additive white Gaussian noise (AWGN) channel. 
Our proposal, coined MK-dist in the figures, will be compared to the reliability-based design of multi-kernel polar codes proposed in <cit.>, coined MK-rel in the figures. 
We emphasize that MK-dist is designed according to the row selection algorithm described in the previous sections. 
Moreover, we add as references state-of-the-art punctured <cit.> and shortened <cit.> polar code constructions, coined polar-punct and polar-short respectively. 



First, in Figure <ref>, we show the performance of a code with length N = 192 and dimension K = 96. 
In this case, the transformation matrix is given by T_192=T_2^⊗ 6⊗ T_3, i.e., there is only one T_3 kernel at the rightmost of the Kronecker product. 
In this case, the proposed row selection algorithm can be run using the minimum-distance spectrum of the T_3 kernel presented before, and we observe that the minimum-distance based design outperforms all other designs. 



In Figure <ref> we show the performance of a code of length N = 144 and dimension K = 72. 
The transformation matrix is given by T_144=T_2^⊗ 4⊗ T_3^⊗ 2, i.e., there are two T_3 kernels at the rightmost of the Kronecker product. 
In this case, the minimum-distance spectrum for the Kronecker product kernel T_3 ⊗ T_3 has to be calculated, along with the auxiliary lists ℐ_T_3 ⊗ T_3. 
Potentially, two different kernels of size 3 may be used, like proposed in <cit.>, augmenting the flexibility of the minimum-distance spectrum, but this kind of optimization is out of the scope of this paper. 
The resulting spectrum is S_T_3 ⊗ T_3 = (9,6,4,4,3,2,2,2,1), and the multi-kernel polar codes resulting from our design still outperform all other depicted designs. 

In Figure <ref> we show the performance of a code of length N = 40 and dimension K = 20. 
The transformation matrix is given by T_40=T_2^⊗ 3⊗ T_5, i.e., there is only one T_5 kernel at the rightmost of the Kronecker product. 
In this case, the BLER performance of the proposed construction is again better than the one of the other constructions, though the gain is smaller than in the previous two cases where T_3 is used. 

Finally, in Figure <ref> we show the performance of a code of length N = 90 and dimension K = 45. 
In this case, the transformation mixes three different kernels, and we define T_90=T_2 ⊗ T_3^⊗ 2⊗ T_5. 
The BLER performance of the proposed construction, while is only able to match the performance of the shortened polar code. 
This shows that the proposed algorithm should be further optimized in the presence of multiple high size kernels. 

In conclusion, the proposed distance-based construction significantly outperforms state-of-the-art punctured and shortened polar codes for small block lengths, as well as the previously proposed reliability-based construction in <cit.>. 
We expect this property to hold true for short code lengths, when the polarization effect has lower importance than the distance profile in the design of the codes. 
Moreover, we argue that the encoder and the decoder of the proposed multi-kernel polar codes have a lower complexity compared to the encoder and the decoder of the state-of-the-art punctured polar codes, due to the larger length of the mother polar code and the reliability calculations required for these constructions <cit.>.







§ CONCLUSIONS


In this paper, we proposed a construction for multi-kernel polar codes, introduced in <cit.>, based on the maximization of the minimum distance. 
While the original construction based on bit reliabilities is suitable for long codes, our new minimum-distance based construction provides significant performance gains for short codes, i.e., where the polarization effect is less important than distance properties. 
This gives fundamental insights for the design of multi-kernel polar codes of any length. 
We further introduced the minimum-distance spectrum of a transformation matrix, and we developed a greedy algorithm that finds the information set achieving this minimum distance. 
Simulations illustrate the competitive performance of our design for short-length codes. 



IEEEbib


