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

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

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

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

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

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

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

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

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

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

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

История

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

Помимо этих простых версий, первым кодом RLL, использованным в жёстких дисках, был (2,7) RLL, разработанный инженерами IBM и впервые применённый в коммерческих целях в 1979 году на устройстве IBM 3370 для использования с мейнфреймами серии 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 — это минимальная и максимальная допустимые длины серий. Для более подробного ознакомления с технологиями хранения данных полезны ссылки, приведённые в этой статье.

Технический обзор Длина серии обычно означает количество бит, в течение которых сигнал считается неизменным. Серия длиной 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" означает, что магнитное поле на диске не изменяется в течение этого временно́го интервала.

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

Данные Код 0 10 1 11

Пример: Данные: 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

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

Данные Код 0000 11001 0001 11011 0010 10010 0011 10011 0100 11101 0101 10101 0110 10110 0111 10111 Данные Код 1000 11010 1001 01001 1010 01010 1011 01011 1100 11110 1101 01101 1110 01110 1111 01111

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

Пример: Данные: 0010 1101 0001 1000 Код: 10010011011101111010

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

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