Run-length limited


Run-length limited is a line coding technique that is used to send arbitrary data over a communications channel with bandwidth limits. RLL is used in both telecommunication and storage systems that move a medium past a fixed recording head.
Different run-length limited codes are often distinguished with the parametrized nomenclature RLL, but they are actually defined by four main parameters: m, n, d, k. The first two, m/''n, refer to the rate of the code, while the remaining two specify the minimal d'' and maximal k number of zeroes between consecutive ones. Specifically, RLL bounds the length of stretches of repeated bits during which the signal does not change. If the runs are too long, clock recovery is difficult; if they are too short, the high frequencies might be attenuated by the communications channel. By modulating the data, RLL reduces the timing uncertainty in decoding the stored data, which would lead to the possible erroneous insertion or removal of bits when reading the data back. This mechanism ensures that the boundaries between bits can always be accurately found, while efficiently using the media to reliably store the maximal amount of data in a given space.
Degenerate RLL encoding schemes, such as FM and MFM code, which were widely used in hard disk drives until the mid-1980s. Higher-density RLL and RLL codes became the de facto industry standard for hard disks by the early 1990s. Higher order RLL codes are still used in digital optical discs such as CD, DVD, MD, Hi-MD and Blu-ray.

Need for RLL coding

On a hard disk drive, information is represented by changes in the direction of the magnetic field on the disk, and on magnetic media, the playback output is proportional to the density of flux transition. In a computer, information is represented by the voltage on a wire. No voltage on the wire in relation to a defined ground level would be a binary zero, and a positive voltage on the wire in relation to ground represents a binary one. Magnetic media, on the other hand, always carries a magnetic flux either a "north" pole or a "south" pole. In order to convert the magnetic fields to binary data, some encoding method must be used to translate between the two.
One of the simplest practical codes, modified non-return-to-zero-inverted, simply encodes a 1 as a magnetic polarity transition, also known as a "flux reversal", and a zero as no transition. With the disk spinning at a constant rate, each bit is given an equal time period, a "data window", for the magnetic signal that represents that bit, and the flux reversal, if any, occurs at the start of this window.
This method is not quite that simple, as the playback output is proportional to the density of ones, a long run of zeros means no playback output at all.
In a simple example, consider the binary pattern 101 with a data window of 1 ns. This will be stored on the disk as a change, followed by no change, and then another change. If the preceding magnetic polarity was already positive, the resulting pattern might look like this: −−+. A value of 255, or all binary ones, would be written as −+−+−+−+ or +−+−+−+−. A zero byte would be written as ++++++++ or −−−−−−−−. A 512-byte sector of zeros would be written as 4096 sequential bits with the same polarity.
Since a disk drive is a physical piece of hardware, the rotational speed of the drive can change slightly, due to a change in the motor speed or thermal expansion of the disk platter. The physical media on a floppy disk can also become deformed, causing larger timing errors, and the timing circuit on the controller itself may have small variations in speed. The problem is that, with a long string of zeros, there's no way for the disk drive's controller to know the exact position of the read head, and thus no way to know exactly how many zeros there are. A speed variation of even 0.1%, which is more precise than any practical floppy drive, could result in 4 bits being added to or removed from the 4096-bit data stream. Without some form of synchronization and error correction, the data would become completely unusable.
The other problem is due to the limits of magnetic media itself: it is only possible to write so many polarity changes in a certain amount of space, so there's an upper limit to how many ones can also be written sequentially, this depends on the linear velocity and the head gap.
To prevent this problem, data is coded in such a way that long repetitions of a single binary value do not occur. By limiting the number of zeros written consecutively to some maximum k, this makes it possible for the drive controller to stay synchronized. By limiting the number of zeros written in a row to some minimum d between each and every one, the overall frequency of polarity changes is reduced, allowing the drive to store more data in the same amount of space, resulting in either a smaller package for the same amount of data or more storage in the same size package.

History

The name "RLL" is commonly used only for the more complex variants but the early methods of recording to magnetic disks, frequency modulation and modified frequency modulation, are actually degenerate RLL variants as they limited the length of transition-free runs.
Outside of these simple versions, the first RLL code used in hard drives was RLL, developed by IBM engineers and first used commercially in 1979 on the IBM 3370 DASD, for use with the 4300 series mainframe. During the late 1980s, PC hard disks began using RLL proper. RLL codes have found almost universal application in optical-disc recording practice since 1980. In consumer electronics, RLLs like the EFM code are employed in the Compact Disc and MiniDisc, and the EFMPlus code used in the DVD. Parameters d and k are the minimal and maximal allowed run lengths. For more coverage on the storage technologies, the references cited in this article are useful.

Technical overview

Generally run length is the number of bits for which signal remains unchanged. A run length of 3 for bit 1, represents a sequence 111. For instance, the pattern of magnetic polarizations on the disk might be +−−−−++−−−++++++, with runs of length 1, 4, 2, 3, and 6. However, run-length limited coding terminology assumes NRZI encoding, so 1 bits indicate changes and 0 bits indicate the absence of change, the above sequence would be expressed as 11000101001000001, and only runs of zero bits are counted.
Somewhat confusingly, the run length is the number of zeros between adjacent ones, which is one less than the number of bit times the signal actually remains unchanged. Run-length limited sequences are characterized by two parameters, d and k, which stipulate the minimal and maximal zero-bit run length that can occur in the sequence. So RLL codes are generally specified as RLL, e.g.: RLL.

Coding

In the encoded format a "1" bit indicates a flux transition, while a "0" indicates that the magnetic field on the disk does not change for that time interval.

FM: (0,1) RLL

Generally, the term "RLL code" is used to refer to more elaborate encodings, but the original Frequency Modulation code, also called differential Manchester encoding, can be seen as a degenerate rate-1/2 RLL code.
The added 1 bits are referred to as clock bits.
Example:
Data: 0 0 1 0 1 1 0 1 0 0 0 1 1 0
Encoded: 1010111011111011101010111110
Clock: 1 1 1 1 1 1 1 1 1 1 1 1 1 1

GCR: (0,2) RLL

By extending the maximal run length to 2 adjacent 0 bits, the data rate can be improved to 4/5. This is the original IBM group coded recording variant.

Where possible, the bit pattern abcd is encoded by prefixing it with the complement of a: abcd. In the 5 cases where this would violate one of the rules, a code beginning with 11 is substituted.
Example:
Data: 0010 1101 0001 1000
Encoded: 10010011011101111010
Note that to meet the definition of RLL, it is not sufficient only that each 5-bit code contain no more than two consecutive zeros, but it is also necessary that any pair of 5-bit codes as a combined sequentially not contain more than two consecutive zeros. That is, there must not be more than two zeros between the last one bit in the first code and the first one bit in the second code, for any two arbitrarily chosen codes. This is required because for any RLL code, the run-length limits 0 and 2 in this case apply to the overall modulated bitstream, not just to the components of it that represent discrete sequences of plain data bits. The IBM GCR code above meets this condition, since the maximal run length of zeros at the beginning of any 5-bit code is one, and likewise the maximal run length at the end of any code is one, making a total run length of two at the junction between adjacent codes.

MFM: (1,3) RLL

Modified frequency modulation begins to get interesting, because its special properties allow its bits to be written to a magnetic medium with twice the density of an arbitrary bit stream. There is a limit to how close in time flux transitions can be for reading equipment to detect them, and that constrains how closely bits can be recorded on the medium: In the worst case, with an arbitrary bit stream, there are two consecutive ones, which produces two consecutive flux transitions in time, so bits must be spaced far enough apart that there would be sufficient time between those flux transitions for the reader to detect them. But this code imposes a constraint of d = 1, i.e. there is a minimum of one zero between each two ones. This means that in the worst case, flux transitions are two bit times apart, so the bits can be twice as close together as with the arbitrary bit stream without exceeding the reader's capabilities.
This doubled recording density compensates for the 1/2 coding rate of this code and makes it equivalent to a rate-1 code.
The encoding is very similar to the FM encoding.
Where "x" is the complement of the stream's previously encoded bit.
Except for the clock bits not always being one, this is the same as the FM table, and that is how this code gets its name. The inserted clock bits are 0 except between two 0 data bits.
When combined with the previous n-1 bit, the resulting encoding table for each data bit n effectively becomes.
Data Data Encoded
0010
0100
1001
1101

Example:
Data: 0 0 1 0 1 1 0 1 0 0 0 1 1 0
Encoded: x010010001010001001010010100
Clock: x 1 0 0 0 0 0 0 0 1 1 0 0 0