Decoding technique for linear block codes

A computer-readable storage media having computer-executable instructions for decoding a code sequence, the instructions, when executed by a computing device, performing a method comprising:

• incrementally flipping a subset of bits out of a plurality of bits within the code sequence if the code sequence is not one of a plurality of valid codewords, wherein each incremental flip yields one of a plurality of modified code sequences, wherein the flipping comprises:
• initializing a sequence S1,1 of length n with elements from a finite field;
• initializing an index i and an index r each to a value of 1;
• obtaining a subsequence S1,1 by copying entries from the sequence S1,1, wherein the sequence S1,1 defines a prior sequence;
• reversing an order of the modified code sequences within the subsequence S1,1;
• incrementing an i-th bit of entries in the subsequence to a next element in the finite field to yield S1,1;
• concatenating the subsequence and the prior sequence to obtain a new sequence;
• incrementing index r;
• when index r equals q+1, wherein q is the number of elements:
• determining when index i is equal to n, and when index i is equal to n, completing the output sequence containing the modified code sequences;
• when index i is not equal to n, incrementing index i, setting index r to 1, and returning to obtaining a subsequence S1,1 by copying entries;
• and
• when index r is not equal to q+1, returning to obtaining a subsequence S1,1 by copying entries
• for each modified code sequence, saving the modified code sequence if a syndrome associated with the modified code sequence indicates that the modified code sequence is one of the plurality of valid codewords, the syndrome being computed by adding an update vector to a prior syndrome computed for a preceding code sequence;
• identifying a corrected codeword from the modified code sequences that were saved;
• and
• obtaining information from the corrected codeword.

A computing device, comprising:

• a processor;
• a memory into which a plurality of instructions are loaded, wherein upon execution of the plurality of instructions by the processor, the system being configured to:
• receive an encoded bit stream, the bit stream comprising a plurality of code sequences;
• obtain a plurality of information bits within each code sequence representing a valid codeword;
• and
• obtain another plurality of information bits within each code sequence representing a non-valid codeword, the other plurality of information bits being obtained by estimating a confidence for a plurality of bits within the code sequence to determine a subset of the plurality of bits, wherein the subset is incrementally flipped to obtain a set of modified code sequences, one modified code sequence of the set is selected as a corrected codeword and used to obtain the other plurality of information bits, wherein the incremental flipping comprises:
• initializing a sequence S1,1 of length n with elements from a finite field;
• initializing an index i and an index r each to a value of 1;
• obtaining a subsequence S1,1 by copying entries from the sequence S1,1 wherein the sequence S1,1 defines a prior sequence;
• reversing an order of the modified code sequences within the subsequence S1,1;
• incrementing an i-th bit of entries in the subsequence to a next element in the finite field to yield S1,1;
• concatenating the subsequence and the prior sequence to obtain a new sequence;
• incrementing index r;
• when index r equals q+1, wherein q is the number of elements:
• determining when index i is equal to n, and when index i is equal to n, completing the output sequence containing the modified code sequences;
• when index i is not equal to n, incrementing index i, setting index r to 1, and returning to obtaining a subsequence S1,1 by copying entries;
• and
• when index r is not equal to q+1, returning to obtaining a subsequence S1,1 by copying entries.