This is a library and simulation tool for a Forward Error Correcting (FEC) scheme named "Polar Codes". A very promising group of codes that have low encoding and decoding latency with high BLER-performance.
This should be straight forward, given that you have a recent compiler (GCC).
You need to clone the repo with the --recursive option to ensure that the pybind11 submodule is checked out as well.
git clone --recursive
Before compiling this project the following packages need to be installed on your system:
- doxygen
- libcppunit-dev
- libtclap-dev
- libssl-dev
- libfmt-dev
- python3-numpy
- python3-scipy
mkdir build
cd build
cmake ..
make -j<cputhreads>
make install
In build/bin
./pctest # Run a set of C++ tests
./pcsim # Run C++ simulations
With import pypolar you can use the Encoders, Decoders, Puncturers and Detectors with Python3. Also, you can use pypolar.frozen_bits to get a suitable frozen bit set for polar codes.
A quick example
import numpy as np
import pypolar
frozen_bit_positions = pypolar.frozen_bits(64, 40, 1.0, 'BB')
encoder = pypolar.PolarEncoder(64, frozen_bit_positions)
info_bits = np.random.randint(0, 2, 40, dtype=np.uint8)
info_bytes = np.packbits(info_bits)
codeword_bytes = encoder.encode_vector(info_bytes)
codeword_bits = np.unpackbits(codeword_bytes)
llrs = 1.0 - 2.0 * codeword_bits
decoder = pypolar.PolarDecoder(64, 4, frozen_bit_positions, 'mixed')
hat_bytes = decoder.decode_vector(llrs)
assert np.all(info_bytes == hat_bytes)We have some CRC polynomials available. First, we have a CRC-8, CRC-16-CCITTFALSE, and CRC-32 which only work on byte multiples. Further, we have some 5G NR CRCs available that can operate on any bit size.
- CRC6
- CRC11
- CRC16
- CRC24C
import numpy as np
import pypolar
detector = pypolar.Detector(11, "CRCNR")
data = np.array([1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0], dtype=np.uint8)
packed_data = np.packbits(data)
# NumPy (and probably most software) append 0's to pack bytes. Here [0, 0, 0]
reference = 0x06c8
print(f'0x{reference:03x}')
# We expect packed input with packed_data: 2 byte
# We provide the total number of bits: 13
checksum = detector.calculate(packed_data, data.size)
print(f'0x{checksum:03x}')As seen in the example, we can't infer the actual number of significant bits from the packed vector data size.
The library is split into four independent modules:
- An encoder,
- a decoder,
- error detection for list decoding and
- a code constructor
Their respective base classes are purely virtual, so every algorithm implementation can be called via the base object's functions. This allows for easy testing as you can throw any algorithm at a general performance tester without having to modify the testers code in any way.
Sometimes, the installed version is not on the correct path. In case you used cmake .. without further arguments, it might help to run:
export PYTHONPATH=/usr/local/lib/python3/dist-packages:$PYTHONPATH
export LD_LIBRARY_PATH=/usr/local/lib:$LD_LIBRARY_PATH
in every terminal you open. Or put this in your .bashrc or .zshrc or your shell config file. The /usr/local part in the lines above must match your CMAKE_INSTALL_PREFIX. You can set this to any path with cmake -DCMAKE_INSTALL_PREFIX=/your/custom/fancy/install/prefix ... A more permanent solution needs further consideration because of the interaction between different system components.
Theoretically, there is libbenchmark-dev in Ubuntu 20.04 but we need a newer benchmark version. Thus, we must build and install from source.
This implementation relies on prior publications. We'd like to point out some of them. It should be noted that the number of publications on polar codes is enormous. This is a subjective selection of references that helped shape this implementation.
- E. Arıkan, "Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels", IEEE Transactions on Information Theory, July 2009, DOI: 10.1109/TIT.2009.2021379
- H. Vangala, E. Viterbo, Y. Hong, "A Comparative Study of Polar Code Constructions for the AWGN Channel", arXiv, January 2015, DOI: 10.48550/arXiv.1501.02473
- I. Tal, A. Vardy, "List Decoding of Polar Codes", IEEE Transactions on Information Theory, May 2015, DOI: 10.1109/TIT.2015.2410251
- A. Balatsoukas-Stimming, M. Parizi, A. Burg, "LLR-Based Successive Cancellation List Decoding of Polar Codes", IEEE Transactions on Signal Processing, October 2015, DOI: 10.1109/TSP.2015.2439211
- H. Vangala, E. Viterbo, Y. Hong, "Efficient algorithms for systematic polar encoding", IEEE Communications Letters, January 2016, DOI: 10.1109/LCOMM.2015.2497220
- P. Giard "High-Speed Decoders for Polar Codes", McGill University, Montreal, Canada, September 2016, DOI: 10.1007/978-3-319-59782-9, https://escholarship.mcgill.ca/concern/theses/3r074x791
- M. Sybis et al., "Channel coding for ultra-reliable low-latency communication in 5G systems", Vehicular Technology Conference (VTC Fall), Montreal, QC, Canada, September 2016, DOI: 10.1109/VTCFall.2016.7880930
- M. Hanif, M Ardakani, "Fast Successive-Cancellation Decoding of Polar Codes: Identification and Decoding of New Nodes", IEEE Communications Letters, November 2017, DOI: 10.1109/LCOMM.2017.2740305
- G. He et al., "Beta-Expansion: A Theoretical Framework for Fast and Recursive Construction of Polar Codes", Global Communications Conference (GLOBECOM), Singapore, December 2017, DOI: 10.1109/GLOCOM.2017.8254146
This program is licensed under the GPLv3+ license, see [[COPYING]].
Some CRCs are calculated with CRC++. CRC++ is free to use and provided under a BSD license.