Run Length Limited

Run Length Limited (RLL) is a group of line codes , which in the field of telecommunications and storage media such as magnetic disk memories as a write method may be used. These codes are characterized by the fact that they restrict the length of uniform data sequences from the states logic 0 or logic 1 . The name is derived from this property.

The first RLL codes were patented by IBM in 1972 and used commercially from 1979 in the direct access storage device IBM 3370 for the mainframe computer series 4300. Simple RLL codes were used in the field of data recording from hard drives in the 1980s and 1990s . With adaptations, they are still used today in the field of magnetic data recording and optical storage media such as compact discs (CD).

Classification

In the literature, RLL codes are classified by two parameters d and κ and written in the form ( d , κ ) -RLL. The parameter d specifies the minimum and κ the maximum number of logical- 0 between two logical- 1 may occur in the data sequence. As a borderline case of a degenerate RLL code, κ can also be infinite.

If the RLL code is used in conjunction with the differential NRZI line code, as is customary when the RLL codes are used in magnetic storage media, a sufficient number of signal edges can be guaranteed for clock recovery when the data sequence is read . This dynamic clock recovery from the data signal is essential for synchronization with mechanical drives and their wow and flutter when the speed of rotation is only approximately specified.

All RLL codes can be described by means of a finite automaton , which must have κ + 1 states. A specific RLL code can then be clearly specified as a state diagram matrix, only the specification ( d , κ ) -RLL does not classify a specific RLL code.

Another essential parameter is the minimum length n of the required code words which meet a given ( d , κ ) condition. The lengths of the specifically selected code words can be uniform, but do not have to be. In the case of a uniform code word length, each user data bit or fixed block of user data bits of length k is uniquely assigned a code word of length n , the condition being: n> k. One example is the 4B5B code , which uniquely assigns 4 useful data bits to a 5-bit long code word. The ratio ^k / _n is the code rate R . The number k of information bits which a code word sequence of length N ( n ) carries is generally given as:

${\displaystyle k=\lfloor \log _{2}N(n)\rfloor }$

The capacity C ( d , κ ) of an RLL code is

${\displaystyle C(d,\kappa )=\lim _{n\to \infty }{\frac {1}{n}}\log _{2}N(n)=\log _{2}\lambda _{\mathrm {max} }}$

and can be determined using the Shannon-Hartley law using the largest eigenvalues λ of the state transition matrix . Tables of the capacity as a function of ( d , κ ) can be found in the relevant literature.

The efficiency of a certain RLL code is the ratio of its code rate R and its capacity C ( d , κ ). In practical applications, attempts are usually made to use RLL codes with the greatest possible efficiency.

variants

(0,1) -RLL - FM

The simplest (0.1) RLL code with a fixed code word length and a rate of ½ is also known as Frequency Modulation (FM) in combination with the differential line coding NRZI and is described by the following coding table:

Input data	code word
0	10
1	11

(1,3) -RLL - MFM

The (1,3) -RLL code, also known as Modified Frequency Modulation (MFM), is used for magnetic storage media such as floppy disks . This code also has a rate of ½:

Input data	code word
0	x0
1	01

The state of x depends on the previous data bit: x is 1 if the previous data bit was 0 , and 0 if the previous data bit was 1 .

(0.2) -RLL

A (0,2) -RLL code with a fixed block length is, among other things, the (0,2) -RLL code originally developed by IBM for magnetic storage, which belongs to the group of Group-Coded Recording (GCR) codes. It is a variant of a 4B5B code , but not identical to it. In addition, there are other GCR codes from various other companies that are not (0,2) -RLL codes; H. not all GCR codes are automatically (0,2) -RLL.

Input data code word 0000 11001 0001 11011 0010 10010 0011 10011 0100 11101 0101 10101 0110 10110 0111 10111

Input data code word 1000 11010 1001 01001 1010 01010 1011 01011 1100 11110 1101 01101 1110 01110 1111 01111

Another very simple (0,2) -RLL code, but with variable data length and fixed code word length, is the following:

Input data	code word
0	01
10	10
11	11

(2,7) -RLL

The following non-trivial (2,7) -RLL code with both variable data length and variable code word length was used in the 1980s and 1990s by manufacturers of hard disks with “RLL recording” (it comes from Peter Franaszek ). It fulfills both the prefix condition and has a fixed code rate of ½. There are some variants of this, one possible variant is given in the following table:

Input data	code word
10	0100
11	1000
011	001000
010	100100
000	000100
0010	00100100
0011	00001000

(1,7) -RLL

A (1,7) RLL code at a fixed rate of ² / ₃ is in which by a Boolean formation rule and thereby easily in the digital technology can be realized without a table, is the following code:

Input data	code word
00 00	101,000
00 01	100,000
10 00	001 000
10 01	010 000
00	101
01	100
10	001
11	010

The formation rule reads: If the input data sequence of the form (x, 0, 0, y) is sufficient, the code word ( NOT x, x AND y, NOT y, 0, 0, 0) is formed. If the input data does not meet this form, the code word (NOT x, x AND y, NOT y) is formed from the input data (x, y). Since this code does not meet the prefix condition, the order of the lines in the code word formation is important.

Also worth mentioning are RLL codes free of equal parts. The freedom from DC components is fulfilled when each data word sequence has, on average, the same number of ones and zeros. In other words, each data word sequence results in a sequence of code words which, in the case of an antipodal representation, i.e. H. logic-0 receives the value −1, logic-1 the value +1, has an equivalent value of 0. This property is important when the code sequence is to be transmitted via channels that cannot transmit direct signals, for example radio channels or pulse transformers for galvanic isolation in electrical circuits.

The following is an equal component-free (1,7) -RLL code:

Input data	code word
00	x01
01	010
10	x00
11 00	010 001
11 01	x00,000
11 10	x00 001
11 11	010 000

The state of x depends on the last bit of the code word that occurred immediately before: x is 1 if the last code bit was 0 , and 0 if the last code bit was 1 .

literature

• John G. Proakis, Masoud Salehi: Communication Systems Engineering . 2nd Edition. Prentice Hall, 2002, ISBN 0-13-095007-6 .

Individual evidence

1. ↑ JM Harker, DW Brede, RE Pattison, GR Santana, LG Taft: A Quarter Century of Disk File Innovation . In: IBM Journal of Research and Development . tape 25 , Issue 5, 1981, pp. 677-690 , doi : 10.1147 / approx . 255.0677 .
2. ^ PA Franaszek: Run-Length-Limited Variable Length Coding with Error Propagation Limitation. 1972, U.S. Patent No. 3689899
3. ↑ John G. Proakis, Masoud Salehi: Communication Systems Engineering . 2nd Edition. Prentice Hall, 2002, ISBN 0-13-095007-6 , pp. 512 .
4. ↑ C. Denis Mee, Eric D. Daniel: Magnetic Storage Handbook . 2nd Edition. McGraw Hill, 1996, ISBN 0-07-041275-8 .