New Search for the Polarization-Adjusted
Convolutional Codes with respect to the
AFER-Optimality Criterion
Presenter: Murad ABDULLAH (HKUST)
Supervisor: Wai Ho MOW (HKUST)
2022.09 .09
1

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

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
3

Polar codes
4
Figure credit: Qualcomm
́ 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

Polar codes (cont.)
5
́ W : {0,1} → Y is binary input channel with 0,1 as input alphabet, and Y
as output alphabet
́ Symmetric capacity I W ∈ [0,1]
IW≜$
!∈Y
$$∈{&,(}
1
2
W(y|x)
W(y|x)
1
2Wy0+
1
2 W(y|1)
́ Bhattacharya parameter Z W ∈ [0,1]
ZW≜$
!∈Y
Wy0W(y|1)

Polar codes (cont.)
6
W
W
=
u/
u0
x/
x0
y/
y0
W!y",y#u" = 4
$!
"
∈{",#}
1
2
W y" u"⨁u#
)
W(y#|u#
)
)
W*y",y#,u"u# =
1
2
W y" u"⨁u# W(y#|u#)
[1] Arikan, Erdal. "Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. " I E EE Transactions on Information Theory 55.7 (2009): 3051-3073 .
́ The basic polarization kernel[1]
G+=
10
11
́ [u" u#]G+=[u"+u# u#]
́ This can be thought of combining two independent
copies of the channel W
́IW
!
≤ I(W*)
́ Polar code of block length N = 2
,
,n≥0 canbe
constructed by n-th Kronecker power of G+
́ G-=G+
⊗,
, Polar transform, e.g., G/ =
G+ 0+×+
G+ G+

Polar codes (cont.)
7
́ Polar codes can be defined by the tuple N, K , A
́N=2
,
,n≥0isthecodelength
́ K is the code dimension
́ setA⊂{0,1,...,N −1}and A =Kisinformationindexset
́ Selecting the K rows of G! , indices present in A
́ Minimum Hamming distance of the code depends on A
́ x = uGN is the encoding operation
́ u is the length N vector contains information bits at the indices present in A

Polar codes (cont.)
8
́ Finding the set A and assigning the information bits to the indices present in A 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 G! having highest Hamming weight
́ Capacity score function
́ Indices of the K bit-channels having highest capacity
́ Gaussian approximation (GA) rate profiling
́ Choose the K most reliable bit-channels reliability calculated based on GA
́ 5G Universal reliability sequence
́ 5G standardization includes the universal sequence up to block length N = 1024

Polarization-adjusted convolutional
(PAC) codes
9
[1] Arıkan, Erdal. "From sequential decoding to channel polarization and back again." arXiv preprint arXiv:1908.09594 (2019).
́ PAC codes proposed by Arikan in his 2019 Shannon lecture[1]
́ Performs very close to the AWGN dispersion bound
́ Convolution as pre-transformation
́ c impulse response of the convolution transform can be written as
wherec"=c9 = 1andm+1isconstraintlength

10
Polarization-adjusted convolutional
(PAC) codes (cont.)
[1] Arıkan, Erdal. "From sequential decoding to channel polarization and back again." arXiv preprint arXiv:1908.09594 (2019).
PAC coding scheme[1]
Rate
Profiling
Convolution
Transform
Polar
Transform
Retrieving
Message
Tree
Search
Successive
Cancellation
Channel
d
v
u
x
y
M
d
N
u
O
v
́ PAC codes can be described by
thetuple(N,K,A,c)
́ N is code length
́ K is the code dimension
́ A information index set
́ c impulse response of the convolution
transform
́ PAC encoding can be described as
x=vTG!
where T, G- are upper triangular and
polar transform matrices, respectively.

11
Polarization-adjusted convolutional
(PAC) codes (cont.)
[1] Arıkan, Erdal. "From sequential decoding to channel polarization and back again." arXiv preprint arXiv:1908.09594 (2019).
PAC coding scheme[1]
Rate
Profiling
Convolution
Transform
Polar
Transform
Retrieving
Message
Tree
Search
Successive
Cancellation
Channel
d
v
u
x
y
M
d
N
u
́ SC is an efficient method for
computing the metrics
́ Fano algorithm as tree search
algorithm[1]
́ SCL can be used as tree search
algorithm

Polarization-adjusted convolutional
(PAC) codes (cont.)
12
́ 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
1Qx=
!
"#
∫$
%
exp −
&!
"
dt
́ From truncated union bound FER under MLD P:
;< ≈ A=#$%Q 2d9>,RE?/N@
1, so
maximizing d9>, and minimizing A=#$%
(no. of d9>, codewords), we call this asymptotic
frame error rate (AFER)-optimality criteria
́ Higher d9>, of RM rate-profile makes it to outperform others by 0.15 dB @ 10!A
́ So, our objective is to optimize the A & c to maximize d9>, & minimize A=#$%
́ There are
-
B
2-!# total solutions (huge search space)
́ Need to compute exact d9>, (compute intensive task)
́ CUDA assisted simulated annealing (SA) could be used for limited N & K.

14
CPU
GPU
GPU threads
Data transfer
CPU thread
Figure credit: Nvidia
Optimizing PAC codes (cont.)
́ 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

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 A and c, and compute the d9>,
́ d9>, improves keep with probability 1, otherwise accept with probability
e
!
C&'
()#*
,where Temp is the temperature used by SA, and ΔE is difference in
energies of the current solution and previous solution

16
[1] Bioglio, Valerio, et al. "Minimum-distance based construction of multi-kernel polar codes." GLOBE COM 2017-2017 IEEE Global Communications Conference. IEEE, 2017.
́ 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]

Results
17
́ Implemented SA in CUDA-C++
́ Could search up to block length 64
́ N = 64 , possible solutions 10AD
,
our
algorithm searched only for 10D

Results (cont.)
18
[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]
́ Our newly discovered (64,32) PAC codes
have d9>, 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]
́ A#+ = 720 (Ours)
́ A#+ = 12878 [1]

Results (cont.)
19
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 .
́ Our newly discovered (32,18) PAC codes
have d9>, 6
́ 0.49 dB less SNR @ 10!/
FER as compared
to the best-known minimum distance
codes in the literature[1]
́ AE=110(our)
́ AE=543[1]

Results (cont.)
20
[1]
[2]
[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 .
[2] Solé, Patrick, et al. "Linear Programming Bounds on the Kissing Number of q-ary Codes." 2021 IEEE Information Theory Workshop (ITW). IEEE, 2021.
́ 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 A%
́ We have general constructions for some of these codes

21
[1]
[2]
[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 .
[2] Solé, Patrick, et al. "Linear Programming Bounds on the Kissing Number of q-ary Codes." 2021 IEEE Information Theory Workshop (ITW). IEEE, 2021.

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
22

23
Thank you!