US 5,220,568 A · Shift correcting code for channel encoded data

Abstract

Channel encoded data (for example run length limited encoded data) is further encoded in accordance with a shift correction code prior to transmission. Upon reception, forward and backward shift errors present in the received channel encoded data are corrected by a shift correction decoder. The shift error correction is accomplished using a code, such as (for example) a BCH code over GF(p) or a negacyclic code, which treats each received symbol as a vector having p states. For a single shift error correction, p=3 and there are three states (forward shift, backward shift, no shift). In one embodiment, conventional error correction codewords which encode the user data may be interleaved within successive shift correction codewords prior to channel encoding, thereby enabling the error correction system to easily handle a high rate of randomly distributed shift errors (which otherwise would result in a high rate of short error bursts that exceed the capacity of the block error correction code).

Claims30

Dependent claims

A data processing system associated with a channel, comprising:

channel encoder means for transforming a stream of digital data to a stream of binary data in accordance with a run length limited code for transmission through said channel;
channel decoder means for receiving from said channel a stream of binary data encoded by said channel encoder means and transforming it to digital data in accordance with said run length limited code;
and
a shift correction encoder connected between said channel encoder means and said channel and comprising;
first means for transforming a block of binary symbols in said binary data stream to a block of symbols of a first field;
second means for transforming said block of symbols of said first field to produce a block of k elements of a finite field;
third means for computing r redundant check symbols from said k finite field elements in accordance with a first code over said finite field, wherein said k finite field elements and said r redundant check symbols comprise a first codeword comprising n=k+r symbols of said finite field;
and
fourth means for transforming said r redundant check symbols to a sequence of binary symbols in accordance with constraints of said run length limited code and transmitting them to said channel so that they are appended to said block of binary symbols in said stream of binary data, wherein said first means comprises means for sensing the number of consecutive binary zeroes between successive binary ones in said stream of channel encoded binary data, whereby said first field is a field of natural numbers.

6 more elements

A shift correction system for correcting time shift errors in run length limted (RLL) channel encoded data received from a channel, said data consisting of runs that are characterized by a run bit (such as 0) and a separation bit (such as 1), wherein such time shift errors cause as many as t separation bits in a block of said data to shift position with respect to the position of other bits in said RLL data in as many as p possible states, p being at least three (forward shift, backward shift, no shift), said system comprising:

first means for receiving a block of digital symbols which are to be run length limited channel encoded;
second means for channel encoding said block of symbols in accordance with a run length limited code to generate a block of RLL encoded data;
third means for transforming each run length in said block of RLL encoded data to an element of a Galois field related to GF(p.sup.m) so as to generate a corresponding block of GF(p.sup.m) related symbols;
fourth means for encoding said block of GF(p.sup.m) related symbols in accordance with a first code related to GF(p.sup.m) so as to generate a set of redundant check elements from GF(p.sup.m);
fifth means for channel encoding said redundant check elements into a check block of RLL encoded data, and appending said check block to said block of RLL data to from a shift correction RLL data block and transmitting said RLL data block to said channel;
sixth means for receiving run length limited encoded data from said channel as a received encoded RLL data block;
seventh means for transforming each run length in said received data block into an element of said Galois field to form a received codeword;
and
eighth means for decoding said received codeword in accordance with said first code;

6 more elements

A process for correcting shift errors in a block of run length limited (RLL) channel encoded data in a channel, wherein shift errors cause as many as t separation bits in said block of channel encoded data each to be shifted by as many as (p-1)/2 bit positions, wherein p is at least 3 (one bit forward, one bit back, no shift), said process comprising:

run length limited encoding a set of digital symbols to generate a block of RLL data, converting each run length in said RLL data block to an element of a Galois field related to GF(p.sup.m) so as to form a block of Galois field symbols;
encoding said Galois field symbol block in accordance with a first code related to GF(p.sup.m) so as to compute a set of check symbols from said Galois field;
and
RLL encoding said set of check symbols from said Galois field to produce a check block of RLL data and appending said check block to said RLL data block to form a shift correction RLL data block, and transmitting said shift correction RLL data block to said channel.

1 more element

Dependencies are inferred from the claim text.

Shift correcting code for channel encoded data

Life of this patent

Shift correcting code for channel encoded data

Life of this patent

Abstract

Claims30