Файл: Методы кодирования данных (Сущность теории кодирования, ее цели и задачи).pdf

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

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

---

1) Определение объёма информации, подлежащей кодированию.

2) Классификация и систематизация информации.

3) Выбор системы кодирования и разработка кодовых обозначений.

4) Непосредственное кодирование

1.3 Классификация методов кодирования

Одним из видов кодирования является арифметическое кодирование.

Пусть задано конечное множество A = {a₁, a₂ … a_n}, которое называется алфавитом [1].

Элементы алфавита называются буквами. Последовательность букв называется словом. Множество слов в алфавите А обозначается А*. Если слово α = a₁, a₂... а_к, то k - длина слова.

Если а = a₁, a₂ , то a₁ называется началом или префиксом слова, а a₂ -концом или постфиксом слова.

Алфавитное, или побуквенное, кодирование задается схемой (таблицей кодов),δ:

Приведем следующий пример. Рассмотрим алфавиты А:={0,1,2,3,4,5,6,7,8,9}, B:={0,1} и таблицу кодов δ:

0–0	5–101	Эта схема однозначна, но декодирование не является однозначным, например Fδ (333) = 111111 = = Fδ (77), и, значит, невозможно однозначное декодирование.
1–1	6–110
2–10	7–111
3–11	8–1000
4–100	9–1001.

С другой стороны, таблица кодов δ, известная как двоично-десятичное кодирование, допускает однозначное декодирование.

0–0000	5–0101
1–0001	6–0110
2–0010	7–0111
3–0011	8–1000
4–0100	9–1001

Таким образом, очевидно, что не всякое кодирование дает возможность восстановить исходную информацию.

Введем следующие два понятия. Разделимое кодирование – такое, что любое слово, состоящее из элементарных кодов, единственным образом разлагается на элементарные коды. Очевидно, что двоично-десятичный код является разделимым.

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

A = {a,b}, B = {0,1}, δ = {a – 0, b – 01}.

---

Следовательно, свойство быть префиксной является достаточным, но не является необходимым для разделимости кода (хотя префиксная схема всегда является разделимой).

Для получения разделимой схемы алфавитного кодирования необходимо, чтобы длины элементарных кодов удовлетворяли определенному соотношению, известному как неравенство Макмиллана:

Если числа l_1,l_2, …, l_n , соответствующие длинам элементарных кодов β₁, β_2, …, β_n , удовлетворяют неравенству:

то существует разделимая схема алфавитного кодирования

Примером является азбука Морзе, которая задается таблицей алфавитного кодирования, где 0 называется точкой, а 1 - тире.

A – 01	H – 0000	O – 111	V – 0001
B – 1000	I – 00	P – 0110	W – 011
C – 1010	J – 0111	Q – 1101	X – 1001
D – 100	K – 101	R – 010	Y – 1011
E – 0	L – 0100	S – 000	Z – 1100
F – 0010	M – 11	T – 1
G – 110	N – 10	U – 001

Проверим выполнение неравенства Макмиллана для азбуки Морзе:

4 · (1/4) + 12 · (1/16) + 8 · (1/8) + 2 · (1/2) = 3 + 6/8 > 1.

Эта схема кодирования не является разделимой, так как неравенство Макмиллана для нее не выполнено. Заметим, что в азбуке Морзе имеются дополнительные элементы - паузы между буквами и словами, что все же позволяет разделить текст для декодирования. Манчестерское кодирование

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

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

---

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

Асинхронные методы передачи данных представляют собой наиболее старый способ связи. Они оперируют не с фреймами, а с отдельными символами, которые представлены байтами со стартстоповыми символами (рис.1).

Рис.1. Асинхронная передача на уровне байтов

При использовании асинхронных методов передачи применяются стандартные наборы символов, например широко известная кодировка ASCII (American Standard Code for Information Interchange), так как первые 32 кода этого набора являются специальными, которые не отображаются на дисплее или принтере, то они могут использоваться для управления режимом обмена данными (рис.2). В самих пользовательских данных, которые представляют собой буквы, цифры, а также такие знаки, как @, #, $ и подобные, специальные символы не встречаются, так что проблема их отделения от пользовательских данных решается достаточно тривиально.

Рис.2. Код ASCII (American Standard Code for Information Interchange)

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

Синхробиты

Служебная информация

Данные

Контрольная сумма

Рис.3. Структура кадра при использовании синхронных методов передачи

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

Современные способы передачи данных в телекоммуникационных сетях используют два основных метода синхронизации:

---

• символьно-ориентированный (байт-ориентированный);
• бит-ориентированный.

Главное различие между ними заключается в методе синхронизации символов и кадров.

ГЛАВА 2. Прикладные аспекты методов кодирования

2.1. Применение специальных методов кодирования информации при передаче данных по волоконно-оптическим линям связи

Специфика природы сигнала в волоконном световоде начинает проявляться на скоростях передачи данных порядка 10 Гбит/с в одном частотном канале. В этом случае на передачу данных начинают оказывать значительное воздействие так называемые нелинейные эффекты. Их отличительной особенностью является то, что сила их воздействия увеличивается с ростом мощности сигнала, что отличает их от других, «линейных», эффектов. В информационном плане канальные нелинейности проявляются зависимостью количества ошибок при передаче информации от вида самой информации – так называемым паттерн-эффектом (patterning effect). В этом случае в канале наблюдается неравномерность статистики ошибок по элементарным битовым последовательностям – паттернам.

Такой характер искажений сигнала позволяет в качестве средств кодирования использовать не только корректирующие коды (forward error correction, FEC-коды), но также и коды с ограничениями (constrained codes), направленные на снижение в сообщении количества наиболее подверженных ошибкам паттернов. Данный вид кодов было предложено применять в оптике. И хотя набор паттернов, подлежащих подавлению, варьируется в зависимости от конкретной статистики ошибок, в большинстве случаев в бинарных каналах максимальную вероятность ошибки имеют паттерны 101 и 010. Ниже будет рассмотрен более общий, адаптивный подход, учитывающий сложную статистику ошибок; также будет проведён анализ того, при каких условиях использование предложенного кода улучшает качество работы телекоммуникационной системы.

Адаптивным блочным кодом называется ограниченный код, удаляющий из сообщения паттерны, наиболее подверженные возникновению в них ошибок во время передачи по каналу с паттерн-эффектом. Набор паттернов определяется исходя из статистики ошибок в канале связи.

---