Файл: Методы кодирования данных».pdf

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

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

1.3. Метод Хаффмана

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

Этот метод состоит из двух этапов:

• Построение кодового .
• Построение отображения на основе построенного .

Алгоритм основан на том, что символы из 256-символьного набора в тексте могут чаще среднего повтора, а - реже. Следовательно, для записи распространенных использовать короткие бит, длиной 8, а для записи редких - длинные, то суммарный файла уменьшится. В получается данных в виде («двоичное дерево»).

A={a1,a2,...,an} - алфавит из n различных , W={w1,w2,...,wn} - соответствующий ему положительных целых . Тогда набор кодов C={c1,c2,...,cn}, такой что:

- ci не префиксом для cj, при i!=j; (|ci| длина кода ci) минимально-избыточным префиксным или иначе кодом . ^[6]

Бинарным называется ориентированное , полустепень исхода из вершин которого не двух.

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

Т- бинарное дерево, =(0,1)- двоичный и каждому ребру приписана одна из алфавита таким , что все ребра, из одной вершины, различными буквами. любому листу можно уникальное кодовое , образованное из букв, помечены ребра, при движении от к соответствующему листу. описанного способа в том, что полученные коды префиксными.

---

, что стоимость хранения , закодированной при помощи , равна сумме путей из к каждому листу , взвешенных частотой кодового слова или взвешенных : , где - частота кодового длины во входном . Рассмотрим в качестве кодировку в стандарте ASCII. каждый символ собой кодовое фиксированной(8 ) длины, поэтому хранения определится , где W- количество кодовых во входном .

Поэтому стоимость 39 кодовых слов в ASCII равна 312, от относительной отдельных символов в потоке. Алгоритм позволяет уменьшить хранения кодовых слов такого подбора кодовых слов, минимизирует взвешенных путей. называть дерево с длиной путей Хаффмана.

алгоритм Хаффмана на получает таблицу встречаемости символов в . Далее на этой таблицы дерево кодирования (Н-дерево). ^[7]

1. Символы алфавита список свободных . Каждый лист вес, который может равен вероятности, либо вхождений символа в сообщение;
2. Выбираются два узла с наименьшими весами;
3. их родитель с весом, их суммарному весу;
4. добавляется в свободных узлов, а два его удаляются из этого ;
5. Одной дуге, из родителя, в соответствие бит 1, другой - бит 0;
6. , начиная со второго, до тех пор, пока в списке узлов не только один узел. Он и будет корнем дерева.

, у нас есть таблица частот.

1

Таблица частот

15	7	6	6	5
А	Б	В	Г	Д

На шаге из листьев выбираются два с весами - Г и Д. Они присоединяются к узлу- родителю, вес устанавливается 5+6= 11. узлы Г и Д из списка свободных. Г соответствует ветви 0 , узел Д - ветви 1.

На шаге то же с узлами Б и В, так как теперь эта имеет самый вес в дереве. Создается узел с 13, а узлы Б и В удаляются из свободных.

На следующем «наилегчайшей» парой узлы Б/В и Г/Д.

Для них еще раз родитель, теперь уже с 24. Узел Б/В соответствует 0 родителя, Г/Д - ветви 1.

На шаге в свободных осталось 2 узла - это узел А и Б (Б/В)/(Г/Д). В очередной раз родитель с 39, и бывшие свободные присоединяются к разным его .

Поскольку свободным только узел, то алгоритм дерева кодирования завершается.

Каждый , входящий в , определяется как конкатенация и единиц, сопоставленных дерева Хаффмана, на от корня к листу.

Для данной символов коды будут выглядеть, как в табл. 2.

---

ица 2

Коды Хаффмана

А	01
Б	100
В	101
Г	110
Д	111

частый символ А закодирован наименьшим бит, а наиболее символ Д - наибольшим. хранения кодированного , определенная как сумма взвешенных , определится выражением что существенно меньше хранения входного (312).

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

Алгоритм предполагает просмотр битов и синхронное от корня по дереву Хаффмана в со считанным значением до тех пор, не будет достигнут , то есть очередное кодовое , после чего следующего слова начинается с дерева. ^[8]

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

2. АНАЛИЗ КОДИРОВАНИЯ ДАННЫХ

2.1. кодирование 

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

- 4B/5B — каждые 4 входного потока 5-битным (табл 1.1). Получается избыточность, так как 24 = 16 комбинаций показываются из 25 = 32. по количеству битовых составляют: (5-4)/4 = 1/4 Такая избыточность определить ряд символов, которые для синхронизации. Применяется в 100, FDDI

- 8B/10B — схема (8 бит 10-битным символом) но уже равна 4 раза входных в 1024 ).

- 5B/6B — 5 бит потока кодируются 6- символами. Применяется в 100

- 8B/6T — 8 бит входного кодируются троичными (T = ternary) (-,0,+). К примеру: 00h: 01h: 0+-+=0; Код имеет 36/28 = = 2,85. Скорость транспортировки в линию является битовой скорости и их на кодирования. в 100BaseT4. ^[9]

Вставка бит — схема работает на недопустимых последовательностей бит. Ее объясним на в протоколе HDLC. Тут поток смотрится как последовательность бит, для которой из более чем смежных 1 анализируется как служебный (пример: 01111110 флагом-разделителем кадра). в транслируемом встречается непрерывная из 1, то после пятой в выходной передатчик  0. Приемник анализирует цепочку, и если цепочки 011111 он видит 0, то он его и последовательность 011111 присоединяет к выходному потоку . Если принят  1, то последовательность 011111смотрится как служебный . Такая решает две задачи — длинные монотонные , которые неудобные для физического и разрешает опознание кадра и особых в непрерывном битовом .

---

Таблица 3

4В/5В

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

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

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

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

2.2. Скремблирование 

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

- Транзитное — информативным есть из одного состояния в

- Потенциальное кодирование — есть сигнала в конкретные времени

- Полярное — одной полярности для представления значения, сигнал полярности для — другого. При транспортировке вместо используют импульса

- Униполярное — одной полярности для представления одного , нулевой — для другого

- Биполярное — отрицательное, положительное и значения для представления состояний

- — в каждом битовом присутствует переход из состояния в другое, что для выделения . ^[11]

2.3. Схемы кодирования, применяются в локальных

---

AMI/ABP

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

Рисунок 1

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

B8ZS

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

HDB3

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

2

Манчестерское кодирование

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

3

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

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

Рисунок 4

-3

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

5

NRZ и NRZI

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

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

---