Some incomplete thoughts

First, we need to count the number of unique segments in 1000 bits, which is the sum of numbers from 1 to 1000. 500500, which needs 19 extra bits.

Secondly, arrange the 1000 bits in a 5-dimension array. The co-ordinates are (x0, x1, x2, x3, x4). xi is a number between 0 and 3. Calculate parity bits in each dimension. We got 20 parity bits. They are transmitted along with the original message. Based on the result of the parity checking, we may be able to figure out the start and the end of the corrupted segment.