Продолжительность ограничена
 | Эта статья нуждается в дополнительных цитатах для проверки . ( июнь 2023 г. ) |
Кодирование с ограничением длины серии или 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-х годов.
Необходимость кодирования RLL
[ редактировать ]На жестком диске информация представлена изменениями направления магнитного поля на диске, а на магнитных носителях выходной сигнал воспроизведения пропорционален плотности перехода магнитного потока. В компьютере информация представлена напряжением на проводе. Никакое напряжение на проводе по отношению к определенному уровню земли не будет представлять собой двоичный ноль, а положительное напряжение на проводе по отношению к земле представляет собой двоичную единицу. С другой стороны, магнитные носители всегда несут магнитный поток – либо «северный» полюс, либо «южный» полюс. Чтобы преобразовать магнитные поля в двоичные данные, необходимо использовать какой-то метод кодирования для перевода между ними.
Один из простейших практических кодов, модифицированный «без возврата к нулю с инвертированием» ( 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» указывает на то, что магнитное поле на диске не меняется в течение этого интервала времени.
ФМ: (0,1) РЛЛ
[ редактировать ]Обычно термин «код RLL» используется для обозначения более сложных кодировок, но исходный код частотной модуляции , также называемый дифференциальным манчестерским кодированием , можно рассматривать как простой код RLL со скоростью 1/2. Добавленные биты 1 называются тактовыми битами.
| Данные | Закодированный |
|---|---|
| 0 | 10 |
| 1 | 11 |
Пример:
Data: 0 0 1 0 1 1 0 1 0 0 0 1 1 0 Encoded: 1010111011111011101010111110 Clock: 1 1 1 1 1 1 1 1 1 1 1 1 1 1
ГКЛ: (0,2) РЛЛ
[ редактировать ]Увеличив максимальную длину серии до двух соседних нулевых битов, скорость передачи данных можно повысить до 4/5. Это оригинальный вариант записи с групповым кодом IBM.
|
|
Там, где это возможно (11 из 16 кодов), битовая комбинация abcd кодируется путем добавления к нему префикса : aabcd. В 5 случаях, когда это нарушает одно из правил ( 000d или ab00), подставляется код, начинающийся с 11 ( 11bea, где е = а ∨ d ).
Пример:
Data: 0010 1101 0001 1000 Encoded: 10010011011101111010
Обратите внимание, что для соответствия определению (0,2) RLL недостаточно только того, чтобы каждый 5-битный код содержал не более двух последовательных нулей, но также необходимо, чтобы любая пара 5-битных кодов, объединенных последовательно, не содержать более двух последовательных нулей. То есть между последним битом первого кода и первым битом второго кода не должно быть более двух нулей для любых двух произвольно выбранных кодов. Это необходимо, поскольку для любого кода RLL ограничения длины серии (в данном случае 0 и 2) применяются ко всему модулированному потоку битов, а не только к его компонентам, которые представляют собой дискретные последовательности простых битов данных. (Это правило должно выполняться для любой произвольной пары кодов без исключения, поскольку входные данные могут представлять собой любую произвольную последовательность битов.) Приведенный выше код IBM GCR соответствует этому условию, поскольку максимальная длина серии нулей в начале любых 5 -битовый код равен единице, и аналогичным образом максимальная длина серии в конце любого кода равна единице, что делает общую длину серии равной двум на стыке соседних кодов. (Пример максимальной длины серии, возникающей между кодами, можно увидеть в приведенном выше примере, где код данных «0010» заканчивается нулем, а код следующих данных «1101» начинается с нуля. образуя серию из двух нулей на стыке этих двух 5-битных кодов.)
МФМ: (1,3) РЛЛ
[ редактировать ]Модифицированная частотная модуляция становится интересной, поскольку ее особые свойства позволяют записывать биты на магнитный носитель с удвоенной плотностью произвольного потока битов. Существует предел того, насколько близкими по времени переходы потока могут быть для считывающего оборудования, чтобы обнаружить их, и это ограничивает то, насколько точно биты могут быть записаны на носителе: в худшем случае, при произвольном потоке битов, есть два последовательных бита, который создает два последовательных перехода потока во времени, поэтому биты должны быть расположены достаточно далеко друг от друга, чтобы между этими переходами потока было достаточно времени, чтобы читатель мог их обнаружить. Но этот код накладывает ограничение d = 1, т.е. между каждыми двумя единицами должен быть минимум один ноль. Это означает, что в худшем случае переходы потока отличаются друг от друга на два бита, поэтому биты могут быть в два раза ближе друг к другу, чем в произвольном потоке битов, не превышая при этом возможности считывателя.
Эта удвоенная плотность записи компенсирует 1/2 скорости кодирования этого кода (для представления одного бита реальной информации требуется два бита) и делает его эквивалентным коду со скоростью 1.
Кодировка очень похожа на кодировку FM.
| Данные | Закодированный |
|---|---|
| 0 | х0 |
| 1 | 01 |
Где «x» — это дополнение ранее закодированного бита потока.
За исключением того, что тактовые биты не всегда равны единице, это то же самое, что и таблица FM, и именно поэтому этот код получил свое название. Вставленные тактовые биты равны 0, за исключением двух нулевых битов данных.
В сочетании с предыдущим битом n-1 получается результирующая таблица кодирования для каждого бита данных n .
| Данные ( н ) | Данные ( n-1 ) | Закодированный ( n ) |
|---|---|---|
| 0 | 0 | 10 |
| 1 | 00 | |
| 1 | 0 | 01 |
| 1 | 01 |
Пример:
Data: 0 0 1 0 1 1 0 1 0 0 0 1 1 0 Encoded: x010010001010001001010010100 Clock: x 1 0 0 0 0 0 0 0 1 1 0 0 0
(1,7) РЛЛ
[ редактировать ](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] При кодировании по таблице ниже необходимо использовать самое длинное (последнее в таблице) совпадение; это ситуации обработки исключений, когда применение предыдущих правил приведет к нарушению ограничений кода.
| Данные | Закодированный |
|---|---|
| 00 | 101 |
| 01 | 100 |
| 10 | 001 |
| 11 | 010 |
| 00 00 | 101 000 |
| 00 01 | 100 000 |
| 10 00 | 001 000 |
| 10 01 | 010 000 |
Пример:
Data: 0 0 1 0 1 1 0 1 0 0 0 1 1 0 Encoded: 101 001 010 100 100 000 001
(2,7) РЛЛ
[ редактировать ](2,7) RLL – скорость- 1 ⁄ кода , отображающий n бит данных на 2 n бит на диске, как и MFM, но поскольку минимальная длина прогона на 50 % больше (3 бита вместо 2), биты можно записывать быстрее, достигая 50 % более высокая эффективная плотность данных. Кодирование выполняется 2-, 3- или 4-битными группами.
Western Digital WD5010A, WD5011A, WD50C12
| Данные | (2,7) RLL-кодирование |
|---|---|
| 11 | 1000 |
| 10 | 0100 |
| 000 | 100100 |
| 010 | 000100 |
| 011 | 001000 |
| 0011 | 00001000 |
| 0010 | 00100100 |
Seagate ST11R, IBM
| Данные | (2,7) RLL-кодирование |
|---|---|
| 11 | 1000 |
| 10 | 0100 |
| 000 | 000100 |
| 010 | 100100 |
| 011 | 001000 |
| 0011 | 00001000 |
| 0010 | 00100100 |
Перстор Системс ADRC
| Данные | (2,7) RLL-кодирование |
|---|---|
| 11 | 1000 |
| 10 | 0100 |
| 000 | 100100 |
| 010 | 000100 |
| 001 | 001000 |
| 0111 | 00001000 |
| 0110 | 00100100 |
Закодированные формы начинаются не более чем с 4 и заканчиваются не более чем с 3 нулевых битов, что дает максимальную длину серии 7.
Пример:
Data: 1 1 0 1 1 0 0 1 1 Encoded: 1000 001000 00001000
ЧЧЧ(1,13)
[ редактировать ]Код HHH(1,13) — это код со скоростью 2/3, разработанный тремя исследователями IBM (Хиртом, Хасснером и Хейзом) для использования на физическом уровне IrDA VFIR со скоростью 16 МБ/с. [8] В отличие от магнитного кодирования, оно предназначено для инфракрасного передатчика, где бит 0 означает «выключено», а бит 1 означает «включено». Поскольку 1 бит потребляет больше энергии для передачи, это предназначено для ограничения плотности 1 бита до уровня менее 50%. В частности, это код RLL (1,13|5), где последняя цифра 5 указывает на дополнительное ограничение, состоящее в том, что существует не более 5 последовательных пар бит «10».
| Данные | Закодированный |
|---|---|
| 00 | 010 |
| 01 | 001 |
| 10 | 100 |
| 11 | 101 |
| 01 10 | 001 000 |
| 01 11 | 010 000 |
| 11 10 | 101 000 |
| 11 11 | 100 000 |
| 00 11 00 | 010 000 000 |
| 00 11 01 | 001 000 000 |
| 10 11 00 | 100 000 000 |
| 10 11 01 | 101 000 000 |
| 00 11 10 11 | 010 000 000 000 |
| 10 11 10 11 | 100 000 000 000 |
Первые восемь строк описывают стандартный (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 разными кодировками.
| Кодирование | Данные | Закодированный |
|---|---|---|
| РЛЛ(0,1) | 10110010 | 1110111110101110 |
| РЛЛ(0,2) | 1011 0010 | 01011 10010 |
| РЛЛ(1,3) | 10110010 | 0100010100100100 |
| РЛЛ(1,7) | 10 11 00 10 | 001 010 101 001 |
| РЛЛ(2,7) | 10 11 0010 | 0100 1000 00100100 |
Плотность
[ редактировать ]Предположим, что магнитная лента может содержать до 3200 разворотов магнитного потока на дюйм. Модифицированная частотная модуляция, или (1,3)-кодирование RLL, сохраняет каждый бит данных как два бита на ленте, но поскольку между любыми битами 1 (реверс потока) гарантированно находится один бит 0 (без реверса потока), то На ленте можно хранить 6400 закодированных бит на дюйм или 3200 бит данных на дюйм. Кодировка RLL (1,7) также может хранить на ленте 6400 закодированных битов на дюйм, но поскольку для хранения 2 битов данных требуется всего 3 закодированных бита, это составляет 4267 битов данных на дюйм. Кодирование RLL (2,7) требует 2 закодированных бита для хранения каждого бита данных, но поскольку между любыми битами 1 гарантированно находятся два 0-бита, то на ленте можно хранить 9600 закодированных битов на дюйм, или 4800 бит данных на дюйм.
Плотность обращения потока на жестких дисках значительно выше, но такое же улучшение плотности хранения наблюдается при использовании различных систем кодирования.
См. также
[ редактировать ]- Кодирование 8b/10b
- Проскальзывание бита
- Модуляция от восьми до четырнадцати и EFMplus представляют собой коды RLL без постоянного тока (2,10), используемые на компакт-дисках и DVD-дисках соответственно.
- Коды исправления ошибок
- Код линии
- Модуляция
- Физический уровень
- ПРМЛ
- Кодирование длины серии
- Самосинхронизирующийся код и битовая синхронизация
- Исходное кодирование
Ссылки
[ редактировать ]- ^ Кес Шухамер Имминк (октябрь 2022 г.). «Инновации в ограниченных кодах» . Журнал коммуникаций IEEE . 60 (10): 20–24. дои : 10.1109/MCOM.002.2200249 .
Ограниченная система определяется ограниченным набором «хороших» или «разрешенных» последовательностей, подлежащих записи или передаче. Ограниченное кодирование фокусируется на анализе ограниченных систем и разработке эффективных кодеров и декодеров, которые преобразуют произвольные пользовательские последовательности в ограниченные последовательности.
- ^ Четверть века инноваций в дисковых файлах , Журнал исследований и разработок IBM.
- ^ П. А. Франашек (1972), «Кодирование переменной длины с ограничением длины серии и ограничением распространения ошибок», патент США 3,689,899 .
- ^ Пять десятилетий новаторства в отрасли жестких дисков , DISK/TREND, Inc., издатель исследований рынка мировой индустрии жестких дисков и систем хранения данных. веб.архив.орг.
- ^ Кес Шухамер Имминк (декабрь 1990 г.). «Последовательности с ограниченной длиной» . Труды IEEE . 78 (11): 1745–1759. дои : 10.1109/5.63306 .
Дано подробное описание ограничивающих свойств последовательностей с ограниченной длиной.
- ^ Кис А. Шухамер Имминк (ноябрь 2004 г.). Коды для систем массового хранения данных (Второе полностью переработанное издание). Эйндховен, Нидерланды: Издательство Shannon Foundation. ISBN 90-74249-27-2 . Проверено 23 августа 2015 г.
- ^ Ми, К. Денис; Дэниел, Эрик Д. (1996). Справочник по магнитному хранению (2-е изд.). МакГроу Хилл. ISBN 0-07-041275-8 .
- ^ Хирт, Уолтер; Хасснер, Мартин; Хейз, Найлс (февраль 2001 г.), «IrDA-VFIr (16 Мбит/с): код модуляции и конструкция системы» , IEEE Personal Communications , 8 (1): 58–71, doi : 10.1109/98.904900 .