Method and apparatus for constructing asymptotically optimal second order DC-free channel codes

An encoding apparatus for constructing a second order DC-free channel code from an input data sequence over a bipolar binary alphabet, and comprising:

• a) means for appending to each input vector of length m of a first input array a sign-bit so as to produce a first output array of equal length vectors of size m+1;
• b) means for balancing each vector in said first output array of vectors of size m+1 by appending r redundancy bits, so as to produce a second output array of balanced vectors each of size m+1+r;
• c) means for computing a first moment for each of the balanced vectors;
• and
• d) means for accumulating an accumulated sum of first moments of the individual balanced vectors x.sub.i of the second output array, said means for accumulating including for driving the accumulated sum in the direction of zero so as to produce a final output array which is second order DC-free.

An encoding apparatus for constructing second order DC-free channel codes from an input data sequence over a bipolar binary alphabet, and comprising:

• a) means for breaking said input sequence of bits of data into equal sized vectors so as to produce a first input array of equal length vectors of size m and means for appending to each input vector of length m of a first input array a sign-bit so as to produce a first output array of equal length vectors of size m+1;
• b) means for balancing each vector in said first output array of vectors of size m+1 so as to produce a second output array of balanced vectors each of size m+1+r where r represents the number of redundancy bits appended to each vector of said first output array;
• and
• c) means for driving an accumulated sum of first moments of the individual balanced vectors x.sub.i of the second output array in the direction of zero so as to produce a final output array which is second order DC-free comprising:
• calculating means for determining the first moments m.sub.1 (x.sub.i) of the individual balanced vectors x.sub.i ;
• summing means for accumulating a running sum m.sub.1 (m.sub.y-1) of all the first moments of all the balanced vectors;
• testing means for determining whether the addition of the first moment value m.sub.1 (x.sub.i) to the accumulated sum of first moments m.sub.1 (y.sub.i-1) drives the new total accumulated first moment value in the direction of zero;
• means for inverting the first moment value m.sub.1 (x.sub.i) before the addition of this value to the accumulated sum of first moments;
• means for adding together the calculated first moment value to the accumulated sum of first moments so as to produce a new accumulated sum of first moments;
• and
• means for inverting the bits of the input vector x.sub.i and means for toggling said sign-bit in the case wherein the bits of the input vector x.sub.i have been inverted;
• and
• d) means for producing a last balanced vector having a first moment which, when added to the accumulated sum of first moments of all the vectors in the final output array, effectively drives the accumulated sum of first moments to zero.

A method for encoding a second order DC-free array from an input data sequence over a bipolar binary alphabet comprising the steps of:

• a) appending to each input vector of length m of a first input array a sign-bit so as to produce a first output array of equal length vectors of size m+1;
• b) balancing each vector in the first output array of vectors of size m+1 so as to produce a second output array of balanced vectors each of size m+1+r where r represents the number of redundancy bits appended to each vector of the first output array;
• and
• c) driving an accumulated sum of first moments of the balanced vectors x.sub.i of the second output array in the direction of zero so as to produce a final output array which is second order DC-free.

A decoding apparatus for converting a balanced second order DC-free array to an output data sequence over a bipolar binary alphabet, comprising:

• a) means for removing a last vector from the data array;
• b) means for reversing the balancing of said data array;
• c) means for detecting and inverting those vectors in said data array which have been inverted;
• and
• c) means for removing a sign bit appended to each vector of said data array.

A digital communication system having an encoder and decoder wherein said encoder converts an input data sequence of a bipolar binary alphabet into a high-rate second order DC-free channel code for transmission and storage, and wherein said decoder converts said high-rate second order DC-free channel code back into said input data sequence upon reception and retrieval thereof, said system comprising:

• a) means for encoding an input data sequence into a high-rate second order DC-free code, said means for encoding including:
• means for dividing the input data sequence into input vectors;
• means for balancing the input vectors to produce balanced vectors x.sub.i ;
• means for computing a first moment for each of the balanced vectors x.sub.i ;
• means for accumulating an accumulated sum of the first moments;
• and means for driving the accumulated sum of the first moments of the balanced vectors x.sub.i in the direction of zero so as to produce a final output array which is second order DC-free;
• b) means for transmitting said second order DC-free channel code;
• c) means for receiving said second order DC-free channel code;
• and
• d) means for decoding said received second order DC-free channel code to reproduce said input data sequence, the means for decoding including means for removing a last vector from the received sound order DC-free channel code;
• means for detecting and inverting those vectors in said received second order DC-free channel code which have been inverted;
• means for removing a sign bit appended to each vector;
• and means for reversing a balancing of each vector.

A digital data storage and retrieval system having an encoder and decoder wherein said encoder converts an input data sequence of a bipolar binary alphabet into a high-rate second order DC-free channel code for transmission and storage, and wherein said decoder converts said high-rate second order DC-free channel code back into said input data sequence upon reception and retrieval thereof, said digital data storage and retrieval system comprising:

• a) digital data storage medium for storage of an encoded data array;
• b) means for encoding an input data sequence into a high-rate second order DC-free code, said means for encoding including
• means for dividing the input data sequence into input vectors;
• means for balancing the input vectors to produce balanced vectors x.sub.i ;
• means for computing a first moment for each of the balanced vectors x.sub.i ;
• means for accumulating an accumulated sum of the first moments;
• and means for driving the accumulated sum of the first moments of the balanced vectors x.sub.i in the direction of zero so as to produce a final output array which is second order DC-free;
• c) means for recording said second order DC-free channel code on said storage medium;
• d) means for retrieving said second order DC-free channel code from said storage medium;
• and
• d) means for decoding said second order DC-free channel code retreived by the means for retreiving to reproduce said input data sequence, said means for decoding including means for removing a last vector from the data array;
• means for detecting and inverting those vectors in said received data array which have been complemented;
• means for removing a sign bit appended to each vector;
• and
• means for reversing a balancing of each vector.