Error detection/correction and fault detection/recovery – Pulse or data error handling – Data formatting to improve error detection correction...
Reexamination Certificate
1999-06-30
2002-08-06
Moise, Emmanuel L. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Data formatting to improve error detection correction...
C341S058000, C341S059000, C341S095000, C341S106000, C360S040000, C360S048000
Reexamination Certificate
active
06430713
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to protecting magnetic recording systems from errors, and more particularly to methods and systems for constructing block encoders (and corresponding decoders) for expanding shorter p-bit datawords to longer q-bit code words.
2. Description of the Related Art
In data recording devices such as magnetic or optical disk drives and tape drives, data to be recorded is received in groups of p-bit datawords, wherein p is an integer. As is known in the art, to reduce errors in the device it can be helpful to convert (“encode”) the p-bit datawords into q-bit codewords, wherein q is an integer that is larger than p and the codewords consequently are longer than the datawords. The codewords, not the actual datawords, are then recorded. When a requesting device desires to retrieve the data, the codewords are converted back (“decoded”) to the corresponding datawords, and the datawords are then sent to the requesting device. Using this encoding and decoding provides for timing recovery and/or reduces system errors and/or alleviates the effects of system errors when they occur.
When using longer codewords for error protection as set forth above, the acceptable codewords are characterized by certain constraints. For instance, the recording system might have a constraint that forbids any word from having three consecutive 0's in its bit stream. With this constraint, for example, a 9-bit word having the bit sequence 100111001 would be acceptable as a codeword, whereas a 9-bit word having the bit sequence 100011001 would not be acceptable. Additional system constraints might also forbid, e.g., any word from having more than two consecutive 0's at the start or end of the word, and so on. Accordingly, the set of codewords must be selected to satisfy the various constraints, with those words that do not satisfy the constraints being omitted from the set. Because a block code requires 2
P
q-bit codewords, having to eliminate words that do not satisfy the constraints is not a problem, if “q” is sufficiently large: there are at least twice as many candidate codewords as datawords when q exceeds p by one, four times as many when q exceeds p by two, and so on.
Having set forth why codewords are used and the fact that they must be selected to meet certain system constraints, attention is now directed to the problem at hand, namely, mapping the datawords to corresponding codewords. It is important that the mapping be implementable with reasonable complexity in terms of logic gates and storage area required for the encoder. Finding such a mapping is non-trivial even in a relatively simple case where, e.g., 4-bit datawords are to be mapped to 5-bit codewords with the constraint that the bit stream never has three consecutive zeroes. In this simple example, there are 17 factorial (about 10
14
) candidate mappings. A bad mapping can result in an encoder that is unduly complex in terms of logic gates and storage area required for the encoder.
Owing to the enormous number of possible mappings for most encoding scenarios, it is not practical to wade through each and every candidate mapping to determine which one is best. Instead, data-to-codeword mappings currently are constructed empirically by hand, to yield a “good” mapping in terms of encoder complexity as measured by accepted test protocols in the art. This is very time-consuming and burdensome, but nevertheless necessary to provide low-complexity coders from both a storage area consumption and energy consumption standpoint. The present invention understands that while it might not be practical to find the “best” codeword-dataword mapping for any given combination of constraints, it is nevertheless possible to provide an automated system to find a “good” mapping.
SUMMARY OF THE INVENTION
A computer system includes a general purpose computer and a program of instructions that is accessible by the computer to undertake method acts to map p-bit datawords to q-bit codewords. The method acts undertaken by the computer include receiving an input set of q-bit candidate codewords, and using the input set of codewords to establish plural simple subsets of codewords, as “simple” is defined below. Also, the method acts include associating the subsets with respective p-bit datawords, and then mapping codewords to datawords using the subsets. In a preferred embodiment, the mapping act includes establishing at least some bit values of the datawords based on bit values of the codewords. The method constructs the decoder and then defines the encoder to be the inverse of the decoder.
As disclosed in greater detail below, the preferred method for constructing the decoder includes filling an index set I
p
with codewords from the input set, and then removing fixed coordinates and dependent coordinates from the index set I
p
. Next, it is determined whether the input set is a simple set, using the index set I
p
. When the input set is not a simple set, the input set is divided into at least two subsets. The act of dividing the input set is executed by determining a most constrained coordinate, and establishing a first subset containing all codewords having a zero binary value in the most constrained coordinate and a second subset containing all codewords having a binary value of one in the most constrained coordinate.
In accordance with the present invention, after decomposing the codewords into simple subsets, the codewords and datawords can be arranged in respective C and D matrices, and the mapping act includes designating free coordinates in datawords as unfilled and free coordinates in codewords as unused. A free coordinate is a coordinate other than a fixed or dependent coordinate, as defined below. A column j* of the D matrix that has a largest number of unfilled coordinates is identified, and for each j, 0≦j≦q−1, a number d
j
of rows of the D matrix is determined in which the coordinate j* has been previously filled with the free coordinate j. Additionally, for each j, a number e
j
of rows of the C matrix is determined for which the coordinate j is unused and the corresponding row of the D matrix is unfilled in coordinate j*. A coordinate j† is then defined to be the value of j that results in the maximum value of the sum of d
j
and e
j
. For every row of the D matrix wherein the coordinate j* is unfilled and the coordinate j† is unused in the corresponding row of the C matrix, the value of the coordinate j† in the C matrix is assigned to the coordinate j* in the D matrix. The mapping act is recursively iterated until all coordinates of the D matrix have been filled. The system is also disclosed in combination with a data recording device.
In another aspect, a computer program device includes a computer program storage device that is readable by a digital processing apparatus. A program is on the program storage device, and the program includes instructions that can be executed by the digital processing apparatus for mapping a set of datawords to a set of codewords. The instructions include decomposing the set of codewords into subsets using a most constrained coordinate, and decomposing the set of datawords into subsets corresponding to the subsets of codewords. Also, the instructions include filling selected coordinates in the datawords with selected coordinates from the codewords.
In still another aspect, a computer-implemented method is disclosed for mapping datawords to codewords for recording of the codewords onto a storage medium. The method includes receiving a set of q-bit codewords and decomposing the set of codewords into subsets of codewords containing at least some fixed coordinates and at least some free coordinates. Moreover, for each subset of codewords, a respective subset of datawords is provided that contains at least some fixed coordinates and at least some free coordinates. The free coordinates in the subsets of datawords are filled with binary values from free coordinates in the subsets of codewords. In this manner, the decoder
Marcus Brian Harry
Modha Dharmendra Shantilal
International Business Machines - Corporation
Moise Emmanuel L.
Rogitz John L.
LandOfFree
System and method for constructing low complexity block coders does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for constructing low complexity block coders, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for constructing low complexity block coders will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2882877