Кодирование с ограниченной длиной серии или RLL — это метод линейного кодирования , который используется для передачи произвольных данных по каналу связи с ограничениями полосы пропускания . Коды RLL определяются четырьмя основными параметрами: m , n , d , k . Первые два, m / n , относятся к скорости кода, а оставшиеся два определяют минимальное d и максимальное k количество нулей между последовательными единицами. Это используется как в телекоммуникационных системах, так и в системах хранения, которые перемещают носитель мимо фиксированной записывающей головки . [1]
В частности, RLL ограничивает длину отрезков (прогонов) повторяющихся битов, в течение которых сигнал не изменяется. Если прогоны слишком длинные, восстановление тактовой частоты затруднено; если они слишком короткие, высокие частоты могут быть ослаблены каналом связи. Модулируя данные , RLL снижает временную неопределенность при декодировании сохраненных данных, что может привести к возможной ошибочной вставке или удалению битов при обратном считывании данных. Этот механизм гарантирует, что границы между битами всегда могут быть точно найдены (предотвращая проскальзывание битов ), при этом эффективно используя носитель для надежного хранения максимального объема данных в заданном пространстве.
Ранние дисководы использовали очень простые схемы кодирования, такие как код RLL (0,1) FM, за которым следовал код RLL (1,3) MFM, которые широко использовались в жестких дисках до середины 1980-х годов и до сих пор используются в цифровых оптических дисках, таких как CD , DVD , MD , Hi-MD и Blu-ray . Более плотные коды RLL (2,7) и RLL (1,7) стали фактическим отраслевым стандартом для жестких дисков к началу 1990-х годов.
На жестком диске информация представлена изменениями направления магнитного поля на диске, а на магнитном носителе выход воспроизведения пропорционален плотности потока перехода. В компьютере информация представлена напряжением на проводе. Отсутствие напряжения на проводе по отношению к определенному уровню земли будет двоичным нулем, а положительное напряжение на проводе по отношению к земле представляет двоичную единицу. Магнитные носители, с другой стороны, всегда несут магнитный поток — либо «северный» полюс, либо «южный» полюс. Чтобы преобразовать магнитные поля в двоичные данные, необходимо использовать какой-то метод кодирования для перевода между ними.
Один из самых простых практических кодов, модифицированный код без возврата к нулю с инверсией ( NRZI ), просто кодирует 1 как магнитный переход полярности, также известный как «переворот потока», а ноль — как отсутствие перехода. При вращении диска с постоянной скоростью каждому биту дается равный период времени, «окно данных», для магнитного сигнала, представляющего этот бит, и переворот потока, если таковой имеется, происходит в начале этого окна. (Примечание: старые жесткие диски использовали один фиксированный отрезок времени в качестве окна данных по всему диску, но современные диски более сложны; для получения дополнительной информации см. раздел зонированная битовая запись .)
Этот метод не так прост, поскольку выходной сигнал воспроизведения пропорционален плотности единиц, а длинная серия нулей означает отсутствие выходного сигнала воспроизведения вообще.
В простом примере рассмотрим двоичный шаблон 101 с окном данных 1 нс (одна наносекунда, или одна миллиардная секунды). Это будет сохранено на диске как изменение, за которым последует отсутствие изменений, а затем еще одно изменение. Если предыдущая магнитная полярность уже была положительной, результирующий шаблон может выглядеть следующим образом: −−+. Значение 255 или все двоичные единицы будут записаны как −+−+−+−+ или +−+−+−+−. Нулевой байт будет записан как ++++++++ или −−−−−−−−. 512-байтовый сектор нулей будет записан как 4096 последовательных бит с той же полярностью.
Поскольку дисковод является физическим устройством, скорость вращения дисковода может немного меняться из-за изменения скорости двигателя или теплового расширения пластины диска. Физический носитель на дискете также может деформироваться, вызывая большие ошибки синхронизации, а схема синхронизации на самом контроллере может иметь небольшие изменения скорости. Проблема в том, что при длинной строке нулей контроллер дисковода не может узнать точное положение считывающей головки, и, следовательно, не может точно узнать, сколько нулей. Изменение скорости даже на 0,1%, что точнее, чем у любого практического дисковода, может привести к добавлению или удалению 4 бит из 4096-битного потока данных. Без какой-либо формы синхронизации и исправления ошибок данные станут совершенно непригодными для использования.
Другая проблема обусловлена ограничениями самого магнитного носителя: на определенном участке пространства можно записать лишь определенное количество изменений полярности, поэтому существует верхний предел того, сколько изменений полярности можно записать последовательно; это зависит от линейной скорости и зазора головки.
Чтобы предотвратить эту проблему, данные кодируются таким образом, что не происходит длинных повторений одного двоичного значения. Ограничивая количество нулей, записанных последовательно, некоторым максимальным значением k , это позволяет контроллеру привода оставаться синхронизированным. Ограничивая количество нулей, записанных подряд, некоторым минимальным значением d между каждым, общая частота изменений полярности уменьшается, что позволяет приводу хранить больше данных в том же объеме пространства, что приводит либо к меньшему пакету для того же объема данных, либо к большему объему хранения в пакете того же размера.
Все коды, используемые для записи на магнитные диски, имеют ограниченную длину свободных от переходов пробегов и поэтому могут быть технически охарактеризованы как коды RLL. Самые ранние и простейшие варианты получили специальные названия, такие как модифицированная частотная модуляция (MFM), а название «RLL» обычно используется только для более сложных вариантов, не имеющих специальных названий, но технически этот термин применим ко всем из них.
За пределами этой простейшей версии первым кодом RLL, использованным в жестких дисках, был RLL (2,7), разработанный инженерами IBM и впервые использованный в коммерческих целях в 1979 году на IBM 3370 DASD [2] [ 3] [4] для использования с мэйнфреймами серии 4300. В конце 1980-х годов жесткие диски ПК начали использовать собственно RLL (т. е. варианты, более сложные, чем те, которые получили собственные имена, такие как MFM). Коды RLL нашли почти универсальное применение в практике записи оптических дисков с 1980 года. В бытовой электронике коды RLL, такие как код EFM (скорость = 8/17, d = 2, k = 10), используются в компакт-дисках (CD) и мини-дисках (MD), а код EFMPlus (скорость = 8/16, d = 2, k = 10) используется в DVD . Параметры d и k — это минимальная и максимальная допустимая длина пробега. Для более подробного изучения технологий хранения, ссылки, цитируемые в этой статье, полезны. [5] [6]
Обычно длина серии — это количество бит, для которых сигнал остается неизменным. Длина серии 3 для бита 1 представляет последовательность 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. Добавленные биты 1 называются битами синхронизации.
Пример:
Данные: 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. Это оригинальный вариант записи с групповым кодированием IBM
Где это возможно (11 из 16 кодов), битовая комбинация abcdкодируется путем добавления к ней префикса с дополнением a : aabcd. В 5 случаях, когда это нарушает одно из правил ( 000dили ab00), заменяется код, начинающийся с 11 ( , где e = a ∨ d ).11bea
Пример:
Данные: 0010 1101 0001 1000Закодировано: 10010011011101111010
Обратите внимание, что для соответствия определению (0,2) RLL недостаточно только того, чтобы каждый 5-битный код содержал не более двух последовательных нулей, но также необходимо, чтобы любая пара 5-битных кодов в совокупности последовательно не содержала более двух последовательных нулей. То есть между последним единичным битом в первом коде и первым единичным битом во втором коде для любых двух произвольно выбранных кодов не должно быть более двух нулей. Это необходимо, поскольку для любого кода RLL ограничения длины серии — 0 и 2 в данном случае — применяются к общему модулированному потоку битов, а не только к его компонентам, представляющим дискретные последовательности простых битов данных. (Это правило должно выполняться для любой произвольной пары кодов без исключений, поскольку входные данные могут быть любой произвольной последовательностью битов.) Код IBM GCR выше соответствует этому условию, поскольку максимальная длина серии нулей в начале любого 5-битного кода равна единице, и аналогично максимальная длина серии в конце любого кода равна единице, что делает общую длину серии равной двум на стыке между соседними кодами. (Пример максимальной длины серии, возникающей между кодами, можно увидеть в примере, приведенном выше, где код для данных «0010» заканчивается нулем, а код для следующих данных, «1101», начинается с нуля, образуя серию из двух нулей на стыке этих двух 5-битных кодов.)
Модифицированная частотная модуляция становится интересной, потому что ее особые свойства позволяют записывать ее биты на магнитный носитель с плотностью, вдвое превышающей плотность произвольного потока битов. Существует предел того, насколько близко по времени могут быть переходы потока для их обнаружения считывающим оборудованием, и это ограничивает то, насколько близко биты могут быть записаны на носитель: в худшем случае с произвольным потоком битов есть два последовательных, что создает два последовательных перехода потока во времени, поэтому биты должны быть разнесены достаточно далеко друг от друга, чтобы между этими переходами потока было достаточно времени для их обнаружения считывателем. Но этот код накладывает ограничение d = 1, то есть между каждыми двумя единицами есть минимум один ноль. Это означает, что в худшем случае переходы потока находятся на расстоянии двух битовых времен друг от друга, поэтому биты могут быть вдвое ближе друг к другу, чем с произвольным потоком битов, не превышая возможностей считывателя.
Эта удвоенная плотность записи компенсирует 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 бита на диске, и кодирование выполняется в 2- или 4-битных группах. Правила кодирования следующие: ( x , y ) становится (NOT x , x AND y , NOT y ), за исключением ( x , 0, 0, y ) становится (NOT x , x AND y , NOT y , 0, 0, 0). [7] При кодировании в соответствии с таблицей ниже необходимо использовать самое длинное (последнее в таблице) совпадение; это исключения, обрабатывающие ситуации, когда применение более ранних правил приведет к нарушению ограничений кода.
Пример:
Данные: 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 бит данных на 2 n бит на диске, как MFM, но поскольку минимальная длина пробега на 50% больше (3 бита вместо 2), биты могут быть записаны быстрее, достигая на 50% более высокой эффективной плотности данных. Кодирование выполняется в 2-, 3- или 4-битных группах.
Вестерн Диджитал WD5010A, WD5011A, WD50C12
Seagate ST11R, IBM
Perstor Systems ADRC
Закодированные формы начинаются максимум с 4 и заканчиваются максимум 3 нулевыми битами, что дает максимальную длину серии 7.
Пример:
Данные: 1 1 0 1 1 0 0 1 1Закодировано: 1000 001000 00001000
Код HHH(1,13) — это код со скоростью 2/3, разработанный тремя исследователями IBM (Хиртом, Хасснером и Хайзе) для использования на физическом уровне IrDA VFIR 16 МБ/с. [8] В отличие от магнитного кодирования, он разработан для инфракрасного передатчика, где бит 0 представляет «выкл.», а бит 1 представляет «вкл.». Поскольку биты 1 потребляют больше энергии для передачи, он разработан для ограничения плотности битов 1 до менее 50%. В частности, это код RLL (1,13|5), где последняя 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-кодирование, сохраняет каждый бит данных как два бита на ленте, но поскольку гарантированно существует один бит 0 (нет переворота потока) между любыми битами 1 (переворот потока), то можно сохранить 6400 закодированных бит на дюйм на ленте или 3200 бит данных на дюйм. (1,7) RLL-кодирование также может хранить 6400 закодированных бит на дюйм на ленте, но поскольку для хранения 2 бит данных требуется всего 3 закодированных бита, это составляет 4267 бит данных на дюйм. Кодирование (2,7) RLL требует 2 закодированных бита для хранения каждого бита данных, но поскольку между любыми битами 1 гарантированно находятся два нулевых бита, то на ленте можно хранить 9600 закодированных битов на дюйм или 4800 бит данных на дюйм.
Плотность реверсирования потока на жестких дисках значительно выше, но такие же улучшения в плотности хранения наблюдаются при использовании различных систем кодирования.
Ограниченная система определяется ограниченным набором «хороших» или «допустимых» последовательностей для записи или передачи. Ограниченное кодирование фокусируется на анализе ограниченных систем и проектировании эффективных кодеров и декодеров, которые преобразуют произвольные пользовательские последовательности в ограниченные последовательности.
Дано подробное описание предельных свойств runlength-limited sequences.