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

ВВЕДЕНИЕ

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

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

Кодирование Хаффмана является простым алгоритмом для построения кодов переменной длины, имеющих минимальную среднюю длину. Этот весьма популярный алгоритм служит основой многих компьютерных программ сжатия текстовой и графической информации. Некоторые из них используют непосредственно алгоритм Хаффмана, а другие берут его в качестве одной из ступеней многоуровневого процесса сжатия. Метод Хаффмана производит идеальное сжатие (то есть, сжимает данные до их энтропии), если вероятности символов точно равны отрицательным степеням числа 2. Алгоритм начинает строить кодовое дерево снизу вверх, затем скользит вниз по дереву, чтобы построить каждый индивидуальный код справа налево (от самого младшего бита к самому старшему). Начиная с работ Д. Хаффмана 1952 года, этот алгоритм являлся предметом многих исследований.

Коды Хаффмана преподаются во всех технических ВУЗах мира и, кроме того, входят в программу для углубленного изучения информатики в школе.

Поэтому изучение кодирования информации и методов кодирования, в частности метода кодирования Хаффмана является актуальным.

Объект исследования: кодирование и методы кодирования информации.

Предмет исследования: программное приложение, показывающие основные принципы кодирования на примере метода кодирования Хаффмана.

Целью курсовой работы является изучения методов кодирования информации в частности метод кодирования Хаффмана и применить их в процессе программной реализации этого метода. Данная цель обусловила выделение следующих задач:

1) рассмотреть основные понятия и принципы кодирования информации;

2) изучить метод кодирования Хаффмана,

3) рассмотреть практические примеры кодирования данных.

Объект исследования - кодирование.

Предмет исследования - методы кодирования данных.

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

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

---

ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ КОДИРОВАНИЯ ДАННЫХ

1.1 Понятие кодирование

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

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

• 4B/5B — каждые 4 бита входного потока кодируются 5-битным символом (табл 1). Получается двукратная избыточность, так как 2⁴ = 16 входных комбинаций показываются символами из 2⁵ = 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; Код имеет избыточность 3⁶/2⁸ = 729/256 = 2,85. Скорость транспортировки символов в линию является ниже битовой скорости и их поступления на кодирования. Применяется в 100BaseT4.
• Вставка бит — такая схема работает на исключение недопустимых последовательностей бит. Ее работу объясним на реализации в протоколе HDLC. Тут входной поток смотрится как непрерывная последовательность бит, для которой цепочка из более чем пяти смежных 1 анализируется как служебный сигнал (пример: 01111110 является флагом-разделителем кадра). Если в транслируемом потоке встречается непрерывная последовательность из 1, то после каждой пятой в выходной поток передатчик вставляет 0. Приемник анализирует входящую цепочку, и если после цепочки 011111 он видит 0, то он его отбрасывает и последовательность 011111 присоединяет к остальному выходному потоку данных. Если принят бит 1, то последовательность 011111смотрится как служебный символ. Такая техника решает две задачи — исключать длинные монотонные последовательности, которые неудобные для самосинхронизации физического кодирования и разрешает опознание границ кадра и особых состояний в непрерывном битовом потоке.

---

Таблица 1 — Кодирование 4В/5В

Входной символ	Выходной символ
0000 (0)	11110
0001 (1)	01001
0010 (2)	10100
0011 (3)	10101
0100 (4)	01010
0101 (5)	01011
0110 (6)	01110
0111 (7)	01111
1000 (8)	10010
1001 (9)	10011
1010 (A)	10110
1011 (B)	10111
1100 (C)	11010
1101 (D)	11011
1110 (E)	11100
1111 (F)	11101

Служебный символ	Выходной символ
Idle	11111
J	11000
K	10001
T	01101
R	11001
S	11001
Quiet	00000
Halt	00100

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

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

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

---

1.2 Популярные схемы кодирования, которые применяются в локальных сетях

AMI/ABP

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

Рисунок 1 – MAMI

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

B8ZS

B8ZS — Bipolar with 8 Zero Substitution, схема аналогичная AMI, но для синхронизации исключает цепочки 8 и более нулей ( за счет вставки бит).

HDB3

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

Рисунок — 2 Манчестерское кодирование

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

Рисунок — 3

Дифференциальное манчестерское кодирование

Differential manchester encoding — двухфазное полярное/униполярное самосинхронизирующиеся код. Текущий бит узнается по наличию перехода в начале битового интервала (рис. 4.1), например 0 — есть переход (Вертикальный фрагмент), 1 — нет перехода (горизонтальный фрагмент). Можно и наоборот определять 0 и 1.В середине битового интервала переход есть всегда. Он нужен для синхронизации. В Token Ring применяется измененная версия такой схемы, где кроме бит 0 и 1 определенны также два бита j и k (Рис. 4.2). Здесь нет переходов в середине интервала. Бит К имеет переход в начале интервала, а j — нет.

Рисунок — 4.1 и 4.2

---

MLT-3

Трехуровневое кодирование со скремблированием который не самосинхронизуется. Используются уровни (+V, 0, -V) постоянные в линии каждого битового интервала. При передаче 0 значения не меняются, при передаче 1 — меняются на соседние по цепочке +V, 0, -V, 0, +V и тд. (рис. 5). Такая схема является усложнонным вариантом NRZI. Применяется в FDDI и 100BaseTX.

Рисунок — 5 NRZ и NRZI

NRZ — Non-return to zero (без возврата к нулю), биполярная нетранзиктивная схема (состояния меняются на границе), которая имеет 2 варианта. Первый вариант это недифференциальное NRZ (используется в RS-232) состояние напрямую отражает значение бита (рис. 6.а). В другом варианте — дифференциальном, NRZ состояние меняется в начале битового интервала для 1 и не меняется для 0. (рис.6.Б). Привязки 1 и 0 к определенному состоянию нету.

NRZI — Non-return to zero Inverted, измененная схема NRZ (рис. 6.в). Тут состояния изменяются на противоположные в начале битового интервала 0, и не меняются при передаче 1. Возможна и обратная схема представления. Используются в FDDI, 100BaseFX.

Рисунок — 6-а,б,в RZ

RZ — Return to zero (с возвратом к нулю), биполярная транзитивная самосинхронизирующаяся схема. Состояние в определенный момент битового интервала всегда возвращается к нулю. Имеет дифференциальный/недифференциальный варианты. В дифференциальном привязки 1 и 0 к состоянию нету. (рис. 7.а).

Рисунок — 7-а,б

FM 0

FM 0 — Frequency Modulation 0 (частотная модуляция), самосинхронизирующийся полярный код. Меняется на противоположное на границе каждого битового интервала. При передаче 1 в течение битового интервала состояние неизменное. При передаче 0, в середине битового интервала состояние меняется на противоположное. (рис. 8). Используется в LocalTalk.

Рисунок — 8

PAM 5

PAM 5 — Pulse Amplitude Modulation, пятиуровневое биполярное кодирование, где пара бит в зависимости от предыстории оказывается одним из 5 уровней потенциала. Нужен неширокая полоса частот (вдвое ниже битовой скорости). Используется в 1000BaseT.

2B1Q

Здесь пара бит оказывается одним четверичным символом (Quater-nary symbol), где каждому соответствует один из 4 уровней сигнала. В таблице показано представление символов в сети ISDN.

Таблица 2 - Представление символов в сети ISDN.

---