Run-length limited (RLL) 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 (d,k) 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 (runs) 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 (preventing bit slip), 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 (2,7) RLL and (1,7) 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 (NRZI), 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. (Note: older hard disks used one fixed length of time as the data window over the whole disk, but modern disks are more complicated; for more on this, see zoned bit recording.) 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 (one nanosecond, or one billionth of a second). 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 (FM) and modified frequency modulation (MFM), 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 (2,7) 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 (i.e. variants more complex than those that had received their own proper names, such as MFM). RLL codes have found almost universal application in optical-disc recording practice since 1980. In consumer electronics, RLLs like the EFM code (rate = 8/17, d = 2, k = 10) are employed in the Compact Disc (CD) and MiniDisc (MD), and the EFMPlus code (rate = 8/16, d = 2, k = 10) 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.
… excerpt ends here. Continue reading the full article.
