New Search for the Polarization-Adjusted
Convolutional Codes with respect to the
AFER-Optimality Criterion
1

Presenter: Murad ABDULLAH (HKUST)
Supervisor: Wai Ho MOW (HKUST)
2022.09.09

2

Outline
´ Introduction & Motivation
´ Polar codes
´ Polarization-adjusted convolutional (PAC) codes
´ Optimizing PAC codes
´ Conclusion

3

Introduction & Motivation
´ New applications in the 5G standardization demand improved
performance of the channel codes
´ In coding theory, finding a codebook with maximum possible value of the
minimum distance is a central open problem
´ In the high SNR regime, the performance of a code depends on the
minimum distance and its error coefficient (i.e., number of codewords of
weight d)
´ Improve the performance of polarization-adjusted convolutional (PAC)
codes an extension of polar codes by maximizing minimum distance and
minimizing error coefficient

Polar codes

4

´ Invented by E. Arikan in 2009
´ Channel polarization is the underlying principle of
polar codes
´ First mathematically proven codes to achieve
capacity of binary input–discrete memoryless
channels (BI-DMCs)
´ Included as control channel codes in enhanced
mobile broadband (eMBB) service of 5G standard

Figure credit: Qualcomm

5

Polar codes (cont.)
´ 𝑊: {0,1} → 𝒴 is binary input channel with 0,1 as input alphabet, and 𝒴
as output alphabet
´ Symmetric capacity 𝐼 𝑊 ∈ [0,1]

1
𝑊(𝑦|𝑥)
𝑊(𝑦|𝑥)
1
1
2
𝑊 𝑦 0 + 𝑊(𝑦|1)
!∈𝒴 $∈{&,(}
2
2

𝐼 𝑊 ≜$ $

´ Bhattacharya parameter 𝑍 𝑊 ∈ [0,1]
𝑍 𝑊 ≜ $ 𝑊 𝑦 0 𝑊(𝑦|1)
!∈𝒴

Polar codes (cont.)

6

´ The basic polarization kernel[1]
𝐺+ =
´ [𝑢"

1
1

0
1

𝑢# ]𝐺+ = [𝑢" + 𝑢#

𝑢# ]

´ This can be thought of combining two independent
copies of the channel 𝑊
´ 𝐼 𝑊 ! ≤ 𝐼(𝑊 * )
´ Polar code of block length 𝑁 = 2, , 𝑛 ≥ 0
constructed by n-th Kronecker power of 𝐺+
´ 𝐺- =

𝐺+⊗, ,

𝐺
Polar transform, e.g., 𝐺/ = +
𝐺+

0+×+
𝐺+

𝑢/

𝑥/

𝑊

𝑢0

𝑥0

𝑊

=

𝑊 ! 𝑦" , 𝑦# 𝑢" =
can be

4
$!" ∈{",#}

𝑊 * 𝑦" , 𝑦# , 𝑢" 𝑢# =

𝑦/
𝑦0

1
𝑊 𝑦" 𝑢" ⨁𝑢#) 𝑊(𝑦# |𝑢#) )
2

1
𝑊 𝑦" 𝑢" ⨁𝑢# 𝑊(𝑦# |𝑢# )
2

[1] Arikan, Erdal. "Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels." IEEE Transactions on Information Theory 55.7 (2009): 3051-3073.

7

Polar codes (cont.)
´ Polar codes can be defined by the tuple 𝑁, 𝐾, 𝒜
´ 𝑁 = 2, , 𝑛 ≥ 0 is the code length
´ 𝐾 is the code dimension
´ set 𝒜 ⊂ {0,1, … , 𝑁 − 1} and 𝒜 = 𝐾 is information index set

´ Selecting the 𝐾 rows of 𝐺! , indices present in 𝒜
´ Minimum Hamming distance of the code depends on 𝒜
´ 𝒙 = 𝒖𝑮𝑵 is the encoding operation
´ 𝒖 is the length 𝑁 vector contains information bits at the indices present in 𝒜

8

Polar codes (cont.)
´ Finding the set 𝒜 and assigning the information bits to the indices present in 𝒜 is called
rate-profiling
´ Followings are the commonly used rate-profiling methods
´ Reed-Muller (RM) rate profiling
´ Selecting the indices of the rows of the matrix 𝐺! having highest Hamming weight

´ Capacity score function
´ Indices of the 𝐾 bit-channels having highest capacity

´ Gaussian approximation (GA) rate profiling
´ Choose the 𝐾 most reliable bit-channels reliability calculated based on GA

´ 5G Universal reliability sequence
´ 5G standardization includes the universal sequence up to block length 𝑁 = 1024

9

Polarization-adjusted convolutional
(PAC) codes

´ PAC codes proposed by Arikan in his 2019 Shannon lecture[1]
´ Performs very close to the AWGN dispersion bound
´ Convolution as pre-transformation
´ 𝒄 impulse response of the convolution transform can be written as

where 𝑐" = 𝑐9 = 1 and 𝑚 + 1 is constraint length
[1] Arıkan, Erdal. "From sequential decoding to channel polarization and back again." arXiv preprint arXiv:1908.09594 (2019).

Polarization-adjusted convolutional
(PAC) codes (cont.)

10

´ PAC codes can be described by
the tuple (𝑁, 𝐾, 𝒜, 𝒄)
´ 𝑁 is code length

𝒅

´ 𝐾 is the code dimension

Rate
Profiling

𝒗 Convolution 𝒖
Transform

Polar
Transform

𝒙

´ 𝒜 information index set
´ 𝒄 impulse response of the convolution
transform

´ PAC encoding can be described as

Channel

M
𝒅

𝒙 = 𝒗𝑇𝐺!
where 𝑇, 𝐺- are upper triangular and
polar transform matrices, respectively.

[1] Arıkan, Erdal. "From sequential decoding to channel polarization and back again." arXiv preprint arXiv:1908.09594 (2019).

Retrieving
Message

O
𝒗

Successive 𝒚
Cancellation

Tree
Search

𝑢N
PAC coding scheme[1]

11

Polarization-adjusted convolutional
(PAC) codes (cont.)

´ SC is an efficient method for
computing the metrics

𝒅

´ Fano algorithm as tree search
algorithm[1]
´ SCL can be used as tree search
algorithm

Rate
Profiling

𝒗 Convolution 𝒖
Transform

Polar
Transform

𝒙

Channel

M
𝒅

Retrieving
Message

Successive 𝒚
Cancellation

Tree
Search

𝑢N
PAC coding scheme[1]

[1] Arıkan, Erdal. "From sequential decoding to channel polarization and back again." arXiv preprint arXiv:1908.09594 (2019).

12

Polarization-adjusted convolutional
(PAC) codes (cont.)
´ Polar codes constructed under
RM rate-profile has highest
possible minimum distance,
hence outperforms all others
´ Pre-transformation reduces the
number
of
low-weight
codewords
´ Higher minimum distance and
smaller
number
low-weight
codewords made PAC codes
able to perform close to
dispersion bound with list size of
128

Optimizing PAC codes

13

´ From truncated union bound FER under MLD 𝑃:;< ≈ 𝐴=#$% 𝒬 2𝑑9>, 𝑅𝐸? /𝑁@ 1, so
maximizing 𝑑9>, and minimizing 𝐴=#$% (no. of 𝑑9>, codewords), we call this asymptotic
frame error rate (AFER)-optimality criteria
´ Higher 𝑑9>, of RM rate-profile makes it to outperform others by 0.15 dB @ 10!A
´ So, our objective is to optimize the 𝒜 & 𝒄 to maximize 𝑑9>, & minimize 𝐴=#$%
´ There are

B

2-!# total solutions (huge search space)

´ Need to compute exact 𝑑9>, (compute intensive task)
´ CUDA assisted simulated annealing (SA) could be used for limited 𝑁 & 𝐾.

1

𝒬 𝑥 =

%
!
∫ exp
"# $

!

− &" 𝑑𝑡

Optimizing PAC codes (cont.)

14

´ CUDA an acronym for Compute Unified
Device Architecture
´ a parallel computing platform & application
programing interface model created by
Nvidia
´ Used to program graphics processing unit
developed Nvidia for compute intensive tasks
´ Computation of minimum distance of code is
compute intensive task
´ Computation of codewords are independent

CPU thread
CPU
Data transfer
GPU

Figure credit: Nvidia

GPU threads

Optimizing PAC codes (cont.)

15

´ Effective and general form of optimization algorithm
´ Annealing refers to an analogy with thermodynamics
´ Cooling and annealing of metals
´ Uses the objective function of an optimization problem instead of the energy of the
material
´ Randomly generate 𝒜 and 𝒄, and compute the 𝑑9>,
´ 𝑑9>,
! &'

improves keep with probability 1, otherwise accept with probability

C()#*
𝑒
,where 𝑇𝑒𝑚𝑝 is the temperature used by SA, and Δ𝐸 is difference in
energies of the current solution and previous solution

16
´ Figure on the right presents
the detailed CUDA-assisted SA
algorithm to search for better
PAC codes
´ We also consider mixed kernel
construction of PAC codes [1]

[1] Bioglio, Valerio, et al. "Minimum-distance based construction of multi-kernel polar codes." GLOBECOM 2017-2017 IEEE Global Communications Conference. IEEE, 2017.

17

Results

´ Implemented SA in CUDA-C++
´ Could search up to block length 64
´ 𝑁 = 64 , possible solutions 10AD ,
algorithm searched only for 10D

our

18

Results (cont.)

´ Our newly discovered (64,32) PAC codes
have 𝑑9>, 12
´ 0.29 dB gap to dispersion approximation @
10!/ FER
´ 0.36 dB less SNR @ 10!/ FER as compared to
the best-known minimum distance code in
the literature[1]
´ 𝐴#+ = 720 (Ours)
´ 𝐴#+ = 12878 [1]

[1] M. Grassl, “Bounds on the minimum distance of linear codes and quantum codes,” Online available at http://www.codetables.de, 2007, accessed on 2020-11-03.

[1]

19

Results (cont.)
´ Our newly discovered (32,18) PAC codes
have 𝑑9>, 6
´ 0.49 dB less SNR @ 10!/ FER as compared
to the best-known minimum distance
codes in the literature[1]
´ 𝐴E = 110 (our)
´ 𝐴E = 543 [1]

Union bound of (32,18) codes

[1] M. Grassl, “Bounds on the minimum distance of linear codes and quantum codes,” Online available at http://www.codetables.de, 2007, accessed on 2020-11-03.

20

Results (cont.)

´ Detailed search results of the PAC codes
´ Kernels column shows the permutation order of the kernels used to construct
polarization matrix
´ Eb/N0 gain is calculated using the truncated ML bound @ 10#$ FER
´ In some cases, our codes achieve the lower bound on 𝐴%
´ We have general constructions for some of these codes

21

[8] M. Grassl, “Bounds on the minimum distance of linear codes and quantum codes,” Online available at http://www.codetables.de, 2007, accessed on 2020-11-03.
[14] Solé, Patrick, et al. "Linear Programming Bounds on the Kissing Number of q-ary Codes." 2021 IEEE Information Theory Workshop (ITW). IEEE, 2021.

22

Conclusions
´ We presented an algorithm to search for better PAC codes having higher minimum
distance and smaller error coefficient
´ Some of these codes achieve lower and upper bound on error coefficient &
minimum distance, respectively

23

Thank you!