RLL

Не варто плутати із RLE - Run-length encoding

Кодування з обмеженням довжини запису (англ. RLL, Run-length limited) — технологія кодування, яка застосовується для передачі даних через канал зв'язку із обмеженою смугою пропускання та для запису даних на магнітні, оптичні носії з метою уникнення зсуву бітів під час читання/запису. Використовувалась на жорстких дисках до 1980-х років; використовується на оптичних дисках (CD, DVD, MD, Hi-MD та Blu-ray). Скорочення RLL вжито інженерами компанії IBM в 1979 році під час розробки комп'ютера IBM 3370, де вперше застосована схема кодування RLL(2,7).

RLL є перетворенням послідовності бітів в послідовність наявностей чи відсутностей зміни сигналу. Схема кодування має два параметри run length та run limit, які означають мінімальну та максимальну відстань між двома змінами сигналу. Конкретна схема кодування записується як RLL(run length, run limit), наприклад, RLL(2,7). Перші жорсткі диски використовували дуже прості схеми, такі як RLL(0,1). Пізніше стали використовувати схеми RLL(1,7) та RLL(2,7).

Всі кодування, які застосовуються на магнітних дисках, обмежують довжину послідовностей, у яких відсутня зміна намагніченості, тому всіх їх можна віднести до RLL-кодувань. Найперші та найпростіші схеми кодування мали свої власні назви, наприклад, Modified Frequency Modulation (MFM), який фактично є RLL(1,3). Зазвичай позначення RLL застосовують лише для складніших схем, які не мають власних назв.

Навіщо потрібен RLL

У комп'ютері двійкові дані (0 чи 1) кодують відсутність чи наявність електричного струму (або заряду). На жорстких дисках дані зберігають як зміну напряму намагніченості ділянок диска. Потрібен метод перетворення магнітного сигналу в електричний і навпаки. Очевидним рішенням може здатися трактування відсутності зміни намагніченості як 0 і зміни намагніченості — як 1. Такий метод називається Non-Return-to-Zero-Inverted або NRZI. При застосуванні такого методу послідовність бітів 1010011 буде представлена у вигляді ++---±, якщо перед цим був -, або --+++-+, якщо перед цим був +. Але при застосуванні такого методу виникають проблеми.

По-перше, жорсткий диск обертається з деякою швидкістю і в магнітної голівки є якийсь певний проміжок часу, протягом якого вона може прочитати певний біт (це дещо спрощене твердження, детальніше дивись ZBR). Але через теплове розширення, деформацію чи недосконалість контролера, швидкість обертання може трохи коливатися. Тому при зчитуванні довгої послідовності нулів (які будуть записані як довга ділянка з однаковою намагніченістю), через непостійність швидкості неможливо буде дізнатися, скільки ж нульових бітів було записано. Наприклад, якщо записана послідовність із 4096 нульових бітів і диск обертається із швидкістю, яка може відхилятися на 0,1 %, то похибка у підрахунку зчитаних нульових бітів може сягати 4 бітів. Тобто, ділянка з 4096 нульових бітів може бути прочитана або як 4092, або як 4100 нульових бітів, що зробить дані абсолютно неправильними. Тому потрібна така схема, у якій послідовності нулів кодують зі змінами намагніченості, щоб магнітна голівка могла синхронізуватися.

Другою проблемою є те, що на магнітних носіях обмежена частота змін намагніченості — на ділянку можна записати не більше якоїсь певної кількості змін намагніченості. Тому бажана така схема кодування, в якій кількість змін намагніченості менша за кількість бітів зі значенням 1, або іншими словами, кількість змін намагніченості на кодування одиничного біта менша одиниці.

Кодування

Зміна намагніченості на протилежну позначатиметься як «^», а відсутність зміни позначатиметься як «-».

RLL(0,1) або FM

Біт Зміни намагніченості Ймовірність появи в потоку даних Кількість змін намагніченості на біт
0 ^- 50 % 1
1 ^^ 50 % 2
Середнє значення 1.5

RLL(0,2) або GCR

Біти Зміни намагніченості Ймовірність появи
в потоку даних 		Кількість змін
намагніченості на біт
0000 ^^--^ 6.25 % 3/4
0001 ^^-^^ 6.25 % 1
0010 ^--^- 6.25 % 1/2
0011 ^--^^ 6.25 % 3/4
0100 ^^^-^ 6.25 % 1
0101 ^-^-^ 6.25 % 3/4
0110 ^-^^- 6.25 % 3/4
0111 ^-^^^ 6.25 % 1
1000 ^^-^- 6.25 % 3/4
1001 -^--^ 6.25 % 1/2
1010 -^-^- 6.25 % 1/2
1011 -^-^^ 6.25 % 3/4
1100 ^^^^- 6.25 % 1
1101 -^^-^ 6.25 % 3/4
1110 -^^^- 6.25 % 3/4
1111 -^^^^ 6.25 % 1
Середнє значення 0.78125

RLL(1,3) або MFM

Біти Зміни намагніченості Ймовірність появи в потоку даних Кількість змін намагніченості на біт
0 (після 0) ^- 25 % 1
0 (після 1) -- 25 % 0
1 -^ 50 % 1
Середнє значення 0.75

RLL(1,7)

У схемі RLL(1,7) пара бітів (x, y) перетворюється на (НЕ x, x ТА y, НЕ y), окрім випадків, де має місце послідовність (x, -, -, y), яка перетворюється на (НЕ x, x ТА y, НЕ y, -, -, -). Якщо є можливість закодувати одразу чотири біти, так і робиться. Якщо такої можливості нема, то закодовується лише два біти.

Біти Зміни намагніченості Ймовірність появи в потоку даних Кількість змін намагніченості на біт
00 ^-^ 12.5 % 1
01 ^-- 25 % 1/2
10 --^ 12.5 % 1/2
11 -^- 25 % 1/2
0000 ^-^ — 6.25 % 1/2
0001 ^-- — 6.25 % 1/4
1000 --^ — 6.25 % 1/4
1001 -^- — 6.25 % 1/4
Середнє значення 0.515625

RLL(2,7)

Біти Закодовані біти Ймовірність появи в потоку даних Кількість змін намагніченості на біт
10 -^-- 25 % 1/2
11 ^--- 25 % 1/2
000 --- ^-- 12.5 % 1/3
010 ^-- ^-- 12.5 % 2/3
011 --^ — 12.5 % 1/3
0010 --^- -^-- 6.25 % 1/2
0011 ---- ^--- 6.25 % 1/4
Середнє значення 0.4635

Приклади

Для прикладу закодуємо послідовність бітів 10110010 різними схемами кодування

Схема кодування Вихідна послідовність Закодована послідовність
RLL(0,1) 10110010 ^^^-^^^^^-^-^^^-
RLL(0,2) 1011 0010 -^-^^ ^--^-
RLL(1,3) 10110010 -^---^-^--^--^--
RLL(1,7) 10 11 00 10 --^ -^- ^-^ --^
RLL(2,7) 10 11 0010 -^-- ^--- --^--^--

Див. також

Посилання