Two-dimensional DC-free encoder and decoder

Details Two-dimensional DC-free encoder and decoder Two-dimensional DC-free encoder and decoder

1999-07-24

2001-01-16

Tokar, Michael (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from minimum d.c. level codes

C341S094000

Reexamination Certificate

active

06175317

ABSTRACT:

BACKGROUND OF THE INVENTION
The invention relates to data storage. More specifically, the invention relates to modulation encoding of data prior to storage on a recordable medium.
In magnetic and optical memory devices, sectors of user data are typically encoded prior to storage on recordable media. The sectors are arranged into blocks, and the blocks of user data are encoded for forward error correction. Redundancy data such as error correction codewords are added to the user data, thereby forming Error Correction Codeword (“ECC”) blocks. The redundancy data allows for forward error correction of user data that, after retrieval, has been found to contain errors (for example, due to an error on the storage medium).
The ECC blocks are then modulation encoded. During modulation encoding, slices of bits (hereinafter referred to as “messages”) of the blocks are mapped into distinct symbols. For instance, 8-bit messages might be mapped into distinct 16-bit symbols or codewords. One popular modulation code is a “(2,10)-Run Length Limited” code.
Blocks of these codewords are then written to a storage medium. In the case of a hard drive, the codewords are typically arranged on a platter in concentric tracks. In the case of an optical disc such as a CD or DVD, the data is stored in a spiral groove in a substrate (and perhaps on lands too). In both cases, the data storage is one-dimensional.
Recent proposals for the design of optical storage-in particular holographic memory design-have attempted to take advantage of the fact that the recording surface of the media is actually two-dimensional. Storing data in two dimensions instead of one dimension would allow recording density to be increased.
Adding the additional dimension to encoding, however, introduces new types of constraints on the recorded data. Experiments reported on holographic memory, and experience gathered in other existing optical devices, suggest that the number of 0's and 1's in the recorded data should be balanced within certain areas or patterns. If data is recorded in two-dimensional n×m rectangular arrays (that is, arrays having n rows and m columns), one constraint of potential interest requires that every row and column of the recorded array be balanced. A row or column or, more generally, a vector having 0,1 entries is balanced if it has the same number of 0's and 1's. Such arrays shall be referred to as balanced arrays. Thus, the problem becomes one of encoding unconstrained (binary) messages into distinct n×m balanced arrays of recorded data.
Lowering the redundancy of the encoding algorithm makes it more efficient since it can represent a greater number of messages using a given array size, and hence a given area on the storage medium. A two-dimensional encoding algorithm for balanced arrays has been proposed in a paper by R. Talyansky, T. Etzion and R. M. Roth in “Efficient code constructions for certain two-dimensional constraints,” IEEE Trans. Inform. Theory, 45 (1999), pp. 794-99.
An encoding algorithm that achieves a smaller redundancy would be desirable. Reducing the redundancy would allow a greater number of messages to be packed into n×m balanced arrays. This, in turn, would allow more data to be placed on the tracks. Reducing the redundancy would also allow tracks to be spaced closer together. Thus, reducing the redundancy in two dimensions would allow storage density to be increased.
SUMMARY OF THE INVENTION
A message is encoded into a corresponding constrained array, which is an element of a set of distinct constrained arrays. A column-wise method of encoding a message into a corresponding array of the constrained array set may be performed by (a) considering a predetermined ordering of candidates for a j
th
column of the corresponding array, where j is a positive integer; (b) for each candidate being considered, computing a lower bound on the number of constrained arrays having that candidate as the j
th
column and any previously selected columns of the corresponding array as the first j−1 columns; (c) determining an index range for each candidate being considered, upper and lower limits of each index range being based upon the lower bounds of the candidates being considered; (d) determining the range in which an intermediate message lies; and (e) selecting the candidate corresponding to the determined range as the j
th
column of the corresponding array.
In the alternative, a bit-wise method of encoding a message into a corresponding array of the constrained array set may be performed by (a) determining a lower bound on the number of constrained arrays with a 0 as the k
th
bit of the j
th
column and the first k-1 bits of the j
th
column and first j−1 columns being equal to previously selected entries of the corresponding array; and (b) setting the value of the k
th
bit of the corresponding array depending upon the value of the lower bound relative to an intermediate message. Steps (a) and (b) are performed for each bit in the corresponding array.
Such encoding of messages into constrained arrays achieves a lower redundancy than encoding according to the algorithm mentioned above in the Roth et al. paper. The reduction of redundancy allows storage density to be increased.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.


REFERENCES:
patent: 5450440 (1995-09-01), Siegel et al.
patent: 5929794 (1999-07-01), Hayakawa et al.
Ronald M. Roth et al., “Efficient code construction for certain two-dimensional constraints”, Proc. IEEE Int'l Symp. Inform. Theory, Ulm, Germany (Jun. 1999), p. 387.
Kees A. Schouhamer Immink, “A practical method for approaching the channel capacity of constrained chanels”, IEEE Transactions on Information Theory, vol. 43, No. 5, Sep. 1997.

Affiliated with

Also associated with

Rating

Two-dimensional DC-free encoder and decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Two-dimensional DC-free encoder and decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two-dimensional DC-free encoder and decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2519168