Using List Decoding to Improve
the Finite-Length Performance of
Sparse Regression Codes

We use $\log$ to denote the logarithm to the base 2, and use $\ln$ to denote the natural logarithm. We use boldface font to denote (column) vectors or matrices, plain font for scalars, and subscripts for indexing entries of a vector or a matrix. We denote the complex conjugate transpose of the matrix $\bm{A}$ and the transpose of the vector $\bm{\beta}$ by $\bm{A}^{\ast}$ and $\bm{\beta}^{\intercal}$, respectively. We denote the indicator function of a statement $\mathcal{A}$ by $\mathbbm{1}\left(\mathcal{A}\right)$. We write $\mathcal{N}(0,\,\sigma^{2})$ to denote the (real) Gaussian distribution with zero mean and variance $\sigma^{2}$. We write $\mathcal{CN}(0,\,\sigma^{2})$ to denote the circularly-symmetric complex Gaussian distribution with zero mean and variance $\sigma^{2}$. For a positive integer $M$, we use $[M]$ to denote the set $\{1,\ldots,M\}$.

Encoding of a SPARC is defined in terms of a design matrix $\bm{A}$ of size $n\times ML$, where $n$ is the block length and where $M$ and $L$ are positive integers that are specified below in terms of $n$ and the rate $R$. In the original construction of SPARCs, the entries of $\bm{A}$ are assumed to be i.i.d. Gaussian $\sim\mathcal{N}(0,\,1/n)\,$. For this paper, the entries of $\bm{A}$ have been extended to be i.i.d. Gaussian $\sim\mathcal{CN}(0,\,1/n)\,$ for the complex AWGN channels.

Codewords are constructed as sparse linear combinations of the columns of $\bm{A}$. Specifically, a codeword $\bm{x}=\left(x_{1},\ldots,x_{n}\right)$ is of the form $\bm{A}\bm{\beta}$, where $\bm{\beta}=\left(\bm{\beta}_{1}^{\intercal},\ldots,\bm{\beta}_{L}^{\intercal}\right)^{\intercal}$ is an $ML\times 1$ vector and where each section $\bm{\beta}_{\ell}\triangleq\left(\beta_{(\ell-1)\cdot M+1},\ldots,\beta_{\ell\cdot M}\right)^{\intercal},\ell=1,\ldots,L$, has the property that only one of its components is non-zero. The non-zero value¹¹1In this paper, we mainly focus on techniques for improving the performance of SPARCs, so we only encode information by the location of non-zero entries in $\bm{\beta}$ with values fixed a priori for simplicity. However, the values (specifically the phases) of the non-zero entries can also be different in the case of complex channels, and the details w.r.t. these so-called modulated SPARCs can be found in [15]. of section $\bm{\beta}_{\ell}$ is set to $\sqrt{nP_{\ell}}$, where $P_{1},\ldots,P_{L}$ are pre-specified positive constants that satisfy $\sum\limits_{\ell=1}^{L}P_{\ell}=P$. This guarantees that $\frac{1}{n}\sum\limits_{i=1}^{n}\absolutevalue{x_{i}}^{2}\leq P$ with high probability. (See Appendix B in the arXiv version [16] of [2] for details.)

Both the matrix $\bm{A}$ and the power allocation $\{P_{1},\ldots,P_{L}\}$ are known to the sender and the receiver before transmission. The choice of power allocation plays a crucial role in determining the finite-length performance of SPARCs, which will be illustrated in the following. Without loss of generality, we can choose the power allocation to be non-increasing since messages are independent across sections and the AWGN channels we consider here are memoryless.

Because the design matrix $\bm{A}$ can be regarded as $L$ blocks with $M$ columns each, and because we pick one column from each block of the design matrix to comprise one codeword, the total number of codewords for a SPARC will be $M^{L}$. With the block length being $n$, the rate $R$ will be $\frac{\log(M^{L})}{n}$, i.e., $\frac{L\cdot\log M}{n}$. In actual implementations, the input bitstream is split into chunks of $\log M$ bits, and each chunk of $\log M$ bits is first bijectively mapped to the position of the non-zero element for the corresponding section. Based on $L$ consecutive chunks, the sender constructs the message vector $\bm{\beta}$ by assigning the pre-specified positive constants to the corresponding positions for each section (see “position mapping” in Fig. 1). Eventually, the sender transmits the codeword $\bm{x}\triangleq\bm{A}\bm{\beta}$ (see “SPARC encoding” in Fig. 1).

For decoding SPARCs over complex AWGN channels, we derive the following AMP decoder, which is similar to the one used for the real case in [10].

Namely, given the channel output $\bm{y}\triangleq\bm{A}\bm{\beta}+\bm{w}$, where $\bm{w}=\left(w_{i}\right)_{i\in[n]}$ and $w_{i}$ are i.i.d. $\mathcal{CN}(0,\,\sigma^{2})$ for all $i\in[n]$, the AMP decoder will generate successive estimates of the message vector, denoted by $\{\bm{\beta}^{t}\},\bm{\beta}^{t}\in\mathbb{R}^{LM}$, for $t=0,1,2,\ldots$.

Initialize $\bm{\beta}^{0}\coloneqq\bm{0}$, then compute

where the constants $\{\tau_{t}\}$ and the denoiser functions $\eta_{i}^{t}\left(\cdot\right)$ are defined as follows. First, define

where

where $\{U_{j}^{\ell}\}$ are i.i.d. $\mathcal{CN}(0,\,1)$, for all $j\in[M]$ and all $\ell\in[L]$. Note that Equations (3) and (4) together are called the state evolution. Finally, for all $\ell\in[L]$ and all $i\in\mathrm{sec}_{\ell}\triangleq\{(\ell-1)\cdot M+1,\ldots,\ell\cdot M\}$, define

The above AMP decoder and its state evolution for SPARCs over complex AWGN channels is the same as those in the real case [10] up to a factor 2 appearing in (5) and (4) and a few minor modifications, which is because we can regard transmission of SPARCs with rate $R$ over a complex AWGN channel with a given SNR as two independent (orthogonal) transmissions of SPARCs with rate $\frac{R}{2}$ over real AWGN channels with the same SNR.

The denoiser functions (5) for this AMP decoder can be derived from the minimum mean squared error (MMSE) estimator of $\beta_{i}$, for $i\in[ML]$, which is Bayes-optimal under the distributional assumption on $\bm{s}=\bm{\beta}+\tau\bm{u}$ with $\bm{u}$ having i.i.d. $\mathcal{CN}(0,\,1)$ entries and independent with $\bm{\beta}$. I.e., $\eta_{i}^{t}\left(\bm{s}\right)\triangleq\mathbb{E}\left[\beta_{i}|\bm{s}=\bm{\beta}+\tau\bm{u}\right]$, where the expectation is over $\bm{\beta}$ and $\bm{u}$ given $\bm{s}$.

From (3), we see that the effective noise variance $\tau_{t}^{2}$ is the sum of two terms, where the first term is the channel noise variance $\sigma^{2}$, and the other term $P\cdot\left(1-x\left(\tau_{t-1}\right)\right)$ can be regarded as the interference from the undecoded sections in $\bm{\beta}^{t}$. In other words, $x\left(\tau_{t-1}\right)$ is the expected fraction of sections that are correctly decoded at the end of iteration $t$. In the following, we adapt Lemma 1 in [12], which gives upper and lower bounds on $x\left(\tau\right)$ for the real AWGN case, to our complex AWGN case. This adaptation requires the redefinition of $\nu_{\ell}$ from [12, Lemma 1].

In the limit $M\to\infty$, we can use the following approximation for $x(\tau)$:

This approximation for $x(\tau)$ gives us a quick way to check whether a given power allocation scheme leads to reliable decoding in the large-system limit. Based on this approximation, we can design an iterative power allocation algorithm as follows. Namely, the $L$ sections of the SPARC are divided into $B$ blocks of $L/B$ sections each, and the same power is allocated to every section within a block. We sequentially allocate the power to all blocks in the following way: for each section within the first block, we allocate the minimum power needed so that all sections within this block can be decoded in the first iteration when $\tau_{0}^{2}\coloneqq\sigma^{2}+P$. Using the approximation (8), we assign the power

to each section within the first block, and then we get $\tau_{1}^{2}\coloneqq\sigma^{2}+(P-\frac{L}{B}\cdot P_{1})$ due to (3). We sequentially allocate the power derived in the same way as (9) to the remaining blocks. For $R\leq C$,²²2Here, $C\triangleq\log\left(1+\frac{P}{\sigma^{2}}\right)$ is the channel capacity. we can readily derive the result that $\sum\limits_{\ell=1}^{L}P_{\ell}$ will be less than the average power $P$. In order to fully allocate the average power $P$, we can slightly modify the algorithm in the following way: for every block, we first compare the average of the remaining available power with the minimum required power computed similarly to (9). If the former one is larger than the latter one, we allocate the remaining power to the remaining sections evenly and terminate the algorithm; otherwise, we assign the minimum required power to each section within the current block and the algorithm continues. The above iterative power allocation scheme for the complex case is straightforwardly extended from the one for the real case proposed in [12].

When we consider the finite-length performance of SPARCs, it has been observed that the above iterative power allocation algorithm works better than the exponentially-decaying power allocation which was proved in [10] to be asymptotically capacity-achieving in the large-system limit. Since the above iterative scheme is derived based on the asymptotic approximation for $x(\tau)$ (see Eq. (8)), the power allocated by using the above iterative scheme may be slightly different from the non-asymptotic bounds on $x(\tau)$ in Lemma 1 at finite lengths. In order to compensate their difference, we can introduce a parameter $R_{\mathrm{PA}}$ that serves as the code rate $R$ in (9); by carefully tuning this parameter to be slightly different from the code rate, we can further improve the finite-length performance. The details of this iterative power allocation scheme for the real case can be found in [12] and all the reasoning can be straightforwardly modified to the complex AWGN channel scenario considered here.

The effective noise variance $\tau_{t}^{2}$ can be estimated via (3), (4) in advance for iteration $t$ up to the maximum iteration $T$,³³3The number of iterations can also be determined in advance by running the state evolution until it converges to some fixed point (within a specified tolerance). but this procedure is extremely time-consuming since we need to estimate $L$ expectations over $M$ random variables via Monte-Carlo simulation for each iteration $t$. Rush et al. in [17] have already shown that $\tau_{t}^{2}$ is concentrated around $\frac{\norm{\bm{z}^{t}}^{2}}{n}$, i.e., we can estimate

We call this an online estimate of $\tau_{t}^{2}$, and Greig et al. [12] have already empirically shown that this online estimate provides a good estimate of the noise variance in each iteration as it accurately reflects how the decoding is progressing in that simulation run.

The key part of our proposed concatenated coding scheme is using CRC codes as outer codes. There are two ways to employ CRC codes: (a) an “inter-section-based approach” that encodes the original message to generate extra check sections bit by bit when we focus on the bit error rate (BER) performance, (b) an “intra-section-based approach” that encodes them section by section when we focus on the section error rate (SecER) performance. We will only discuss the former way since the latter way is essentially the same.⁸⁸8The only difference between these two SPARCs with CRC codes is the CRC encoding part, and there is no need to discuss the section-by-section encoding separately. The block diagram in Fig. 1 gives a high-level view of the proposed concatenated coding scheme with SPARCs as inner codes and CRC codes as outer codes, where CRC codes with suitable parameters were taken from [20]. In the following, we discuss the main blocks of Fig. 1.

(CRC Encoding) We first encode the original message $\bm{u}$ with size $L\cdot\log{M}$ bit by bit in the following way:

1. 1.

   Partition the original message $\bm{u}$ into $L$ sections, denoted by $\{\bm{u}_{1},\ldots,\bm{u}_{L}\}$. These $L$ sections are organized into $\frac{L}{K}\left(\triangleq N_{\mathrm{g}}\right)$ groups of $K$ sections each.⁹⁹9For simplicity, we assume that $L$ is divisible by $K$. For the case that $L$ is not divisible by $K$, we can take the last mod$\left(L,K\right)$ sections as one group, and encode this group individually. More precisely, these $N_{\mathrm{g}}$ groups will be $\{\bm{u}_{1},\bm{u}_{N_{\mathrm{g}}+1},\ldots,\bm{u}_{L-N_{\mathrm{g}}+1}\}$, $\ldots$, $\{\bm{u}_{j},\bm{u}_{N_{\mathrm{g}}+j},\ldots,\bm{u}_{L-N_{\mathrm{g}}+j}\}$, $\ldots$, $\{\bm{u}_{N_{\mathrm{g}}},\bm{u}_{2N_{\mathrm{g}}},\ldots,\bm{u}_{L}\}$.

2. 2.

   Use the CRC code to systematically encode each group of $K$ sections bit by bit as shown in Fig. 3 to generate $r$ extra sections that are appended at the end of the original message; for instance, the group $\{\bm{u}_{j},\bm{u}_{N_{\mathrm{g}}+j},\ldots,\bm{u}_{L-N_{\mathrm{g}}+j}\}$ will generate extra sections $\{\widetilde{\bm{u}}_{L+j},\widetilde{\bm{u}}_{L+N_{\mathrm{g}}+j},\ldots,\widetilde{\bm{u}}_{L+(r-1)\cdot N_{\mathrm{g}}+j}\}$.

This CRC encoding procedure yields $L+N_{\mathrm{g}}\cdot r\ \bigl{(}\triangleq\widetilde{L}\bigr{)}$ sections. One can readily see that $K$ is the number of information bits and $r$ is the number of check bits for each codeword of CRC encoding, and $N_{\mathrm{g}}\cdot\log{M}\bigl{(}\triangleq N_{\mathrm{C}}\bigr{)}$ is the total number of codewords; the resulting codewords are denoted by $\{\mathrm{C}_{i}|i\in[N_{\mathrm{C}}]\}$. The number of additional parity bits $N_{\mathrm{C}}\cdot r$ are the cost for error detection, which leads to a trade-off between error detection capability and rate loss.

(Position Mapping and SPARC Encoding) We first map the encoded message to the corresponding $\widetilde{\bm{\beta}}$ and then perform SPARC encoding by multiplying the design matrix with $\widetilde{\bm{\beta}}$ to get the corresponding codeword $\bm{x}$, which is transmitted over the complex AWGN channel.

(AMP Decoding and List Decoding) At the receiver side, we can decode the received message in the following way:

1. 1.

   Perform $T$ iterations of AMP decoding; the resulting estimate of $\widetilde{\bm{\beta}}$ is called $\widetilde{\bm{\beta}}^{(T)}$.

2. 2.

   For each section $\ell\in\bigl{[}\widetilde{L}\bigr{]}$, normalizing $\widetilde{\bm{\beta}}^{(T)}_{\ell}$ gives the a posterior distribution estimate of the location of the non-zero entry of $\widetilde{\bm{\beta}}_{\ell}$, denoted by $\hat{\tilde{\bm{\beta}}}^{(T)}_{\ell}$.

3. 3.

   For each section $\ell\in\bigl{[}\widetilde{L}\bigr{]}$, convert the posterior distribution estimate $\hat{\tilde{\bm{\beta}}}^{(T)}_{\ell}$ into $\log_{2}{M}$ bit-wise posterior distribution estimates according to Algorithm 1, which is essentially the same as “Algorithm 2” in [12].

4. 4.

   For each codeword $\mathrm{C}_{i}$, we establish a binary tree of depth $K+r$, where, starting at the root, at each layer, we keep at most $S$ branches, which are the most likely ones.

5. 5.

   For each codeword $\mathrm{C}_{i}$, once we have established such a binary tree, list decoding will give us $S$ ordered candidates corresponding to the remaining $S$ paths from the root to the leaves. For each path (i.e., a candidate with $K+r$ bits) from the most likely one to the least likely one, we detect whether this candidate is valid or not via CRC detection and take the candidate as $\hat{\mathrm{C}}_{i}$ once the CRC condition is satisfied.¹⁰¹⁰10Although we have already found the most likely valid codeword, it might be an “undetected error” in the sense that the codeword is different from what we transmitted. This is the worst case since we cannot even realize that we made an error. If no candidate satisfies the CRC condition after checking all candidates, it means that there is a “detected error” and we take the first candidate as $\hat{\mathrm{C}}_{i}$. Although at least one bit is decoded incorrectly, this first candidate can be potentially better than other candidates.

Besides the above regular list decoding assisted with CRC codes, we can try to further improve the performance by running AMP and list decoding again (denoted by “AMP again”) for parts of the message, especially when most of the errors stemming from list decoding are detected errors. More specifically, we can apply the following procedure:

1. 1.

   Run AMP decoding as before, except that at each iteration, fix the “correctly decoded”¹¹¹¹11It may contain wrongly decoded sections which were regarded as correct ones; we call these errors “undetected errors”. (See also Footnote 10.) parts of the message and only estimate the other sections. When the maximum number of iteration $T$ is reached or some halting condition is satisfied, the algorithm outputs $\widetilde{\bm{\beta}}^{\ast}$.

2. 2.

   Take only the wrongly decoded sections of $\widetilde{\bm{\beta}}^{\ast}$, denoted by $\widetilde{\bm{\beta}}^{\ast}_{\mathrm{WD}}$, and apply the above list decoding procedure to $\widetilde{\bm{\beta}}^{\ast}_{\mathrm{WD}}$, which gives the decoded message.

In this subsection, we evaluate the BER performance of SPARCs concatenated with CRC codes and SPARCs without CRC codes over the complex AWGN channel for different overall rates. For SPARCs concatenated with CRC codes, we consider the finite-length performance of list decoding with different list sizes as well. For complex AWGN channels, the SNR per information bit, i.e., $\mathrm{SNR}_{\mathrm{b}}$, is defined as $\frac{P}{\sigma^{2}}\cdot\frac{1}{R}$.

The setup for the simulation results in Fig. 4 is as follows. We consider SPARCs with overall rate $R=0.8$ bits/(channel use)/dimension, in which case $R_{\mathrm{PA}}=0$ and the iterative power allocation scheme gives a flat allocation (see Section II-C for details). Moreover,

• •

  we choose the number of information sections $L$ to be 1000,

• •

  we choose the size of each section $M$ to be 512,

• •

  we choose the number of information bits $K$ to be 100,

• •

  we use the 8-bit CRC code whose generator polynomial is 0x97$=x^{8}+x^{5}+x^{3}+x^{2}+x+1$ (see, e.g., [20]).

The difference between Fig. 4(a) and Fig. 4(b) is as follows. Namely, Fig. 4(a) considers the list decoder with the list size $S=64$, whereas Fig. 4(b) considers the performance of SPARCs concatenated with CRC codes under list decoding with different list sizes. The plot in Fig. 4(a) shows that SPARCs concatenated with CRC codes can provide a steep waterfall-like behavior¹²¹²12Note that the dashed vertical line in Fig. 4(a) indicates that no error was observed in $10^{3}$ simulation runs. above a threshold of $\mathrm{SNR}_{\mathrm{b}}=3.5$ dB. Besides this, the proposed concatenated coding scheme can also provide a boost compared with the original SPARCs below this threshold. This is different from SPARCs with LDPC codes as outer codes that were considered in [12], since the performance of that concatenated coding scheme is dramatically worse than the original SPARCs below the threshold. Note that in the case of concatenation with LDPC codes [12], the “AMP again” procedure improves the performance significantly. However, in our case, running “AMP decoder again” usually yields rather limited improvements. We can analyze this as follows.

• •

  When $\mathrm{SNR}_{\mathrm{b}}\lesssim 2\text{dB}$, the AMP decoder can barely decode a few sections and the number of errors are beyond the CRC code’s error detection capability; therefore, the output of list decoding may contain several “undetected errors”, which misleads further decoding in the “AMP again” part.

• •

  When $2\text{dB}\lesssim\mathrm{SNR}_{\mathrm{b}}\lesssim 3.5\text{dB}$, the outer error-detection code improves the performance and results in very few “undetected errors” since parts of the received message with few errors are within the CRC code’s error detection capability. Because there are very few “undetected errors”, we can further improve the performance by runing the “AMP again” procedure.

• •

  When $\mathrm{SNR}_{\mathrm{b}}\gtrsim 3.5$dB, almost all the errors are corrected when performing list decoding and there are very few errors remaining; therefore, usually there is no noticeable improvement obtained by running “AMP again”.

Fig. 4(b) illustrates how the list size affects the performance of SPARCs with CRC codes. From this plot we deduce that $S=64$ is the best choice for the considered setup. This can be explained as follows. The list size cannot be too small, otherwise we cannot find a candidate satisfying the CRC condition, and the resulting estimate will be the same as the estimate deduced from the original AMP decoder. However, the list size also cannot be too large since it may result in a few “undetected errors”, which will mislead the “AMP again” part.

The setup of the simulation results in Fig. 5 is the same as for Fig. 4, except that we consider SPARCs with overall rate $R=1.5$ bits/(channel use)/dimension and $R_{\mathrm{PA}}=3\times 1.1=3.3$ $(\approx 3)$ in this case. Unsurprisingly, the plot in Fig. 5 exhibits the same waterfall-like behavior¹³¹³13Note that the dashed vertical line in Fig. 5 indicates that no error was observed in $10^{3}$ simulation runs. as in Fig. 4(a). Based on the non-increasing power allocation assumption, we know that all errors appear in the last few sections and may even be consecutive. Such consecutive errors can typically be dealt with successfully thanks to the interleaving feature of the grouping scheme proposed in Section IV-A. Whereas the original SPARC is very sensitive with respect to the choice of $R_{\mathrm{PA}}$, our coding scheme turns out to be relatively robust to the choice of $R_{\mathrm{PA}}$ due to our choice of outer error-detection code and decoding scheme. Therefore, we tackled the sensitivity issue of the iterative power allocation scheme to a great extent thanks to our concatenated coding scheme.

The simulation results regarding the prediction for the SecER¹⁴¹⁴14The BER performance should be roughly half of the SecER performance since the position of the non-zero value is chosen uniformly for each section. via state evolution in [12] shows that the performance gets better when the section size $M$ gets larger. In the following, we investigate how the section size $M$ affect the BER performance of our concatenated coding scheme. The setup of the simulation results in Fig. 6 are the same as for the previous ones except that we consider how the section size $M$ will affect the BER performance of our concatenated coding scheme. Specifically, Fig. 6(a) and Fig. 6(b) illustrate the BER performance comparison of SPARCs concatenated with CRC codes using list decoding when the overall rate is $R=0.8$ bits/(channel use)/dimension and when the overall rate is $R=1.5$ bits/(channel use)/dimension, respectively. When the overall rate is $R=0.8$ bits/(channel use)/dimension, Fig. 6(a) shows that the BER performance becomes better when the section size $M$ gets larger; especially, when the section size $M$ is larger than or equal to $1024$, these SPARCs concatenated with CRC codes have a better threshold. This result coincides with the prediction. However, when the overall rate is $R=1.5$ bits/(channel use)/dimension, Fig. 6(b) shows that there is a “best” section size, i.e., $M^{*}=512$; in other words, the BER performance of our concatenated coding scheme with the section size $M^{*}=512$ is the best for section sizes from $M=2^{6}$ to $M=2^{11}$. This result can be explained as follows; in the context of high-rate SPARCs (say, the overall rate $R>1$), as $M$ goes beyond the “best” $M^{*}$, the further benefit from the extra increase in $M$ is weaker than the loss of concentration on the prediction via state evolution. The effect of the section size $M$ on concentration is still theoretically unclear and the prediction of the “best” section size $M^{*}$ even for the original SPARC is still an open problem.

After discussing the simulation results, let us discuss the encoding and decoding complexities regarding our concatenated coding scheme in the following. The encoding complexity is mainly dominated by the inner encoding, i.e., one vector-matrix multiplication, which can be done efficiently via one FFT. The complexity of one FFT is $O(LM\log(LM))$, thus the encoding complexity is $O(LM\log(LM))$. The decoding complexity is mainly dominated by AMP decoding and list decoding. Firstly, the complexity of AMP decoding is dominated by two FFTs, so its complexity is $O(LM\log(LM))$. Secondly, the complexity of list decoding is $O(\frac{\widetilde{L}}{K}\log(M)\left(2S\cdot(K+r)+S\right))$, i.e., $O(SL\log(M))$. Therefore, the decoding complexity is $O(LM\log(LM)+SL\log(M))$. Once the CRC code for our concatenated coding scheme is chosen, the number of redundant bits $r$ will be constant and it will stay constant as $L$ grows large. The number of information bits $K$ can be varied within some range (see, e.g., [20]). The choice of $K$ will not only affect the rate loss of the overall code, but also affect the error detection capability of the CRC code. Thus, the choice of $K$ leads to a trade-off between error detection capability and rate loss. Furthermore, the choice of CRC codes, i.e., the parameters $r$ and $K$, will not affect the decoding complexity since the decoding complexity is $O(LM\log(LM)+SL\log(M))$.

Besides AMP decoders for the original SPARCs having been proven to be asymptotically capacity achieving with a suitably chosen power allocation, “spatial coupling” is the other technique with which the corresponding AMP decoder has been proved to be asymptotically capacity achieving as well. The “spatial coupling” technique was first introduced in the context of LDPC codes. In particular, [21, 22] showed that the “coupling” of several copies of individual codes increases the algorithmic threshold (belief propagation (BP) threshold) of this new ensemble to the information-theoretic threshold (maximum a posteriori (MAP) threshold) of the underlying ensemble. This phenomenon is called “threshold saturation” and it has also been observed in the compressed sensing setting [23, 24]. In the context of SPARCs, spatial coupling was first introduced by Barbier et al.in [25] and then Barbier et al. [9] used the replica analysis to show that SC-SPARCs with AMP decoders are capacity achieving over AWGN channels. The fully rigorous and complete proof was first given by Rush et al. [26]. SC-SPARCs can be suitably modified to the complex AWGN channel, and Hsieh et al. [15] proposed modulated (spatially coupled) SPARCs in which information is encoded by both the location and the value of the non-zero entries in $\bm{\beta}$ in the case of complex AWGN channels. Since we mainly focus on techniques for improving the finite-length performance, SC-SPARCs for complex AWGN channels here will only encode information via the localation of the non-zero entries in $\bm{\beta}$. In other words, we will consider unmodulated SC-SPARCs over complex AWGN channels as in [15]. The details regarding AMP decoders for SC-SPARCs over complex AWGN channels can be found in [15] and will be omitted here.

The previous results mainly focus on the asymptotic characterization of the error performance of SC-SPARCs. There are very few papers (e.g., [27]) discussing how to further improve the finite-length performance of SC-SPARCs. In this subsection, we will show that list decoding can improve the finite-length performance of SC-SPARCs for the low-rate region¹⁵¹⁵15When the overall rate of our concatenated coding scheme is less than 1 bit/(channel use)/dimension, we say it is in the low-rate region; otherwise, we say it is in the high-rate region. via simulation results. A detailed introduction of SC-SPARCs can be found in [28].

Before we get into the list decoding part, we need first introduce some extra parameters used in the design matrix of SC-SPARCs via the following definition (see [28] for details).

For example, for $w=3$, the above $\left(w,\Lambda\right)$ base matrix $W$ will be in the shape

Replacing each non-zero entry with an $M_{R}\times M_{C}$ matrix with entries i.i.d. sampled from $\mathcal{CN}(0,\,W_{r,c}/L)$ and each zero entry with an $M_{R}\times M_{C}$ all-zero matrix, we can finally get the design matrix $A$ with the same structure as the above base matrix. Note that $n=M_{R}L_{R}$ and $ML=M_{C}L_{C}$.

The procedure for encoding and decoding SC-SPARCs with CRC codes is very similar to the one discussed in Section IV-A, so it is omitted here. We evaluate the BER performance and the SecER performance of SC-SPARCs concatenated with CRC codes and without CRC codes over the complex AWGN channels for different overall rates.

In order to make the performance of SC-SPARCs and the performance of the original SPARCs discussed previously comparable, we will consider the settings as close as possible to the ones in Section IV-B.¹⁶¹⁶16Due to the structure of design matrices of SC-SPARCs, the overall rate of the concatenated code cannot be chosen arbirarily.

The setup for the simulation results in Fig. 7 is as follows. We consider SC-SPARCs with overall rate $R=0.8$ bits/(channel use)/dimension. Moreover,

• •

  we choose the number of information sections $L$ to be 1000;

• •

  we choose the size of each section $M$ to be 512;

• •

  we choose the number of information bits $K$ to be 100;

• •

  we use the 8-bit CRC code whose generator polynomial is 0x97$=x^{8}+x^{5}+x^{3}+x^{2}+x+1$ (see, e.g., [20]);

• •

  for the base matrix, we choose $\Lambda=40$, $w=6$; therefore, $L_{C}=\Lambda=40$, $L_{R}=\Lambda+w-1=45$;

• •

  we choose the list size for list decoding to be $S=64$;

The plot in Fig. 7(a) shows that SC-SPARCs concatenated with CRC codes can also provide a steep waterfall-like behavior above a threshold of $\mathrm{SNR}_{\mathrm{b}}=4$ dB, which is larger than the result in the original SPARCs case. Furthermore, we observe that the BER performance of SC-SPARCs when “AMP again” is employed without further list decoding is worse than the BER performance when “AMP again” is not employed. This unusual result can be explained as follows, based on the SecER performance of SC-SPARCs.

• •

  From Fig. 7(b), we see that the SecER performance of SC-SPARC when “AMP again” is employed without further list decoding is better than the SecER performance when “AMP again” is not employed. This explains that the AMP decoder for the remaining part can further decode a few sections of original messages.

• •

  However, in terms of BER performance, the amount of extra bits successfully decoded by the AMP decoder for the remaining part might not be larger than the amount of corrected bits within the wrongly decoded sections during the list decoding stage. This is because list decoding separately decodes the original messages based on the way we partition the original messages during the CRC encoding procedure and this decoding results in some mostly corrected sections which have corrected most of bits contained in each section’s information. (E.g., when $M=512$, each section contains 9 bits of information.) Because the AMP decoder decodes the original messages in the section-wise level, the AMP decoder cannot guarantee that it decodes more bits successfully although it successfully decodes some sections within these remaining sections.

The setup of the simulation results in Fig. 8 is the same as for Fig. 7 except that we consider SC-SPARCs with overall rate $R=1.493$ bits/(channel use)/dimension. Surprisingly, the performance of this concatenated coding scheme is much worse than the performance of SC-SPARCs without CRC codes. Therefore, we conclude that under the current setup, list decoding for SC-SPARCs with CRC codes in the high-rate region might not significantly improve the finite-length performance. It is an interesting direction for future work to take the spatial coupling structure into account when we encode the original messages with CRC codes to further improve the finite-length performance of SC-SPARCs concatenated with CRC codes especially for the high-rate region. Another observation from Fig. 8(b) is that the SecER performance of SC-SPARCs with CRC codes is better than the SecER performance of SC-SPARCs without CRC codes when $\mathrm{SNR}_{\mathrm{b}}$ is below some value (in this case, $\mathrm{SNR}_{\mathrm{b}}<5.5$ dB), and this is because our implementation scheme puts all the CRC redundant sections in the middle of the encoded messages. Due to the wave-like decoding behavior of SC-SPARCs, those CRC redundant sections are more likely to be wrongly decoded and relatively more information sections will be decoded successfully. This finally results in a relatively lower SecER since SecER is the number of section errors within information sections divided by the number of information sections.