Inside memory a bit is unambiguous: a cell either holds a 1 or a 0. Once bits leave the computer, along a cable or onto a magnetic disk, they become an analogue signal that must be read back by a receiver whose clock is not perfectly in step with the sender’s. Data encoding is the process of converting a simple code (such as ASCII) into another code that is more effective to store or transmit. This lesson covers the classic encodings in Null & Lobur, Ch. 2: NRZ, NRZI, Manchester, FM, MFM and RLL.
Bit cells and flux reversals
To transmit data, pulses of “high” and “low” voltage are sent along the medium.
To store data on magnetic media, the magnetic polarity of tiny areas of the surface is set one way or the other. A change of polarity from one area to the next is a flux reversal, and it is the change that the read head detects, not the polarity itself.
A bit cell is the unit that holds one bit:
for transmission, the period of time during which one bit is sent (at 2 Kbps, one bit lasts 1/2000s=0.5 ms);
for storage, the area of the magnetic surface in which one bit is stored.
The central problem is synchronisation. The receiver finds bit-cell boundaries by watching for transitions. If a long stretch of signal has no transitions, its clock drifts and it may count, say, seven zeros where there were eight. Every code below is a different trade-off between having enough transitions to stay synchronised and not wasting bandwidth or disk area on extra transitions.
Conventions used on this page (as in the lecture figures): bit cells are separated by dashed lines; each cell is split into two halves (dotted line), and a transition can happen at a cell boundary or in the middle of a cell. The tables in the worked examples list the level in the first half and second half of every cell (H = high, L = low), which is the unambiguous version of the picture. Transition counts include every level change inside the drawn cells.
Non-Return-to-Zero (NRZ)
Rule: 1 = high for the whole cell, 0 = low for the whole cell. It is the simplest code and the most compact: at most one transition per cell, and only where the bit value changes.
Problem: a long string of identical bits (e.g. 00000000 or 11111111) is a flat line with no transitions, so the receiver loses synchronisation.
Mini-example
Data 10011:
Two transitions (1→0 after cell 1, 0→1 after cell 3).
Non-Return-to-Zero-Invert (NRZI)
Rule: a 1 causes a transition (high→low or low→high, whichever is opposite to the current level); a 0 causes no transition. The level itself means nothing; only the presence of a transition carries information. In the lecture’s figures the transition is drawn in the middle of the 1’s cell.
Good: long strings of 1s now produce a transition in every cell, so they no longer cause synchronisation loss. Used in low-speed links (RS-232), tape and basic optical storage.
Problem: long strings of 0s are still a flat line.
Mini-example
Data 10011, line starting high:
Three 1s → three transitions; the two 0s keep the level unchanged.
Manchester code (phase modulation)
Rule: every cell has a transition in the middle: a 1 is an “up” transition (low → high) and a 0 is a “down” transition (high → low). When two equal bits are adjacent, the signal must also flip at the boundary between them to get back to the correct starting level.
Good: no long flat stretches ever: the receiver gets a transition in every cell, so the clock is effectively carried in the data. For many years Manchester code was the dominant transmission code for LANs (classic Ethernet), and it is still found in legacy industrial-control networks.
Cost: up to two transitions per cell, which is twice the bit density of NRZ. On a disk this wastes storage capacity.
Mini-example
Data 10011:
Five mid-cell transitions plus two boundary transitions (between the two 0s and between the two 1s) = 7.
Frequency Modulation (FM)
Rule: there is a transition at every cell boundary (the “clock” transition; the lecture draws it at the end of each cell), and cells containing a 1 also get a transition in the middle (the “data” transition). A 0 cell is flat between its boundaries; a 1 cell flips in the middle.
Comparison: FM has even more transitions than Manchester (one per cell for the clock plus one per 1), so it is the least dense of the disk codes. It is easy to decode: “was there an extra transition in the middle?” is the bit value.
Mini-example
Data 10011:
Within the five cells: three mid-cell (data) transitions + four boundary transitions between cells = 7, plus the clock transition at the end of the last cell = 8 = 5 cells + three 1s.
Modified FM (MFM)
MFM removes most of FM’s clock transitions:
a cell containing a 1 has a transition in the middle, as in FM;
a cell-boundary transition occurs only between two adjacent cells that both contain 0.
So a boundary transition is only inserted where it is needed: a run of 0s would otherwise have no transitions at all. Between a 1 and anything else no boundary transition is needed, because the 1 already provides a mid-cell transition. MFM was the standard for floppy disks and early hard disks.
Mini-example
Data 10011:
Three mid-cell transitions (the 1s) + one boundary transition (between the two 0s) = 4.
Run-Length-Limited code, RLL(2,7)
Idea: rather than adding clock transitions, first re-code the data so that 1s never come too close together or too far apart, then record the result with NRZI (a transition for each 1).
An RLL(d,k) code guarantees at least d and at most k consecutive 0s between any two 1s. RLL(2,7) therefore has at least two and at most seven 0s between 1s:
min 2 zeros → flux reversals are always at least 3 code cells apart, so code cells can be made very small;
max 7 zeros → there is a transition at least every 8 code cells, so synchronisation is kept.
RLL(2,7) maps variable-length groups of data bits to code groups twice as long, using this table:
Data bit pattern
RLL(2,7) code
10
0100
11
1000
000
000100
010
100100
011
001000
0010
00100100
0011
00001000
The data patterns form a prefix code (no pattern is the beginning of another), built like a Huffman code from the probability tree of bit patterns: 10 and 11 each occur with probability 41, the 3-bit patterns 81, the 4-bit patterns 161. So the data can be split into groups left to right without ambiguity.
Parsing procedure (read data left to right):
If the next bit is 1, take 2 bits (10 or 11).
If the next bits are 01, take 3 bits (010 or 011).
If the next bits are 000, take 3 bits (000).
If the next bits are 001, take 4 bits (0010 or 0011).
Replace each group by its code, concatenate, then record with NRZI (a transition for every 1 in the code).
RLL(2,7) was the dominant disk coding method for many years. Modern drives use newer techniques such as PRML (Partial Response Maximum Likelihood), which models the channel’s response and uses maximum-likelihood decoding to find the most probable bit sequence.
Only three 1s in the code, so NRZI gives only three flux reversals for 8 data bits.
Density comparison
Code
Transitions per data bit
Notes
NRZ
0 – 1
densest, but loses sync on runs of 0s or 1s
NRZI
0 – 1
loses sync on runs of 0s
Manchester
1 – 2
self-clocking, twice NRZ density
FM
1 – 2
clock transition every cell + data transitions
MFM
0.5 – 1
clock transitions only between adjacent 0s
RLL(2,7)
0.25 – 0.67
2 code cells per data bit, but code 1s are at least 3 and at most 8 code cells apart
Bit-cell sizing: for the same number of flux reversals per unit area, the cells can be smallest in RLL, then MFM, then FM. Equivalently, if a disk is limited by the number of flux transitions per square mil, we can pack the most data with RLL, then MFM, then FM: RLL > MFM > FM in density.
For the lecture’s message “OK” (16 data bits) the counts are: NRZ 8, NRZI 10, Manchester 23, FM 26, MFM 12, RLL(2,7) 8. MFM needs 12/16=0.75 transitions per data bit, RLL only 8/16=0.5: RLL saves 0.25 of a flux transition per data bit, i.e. 4 transitions in 16 bit cells = 25% compared with MFM. (Put another way, RLL uses only 8/12=2/3 as many flux reversals, so the same surface can hold 1.5 times as many “OK”s.) Worked Examples 2 to 5 derive every one of these numbers.
Worked Examples
Exercise 1
(a) A serial line runs at 2 Kbps. How long is one bit cell?
(b) The same question for 9600 bps.
(c) Classic Ethernet sends 10 Mbps using Manchester code. How long is a bit cell, and what is the largest number of transitions per second on the wire?
Show solution ↓Hide solution ↑
Solution
A bit cell (for transmission) is the time for one bit, i.e. 1/(bit rate).
(a)2000bit/s1=0.0005s=0.5ms.
(b)96001≈0.000104s=104.17μs.
(c)10×1061=100ns per cell. Manchester has a mid-cell transition in every cell and, when two equal bits are adjacent, a boundary transition too. The worst case is a long run of identical bits (all 1s or all 0s): 2 transitions per cell, so at most 2×107=20 million transitions per second, with half-cells of 50 ns. This is why Manchester “costs” twice the bandwidth of NRZ.
Exercise 2
The message “OK” in ASCII with even parity is O = 11001111, K = 01001011. Draw it in NRZ and in NRZI and count the transitions in each.
Transitions occur only where the bit value changes between neighbouring cells: after cells 2, 4, 8, 9, 10, 12, 13, 14 → 8 transitions.
NRZI (line starting high, as in the lecture figure): flip in the middle of every 1 cell, hold for every 0.
One transition per 1. “OK” contains six 1s in O and four 1s in K → 10 transitions. Notice the flat stretch over cells 11–12 (00): two 0s in a row already give no transitions, and a longer run would lose synchronisation.
Level table:
Cell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Bit
1
1
0
0
1
1
1
1
0
1
0
0
1
0
1
1
NRZ
HH
HH
LL
LL
HH
HH
HH
HH
LL
HH
LL
LL
HH
LL
HH
HH
NRZI
HL
LH
HH
HH
HL
LH
HL
LH
HH
HL
LL
LL
LH
HH
HL
LH
Exercise 3
Draw “OK” (11001111 01001011) in Manchester code and in FM, and count the transitions.
Show solution ↓Hide solution ↑
Solution
Manchester: 1 = low→high in mid-cell (LH), 0 = high→low in mid-cell (HL). Insert a boundary flip wherever two equal bits are neighbours.
Mid-cell transitions: one per cell = 16.
Boundary transitions: between equal neighbours: cells 1–2 (11), 3–4 (00), 5–6, 6–7 and 7–8 (the run 1111), 11–12 (00), 15–16 (11) = 7.
Total: 16+7=23 transitions.
FM: a clock transition at the end of every cell; an extra mid-cell transition in every 1 cell. Starting low:
Data (mid-cell) transitions: one per 1 = 10.
Clock transitions: one at the end of every cell = 16 (15 between cells, visible above, plus one at the end of cell 16 that starts the next character).
Total: 10+16=26 transitions.
Level table:
Cell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Bit
1
1
0
0
1
1
1
1
0
1
0
0
1
0
1
1
Manchester
LH
LH
HL
HL
LH
LH
LH
LH
HL
LH
HL
HL
LH
HL
LH
LH
FM
LH
LH
LL
HH
LH
LH
LH
LH
LL
HL
HH
LL
HL
HH
LH
LH
Reading the FM table: a cell whose two halves differ (LH or HL) is a 1, a cell whose halves are equal (LL or HH) is a 0, and the level always flips between one cell and the next.
Exercise 4
Draw “OK” (11001111 01001011) in MFM and count the transitions. How many of FM’s transitions has MFM removed?
Show solution ↓Hide solution ↑
Solution
Rules: mid-cell transition for every 1; boundary transition only between two adjacent 0 cells. Starting low:
Step by step:
Mid-cell transitions: one per 1 = 10.
Pairs of adjacent 0s: cells 3–4 (00) and cells 11–12 (00) → 2 boundary transitions. (Cell 9 and cell 14 are single 0s between 1s, so they get none.)
Total: 10+2=12 transitions.
Level table:
Cell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Bit
1
1
0
0
1
1
1
1
0
1
0
0
1
0
1
1
MFM
LH
HL
LL
HH
HL
LH
HL
LH
HH
HL
LL
HH
HL
LL
LH
HL
FM needed 26 transitions for the same data, so MFM removed 26−12=14 of them: all the clock transitions except the two that keep the runs of 0s synchronised.
Exercise 5
Encode “OK” (1100111101001011) in RLL(2,7), record it with NRZI, count the transitions and compare with MFM. Show that RLL saves 25% compared with MFM.
Show solution ↓Hide solution ↑
Solution
Step 1: parse the data into table patterns (left to right):
Check the (2,7) constraint: the runs of 0s between consecutive 1s are 7, 3, 3, 2, 2, 2, 2 zeros, all between 2 and 7 ✓.
Step 3: record with NRZI (one transition per code 1), starting low:
Data group
RLL(2,7) code
Level in each code cell (first half, second half)
11
1000
LH HH HH HH
0011
00001000
HH HH HH HH HL LL LL LL
11
1000
LH HH HH HH
010
100100
HL LL LL LH HH HH
010
100100
HL LL LL LH HH HH
11
1000
HL LL LL LL
Step 4: count and compare.
Code
Cells drawn
Flux transitions
MFM
16 data cells
12
RLL(2,7)
32 code cells (= 16 data bits)
8 (one per 1 in the code)
Transitions per data bit: MFM 12/16=0.75, RLL 8/16=0.50.
saving=1612−8=164=25%
RLL needs 4 fewer flux reversals for the 16 bits of “OK”, a saving of one quarter of a transition per data bit (25%) compared with MFM. Equivalently RLL uses only 8/12=2/3 of MFM’s transitions, so a surface limited by flux reversals holds 12/8=1.5 times as much data.
Exercise 6
Encode the byte 10001111 in FM, MFM and RLL(2,7) and rank the three codes by the number of flux transitions.
Show solution ↓Hide solution ↑
Solution
FM (clock transition at the end of every cell + mid-cell for 1s):
Transitions: 5 ones + 8 clock = 13 (12 drawn between/inside the cells, plus the one at the end of cell 8).
MFM (mid-cell for 1s, boundary only between two 0s):
Transitions: 5 mid-cell + 2 boundaries (between 0s in cells 2–3 and 3–4) = 7.