DOCSEARCHbyAlgolia
Submit Docs

LDPC: Python Tools for Low Density Parity Check Codes

repository·main·Indexed 42 days ago

https://github.com/quantumgizmos/ldpc

A Python library for Low-Density Parity-Check (LDPC) codes providing tools for classical and quantum coding. It includes decoding algorithms such as Belief Propagation (BpDecoder), Ordered Statistics Decoding (BpOsdDecoder), and Local Soft Decoding (BpLsdDecoder). The package features utilities for code analysis (ldpc.code_util), GF(2) linear algebra (ldpc.mod2), standard code generation (ldpc.codes), and Monte-Carlo simulations via MonteCarloBscSimulation.

Tokens
6.6K
Snippets
24
Records
36
Agent score
53%

What's inside LDPC

  1. Use Sinter Decoders for LDPC decoding

    main

    The ldpc.sinter_decoders module provides specialized decoder implementations. The primary available classes are:

    • SinterBpOsdDecoder: A decoder implementing Bit Flipping with Ordered Statistics Decoding (OSD).
    • SinterBeliefFindDecoder: A decoder implementing a belief-based decoding approach.

    These decoders are part of the sinter suite within the ldpc package.

  2. Use ldpc.code_util for code analysis and construction

    main
    The ldpc.code_util module provides a suite of utility functions for analyzing Low-Density Parity-Check (LDPC) codes and constructing their fundamental matrices. Use these tools to compute code parameters, estimate or calculate exact code distances, search for cycles in the parity-check matrix, and construct generator matrices.

  4. Install ldpc from source

    main

    To install the Python bindings from source, you must have a C compiler installed (e.g., gcc on Linux or clang on Windows) and use python>=3.8. The Python bindings are implemented using Cython and are located in src/ldpc, while the core C++ source is in src_cpp.

    Follow these steps:

    1. Clone the repository.
    2. Navigate to the root directory.
    3. Install the package in editable mode using pip install -Ue ..
    git clone git@github.com:quantumgizmos/ldpc_v2.git
cd ldpc
pip install -Ue .

  5. Load and inspect binary linear codes

    main

    In ldpc, binary linear error correction codes are represented by their parity check matrix $H$ stored in scipy.sparse format. You can load standard codes from the ldpc.codes submodule. To view the matrix in a human-readable dense format, use the .toarray() method on the sparse matrix object.

    import numpy as np
import ldpc.codes

n = 5  # length of the repetition code
H = ldpc.codes.rep_code(n)  # returns the parity check matrix
print(H.toarray())

  6. Integrate BPOSD and BeliefFind decoders with Stim Sinter

    main

    To perform circuit-level noise decoding and Monte Carlo sampling, the BPOSD and BeliefFind decoders are integrated with the Stim Sinter library.

    To use them, you must pass the SinterBpOsdDecoder and SinterBeliefFindDecoder classes into the custom_decoders dictionary within the sinter.collect function. This allows Sinter to use these specific LDPC decoders to process the quantum error correction circuits generated by Stim.

    import sinter
from ldpc.sinter_decoders import SinterBeliefFindDecoder, SinterBpOsdDecoder

# Example usage within sinter.collect
samples = sinter.collect(
    tasks=my_tasks,
    decoders=["bposd", "belief_find"],
    custom_decoders={
        "bposd": SinterBpOsdDecoder(
            max_iter=5,
            bp_method="ms",
            ms_scaling_factor=0.625,
            schedule="parallel",
            osd_method="osd0",
        ),
        "belief_find": SinterBeliefFindDecoder(
            max_iter=5, 
            bp_method="ms", 
            ms_scaling_factor=0.625, 
            schedule="parallel"
        ),
    },
    # ... other arguments
)

  7. Encode data using a generator matrix

    main

    To transform unencoded data into codewords, you must first construct a generator matrix $G$ from the parity check matrix $H$ using ldpc.code_util.construct_generator_matrix(H).

    To encode a $k$-bit message $b$ into an $n$-bit codeword $c$, perform the matrix multiplication $c = G^T imes b ext{ mod } 2$. A valid codeword $c$ must satisfy the condition $H imes c^T = 0 ext{ mod } 2$.

    import numpy as np
import ldpc.codes
import ldpc.code_util

# 1. Setup code
H = ldpc.codes.hamming_code(3)
G = ldpc.code_util.construct_generator_matrix(H)

# 2. Encode a 4-bit message
b = np.array([1, 0, 1, 1])
c = G.T @ b % 2

# 3. Verify codeword validity
print(H @ c % 2)  # Should result in all zeros

  8. Generate LDPC codes using ldpc.codes

    main

    The ldpc.codes module provides functions to generate various types of error-correcting codes. You can use these functions to create specific code structures such as Hamming codes, repetition codes, ring codes, or random binary codes.

    from ldpc.codes import hamming_code, rep_code, ring_code, random_binary_code

# Example usage (exact parameters depend on implementation)
code = hamming_code(n=7)
# or
code = rep_code(n=3)
# or
code = ring_code(n=4)
# or
code = random_binary_code(n=10, k=5)

  11. Use the BpOsdDecoder for LDPC decoding

    main

    The BpOsdDecoder class provides a decoder that combines Belief Propagation (BP) with Ordered Statistics Decoding (OSD). This hybrid approach leverages the efficiency of BP and the error-correction capabilities of OSD to improve decoding performance in LDPC codes.

    To use this decoder, you can instantiate ldpc.bposd_decoder.BpOsdDecoder. Detailed member functions and initialization parameters are available via the ldpc.bposd_decoder module.

    from ldpc.bposd_decoder import BpOsdDecoder

# Initialize the BP+OSD decoder
decoder = BpOsdDecoder(...)

  12. Perform classical Monte Carlo simulations with MonteCarloBscSimulation

    main

    The MonteCarloBscSimulation class in the ldpc.monte_carlo_simulation module is used to perform classical Monte Carlo simulations for Low-Density Parity-Check (LDPC) codes, specifically targeting the Binary Symmetric Channel (BSC).

    from ldpc.monte_carlo_simulation import MonteCarloBscSimulation