Длина тиража ограничена

Кодирование с ограничением длины прогона или RLL- кодирование - это метод линейного кодирования , который используется для отправки произвольных данных по каналу связи с ограничениями полосы пропускания . Коды RLL определяются четырьмя основными параметрами: m , n , d , k . Первые два, m / n , относятся к скорости кода, а оставшиеся два определяют минимальное d и максимальное k количество нулей между последовательными единицами. Это используется как в телекоммуникационных системах, так и в системах хранения, которые перемещают носитель мимо фиксированной записывающей головки .

В частности, 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-х годов.

Необходимость кодирования RLL [ править ]

На жестком диске информация представлена ​​изменениями направления магнитного поля на диске, а на магнитных носителях результат воспроизведения пропорционален плотности перехода потока. В компьютере информация представлена ​​напряжением на проводе. Отсутствие напряжения на проводе относительно определенного уровня земли будет двоичным нулем, а положительное напряжение на проводе относительно земли представляет собой двоичное значение. Магнитная среда, с другой стороны, всегда несет магнитный поток - либо «северный» полюс, либо «южный» полюс. Чтобы преобразовать магнитные поля в двоичные данные, необходимо использовать некоторый метод кодирования для преобразования между ними.

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

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

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

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

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

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

История [ править ]

Все коды, используемые для записи на магнитные диски, имеют ограниченную длину пробегов без переходов и поэтому могут быть охарактеризованы как коды RLL. Самым ранним и простейшим вариантам были даны определенные имена, такие как модифицированная частотная модуляция (MFM), а название «RLL» обычно используется только для более сложных вариантов, которым не даны такие конкретные имена, но этот термин технически применим ко всем.

Первым кодом "RLL", используемым в жестких дисках, был RLL (2,7), разработанный инженерами IBM и впервые коммерчески использованный в 1979 году на IBM 3370 DASD , ^{[1] [2] [3]} для использования с мэйнфреймами серии 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 - это минимальная и максимальная допустимая длина цикла. Для получения дополнительной информации о технологиях хранения полезны ссылки, цитируемые в этой статье. ^{[4] [5]}

Технический обзор [ править ]

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

FM: (0,1) RLL [ править ]

Обычно термин «код 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

GCR: (0,2) RLL [ править ]

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

Там , где это возможно (11 из 16 кодов), битовая комбинация abcdкодируется префиксом с дополнением : . В 5 случаях, когда это нарушит одно из правил ( или ), код, начинающийся с 11, заменяется ( , где e = a ∨ d ).aabcd000dab0011bea

Пример:

Данные: 0010 1101 0001 1000Закодировано: 10010011011101111010

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

MFM: (1,3) RLL [ править ]

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

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

Здесь «x» - это дополнение к предыдущему закодированному биту (который также является предыдущим битом данных). За исключением битов часов - этого бита «x» и «0» в коде «01» - это то же самое, что и таблица FM, и именно так этот код получил свое название. Вставленные тактовые биты равны 0, за исключением двух 0 битов данных.

Пример:

Данные: 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 [ править ]

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

Пример:

Данные: 0 0 1 0 1 1 0 1 0 0 0 1 1 0Кодируется: 101010101001000000001

(2,7) RLL [ править ]

(2,7) RLL является лимитирующим ¹ / ₂ - код, отображение п бит данных на 2 п бит на диске, как MFM, а потому , что минимальная длина последовательности составляет 50% больше (3 раза бита вместо 2), биты могут быть записаны быстрее, обеспечивая на 50% более высокую эффективную плотность данных. Кодирование выполняется в 2-, 3- или 4-битных группах.

Western Digital WD5010A, WD5011A, WD50C12

Seagate ST11R, IBM

Perstor Systems ADRC

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

Пример:

Данные: 1 1 0 1 1 0 0 1 1Закодировано: 1000 001000 00001000

DC-free (1,7) RLL [ править ]

Существует также альтернативное (1,7) кодирование RLL, которое иногда используется, чтобы избежать смещения постоянного тока (что помогает при отправке сигнала на большие расстояния или с некоторыми типами носителей записи).

Здесь «x» - это дополнение к предыдущему закодированному биту (т.е. 1, если предыдущий бит был 0, и 0, если предыдущий бит был 1).

Пример:

Данные: 0 1 0 0 1 1 0 1 0 1Зашифровано: 010101 000 000 010

HHH (1,13) [ править ]

Код HHH (1,13) - это код со скоростью 2/3, разработанный тремя исследователями IBM (Hirt, Hassner и Heise) для использования на физическом уровне IrDA VFIR со скоростью 16 МБ / с . ^[7] В отличие от магнитного кодирования, это предназначено для инфракрасного передатчика, где бит 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–0 пар - 000 101 010 101 000.

Этот код ограничивает плотность те , чтобы между ¹ / ₁₂ и ¹ / ₃ , с в среднем 25,8%.

Примеры [ править ]

Например, закодируем битовую последовательность 10110010 разными кодировками

Плотности [ править ]

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

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

См. Также [ править ]

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

Ссылки [ править ]

Эта статья основана на материалах, взятых из Free On-line Dictionary of Computing до 1 ноября 2008 г. и включенных в соответствии с условиями «перелицензирования» GFDL версии 1.3 или новее.

Внешние ссылки [ править ]

• Цифровая запись на магнитную ленту