"Constant Weight Codes for Correcting Single Deletion"

Asymptotically optimal codes that can correct a single deletion have been known for decades, but the best known codes that correct multiple deletions are still poor. We suggest constructing codes with constant Hamming weight and taking the union of codes with sufficiently different weights. This approach is attractive for two reasons. First, it produces asymptotically optimal codes in the single deletion case. Second, it significantly reduces the growth rate of the problem size.