General rate N/(N+1) (0, G) code construction for data coding

Apparatus for decoding a sequence of codewords having at least N+1 elements into a sequence of N-element datawords, the sequence of codewords received as a signal from a storage or transmission medium, the decoder comprising:

• a processing adapted to detect a middle pivot bit and first and second portions of each codeword, each portion adjacent to the middle pivot bit;
• a logic circuit, coupled to the processor, adapted to generate the dataword from the first and second portions by:
• if the middle pivot bit is set to a first value:
• 1) extracting a set of one or more preserved bits and a first pivot bit for each portion;
• 2) generating, for each portion, a substring from the set of preserved elements and, if a second pivot bit and at least one correction bit is detected in the portion, from at least one code violation defined by the second pivot bit;
• 3) combining each substring to form the dataword;
• otherwise, if the middle pivot bit is set to second value, by:
• 4) providing the first and second portions as the dataword.

A method of encoding a sequence of N-element datawords into a sequence of codewords having at least N+1 elements for storage or transmission such that the sequence of codewords satisfies a G constraint, wherein the G constraint corresponds to a maximum number of consecutive elements having the same value, the method comprising the steps of:

• (a) dividing each dataword into left and right substrings by inserting a middle pivot bit therebetween;
• (b) determining whether each of the left and right substrings contains at least one code violation of a first or second case, wherein:
• the first case corresponds to a substring having only an end code violation in which the G constraint would be violated by two adjacent codewords having adjacent end code violations;
• and
• the second case corresponds to a substring having at least one G constraint violation within the substring;
• (c) if at least one of the left and right substrings has a code violation, then defining a first pivot bit for the left substring and a first pivot bit for the right substring, each first pivot bit adjacent to the middle pivot bit and the pair of first pivot bits indicating whether code violations exist in the left substring only, the right substring only, or both left and right substrings
• (d) if a substring has a code violation, then defining a second pivot bit for the substring, the second pivot bit indicating whether the code violation is of the first case or the second case;
• (e) if the code violation is of the first case, then setting the second pivot bit to correct the end code violation and defining and setting a first correction bit to prevent a violation of the G constraint resulting from setting the middle pivot bit and the first pivot bit of the substring;
• (f) if the code violation is of the second case, then defining and setting second correction bit to correct an end code violation and defining and setting a third correction bit to correct the violation of the G constraint within the substring;
• and
• (g) moving values of one or more elements overwritten by a pivot or correction bit to element positions corresponding to elements whose values are identified by the pivot bits as being part of a code violation, thereby generating the (N+1)-element codeword corresponding to the N-element dataword.

A method of decoding a sequence of codewords each having at least N+1 elements into a sequence of N-element datawords, the sequence of (N+1)-element codewords received as a signal from a storage or transmission media, the method comprising the steps of:

• a) detecting a middle pivot bit and first and second portions of the codeword, each portion adjacent to the middle pivot bit;
• b) generating the dataword from the first and second portions by:
• if the middle pivot bit is set to one value:
• b1) detecting a set of preserved bits for each portion and a pair of first and second pivot bits;
• b2) generating, for each portion, a substring from the set of preserved elements and, if a second pivot bit is detected in the portion, from at least one code violation defined by the second pivot bit;
• b3) combining each substring to form the dataword;
• otherwise, if the middle pivot bit is set to another value:
• b4) providing the first and second portions as the dataword.

An integrated circuit including a circuit for encoding a sequence of N-element datawords into a sequence of codewords each having N+1 elements for storage or transmission such that the sequence of codewords satisfies a G constraint, wherein the G constraint corresponds to a maximum number of elements having the same value and G being (N/4)+1, the circuit comprising:

• a storage circuit, coupled to an input stream to receive each dataword, adapted to store each dataword as left and right substrings;
• a processor, coupled to the storage circuit, which determines whether each of the left and right substrings contains at least one code violation of either a first or second case, wherein:
• the first case corresponds to a substring having only an end code violation in which the G constraint would be violated by two adjacent codewords having adjacent end code violations;
• and
• the second case corresponds to a substring having at least one G constraint violation within the substring;
• an encoder circuit, coupled to the storage register, adapted to insert a middle pivot bit between the left and right substrings and adapted to encode the dataword into the codeword,
• wherein, if at least one of the left and right substrings has a code violation, the encoder circuit encodes by defining a first pivot bit for the left substring and a first pivot bit for the right substring, each first pivot bit adjacent to the middle pivot bit and the pair of first pivot bits indicating whether code violations exist in the left substring only, the right substring only, or both left and right substrings, and if a substring has a code violation, the encoder circuit defines a second pivot bit of the substring, the second pivot bit indicating whether the code violation is of the first case or the second case;
• and wherein the encoder circuit corrects each code violation by:
• (i) if the code violation is of the first case, then setting the second pivot bit to correct the end code violation and defining and setting a first correction bit to prevent a violation of the G constraint resulting from setting the middle pivot bit and the first pivot bit of the substring;
• (ii) if the code violation is of the second case, then defining and setting second correction bit to correct an end code violation and defining and setting a third correction bit to correct the violation of the G constraint within the substring;
• and
• (iii) moving values of one or more elements overwritten by a pivot or correction bit to element positions corresponding to elements whose values are identified by the pivot bits as being part of a code violation, thereby generating the codeword corresponding to the N-element dataword.

An integrated circuit including a circuit for decoding a sequence of (N+1)-element codewords into a sequence of N-element datawords, the sequence of (N+1)-element codewords received as a signal from a storage or transmission media, the decoder comprising:

• a processor adapted to detect a middle pivot bit and first and second portions of the codeword, each portion adjacent to the middle pivot bit;
• a logic circuit, coupled to the processor, adapted to generate the dataword from the first and second portions by:
• if the middle pivot bit is set to one value:
• 1) extracting a set of preserved bits and a first pivot bit for each portion;
• 2) generating, for each portion, a substring from the set of preserved elements and, if a second pivot bit is detected in the portion, from at least one code violation defined by the second pivot bit;
• 3) combining each substring to form the dataword;
• otherwise, if the middle pivot bit is set to another value, by:
• 4) providing the first and second portions as the dataword.

A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to implement a method for encoding a sequence of N-element datawords into a sequence of (N+1)-element codewords for storage or transmission such that the sequence of codewords satisfies a G constraint, wherein the G constraint corresponds to a maximum number of elements having the same value and G being (N/4)+1, the method comprising the steps of:

• (a) dividing each dataword into left and right substrings by inserting a middle pivot bit therebetween;
• (b) determining whether each of the left and right substrings contains at least one code violation of a first or second case, wherein:
• the first case corresponds to a substring having only an end code violation in which the G constraint would be violated by two adjacent codewords having adjacent end code violations;
• and
• the second case corresponds to a substring having at least one G constraint violation within the substring;
• (c) if at least one of the left and right substrings has a code violation, then defining a first pivot bit for the left substring and a first pivot bit for the right substring, each first pivot bit adjacent to the middle pivot bit and the pair of first pivot bits indicating whether code violations exist in the left substring only, the right substring only, or both left and right substrings
• (d) if a substring has a code violation, then defining a second pivot bit for the substring, the second pivot bit indicating whether the code violation is of the first case or the second case;
• (e) if the code violation is of the first case, then setting the second pivot bit to correct the end code violation and defining and setting a first correction bit to prevent a violation of the G constraint resulting from setting the middle pivot bit and the first pivot bit of the substring;
• (f) if the code violation is of the second case, then defining and setting second correction bit to correct an end code violation and defining and setting a third correction bit to correct the violation of the G constraint within the substring;
• and
• (g) moving values of one or more elements overwritten by a pivot or correction bit to element positions corresponding to elements whose values are identified by the pivot bits as being part of a code violation, thereby generating the (N+1)-element codeword corresponding to the N-element dataword.

A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to implement a method for decoding a sequence of (N+1)-element codewords recorded on a storage media into a sequence of N-element datawords, the method comprising the steps of:

• a) detecting a middle pivot bit and first and second portions of the codeword, each portion adjacent to the middle pivot bit;
• b) generating the dataword from the first and second portions by:
• if the middle pivot bit is set to one value:
• b1) detecting a set of preserved bits and a first pivot bit for each portion;
• b2) generating, for each portion, a substring from the set of preserved elements and from the at least one code violation defined by the pair of first and second pivot bits
• b3) combining each substring to form the dataword;
• otherwise, if the middle pivot bit is set to another value:
• b4) providing the first and second portions as the dataword.