Polar coding and decoding for correcting deletion and/or insertion errors

A data processing system with improved error correction operation, comprising:

• a processor;
• and
• a non-transitory memory with instructions thereon, wherein the instructions upon execution by the processor cause the processor to:
• receive a portion of a block of symbols that includes a plurality of errors, the symbols corresponding to information bits encoded using a polar code, the block of symbols having been provided to an insertion channel or a deletion channel prior to reception by the data processing system, the plurality of errors comprising (a) two or more deleted symbols, (b) two or more inserted symbols, or (c) at least one deleted symbol and at least one inserted symbol, wherein the block comprises N symbols and the received portion of the block comprises M symbols, and wherein M and N are integers;
• and
• use the received portion of the block of symbols to perform successive cancellation decoding to generate an estimate of the information bits corresponding to the block of symbols,
• wherein at least one bit of the information bits has a known value at the data processing system prior to receiving the portion of the block of polar-coded symbols, and
• wherein generating the estimate has a complexity that scales polynomially with a number of the plurality of errors and a number of symbols in the block (N).

A non-transitory computer-readable storage medium having instructions stored thereupon for improved error correction, comprising:

• instructions for receiving, at a data processing system, a portion of a block of polar-coded symbols that includes d insertion or deletion symbol errors, the block of polar-coded symbols having been provided to an insertion channel or a deletion channel prior to reception by the data processing system, the block comprising N symbols, the received portion of the block comprising M symbols, and wherein d≥2, M and N are integers;
• instructions for estimating, based on one or more recursive calculations in a successive cancellation decoder, a location or a value corresponding to each of the d insertion or deletion symbol errors;
• and
• instructions for decoding, based on estimated locations or values, the portion of the block of polar-coded symbols to generate an estimate of information bits that correspond to the block of polar-coded symbols,
• wherein the successive cancellation decoder comprises at least log2(N)+1 layers, each layer comprising up to d2N processing nodes arranged as N groups, each of the N groups comprising up to d2 processing nodes,
• wherein a complexity of estimating the location or the value has a complexity that scales polynomially with d,
• wherein at least one bit of the information bits has a known value at the data processing system prior to receiving the portion of the block of polar-coded symbols, and
• wherein the d insertion or deletion symbol errors comprise (a) two or more deleted symbols, (b) two or more inserted symbols, or (c) at least one deleted symbol and at least one inserted symbol.

A method for improved error correction, comprising:

• receiving, at a data processing system, a portion of a block of polar-coded symbols that includes d insertion or deletion symbol errors, the block of polar-coded symbols having been provided to an insertion channel or a deletion channel prior to reception by the data processing system, the block comprising N symbols, the received portion of the block comprising M symbols, and wherein d≥2, M and N are integers;
• estimating, based on one or more recursive calculations in a successive cancellation decoder, a location or a value corresponding to each of the d insertion or deletion symbol errors;
• and
• decoding, based on estimated locations or values, the portion of the block of polar-coded symbols to generate an estimate of information bits that correspond to the block of polar-coded symbols,
• wherein the successive cancellation decoder comprises at least log2(N)+1 layers, each layer comprising up to d2N processing nodes arranged as N groups, each of the N groups comprising up to d2 processing nodes,
• wherein estimating the location or the value has a complexity that scales polynomially with d,
• wherein at least one bit of the information bits has a known value at the data processing system prior to receiving the portion of the block of polar-coded symbols, and
• wherein the d insertion or deletion symbol errors comprise (a) two or more deleted symbols, (b) two or more inserted symbols, or (c) at least one deleted symbol and at least one inserted symbol.