Minimum-Distance Based Construction of
Multi-Kernel Polar Codes
Valerio Bioglio, Frédéric Gabry, Ingmar Land, Jean-Claude Belfiore

arXiv:1701.07616v2 [] 4 Sep 2017

Mathematical and Algorithmic Sciences Lab
France Research Center, Huawei Technologies France SASU
Email: {valerio.bioglio,frederic.gabry,ingmar.land, jean.claude.belfiore}@huawei.com

Abstract—In this paper, we propose a construction for multikernel 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-theart punctured or shortened Arikan polar codes, multi-kernel
polar codes with our new design show significantly improved
error-rate performance.

I. I NTRODUCTION
Polar codes, introduced by Arikan in [1], 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 T2 = 11 01 . The generator matrix of a polar
code is then a sub-matrix of the transformation matrix T2⊗n .
Arikan conjectured in [1] that the polarization effect is not
restricted to powers of the kernel T2 , which was verified in [2],
where the authors provide necessary and sufficient conditions
for binary kernels Tp of size p × p, p > 2, to allow for
the polarization effect. Recently, polar codes based on larger
kernels were proposed in [3], [4], while in [5] 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 = pn . However,
not all code lengths can be expressed as powers of integers.
To overcome this length matching problem, puncturing [6], [7]
and shortening [8] 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 multikernel construction has been proposed in [9]. 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 [10]. 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 [1], and it is similarly used
for the design of multi-kernel polar codes [9]. Such design
by reliability is appropriate for long codes under successive
cancellation decoding; for short codes under list decoding [11],
however, design principles that give more weight to distance
properties may give superior error-rate performance. Related to
this is the work in [12], 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 T2⊗n .
This paper is organized as follows. In Section II, we review
construction, encoding, and decoding of multi-kernel polar
codes. In Section III we describe explicitly the new distancebased design for multi-kernel polar codes. In Section IV
we illustrate numerically the performance of the codes, and
Section V concludes this paper.
II. M ULTI -K ERNEL P OLAR C ODES
In this section, we briefly review the structure, encoding and
decoding of multi-kernel polar codes; for details, we refer the
reader to [9]. Multi-kernel polar codes are a generalization
of the Arikan polar codes [1], simply referred to as polar
codes throughout the paper, and therefore we will provide a
comparison to the Arikan construction for clarity.

A. Code Structure and Encoding
Polar codes are based on the
T2⊗n , N = 2n , where T2 denotes

1
T2 =
1

u0

Kronecker product GN =
the 2 × 2 kernel

0
.
1

Let us assume an information set I ⊂ [N ], [N ] =
{0, 1, . . . , N −1}, of size |I| = K and a corresponding frozen
set F = [N ]\I of size |F | = N − K. An (N, K) polar code
of length N and dimension K is then defined by the encoder
x = u GN , mapping the input vector u ∈ F2 N to the codeword
x ∈ F2 N , where ui = 0 for i ∈ F , denoting the frozen bits,
and ui , 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


1 1 1 1 1


1 0 0 0 0
1 1 1





T3 = 1 0 1 ,
T5 = 
(1)
1 0 0 1 0 .

0 1 1
1 1 1 0 0
0 0 1 1 1
The transformation matrix of a multi-kernel polar code is given
by
GN = Tp1 ⊗ Tp2 · · · ⊗ Tps ,

(2)

where Tpi , i = 1, 2, . . . , s, denotes the kernel matrix of size
pi × pi , and kernels of same size can be used multiple times,
i.e., it may be that pi = pj for some i, j. The length of the code
is N = p1 · p2 · · · ps . 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
GN and the information set I, with corresponding frozen set
F = [N ]\I. Codewords x ∈ F2 N are generated from the
input words u ∈ F2 N by x = u GN , where ui = 0 for
i ∈ F and ui , i ∈ I, stores the information bits. In [9],
I is generated according to the reliabilities of the positions
in the input vector u = (u0 , u1 , . . . , uN −1 ), which can be
determined e.g. through density evolution [13]. 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 T2 , 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 (2) consists of s stages. On stage i, there are N/pi blocks,
each of size pi × pi , corresponding to a Tpi kernel, with
pi edges to the left and to the right. The connections and
edge permutations follow from the Kronecker product [9]. An
example is given in Fig. 1, with edge-permutations indicated
by dotted boxes.

x0
T2

u1

x1

T3

u2

x2
T2

u3
u4

x3
x4

T3
T2

u5

x5
Stage 2

Stage 1

Fig. 1. Tanner graph of the multi-kernel polar code for G6 = T2 ⊗ T3 .

B. 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 [9], or enhanced SC-based
decoding methods like SC list (SCL) decoding [11]. Loglikelihood 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.
u0 , λ0
u1 , λ1
up−1 , λp−1

..
.

Tp

..
.

x0 , L0
x1 , L1
xp−1 , Lp−1

Fig. 2. Block in Tanner graph, corresponding to p × p kernel Tp .

The notation used for the p × p block corresponding to a Tp
kernel is depicted in Fig. 2. Denote u = (u0 , u1 , . . . , up−1 ) the
binary input vector to this block and x = (x0 , x1 , . . . , xp−1 )
its binary output vector. Then we have the relationship u Tp =
x, defining the update rule for the hard-decisions going from
left to right. Further denote Li the LLR of output bit xi
and λi the LLR of the input bit ui . The general structure
of the update rule for LLRs, going from right to left, is
λi = f (L0 , L1 , . . . , Ll−1 , û0 , û1 , . . . , ûi−1 ), i.e., all LLRs
Lj and only previous hard-decisions (estimates) ûj may be
used for the computation, following the SC principle. The
corresponding LLR calculations for T2 from [1] are
λ0 = L0 ⊞ L1 ,
λ1 = (−1)u0 · L0 + L1 ,
for T3 depicted in (1), from [9], are
λ0 = L0 ⊞ L1 ⊞ L2 ,
λ1 = (−1)u0 · L0 + L1 ⊞ L2 ,
λ2 = (−1)u0 · L1 + (−1)u0 ⊕u1 · L2 ,

and for T5 in (1), presented here for the first time, are
λ0 = L1 ⊞ L2 ⊞ L4 ,
λ1 = (−1)û0 · (L0 ⊞ (L2 + (L1 ⊞ L4 )) ⊞ L3 ),
λ2 = (−1)û1 · (L0 ⊞ L1 ) + (L3 ⊞ L4 ),
λ3 = (−1)û0 ⊕û1 ⊕û2 · L0 + (−1)û0 · L1 + (L2 ⊞ (L3 + L4 )),
λ4 = (−1)û0 ⊕û3 · L2 + (−1)û0 ⊕û2 · L3 + (−1)û0 · L4 .

where sort(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 GN using the Kronecker product of the spectra of
the kernels composing it.
Proposition 1 (Minimum-distance spectrum).
If GN = T2⊗n ⊗ Tp , then SGN = sort(ST ⊗n ⊗ STp ).
2

The boxplus operator for two LLRs a and b may be evaluated
exactly as a⊞b = 2 tanh−1 tanh a2 ·tanh 2b or approximately
as a ⊞ b ≈ sgn a · sgn b · min{|a|, |b|}; the extension to
multiple LLRs is as usual. For other kernels similar LLR
update equations can be derived [14]. In the next section,
we will show that the presented kernels T3 and T5 permit
to construct multi-kernel polar codes with good minimum
distance.
III. D ESIGN FOR M INIMUM -D ISTANCE
In this section, we describe how to design multi-kernel polar
codes to increase the minimum distance of the code. In [9],
the information set I 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 GN = T2⊗n ⊗ Tp , 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 GN , and thus leads to equivalent codes.
A. 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 GN . More formally, we define the
minimum-distance spectrum SGN of the transformation matrix
GN to be the mapping from dimension K to the maximal
minimum distance d achievable by selecting an information
set I of size K, i.e., SGN (K) is the largest minimum distance
achievable by an (N, K) multi-kernel polar code derived from
the transformation matrix GN .
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,
ST ⊗n = sort([2
2

1]⊗n ),

Proof. The proposition is proved by induction on the number
n of T2 kernels employed in the transformation matrix GN .
The property obviously holds for n = 0, and by inductive
hypothesis we suppose that SGN/2 = sort(ST ⊗n−1 ⊗ STp )
2
given GN/2 = T2⊗n−1
 the transformation matrix
 ⊗ Tp . Given
G

0

GN = T2⊗n ⊗ Tp = GN/2
GN/2 , this matrix can be divided
N/2
into two parts, an upper matrix GU = [GN/2 |0] and a lower
matrix GL = [GN/2 |GN/2 ], for which SGU = SGN/2 and
SGL = 2SGN/2 . Given V = sort(ST ⊗n ⊗ STp ), the goal of the
2
proof is to show that SGN = V , i.e., that for every dimension
K, there exists a subset of K rows of GN such that the span
of these rows has minimum distance V (K).
To do that, for every K we show how to construct a submatrix of GN 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
L
K U + K L = K, and two sub-matrices GU
A and GB , formed
U
U
L
L
by K rows of G and by K rows of G respectively,
such that SGUA (K U ) ≥ V (K) and SGLB (K L ) ≥ V (K). To
end the proof, it is sufficient to use the distance property of
the classical (u|u + v) construction
h U i [15] to verify that the
G
code generated by GA,B = GLA has minimum distance
B
min(SGUA (K), SGLB (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.
B. Kernel Design
For polar codes, kernels are usually designed to maximize
the polarization effect on the input bits of the transformation
GN , 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 T2 . 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 T3 kernel depicted in (1),
introduced in [9], 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. T3
thus has the minimum-distance spectrum ST3 = (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 T5 kernel presents a similar behavior,
with minimum-distance spectrum ST5 = (5, 3, 2, 1, 1).
C. 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 minimumdistance spectrum itself, this may be accomplished by an
exhaustive search, which in general will be very complex. The
proof of Proposition 1, however, gives an insight on how to
select rows of GN 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 1. Since the algorithm is based on Proposition 1, 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 GN = T2⊗n ⊗ Tp , we
assume the kernel Tp to have minimum-distance spectrum
STp = (dp (1), · · · , dp (p)), where dp (k) is the minimum
distance of the code of dimension k. The list I k = {ik1 , . . . , ikk }
is associated to every entry dp (k) of the spectrum, collecting
the indices of the k rows of Tp giving the optimal minimum
distance of the kernel. To begin with, the vector rN =
(2, 1)⊗n ⊗ STp is created. This vector is an unsorted version
of the minimum-distance spectrum, collecting the minimum
achievable distances of each part of GN .
For a code of dimension K, at each step the algorithm
adds sequentially one row index to the information set I,
which is initially empty. At each step, the position l, with
l = 0, . . . , N − 1, of the last largest entry in rN is found, and
rN (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
STp the distances are sorted in descending order, we know that
{ic1 + q, . . . , icc + q} ⊂ I. 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 1, 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 = I \ {ic1 + q, . . . , icc + q} ∪ {ic+1
+ q, . . . , ic+1
1
c+1 + q}. The
algorithm stops when I includes K elements. The remaining
N − K indices compose the frozen set F .
Algorithm Information set to maximize minimum distance
1: Initialize the set I = 0
2: Load N -vector rN
3: Load j-vectors I j , j = 1 . . . p
4: for k = 1 . . . K do
5:
l = argmax(rN )
6:
c = (l mod p) + 1
7:
q =l−c+1
8:
rN (l) = 0
9:
if c > 1 then
c+1
10:
I = I\{ic1 +q, . . . , icc +q}∪{ic+1
1 +q, . . . , ic+1 +q}
11:
else
12:
I = I ∪ {i11 }
13:
end if
14: end for
D. 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. 1 with transformation matrix


1 1 1 0 0 0


 1 0 1 0 0 0 

0 1 1 0 0 0 
T3 0

=
G6 = T2 ⊗ T3 =
1 1 1 1 1 1  .
T3 T3


1 0 1 1 0 1 
0 1 1 0 1 1
For the described kernel of size 3, we have that ST3 =
(3, 2, 1) with IT3 (1) = {0}, IT3 (2) = {1, 2} and obviously IT3 (3) = {0, 1, 2}. The minimum-distance spectrum
is given by SG6 = sort((2, 1) ⊗ ST3 ) = (6, 4, 3, 2, 2, 1);
consequently, r6 = (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 I is initially empty. At the first step, l = 3,
hence c = 0 and q = 3; since c = 0, no entries of I have
to be deleted, and I = {3}. At the second step, l = 4,
so c = 1 and q = 3; the information set is calculated as
I = I \ {3} ∪ {4, 5} = {4, 5}. Finally, at the third step

10 0

10 0
MK rel [9]
MK dist (proposed)
polar punct [6]
polar short [8]

10 -1

MK rel [9]
MK dist (proposed)
polar punct [6]
polar short [8]

10 -1

BLER

10 -2

BLER

10 -2

10 -3

10 -3

10 -4

10 -4

1

2

3

4

5

6

Eb N0 (dB)

l = 0, and the resulting information set is I = {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 I
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 minimumdistance based construction.
Rate
Information Set
Minimum Distance
Information Set
Minimum Distance

1/6
u5
4
u3
6

2

3

4

5

6

Eb N0 (dB)

Fig. 3. Block error rates for length N = 192 and rate R = 1/2 under SCL
decoding with list size L = 8.

Reliability
Design
Distance
Design

1

2/6
(u4 , u5 )
4
(u4 , u5 )
4

3/6
(u2 , u4 , u5 )
2
(u0 , u4 , u5 )
3

TABLE I
C OMPARISON OF MINIMUM DISTANCES FOR N = 6.

IV. N UMERICAL I LLUSTRATIONS
In the following, we show the performance of the proposed
minimum distance construction of multi-kernel polar codes.
In particular, in Figures 3, 4, 5 and 6, we show the BLER
performance of the codes designed according to the proposed
minimum distance construction under list decoding [11] with
list size L = 8 for BPSK transmission over an additive white
Gaussian noise (AWGN) channel. Our proposal, coined MKdist in the figures, will be compared to the reliability-based
design of multi-kernel polar codes proposed in [9], 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-theart punctured [6] and shortened [8] polar code constructions,
coined polar-punct and polar-short respectively.
First, in Figure 3, we show the performance of a code with
length N = 192 and dimension K = 96. In this case, the
transformation matrix is given by T192 = T2⊗6 ⊗ T3 , i.e.,

Fig. 4. Block error rates for length N = 144 and rate R = 1/2 under SCL
decoding with list size L = 8.

there is only one T3 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 T3 kernel
presented before, and we observe that the minimum-distance
based design outperforms all other designs.
In Figure 4 we show the performance of a code of length
N = 144 and dimension K = 72. The transformation matrix
is given by T144 = T2⊗4 ⊗ T3⊗2 , i.e., there are two T3 kernels
at the rightmost of the Kronecker product. In this case, the
minimum-distance spectrum for the Kronecker product kernel
T3 ⊗ T3 has to be calculated, along with the auxiliary lists
IT3 ⊗T3 . Potentially, two different kernels of size 3 may be
used, like proposed in [5], 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
ST3 ⊗T3 = (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 5 we show the performance of a code of length
N = 40 and dimension K = 20. The transformation matrix is
given by T40 = T2⊗3 ⊗ T5 , i.e., there is only one T5 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 T3 is used.
Finally, in Figure 6 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
T90 = T2 ⊗T3⊗2 ⊗T5 . 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 short-

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.

10 0
MK rel [9]
MK dist (proposed)
polar punct [6]
polar short [8]

10 -1

BLER

10 -2

10 -3

R EFERENCES
10 -4

1

2

3

4

5

6

7

Eb N0 (dB)

Fig. 5. Block error rates for length N = 40 and rate R = 1/2 under SCL
decoding with list size L = 8.

10 0
MK rel [9]
MK dist (proposed)
polar punct [6]
polar short [8]

10 -1

BLER

10 -2

10 -3

10 -4

10 -5

1

2

3

4

5

6

7

Eb N0 (dB)

Fig. 6. Block error rates for length N = 90 and rate R = 1/2 under SCL
decoding with list size L = 8.

ened polar codes for small block lengths, as well as the
previously proposed reliability-based construction in [9]. 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 [9].
V. C ONCLUSIONS
In this paper, we proposed a construction for multi-kernel
polar codes, introduced in [9], based on the maximization
of the minimum distance. While the original construction
based on bit reliabilities is suitable for long codes, our

[1] E. Arikan, “Channel polarization: a method for constructing capacityachieving codes for symmetric binary-input memoryless channels,”
IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3051–
3073, July 2009.
[2] S. B. Korada, E. Sasoglu, and R. Urbanke, “Polar codes: Characterization of exponent, bounds, and constructions,” IEEE Transactions on
Information Theory, vol. 56, no. 12, pp. 6253–6264, Dec. 2010.
[3] N. Presman, O. Shapira, S. Litsyn, T. Etzion, and A. Vardy, “Binary
polarization kernels from code decompositions,” IEEE Transactions on
Information Theory, vol. 61, no. 5, pp. 2227–2239, May 2015.
[4] H.-P. Lin, S. Lin, and K. Abdel-Ghaffar, “Linear and nonlinear binary
kernels of polar codes of small dimensions with maximum exponents,”
IEEE Transactions on Information Theory, vol. 61, no. 10, pp. 5253–
5270, Oct. 2015.
[5] M. Ye and A. Barg, “Polar codes using dynamic kernels,” in IEEE
International Symposium on Information Theory (ISIT), Hong Kong,
China, June 2015.
[6] K. Niu, K. Chen, and J.-R. Lin, “Beyond turbo codes: Rate-compatible
punctured polar codes,” in IEEE International Conference on Communications (ICC), Budapest, Hungary, June 2013.
[7] L. Zhang, Z. Zhang, X. Wang, Q. Yu, and Y. Chen, “On the puncturing
patterns for punctured polar codes,” in IEEE International Symposium
on Information Theory (ISIT), Hawaii, U.S.A., July 2014.
[8] R. Wang and R. Liu, “A novel puncturing scheme for polar codes,”
IEEE Communications Letters, vol. 18, no. 12, pp. 2081–2084, Dec.
2014.
[9] F. Gabry, V. Bioglio, I. Land, and J.-C. Belfiore, “Multi-kernel
construction of polar codes,” in IEEE International Conference on
Communications (ICC), Paris, France, May 2017.
[10] M. Benammar, V. Bioglio, F. Gabry, and I. Land, “Multi-kernel polar
codes: Proof of polarization and error exponents,” in IEEE Information
Theory Workshop (ITW), Kaohsiung, Taiwan, Nov. 2017.
[11] I. Tal and A. Vardy, “List decoding of polar codes,” in IEEE
International Symposium on Information Theory Proceedings (ISIT), St.
Petersburg, Russia, July 2011.
[12] M. Mondelli, S. H. Hassani, and R. L. Urbanke, “From polar to ReedMuller codes: A technique to improve the finite-length performance,”
IEEE Transactions on Communications, vol. 62, no. 9, pp. 3084–3091,
Sept. 2014.
[13] R. Mori and T. Tanaka, “Performance of polar codes with the construction using density evolution,” IEEE Communications Letters, vol. 13,
no. 7, pp. 519–521, July 2009.
[14] Z. Huang, S. Zhang, F. Zhang, C. Duanmu, and M Chen, “On the
successive cancellation decoding of polar codes with arbitrary binary
linear kernels,” in arXiv preprint, arXiv:1701.03264, Jan. 2017.
[15] F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting
codes, Elsevier, 1977.

