# Low Complexity List Decoding for Polar Codes with Multiple CRC Codes
## 3 Low Complexity SCL Decoding with Multiple CRC Codes
### Encoding and Decoding of the J-Tuple CRC Scheme  
Let us consider a precoding of a partitioned message block with multiple CRC codes, followed by polar encoding. Before the polar encoding, the message vector \(\mathbf{m}\) is partitioned into \(J\) subblocks \((\mathbf{m}_{1},\mathbf{m}_{2},...,\mathbf{m}_{J})\), and they are encoded serially with \(J\)-tuple CRC codes as shown in Figure 3. A CRC encoding is carried out recursively to the concatenation of a CRC encoded block and a message subblock. CRC code lengths are defined by \((p_{1},p_{2},...,p_{J})\), and the CRC parities are denoted by \((\mathbf{r}_{1},\mathbf{r}_{2},...,\mathbf{r}_{J})\). Through this nested encoding structure, undetected error by previous CRCs can be detected by following CRCs. The length of \(j\)-th message subblock is denoted by \(k_{j}\) and the total sum of \(k_{j}\) is \(K\). Likewise, the total sum of \(p_{j}\) is \(P\). The CRC encoded message is encoded by a polar code. This scheme is termed the \"\(J\)-tuple CRC scheme\". In this scheme, the lengths of \(J\) message subblocks can be determined by optimization of CRC positions that will be explained in Section 3.2. We introduce a decoding scheme for the \(J\)-tuple CRC scheme that is described in Algorithm 2. The temporary list size update is included in Algorithm 2 for a better presentation of the decoding procedure. The decoding is based on the conventional SCL decoding. However, the decoding is different in two aspects. First, \(J-1\) CRC operations are additionally conducted to discard incorrect paths (lines 12-13 in Algorithm 2). Thus, due to the added \(J-1\) CRCs, the temporary list size vector \(\mathbf{l}=(l_{1},l_{2},...,l_{N})\) varies depending on the decoding instance. Note, however, I of the SCRC scheme is invariant because decoding path validity is checked only once at the bottom of the decoding tree. If any of the CRCs fail in all decoding paths during the decoding, then the decoding is terminated and a block error is declared. This event is called \"early stopping\" that is rare at a high SNR but frequent at a low SNR. If the decoder finds paths with valid CRC, all such paths proceed to the next step. Note that we do not assume that best effort decoding is required. ```
0: Received vector, \(\mathcal{A}\), \(\mathcal{A}_{g}\), \(\mathbf{k}\), \(\mathbf{p}\)
0: Estimated codeword
1:\(l_{1}\gets 1\);
2:for\(i=1:N\)do
3:if\(i\in\mathcal{A}\)then
4:if\(i\in\mathcal{A}_{g}\)then
5: SCL decoding of \(u_{i}\) maintaining number of survival paths and \(l_{i+1}\gets l_{i}\);
6:else
7: SCL decoding of \(u_{i}\) with list size of \(\min(2l_{i},L)\) and \(l_{i+1}\leftarrow\min(2l_{i},L)\);
8:endif
9:else
10: Frozen bit decoding and \(l_{i+1}\gets l_{i}\);
11:endif
12:if\(i\) indicates the last parity bit of the \(j\)-th CRC then
13: Discard \(j\)th-CRC-invalid paths and update \(l_{i+1}\);
14:endif
15:endfor
16:return ML codeword that passes the \(J\)-th CRC;
```  
**Algorithm 2** The ID-SCL decoding for the \(J\)-tuple CRC scheme  
At each CRC operation, only valid paths--from a CRC perspective--survive so that the temporary list size is spontaneously reduced to one or just a few. The temporary list grows as the decoding proceeds, but if frozen bits follow consecutively, then the growth can progress slowly. This sporadic reduction of temporary list due to multiple CRC operations induces non-negligible complexity reduction. Second, we consider a simple complexity reduction criterion for list management that was first proposed in [24] for reduction of sorting complexity. When a highly reliable bit is processed, the list is forced not to grow (lines 4-5 in Algorithm 2) and the sorting operation is skipped. Let \(\mathcal{A}_{g}\) be the set of indices where the capacity of corresponding split channels exceeds a certain threshold. (\(\mathcal{A}_{g}\) may alternatively be defined in terms of bit error rate. (period position)) When \(u_{i}\) is processed, if \(i\in\mathcal{A}_{g}\), we run the SC decoding instead of SCL decoding.