SCL Successive Cancellation List

Successive Cancellation List (SCL) is an algorithm used in decoding polar codes, which is a class of error-correcting codes invented by Erdal Arikan in 2009. Polar codes are known for their excellent performance in terms of error correction and have been adopted in various communication standards, including 5G.

The SCL algorithm is a variant of the Successive Cancellation (SC) algorithm, which is the original decoding algorithm for polar codes. The SC algorithm is a recursive process that starts with the received codeword and performs a series of computations to estimate the transmitted information bits. However, the SC algorithm has a complexity that grows exponentially with the code length, which limits its practical use for long codes.

The SCL algorithm improves upon the SC algorithm by introducing a list-based decoding approach. Instead of making a single decision at each decoding step, the SCL algorithm maintains a list of partial decoding paths, with each path representing a potential estimate of the transmitted bits. This list is continuously updated and pruned as the decoding process progresses.

Here is a step-by-step explanation of the SCL algorithm:

1. Initialization: The SCL algorithm starts with an empty list of decoding paths. Initially, there is only one empty path in the list.
2. Path Extension: For each path in the list, the algorithm duplicates the path and extends it by making a decision for the next bit. This decision is based on the computed reliability metrics of the channel and the previously decoded bits. Each path in the list represents a potential decoding of the codeword up to the current position.
3. Metric Calculation: After extending each path, a metric is computed for each new path. This metric represents the likelihood of the path being the correct decoding. The metric is typically based on the reliability of the channel and the correctness of the previous decisions made along the path.
4. Path Pruning: The list of paths is then pruned to keep only the most likely paths based on their metrics. The pruning step helps reduce the complexity of the algorithm by discarding paths that are unlikely to be correct.
5. Check for Completion: The algorithm checks if the decoding process is complete by examining the decoded bits. If all bits have been decoded, the algorithm terminates, and the paths in the list are considered as potential decoding candidates.
6. Iteration: If the decoding is not complete, the algorithm repeats steps 2 to 5 until all bits are decoded.
7. Final Decision: Once the decoding is complete, the algorithm selects the path with the highest metric as the final decoded sequence. This path represents the most likely estimate of the transmitted bits.

The SCL algorithm achieves a trade-off between complexity and decoding performance. By maintaining a list of decoding paths, it explores multiple potential solutions and increases the chances of finding the correct decoding. The complexity of the algorithm depends on the number of paths in the list, which can be controlled to meet specific complexity requirements.

Overall, the SCL algorithm is an efficient and effective approach for decoding polar codes, providing high error correction capability with manageable complexity. It has contributed to the widespread adoption of polar codes in various communication systems.