Verification Codes for Deletions

We demonstrate new deletion codes based on low-density parity-check (LDPC) codes using the verification code framework. Verification codes are designed to work with data organized as packets; packets could be thousands of bits (Internet packets) or simply represent a thirty-two bit integer. Deletions are assumed to occur at the packet level. Verification codes for deletions (VCDs) have polynomial time encoding and decoding algorithms and can be analyzed asymptotically using standard LDPC techniques. Variations of VCDs are also robust against transpositions, random insertions, and random substitution errors.