Файл: Методы кодирования данных (Основные принципы кодирования данных).pdf

Главная процедура, выполняемая над каждым элементом текстовых данных, это сопоставление символов. В процедуре сравнения символов основным моментом выступает неповторимость шифра (кода) любого символа и размер данного шифра (кода), а собственно метод кодировки фактически не важен. Чтобы закодировать какой-либо текст, применяются разнообразные таблицы перекодирования. Главное, чтобы для кодирования и последующего декодирования применялись одни и те же таблицы. Таблица перекодирования должна включать в свой состав формализованный определённым порядком список символов для кодирования, согласно которому выполняется перевод символа в двоичный код, а также обратная процедура. Наиболее распространёнными формами таблиц являются ДКОИ-8, ASCII, CP1251 и Unicode.

Рисунок 1. Фрагмент таблицы Unicode с «эмодзи»

Длина кода представления символа уже давно сформировалась как 8 бит (1 байт). И именно по этой причине один текстовый символ занимает один байт памяти компьютера. Соответственно, число вариантов (комбинаций) набора нулей и единиц при размере кода 8 бит будет два в восьмой степени, то есть 256. Это означает, одна таблица для перекодирования позволяет кодировать максимум 256 символов. Но если использовать код длиною в два байта, то это число соответственно возрастёт до 65536 символов.

У кодирования чисел и текста есть один общий момент, для возможности сравнения данных такого вида, различные числа (как и в случае символов) обязаны иметь разные коды. Главной отличительной особенностью числовой информации от символьной, является то, что числа кроме процедуры сравнения, подвергаются ещё самым разным арифметическим операциям (вычитание и сложение, умножение и так далее). Для выполнения этих действий в электронных вычислительных машинах служит двоичная позиционная система счисления^[8].

При кодировании текстовой информации каждый символ имеет своё двоичное число (код) от 00000000 до 11111111, что в десятичной системе соответствует числам от 0 до 255. Следует учитывать, что для кодирования букв русского алфавита существует пять разных кодовых таблиц (КОИ - 8, СР1251, СР866, Мас, ISO), при этом, если текст вводился с применением одной из таблиц, то он будет неправильно декодироваться при использовании другой таблицы.

Целые положительные числа представляются в виде двоичных (битовых, бинарных) последовательностей. Длина этих последовательностей зависит от величины числа. Например, для записи чисел он 0 до 255 достаточно 8 бит. Такую "порцию" информации принято называть байтом (byte). Для более длинных чисел выделяют по 16 (word), 32 (int), 64 (long) бита. Более длинные последовательности используются редко, поскольку с помощью 64 бит можно закодировать большинство чисел, используемых в человеческой практике^[9] (264=18446744073709551616).

---

Для представления отрицательных чисел задействуют отдельный (обычно старший) бит. Для представления действительных (дробных) чисел используется форма записи с плавающей точкой.

Рисунок 2. Представление дробного числа в виде байтовой последовательности

Методы кодирования, которые имеют статус самостоятельных, называются регистрационными методами кодирования. Методы, основанные на первоначальной классификации объектов, называются классификационными методами кодирования. В свою очередь, регистрационное кодирование делится на два типа:

• Порядковый тип.
• Серийно-порядковый тип.

Порядковый метод использует для кодирования наборы натуральных чисел. При этом все объекты множества получают свой порядковый номер. Данный метод кодировки имеет небольшую избыточность информации, даёт значительную долговечность классификатора и при этом очень прост, применяет самые короткие кодовые комбинации и позволяет обеспечить однозначное определение каждого классифицируемого объекта^[10]. Плюс ко всему, достаточно просто присвоить коды вновь появившемся при классификации объектам.

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

Серийно – порядковый метод кодирования основывается на применении в качестве кодов натуральных чисел, но с резервированием некоторых наборов таких чисел (фрагментам натурального ряда) для объектов классификации с совпадающими признаками. Во всех сериях чисел, кроме кодирования уже существующих объектов классификации, фиксируется некоторое число резервных кодов. Резервные коды могут быть расположены в середине или в окончании кодового набора. По этой причине, лучше использовать серийно-порядковый метод кодирования, чем просто порядковый. Он имеет все преимущества и недостатки порядкового метода кодировки. Но чаще всего он применяется совместно с классификационными методами кодирования, которые также делятся на два типа:

---

• Последовательное кодирование.
• Параллельное кодирование.

Последовательное кодирование основано на формировании кодов группировки или объекта с использованием кодов, идущих друг за другом, зависимых группировок, образованных иерархическим методом кодировки. Его главным достоинством можно считать логичность формирования кодов и значительную ёмкость. Но при этом, у него есть все недостатки, которыми обладает иерархический метод классификации, и у него ограничена возможность идентификации объекта.

При параллельном методе кодирования коды классификационной группировки или классифицируемого объекта формируются с применением свободных группировок, которые получены с помощью фасетного метода классификации.

В локальных сетях процедура логического кодирования данных изменяет поток бит созданного кадра МАС-уровня в последовательность символов, которые подлежат физическому кодированию для транспортировки по каналу связи. Для логического кодирования применяются различные схемы^[11]:

• 4B/5B — каждые 4 бита входного потока кодируются 5-битным символом. Получается двукратная избыточность, так как 24 = 16 входных комбинаций показываются символами из 25 = 32. Расходы по количеству битовых интервалов составляют: (5-4)/4 = 1/4 (25%). Такая избыточность разрешает определить ряд служебных символов, которые служат для синхронизации. Применяется в 100BaseFX/TX, FDDI
• 8B/10B — аналогичная схема (8 бит кодируются 10-битным символом) но уже избыточность равна 4 раза (256 входных в 1024 выходных).
• 5B/6B — 5 бит входного потока кодируются 6-битными символами. Применяется в 100VG-AnyLAN
• 8B/6T — 8 бит входного потока кодируются шестью троичными (T = ternary) цифрами (-,0,+). К примеру: 00h: +-00+-; 01h: 0+-+=0; Код имеет избыточность 36/28 = 729/256 = 2,85. Скорость транспортировки символов в линию является ниже битовой скорости и их поступления на кодирования. Применяется в 100BaseT4.
• Вставка бит — такая схема работает на исключение недопустимых последовательностей бит. Ее работу объясним на реализации в протоколе HDLC. Тут входной поток смотрится как непрерывная последовательность бит, для которой цепочка из более чем пяти смежных 1 анализируется как служебный сигнал (пример: 01111110 является флагом-разделителем кадра). Если в транслируемом потоке встречается непрерывная последовательность из 1, то после каждой пятой в выходной поток передатчик вставляет 0. Приемник анализирует входящую цепочку, и если после цепочки 011111 он видит 0, то он его отбрасывает и последовательность 011111 присоединяет к остальному выходному потоку данных. Если принят бит 1, то последовательность 011111 смотрится как служебный символ. Такая техника решает две задачи — исключать длинные монотонные последовательности, которые неудобные для самосинхронизации физического кодирования и разрешает опознание границ кадра и особых состояний в непрерывном битовом потоке.

---

Избыточность логического кодирования разрешает облегчить задачи физического кодирования — исключить неудобные битовые последовательности, улучшить спектральные характеристики физического сигнала и др.

Физическое/сигнальное кодирование пишет правила представления дискретных символов, результат логического кодирования в результат физические сигналы линии. Физические сигналы могут иметь непрерывную (аналоговую) форму — бесконечное число значений, из которого выбирают допустимое распознаваемое множество. На уровне физических сигналов вместо битовой скорости (бит/с) используют понятие скорость изменения сигнала в линии, которая измеряется в бодах (baud)^[12]. Под таким определением определяют число изменений различных состояний линии за единицу времени. На физическом уровне проходит синхронизация приемника и передатчика. Внешнюю синхронизацию не используют из-за дороговизны реализации еще одного канала. Много схем физического кодирования являются самосинхронизирующимися — они разрешают выделить синхросигнал из принимаемой последовательности состояний канала.

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

• Транзитное кодирование — информативным есть переход из одного состояния в другое
• Потенциальное кодирование — информативным есть уровень сигнала в конкретные моменты времени
• Полярное — сигнал одной полярности реализуется для представления одного значения, сигнал другой полярности для — другого. При оптоволоконной транспортировке вместо полярности используют амплитуды импульса
• Униполярное — сигнал одной полярности реализуется для представления одного значения, нулевой сигнал — для другого
• Биполярное — используется отрицательное, положительное и нулевое значения для представления трех состояний
• Двухфазное — в каждом битовом интервале присутствует переход из одного состояния в другое, что используется для выделения синхросигнала.

К наиболее популярным схемам кодирования, используемым в локальных сетях относятся^[13]:

AMI — Alternate Mark Inversion или же ABP — Alternate bipolare, биполярная схема, которая использует значения +V, 0V и -V. Все нулевые биты имеют значения 0V, единичные — чередующимися значениями +V, -V (рис.1). Применяется в DSx (DS1 — DS4), ISDN. Такая схема не есть полностью самосинхронизирующейся — длинная цепочка нулей приведет к потере синхронизации.

---

Рисунок 3. Цепочка данных в AMI

MAMI — Modified Alternate Mark Inversion, или же ASI — модифицированная схема AMI, импульсами чередующейся полярности кодируется 0, а 1 — нулевым потенциалом. Применяется в ISDN (S/T — интерфейсы).

HDB3 — High Density Bipolar 3, схема аналогичная AMI, но не допускает передачи цепочки более трех нулей. Вместо последовательности из четырех нулей вставляется один из четырех биполярных кодов.

Рисунок 4. Последовательность кода в HDB3

Manchester encoding (манчестерское кодирование) - двухфазное полярное/униполярное самосинхронизирующееся кодирование. Текущий бит узнается по направлению смены состояния в середине битового интервала: от -V к +V: 1. От +V к -V: 0. Переход в начале интервала может и не быть.

Рисунок 5. Цепочка данных в манчестерском кодировании

Манчестерское кодирование представляет собой метод модуляции данных, который может применяться во многих ситуациях, но особенно полезен при двоичной передаче информации на основе аналоговых, радиочастотных, оптических, высокоскоростных цифровых или дальних цифровых сигналов.

Синхронизация сигналов является основным преимуществом манчестерского кодирования. Она обеспечивает более высокую надежность с той же скоростью передачи данных по сравнению с другими методами^[14]. Но манчестерское кодирование также имеет некоторые недостатки. Например, оно потребляет больше полосы пропускания, чем исходный сигнал.

Манчестерский код содержит частые переходы уровня, которые позволяют приемнику извлекать синхронизирующий сигнал с помощью цифровой фазовой блокированной петли (DPLL) и правильно декодировать значение и синхронизацию каждого бита. Чтобы обеспечить надежную работу с использованием DPLL, передаваемый бит-поток должен содержать высокую плотность бит-переходов. Все виды кодов гарантируют это, позволяя принимающему DPLL правильно извлекать тактовый сигнал.

Двухфазный манчестерский код может потреблять примерно вдвое большую ширину полосы исходного сигнала (20 МГц). Это штраф за введение частых переходов. Для локальной сети 10 Мбит/с спектр сигналов лежит между 5 и 20 МГц. Манчестерское кодирование используется в качестве физического уровня локальной сети Ethernet, где дополнительная пропускная способность не является существенной проблемой для передачи коаксиального кабеля. Ограниченная пропускная способность кабеля CAT5e потребовала более эффективного метода кодирования для передачи 100 Мбит/с с использованием кода MLT 4b/5b. Это использует три уровня сигнала (вместо двух уровней, используемых в манчестерском кодировании), и следовательно, сигнал 100 Мбит/с занимает только полосу пропускания 31 МГц. Gigabit Ethernet использует пять уровней и кодирование 8b/10b, чтобы обеспечить еще более эффективное использование ограниченной пропускной способности кабеля, передавая 1 Гбит/с в полосе пропускания 100 МГц.

---