LDPC: Python Tools for Low Density Parity Check Codes
Project description
LDPC version 2 (Beta version)
A C++ rewrite of the LDPC
package for decoding low density parity check checks.
Warning, whilst efforts have been made to provide backwards compatability with LDPCv1, the new version may introduce breaking changes.
Documentation
The documentation for LDPCv2
can be found here
Installation
The easiest way to install the package is via pip.
pip install -U ldpc
Python - Installation from source
The C++ source code can be found in src_cpp. Python bindings are implemented using Cython and can be found in src/ldpc. To install the Python version of the repository follows the instructions below:
- Download the repo.
- Navigate to the root.
- Pip install with
python>=3.8
. Note: installation requires aC
compiler. Eg.gcc
on Linux orclang
on Windows.
git clone git@github.com:quantumgizmos/ldpc_v2.git
cd ldpc
pip install -Ue .
New features
- A new C++ template class
GF2Sparse
. This is a more flexible implementation of themod2sparse
data structure used in the LDPCv1. This will make it much easier to expand the package. - Serial schedules for the BP decoder.
- Run-time improvements for BP+OSD OSD-0. The decoder now implements the fast-syndrome OSD-0 implementation (https://arxiv.org/abs/1904.02703), where Gaussian elimination is terminated as soon as the syndrome becomes linearly dependent on the reduced columns.
- BP+LSD: Belief propagation plus localised statistics decoding. A parallel decoding algorithm that matches the perforance of BP+OSD. Note that the version implemented currenlty runs in serial. We are working on the parallel version! See our paper: https://arxiv.org/abs/2406.18655
- The union-find matching decoder (https://arxiv.org/abs/1709.06218). This is an implementation of the Delfosse-Nickerson union-find decoder that is suitable for decoding surface codes and other codes with "matchable" syndromes.
- The BeliefFind decoder. A decoder that first runs belief propagation, and falls back on union-find if if the BP decoder fails to converge as proposed by Oscar Higgott in https://arxiv.org/abs/2203.04948
- Flip and P-flip decoders as introduced by Thomas Scruby in https://arxiv.org/abs/2212.06985.
- Improved GF2 linear algebra routines (useful for computing code parameters)
ToDos
LDPCv2
is still a work in progress. Ongoing projects are listed below:
- Implement parallel version of BP+LSD algorithm using OpenMP.
- Improve support for parallel processing across the package.
- More decoders could be implemented (eg. small set-flip, https://arxiv.org/abs/1810.03681)
- Stabiliser inactivation BP (https://arxiv.org/abs/2205.06125)
- Generalised BP (https://arxiv.org/abs/2212.03214)
- Functions need to be properly documented (in progress)
- Further STIM integration
- More functionality for studying classical codes. Eg. support for received vector decoding and the AWGN noise channel.
BP+LSD Quickstart
Usage of the new BP+LSD decoder from https://arxiv.org/abs/2406.18655. Similar to BP+OSD, the LSD decoder can be applied to any parity check matrix. We recommend you start with lsd_order=0
. The speed/accuracy trade-off for higher order values can be explored from there. Example below:
import numpy as np
import ldpc.codes
from ldpc.bplsd_decoder import BpLsdDecoder
H = ldpc.codes.hamming_code(5)
## The
bp_osd = BpLsdDecoder(
H,
error_rate = 0.1,
bp_method = 'product_sum',
max_iter = 2,
schedule = 'serial',
lsd_method = 'lsd_cs',
lsd_order = 0
)
syndrome = np.random.randint(size=H.shape[0], low=0, high=2).astype(np.uint8)
print(f"Syndrome: {syndrome}")
decoding = bp_osd.decode(syndrome)
print(f"Decoding: {decoding}")
decoding_syndrome = H@decoding % 2
print(f"Decoding syndrome: {decoding_syndrome}")
Attribution
If you use this software in your research please cite as follows:
@software{Roffe_LDPC_Python_tools_2022,
author = {Roffe, Joschka},
title = {{LDPC: Python tools for low density parity check codes}},
url = {https://pypi.org/project/ldpc/},
year = {2022}
}
If you have used the BP+OSD class for quantum error correction, please also cite the following paper:
@article{roffe_decoding_2020,
title={Decoding across the quantum low-density parity-check code landscape},
volume={2},
ISSN={2643-1564},
url={http://dx.doi.org/10.1103/PhysRevResearch.2.043423},
DOI={10.1103/physrevresearch.2.043423},
number={4},
journal={Physical Review Research},
publisher={American Physical Society (APS)},
author={Roffe, Joschka and White, David R. and Burton, Simon and Campbell, Earl},
year={2020},
month={Dec}
}
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for ldpc-2.1.0-cp313-cp313-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | da434f7633ec3acd0914eb9ac449d3419e558d13952f425d21a78a72e398bb9a |
|
MD5 | 7882983a537b2eea110af0f0edcb83b1 |
|
BLAKE2b-256 | fcc3e7ea29ca44935ff20b0ae283f9b0ad8162604e3f9836b7f6b3fbbb4cb088 |
Hashes for ldpc-2.1.0-cp313-cp313-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6e714d386581414a200108aa675a1a14c81215662f1681fa1654d99fd49b7038 |
|
MD5 | 6e324a2ad5309d679ad3a4fd20e29def |
|
BLAKE2b-256 | 3a682b3bab28764cb035ce56b9994ccc2edda1009d8cc433c1201080552a622c |
Hashes for ldpc-2.1.0-cp313-cp313-macosx_13_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b1916c2eafad4730706b379c40548a29a44b5b579e7f8d036e82f449af25449b |
|
MD5 | 31aaf482bf545701a16da0a803ff8e3a |
|
BLAKE2b-256 | be9affb350d28127cb65acec356d4d84aed6b401439dc6161685857eca17e158 |
Hashes for ldpc-2.1.0-cp313-cp313-macosx_13_1_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b87bceac2cdf684c4670b79d68827c493276ed48419853b1878dbf3c81c363d8 |
|
MD5 | 0345591b40d0b4e65379e751e9386200 |
|
BLAKE2b-256 | 12774ce72a79f4577b70e57178d97dc95bc639e50d9b13dbb89c5c9453ba43db |
Hashes for ldpc-2.1.0-cp312-cp312-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f2c9347baf2233542b6c34595a172836711f3c4ab43a2c73490701064166028c |
|
MD5 | 730d2d23d2c0d061a2b114218fd40e39 |
|
BLAKE2b-256 | 72316a7b4e0c3885cba0b50db1e06d855f6386a4e1536082e393b19b6ec139f4 |
Hashes for ldpc-2.1.0-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cae74b5f57aca937c0efefcc4f250a4fac0b1e5bf84c9a59e43b9fa45aa43bbc |
|
MD5 | e9f28a795bdbba9c5fff00b7a306019e |
|
BLAKE2b-256 | f6bd70883e7d3e7af00fc8c5080c97c5de30f311ec2c60b4aa2f40d774adbd87 |
Hashes for ldpc-2.1.0-cp312-cp312-macosx_13_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 33222354e29ee3258d571e45e804267c2b80de561ceb544934ad8d9928d6339f |
|
MD5 | 6c3ba19e52caca2a7b541ef6e5226326 |
|
BLAKE2b-256 | 162dc8ce7f6e20a79501c37b0c120a02212ab4ea22f0dc99d055993886d72df9 |
Hashes for ldpc-2.1.0-cp312-cp312-macosx_13_1_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d0ad5c47b792b13b7f72c76bf30a58dc221c6c34ab711e3c1f7c3a04b71b00e9 |
|
MD5 | b281a5f667b8a914861b0a0a10f13498 |
|
BLAKE2b-256 | 5cca5ed88336c305e33e0aad8b06c8ebe34c5e5173fce6934b680b612df20526 |
Hashes for ldpc-2.1.0-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 481e9ec80a6a4e57c4a9613eac7b6fd7411f1db68df184838eb12134fa873d30 |
|
MD5 | 7614a9d24b1570c8f7f5eda869ea6ee6 |
|
BLAKE2b-256 | 3b8234f9a7e8513733d2c4cbf2a5ea125d7bbcbdbd4b148914002920af4a9d71 |
Hashes for ldpc-2.1.0-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | be14c275a45a4cfb7917b3d28ea6b94853df2de36b35cd44713a5f4da9a846f9 |
|
MD5 | 43e9b72a4f1388a93c8ca79d6e6cdaa7 |
|
BLAKE2b-256 | a6d0a2d4d3a22d85d01877d71382356375301f0f78dedc616365d8eaf69664ef |
Hashes for ldpc-2.1.0-cp311-cp311-macosx_13_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 66ce38cc85d55aff3e29bd8a6a51d4a381494e7a71c91641b7316853e4c39328 |
|
MD5 | d1667e09aaa801ae41872316a4c3b08a |
|
BLAKE2b-256 | cff0d7a8daf80e74a81d30b9731ffb555e4c6c59eae42c8f0cc7b6b44b53acb4 |
Hashes for ldpc-2.1.0-cp311-cp311-macosx_13_1_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cc400855ca33fded76e8e27ff39950d833f2912b0ba039a5c452fe595f870493 |
|
MD5 | afae2a53885b9a29b4b50ae4820c822f |
|
BLAKE2b-256 | a095692268cb751f5eb68a22680aa7b4b476b0b0fcb7f2919b521df8c180cb33 |
Hashes for ldpc-2.1.0-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a82c76a1857816097550882974f3b1584813a7e597194c17dd3dead1fa05f27a |
|
MD5 | 60e19d1c74b58d24e73162718476133a |
|
BLAKE2b-256 | f0c27e068a9eccbdc859b4d81978360844feb24fbf144f280943fa15b06f9e9e |
Hashes for ldpc-2.1.0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 14c5ff3908de0ca651514dcd5bbc8b3e2ea84d92ca5fcd95a91178721cb1efb6 |
|
MD5 | 6b8d967f176c964918deab319dad86a1 |
|
BLAKE2b-256 | fd2ace925f8d739660d8578e8638ea48dc93226f2ed37180b8158fb2b5b3d53d |
Hashes for ldpc-2.1.0-cp310-cp310-macosx_13_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 925c042dbae3902e11776243c1e51cbc1a7dfa57b59a225d8b66716aaa229e5b |
|
MD5 | bf55204bbb05acd9fb479b01f164176d |
|
BLAKE2b-256 | 769a88ffbeaacf275b7c36f49ecc9560b1b50a78ed2899a5804512c92836e45e |
Hashes for ldpc-2.1.0-cp310-cp310-macosx_13_1_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d729f36b5243fa497fc0bf419c3df0f993bd46cc1a6bd20f755a7d5df0a8a98f |
|
MD5 | 351a931906bc55a8bafe4066d7b60d89 |
|
BLAKE2b-256 | 7dc1d16bcaaff72e3d57471c948e8a69265da5f3b6838d23f8a16c198853c62c |
Hashes for ldpc-2.1.0-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e8a785d503db372919b55841ca6d486a865a26b0b5b1c0dee59734fc94dfac79 |
|
MD5 | 0573f1dda9a98e929515d977faef6cc3 |
|
BLAKE2b-256 | 300d78bd6936bc9c5ae155d6274ed78ffeaba9be4dff938496f44b808f07dcec |
Hashes for ldpc-2.1.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b9e8317ed1a7450c5e778e2bd8ecc57dfaa4ef03b1aba8b9771e92a12a29c4f2 |
|
MD5 | b7e02ba67f67f9347738ee21ce2d5469 |
|
BLAKE2b-256 | 3bacbc9a73725e6404bec20c35d65c72a4ce58115a77900eb31d3a44374399df |
Hashes for ldpc-2.1.0-cp39-cp39-macosx_13_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0430e6cb59f04bbf7be96d3b259cec2fd3c0f064c3f8d93f110679b85b3ccbc8 |
|
MD5 | c8c1e4505e50ea8b57544d14201423e5 |
|
BLAKE2b-256 | 663c0cc1e1817dcb05e6486abf9cc7b4e8186dc539c73165948c34176e8311c5 |
Hashes for ldpc-2.1.0-cp39-cp39-macosx_13_1_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6dca9f3b68970ecd9dd3ca1c01fbda17eb255d44447d3b7faabcadb0b11618c0 |
|
MD5 | 263363d716c1c56eb596e844ae79c0dd |
|
BLAKE2b-256 | 5ef496346e740dc39a3aa536cb91d7fbfb340aca494ac4b77dc84c11f30895e2 |
Hashes for ldpc-2.1.0-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b21dc3395f4bbbfb3ba4f2854548314814d0252320353a6b75e31e36f97aa4b6 |
|
MD5 | 627cd8145dace2e09f6a12e4283e83a6 |
|
BLAKE2b-256 | 3d024f2097ff4a603fb97318bb97df5258aa366e7af25d1bb9c47b99784c7f0d |
Hashes for ldpc-2.1.0-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c6ed9211a4b2a6b8a2a6818bc2a72f22c2461758cc20c735dcbc2aa14e0600c4 |
|
MD5 | e9270285264d2849d342148b6458481c |
|
BLAKE2b-256 | b68daedd768538111ccfcfbae8dc3912d366a717f40d995be53c3c4aae1a121f |
Hashes for ldpc-2.1.0-cp38-cp38-macosx_13_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5045b9309357cddd2b0040410b7f9b6f5b995973d5f6f3e6471deeb54b5d8568 |
|
MD5 | 7b678af440641f5cc2bc9e42aa109bc7 |
|
BLAKE2b-256 | b802b043af0b5700bd37c305ea3319d4554573504478f7b570ccbb38f780dbba |
Hashes for ldpc-2.1.0-cp38-cp38-macosx_13_1_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 179b63aad2693e1faa5b83012447b1d8fbf2756860debad5dd0e9a6ce186dc9a |
|
MD5 | 2d4dedcf466bf4c63dedd4a491ffb574 |
|
BLAKE2b-256 | b436e8d61a06300abd599d2986d9cc6de867f242743de12d08b1a4f9ae5f76eb |