Рис. 3.1

Затем, двигаясь по кодовому дереву сверху вниз, записываем для каждой буквы соответствующую ей кодовую комбинацию:

Выберем из ансамбля А произвольную комбинацию из пяти символов и закодируем их полученным кодом Хаффмана:

А1А2А7А6А4

011100100010111000101100000.

Потенциальный минимум будем искать по формуле (2.12) лекции:

;

Так как код является двоичным, тогда основание кода N = 2. Следовательно:

.

Найдем энтропию источника, пользуясь мерой Шеннона:

;

Рассчитаем среднее количество символов, приходящихся на одно сообщение:

, где

М - объем алфавита кода (М = 2);

Pi - вероятность появления события;

n - количество символов в коде.

Согласно (2.12.а) лекции эффективность кода находим, как:

.

Ответ: потенциальный минимум ; среднее количество символов, приходящихся на одно сообщение ; эффективность кода .

3.4 Задачи № 3.114

Закодировать кодом Хаффмана, с объемом алфавита М=5, ансамбль

Закодировать произвольную комбинацию, состоящую из пяти символов ансамбля А; Определить потенциальный минимум среднего количества символов кода, приходящихся на одно сообщение ансамбля А; Определить среднее количество символов разработанного кода Хаффмана, приходящихся на одно сообщение из ансамбля А; Рассчитать эффективность разработанного кода.

Решение:

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

Затем строится кодовое дерево, в процессе которого осуществляется кодирование: верхняя точка дерева равна единице; из нее направляется четыре ветви, причем, ветви с большей вероятностью приписывается значение «4», а с меньшей - «0». Такое последовательное ветвление продолжается до тех пор, пока не добираются вероятности каждой буквы.

25

Рис.3.2

Затем, двигаясь по кодовому дереву сверху вниз, записываем для каждой буквы соответствующую ей кодовую комбинацию:

Выберем из ансамбля А произвольную комбинацию из пяти символов и закодируем их полученным кодом Хаффмана:

А8А7А6А5А4

2023023023322.

Потенциальный минимум будем искать по формуле (2.12) лекции:

;

Так как код является четверичным, тогда основание кода N =5. Следовательно:

.

Найдем энтропию источника, пользуясь мерой Шеннона:

;

Тогда потенциальный минимум

.

Рассчитаем среднее количество символов, приходящихся на одно сообщение:

, где

М - объем алфавита кода (М = 5);

Pi - вероятность появления события;

n - количество символов в коде.

Согласно (2.12.а) лекции эффективность кода находим, как:

.

Ответ: потенциальный минимум ; среднее количество символов, приходящихся на одно сообщение ; эффективность кода .

4. Согласование дискретного источника с дискретным каналом с шумом. Помехоустойчивое кодирование

4.1 Задача № 4.24

Определить избыточного оптимального по Шеннону кода (существование которого утверждается теоремой для канала с шумом) с объемом алфавита М =3 и средним количеством символов, переданных в единицу времени - Vk, предназначенного для безошибочной передачи информации по каналу с пропускной способностью С. Найти минимально возможную избыточность оптимального кода для симметричного канала с вероятностью ошибки Р = 0,1.

Решение:

В соответствии с (1.12) лекции, избыточность источника дискретного сообщения с объемом алфавита М называется величина

,

Причем, если ввести понятие производительности

,

То величину можно переписать в виде:

.

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

.

В соответствии с условием (2.15) теоремы Шеннона

или для оптимального кода

, где .

Поэтому, окончательная формула для вычисления избыточности будет выглядеть:

.

В соответствии с §1.6 лекции, среднее количество символов, передающихся в единицу времени будем определять по формуле (1.27.а):

Подставляя полученное значение в выведенную формулу избыточности, получим:

Ответ: минимальная возможная избыточность оптимального кода для симметричного канала с вероятностью ошибки Р = 0,1 и объемом алфавита М = 3 будет равна .

4.2 Задача № 4.54

Построить производящую матрицу G линейного двоичного блочного кода, способного исправлять одиночную ошибку при передаче дискретных сообщений источника, представляющих собой последовательность десятичных цифр из диапазона 0 … M-1 (с объёмом алфавита M = 1981). Пользуясь разработанной матрицей G, сформировать кодовую комбинацию для сообщения i (i = 1569). Построить соответствующую производящей матрице G проверочную матрицу H и с её помощью сформировать кодовую комбинацию для сообщения i. По виду синдрома найти и исправить ошибку в принимаемой кодовой комбинации (дополнительно заданной преподавателем). Определить, является ли разработанный код кодом Хэмминга.

Решение:

Производящая матрица G линейного двоичного блочного кода имеет размерность (n; k). Так как код является двоичным, то

.

Отсюда находим k:

Матрица G линейного двоичного кода состоит из двух матриц:

.

Построим матрицу I: I - это единичная матрица, размерности (k; k), при k = 11

Построим матрицу П: П - имеет размерность (k; n-k), k - число строк, а n - число столбцов.

Матрицу П будем строить по определенным правилам:

1. так как код должен исправлять единичную ошибку, получим, что исправная способность будет равна единице, т.е. .

В одной стоке матрицы должно быть не менее d - 1 единиц. Найдем d как

2. все строки должны быть разными;

3. число элементов в стоке должно быть минимально.

Используя правила построения, получим матрицу П:

n - k = 4

k = 11

n = 15

После построения вспомогательных матриц, можно построить матрицу G:

Проверочная матрица Н имеет размерность (n-k; k) и представляет собой транспонированную матрицу П:

Пользуясь разработанной матрицей G, сформируем кодовую комбинацию для сообщения - i (i =1569). Переведем ее из десятичного в двоичный вид: 1569 11000100001.

Разрешенная комбинация

Получится кодовая комбинация Vi

Полученная комбинация состоит из информационных и проверочных разрядов:

.

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

.

берется из матрицы Н.

j = 1:

j = 2:

j =3:

j = 4:

Для того, что бы найти ошибку, надо найти синдром. Правило нахождения синдрома:

1. по информационным разрядам задается комбинация, определяющая проверочные разряды;

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

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

,

где I - единичная матрица, размерности (n-k; n-k)

Попробуем найти ошибку с помощью синдрома: пусть получена следующая комбинация - [101000001111100]. Воспользуемся правилом нахождения синдрома:

1. по информационным разрядам определяем проверочные разряды исходного кода - [1001];

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

[1001][1100] = [0101].

Теперь строим проверочную матрицу Нпроверочную:

Найдем в Нпроверочной столбец, совпадающий с комбинацией синдрома. Номер этого столбца указывает на номер столбца в принятой комбинации, в которой допущена ошибка. В нашем случае комбинация синдрома совпадает с 2 столбцом Нпроверочную.

Для исправления этой ошибки надо инвертировать значение этого разряда. Тогда у нас получается - [111000001111100].

Код Хемминга, это код (n; k), который определяется:

Полученная мной матрица имеет размерность . Она является кодом Хемминга.

Заключение

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

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

В результате выполнения работы все требования задания были выполнены.

Список использованных источников

1. Прикладная теория информации: Учебн. Для студ. ВУЗов по спец. «Автоматизированные системы обработки информации и управления». - М.: Высш. шк., 1989. - 320с.:ил.

Страницы: 1, 2, 3