M=10 (2,10), D=3.75 runlength limited code for multi-level data

Claims

What is claimed is:

1. A method for encoding a series of binary input data bits x into an M=10 run-length limited (2,10) code having a rate R=5/4, to produce a series of code symbols y, the method comprising the steps of:

receiving at a seven-state encoder an input data bit set x.sub.0 -x.sub.4 to be encoded into the M=10 run-length limited (2,10) code; and

generating in said encoder a code symbol set y.sub.0 -y.sub.3 based on said input data bit set x.sub.0 -x.sub.4 according to the following table:

wherein said code symbol set y.sub.0 -y.sub.3 is generated based on the input data bit set x.sub.0 -x.sub.4 and the current state of said seven-state encoder when said data bit set x.sub.0 -x.sub.4 is received.

2. The method of claim 1, further comprising the step of:

modulating a signal with waveform signal amplitudes to transmit a series of features across the channel, each feature being at a level corresponding to one of said waveform signal amplitudes; and

wherein said generating step comprises the steps of:

encoding the binary input data bits into an M=10 (2,10) code having a rate R=5/4 to produce a series of code symbols, each code symbol being at one of M levels, and each pair of non-zero code symbols having a minimum of two and a maximum of ten zeroes therebetween, said encoding step comprising the step of generating a code symbol set y.sub.0 -y.sub.3 for each input data bit set x.sub.0 -x.sub.4 according to the following table:

wherein said code symbol set y.sub.0 -y.sub.3 is generated based on the input data bit set x.sub.0 -x.sub.4 and the current state of said seven-state encoder when said data bit set x.sub.0 -x.sub.4 is received; and

generating in a waveform encoder waveform signal amplitudes based on said code symbols, wherein each said waveform signal amplitude is generated by modulo ten addition of a current code symbol with a previous waveform signal amplitude.

3. A method for converting binary input data bits into a series of waveform amplitudes, each amplitude being at one of M=10 levels, the method comprising the steps of:

encoding the binary input data bits into an M=10 (2,10) code having a rate R=5/4 to produce a series of code symbols, each code symbol being at one of M levels, and each pair of non-zero code symbols having a minimum of two and a maximum of ten zeroes therebetween, said encoding step comprising the step of generating a code symbol set y.sub.0 -y.sub.3 for each input data bit set x.sub.0 -x.sub.4 according to the following table:

wherein said code symbol set y.sub.0 -y.sub.3 is generated based on the input data bit set x.sub.0 -x.sub.4 and the current state of said seven-state encoder when said data bit set x.sub.0 -x.sub.4 is received; and

generating in a waveform encoder waveform signal amplitudes based on said code symbols, wherein each said waveform signal amplitude is generated by modulo ten addition of a current code symbol with a previous waveform signal amplitude.

4. The method of claim 3, further comprising the step of

modulating a signal with said waveform signal amplitudes to generate a series of features, each feature being at a level corresponding to a waveform signal amplitude; and

wherein said waveform signal amplitudes modulate a write laser and wherein said modulated write laser writes said features onto a storage medium.

5. The method of claim 4, further comprising the steps of:

receiving said features to recover output waveform signal amplitudes;

converting said output waveform signal amplitudes into output code symbols, wherein each output code symbol is at one of ten levels; and

decoding said output code symbols to obtain output data bits, wherein said output data bits correspond to the binary input data.

6. The method of claim 5, wherein said step of decoding comprises the steps of:

identifying with a sliding window a sequence of code symbols that represents a given code symbol set; and

in a table comprising a number of entries corresponding to a number of possible unique sequences of code symbols, each entry identified by one of said possible unique sequences of code symbols, and wherein each entry identifies an output data bit set that is a decoded data bit set for the code symbol set represented by the sequence of code symbols that identifies that entry, looking up with said identified sequence of code symbols the output data bit set for said given code symbol set.

7. The method of claim 6, wherein said lookup table provides an output bit set x' for each sequence of code symbols y' according to the following table:

8. The method of claim 6, wherein said look-up step comprises the step of determining, using a squared euclidean distance, which table entry is identified by a sequence of code symbols.

9. The method of claim 3, further comprising the step of

modulating a signal with said waveform signal amplitudes to generate a series of features, each feature being at a level corresponding to a waveform signal amplitude; and

wherein said waveform signal amplitudes modulate a transmitter and wherein said transmitter transmits said features over a communications channel.

10. A method for decoding data on a channel, wherein said data has been encoded using an M=10 (2,10) code, comprising the steps of:

reading the data to recover output waveform signal amplitudes;

converting said output waveform signal amplitudes into output code symbols, wherein each output code symbol is at one of ten levels; and

decoding said output code symbols to obtain output data bits, wherein said output data bits correspond to the encoded data.

11. The method of claim 10, wherein said decoding step comprises the steps of:

identifying with a sliding window a sequence of code symbols that represents a given code symbol set; and

in a table comprising a number of entries corresponding to a number of possible unique sequences of code symbols, each entry identified by one of said possible unique sequences of code symbols, and wherein each entry identifies an output data bit set that is a decoded data bit set for the code symbol set represented by the sequence of code symbols that identifies that entry, looking up with said identified sequence of code symbols the output data bit set for said given code symbol set.

12. The method of claim 11, wherein said table provides an output bit set x' for each sequence of code symbols y' according to the following table:

13. The method of claim 10, wherein said channel is a storage medium or a communications channel.

14. A system for encoding a series of binary input data bits x into an M=10 run-length limited (2,10) code having a rate R=5/4, to produce a series of code symbols y, the system comprising:

means for receiving at a seven-state encoder an input data bit set x.sub.0 -x.sub.4 to be encoded into the M=10 run-length limited (2,10) code; and

means for generating in said encoder a code symbol set y.sub.0 -y.sub.3 based on said input data bit set x.sub.0 -x.sub.4 according to the following table:

wherein said code symbol set y.sub.0 -y.sub.3 is generated based on the input data bit set x.sub.0 -x.sub.4 and the current state of said seven-state encoder when said data bit set x.sub.0 -x.sub.4 is received.

15. A system for converting binary input data bits into a series of waveform amplitudes, each amplitude being at one of M=10 levels, the system comprising:

means for encoding the binary input data bits into an M=10 (2,10) code having a rate R=5/4 to produce a series of code symbols, each code symbol being at one of M levels, and each pair of non-zero code symbols having a minimum of two and a maximum of ten zeroes therebetween, said means for encoding comprising means for generating a code symbol set y.sub.0 -y.sub.3 for each input data bit set x.sub.0 -x.sub.4 according to the following table:

wherein said code symbol set y.sub.0 -y.sub.3 is generated based on the input data bit set x.sub.0 -x.sub.4 and the current state of said seven-state encoder when said data bit set x.sub.0 -x.sub.4 is received; and

means for generating in a waveform encoder waveform signal amplitudes based on said code symbols, wherein each said waveform signal amplitude is generated by modulo ten addition of a current code symbol with a previous waveform signal amplitude.

16. The system of claim 15, further comprising

means for modulating a signal with said waveform signal amplitudes to generate a series of features, each feature being at a level corresponding to a waveform signal amplitude; and

wherein said waveform signal amplitudes modulate a write laser and wherein said modulated write laser writes said features onto a storage medium.

17. The system of claim 16, further comprising:

means for receiving said features to recover output waveform signal amplitudes;

means for converting said output waveform signal amplitudes into output code symbols, wherein each output code symbol is at one of ten levels; and

means for decoding said output code symbols to obtain output data bits, wherein said output data bits correspond to the binary input data.

18. The system of claim 17, wherein said means for decoding comprises:

means for identifying with a sliding window a sequence of code symbols that represents a given code symbol set; and

means for, in a table comprising a number of entries corresponding to a number of possible unique sequences of code symbols, each entry identified by one of said possible unique sequences of code symbols, and wherein each entry identifies an output data bit set that is a decoded data bit set for the code symbol set represented by the sequence of code symbols that identifies that entry, looking up with said identified sequence of code symbols the output data bit set for said given code symbol set.

19. The system of claim 18, wherein said lookup table provides an output bit set x' for each sequence of code symbols y' according to the following table:

20. The system of claim 18, wherein said means for looking up comprises means for determining, using a squared euclidean distance, which table entry is identified by a sequence of code symbols.

21. The system of claim 15, further comprising

means for modulating a signal with said waveform signal amplitudes to generate a series of features, each feature being at a level corresponding to a waveform signal amplitude; and

wherein said waveform signal amplitudes modulate a transmitter and wherein said transmitter transmits said features over a communications channel.

22. A system for decoding data on a channel, wherein said data has been encoded using an M=10 (2,10) code, comprising:

means for reading the data to recover output waveform signal amplitudes;

means for converting said output waveform signal amplitudes into output code symbols, wherein each output code symbol is at one of ten levels; and

means for decoding said output code symbols to obtain output data bits, wherein said output data bits correspond to the encoded data.

23. The system of claim 22, wherein said means for decoding comprises:

means for identifying with a sliding window a sequence of code symbols that represents a given code symbol set; and

means for, in a table comprising a number of entries corresponding to a number of possible unique sequences of code symbols, each entry identified by one of said possible unique sequences of code symbols, and wherein each entry identifies an output data bit set that is a decoded data bit set for the code symbol set represented by the sequence of code symbols that identifies that entry, looking up with said identified sequence of code symbols the output data bit set for said given code symbol set.

24. The system of claim 23, wherein said table provides an output bit set x' for each sequence of code symbols y' according to the following table:

25. The system of claim 22, wherein said channel is a storage medium or a communications channel.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to multi-level coding techniques, and more specifically to a system and method for coding data using an M=10 (2,10) runlength limited code, such code being particularly useful for storing and/or transmitting multi-level data.

2. Related Art

Various techniques are currently in use for increasing the recording density on various digital recording mediums such as magnetic tapes and disks and in other similar media. One technique utilizes an approach known as run-length-limited coding. This technique requires that each "1" in a coded bit sequence must be separated by a specified number of "0's." This number of zeros must be at least a minimum quantity, d, to reduce intersymbol interference, and is limited to a maximum quantity k for self clocking purposes. Such codes are generally referred to as (d,k) run-length-limited (RLL) codes.

Because conventional recording techniques use saturation recording to store information, binary recording techniques are often used to mark the recording medium. As a result, conventional (d,k) RLL codes developed to date are developed and optimized to store binary data.

Significant advances in data storage materials have lead to the development of a storage medium that provides a linear response characteristic. One such material providing a linear response characteristic is an electron trapping material such as is disclosed in U.S. Pat. Nos. 4,864,536, 5,007,037, and 5,142,493, all to Lindmayer.

Using a material which provides a linear response characteristic yields an advantage over saturation-type media in that it adds an analog dimension to the storage capacity of the medium. Because the response is linear, the linear-response storage materials provide the ability to encode information in two dimensions--amplitude and phase.

As a result, the storage medium is no longer confined to storing binary or even tri-level data. Instead, the concept of M-ary, or non-binary, data coding and storage is provided. The increased symbol set allowed by such encoding provides the opportunity to dramatically increase the data recording density and transfer rate of the storage device. For example, the potential storage capacity of a single 51/4 inch disk can be extended to several gigabytes if that disk is implemented using electron trapping materials with M-ary (multi-level) data coding.

SUMMARY OF THE INVENTION

The present invention is directed toward an M=10 (2,10) runlength-limited code for multi-level data storage and/or communications. Also disclosed herein is a system and method for generating multi-level data from a binary input data stream using an M-ary (d,k) code such as the M=10 (2,10) runlength limited code.

According to the invention input data bits are coded using an M-ary (d,k) encoder to generate code symbols. Specifically, input data bits x are encoded using the M-ary (d,k) encoder to generate code symbols y, where:

for p input date bits, and

where p/q is the code rate R.

The code symbols y are multi-level symbols, each being at one of M levels. The code symbol stream provided meets the code specifications of no fewer than d and no greater than k zeros between each non-zero symbol. Thus, according to the M=10 (2,10) code disclosed herein, code symbols are each at one of ten levels and there is a minimum of two and a maximum of ten zeros between each non-zero symbol.

The code symbols y are encoded to generate a series of waveform amplitudes z. The waveform amplitudes are generated by modulo M addition of the current code symbol y.sub.i with the previous waveform amplitude z.sub.i-1. The waveform amplitudes are used to modulate a write laser to store information onto an optical disk or to otherwise store or communicate the input data bits x in the form of multi-level information.

To recover the original data bits x from the medium, the information stored on the medium is read and the resultant signal amplitudes are decoded. Two stages of decoding are provided. In the first stage, the waveform amplitudes are decoded to generate code symbols. In the second stage, the code symbols are decoded to recover the original data bits.

The system and method described herein for coding and decoding the data is described with respect to the M=10 (2,10) code disclosed herein. However, while other codes may not be obvious in light of the code disclosed herein, given a specific M-ary (d,k) code, after reading the below disclosure, it will become apparent to a person skilled in the relevant art how the disclosed system and method can be implemented to code and decode the data using such a specific M-ary (d,k) code.

An advantage of the invention is that the recording density can be increased by coding the input data using the disclosed M=10 (2,10) code. Because there are at least d zeros between every non-zero code symbol, there can be at least d+1 symbols stored for a given minimum feature size. Given a code of rate R, the density achievable is (d+1)R.

It should be noted that the coding techniques described herein are not limited to optical recording. Other recording systems capable of supporting multi-level data would benefit from the coding techniques described herein. Additionally, these coding techniques are also applicable to communications systems where the communications channel is capable of supporting multi-level data. In such an implementation, the waveform amplitudes could be used to modulate a signal carrier for transmission across the multi-level channel.

Further features and advantages of the present invention, as well as the structure and operation of various embodiments of the present invention, are described in detail below with reference to the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention is described with reference to the accompanying drawings. In the drawings, like reference numbers indicate identical or functionally similar elements. Additionally, the left-most digit of a reference number identifies the drawing in which the reference number first appears.

FIG. 1 is a diagram illustrating a portion of an optical storage medium and features thereon.

FIG. 2 is a diagram illustrating a data storage system for storing a multi-level coded data.

FIG. 3 is a diagram illustrating an encoder for encoding multi-level data using a multi-level (d,k) code.

FIG. 4 is a flow diagram illustrating the operation of a multi-state encoder.

FIG. 5 is a diagram illustrating an example input data stream being coded using the encoder illustrated in FIG. 4.

FIG. 6 is a diagram illustrating a decoder for decoding multi-level (d,k) coded data.

FIG. 7 is a diagram illustrating a sliding block decoder.

FIG. 8 is a diagram illustrating encoder shut-down.

DETAILED DESCRIPTION OF THE EMBODIMENTS

1. Introduction

The present invention is directed toward an M-ary (d,k) code for use in storage and/or transmission of multi-level data, and a system and method for generating the same. This discussion is provided in several sections. In Section 2, before discussing the invention in detail, a brief discussion of binary (d,k) codes is presented. In Section 3, a coding system for coding input data using an M-ary (d,k) code is described. In Section 4, some code design factors are described. In Section 5, a specific M=10 (2,10) code is described that is particularly useful for storage and/or transmission of multi-level data. Section 5 also provides a detailed description of the encoder used to code data using the disclosed M=10 (2,10) code. In Section 6 there is presented a discussion of a sliding block decoder generally useful for decoding M-ary (d,k) codes, as well as a specific decoder for decoding the M=10 (2,10) code described in Section 5.

The present invention is generally described in terms of an embodiment where multi-level data are stored on and retrieved from an optical disk. In such an embodiment, the encoder and decoder described herein may be implemented for multi-level data storage in an optical disk system such as that disclosed in U.S. Pat. No. 5,007,037, which is incorporated herein by reference. However, after reading the below description, it will become apparent to a person skilled in the relevant art how the systems and methods of the invention can be implemented for alternative applications such as multi-level data communications and storage of multi-level data on media other than optical disks. In yet other alternative embodiments, the invention can be implemented to transmit and receive data across an M-ary communications channel. In this document, the term "channel" is sometimes used to refer to the optical disk. It should be understood that in the alternative embodiments the term channel can be used to describe alternative storage media and/or communications channels.

Additionally, after reading the below detailed description of the encoder and decoder of the present invention, it will become apparent to a person skilled in the art that these disclosed components can be implemented using hardware, software or a combination of both hardware and software.

2. Binary (d,k) Run-Length-Limited Coding

Using conventional binary storage techniques, data are written to a storage medium using binary 1's and 0's. Using run-length limited coding, the data to be recorded are first encoded using a run-length-limited encoder. As stated above, with a (d,k) RLL code, there is a minimum and a maximum number of 0's that can occur between each pair of 1's, as specified by the code parameters d and k. Thus, the (d,k) RLL encoder results in a 1 followed by at least d and at most k 0's before another 1 occurs. Such (d,k) RLL codes for binary applications are well known in the art.

To write input data to the saturation storage medium, the input data are first encoded to create symbols. The encoder is designed such that the output symbols conform to the code specifications: each 1 is followed by a minimum of d and a maximum of k 0's. These symbols are then written to the storage medium as a series of features. For example, for optical disks, a feature is the presence or absence of a bum mark. In a magnetic tape, the feature is a grouping of magnetic particles oriented in a particular manner.

FIG. 1 illustrates a portion of an optical storage medium 108 t