Файл: Методы кодирования данных (ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ).pdf

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

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

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

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

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

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

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

Пусть задано конечное множество 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. Ниже будет рассмотрен более общий, адаптивный подход, учитывающий сложную статистику ошибок; также будет проведён анализ того, при каких условиях использование предложенного кода улучшает качество работы телекоммуникационной системы.

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

---

Для подавления паттернинга в этом случае определим для каждого возможного двоичного кодового слова длины n величину:

где Ti – элементарные паттерны, из которых состоит данное кодовое слово.

Например кодовое слово 0110010 состоит из элементарных триплетов 011, 110, 100, 001 и 010. Данная величина фактически является вероятностью того, что внутренние биты кодового слова будут переданы без ошибок. Такая величина определяется для каждого кодового слова, количество которых равно, очевидно, 2ⁿ. Получается совокупность пар (i; P_ne(i)), которая упорядочивается в порядке убывания величины P_ne(i). Такой подход позволяет получить кодовую таблицу W, первые элементы которой являются наиболее пригодными кодовыми словами для передачи по линии, поскольку обладают максимальной вероятностью безошибочной передачи.

Перед тем как начать кодирование, определяется, код с какой кодовой скоростью m/n необходимо получить. В данном случае m – количество битов исходного сообщения, соответствующих одному кодовому слову длины n в закодированном сообщении. Далее будем обозначать за A(m,n) адаптивный код со скоростью m/n. Чем ниже кодовая скорость (и, соответственно, больше кодовая избыточность), тем меньше кодовых слов из таблицы W будет задействовано в кодировании а, значит, будут задействованы только самые надёжные кодовые слова, порождающие минимум ошибок при их трансмиссии по оптоволоконному каналу связи. Кодирование ведётся путём поиска по таблице (table lookup), в результате чего из исходных кодовых слов размера m получаются кодовые слова, каждое из которых лежит среди первых 2^m элементов таблицы W.

Декодируется сообщение путём поиска по обратной таблице W^-1, ставящей в соответствие кодовому слову его индекс в «прямой» таблице W.

Код был применён к результатам моделирования линии в 5 каналов каждый по 40 Гбит/с WDM RZ-OOK SMF/DCF с гибридным усилением. Статистика ошибок в сигнале после прохождения им 4500 км по линии имеет вид, показанный гистограммой на рис.4.

Рис.4. Гистограмма статистики ошибок

Красные столбцы представляют собой триплетную частоту ошибок, а голубые – частоту ошибок по квинтуплетам. Например, голубые столбцы, окружающие столбец 101, соответствуют квинтуплетам 01010, 01011, 11010, 11011, если их просматривать слева направо.

В ходе эксперимента были построены 16- и 24-битные адаптивные коды, результаты для расстояния в 3400 км и в 6400 км приведены на рис.5.

---