Verification Codes

Most work in low-density parity-check codes focuses on bit-level errors. In this paper, we introduce and analyze verification codes, which are simple low-density parity-check codes specifically designed to manipulate data in packet-sized units. Verification codes require only linear time for both encoding and decoding and succeed 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. Although verification codes over n packets require Omega(log n) bits per packet, in practice they function well for packet sizes as small as thirty-two bits. Verification codes therefore offer advantages for applications that naturally handle data in packet-sized units, and may also prove useful as an outer code for other code constructions.