Кодирование с ограничением длины пробега

Кодирование с ограничением длины пробега или длины серии, RLL-кодирование (англ. Run-length limited, RLL) — это техника линейного кодирования, которая используется для передачи произвольных данных по каналам связи с ограниченной полосой пропускания. RLL применяется как в телекоммуникационных системах, так и в системах хранения данных, где носитель перемещается мимо фиксированной записывающей головки.

Различные коды с ограниченной длиной серий часто различают по параметрической номенклатуре (d,k) RLL^[1], но на самом деле они определяются четырьмя основными параметрами: m, n, d, k. Первые два, m и n, относятся к скорости кода, тогда как оставшиеся два определяют минимальное d и максимальное k число нулей между последовательными единицами ^[2]. В частности, RLL ограничивает длину серий (участков) повторяющихся битов в течение которых сигнал не меняется. Если серии слишком длинные, затруднено восстановление тактовой синхронизации, если они слишком короткие, высокие частоты могут быть ослаблены каналом связи. Модулируя данные, RLL уменьшает неопределённость синхронизации при декодировании сохранённых данных, что могло бы привести к возможной ошибочной вставке или удалению битов при чтении данных. Этот механизм гарантирует, что границы между битами всегда могут быть точно найдены (предотвращая проскальзывание бита), при этом эффективно используя носитель для надёжного хранения максимального объёма данных в заданном пространстве.

Вырожденные схемы RLL-кодирования, такие как FM и MFM, широко использовались в жёстких дисках до середины 1980-х годов. Более плотные коды RLL (2,7) и RLL (1,7) стали, фактически, отраслевым стандартом для жёстких дисков в начале 1990-х годов. Коды RLL более высокого порядка до сих пор используются в цифровых оптических дисках, таких как CD, DVD, MD, Hi-MD и Blu-ray.

На жёстком диске информация представлена путём изменения направления магнитного поля. На магнитных носителях выходной сигнал при воспроизведении пропорционален плотности магнитных переходов. В компьютере информация представлена напряжением на проводе. Отсутствие напряжения относительно определённого уровня земли соответствует двоичному нулю, а положительное напряжение относительно земли – двоичной единице. Магнитные носители, с другой стороны, всегда содержат магнитный поток. Для преобразования магнитных полей в двоичные данные необходимо использовать метод кодирования, который осуществляет перевод между этими двумя представлениями.

Один из самых простых практических кодов, модифицированный невозврат к нулю с инверсией (англ. non-return-to-zero-inverted, NRZI), просто кодирует единицу как переход магнитной полярности, также известный как «смена потока», а ноль — как отсутствие перехода. При постоянной скорости вращения диска каждому биту отводится равный промежуток времени «окно данных», для представляющего этот бит магнитного сигнала, и смена потока, если она происходит, случается в начале этого окна. (Заметим: старые жёсткие диски использовали одну фиксированную длительность окна данных для всего диска, но современные диски сложнее, подробнее об этом читайте в статье Зональная побитовая запись.)

Этот метод не так прост, поскольку выходной сигнал при воспроизведении пропорционален плотности единиц, а длинная последовательность нулей означает полное отсутствие выходного сигнала.

В качестве простого примера рассмотрим двоичное значение 101 с окном данных в одну наносекунду (миллиардная доля секунды). На диске это будет представлено как изменение, затем отсутствие изменения и снова изменение. Если предыдущая магнитная полярность была положительной, результирующий шаблон может выглядеть так −−+. Значение 255 (состоящее из единиц в двоичном коде), будет записано как −+−+−+−+ или +−+−+−+−. Нулевой байт будет записан как ++++++++ или −−−−−−−−. Сектор из 512 байт, заполненный нулями, будет записан как последовательность 4096 бит одинаковой полярности.

Поскольку дисковод является физическим устройством, скорость его вращения может незначительно меняться из-за изменения скорости двигателя или теплового расширения пластины диска. Физический носитель на дискете также может деформироваться, вызывая большие ошибки синхронизации, а сама схема синхронизации контроллера может иметь небольшие отклонения в скорости. Проблема заключается в том, что при длинной последовательности нулей контроллер дисковода не может точно определить положение головки чтения, а следовательно, и точное количество нулей. Даже изменение скорости на 0,1%, что является более точным показателем, чем у любого практического дисковода для дискет, может привести к добавлению или удалению 4 бит из потока данных объёмом 4096 бит. Без какой-либо формы синхронизации и коррекции ошибок данные станут совершенно непригодными для использования.

Другая проблема связана с ограничениями самих магнитных носителей — можно записать лишь ограниченное количество изменений полярности в определённом объёме пространства, так что существует верхний предел для последовательной записи единиц, который зависит от линейной скорости и зазора головки.

Во избежание этой проблемы данные кодируются таким образом, что длинные повторения одного бинарного значения не возникают. Ограничение максимального количества последовательных нулей до некоторого значения k позволяет контроллеру диска оставаться синхронизированным. Ограничение же минимального количества нулей между единицами до некоторого значения d снижает общую частоту изменения полярности, что позволяет диску хранить больше данных в том же объёме пространства, что приводит либо к уменьшению размера устройства при том же объёме данных, либо к увеличению объёма хранения в устройстве того же размера.

Название «RLL» обычно применяется только к более сложным вариантам, но ранние методы записи на магнитные диски, частотная модуляция (ЧМ, англ. frequency modulation, FM) и MFM-кодирование (англ. modified frequency modulation, MFM), по сути, являются вырожденными вариантами RLL, поскольку они ограничивали длину последовательностей без переходов^[3].

Помимо этих простых версий, первым кодом RLL, использованным в жёстких дисках, был (2,7) RLL, разработанный инженерами IBM^[4] и впервые применённый в коммерческих целях в 1979 году на устройстве IBM 3370 DASD^[5][6][7] для использования с мейнфреймами серии 4300. В конце 1980-х годов жёсткие диски PC начали использовать RLL в полном смысле этого слова (то есть более сложные варианты, чем те, которые получили собственные названия, такие как MFM). Коды RLL нашли почти универсальное применение в практике записи на оптические диски с 1980 года. В потребительской электронике RLL, такие как EFM-модуляция (скорость = 8/17, d = 2, k = 10) используются в Компакт-дисках (CD) и минидисках (MD), а EFMPlus код (скорость = 8/16, d = 2, k = 10) используется в DVD. Параметры d и k — это минимальная и максимальная допустимые длины серий. Для более подробного ознакомления с технологиями хранения данных полезны ссылки, приведённые в этой статье^[8][9].

Длина серии обычно означает количество бит, в течение которых сигнал считается неизменным. Серия длиной 3 из единиц, представляет последовательность 111. Например, шаблон магнитных поляризаций на диске может выглядеть как +−−−−++−−−++++++, с сериями длиной 1, 4, 2, 3 и 6. Однако, в терминологии кодирования с ограниченной длиной серии предполагается кодирование NRZI, где биты 1 означают изменения, а биты 0 — отсутствие изменений. Указанная выше последовательность будет выражена как 11000101001000001, и подсчитываются только серии нулевых битов.

Несколько сбивает с толку, но длина серии — это количество нулей (0, 3, 1, 2 и 5 в предыдущем примере) между соседними единицами, что на единицу меньше, чем количество временны́х интервалов, в течение которых сигнал фактически остается неизменным. Последовательности с ограниченной длиной серии характеризуются двумя параметрами, d и k, которые определяют минимальную и максимальную длину серии нулевых битов, которая может встречаться в последовательности. Таким образом, коды RLL обычно указываются как (d,k) RLL, например, (1,3) RLL.

В закодированном формате бит "1" указывает на переход магнитного потока, тогда как "0" означает, что магнитное поле на диске не изменяется в течение этого временно́го интервала.

Термин «код RLL» обычно применяется к более сложным методам кодирования, но исходный код частотной модуляции, известный также как дифференциальное манчестерское кодирование, можно рассматривать как вырожденный RLL код со скоростью 1/2. Дополнительные единицы называются тактовыми битами^[4].

Пример:

Данные:          0 0 1 0 1 1 0 1 0 0 0 1 1 0
Код:             1010111011111011101010111110
Тактовый сигнал: 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Расширяя максимальную длину последовательности из нулевых бит до 2 смежных, можно повысить скорость передачи данных до 4/5. Это оригинальный вариант группового кодирования (англ. Group Coded Recording, GCR) IBM.

Где допустимо (в 11 кодах из 16), битовая последовательность abcd кодируется добавлением инвертированного бита a: aabcd. В пяти кодах, где такое кодирование нарушает одно из правил (000d или ab00), используется код, начинающийся с 11 (11bea, где e = a ∨ d).

Пример:

Данные: 0010 1101 0001 1000
Код:    10010011011101111010

Заметьте, что для соответствия определению (0,2) RLL недостаточно, чтобы каждый 5-битный код содержал не более двух нулей подряд, необходимо также, чтобы любая пара 5-битных кодов, объединённых последовательно, не содержала более двух нулей подряд. То есть, между последним единичным битом первого кода и первым единичным битом второго кода не должно быть более двух нулей, независимо от того, какие два кода выбраны произвольно. Это требование обусловлено тем, что для любого RLL-кода ограничения на длину последовательности нулей – в данном случае 0 и 2 – применяются ко всему модулированному битовому потоку в целом, а не только к его отдельным частям, представляющим дискретные последовательности исходных битов данных. (Это правило должно соблюдаться для любой произвольной пары кодов без исключений, поскольку входные данные могут представлять собой любую произвольную последовательность битов.) Приведённый выше код IBM GCR удовлетворяет этому условию, поскольку максимальная длина последовательности нулей в начале любого 5-битного кода составляет единицу, и аналогично максимальная длина последовательности нулей в конце любого кода также составляет единицу, что в сумме дает длину последовательности из двух нулей на стыке соседних кодов. (Пример максимальной длины последовательности нулей, возникающей между кодами, можно увидеть в приведённом выше примере, где код для данных "0010" заканчивается нулём, а код для следующих данных, "1101", начинается с нуля, образуя последовательность из двух нулей на стыке этих двух 5-битных кодов.)

Модифицированная частотная модуляция (англ. Modified frequency modulation, MFM) становится по-настоящему интересной, поскольку её особые свойства позволяют записывать биты на магнитный носитель с удвоенной плотностью произвольного потока битов. Существует предел того, насколько близко во времени могут располагаться переходы магнитного потока, чтобы считывающее оборудование могло их обнаружить. В худшем случае при произвольном потоке битов имеются две единицы подряд, что приводит к двум последовательным переходам магнитного потока по времени, так что биты должны располагаться достаточно далеко друг от друга, чтобы между этими переходами было достаточно времени для их обнаружения считывателем. Однако данный код накладывает ограничение d = 1, то есть между каждыми двумя единицами должен быть как минимум один ноль. Это означает, что в худшем случае переходы магнитного потока находятся на расстоянии двух битовых интервалов друг от друга, поэтому биты могут располагаться в два раза ближе, чем при произвольном потоке битов, не превышая возможностей считывателя^[10][4].

Эта удвоенная плотность записи компенсирует скорость кодирования 1/2 этого кода (для представления одного бита реальной информации требуется два бита) и делает его эквивалентным коду со скоростью 1.

Кодирование очень похоже на FM-кодирование.

Где "x" является инверсией предыдущего закодированного бита потока.

За исключением тактовых битов, которые не всегда равны единице, это совпадает с таблицей FM, и именно так этот код получил свое название. Вставленные тактовые биты равны 0, кроме случаев, когда они находятся между двумя нулевыми битами данных..

При объединении с предыдущим битом n-1, результирующая таблица кодирования для каждого бита данных n фактически становится.

Пример:

Данные:          0 0 1 0 1 1 0 1 0 0 0 1 1 0
Код:             x010010001010001001010010100
Тактовый сигнал: x 1 0 0 0 0 0 0 0 1 1 0 0 0

(1,7) RLL отображает 2 бита данных в 3 бита на диске, а само кодирование выполняется для групп из двух или четырёх бит. Правила кодирования следующие: (x, y) становится (NOT x, x AND y, NOT y), за исключением группы (x, 0, 0, y), которая преобразуется в (NOT x, x AND y, NOT y, 0, 0, 0)^[11]. При кодировании согласно приведённой ниже таблице необходимо использовать самое длинное совпадение (последнее в таблице). Это исключает ситуации, при которых применение более ранних правил привело бы к нарушению ограничений.

Пример:

Данные: 0 0 1 0 1 1 0 1 0 0 0 1 1 0
Код:    101 001 010 100 100 000 001

(2,7) RLL — это код со скоростью 1⁄2, который преобразует n бит данных в 2n бит на диске, подобно MFM, но поскольку минимальная последовательность серии на 50% больше (3 бита вместо 2), биты могут записываться быстрее, что обеспечивает на 50% более высокую эффективную плотность данных. Кодирование выполняется группами по 2, 3 или 4 бита^[4].

Диски компании Western Digital WD5010A, WD5011A, WD50C12

Диск ST11R компании Seagate, диски компании IBM

ADRC компании Perstor Systems

Закодированные формы начинаются максимум с 4, а заканчиваются максимум 3 нулевыми битами, что дает максимальную длину последовательности в 7.

Пример:

Данные: 1 1  0 1 1  0 0 1 1
Код:    1000 001000 00001000

Код HHH(1,13) — это код со скоростью 2/3, разработанный тремя исследователями IBM (Хирт, Хасснер и Хайзе) для использования в физическом уровне16 Мбит/с IrDA VFIR^[a][12]. В отличие от магнитной записи, этот код предназначен для инфракрасного передатчика, где 0-битное значение означает «выключено», а 1-битное — «включено». Поскольку передача 1-битных значений потребляет больше энергии, код разработан таким образом, чтобы ограничить плотность 1-битных значений менее чем 50%. В частности, это код (1,13|5) RLL, где последнее число 5 указывает на дополнительное ограничение: не более 5 последовательных пар битов "10".

Первые восемь строк описывают стандартный код (1,7) RLL. Дополнительные шесть исключений увеличивают максимальную последовательность нулей до 13 (в допустимом шаблоне 100 000 000 000 001, что соответствует 10 11 10 11, за которым следует 01), но ограничивают максимальную среднюю плотность единиц до 1⁄3. Самая длинная последовательность пар 1-0 составляет 000 101 010 101 000.

Этот код ограничивает плотность единиц в диапазоне от 1⁄12 и 1⁄3, со средним значением 25,8%.

Пример. Закодируем битовую последовательность 10110010 с помощью различных кодировок

Предположим, магнитная лента может вмещать до 3200 изменений магнитного потока на дюйм. Модифицированное частотное кодирование, или (1,3) RLL-кодирование, записывает каждый бит данных как два бита на ленте, но поскольку между любыми битами "1" (изменение магнитного потока) гарантированно находится один бит "0" (без изменения магнитного потока), то на дюйм ленты можно записать 6400 закодированных битов, что соответствует 3200 битам данных. (1,7) RLL-кодирование также позволяет записать 6400 закодированных битов на дюйм ленты, но поскольку для хранения двух битов данных требуется три закодированных бита, это даёт 4267 битов данных на дюйм. (2,7) RLL-кодирование использует два закодированных бита для хранения каждого бита данных, но поскольку между любыми битами "1" гарантированно находятся два бита "0", то на дюйм ленты можно записать 9600 закодированных битов, что соответствует 4800 битам данных.

Плотность изменений магнитного потока на жёстких дисках значительно выше, но такое же повышение плотности хранения достигается при использовании различных систем кодирования.

• 8b/10b кодирование
• Проскальзывание бита
• EFM и EFMplus — коды (2,10) RLL без постоянной составляющей используются на CD и DVD соответственно.
• Корректирующий код
• Линейный код
• Модуляция
• Физический уровень
• PRML
• Кодирование длин серий
• Самосинхронизирующиеся коды и битовая синхронизация
• Сжатие данных

• Digital Magnetic Tape Recording