Codes to detect insertion and deletion errors in a dense storage medium

A non-transitory computer-readable medium comprising instructions that are executable by one or more processors to cause a computing system to:

• receive, at a decoder, a first input at a first time, wherein the decoder has a first state at the first time;
• calculate a first distance between the first input and a first set of valid inputs, wherein the first set of valid inputs is defined by a first component trellis code;
• determine a second state of the decoder based on the first state, the first input, and the first component trellis code;
• receive, at the decoder, a second input at a second time after the first time;
• calculate a second distance between the second input and a second set of valid inputs, wherein the second set of valid inputs is defined by a second component trellis code and wherein the second set of valid inputs is disjoint from the first set of valid inputs;
• and
• determine a third state of the decoder based on the second state, the second input, and the second component trellis code.

A method for detecting deletion and insertion errors, the method comprising:

• encoding a set of inputs using a convolutional encoder to produce a set of encoded outputs, wherein the convolutional encoder includes a first component convolutional code and a second component convolutional code, the first component convolutional code produces outputs within a first subset of a set of possible outputs, the second component convolutional code produces outputs within a second subset of the set of possible outputs, and the first subset is disjoint from the second subset;
• receiving, at a decoder, a set of encoded inputs, wherein each encoded input in the set of encoded inputs represents a sequence of one or more symbols, wherein the decoder includes a first component trellis code and a second component trellis code, the first component trellis code defines a first set of valid inputs, the second component trellis code defines a second set of valid inputs, the first set of valid inputs is equivalent to the first subset of possible outputs, and the second set of valid inputs is equivalent to the second subset of possible outputs;
• determining a distance between each encoded input in the set of encoded inputs and an applicable set of valid inputs to produce a set of distances, wherein the applicable set of valid inputs switches between the first set of valid inputs and the second set of valid inputs;
• producing a set of decoded outputs for the set of encoded inputs, wherein the set of decoded outputs is determined based on the first component trellis code and the second component trellis code;
• identifying, based on the set of distances, insertion and deletion errors in the set of encoded inputs;
• and
• modifying, based on identifying the insertion and deletion errors in the set of encoded inputs, the set of decoded outputs to produce a modified set of decoded outputs.