Member, IEEE Samet Gelincik

Member, IEEE Philippe Mary

Member, IEEE Anne Savard

Jean-Yves Baudais

A Pre-Transformation Method to Increase the Minimum Distance of Polar-Like Codes

Reed Muller (RM) codes are known for their good minimum distance. One can use their structure to construct polar-like codes with good distance properties by choosing the information set as the rows of the polarization matrix with the highest Hamming weight, instead of the most reliable synthetic channels. However, the information length options of RM codes are quite limited due to their specific structure. In this work, we present sufficient conditions to increase the information length by at least one bit for some underlying RM codes and in order to obtain pre-transformed polar-like codes with the same minimum distance than lower rate codes.The proofs give a constructive method to choose the row triples to be merged together to increase the information length of the code and they follow from partitioning the row indices of the polar encoding matrix with respect to the recursive structure imposed by the binary representation of row indices. Moreover, our findings are combined with the method presented in [2] to further reduce the number of minimum weight codewords. Numerical results

show that the designed codes perform close to the meta-converse bound at short blocklengths and better than the polarization-adjusted-convolutional polar codes with the same parameters.

Index Terms

Polar codes, Reed Muller codes, minimum distance, finite block length.

I. INTRODUCTION

New usages and services of 5G and beyond wireless systems, such as machine type communication or ultra-reliable low latency communications are pushing the limits of channel coding by requiring efficient error correcting codes at short to moderate block lengths. Indeed, These usecases involve communicating objects that either occasionally transmit short packets at low power transmission to increase the device lifetime or because to meet stringent latency constraint [START_REF] Shirvanimoghaddam | Short block-length codes for ultra-reliable low latency communications[END_REF].

Polar codes, the first provably asymptotically capacity achieving error correcting codes over binary input memoryless channels [START_REF] Arikan | Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels[END_REF] with explicit construction, are currently used over the control channels of 5G networks [START_REF]3rd Generation Partnership Project (3GPP)[END_REF]. They also are envisioned for ultra-reliable low-latency communications and massive machine-type communications [START_REF] Bioglio | Design of polar codes in 5G new radio[END_REF] thanks to their low complexity successive cancellation based decoder. Unfortunately, standard polar codes do not show outstanding performance at short-to-moderate block lengths due to their poor minimum distance and a non-complete polarization [START_REF] Rowshan | Polarization-adjusted convolutional (pac) codes: Sequential decoding vs list decoding[END_REF]. Several methods, such as enhanced-Bose-Chaudhuri-Hocquenghem subcodes [START_REF] Trifonov | Polar subcodes[END_REF] and low-weight-bit polar codes [START_REF] Yuan | Polar code construction for list decoding[END_REF], have hence been proposed to improve their distance spectrum. Cyclic-redundancy-check (CRC) aided successive cancellation list (SCL) decoding, which boosts the performance by choosing the best decoding paths in a hierarchical tree, has been proposed in [START_REF] Tal | List decoding of polar codes[END_REF] and the obtained performances were further enhanced by optimizing the CRC polynomial to improve the minimum distance of the obtained codes [START_REF] Zhang | Crc code design for list decoding of polar codes[END_REF], [START_REF] Piao | Approaching the normal approximation of the finite blocklength capacity within 0.025 dB by short polar codes[END_REF]. The later was considered as the best code design in terms of Frame Error Rate (FER) up to the introduction of polarized adjusted convolutional (PAC) polar codes in [START_REF] Arıkan | From sequential decoding to channel polarization and back again[END_REF].

DRAFT [START_REF] Bioglio | Design of polar codes in 5G new radio[END_REF] PAC polar codes [START_REF] Arıkan | From sequential decoding to channel polarization and back again[END_REF], by choosing the information set of the polar codes according to the Reed-Muller (RM) rule, i.e. the rows of the polarization matrix with the highest Hamming weights, perform very close to the second-order rate approximation of the binary-input additive white Gaussian noise in the short block length regime. It is a special case of the convolutional pre-transformation with an upper-triangular matrix, which has been proven not to reduce the minimum distance of underlying RM code while reducing the number of minimum weight codewords if properly designed [START_REF] Li | On pre-transformed polar codes[END_REF]. Since polar codes are tailored for a given channel, authors in [START_REF] Elkelesh | Decoder-tailored polar code design using the genetic algorithm[END_REF] proposed a genetic algorithm to obtain the frozen set that minimizes the bit or block error rate of the code over additive white Gaussian noise channel and Rayleigh channel. The obtained polar code does not require CRC and the proposed method either outperform CRC-aided polar codes occasionally or performs equally well in terms of bit and block error rate. Since the construction proposed in [START_REF] Elkelesh | Decoder-tailored polar code design using the genetic algorithm[END_REF] is signal to noise ratio dependent, authors in [START_REF] Tonnellier | On systematic polarization-adjusted convolutional (PAC) codes[END_REF] proposed a genetic algorithm, extended from [START_REF] Elkelesh | Decoder-tailored polar code design using the genetic algorithm[END_REF], that relies on the distance spectrum of the code rather than an error rate criterion. This technique allows to achieve the normal approximation of the second-order rate in Gaussian noise channel. However, genetic algorithms are rather complex and strongly depend on the population size and its initial state. Contrarily, in our work, we give an explicit method to increase the minimum distance while adding additional information bits on the underlying RM code.

In [START_REF] Gelincik | Achieving pac code performance without extra computational complexity[END_REF], we proposed a method to decrease the number of low weight codewords compared to RM and PAC codes in the short block length regime. The approach relies on encoding some information bits by the sum of two or three rows of the polar encoding matrix. The pairs and triplets of the merged rows are determined via the connection between the binary representation of the selected row indices and their common 1 bit-positions. Notably, our designed codes achieve the same performance as PAC polar codes of the same parameters without extra computational complexity.

In this paper, we extend our previously proposed method [START_REF] Gelincik | Achieving pac code performance without extra computational complexity[END_REF] and state sufficient conditions April 13, 2022 DRAFT to increase the information length of some polar-like codes, i.e. increasing the rate for a fixed given codeword length, where the information set is built according to the RM rule. Moreover, we explicitly give the corresponding pre-transformation matrix to sustain the same minimum distance as the RM code. The analysis is conducted by extending the method introduced in [START_REF] Polyanskaya | Weight distributions for successive cancellation decoding of polar codes[END_REF] that partitions the row indices of the encoding matrix according to the indices of their binary representation. Numerical simulations show that our proposed code design outperforms the PAC polar codes with the same parameters in terms of FER, and performs close to the meta-converse (MC) bound thanks to the decrease in the number of minimum weight codewords achieved by our previously proposed algorithm in [2, Algortihm 1].

The rest of the paper is organized as follows. Section II introduces the notations and the important definitions that are used in the proofs of our findings. Section III presents our main contribution with the statement of three theorems. Theorems 3 and 4 state the conditions for which the row merging increases the Hamming weight of the resulting row for the case where there is no common 1-bit position among the binary representations of the row indices and when there are such common positions, respectively. Theorem 5 is the main result of the paper and claims that is possible to increase the information length without decreasing the minimum distance of the code. In Section IV, we present our proposed polar-like code design which increases the number of information bits while exhibiting a high minimum distance. Section V compares the performance of our proposed design with PAC polar codes and with the metaconverse bound. Finally, conclusions are drawn in Section VI.

II. PRELIMINARIES

A. Notations

The positions of elements in a vector of length N is indexed from 0 to N -1. Any vector of length N is considered as a row vector and is denoted by x or x N -1 . The j th entry of the vector x is denoted as x j . The set of positive integers is N and the binary field is F 2 . The set For any 0 ≤ j < 2 n , its n-bit binary representation is denoted by the vector b n j , or b j if it is clear enough from the context. The -th bit position of b j is denoted by b j, , 0 ≤ < n and the indexing is started from the least significant bit, which is placed at the rightmost position. The number of 1's and 0's in a vector is represented by i 1 (•) and i 0 (•), respectively.

The operator ∪ represents the element-wise 'OR' operation of binary vectors such that, for

all (j 1 , j 2 ) ∈ [0, 2 n ) 2 : b j 1 , ∪b j 2 , = 1, if b j 1 , = 1 or b j 2 , = 1 (1)
The operator ∩ represents the element-wise 'AND' operation of binary vectors such that

b j 1 , ∩b j 2 , = 1, if b j 1 , = b j 2 , = 1 (2)
The operator ⊕ denotes binary addition in F 2 .

B. Properties of the Polar Encoding Matrix

For any given N = 2 n , n ∈ N, the polarization matrix is G = G ⊗n 2 where

G 2 :=    1 0 1 1    (3)
April 13, 2022 DRAFT is the corresponding kernel matrix and ⊗ is Kronecker product. The jth row g j of G can be represented by

g j = ĝb j,n-1 ⊗ ĝb j,n-2 ⊗ • • • ⊗ ĝb j,0 (4)
where ĝ0 = [1 0] and ĝ1 = [ 1 1]. By (4), for a given n ∈ N, the jth row of G can be divided into n disjoint regions, i.e.

r j, =        0 2 -1 if b j, = 0 [r j,0 r j,1 • • • r j, -1 ] if b j, = 1 (5)
for ∈ [1, n) and r j,0 = ĝb j,0 . Close inspection of the recursive nature of r j, reveals that each bit position ∈ [0, n) of b j is associated with a set of positions at g j denoted by the index set

M ⊂ N M := {k : b k, = 1, k ∈ N } (6)
and M c := N \ M . The fact that g j,M = 0 N/2-1 if b j, = 0 imposes that g j,M c is independent from the value of b j, [START_REF] Gelincik | Achieving pac code performance without extra computational complexity[END_REF]. The following definition highlights this fact.

Definition 1. The projection of a row g j of the polar encoding matrix onto indices of M c is denoted by g j and given as

g j := ĝb j,n-1 ⊗ • • • ⊗ ĝb j, +1 ⊗ ĝb j, -1 • • • ⊗ ĝb j,0 (7)
Note that, by ( 5), b j, = 1 imposes that [r j,0 r j,1 • • • r j, -1 ] is copied to r j, and r j,t> is obtained with respect to corresponding bit values. Hence, the projection of g j onto M is the same as

g j,M c if b j, = 1 g j,M =        0 N 2 -1 if b j, = 0 g j if b j, = 1 (8)
The following definition is the generalization of Definition 1.

DRAFT April 13, 2022

Definition 2. The projection of row g j of the polar encoding matrix onto ∩ ∈B M c is denoted by g B j and g j | ∩ ∈B M c , and is given as

g B j : = g j |∩ ∈B M c = ĝb j,W(|W|-1) ⊗ ĝb j,W(|W|-2) ⊗ • • • ⊗ ĝb j,W(0) (9)
where

W := [0, n) \ B.
Note that, similar to (8), for any subset B 0 ⊂ B, the projection of

g j onto ∩ ∈B 0 M ∩ ˆ ∈B/B 0 M c ˆ is given by g j | ∩ ∈B 0 M ∩ ˆ ∈B\B 0 M c ˆ =      0 N |B| -1 if ∩ ∈B 0 b j, = 0 g B j if ∩ ∈B 0 b j, = 1 (10)

C. Row Merging Pre-transformed Polar-like Codes and RM Codes

A polar-like code (N = 2 n , k) ∈ N 2 , is constructed as

C = {c = uG : u ∈ F n 2 , u F = 0} ( 11
)
where F is the index set of the frozen bit positions, and A = N \ F is the information set.

For classical polar codes under SC decoding, the set A is the set of the most reliable bit subchannels [START_REF] Arikan | Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels[END_REF]. However in this paper, we allow to choose the information set differently. From this perspective, a RM(n, r) code of degree r can be seen as a polar-like code of information set

A = n p=n-r N p , N p := {t : i 1 (b t ) = p, t ∈ N }. (12)
In [START_REF] Hassani | Rate-dependent analysis of the asymptotic behavior of channel polarization[END_REF], the minimum distance of a polar-like code is given by

d(C) = min i∈A i 1 (g i ) (a) = 2 min i∈A i 1 (b i ) (13)
where (a) is due to [2, Theorem 2].

April 13, 2022 DRAFT

The pre-transformed polar-like codes [START_REF] Li | On pre-transformed polar codes[END_REF] is obtained through a pre-transformation matrix

T ∈ F N ×N 2 C P = {c = uTG : u ∈ F n 2 , u F = 0} ( 14
)
where T is an upper triangular matrix with T i,i = 1, i ∈ N and

F d := {j : T i,j = 1, i ∈ N , j > i} is the set of dynamic frozen bits. If T is restricted such that |{i : T i,j , i ∈ N }| ∈ {1, 2} ∀j ∈ F d ,
then T turns out to be a row merging pre-transformation matrix since some information bits are encoded with more than one row of the polarization matrix but any frozen row can be associated with at most one information row

c = uTG = u G (15)
with

gi = g i j∈P 1 ( ti )\i g j ( 16
)
where ti is the i-th row of T.

III. ADDING INFORMATION BITS TO RM INFORMATION SET BY SUSTAINING THE SAME MINIMUM DISTANCE

In this section, we present how to obtain triples of polarization matrix rows to keep the same minimum distance as the underlying RM code and state the size of information length increment for some given parameters. Let T ⊆ N be any subset of row indices of the polarization matrix G and i ∈ N \ T . Then, by g T and g {i,T } , we denote

g T = t∈T g t and g {i,T } = g i ⊕ g T (17)

A. Preliminary Theorems

For the sake of completeness, we first state Theorem 2 of [START_REF] Gelincik | Achieving pac code performance without extra computational complexity[END_REF] and give a corollary that will be exploited later on in this paper.

DRAFT April 13, 2022

Theorem 1. [2, Theorem 2] Let T ⊆ N be any subset of row indices of polar-like code generator matrix G N . Then, the Hamming weight of the sum of the rows g j , j ∈ T is given by

i 1 g T ) = |T | w=1 (-2) w-1 T w ⊂T 2 i 1 ¯ j∈T w b j ( 18
)
where T w is any subset of T with w elements.

Corollary 1. Let Π : F n 2 → F n 2 be a permutation on binary representations of j ∈ N and T be the index set obtained by applying permutation Π to the binary representations of elements of

T : b j = Π(b j ), j ∈ T and j ∈ T . Then, i 1 (g T ) = i 1 (g T ) (19)
Proof: The number of common 1-bits will not change with permutation for any subset

T w ⊂ T , i.e., i 1 ( ∩j∈T w b j ) = i 1 ( ∩j∈T w Π(b j )) = i 1 ( ∩j ∈Π T w b j ) = i 1 ( ∩j ∈ T w b j ) (20)
then, by [START_REF] Hassani | Rate-dependent analysis of the asymptotic behavior of channel polarization[END_REF], the Hamming weight does not change.

The following theorem is also used to obtain subsequent results of this paper. It basically states that for any given set of rows of the polarization matrix, the Hamming weight of the sum of all rows is lower bounded by the maximum Hamming weight of the sum of a subset of rows whose binary representations are zero at the corresponding binary indices.

Theorem 2. For any given T ⊆ N the Hamming weight of g T is lower bounded by

i 1 (g T ) ≥ max ∈[0,n) i 1 (g T 0 ) ( 21
)
where

T 0 := {k : b k, = 0, k ∈ T }. Proof: For any u, v ∈ F 1×N 2 , we have i 1 (u ⊕ v) + i 1 (v) = i 1 (u) + i 1 (v) -2 • i 1 (u ∩v) + i 1 (v) April 13, 2022 DRAFT = i 1 (u) + 2 • (i 1 (v) -i 1 (u ∩v) ≥0 ) ≥ i 1 (u). (22)
Then, note that for any j ∈ N

i 1 (g j ) =        i 1 (g j ) if b j, = 0 2 • i 1 (g j ) if b j, = 1 (23)
for any ∈ [0, n) due to [START_REF] Rowshan | Polarization-adjusted convolutional (pac) codes: Sequential decoding vs list decoding[END_REF] and [START_REF] Trifonov | Polar subcodes[END_REF]. Therefore, for any ∈ [0, n) we can write

i 1 (g T ) = (g T |M c ) + (g T |M ) (a) = i 1 ( j∈T g j ) + i 1 ( j∈T g j I{b j, = 1}) = i 1 ( j∈T g j I{b j, = 0} j∈T g j I{b j, = 1}) + i 1 ( j∈T g j I{b j, = 1}) (b) ≥ i 1 ( j∈T g j I{b j, = 0}) = i 1 ( j∈T 0 g j ) (c) = i 1 ( j∈T 0 g j ) (24)
where (a) is due to ( 7) and ( 8), (b) is due to ( 22) and (c) is due to (23).

Theorem 3. Let C be a polar-like code with information set A = n p= +1 N p . and (i, j, k)

be a triple such that (i,

j) ∈ N , ≥ 2, k ∈ N 2 and i 1 (b i ∩b j ) = i 1 (b i ∩b k ) = i 1 (b j ∩b k ) = 0.
Moreover, let C be another polar-like code that encodes an additional information bit by

g i ⊕ g j ⊕ g k , i.e. C := {C} ∪ {c : c = g {i,j,k} ⊕ g T , T ⊆ A}. ( 25
)
Then, the minimum distance of C is the same as C, i.e.

d( C) = min{d(C), min T ⊆A i 1 (g {i,j,k} ⊕ g T )} = d(C) = 2 +1 (26)
Proof: The proof is given in Appendix VII-B.

DRAFT April 13, 2022

B. Merging Three Rows with Common 1-bit Positions

The following theorem is a generalization of Theorem 3 and states the sufficient conditions on the rows of a triple with some common 1-bit positions in their binary representations, to be merged together such that the minimum distance of the underlying RM code is preserved.

Theorem 4. Let C be a polar-like code with information set A = n p= +1 N p . and (i, j, k) be a triple such that

P 1 (b i ∩b j ) = P 1 (b i ∩b k ) = P 1 (b j ∩b k ) = ∅, (i, j) ∈ N , k ∈ N i 1 (b i ∩b j )+2 , ≥ i 1 (b k ).
Let the code C be:

C := {C} ∪ {c : c = g {i,j,k} ⊕ g T , T ⊆ A} (27)
Then,

d( C) = d(C) = 2 +1 (28)
Proof: Since

d( C) = min{d(C), min T ⊆A i 1 (g {i,j,k} ⊕ g T )} (29)
it is sufficient to prove the following statement

i 1 (g {i,j,k} ⊕ g T ) ≥ 2 +1 , ∀T ⊆ A. (30)
For any T ⊆ A, the index set can be divided into two subsets such that

T := {t : P 1 (b t ) ∩ P 0 (b i ∪b j ∪b k ) = ∅, t ∈ T } (31)
and T = T \ T . Then,

i 1 (g {i,j,k} ⊕ g T ⊕ g T ) (a)
≥ max

p 0 ∈P 0 (b i ∪b j ∪b k ) i 1 (g {i,j,k} ⊕ g T t∈ T g t I{b t,p 0 = 0}) (b) ≥ max p 1 ∈P 0 (b i ∪b j ∪b k )\p 0 i 1 (g {i,j,k} ⊕ g T t∈ T g t I{b t,p 0 = b t,p 1 = 0}) . . . April 13, 2022 DRAFT (c) ≥ i 1 (g {i,j,k} ⊕ g T t∈ T g t I{b t,p 0 = b t,p 1 =• • •= b t,p n-2 -1 = 0}) (d) = i 1 (g {i,j,k} ⊕ g T ) (32)
where

{p 0 , p 1 , • • • , p n-2 -1 } = P 0 (b i ∪b j ∪b k )
, where (a), (b) and (c) follow from the repeated application of Theorem 2, and (d) comes from (31), which implies that there is no t ∈ T such

that P 1 (b t ) ∩ {p 0 , p 1 , • • • , p n-2 -1 } = ∅.
This means that the Hamming weight of g {i,j,k,T } is lower bounded by the Hamming weight of g {i,j,k, T } . Therefore, in the following, we will proceed the proof for T . Now, assume that W = P 1 (b i ∩b j ), i.e., W = P 1 (b i ∩b j ∩b k ) as well, by assumption. Then, by partitioning the row indices of the polar encoding matrix respect to binary bit positions W, we obtain the following expression

i 1 (g {i,j,k} ⊕ g T ) = i 1 (g {i,j,k} ⊕g T |M c W(|W|-1) ∩M c W(|W|-2) ∩• • •∩M c W(0) ) + i 1 (g {i,j,k} ⊕g T |M c W(|W|-1) ∩M c W(|W|-2) ∩• • •∩M W(0) ) . . . + i 1 (g {i,j,k} ⊕g T |M W(|W|-1) ∩M W(|W|-2) ∩• • •∩M W(0) ) (a) = i 1 (g W {i,j,k} t∈ T g W t ) + i 1 (g W {i,j,k} t∈ T g W t I{b t,W(0) = 1}) . . . + i 1 (g W {i,j,k} t∈ T g W t I{b t,W(|W|-1) =b t,W(|W|-2) =• • • = b t,W(0) = 1}) (33)
where (a) is due to ( 9) and [START_REF] Tal | List decoding of polar codes[END_REF]. Since P 1 (b i ) \ P 1 (b i ∩b j ), P 1 (b j ) \ P 1 (b i ∩b j ) and P 1 (b k ) \ P 1 (b i ∩b k ) comply with the conditions of Theorem 3, each term of the partition is lower bounded by 2 -|W|+1 . Then,

i 1 (g {i,j,k} ⊕ g T ) ≥ 2 i 1 (b i ∩b j ) • (2 -i 1 (b i ∩b j )+1 ) = 2 +1 (34)
DRAFT [START_REF] Bioglio | Design of polar codes in 5G new radio[END_REF] where |W| = i 1 (b i ∩b j ).

In the following, we state the sufficient conditions to increase the information length by multiple bits for a fix codeword length. Thanks to the symmetry imposed by Corollary 1, we apply a permutation Π to any given row triple satisfying the conditions of Theorem 4 to have the following form

P 1 (b i ∪b j ∪b k ) P 0 (b i ∪b j ∪b k ) (35)
and

P 1 (b i ∩b j ∩b k ) P 1 (b i ∪b j ∪b k ) \ P 1 (b i ∩b j ∩b k ) (36)
and

P 1 (b k ) \ P 1 (b i ∩b j ) P 1 (b j ) \ P 1 (b i ∩b j ), P 1 (b k ) \ P 1 (b i ∩b j ) P 1 (b i ) \ P 1 (b i ∩b j ) (37)
and

P 1 (b i ) \ P 1 (b i ∩b j ) P 1 (b j ) \ P 1 (b i ∩b j ), P 1 (b j ) \ P 1 (b i ∩b j ) P 1 (b i ) \ P 1 (b i ∩b j ) (38)
Moreover, let Π θ p be a left-circular shift permutation on the index set of binary representation

of p ∈ N , with θ ∈ [0, κ], κ = t 0 • I{t 1 > 0} + t 1 , t 0 = i 0 (b i ∪b j ∪b k ) and t 1 = i 1 (b i ∩b j ∩b k ). We have b Π θ p ,v = b p,v-θ+n (mod n) (39)
The following theorem is the main result of this paper. obtained by encoding each of the extra m ≤ t 0 + t 1 + 1 information bits with a merged row

triple g {Π θ i ,Π θ j ,Π θ k } . Then, d( C) = d(C) (40)
Proof: The proof is given in Appendix VII-C.

The following section explains how Theorem 5 is used in order to increase the information length of a polar-like code with RM information set by preserving the minimum distance.

IV. CODE CONSTRUCTION

Let us consider a triple (i, j, k) that satisfies the conditions of Theorem 4, (35), (36), (37) and (38). For any m ∈ [1, t 0 + t 1 + 1],

• Each of m -1 triples, i.e., {(i 0 , j 0 , k 0 ),

• • • , (i m-2 , j m-2 , k m-2 )
}, corresponds to one of consecutive left-circular shifts of (i, j, k).

• For all triples, the permutation of their binary representations such that the smallest element among all the triples is maximized, is searched. This prevents from adding more badly polarized bit sub-channels to the information set. Indeed, with Corollary 1, the code constructed by any permutation of m-triples has in the same distance spectrum since the underlying information set is chosen by RM rule.

DRAFT April 13, 2022

• Algorithm 1 of [START_REF] Gelincik | Achieving pac code performance without extra computational complexity[END_REF] is applied to obtain the pairs (t, v), where t ∈ N +1 , v ∈ N , v > t, = i 1 (b i ), to decrease the number of minimum weight codewords.

Remark 1. Even though we have verified experimentally that the application of the third step does not decrease the minimum distance, an explicit proof of this evidence is complex and remains to be done.

The pre-transformation matrix is constructed by adding the smallest index of each of m-triple to the information set and the other two indices are considered as dynamic frozen bits. For any obtained pair (t, v), v is considered as the dynamic frozen bit. The pre-transformation matrix T, is such that

T a,a = T a,b = T a,c = T t,v = 1 (41)
where a ∈ N is the minimum of the triples, and v ∈ N is the associated index to any t ∈ N +1 by the application of Algorithm 1 of [START_REF] Gelincik | Achieving pac code performance without extra computational complexity[END_REF] to obtain pairs instead of triples.

Table I summarizes the characteristics of the codes that we can construct with our method.

Each entry of the table is a triple (m, k, d) where m is the number of information bits that can be added on the initial k information bits and d is the minimum distance. The code parameters are given according to two other parameters, (n, r) representing the recursive number and the order of the RM polar codes, respectively. Moreover,'-' means that Theorem 5 cannot be applied for the corresponding RM(n, r). For n = 6 and n = 7, we have codewords of length 64 and 128

respectively. It can be seen that, for instance, for a block length 128 and r = 3, the code rate can be extended from 23/64 to 24/64 while keeping the same minimum distance, which is an interesting improvement at this short block length.

V. SIMULATION RESULTS

We numerically compare in Figure 1 our proposed design (PD) with PAC codes and the saddle-point approximation of the MC (SMC) bound [START_REF] Anada | An upper bound on the error induced by saddlepoint approximationsapplications to information theory[END_REF] for the binary input additive white For PAC codes, the additional information indices are chosen as the most reliable bit subchannel indices from the set N , which are the highest indices due to partial ordering [START_REF] Schürch | A partial order for the synthesized channels of a polar code[END_REF].

We optimize the polynomial of the convolutional code with memory length 7 to minimize the number of minimum weight codewords. We implemented the algorithm [START_REF] Li | An adaptive successive cancellation list decoder for polar codes with cyclic redundancy check[END_REF] with a large list size, i.e. 5 • 10 4 , and we choose the one that leads to the minimal number of second minimum weight codewords since the number of minimum weight codewords does not change for a few increment of the information length. Our proposed design (PD) outperforms PAC codes for the entire range of E b /N 0 , since, at short block lengths, the minimum distance plays an important role in the SCL decoding with large list sizes. In particular, for (128, 66) code, while our design performs within 0.25 dB of SMC bound at FER of 3.10 -4 , PAC code achieves the same performance with 0.4 dB of additional power. For (128, 100) codes, our design outperforms PAC code of about 0.2 dB at FER of 10 -3 .

VI. CONCLUDING REMARKS

In this work, we proposed a method to increase the information length of a polar-like code while keeping the same minimum distance with the underlying RM code. Our findings allow to reduce the number of minimum weight codewords of polar-like codes that perform closer to the MC bound than PAC codes with the same system parameters. We believe that this work may lead to a new method for code design, particularly at short block lengths, with interesting performance. The extension of this work to moderate block lengths is under investigation.

Theorem 6. For any pairs (i, j) ∈ N , N := {t : i 1 (b t ) = , t ∈ N }, such that i 1 (b i ∩b j ) = 0, the combination of g i ⊕ g j with higher hamming weight rows of polar encoding matrix is lower bounded by Hamming weight of g i ⊕ g j :

i 1 (g i ⊕ g j ⊕ g T ) ≥ i 1 (g i ⊕ g j ) (a) = 2 +1 -2 (42)
where T ⊆ ∪ n p= +1 N p and (a) is by Theorem 1.

Proof: For = 1, the statement of the theorem turns to be trivial due to the fact that

i 1 (g {i,j,T } ) ≥ 2 min k∈{i,j,T } i 1 (b k ) = i 1 (g i ⊕ g j ) for = 1.
Hence, in the following, the proof is conducted for ≥ 2.

Due to the symmetry imposed by Corollary 1, without losing generality we assume that

P 1 (b i ) = [0, -1] and P 1 (b j ) = [ , 2 -1].
In the following we use this assumption for the ease of presentation.

We can divide the index set into two subsets such that

T := {k : P 1 (b k ) ∩ [2 • , n) = ∅, k ∈ T } (43)
and T = T \ T . Then, by Theorem 2

i 1 (g i ⊕ g j k∈ T g k t∈ T g t ) ≥ max p 0 ∈[2• ,n) i 1 (g i ⊕ g j k∈ T g k t∈ T g t I{b t,p 0 = 0}) ≥ max p 1 ∈[2• ,n)\p 0 i 1 (g i ⊕ g j k∈ T g k t∈ T g t I{b t,p 0 = b t,p 1 = 0}) . . . (a) ≥ i 1 (g i ⊕ g j k∈ T g k t∈ T g t I{b t,p 0 =b t,p 1 = • • • = b t,p n-2 -1 = 0}) (b) = i 1 (g i ⊕ g j k∈ T g k ) (44)
where (a) comes from the repeated application of Theorem 2 in [2 , n), and (b) comes from (43), which implies for any t ∈ T , P 1 (b t ) ∩ [2 • , n) = ∅. Let us continue for T which is divided [START_REF] Bioglio | Design of polar codes in 5G new radio[END_REF] DRAFT into two subsets such that

T 0 :={k:P 1 (b k ) P 1 (b i ), P 1 (b k ) P 1 (b j ), k∈ T } (45)
and

T 1 :={k:P 1 (b k )⊃P 1 (b i ) or P 1 (b k )⊃P 1 (b j ),k∈ T } (46)
Two cases have to be investigated, i.e. when T 0 is not empty and T 0 is empty.

Case 1, T 0 = ∅: The elements of this set are partitioned with respect to the Hamming weights of their binary representations:

T 0 = n- d=1 T 0 +d , T 0 +d := {k : i 1 (b k ) = + d, k ∈ T 0 } (47)
Now, let us assume that d * be the minimum number such that T 0 +d is not empty, i.e.,

d * = min{d : T 0 +d = ∅, n -≥ d ≥ 1}. Note that for any t ∈ T 0 +d * , ∃p 0 ∈ P 0 (b i ) ∩ P 0 (b t ) ∩ P 1 (b j ) and p 1 ∈ P 1 (b i ) ∩ P 0 (b j ) ∩ P 0 (b t ) such that i 1 (g i ⊕ g j ⊕ g T 0 ⊕ g T 1 ) (a) ≥ i 1 (g i I{b i,p 0 = 0} ⊕ g j I{b j,p 0 = 0} ⊕ g t I{b t,p 0 = 0} k∈ T 0 \t g k I{b k,p 0 = 0} k∈ T 1 g k I{b k,p 0 = 0}) (b) ≥ i 1 (g i ⊕ g t k∈ T 0 \t g k I{b k,p 0 = 0} k∈ T 1 g k I{b k,p 0 = 0}) (c) ≥ i 1 (g i I{b i,p 0 = b i,p 1 = 0}g t I{b t,p 0 = b t,p 1 = 0} k∈ T 0 \t g k I{b k,p 0 = b k,p 1 = 0} k∈ T 0 g k I{b k,p 0 = b k,p 1 = 0}) = i 1 ( k∈ T 0 g k I{b k,p 0 = b k,p 1 = 0}) (d) ≥ 2 +d * (48) DRAFT April 13, 2022
where (a) and (c) come from Theorem 2 and from the conditions imposed by ( 45) and (46), and (b) comes from the fact b j,p 0 = 1 by hypothesis. Moreover (d) is due to the fact that i 1 (g S ) ≥ min j∈S 2 i 1 (b j ) , i.e., by [START_REF] Arıkan | From sequential decoding to channel polarization and back again[END_REF]. That means if T 0 is not empty, the lower bound is satisfied whatever T 1 is empty or not.

Case 2, T 0 = ∅: The elements of T 1 are partitioned such as

T 1 i =        {k : P 1 (b k ) ⊃ P 1 (b i ), k ∈ T 1 } \ {2 2• -1} if 2 2• -1 ∈ T 1 {k : P 1 (b k ) ⊃ P 1 (b i ), k ∈ T 1 } otherwise (49)
and

T 1 j = {k : P 1 (b k ) ⊃ P 1 (b j ), k ∈ T 1 } (50)
Then, we obtain the total Hamming weight by partitioning the indices of row vectors into 2 subsets with respect to binary representation indices [0, -1] and using Definition 2:

i 1 (g i ⊕ g j ⊕ g T 0 i ⊕ g T 1 i ) = i 1 (g i ⊕g j ⊕ g T 0 i ⊕ g T 1 i |M c -1 ∩M c -2 ∩• • •∩M c 1 ∩ M c 0 ) + i 1 (g i ⊕g j ⊕ g T 0 i ⊕ g T 1 i |M c -1 ∩M c -2 ∩• • •∩M c 1 ∩M 0 ) • • • • • • + i 1 (g i ⊕g j ⊕ g T 0 i ⊕ g T 1 i |M -1 ∩M -2 ∩• • •∩M 1 ∩M 0 ) (51)
By Definition 2, we can write (51) in a more compact form by denoting M c p with 0 and M p with 1 for p ∈ [0, -1], then

i 1 (g i ⊕ g j ⊕ g T 1 i ⊕ g T 1 j ) = 2 -1 k=0 i 1 (g [0, -1] i I{P 1 (b i )⊃P 1 (b k )}⊕g [0, -1] j I{P 1 (b j )⊃P 1 (b k )} t∈ T 1 i g [0, -1] t I{P 1 (b t )⊃P 1 (b k )} t∈ T 1 j g [0, -1] t I{P 1 (b t )⊃P 1 (b k )}))
April 13, 2022 DRAFT and (b) comes from the fact that g t * , t * = max{{j, T 1 j }} is the only element from {j, T 1 j } such that (52) simplifies to

i 1 (g [0, -1] {i, T 1 i } t∈{j,T 1 j } g [0, -1] t I{P 1 (b t )⊃P 1 (b t * )}) = i 1 (g [0, -1] {i, T 1 i } ⊕ g [0, -1] t * ) = 2 -i 1 (g [0, -1] {i, T 1 i } ) (58)
by using [START_REF] Tal | List decoding of polar codes[END_REF]. When (54) and ( 56) are satisfied, (55) cannot be less than 2 +1 -2. This ends the proof for Theorem 6.

Theorem 7. For any pairs (i, j) ∈ N , ≥ 2, the combination of g i ⊕ g j with higher Hamming weight rows of polar encoding matrix is lower bounded by Hamming weight of

g i ⊕ g j i 1 (g i ⊕ g j ⊕ g T ) ≥ i 1 (g i ⊕ g j ) (59)
where T ⊆ ∪ n p= +1 N p .

Proof: We can divide the index set into two subsets such that

T := {k : P 1 (b k ) ∩ P 0 (b i ∪b j ) = ∅, k ∈ T } (60)
and T = T \ T .

Applying the same reasoning as in Theorem 6 in (44), the proof is conducted for T .

When i 1 (b i ∩b j ) = -1, the proof is trivial since

i 1 (g T ∪{i,j} ) ≥ min k∈ T ∪{i,j} 2 i 1 (b k ) = 2 i 1 (b i ) = 2 (61) and i 1 (g i ⊕ g j ) = 2 by [2, Theorem 2] if i 1 (b i ∩b j ) = -1. Now assume that i 1 (b i ∩b j ) = |P 1 (b i ∩b j )| ≤ -2 and let W = P 1 (b i ∩b j )
, which is the index set of common one bit positions of b i and b j . Then, by partitioning the row indices of the polar encoding matrix, we obtain the following expression

i 1 (g {i,j} ⊕ g T ) = i 1 (g {i,j} ⊕g T |M c W(|W|-1) ∩M c W(|W|-2) ∩• • •∩M c W(0) ) (62)
+ i 1 (g {i,j} ⊕g T |M c W(|W|-1) ∩M c W(|W|-2) ∩• • •∩M W(0) )
April 13, 2022 DRAFT . . .

+ i 1 (g {i,j} ⊕g T |M W(|W|-1) ∩M W(|W|-2) ∩• • •∩M W(0) ) (a) = i 1 (g W {i,j} k∈ T g W k ) + i 1 (g W {i,j} k∈ T g W k I{b k,W(0) = 1})
. . .

+ i 1 (g W {i,j} k∈ T g W k I{b k,W(|W|-1) = b k,W(|W|-2) = • • • = b k,W(0) = 1})
where (a) is due to ( 9) and [START_REF] Tal | List decoding of polar codes[END_REF]. By Theorem 6, each term of the partition is greater than

2 -|W|+1 -2 since |P 1 (b k ) ∩ P 1 (b i ⊕ b j )| > -|W| for any k ∈ T by assumption. Then, i 1 (g i ⊕ g j ⊕ g T ) ≥ 2 i 1 (b i ∩b j ) • (2 -i 1 (b i ∩b j )+1 -2) = 2 +1 -2 i 1 (b i ∩b j )+1 (a) = i 1 (g i ⊕ g j ) (63)
where (a) is due to Theorem 1.

B. Proof of Theorem 3

The proof relies on Theorem 6, given at the beginning of the appendices. Theorem 6 states that, for any given pair of rows with the same Hamming weight and no intersection in their binary representations, the Hamming weights of combination of the given pair with any subset of rows with higher Hamming weights is lower bounded by the Hamming weight of the given pair.

Since

d( C) = min{d(C), min T ⊆A i 1 (g {i,j,k} ⊕ g T )} (64)
it is sufficient to prove the following statement

i 1 (g {i,j,k} ⊕ g T ) ≥ 2 +1 , ∀T ⊆ A (65)
to prove the theorem.

DRAFT [START_REF] Bioglio | Design of polar codes in 5G new radio[END_REF] We can divide the index set into two subsets such that

T := {t : P 1 (b t ) ∩ P 0 (b i ∪b j ∪b k ) = ∅, t ∈ T } (66)
and T = T \ T . Then by Theorem 2

i 1 (g {i,j,k} ⊕ g T ⊕ g T ) ≥ max p 0 ∈P 0 (b i ∪b j ∪b k )) i 1 (g {i,j} ⊕ g T t∈ T g t I{b t,p 0 = 0}) ≥ max p 1 ∈P 0 (b i ∪b j ∪b k ))\{p 0 } i 1 (g {i,j,k} ⊕ g T t∈ T g t I{b t,p 0 = b t,p 1 = 0}) . . . ≥ i 1 (g {i,j,k} ⊕g T t∈ T g t I{b t,p 0 =b t,p 1 = • • • = b t,p n-2 -1 = 0}) (a) = i 1 (g i ⊕ g j ⊕ g k ⊕ g T ) (67)
where {p 0 , p 1 , • • • , p n-2 -1 } = P 0 (b i ∪b j ∪b k ) and (a) comes from (66), which implies for any

t ∈ T , P 1 (b t ) ∩ P 0 (b i ∪b j ∪b k ) = ∅.
This result means that the Hamming weight of g {i,j,k,T } is lower bounded by the Hamming weight of g {i,j,k, T } . Therefore, in the following, the proof is conducted for T .

We divide T into three subsets

Tk,1 = {t : P 1 (b t ) ⊃ P 1 (b k ), t ∈ T } (68) Tk,2 = {t : |P 1 (b t ) ∩ P 1 (b k )| = 1, t ∈ T } (69) T0 = T \ { Tk,1 ∪ Tk,2 } (70)
In the following, we show that the theorem holds whatever the sets Tk,1 and Tk,2 are empty or not.

Case 1, Tk,1 = ∅ and Tk,2 = ∅: Since, k ∈ N 2 , we denote {p 1 , p 2 } = P 1 (b k ). Then, by partitioning the row indices of the polar encoding matrix, we obtain the following expression:

i 1 (g i ⊕ g j ⊕ g k ⊕ g T ) = i 1 (g i ⊕ g j ⊕ g k ⊕ g T |M c p 1 ∩ M c p 2 ) + i 1 (g i ⊕ g j ⊕ g k ⊕ g T |M c p 1 ∩ M p 2 ) April 13, 2022 DRAFT g {p 1 ,p 2 } θ I{b θ,p 1 = 1}) (d) ≥ 2 +1 (71)
where (a) is due to ( 9) and ( 10), (b) and (c) are due to the fact that i

1 (u ⊕ v) + i 1 (v) ≥ i 1 (u),
i.e., by (22), and (d) is by [START_REF] Arıkan | From sequential decoding to channel polarization and back again[END_REF], i.e., the Hamming weight of any row at each expression is at least 2 . This means that if neither Tk,1 nor Tk,2 is empty, the lower bound is satisfied whatever T0 .

Case 2, Tk,1 = Tk,2 = ∅: By partitioning the row indices with respect to {p 1 , p 2 } = P 1 (b k ),

we obtain the following expression:

i 1 (g i ⊕ g j ⊕ g k ⊕ g T ) = i 1 (g i ⊕ g j ⊕ g k ⊕ g T |M c p 1 ∩ M c p 2 ) + i 1 (g i ⊕ g j ⊕ g k ⊕ g T |M c p 1 ∩ M p 2 ) + i 1 (g i ⊕ g j ⊕ g k ⊕ g T |M p 1 ∩ M c p 2 ) + i 1 (g i ⊕ g j ⊕ g k ⊕ g T |M p 1 ∩ M p 2 ) = i 1 (g {p 1 ,p 2 } i ⊕ g {p 1 ,p 2 } j ⊕ g {p 1 ,p 2 } k θ∈ T0 g {p 1 ,p 2 } θ ) + i 1 (g {p 1 ,p 2 } k ) ≥i 1 (g {p 1 ,p 2 } i ⊕g {p 1 ,p 2 } j θ∈ T0 g {p 1 ,p 2 } θ
) by ( 22) comply with the conditions of Theorem 6. Hence, i 1 (g {p 1 ,p 2 } {i,j, T0 } ) ≥ 2 +1 -2, and 2 • i 1 (g

{p 1 ,p 2 } k ) = 2.
The same result can be shown for the other cases of Tk,1 , Tk,2 by following similar steps.

C. Proof of Theorem 5

The proof of this theorem is based on Theorem 2 and Theorem 7. The latter is a generalization of Theorem 6 for the case where there are some common 1-bit indices in the intersection of the binary representations of the pair.

For m = t 0 + t 1 + 1, the code C is given as

C = {C} D⊆[0,t 0 +t 1 ] {c : c = θ∈D g {Π θ i ,Π θ j ,Π θ k } ⊕ g T , T ⊆ A} (73)
and hence, it is sufficient to prove the following statement

i 1 ( θ∈D g {Π θ i ,Π θ j ,Π θ k } ⊕ g T ) ≥ 2 +1 , (74)
for any D ⊆ [0, t 0 + t 1 ] and T ⊆ A.

The proof is done for the whole set {g Π d i ⊕ g Π d j ⊕ g Π d k }, d ∈ [0, t 0 + t 1 ] and the case i 0 (b i ∪b j ∪b k ) > i 1 (b i ∩b j ∩b k ). The same result can be found by following similar steps for any combination of {g Π d i ⊕ g Π d j ⊕ g Π d k }, d ∈ [0, t 0 + t 1 ] and other cases such as i 0 (b i ∪b j ∪b k ) = i 1 (b i ∩b j ∩b k ) or i 0 (b i ∪b j ∪b k ) = 0. The proof can be conducted the same way for all m < t 0 + t 1 + 1 and the proof is complete.

≥ i 1

t 0 +t 1 d=0 g n-2 {Π d i ,Π d j ,Π d k } ⊕ g n-2 T + 2 -1 (d) ≥ i 1   t 0 +t 1 d=0 t∈{Π d i ,Π d j ,Π d k } g n-2 t I{b t,n-1 = b t,t 0 = • • • = b t,t 1 = 0} t∈T g n-2 t I{b t,n-1 = b t,t 0 = • • • = b t,t 1 = 0}   + 2 -1 (e) = i 1 g n-2 Π t 1 i ⊕ g n-2 Π t 1 j t∈T g n-2 t I{b t,n-1 = b t,t 0 = • • • = b t,t 1 = 0} + 2 -1 (f ) ≥ i 1 g n-2 Π t 1 i ⊕ g n-2 Π t 1 j + 2 -1 (g) = 2 +1 -2 i 1 (b i ∩b j )+1 + 2 -1 (h) ≥ 2 +1 (75)
DRAFT April 13, 2022

Figure 1

 1 Figure 1 plots the frame error rate (FER) versus E b /N 0 for a code length of N = 128 in an additive white Gaussian noise channel and two information length, i.e. k = 66 and k = 100.

For

  the considered case, the main steps are summarized in (75) on top of the next page, where (a) is due to the fact that M c n-2 ∩ M n-2 = ∅, (b) is due to (8), (c) is due to the fact that the minimum Hamming weight of any row involved in the right-hand side of the equation is 2 -1 , (d) is due to Theorem 2, (e) is due to (35), (36) and (37), (f) is sinceΠ t 1 i , Π t 1 j and {t : b t,n-1 = b t,t 0 = • • • = b t,t 1 = 0, t ∈ T }comply with the conditions of Theorem 7, (g) is due to Theorem 1 and (h) is due to the assumption i 1 (b i ∩b j ) ≤ -2.

Table I NUMBER

 I OF ADDITIONAL INFORMATION BITS m THAT CAN BE ADDED ON TOP OF THE INFORMATION LENGTH k FOR THE MINIMUM DISTANCE d ACCORDING TO THE RECURSION NUMBER n AND ORDER r OF THE UNDERLYING RM-POLAR CODE.

	n	r	2	3	4	5
	6		(1, 23, 16)	-	-	-
	7		-	(2, 66, 16) (1, 100, 8)	-

Theorem 5. Let C be a polar-like code with information set A = n p= +1 N p . Let (i, j, k) be a triple satisfying the conditions of Theorem 4 and (35), (36), (37), (38). Let C be a code

  April 13, 2022 DRAFT Gaussian noise channel. Our construction for the code (128, 66) is obtained by first adding two extra bits to the (128, 64) polar-like code with RM information set and then by applying [2, Algortihm 1] to obtain (t, v) pairs such that i 1 (b t ∩b v ) = 1. Similarly, the code (128, 100) is obtained by first adding one extra bit to the polar-like code (128, 99) with RM information set and then by applying [2, Algortihm 1] to obtain (t, v) pairs such that i 1 (b t ∩b v ) = 0.

This work has been partially supported by IRCICA, CNRS USR 3380, Lille, France and the French National Agency for Research (ANR) under grant ANR-16-CE25-0001 ARBurst. Part of the content of this paper has been

A. Preliminary Theorems

In this section, we provide preliminary results that are useful in the proof of Theorem 3 and Theorem 5.

DRAFT

April 13, 2022

where (a) is by Definition 2 and conditions imposed by (49) and (50), i.e., P 1 (b t )⊃P 1 (b k ) for any t ∈ {i, T 1 i }.

Note that since i 1 (g

≤ i 1 (g

where (a) is by ( 13) and (b) is by the property of polar encoding matrix that is

This can be deducted once it is recognized that, by [START_REF] Yuan | Polar code construction for list decoding[END_REF], each g

By (53), we can write (52) as

Note that the α is such that

where (a) is due to the fact that, when k = 2 -1 and by [START_REF] Tal | List decoding of polar codes[END_REF], g

DRAFT April 13, 2022