Файл: Методы кодирования данных (Ключевые понятия кодирования данных).pdf

В первую очередь, среднее число двоичных элементарных сигналов, приходящихся в закодированном сообщении на одну букву исходного сообщения, не может быть меньше Н, где Н = - p₁log(p₁) – p₂log (p₂) - … - p_nlog (p_n) – энтропия опыта, состоящего в распознавании одной буквы текста (или, короче, просто энтропия одной буквы). Отсюда сразу следует, что при любом методе кодирования для записи длинного сообщения из М букв требуется не меньше чем МН двоичных знаков, и никак не может превосходить одного бита.

Если вероятности р₁, р₂, … …, р_n не все равны между собой, то Н < logn; ввиду чего естественно думать, что учет статистических закономерностей сообщения может дать возможность построить код более экономичный, чем наилучший равномерный код, требующий не менее Мlogn двоичных знаков для записи текста из М букв [10, c.94].

1.2 Классификация назначения и способы представления кодов

Коды можно классифицировать по разным признакам:

1. По основанию (количеству символов в алфавите): бинарные (двоичные m=2) и не бинарные (m № 2).

2. По длине кодовых комбинаций (слов): равномерные, если все кодовые комбинации имеют одинаковую длину и неравномерные, если длина кодовой комбинации не постоянна.

3. По способам передачи: последовательные и параллельные; блочные - данные сначала помещаются в буфер, а далее передаются в канал и бинарные непрерывные.

4. По помехоустойчивости: простые (примитивные, полные) - для передачи информации применяют все возможные кодовые комбинации (без избыточности); корректирующие (помехозащищенные) - для передачи сообщений используют не все, а лишь часть (разрешенных) кодовых комбинаций.

5. Исходя из назначения и применения условно выделяются следующие типы кодов [9, c.101].

Внутренние коды - это коды, применяемые внутри устройств. Это машинные коды, а также коды, основанные на применении позиционных систем счисления (двоичный, десятичный, двоично-десятичный, восьмеричный, шестнадцатеричный и др.) [9, c.105]. Самым распространенным кодом в ЭВМ является двоичный код, который дает возможность просто реализовать аппаратное устройство для хранения, обработки и передачи данных в двоичном коде. Он обеспечивает высокую надежность устройств и простоту выполнения операций над данными в двоичном коде. Двоичные данные, объединенные в группы по 4, образуют шестнадцатеричный код, который хорошо согласуется с архитектурой ЭВМ, работающей с данными кратными байту (8 бит) [14, c.11].

Коды для обмена данными и их передачи по каналам связи. Широкое распространение в ПК получил код ASCII (American Standard Code for Information Interchange). ASCII - это 7-битный код буквенно-цифровых и других символов. Т.к. ЭВМ работают с байтами, то 8-й разряд применяется для синхронизации или проверки на четность, или расширения кода. В ЭВМ фирмы IBM применяется расширенный двоично-десятичный код для обмена информацией EBCDIC (Extended Binary Coded Decimal Interchange Code). В каналах связи широко применяется телетайпный код МККТТ (международный консультативный комитет по телефонии и телеграфии) и его модификации (МТК и др.).

При кодировании данных для передачи по каналам связи, в том числе внутри аппаратным трактам, применяются коды, обеспечивающие максимальную скорость передачи данных, за счет их сжатия и устранения избыточности (например: коды Хаффмана и Шеннона-Фано), и коды обеспечивающие достоверность передачи данных, ввиду введения избыточности в передаваемые сообщения (например, групповые коды, Хэмминга, циклические и их разновидности) [14, c.45].

Коды для специальных применений - это коды, необходимые для решения специальных задач передачи и обработки данных. Примерами подобных кодов является циклический код Грея, который широко применяется в АЦП угловых и линейных перемещений. Коды Фибоначчи используются для построения быстродействующих и помехоустойчивых АЦП [13, c.99].

Исходя из используемых методов кодирования, применяют различные математические модели кодов, при этом наиболее часто используется представление кодов в виде: кодовых матриц; кодовых деревьев; многочленов; геометрических фигур и т.д. [7, c.56] Рассмотрим основные способы представления кодов.

Матричное представление кодов. Применяется для представления равномерных n - значных кодов. Для примитивного (полного и равномерного) кода матрица содержит n - столбцов и 2n - строк, т.е. код использует все сочетания. Для помехоустойчивых (корректирующих, обнаруживающих и исправляющих ошибки) матрица содержит n - столбцов (n = k+m, где k-число информационных, а m - число проверочных разрядов) и 2k - строк (где 2k - число разрешенных кодовых комбинаций). При больших значениях n и k матрица будет слишком громоздкой, при этом код записывается в сокращенном виде. Матричное представление кодов используется, например, в линейных групповых кодах, кодах Хэмминга и пр [12, c.45].

Представление кодов в виде кодовых деревьев. Кодовое дерево - связной граф, не содержащий циклов. Связной граф - граф, в котором для любой пары вершин существует путь, соединяющий эти вершины. Граф состоит из узлов (вершин) и ребер (ветвей), соединяющих узлы, расположенные на разных уровнях [11, c.70]. Для построения дерева равномерного двоичного кода выбирают вершину называемую корнем дерева (истоком) и из нее проводят ребра в следующие две вершины и т.д.

1.3 Сравнительный анализ методов кодирования данных

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

Ключевые методы кодирования данных представлены ниже.

Запись данных

Данные на магнитном носителе хранятся в аналоговой форме. В то же время сами данные представлены в цифровом виде, так как являются последовательностью нулей и единиц. При выполнении записи цифровая информация, поступая на магнитную головку, создает на диске магнитные домены соответствующей полярности. Если во время записи на головку поступает положительный сигнал, магнитные домены поляризуются в одном направлении, а если отрицательный — в противоположном. Когда меняется полярность записываемого сигнала, происходит также изменение полярности магнитных доменов [6, c.18].

Воспроизведение данных

Если во время воспроизведения головка регистрирует группу (или несколько групп) магнитных доменов одинаковой полярности, она не генерирует никаких сигналов; генерация происходит только тогда, когда головка обнаруживает изменение полярности положения доменов. Эти моменты изменения полярности называются сменой знака. Каждая смена знака приводит к тому, что считывающая головка выдает импульс напряжения; именно эти импульсы устройство регистрирует во время чтения данных. Но при этом считывающая головка генерирует не совсем тот сигнал, который был записан; на самом деле она создает ряд импульсов, каждый из которых соответствует моменту смены знака [6, c.24].

Кодер/декодер

Чтобы оптимальным образом расположить импульсы в сигнале записи, необработанные исходные данные пропускаются через специальное устройство, которое называется кодером/декодером. Это устройство преобразует двоичные данные в электрические сигналы, оптимизированные в аспекте размещения зон смены знака на дорожке записи. Во время считывания кодер/декодер выполняет обратное преобразование: восстанавливает из сигнала последовательность двоичных данных. Существуют различные методы кодирования данных, причем главной целью разработчиков было достижение максимальной эффективности и надежности записи и считывания информации [6, c.31].

Синхронизация данных

При работе с цифровыми данными особое значение приобретает синхронизация. Во время считывания или записи очень важно точно определить момент каждой смены знака. Если синхронизация отсутствует, то момент смены знака может быть определен неправильно, в результате чего неизбежна потеря или искажение информации [14, c.12]. Чтобы предотвратить это, работа передающего и принимающего устройств должна быть строго синхронизирована.

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

Поскольку количество зон смены знака, которые можно записать на диске, ограничено возможностями технологий производства носителей и головок, при разработке дисковых накопителей изобретаются такие способы кодирования данных, с помощью которых можно было бы уместить как можно больше битов данных в минимальное количество зон смены знака. При этом приходится учитывать то неизбежное обстоятельство, что часть из них все равно будет использоваться только для синхронизации [8, c.74].

В таблице 1 приведено соответствие между битами данных и зонами смены знака.

Таблица 1

Последовательность зон смены знака при записи по методу MFM

* T — смена знака есть; N — смены знака нет.

Кодирование с ограничением длины поля записи (RLL)

На сегодняшний день наиболее популярен метод кодирования с ограничением длины поля записи (Run Length Limited — RLL). Он позволяет разместить на диске в полтора раза больше информации, чем при записи по методу MFM, и в три раза больше, чем при FM-кодировании. При использовании этого метода происходит кодирование не отдельных битов, а целых групп, в результате чего создаются определенные последовательности зон смены знака, т.е. при записи по методу RLL одновременно кодируются целые группы битов [20, c.22].

Термин Run Length Limited (с ограничением длины пробега) составлен из названий двух основных параметров, которыми являются минимальное (длина пробега) и максимальное (предел пробега) число ячеек перехода, которые можно расположить между двумя зонами смены знака. Изменяя эти параметры, можно получать различные методы кодирования, но на практике используются только два из них: RLL 2,7 и RLL 1,7 [20, c.32].

Методы FM и MFM, в сущности, являются частными вариантами RLL. Так, например, FM-кодирование можно было бы назвать RLL 0,1, поскольку между двумя зонами смены знака может располагаться максимум одна и минимум нуль ячеек перехода. Соответственно метод MFM в этой терминологии можно было бы обозначить RLL 1,3, так как в этом случае между двумя зонами смены знака может располагаться от одной до трех ячеек перехода. Однако при упоминании этих методов обычно используются более привычные названия FM и MFM.

До последнего времени самым популярным был метод RLL 2,7, поскольку он позволял достичь высокой плотности записи данных (в 1,5 раза больше по сравнению с методом MFM) и достоверности (надежности) их воспроизведения. При этом соотношение размеров зон смены знака и участков с постоянной намагниченностью оставалось тем же, что и при методе MFM. Однако для накопителей очень большой емкости метод RLL 2,7 оказался недостаточно надежным. В большинстве современных жестких дисков высокой емкости используется метод RLL 1,7, который позволяет увеличить плотность записи в 1,27 раза по сравнению с MFM при оптимальном соотношении между размерами зон смены знака и участков с постоянной намагниченностью [19, c.81]. За счет некоторого снижения плотности записи (по сравнению с RLL 2,7) удалось существенно повысить надежность считывания данных. Это особенно важно, поскольку в накопителях большой емкости носители и головки уже приближаются к пределу возможностей современной технологии. И так как при разработке современных жестких дисков приоритет принадлежит надежности считывания данных, можно ожидать, что в ближайшем будущем метод RLL 1,7 достигнет наибольшего распространения.

В таблице 2 приведена схема кодирования по методу RLL 2,7, разработанная компанией IBM при создании кодеров/декодеров.

Таблица 2

Последовательность зон смены знака при записи по методу RLL 2,7

* T — смена знака есть; N — смены знака нет.

При внимательном изучении этой таблицы можно заметить, что кодировать, например, байт 00000001 нельзя, поскольку его нельзя составить из комбинации приведенных в таблице групп битов. Однако на практике при этом никаких проблем не возникает. Дело в том, что контроллер не оперирует байтами, а формирует сразу целые секторы записи. Поэтому, если ему попадается такой байт, он просто начинает искать подходящую для разбивки на группы комбинацию с учетом следующего байта последовательности. Затруднение может возникнуть только в том случае, если указанный байт последний в секторе [8, c.21]. В этой ситуации кодер, установленный в контроллере, просто дописывает в конец последнего байта несколько дополнительных битов. При последующем считывании они отбрасываются, и последний байт воспроизводится таким, каким он должен быть.