Verification-Based Decoding for Packet-Based Low-Density Parity-Check Codes
Michael G. Luby, Michael Mitzenmacher · IEEE Transactions on Information Theory · 2005
We introduce and analyze verification-based decoding for low-density parity-check (LDPC) codes, an approach specifically designed to manipulate data in packet-sized units. Verification-based decoding requires only linear time for both encoding and decoding and succeeds with high probability under random errors. We describe how to utilize code scrambling to extend our results to channels with errors controlled by an oblivious adversary.