What is Run Length Limited (RLL)? (Explained)

What is Run Length Limited (RLL)?

Run Length Limited, or RLL, refers to data encoding schemes on magnetic disks that can pack double the amount of data than Modified Frequency Modulation or MFM. In simple words, it is a method of storing data on a computer hard drive.

Technically, this refers to the process that involves the mapping of groups of bits to a particular flux pattern on the hard disk drives for transition. Here, the transition is adequately close to allow consistent clock recovery.

KEY TAKEAWAYS

• Run Length Limited is one of the most popular coding schemes invented by IBM and was used in mainframe disk drives in the late 1980s. Later on, hard disks on personal computers also started using RLL.
• RLL is the process for storing data on a hard drive in a much more efficient way. It allows saving and makes maximum utilization of the space available on the drives by uniting the repetitive bits in a code system before storing.
• This specific type of data encoding process depends on the resolution of the disks as well as the frequency response of head, with its implementation varying on the maximum and minimum number of transition cells.
• Run Length Limited encoding works on the lossless compression and decompression principle of the data of a code sequence by storing the repeated blocks on the hard drive as a single data value.
• RLL eliminates the chances of losing synchronization of the reading device with the bit periods. It also prevents corruption of data by using an exclusive line coding scheme and reducing the number of bits.

Understanding Run Length Limited (RLL)

Run length limited is a data encoding process which is used on magnetic disks to store information in the best way possible so that minimum space is required for it.

The more advanced version of Run Length Limited is called the Advanced Run Length Limited or ARLL.

The RLL process can store data on different types of magnetic drives such as:

• The traditional Hard Disk Drives (HDDs)
• The floppy disks, which are used rarely now
• The Compact Disks (CDs)
• The Digital Versatile Disks (DVDs)
• The Blu-ray disks

It also supports being used on different interfaces such as:

• Serial Advanced Technology Attachment (SATA)
• Parallel Advanced Technology Attachment (PATA)
• Small Computer System Interface (SCSI)
• Serial Attached SCSI (SAS)

Ideally, a hard disk drive is designed to store data in it, but, in reality, earlier there were more additional bits stored in it than the stream of data bits to allow more spaces between signals.

This helped significantly while the data was read back.

However, with the development of technology and electronics, the number of such additional bits inserted in the hard disks got reduced.

This widened the ratio between the data bits and the recorded bits.

With the use of RLL encoding, the number of 0s before a 1 is added and recorded, and the same is done for the 1s before a 0.

For example, RLL 1,7 means:

• There is one 0 between every 1.
• The digit 7 indicates that up to eight time periods may exist between flux transitions.

The density of the flux pattern created by mapping the group of bits through RLL is however limited to two specific aspects such as:

• The spatial resolution of the hard disk platters
• The frequency response of the electronics and the read/write head

Implementations of Run Length Limited may vary depending on the maximum and minimum numbers of transition cells allowed between the transitions.

Run Length Limited encoding is a pretty simple way to compress data which involves specifying the number of characters or pixel color repeats for the purpose of reducing the number of bits.

It simply puts a limit on the number that can pass through a transition in the magnetic media with the help of a line coding scheme.

This type of encoding prevents losing synchronization of the reading device of the hard drive to the bit periods and eventually corrupting the data.

Analysis

When you need to analyze Run Length Limited encoding to find out exactly how much space is saved, all you have to do is consider each of the original bits to be stored as one character.

Typically, suppose that in an original representation of the image, there are up to 225 digits consisting of 0s and 1s only.

When you count the number of digits and commas, ignoring the newlines or spaces, in the new representation, you will get the number of characters needed to represent the image.

For example, if there are 121 characters in the new representation of the image, it will be about 54% (121/225) of the total number of characters used in the original representation.

This results in saving almost half the space on your hard drive needed to store the image.

Drawbacks

This type of coding needs pairing with repetitive and simple data. Apart from this downside, a couple of other significant ones are as follows:

• The original data may not be accessible instantly since prior decoding is required.
• The size of decoded data cannot be determined beforehand, which causes issues in decompressing a file if there is limited space.

This can be resolved by storing the size of the data as metadata in some other place.

You may also use it with enough space and a dynamic buffer for decompressing the entire content in it.

How Run Length Limited Encoding Works?

The Run Length Limited method of encoding works on the basis of lossless compression. Here, the redundant data in a sequence of a code is stored as one single data value.

It represents the repeated block as the number of times it occurs in the image. Later on, it is decompressed to reconstruct the image, just as it is in the information.

In order to understand the working principle of Run Length Limited encoding, you will first have to understand lossless compression methods.

In this method of data compression, the integrity of the data is preserved for both the original and the subsequent data.

They are the same because, in this method, both the compression and decompression algorithms are the precise inverses of each other.

Ensuring that no data is lost during the encoding process, the exact number of redundant data removed during compression is added during decompression.

This type of image compression is not only used in RLL encoding during image compression but for other techniques as well, such as:

• Variable Length coding like Huffman and Arithmetic coding
• Bit Plane coding
• DPCM or Differential Pulse Code Modulation coding
• Predictive coding
• Entropy encoding
• LZW or Lempel–Ziv–Welch coding
• Adaptive dictionary algorithms that are used commonly in Graphics Interchange Format (GIF) and TIFF
• Deflation as used in Portable Network Graphics (PNG), Multiple-image Network Graphics (MNG), and TIFF
• Chain codes

Each row of an image is replaced with numbers to indicate the number of successive pixels of the same color, always beginning with the number of white pixels.

One of the simplest ways a computer stores a black and white image in binary is by using 0 and 1, where 0 represents white and 1 represents black.

For example, assume that a black and white image of three rows contains the following colors in its first row:

• One white pixel
• two black pixels
• four white pixels
• one black pixel
• four white pixels
• two black pixels
• one white pixel

This can be coded and represented in binary as follows:

• 011000010000110
• 1, 2, 4, 1, 4, 2, 1

Assume that the second row contains the following colors:

• One black pixel
• Five white pixels
• Three black pixels
• Five white pixels
• One black pixel

This can be coded and represented in binary as follows:

• 100000111000001
• 0, 1, 5, 3, 5, 1

Please note that it is required to express the number of white pixels before black, and therefore, in this case, a zero is added at the start of the row for representation.

Why? This is because there has to be a specific, clear, and universal rule for such representations so that the computer does not have any difficulty understanding which color was which while representing the image based on the data available.

Now assume that the third row of the image contains the following colors:

• Five white pixels
• Five black pixels
• Five white pixels

This can be coded and represented in binary as follows:

• 000001111100000
• 5, 5, 5

The process continues for the subsequent number of rows to represent any image.

Later on, when the image is needed to be displayed, the computer decompresses the codes, following the reverse process, into binary involving 0s and 1s only.

Where is RLL Used?

The RRL method was patented for the first time in 1983 by Hitachi. One of the most commonplace where Run Length Limited technique is used is for the black and white scanned images typically used on fax machines.

The main reason behind it being used here and working so well is that in these types of scanned images the number of consecutive white pixels used in them is huge.

In reality, there can be a whole scanned line, which is nothing but a lot of white pixels.

If it is 200 pixels across, which is typical for a fax page, or even more than that, replacing these 200 bits by compressing them into a single number will allow a big saving.

Even if it consumes a single byte, because it may take a few bits to represent it, the overall savings will be significant.

In fact, this compression of bits will reduce the time taken by the fax machines to send pages by as much as seven times.

Though it is not used extensively today since there are more modern and effective options available, it is still used in different files and machines for color and images such as:

• For color on fax machines
• In the field of telecommunications
• In the storage systems to move medium past the static recording head
• For TIFF or Tag Image File Format
• For PDF or Portable Document Format files
• For PCX or Picture Exchange files
• For BMP or Bitmap files
• For TGA or Truevision Graphics Adapter files

Is Run Length Encoding Good?

Yes, Run Length encoding is quite a good type of compression that works best with simple animations and images created with loads of redundant pixels. In fact, this type of encoding is very beneficial, especially for black and white images.

Run Length encoding typically stores runs of data with the help of a type of lossless data compression as a single data count and value in place of the original run.

These data runs are sequences wherein the same data value befalls on several successive data elements. Therefore, this type of encoding is very useful on data with several runs, in simple graphic images, for example, which may include the following:

• Line drawings
• Icons

The overall idea of this type of compression method is to substitute the reiterating and successive occurrences of a data or symbol by one occurrence of the same and the number of such occurrences. This reduces the physical size of the repeating string of characters, called the Run.

It is usually done using just two bytes as follows, but not in the same order:

• The first byte represents the character of the repeating string.
• The second byte represents the number of characters in the run, often referred to as the Run Count.

Typically, in practice, there may be anywhere from 1 to 128 or 256 characters in an encoded run.

The Run Count normally contains the number of characters minus one. Therefore, the value of it would be within the range of 0 to 127 or 255.

The second byte that represents the value of the character of the run is typically within the range of 0 to 255. It is often referred to as the Run Value.

For example:

• The input string AAAAAAA will be represented as A7 according to Run Length Encoding is A7, where A represents the character and 7 indicates the number of times that character appears in the string.
• An input string of WWWWAAADEXXXXXX will be represented in Run Length Encoding as W4A3D1E1X6, following the same principle.

However, Run Length Encoding can make the size of the complex animations and image files bigger instead of smaller if there is no repetition of sections.

Conclusion

After reading this article now you know that Run Length Limited is a useful technique for storing large strings of codes for images especially in a short form on the storage medium to save a lot of space in the process.

Though there are a few drawbacks to this process, it is still beneficial and is used in some areas today.