Ensemble Decoding of Polar Codes

This repository contains the implementation associated with the Bachelor's thesis Ensemble Decoding of Polar Codes and the corresponding paper Subcode Ensemble Decoding of Polar Codes, submitted to ISTC 2025. The paper is available on arXiv: arxiv.org/abs/2504.17511.

Throughout this README, we use the notation introduced in the paper.

---

Running the Code

The file main.cpp includes several entry points that define the code's functionality. To switch between them, manually comment/uncomment the corresponding function calls in main.cpp.

Available Functions

• simul()
  Simulates a given $\mathcal{C}_T(N, k)$ using parameters specified in simulate.cpp.

• generate_undecodable(u)
  Generates a file containing $u$ undecodable SNR patterns (URPs), with parameters set in setmatrix.cpp.

• generate_set_matrix()
  Builds a set matrix from previously generated URPs. Parameters are located in setmatrix.cpp.

• stat_analysis()
  Performs a statistical analysis of pretransformation parameters, configured via setmatrix.cpp.

Note:
Parameter settings differ between setmatrix.cpp and simulate.cpp. Ensure you manually synchronize them to reproduce specific experiments based on set matrices.

---

⚙️ Parameter Configuration

The parameter structure is shared between simulate.cpp and setmatrix.cpp. Below we describe the most relevant settings.

---

🔍 Debug Mode

Debug mode enables detailed intermediate output and uses an artificially high SNR for quick debugging. Additional behaviors may be toggled using this flag.

static bool DEBUG = false;

---

📦 Polar Code Parameters

Block Length and Data Bits

Defines the block length $N$ and the number of data bits $k$.

Note:
k refers to the number of actual transmitted data bits. This may differ from the number of information bits in the polar code due to applied pretransformations.

static uint32_t N = 128;
static uint32_t k = 64;

SCL Decoder List Size

Defines the list size $L$ of the Successive Cancellation List (SCL) decoder.
A list size of 1 corresponds to standard SC decoding.

static uint32_t list_size = 8;

---

Simulation Parameters

SNR Range

Simulations are conducted over a range of SNR values defined by the interval [SNR_start, SNR_end) with increments of SNR_step.

Important:
The interval is open on the right — i.e., if SNR_start + i * SNR_step == SNR_end, the final value is excluded.

static float SNR_start = 0.0;
static float SNR_end = 3.0;
static float SNR_step = 0.5;

Error and Symbol Limits

The simulation stops at MAX_ERRORS for each SNR value, unless the number of simulated symbols exceeds MAX_SYMS.

static uint32_t MAX_ERRORS = 100;
static uint32_t MAX_SYMS = 300000;

---

🧵 Multithreading Support

All kinds of simulations and analysis support multithreading.

static uint32_t THREADS = 1;             // Number of threads to use
static uint32_t SIMS_PER_THREAD = 100;   // Number of simulations per thread before error counts are consolidated

Note:
SIMS_PER_THREAD determines how often threads synchronize and count total errors. Hence, actual error or symbol counts may slightly exceed the defined limits.

Tip:
Use std::thread::hardware_concurrency() to query your system’s maximum thread capacity. It’s recommended to leave one core free (std::thread::hardware_concurrency() - 1) to ensure smooth operation.

---

📤 Output Settings

These options control additional outputs and comparisons.

static bool print_list_error_rate = true;
static bool direct_comparison = true;
static bool compare_auto_to_ed = true;
static int UPDATE_TIME = 100; // Update interval in ms

• print_list_error_rate: Outputs the list error rate — the probability that the correct codeword is not present in the decoding list.
  The list size is $M \cdot L \cdot \mu$, where:

  • $M$ = number of ScED paths
  • $L$ = list size
  • $\mu$ = number of AED paths

• direct_comparison: Enables direct comparison against standard SCL decoding.

  Requires the "unmodified" path to be present in the ScED/AED ensemble.

• compare_auto_to_ed: If enabled and use_automorphisms = true, the system compares AED with standalone ScED rather than with SCL.

---

ScED and AED Parameters

Pretransformation (PT) Definition

A pretransformation (PT) is specified as:

PT{origin_bit_indices, target_bit_index, offset, pt_type}

• pt_type:
  • GENIE_PT: Type A (genie-aided)
  • NORMAL_PT: Type B (standard)
  • ENSEMBLE_PT: Type C (ensemble)

The function pretransforms_from_polynomials(...) can automatically generate PTs from CRC polynomials, especially for Type A PTs:

pretransforms_from_polynomials({Polynomial{0x03, 6}}, N, k, pt_type);

Where:

• 0x03 is the CRC polynomial (hex)
• 6 is the degree (defines how many PTs are generated)

Modifying type A and B pretransformations

static std::vector<std::vector<PT>> ensemble_pretransformations; // Do not modify directly
static std::vector<PT> standard_pretransformations = {}; // Type A pretransformations
static std::vector<PT> genie_pretransformations = {}; // Type B pretransformations

Note:
Do not modify the type C pretransformations right here! See below for proper setup.

---

📉 FER Simulations in simulate.cpp

The following settings are relevant only for simulations using simulate.cpp.

🔄 Automorphisms

An automorphism is defined by a permutation of bit indices:

Automorphism({target_indices})

Each entry in automorphisms generates one AED decoding path.
Therefore, $\mu = \text{automorphisms.size()}$.

To enable AED, set:

static bool use_automorphisms = true;

Example:

static std::vector<Automorphism> automorphisms = {
    Automorphism({0, 1, 2, ..., 127}),      // Identity
    Automorphism({118, 7, 84, ..., 17}),    // Random permutation 1
    Automorphism({102, 21, 68, ..., 19})    // Random permutation 2
};

---

Type C Pretransformations

We provide several presets for ScED:

• SCL: standard SC(L) decoding
• affine2: 2-path affine ScED using the least polarized bit
• affine4: 4-path affine ScED using the two least polarized bits

Note:
These presets internally contain three/five paths to include the unmodified SC(L) path. However, if a covering is ensured, including this path has negligible effect (see paper for reference).

std::vector<std::vector<PT>> SCL = {{}};

std::vector<std::vector<PT>> affine2 = {
    {},
    {PT{{}, rev_info_set[0], 0, ENSEMBLE_PT}},
    {PT{{}, rev_info_set[0], 1, ENSEMBLE_PT}}
};

std::vector<std::vector<PT>> affine4 = {
    {},
    {PT{{}, rev_info_set[0], 0, ENSEMBLE_PT}, PT{{}, rev_info_set[1], 0, ENSEMBLE_PT}},
    {PT{{}, rev_info_set[0], 0, ENSEMBLE_PT}, PT{{}, rev_info_set[1], 1, ENSEMBLE_PT}},
    {PT{{}, rev_info_set[0], 1, ENSEMBLE_PT}, PT{{}, rev_info_set[1], 0, ENSEMBLE_PT}},
    {PT{{}, rev_info_set[0], 1, ENSEMBLE_PT}, PT{{}, rev_info_set[1], 1, ENSEMBLE_PT}}
};

To use a preset:

ensemble_pretransformations = affine4;

Alternatively, you can define a custom ensemble and assign it to ensemble_pretransformations.

Reminder:
Always include the {} (unmodified path) if you plan to use direct_comparison.