Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Новосибирский государственный университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

OPDS_ekzamen (1).doc

Скачиваний:

Добавлен:

01.05.2025

Размер:

7 Мб

Скачать

☆

<<< < Предыдущая 1 2 3 45 / 145 6 7 8 9 10 11 12 13 14 > Следующая >>>

10.Эффективное (статистическое) кодирование.

Эффективное кодирование – это процедуры направленные на устранение избыточности.

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

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

Если сообщения источника равновероятны, то энтропия максимальна и равна Hmax (x) = log₂ K

Если сообщения не равновероятны, то, энтропия источника будет меньше

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

, чем больше вероятность появления, тем меньше длина.

Сообщениям, содержащим большее количество информации, ставят в соответствие более длинные кодовые комбинации, а сообщениям с малым объемом информации – короткие.

Учитывая, что объем информации, содержащейся в сообщении,

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

Т.о. на одно сообщение будет затрачено в среднем меньшее единичных элементов l=∑^k_i₌₁ p(a_i)l_i_,, чем при равномерном.

Теорема Шенона:

1. Нельзя закодировать сообщения источника так, что бы средняя длина кодового слова была численно меньше величины его энтропии

2. Существует способ кодирования, при котором средняя длина кодового слова немногим отличается от энтропии источника

Эффективность применения оптимальных неравномерных кодов может быть оценена:

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

Учитывая, что ,можно записать . Ксс лежит в пределах 2. Коэффициент относительной эффективности

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

Префиксным называют код, для которого никакая короткая комбинация не является началом другого более длинной комбинации. Префиксные коды всегда однозначно декодируемы. Кодовое дерево – наглядное изображение комбинаций какого-либо кода.

Концевые узлы – однозначно декодируемые.

Метод Хаффмена Пусть имеется алфавит из k сообщений: А {а₁; а₂; …а_к}. Каждое сообщение появляется с соответствующей вероятностью p(а₁), p(а₂),… p(а_к).

Алгоритм кодирования:

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

Недостаток кодирования – одна ошибка приводит к треку ошибок.

М етоды сопряжения источника дискретного сигнала с дискретным каналом.

К ритерием эффективности согласования является коэффициент использования синхронного канала η=(Ви/Вс)100%

- Метод наложения. При этом методе используется импульсная несущая, модулируемая передаваемым сигналом. Каждая посылка как бы накладывается на импульсную несущую, в результате в канал поступает пачка импульсов несущей (если 1), либо не поступают (если бестоковая посылка). На приемной стороне каждая пачка импульсов несущей преобразуется в сигнал. Существуют краевые искажения, их величина δ=(Ви/Вс)100%. Краевые искажения меньше, чем скорость Вс.

- Метод скользящего индекса с подтверждением (СИП). Δt разбивается на l зон и попадание значащего момента фиксируется в ту или иную зону. По каналу передается информация о номере зоны и о знаке передаваемой посылки, при этом краевые искажения уменьшаются в l раз. δ=(Ви/l*Вс)100%. Информация о зоне передается двоичным кодом, и в зависимости от количества зон δ=(Ви/2^К*Вс)100%.

Старт	Вспомог.sig	Зоны
Старт	Вспомог.sig	1	2	3	4
1	S1	1	1	0	0
1	S2	1	0	1	0
0	S1	0	0	1	1
0	S2	0	1	0	1

- Стаффинг: *односторонний - положительный и отрицательный; * двухсторонний

Вс>Ви – отрицательный стаффинг.

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

Линейные (групповые) коды.

Двоичный код линейный (групповой), если сумма по модулю 2 двух кодовых слов также является кодовым словом.

Множество элементов с определенной на нем групповой операцией называется группой, если выполняется следующие условия:

1. Замкнутость g_i Å g_j= g_k Î G

2. Ассоциативность (сочетательность) (g_iÅ g_j) Å g_k = g_iÅ (g_j Å g_k)

3. Наличие нейтрального элемента g_j Å e = g_j

4. Наличие обратного элемента g_i Å (g_i)^-1= e

Рассмотрим процедуру построения линейного кода: k=log₂К.

С помощью исправляющей способности можно определить кодовое расстояние d_0.
Необходимо выбрать длину кодовой комбинации больше, чем k (n>k).
Далее из 2ⁿ комбинаций выбрать 2^k комбинаций с расстоянием d≥ d₀ (т.е. не менее заданного)

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

Кодом Хемминга называется групповой (n,k) код, исправляющий одиночные ошибки и обнаруживающий двукратные ошибки.

Построим код, обеспечивающий передачу К сообщений и исправление t-кратной ошибки.

Пусть К = 16 и t_и = 1;

1. Найдем число информационных разрядов k и кодовое расстояние d₀:

k = log₂16 = 4;

d₀ = 2t_и + 1 = 3;

2. Строим производящую матрицу:

- берем единичную матрицу - дописываем проверочные разряды по следующим правилам:

* Число единиц среди дописываемых элементов должно