codes [2] have been extensively studied for applications in wireless and storage systems. Besides conventional applications of codes for error correction, a surge of new applications has also emerged in the past decade including crowdsourcing [3], [4], distributed storage [5], and speeding up distributed machine learning [6], [7]. To this end, new motivations have arisen to study codes with sparsity constraints on their generator and/or parity-check matrices. For instance, the stored data in a failed server needs to be recovered by downloading data from a few servers only, due to bandwidth constraints, imposing sparsity constraints in the decoding process in a distributed storage system. In crowdsourcing applications, e.g., when workers are asked to label items in a dataset, each worker can be assigned only a few items due to capability limitations, imposing sparsity constraints in the encoding process. More specifically, codes defined by sparse generator matrices become relevant for such applications [8], [9].

In this paper, we focus on polar codes in order to construct a sequence of codes defined by sparse GMs with practical utility, such as low decoding complexity, explicit construction, sufficiently fast decay in the error probability, and the potential to approach capacity at large block-length.

Channel polarization, introduced by Arıkan [2], [10], is one of the most recent breakthroughs in coding theory. Polar codes are a class of provably capacity-achieving channel codes with explicit construction for general BMS channels, and have attracted significant attention due to their error correction performance, as well as their low-complexity decoding algorithms. Within the ongoing fifth generation wireless systems (5G) standardization process, polar codes have been adopted for uplink and downlink control information for the enhanced mobile broadband (eMBB) communication service. Furthermore, polar codes and polarization phenomenon have been successfully applied to a wide range of problems including data compression [11], [12], broadcast channels [13], [14], multiple access channels [15], [16], physical layer security [17], [18], and coded modulations [19].

A related line of work on studying linear codes with sparsity constraints on their generator matrices is by associating them with sparse graph representations [20]. In this context, they are referred to as low-density generator matrix (LDGM) codes, also regarded as the counterpart of LDPC codes. The sparsity of the generator matrices of LDGM codes leads to a low encoding complexity, and has been adopted in applications such as lossy source compression [21] and multiple description coding [22]. In [23] and [24] it was pointed out that certain constructions of LDGM codes are not asymptotically good, a behavior which is also studied using an error floor analysis in [25] and [26].

In terms of the sparsity of the GM, the authors of [27] showed the existence of capacity-achieving codes over binary symmetric channels (BSC) using random linear coding arguments when the column weights of the GM are upper bounded by ϵN , for any ϵ > 0, where N is the code block length. Also, it is conjectured in [27] that column weight upper bounds that scale sublinearly in N suffice to achieve the capacity. For binary erasure channels (BEC), bounds that scale as O(log N ) suffice for achieving the capacity, again using random linear coding arguments [27]. Furthermore, the scaling exponent of such random linear codes are studied in [28]. Later, in [29], the existence of capacity-achieving systematic LDGM ensembles over any BMS channel with the expected value of the weight of the entire GM bounded by ϵN 2 , for any ϵ > 0, is shown. While the (ensemble-averaged) block-error probability for the codes goes to zero as the block-length grows large, the speed of decay in the error probability is not provided in [27] and [29].

In [8], the problem of label learning through queries from a crowd of workers was formulated as a coding theory problem. Due to practical constraints in such crowdsourcing scenarios, each query can only contain a small number of items. In [9], we considered the same setting as in [8] with the additional consideration that some workers may not respond to queries, a scenario that resembles a binary erasure channel. Then we showed that a combination of LDPC codes and LDGM codes gives a query scheme where the number of queries approaches the information-theoretic lower bound [9].

In the realm of quantum error correction, quantum low-density-generator-matrix (QLDGM) codes, quantum lowdensity-parity-check (QLDPC) codes, and other sparse-graphbased schemes have been extensively studied due to the small numbers of quantum interactions per qubit during the encoding and/or error correction procedure, avoiding additional quantum gate errors and facilitating fault-tolerant decoding. Amongst these schemes, the error correction performance of the LDGMbased codes proposed in [30] was shown to outperform all other Calderbank-Steane-Shor (CSS) and non-CSS codes of similar complexity.

In both applications highlighted above, the benefit of the LDGM codes follows from a certain upper bound on the column weights of the GM, ensuring the columns are relatively low weight. Motivated by these applications, the main goal of this work is to construct sequences of codes where all of the columns of the GM are low weight, where certain upper bounds on the weight will be specified later.

In this paper, we study capacity-achieving polar and polarbased codes over BMS channels with sparsity constraints on generator matrix column weights. Leveraging polar codes based on general kernels, with rates of polarization studied in [31], we show that capacity-achieving polar codes with column weights bounded from above by N s exist for any given s > 0, where N is the code block length. This verifies the conjecture given in [27]. There is, however, a trade-off between the sparsity parameter s and the rate of polarization, given by s 2 . For the case when the speed of decay for block-error probability and the GM sparsity are both constrained, we propose two new code constructions with sparse GM columns, which provide a better trade-off for s > 0.585. We first consider BEC, and propose a splitting algorithm termed decoderrespecting splitting (DRS) algorithm, which, roughly speaking, splits heavy columns in the GM into several light columns. Note that if one splits the heavy columns in an arbitrary manner to form a new GM, the code defined by the new GM may be substantially different from the original one in terms of the error probability and/or having a low-complexity decoder. Leveraging the fact that the polarization transform of a BEC leads to BECs, the DRS algorithm converts the encoder of a standard polar code into an encoder defined by a sparse GM without hurting the reliability of the bit-channels observed by the source bits. Furthermore, the specific structure of DRS enables a low-complexity successive cancellation decoder in a recursive fashion inheriting that of original polar codes. In particular, we show a sequence of codes defined by GMs with column weights upper bounded by N λ , for any λ > λ * ≈ 0.585 and the existence of a decoder with computation complexity O(N log N ) under which the blockerror probability is bounded by 2 -N β for any β < 0.5.

Next, for general BMS channels, we propose an enhancement of the DRS-based encoding scheme, referred to as augmented-DRS (ADRS) scheme, which requires additional channel uses and decoding complexity. In spite of these limitations, we show that there exists a sequence of capacityachieving codes, referred to as the polar-ADRS codes. The sequence of codes is defined by GMs with column weights upper bounded by N λ , for any λ > λ † ≈ 0.631, and can be decoded with complexity O(N log N ).

The rest of the paper is organized as follows. In Section II, we introduce basic notations and definitions for channel polarization and polar codes. Section III provides a sparsity result for polar codes with general kernels. In Section IV, we introduce the DRS algorithm and the ADRS scheme, and the corresponding code constructions over the BEC and BMS channels, respectively. The successive cancellation decoders are also described and shown to be of low computation complexity. Finally, Section V concludes the paper. The proofs for the results in Sections III and IV are included in the Appendix.

Let h b (•) denote the binary entropy function, exp 2 (x) denotes the function 2 x , ln(•) be the logarithmic function with base e, and log(•) be the logarithmic function with base 2. Z(W ) denote the Bhattacharyya parameter of a channel W .

We give formal definitions for the BMS channel and capacityachieving codes for readers' reference.

Definition 1: A binary memoryless symmetric channel (BMS) W : X → Y is a noisy memoryless channel with binary input alphabet X , and channel output alphabet Y, (we use X = {0, 1}, and assume Y is finite, in this paper.) such that Pr[Y = y|X = 0] = Pr[Y = ϕ(y)|X = 1] for all y ∈ Y for some involution ϕ on Y.

Definition 2: A type of code is said to be capacity achieving over a BMS channel W with capacity C = I(W ) > 0 if, for any given constant R < C, there exists a sequence of codes with rate R and the block-error probability vanishes as the block length N grows large. The block-error probability is evaluated under the maximum likelihood (ML) decoder, unless a different decoding scheme is specified.

The channel polarization phenomenon was discovered by Arıkan [2] and is based on the polarization transform as the building block. Let W denote the class of all BMS channels. The channel transform W → (W -, W + ) that maps W to W 2 , where W -: X → Y 2 and W + : X → Y 2 × X , is defined in [2] and is often referred to as a polarization recursion. Then a channel W s1,s2,...,sn with s i ∈ {-, +} , i = 1, 2, . . . , n, can be defined by applying the channel transform n times recursively, as in [2].

For N = 2 n , the polarization transform is obtained from

, and A ⊗n denote the n-fold Kronecker product of A. A polar code of length N is constructed by selecting certain rows of G ⊗n 2 as its generator matrix. More specifically, let K denote the code dimension. Then all the N bit-channels in the set {W s1,s2,...,sn : s i ∈ {-, +} for i = 1, 2, . . . , n}, resulting from the polarization transform, are sorted with respect to an associated parameter, e.g., their probability of error (or Bhattacharyya parameter), the best K of them with the lowest probability of error are selected, and then the corresponding rows from G ⊗n 2 are selected to form the GM. Hence, the GM of an (N, K) polar code is a K × N sub-matrix of G ⊗n 2 . Then the probability of error of this code, under successive cancellation (SC) decoding, is upper bounded by the sum of probabilities of error of the selected K best bit-channels [2].

It is shown in [31] that if G 2 is replaced by an l × l matrix G l , then polarization still occurs if and only if G l is an invertible matrix in F 2 and it is not upper triangular under any column permutation, in which case the matrix G l is called a polarization kernel. Furthermore, the authors of [31] provided a general formula for the speed of the error rate decay of polar codes constructed based on an arbitrary l × l polarization kernel G l . More specifically, let N = l n denote the block length and C denote the capacity of the channel. For any fixed β < E(G l ) and fixed code rate R < C, where E(G l ) denotes the rate of polarization (see [31,Definition 7]), there is a sequence of polar codes based on G l with probability of error P e under SC decoding bounded by P e (n) ⩽ 2 -N β , for all sufficiently large n. The rate of polarization E(G l ) is given by E(G l ) = 1 l l i=1 log l D i , where {D i } l i=1 are the partial distances of G l . More specifically, for G l = [g T 1 , g T 2 , . . . , g T l ] T , the partial distances D i are given by D i ≜ d H (g i , span(g i+1 , . . . , g l )) for i = 1, 2, . . . , l, where d H (a, b) is the Hamming distance between two vectors a and b, and d H (a, U ) is the minimum distance between a vector a and a subspace U , i.e., d H (a, U ) = min u∈U d H (a, u).

In this section we first show the existence of capacityachieving polar codes with generator matrices for which all column weights scale at most polynomially with arbitrarily small degree in the block length N , hence validating the conjecture in [27]. Second, we show that, for any polar code of rate 1, almost all of the column weights of the GM are polynomial in N .

Theorem 1: For any fixed s ∈ (0, 1) and any BMS channel, there are capacity-achieving polar codes under SC decoding, with generator matrices having column weights bounded by N s , where N denotes the block length of the code.

where l is an even integer such that l ⩾ 2

Hence, the rate of polarization E(G l ) = 1 2 log l 2 > 0, and there is a sequence of capacity-achieving polar codes constructed using G l as the polarizing kernel. Note that in G l , each column has weight at most 2 and, hence, the column weights of G ⊗n l are upper bounded by 2 n . By the specific choice of l, we have

where N = l s is the block length of the code. This completes the proof. Remark 1: While Theorem 1 provides a theoretical guarantee on the existence of capacity-achieving polar codes with sparse generator matrices, the sparsity comes at a cost. Specifically, the rate of polarization E(G l ) = 1 2 log l 2 ⩽ s 2 is smaller than that associated with the kernel G 2 , given by E(G 2 ) = 0.5. On the other hand, while the SC decoding complexity for polar codes defined by general l × l kernels behaves as O( 2 l l N log l N ) [31], in this case, the complexity scales as O(N log l N ) by considering the following viewpoint. Interleave (l/2) n copies of the polar code with block length 2 n based the standard G 2 kernel, to form a code with block length N = l n with an n-stage recursive encoder structure. By decoding each copy with complexity O(2 n log 2 n ) = O(n2 n ) under the SC decoder, the entire code can be decoded with complexity O((l/2

Since we can construct capacity-achieving codes with column weights upper bounded by N s with any fixed s > 0, by using polar codes, the question now is whether it is possible to further improve the sparsity of polar code GMs. For instance, we know it is possible to have an upper bound of O(log N ) on all the GM column weights of capacityachieving codes, over the BEC, by utilizing random linear ensembles [27]. For rate-1 polar codes, the proposition below answers the inquiry in the negative, by showing that almost all the GM columns have weights lower bounded by a polynomial in N .

Proposition 1: Given any l ⩾ 2, l × l polarizing kernel G l , and 1 l > r > 0, the fraction of columns in G ⊗n l with O(N r log l 2 ) Hamming weight vanishes as n grows large, where N = l n .

Proof: The proof is given in Appendix Section A. The trade-off highlighted in Remark 1 suggests that offthe-shelf polar code constructions with large kernels may not be the ideal option when the speed of decay of the error probability is a concern. However, the heaviest column in the polar code with kernel G 2 scales as Θ(N ) for any code rate. To construct codes with sparse GM and suitable decay of the error probability, in the next section, we propose a splitting algorithm for the generator matrix and investigate the resulting codes in terms of the error probability, GM column sparsity, and the decoding complexity.

When all columns of a matrix G are required to be sparse, that is, have low Hamming weights, a splitting algorithm is applied. Given a column weight threshold w u.b. , a splitting algorithm splits any column in G with weight exceeding w u.b. into columns that sum to the original column both in F 2 and in R, and that have weights no larger than w u.b. . Note that a column of G is left intact by the splitting algorithm as long as its Hamming weight does not only exceed w u.b. . Thus a splitting algorithm would be described as an algorithm which takes as input a column vector v and a weight threshold w u.b. , and returns a set of column vectors whose lengths are equal to the length of v. Given a matrix A with m columns and a threshold w u.b. , with a slight abuse of notation, the matrix generated by a splitting algorithm is defined as the matrix whose column vectors are those from the m sets, which are respectively the outputs of the algorithm for each column of A. For example, consider

and a splitting algorithm S. Let S(a i , w u.b. ), i = 1, 2, be the sets of vectors returned by S, given by

as the generator matrix, and G ′ denote the N ×N (1+γ) matrix generated by the splitting algorithm, where N = 2 n . A new code based on G ′ selects the same K rows of G ′ as the polar code C to form the generator matrix, where all the column weights are bounded by w u.b. . Such a code is referred to as a polar-based code corresponding to G ′ , or a PB(G ′ ) code, in this paper.

Note that more detailed description is needed to uniquely specify a splitting algorithm, which then determines the term γ and the performance of the PB(G ′ ) code. Specifically, the channel polarization phenomenon and the recursive encoding and decoding structure may be invalid when the GM is modified by the splitting algorithm. These changes also imply that the codes with the split GM may suffer from drawbacks such as weaker bounds on error probability and larger decoding complexity, as well as the rate loss with a multiplicative factor of 1 + γ, when compared to the polar codes. In this section, we introduce a splitting algorithms, referred to as the decoder-respecting splitting (DRS) algorithm, and two encoding schemes that are effective in avoiding the drawbacks. These schemes enable low-complexity SC decoders based on likelihood ratios that can be calculated with a recursive algorithm. Specifically, when the threshold w u.b. is chosen appropriately, we show in Section IV-A that the term γ goes to 0 exponentially fast in n, when the DRS algorithm is applied to columns of the matrix G = G ⊗n 2 . The encoding of the resulting PB(G ′ ) codes can be realized by a encoding scheme which inherits the recursive structure of the original polar codes, except only at locations that corresponds to a split of a column of G, as dictated by the DRS algorithm. At these locations, the exclusive-OR operations are removed and additional copies of the underlying channel are used. The PB(G ′ ) codes suffer only a negligible 1 + γ multiplicative factor of rate loss compared to the original polar codes for large n. For BEC, this sequence of codes is capacity-achieving with an error exponent of 1 2 , under a new SC decoding scheme (see Theorem 2 in Section IV-B). For general BMS channels, another encoding scheme, referred to as the ADRS scheme, is proposed in Section IV-C. This scheme introduces additional 'noise' nodes and requires even more copies of the underlying channel when the DRS algorithm requires a split. For codes generated by this scheme, results similar to that in Theorem 2 are available with a slightly stricter condition on the choice of w u.b. .

The main idea of the DRS algorithm is to construct a generator matrix that can be realized with an encoding pattern similar to conventional polar codes such that the column weights of the matrix associated with the diagram are at most w u.b. . The pseudo code for the algorithm is provided in Algorithm 1.

The core of the algorithm is the DRS-SPLIT function. When the weight of the input the vector x is larger than the threshold, it splits the vector in half into vectors x h and x t , and recursively finds two sets, Y h and Y t , composed of vectors with the length halved compared to the length of x. The vectors are then appended to the length of x, which collectively form the output of the function. For a vector u ∈ {0, 1}

Output: the set of vectors with length 2 n returned by DRS-SPLIT(w u.b. , v)

else if x t = 0 k×1 then 10:

end if end if 19: end function the weight of v exceeds the threshold, it is first split into x h = [0, 0, 0, 0] T and x t = [1, 1, 1, 1] T . Since x h is an all-zero vector, Y h is an empty set according to line 14 to 15. To compute Y t =DRS-SPLIT(2, [1, 1, 1, 1] T ), the function splits the input into half again, thereby obtaining

, the function proceeds to lines 7 and 8, and returns [0, 0, 0, 0, 0, 0, 1, 1] T , [0, 0, 0, 0, 1, 1, 0, 0] T . In order to analyze the effect of the DRS algorithm on the matrix G ⊗n 2 , we show that the size of the algorithm output does not depend on the order of a sequence of Kronecker product operations, where the size of a set of vectors stands for the number of vectors in the set. Suppose that the Kronecker product operations with the vector [1, 1] T for n 1 times and with the vector [0, 1] T for n 2 times are applied on a vector v, where n = n 1 + n 2 and the order of the operations is specified by a sequence (s 1 , s 2 , . . . , s n ) ∈ {-, +} n with |{i : s i = -}| = n 1 and |{i : s i = +}| = n 2 . Also, let v (i) denote the output of applying the first i Kronecker product operations on v. It is defined by the following recursive relation:

for i ⩾ 1 and the initial condition v (0) = v. We use v (s1,s2,...,si) instead of v (i) when the sequence is needed for clarity. The following lemma shows that any two vectors of the form v (s1,s2,...sn) will be split into the same number of columns under the DRS algorithm as long as the sequences associated with them contain the same number ofand + signs. Lemma 1: Let n = n 1 + n 2 and (s 1 , . . . , s n ) ∈ {-, +} n be a sequence with n 1 minus signs and n 2 plus signs. Let v (n) be the vector defined by a vector v and the sequence (s 1 , . . . , s n ) through equation (1). Then the size of the DRS algorithm output for v (n) depends only on the values n 1 and n 2 .

Proof: The proof is given in Appendix Section B.1. Let a K × N matrix M = [u 1 , u 2 , . . . , u N ] and a threshold w u.b. be given. Suppose that the DRS algorithm is applied to each column in M and the sum of the sizes of the output sets is N (1 + γ). Then DRS(M ) is defined as the K × N (1 + γ) matrix consisting of all the vectors in the output sets (with repetition).

We study the effect of the DRS algorithm in terms of the multiplicative rate loss, i.e., 1 + γ. Since all the columns of G ⊗n 2 are in the form of v (s1,s2,...,sn) with v = [0, 1] T or v = [1, 1] T , Lemma 1 substantially simplifies the analysis for γ. In particular, the following proposition shows an appropriate choice of w u.b. guarantees the existence of a sparse polarbased GM with vanishing γ.

Proposition 2: Let the columns of G ⊗n 2 be the inputs for the DRS algorithm and DRS(G ⊗n

2 ) be the N × N (1 + γ) matrix generated by the DRS algorithm for G ⊗n 2 . The term γ vanishes exponentially fast as n goes to infinity for any

For the effect of the DRS algorithm on G ⊗n 2 with finite n, we compute values of γ for various combinations of n and λ, as shown in Figure 1. The numerical results with 6 ⩽ n ⩽ 26 indicate that, for 0.5 ⩽ λ < 0.6, the multiplicative rate loss γ is larger with larger n, and for λ ⩾ 0.65, γ is smaller with larger n. The fact that the n = 26 does not provide the smallest γ for λ close to λ * should not be considered a contradiction to Proposition 2. Instead, the closer λ > λ * is, the larger n it takes for the exponential decay of γ to dominate.

In this section, we show two results for the polar-based code corresponding to DRS(G ⊗n 2 ) over the BEC. Such codes are referred to as the polar-DRS codes in this paper. First, we propose a low-complexity suboptimal decoder for the polar-DRS codes. Second, with the low-complexity suboptimal decoder, the polar-DRS codes are capacity-achieving for suitable column weight threshold.

It is known that when the channel transformation with kernel G 2 is applied to two BECs, the two new bit-channels are also BECs. Specifically, for two binary erasure channels W 1 and W 2 with erasure probabilities ϵ 1 and ϵ 2 , respectively, the polarized bit-channels W -(W 1 , W 2 ) and W + (W 1 , W 2 ) are binary erasure channels with erasure probabilities ϵ 1 +ϵ 2 -ϵ 1 ϵ 2 and ϵ 1 ϵ 2 , respectively.

The mutual information I(•) and Bhattacharyya parameter Z(•) of a BEC W with erasure probability ϵ are given by:

n , the function Bi2De(s 1 , s 2 , . . . , s n ) returns the decimal value of the binary string in which a minus sign for s i is regarded as a 0 and a plus sign as a 1, e.g., Bi2De(-, +, +) = (011 The following lemma shows that the bit-channel observed by each source bit is better in terms of the Bhattacharyya parameter when G ′ is the generator matrix instead of G.

Lemma 2: Let w u.b. and n be given, and let G denote G ⊗n 2 and G ′ denote DRS(G ⊗n 2 ). The following is true for any (s 1 , s 2 , . . . , s n ) ∈ {-, +} n :

.

Proof: The proof is given in Appendix C. Remark 2: A key to the proof of Lemma 2 is a recursive encoding scheme for the relationship x = uG ′ , where u and x are row vectors of lengths N = 2 n and N (1+γ), respectively. The encoding scheme is most easily understood by considering the low-complexity encoding structure for the standard polar code, as seen in [32], and replacing the exclusive-OR (XOR) operations at locations that correspond to the splitting operations dictated by the DRS algorithm. Specifically, when a split is required on a column of G, the corresponding XOR node is removed, the input bit for the 'worse' channel remains untouched, and two copies of the input bit for the 'good' channel are transmited through the underlying channel. For example, consider G = G ⊗3 2 . The encoding diagram for codes defined by G is shown in Figure 2a. We have

, where G ′ is the matrix DRS(G ⊗3

2 ) when w u.b. = 4. The encoding structure for G ′ is shown in Figure 2b. Since the first column is the only column of G split by the DRS algorithm when w u.b. = 4, we remove the XOR node that performs

, and assigns

Two solid circles, representing transparent nodes where the output variable(s) are identical to the input variable, are used to indicate the location of the removed XOR node. For the case when w u.b. = 2, the DRS algorithm would split the first column of G into three vectors, and the second, third, and fifth column once each. The corresponding encoding diagram is shown in Figure 3, where we color the solid circles associated with splits on the first, second, third, and fifth columns by black, green, orange, and blue, respectively.

We are ready to show the existence of a sequence of capacity-achieving codes over the BEC with GMs where the column weights are bounded by a polynomial in the blocklength, and that the block error probability under a low complexity decoder vanishes as n grows large.

Theorem 2: Let β < E(G 2 ) = 0.5, λ > λ * = h b ( 2 3 ) -1 3 ≈ 0.585, and a BEC W with capacity C be given. There exists a sequence of polar-based codes corresponding to DRS(G ⊗n 2 ) with the following properties for all sufficiently large n: (1) The error probability under a SC decoder is upper bounded by 2 -N β , where N = 2 n , (2) The Hamming weight of each column of the GM is upper bounded by N λ , (3) The rate approaches C as n grows large, and (4) The codes can be decoded by a SC decoding scheme with complexity O(N log N ).

Proof: Let the threshold for DRS algorithm be w u.b. = 2 nλ , G denote G ⊗n 2 , and G ′ denote DRS(G ⊗n 2 ). We prove the four claims in order. First, Lemma 2 shows that for a given n and any t > 0, the following is true:

Using [2, Theorem 2], for any β < 1 2 , we have

Let S G and S G ′ denote the sets of the sequences s ∈ {-, +} n that satisfy Z s G ⩽ 2 -N β and Z s G ′ ⩽ 2 -N β , respectively. Equation (2) guarantees that S G is a subset of S G ′ . Assume the code corresponding to G freezes the input bits observing bit-channels W s1s2...sn for all (s 1 , s 2 , . . . , s n ) / ∈ S G . For the code corresponding to G ′ , we use the bit-channels with the same index as the code corresponding to G, for transmission of information bits, and leave the rest as frozen. The probability of block error under SC decoding, which is described in the last part of this proof, for the code corresponding to G ′ , P e,G ′ , can be bounded above, as in [2], by the sum of the Bhattacharyya parameters of the bit-channels for the source bits (that are not frozen), that is,

where the second inequality follows because, for s ∈ S G , we must have s ∈ S G ′ and thus Z s G ′ ⩽ 2 -N β . From ( 3), for all sufficiently large n, we have P e,G ′ ⩽ N C2 -N β . With some calculus, one may show that, for any β ′ < 1 2 , P e,G ′ ⩽ 2 -N β ′ for all sufficiently large n.

The second claim follows from the fact that the GM for the code corresponding to G ′ is a submatrix of G ′ , and the Hamming weight of each column of G ′ is upper bounded by w u.b. = 2 nλ = N λ .

The third claim is a consequence of Proposition 2 and Lemma 2. The number of information bits of the code corresponding to G ′ is given by |S G |, and the length of the code is N (1 + γ). Hence the code rate is |S G | N (1+γ) . Since the term γ vanishes as n grows large, we have

Finally, we prove the claim for the existence of a lowcomplexity decoder. Just like that of the SC decoder for conventional polar codes with kernel G 2 , the decoding algorithm proceeds in a recursive manner. Let U 1 , . . . , U N be the inputs, and Y 1 , . . . , Y N1 , Y N1+1 , . . . , Y N1+N2 the outputs, where N 1 + N 2 = N (1 + γ), as shown in Figure 4b. However, while the polar code based on G ⊗n 2 , as shown in Figure 4a, is recursive in the encoder structure, i.e., the two encoding sub-blocks corresponding to G ⊗n-1 2 are identical, the code based on (G ⊗n 2 ) ′ is not, as the blocks W u n and W l n are not necessarily equal. In fact, when there is a split in the GM due to the DRS algorithm, i.e., when one or more of the XOR operations shown in Figure 4b is replaced by two solid black circle, the number of inputs of the block W l n will be larger than that of W u n . Let F ⊆ {1, . . . , N } be the set of the indices of the frozen bits. The decoder declares estimates Ûi of the inputs, for 1 ⩽ i ⩽ N , sequentially by:

where

, W n ) can be found in following four cases, and W n denotes the encoding block shown in Figure 4b. Let the symbol e denotes an erasure, and assume e ⊕ b = e for b ∈ {0, 1, e}. We write ψ i in place of

for the sake of space in the following.

• If i is odd and X i = U i ⊕ U i+1 , which corresponds to an unsplit XOR operation observed by U i ,

• If i is odd and X i = U i , which corresponds to a split XOR operation, ψ i ≜ Xi .

• If i is even and X i-1 = U i ⊕ U i-1 , which corresponds to an unsplit XOR operation,

Ûi-1 ̸ = e e, otherwise.

• If i is even and X i,1 = X i,2 = U i , which corresponds to a split XOR operation,

otherwise.

The estimates X1 , X3 , . . . , XN-1 and X2 , X4 , . . . , X2j,1 , X2j,2 , . . . , XN are found in a similar approach using the blocks W u n and W l n along with the outputs Y 1 , . . . , Y N1 and Y N1+1 , . . . , Y N1+N2 , respectively.

For the right-most variables, the blocks they observe are identical copies of the BEC W . Hence the estimates of the variables, denoted as

N1+N2 are naturally defined by the outputs of the channels, i.e., X

At each stage there are at most

estimates to make, and the recursion ends in log(N ) steps. Since each estimate is obtained with constant complexity, the total decoding complexity for the code based on DRS(G ⊗n 2 ) is bounded by O(N log N ). We evaluate the performance of the polar-DRS codes with n = 10 and λ = 0.6, 0.8, 1.0, under the SC decoding scheme described in the proof of Theorem 2, over the BEC with erasure probability ϵ = 0.5. In Figure 5a, the block error probabilities for the curves with smaller λ are smaller, due to the improvement of some of the Bhattacharyya parameters observed by the information bits. That is, there are sequences (s 1 , s 2 , . . . , s n ) ∈ {-, +} n for which the inequality in Lemma 2 is strict. However, after factoring in multiplicative rate loss γ, we may observe in Figure 5b that the performance of the codes with λ = 0.6 are substantially worse than the original polar code (λ = 1 curve), and those with λ = 0.8 deliver trade-off between code rate and error probability comparable to the original polar code, while guaranteeing the threshold w u.b. is one-fourth of the latter. Remark 3: We note that for general BMS channels, Lemma 2 may fail. One key part in the proof (see Appendix C) is the fact that the Bhattacharyya parameter for the bitchannel observed by U i is a non-decreasing function of those of W (X 1 ), . . . , W (X f (m) ) for i ⩽ 2 m , and of W (X f (m)+1 ), . . . , W (X 2f (m) ) for i > 2 m , when all the channels are BECs. We now provide an example where we see the argument for Lemma 2 fail for BMS channels.

The Bhattacharyya parameters for W 1 , W 2 are respectively 0.7666 and 0.7702. If m = 1 and B m is simply the kernel G 2 , the symbols X 1 , X 2 are functions of U 1 , U 2 given by

We now consider two possible cases for the pair

the Bhattacharyya parameters for the bit-channels observed by U 1 , U 2 are respectively 0.9147 and 0.5904. If (W (X 1 ), W (X 2 )) = (W 2 , W 2 ), the Bhattacharyya parameters for the bit-channels observed by U 1 , U 2 are respectively 0.9137 and 0.5932. We note that while the Bhattacharyya parameters for W (X 1 ), W (X 2 ) in the second case are no less than in the first case, the Bhattacharyya Fig. 6. ADRS scheme for a split XOR of first iteration of polarization.

parameter Z(U 1 ) in the second case is smaller than in the first case. With the above observation, one can not claim the validity of Theorem 2 for general BMS channels. This motivates a new code construction for general BMS channels.

This section introduces a capacity-achieving polar-based coding scheme with low-complexity decoder for general BMS channels. For general BMS channels, the Bhattacharyya parameter of the bit-channel W -cannot be expressed only in terms of parameters of the channel W . This implies that Lemma 2 and Theorem 2 are not applicable for channels other than BEC, as pointed out in Remark 3. A procedure that augments the generator matrix corresponding to G ′ , the output of the DRS algorithm for the matrix G ⊗n 2 , may be used to construct a capacity-achieving linear code over any BMS channel W .

1) ADRS Scheme: The encoding scheme, termed augmented-DRS (ADRS) scheme, avoids heavy columns in the GM and, at the same time, guarantees that the bit-channels observed by the source bits U i have the same statistical characteristics as when they are encoded with the generator matrix G ⊗n 2 . Specifically, the ADRS scheme modifies the encoder for G ⊗n 2 starting from the split XOR operations associated with the first polarization recursion, then the second recursion, and proceed all the way to the n-th recursion, where a XOR operation is split if and only if it is split in an encoder with generator matrix DRS(G ⊗n 2 ). Assume an XOR operation with operands U , where i 1 = Bi2De(s 1 , . . . , s j-1 , s j = -, s j+1 , . . . , s n )+1 and i 2 = Bi2De(s 1 , . . . , s j-1 , s j = +, s j+1 , . . . , s n ) + 1 = i 1 + 2 n-j , is to be split (see Section IV-B for the function Bi2De(•)). If j = 1, before modification, the variables U in Figure 6a. If the XOR operation is split according to DRS(G ⊗n 2 ), ADRS scheme replaces the structure by that given in Figure 6b, where n i1,1 is a Bernoulli(0.5) random variable independent of all the other variables.

If j ⩾ 2, assume that the ADRS modification for the split operations for the first (j -1) recursions are completed. Let n i1,j be a Bernoulli(0.5) random variable independent of all the other given variables. The part of encoding diagram to the right of U (n-j+1) i1 is replicated, where n i1,j takes the place of U (n-j+1) i1 in the replica. And then we let U

⊕ n i1,j . In addition, the part of encoding diagram to the right of U (n-j+1) i2 is replicated, and a copy of U (n-j) i2 is transmitted through the replica. The variable

. We demonstrate the procedure described above through the following example. Assume n = 3, N = 8, and w u.b. = 2.

2 is shown in Figure 7a, and the XOR operations that are split in DRS(G ⊗3 2 ) are marked in green and blue, which indicate the operations are due to the first and the second polarization recursions (i.e., s 1 and s 2 ), respectively. The notations

i , U

i . Replacing the XOR operations marked in green as described for the case of j = 1, the encoding diagram is now shown in Figure 7b. For the XOR operations marked in blue, we proceed by using the step for j ⩾ 2 and obtain the diagram shown in Figure 7b.

It can be noted that the bit-channels observed by each of U (j) i , for i = 1, 2, . . . , N and j = 0, 1, 2, . . . , n, in the ADRS encoder are the same as those in the standard encoder for the generator matrix G ⊗n 2 (The variable U (0) i are given by U i for 1 ⩽ i ⩽ N ). When an XOR operation associated with the j-th recursion, with operands U (n-j) i1 and U (n-j) i2 and the output U

, is split and modified under the ADRS scheme, the complexity of computing the likelihood or log-likelihood for Authorized licensed use limited to: University of Michigan Library. Downloaded on October 02,2023 at 21:04:14 UTC from IEEE Xplore. Restrictions apply.

(n-j) i1 and U

(n-j) i2 can be upper bounded by 2(2 1 + 2 2 + . . . + 2 j )c = 2(2 j+1 -2)c, for some constant c > 0.

2) Polar-ADRS Code Performance: We are now ready to show the performance of the polar-based code whose encoding structure is given by the ADRS scheme, referred to as the polar-ADRS code. First we show the existence of a lowcomplexity decoder.

Proposition 3: Let a constant λ > λ † ≜ (log 2 3) -1 ≈ 0.631 be given. The decoding complexity for a SC decoder for the polar-ADRS code is bounded by O(N log N ) for all sufficiently large n if the threshold for the DRS algorithm is w u.b. = 2 nλ .

Proof: The proof is provided in Appendix D.1. Second, it can be observed that the number of additional copies of channels due to the modification for an XOR operation at the j-th polarization recursion is 2 j . We find the total number of extra channel uses and the ratio γ of that to the number N = 2 n of channel uses for the code corresponding to G ⊗n 2 in the following. Assume that the column weight threshold of the DRS algorithm is given by w u.b. = 2 nλ .

Proposition 4: Let N (1+γ) be the number of channel uses of the encoder for the ADRS scheme based on DRS(G ⊗n 2 ) with w u.b. = 2 nλ . Then the term γ goes to 0 as n grows large, if we have λ > λ † .

Proof: The proof is provided in Appendix D.2. We are ready to show the existence of a sequence of capacity-achieving codes over general BMS channels with GMs where the column weights are bounded by a polynomial in the blocklength, and that the block error probability under a low complexity decoder vanishes as n grows large. Note that while this result is also applicable when the underlying channel is a BEC, the constraint on λ is stricter than that in Theorem 2, due to the difference in the encoding and decoding schemes.

Theorem 3: Let β < E(G 2 ) = 0.5, λ > λ † , and a BMS channel W with capacity C be given. There exists a sequence of codes with the following properties for all sufficiently large n: (1) The error probability under SC decoding is upper bounded by 2 -N β , where N = 2 n , (2) The Hamming weight of each column of the GM is upper bounded by N λ , (3) The rate approaches C as n grows large, and (4) The codes can be decoded by a SC decoding scheme with complexity O(N log N ).

Proof: We prove the four properties in order as follows. First, similar to the proof of Theorem 2, for i = 1, 2, . . . , N , the bit U i is frozen in the polar-ADRS code with rate R < C if and only if it is frozen in the polar code with kernel G 2 , blocklength N = 2 n , and the rate R. Hence, the probability of error of the polar-ADRS code can be bounded in the same way as its polar-code counterpart, since the bit-channels observed by the source bits U i , and the corresponding Bhattacharyya parameters, are identical to those when they are encoded with the standard polar code.

Second, when the ADRS scheme is based on DRS(G ⊗n 2 ) with w u.b. = 2 nλ , the generator matrix for the polar-ADRS code is a submatrix of DRS(G ⊗n 2 ). The column weights of the GM for the polar-ADRS code are thus upper bounded by w u.b. = 2 nλ = N λ . The third claim holds by using an argument similar to the one used in the proof of Theorem 2. This is because the term γ vanishes as n grows large according to Proposition 4. Finally, note that the fourth claim is equivalent to Proposition 3.

We evaluate the performance of the polar-ADRS codes with N = 1024, K = 512 and weight thresholds w u.b. ∈ {64, 128, 256, 512, 1024}, under the SC decoding scheme, over the BI-AWGN channels whose SNR (E b /N 0 ) ranges from 0.5 to 3 dB. The indices of frozen bits are designed using a Monte-Carlo scheme for the BI-AWGN channel with E b /N 0 = 2 dB. The auxiliary noise variables are generated with independent Bernoulli(0.5) distribution. The stopping criterion for each data point is ITERATION = 10 5 or BLOCK ERROR COUNT = 100, whichever is reached first. In Figure 8a, the block error probabilities are very close for codes with different weight thresholds over the range of simulated SNR. This is because the bit-channels observed by each information bit are exactly the same with or without the ADRS scheme, and that the block error probability of the codes are determined by the characteristics of the information bit channels.

Note that the use of the auxiliary noise variables are of theoretical reasons and is required for the proof of Theorem 3. In practice, we may freeze the auxiliary noise variables to avoid the channel uses for the transmission of them. In particular, when the auxiliary noise variables are frozen to fixed values known to both the encoder and decoder, the decoder can be considered as a genie-assisted decoder and its performance is better or equivalent to that of a decoder without the information of the auxiliary noise variables. We simulate the performance of the ADRS-polar code with N = 1024, K = 512 and weight thresholds w u.b. ∈ {64, 128, 256, 512, 1024}, where the values of the auxiliary noise variables are fixed to 0's, over the BI-AWGN channels with 0.5 ⩽ E b /N 0 ⩽ 3 (dB), and obtain Figure 8b. The error rates of codes with small thresholds are lower than those with large or no thresholds, a trend which is similar to that observed in Figure 5a.

This paper provided three constructions for capacityachieving linear codes, based on polar coding, where all the GM column weights are upper bounded sublinearly in the block length. The first construction is a sequence of polar codes based on general polarization kernels where the GM column weights are upper bounded by N s for any fixed s > 0, and allows the codes to be decoded by a SC decoder. In order to attain a better trade-off between the GM sparsity and the fall in error probability, we then proposed a columnsplitting algorithm for the GM, termed the DRS algorithm. With the DRS algorithm, we designed two encoding schemes which yield two polar-based codes, referred to as polar-DRS codes and polar-ADRS codes, that are decodable with lowcomplexity decoders for the BECs and general BMS channels, respectively. The polar-based codes preserve several fundamental properties of the standard polar code with G 2 kernel including the asymptotic error rate upper bound and decoding complexity. Further, the GM column weights of the polar-DRS and polar-ADRS codes are bounded from above by N λ , for λ ≈ 0.585 and λ ≈ 0.631, respectively, while the best bound for the standard polar codes scales linearly in N . The proposed constructions are also distinct from known constructions for codes with constraints on the GM sparsity by having analytical error probability upper bounds scaling as O(2 -N t ) under SC decoders, for any t < 0.5. A future direction is to design splitting algorithm and/or encoding schemes that preserve key properties of the polar codes based on general polarization kernels, and show that the corresponding polar-based codes exhibit better sparsity versus error rate trade-off.

Proof of Proposition 1: Since G l is a polarization kernel, there is at least one column in G l with weight at least 2.

To see this, note that G l being invertible implies that all rows and columns are nonzero vectors. If all the columns of G l have weights equal to 1, then all the rows must also have weights equal to 1, i.e., G l is a permutation matrix. Then D i = 1, ∀i, and E(G l ) = 0, which implies that G l can not be polarization kernel. The contradiction shows that at least one column in G l have a weight at least 2.

Let k ⩾ 1 denote the number of columns in G l with a weight at least 2. Let v be a randomly uniformly chosen column of G ⊗n l , and w(v) be the Hamming weight of v. For

where F i is the indicator variable that one of k non-unit-weight columns is used in the i-th Kronecker product of G l to form v.

In order to understand the DRS algorithm's effect on G = G ⊗n 2 , we first study how the order of two special Kronecker product operations affects the number of output vectors. We present the following Lemmas 3 and 4 toward the proof of Lemma 1.

Lemma 3: Let a column vector v and a column weight threshold w u.b. be given. Then the outputs of the DRS algorithm for

T contain the same number of vectors.

Proof: The input vectors can be denoted by:

We note that 2 w H (v) = w H (v LR ) = w H (v RL ), and prove the lemma in two cases:

1) 2w H (v) ⩽ w u.b. : In this case, the algorithm will not split either v LR or v RL . Both outputs contain exactly one vector. 2) 2w H (v) > w u.b. : Let n DRS (v) denote the size, or more precisely, the number of column vectors the DRS algorithm returns when it is applied to v. For v LR , the DRS algorithm observes x h = 0, hence the number of output vectors is the same as the size of DRS-SPLIT(w u.b. ,

For v RL , the number of vectors in the DRS algorithm output is the sum of the sizes of two sets

Proof for Lemma 2: We show the claim by proving the following: when we encode the source bits according to G ′ , the bit-channels observed by the source bits are BECs and that the erasure probabilities are less than or equal to those when G is used. We use proof by induction on n. For ease of notation, we use M ′ to denote DRS(M ) for a given matrix M in this proof.

For

, the latter must be 1 0 0 0 1 1 , corresponding to the encoding block diagram in Figure 9, where the solid black circles indicate a split of the XOR operation, i.e., the two operands of the original XOR operation are transmitted through two copies of channel W . The bitchannels observed by U 1 and U 2 , denoted by W ⊟ and W ⊞ , are BECs with erasure probability ϵ and ϵ 2 , respectively. Note that the Bhattacharyya parameters satisfy the following:

Suppose that, for a fixed w u.b. , the claim holds for all n ⩽ m for some integer m ⩾ 1. Let B m denote the encoding block corresponding to the generator matrix (G ⊗m 2 ) ′ , with inputs U 1 , . . . , U 2 m and encoded bits X 1 , . . . , X f (m) , where f (m) is the number of columns in (G ⊗m 2 ) ′ . Using the matrix notation, the relation between the input bits and encoded bits is:

For n = m + 1, the matrix (G ⊗m+1

) ′ is associated with (G ⊗m 2 ) ′ as follows:

2

Since (G ⊗m 2 ) ′ consists of the outputs of the DRS algorithm, the columns in the right half of the input matrix in equation (11) remain unaltered in the output. For the columns in the left half, they are of the form [v T , v T ] T for some column v of (G ⊗m 2 ) ′ . If 2w H (v) > w u.b. , the outputs of the DRS algorithm are [0 T , v T ] T and [v T , 0 T ] T because the vector v must have weight no larger than the threshold. If 2w H (v) ⩽ w u.b. , the algorithm leaves the vector unchanged. We may represent the encoding block B m+1 as in Figure 10, where it is assumed that the j-th column of the input matrix in (11) is halved by the DRS algorithm.

The erasure probabilities for the bit-channels observed by X i , denoted here as W (X i ), are less than or equal to 2ϵ -ϵ 2 for 1 ⩽ i ⩽ f (m), and are equal to ϵ 2 for f (m) + 1 ⩽ i ⩽ 2 f (m), respectively. Hence we may replace the XOR operations to the right of the X i 's as well as the transmission over W 's by BECs W (X 1 ), . . . , W (X f (m) ), W (X f (m)+1 ), . . . , W (X 2f (m) ), as in Figure 11.

One may observe that the erasure probability for the bit-channel observed by U i is a non-decreasing function of those of W (X 1 ), . . . , W (X f (m) ) for i ⩽ 2 m , and of W (X f (m)+1 ), . . . , W (X 2f (m) ) for i > 2 m . Thus, for i ⩽ 2 m , we have where the first inequality is due to Z(W (X j )) ⩽ 2ϵϵ 2 for 1 ⩽ j ⩽ f (m) and the second inequality follows from the hypothesis of the induction.

Similarly, for i > 2 m , we have

Hence the inequality holds when n = m + 1 as well.

1) Proof of Proposition 3: First note that each XOR operation at the j-th recursion can be associated with exactly one vector s = (s 1 , s 2 , . . . , s n ) ∈ {-, +} n and s j = -. For example, assume that the number of minus signs in s, denoted as m(s), is larger than n lub = log w u.b. = nλ, and let τ = τ (s) be the index such that m(s τ , s τ +1 , . . . , s n ) = n lub and s τ = -. Then for each index i in the set {k : 1 ⩽ k < τ, s k = -}, there is a bijection between the pair (s, i) and an XOR operation at the i-recursion which is split and modified in the ADRS scheme. Hence, the extra complexity of the SC decoder for the ADRS scheme, compared to that of the SC decoder for the code based on G ⊗n 2 , is given by for all sufficiently large n. It suffices to assume that λ < 3 4 . For λ ⩾ 3 4 , note that fewer XOR operations are split and modified, and that the resulting additional decoding complexity is not larger than when λ < 3 4 is used. Let f (α, λ) = (1 -α)h b ( λ 1-α ) + 2α. We find its maximum, for a given λ, by solving

which is true if and only if α = 1 -4 3 λ. And note that

1-α -1 1-α-λ < 0 for all α ∈ [0, 1 -λ]. The maximum of the function is then given by f (1- 4 3 λ, λ) = 2 -λ log 3. Using the union bound, the sum in ( 12) can be bounded by 4cn2 n(2-λ log 3) , and the ratio of the sum to N = 2 n , denoted by γ C , is bounded from above as γ C ⩽ 4cn2 n(1-λ log 3) . Since the exponent n(1 -λ log 3) goes to negative infinity as n grows when λ > λ † = 1/ log 3 ≈ 0.631, the ratio γ C vanishes exponentially in n when λ > λ † . The proposition follows by noting that the SC decoding complexity for the code based on G ⊗n

By the argument in the proof of Proposition 3, the sum in ( 13) can be upper bounded by n2 n(2-λ log 3) , and the ratio of the sum to N = 2 n , denoted by γ, is bounded from above as γ ⩽ n2 n(1-λ log 3) . Since the exponent n(1 -λ log 3) goes to negative infinity as n grows when λ > λ † = 1/ log 2 3 ≈ 0.631, the ratio γ vanishes exponentially in n when λ > λ † .