- •Вопрос 2.
- •Часть 1.Количественная мера информации для равновозможных событий
- •Часть 2. Мера р. Хартли
- •Вопрос 3.
- •Вопрос 4.
- •Вопрос 5.
- •Вопрос 6. Свойства энтропии источника дискретных сообщений
- •Вопрос 7. Энтропия источника совместных сообщений
- •Вопрос 8. Что такое условная энтропия?
- •Вопрос 9.
- •Вопрос 10. Свойства количественной меры информации при неполной достоверности результатов опыта.
- •Вопрос 11. Вычисление количественной меры информации для двоичного канала с помехами.
- •Вопрос 12. Как оценивается избыточность источника сообщений?
- •Вопрос 13.
- •Вопрос 23.
- •Вопрос 24. Приведите модель двоичного канала с шумами
- •Вопрос 25.
- •Вопрос26. Формула Шеннона для аналогового канала с шумами.
- •Вопрос 27. Энтропия источника при наличии коррелятивных связей между двумя соседними символами
- •Вопрос 28. Принципы помехоустойчивого кодирования. Кодовое расстояние.
- •Вопрос 29. Вероятность ошибочного приема кодовой информации для простого двоичного кода и для кода с исправлением ошибок кратности t.
- •Вопрос 30. Простейшие избыточные коды.
- •Вопрос 31. Групповой код Хемминга. Принципы построения. Синдром ошибки. Коды с обнаружением и исправлением ошибок. Код хемминга
- •Вопрос 32. Определение числа проверочных элементов.
- •Вопрос 33. Определение проверочных элементов, входящих в каждую группу. Исправляющая способность кода хемминга
Вопрос 27. Энтропия источника при наличии коррелятивных связей между двумя соседними символами
Энтропия источника при наличии коррелятивных связей между двумя соседними символами
Полученные ранее выражения для энтропии дискретного источника сообщений справедливы в случае, когда все сообщения независимы.
Рассмотрим источник, у которого имеют место коррелятивные связи между двумя соседними символами. Вероятность появления символа xi зависит лишь от того, какой символ был выработан до этого.
Для описания такого источника необходимо задать распределение вероятностей p(xi) и вероятности переходов (условная вероятность) p(xi|xk) или вероятности всех возможных пар символов p(xi, xk).
Нижеприведенное выражение описывает связь между этими вероятностями
. (3.50)
Если коррелятивные связи имеются между двумя соседними символами, то энтропия источника равна
(3.51)
Сравним энтропии источников с независимыми событиями и с коррелятивными связями между двумя соседними сообщениями.
Вероятности каждого из четырех сообщений равны:
p(x1)=1/2, p(x2)=1/4, p(x3)= p(x4)=1/8.
Для независимых событий
.
Пусть между двумя соседними символами имеются коррелятивные связи, которые описываются таблицей
xixj |
p(xi, xj) |
p(xi | xj) |
xixj |
p(xi, xj) |
p(xi | xj) |
x1x1 |
13/32 |
13/16 |
x3x1 |
0 |
0 |
x1x2 |
3/32 |
3/16 |
x3x2 |
0 |
0 |
x1x3 |
0 |
0 |
x3x3 |
0 |
0 |
x1x4 |
0 |
0 |
x3x4 |
1/8 |
1 |
x2x1 |
1/32 |
1/8 |
x4x1 |
1/16 |
1/2 |
x2x2 |
1/8 |
1/2 |
x4x2 |
1/32 |
1/4 |
x2x3 |
3/32 |
3/8 |
x4x3 |
1/32 |
1/4 |
x2x4 |
0 |
0 |
x4x4 |
0 |
0 |
По заданным вероятностям появления символов p(xi) и вероятностям пар импульсов p(xi, xj) из (3.50) определяются условные вероятности
, представленные в третьем и шестом столбцах таблицы.
Используя (3.51), получим , т.е. при наличии коррелятивных связей между сообщениями источника энтропия уменьшается.
Вопрос 28. Принципы помехоустойчивого кодирования. Кодовое расстояние.
Необходимость передачи цифровых сообщений на значительные расстояния, использование сетевых технологий предъявляют повышенные требования к достоверности передачи, обработки и ранения информации. Простые двоичные коды не удовлетворяют этим требованиям. Рассмотрим простой трехразрядный код: 000,
001,
010 …
Для простого двоичного кода искажения любого символа воспринимаются как другая кодовая комбинация. В результате на приемной стороне принимается ошибочная кодовая комбинация. Оценим вероятность такой ошибки.
Пусть р – вероятность искажения одного символа, а q – вероятность правильного приема одного символа.
Искажение и правильный прием образуют пару несовместных событий, поэтому сумма их вероятностей равна единице.
Тогда q=1 – p.
Так как символы искажаются независимо друг от друга, то вероятность правильного приема комбинации из n символов:
(4.1)
Вероятность искажения кодовой комбинации:
(4.2)
При и менее (1– р)n≈1–рn. Тогда Рк≈np. Для .
Для повышения достоверности приема цифровых сигналов используют помехоустойчивое кодирование.
Основной принцип помехоустойчивого кодирования
помехоустойчивый код - Это избыточные коды в которых число разрешенных кодовых комбинаций меньше общего числа кодовых комбинаций, возможных для двоичного кода данной разрядности.
Пусть имеется простой двоичный код, с помощью которого можно передать кодовых комбинаций. Из этого числа N используют лишь кодовых комбинаций.
- число разрешенных кодовых комбинаций.
- число запрещенных кодовых комбинаций.
Для исключения возможности перехода одной разрешенной комбинации в другую разрешенную кодовую комбинацию выполняется соотношение .
Так как в помехоустойчивом коде число разрешенных кодовых комбинаций меньше общего числа кодовых комбинаций, возможных для двоичного кода данной разрядности, то помехоустойчивые коды называют еще избыточными кодами.
Избыточность кода можно оценить выражением:
(4.3)
- число избыточных символов в переданной кодовой комбинации.
Кодовое расстояние.
Возможность корректирующих кодов по исправлению и обнаружению ошибок определяется кодовым расстоянием.
Кодовым расстоянием d называется минимальное количество разрядов, в которых одна кодовая комбинация отличается от другой кодовой комбинации, оно определяет возможность корректирующих кодов по исправлению и обнаружению ошибок.
Для конкретного кода кодовым расстоянием данного кода называется минимальное число элементов, которыми одна кодовая комбинация данного кода отличается от другой кодовой комбинации того же кода.
Иногда кодовое расстояние называется хемминговым расстоянием (по имени Ричарда Хемминга основателя помехоустойчивых кодов) .
У простого двоичного кода d=1. Каким должно быть кодовое расстояние у кодов, обнаруживающих ошибки, и у кодов, исправляющих ошибки?
В общем случае для обеспечения возможности исправления всех ошибок кратности до t включительно при декодировании по методу максимального правдоподобия каждая из ошибок должна приводить к запрещенной кодовой комбинации, входящей в группу таких комбинаций, соответствующих исходной кодовой комбинации.
Пусть имеется n-разрядный двоичный код. Выберем 2 кодовые комбинации и , которые будем считать разрешенными (рисунок 4.1). Каждой разрешенной кодовой комбинации соответствует свое подмножество запрещенных кодовых комбинаций с одиночными ошибками. Число их равно Cn1, а кодовое расстояние относительно исходной кодовой комбинации d=1. Графически это представляется окружностью с радиусом d=1.
Рисунок 4.1 – Определение кодового расстояния
Аналогично, подмножество запрещенных кодовых комбинаций с двойной ошибкой имеет кодовое расстояние относительно исходной d=2, а число их равно Cn2. И так далее до ошибок кратности t включительно.
Для того чтобы при приеме восстановить именно кодовую комбинацию необходимо, чтобы набор ее запрещенных кодовых комбинаций не пересекался с набором запрещенных кодовых комбинаций .
Для исправления ошибок кратности t кодовое расстояние должно удовлетворять условию: .
Для исправления ошибки кратности s кодовое расстояние должно быть:
.
Если код должен исправлять ошибки кратности t и обнаруживать ошибки кратности s, то кодовое расстояние должно быть не менее
Помехоустойчивые коды делятся на два больших класса:
-
Блоковые коды;
-
Непрерывные коды.
Для блоковых кодов к каждой исходной комбинации добавляется блок избыточных символов и получается новая комбинация (рисунок 4.2).
Рисунок 4.2 – Построение блокового кода
Различают разделимые и неразделимые блоковые коды. В разделимых блоковых кодах k символов являются информативными, а r - проверочными.
Такие коды обозначают как (n,k) – коды.
Для неразделимых кодов разделить символы на информативные и проверочные невозможно (см. далее корреляционный код).
Непрерывными кодами называются коды, в которых введение избыточных символов в кодируемую последовательность осуществляется непрерывно, без разделения ее на независимые блоки.