Кодирование с ограничением длины серии или 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) и MiniDisc (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
Увеличив максимальную длину серии до двух соседних нулевых битов, скорость передачи данных можно повысить до 4/5. Это оригинальный вариант записи с групповым кодом IBM.
Там, где это возможно (11 из 16 кодов), битовая комбинация abcdкодируется путем добавления к ней префикса : 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-битными группами.
Western Digital WD5010A, WD5011A, WD50C12
Seagate ST11R, IBM
Перстор Системс 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, сохраняет каждый бит данных как два бита на ленте, но поскольку между любыми битами 1 (реверс потока) гарантированно находится один бит 0 (без реверса потока), то На ленте можно хранить 6400 закодированных бит на дюйм или 3200 бит данных на дюйм. Кодировка RLL (1,7) также может хранить на ленте 6400 закодированных битов на дюйм, но поскольку для хранения 2 битов данных требуется всего 3 закодированных бита, это составляет 4267 битов данных на дюйм. Кодирование RLL (2,7) требует 2 закодированных бита для хранения каждого бита данных, но поскольку между любыми битами 1 гарантированно находятся два 0-бита, то на ленте можно хранить 9600 закодированных битов на дюйм, или 4800 бит данных на дюйм.
Плотность обращения потока на жестких дисках значительно выше, но такое же улучшение плотности хранения наблюдается при использовании различных систем кодирования.
Ограниченная система определяется ограниченным набором «хороших» или «разрешенных» последовательностей, подлежащих записи или передаче. Ограниченное кодирование фокусируется на анализе ограниченных систем и разработке эффективных кодеров и декодеров, которые преобразуют произвольные пользовательские последовательности в ограниченные последовательности.
Дано подробное описание ограничивающих свойств последовательностей с ограниченной длиной.