- 2 -

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

Севастопольский национальный технический университет

Кафедра технической кибернетики

Контрольная работа

по дисциплине:

«Теория информации и кодирования»

Выполнил:

ст. гр. А-31з

Брусинов Сервер Энверович

Проверил:

доцент кафедры:

Мирянов Вячеслав Иванович

Севастополь 2006

ТЕМА 1. КОЛИЧЕСТВЕННАЯ ОЦЕНКА ИНФОРМАЦИИ.

Задача 6

Определить объём и количество информации в принятом тексте:

«Товарищ, верь: взойдёт она,

Звезда пленительного счастья,

Россия вспрянет ото сна…»

Решение

Число принятых символов, включая пробел,

k=80

Объём информации

Q=kl_ср =80*7=560 бит.

Количество информации для:

· равновероятностного алфавита:

H₁=log₂ m=log 32=5 бит/символ,

I₁=kH₁ =80*5=400 бит;

· неравновероятностного алфавита:

Н₂= бит/символ

I₂=kH₂=80*4.36?348,8 бит.

ТЕМА 2. УСЛОВНАЯ ЭНТРОПИЯ И ЭНТРОПИЯ ОБЪЕДИЕНИЯ

Задача 1

В результате статистических испытаний канала связи № 1 со стороны источника сообщений были получены следующие условные вероятности: 0,9; 0,1; 0; 0,1; 0,8; 0,1; 0;0,1; 0,9.

При испытании канала связи № 2 со стороны приёмника сообщений получины условные вероятности: 0,9; 0,08; 0; 0,1; 0,8; 0,08; 0;0,12; 0,92.

Построить соответствующие канальные матрицы и определить частные условные энтропии относительно сигнала а₂ (со стороны источника сообщений) и сигнала b₃( со стороны приёмника).

Решение

Построим канальную матрицу со стороны источника сообщений:

B A	b1	b2	…	bj	…	bm
a1			…,		…,
a2			…,		…,
…	………...…	………...…	………...…	………...…	………...…	………...…
ai			…,		…,
…	………...…	………...…	…,	………...…	…,	………...…
am			…,		…,

Подставим значения:

Построим канальную матрицу со стороны приёмника сообщений:

В А	b1	b2	…	bj	…	bm
a1			…,		…,
a2			…,		…,
…	………...…	………...…	………...…	………...…	………...…	………...…
ai			…,		…,
…	………...…	………...…	…,		…,	………...…
am			…,		…,

Подставим значения:

Найдём частные условные энтропии относительно:

· сигнала а₂ (со стороны источника сообщений)

· сигнала b₃( со стороны приёмника).

ТЕМА 3. ВЫЧИСЛЕНИЕ ИНФОРМАЦИОННЫХ ПОТЕРЬ ПРИ ПЕРЕДАЧЕ СООБЩЕНИЙ ПО КАНАЛАМ СВЯЗИ С ШУМАМИ

Задача 3

Можно ли назвать полным информационное описание канала связи, предоставленного матрицей вида ?

Решение

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

вероятности вида , а сумма по строкам даёт безусловные вероятности вида . Условные вероятности могут быть найдены из выражений:

.

Зная условные и безусловные вероятности, можно найти H(A),H(B),H(A/B) и H(B/A).

Если уровень помех настолько высок, что с равной вероятностью можно ожидать переход любого символа источника сообщения в произвольный символ первичного алфавита, то энтропия канала связи будет равна , а количество информации I=H(A)-, при этом значении I может быть отрицательной величиной, что означает, что канал связи вносит дезинформацию.

Задача8

Канал связи описан матрицей:

.

Определить полные информационные потери при передаче N символов по данному каналу связи.

Решение

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

p(a₁)=0.24, p(a₂)=0.34, p(a₃)=0.38, p(a₄)=0.12

p(b₁)=0.13, p(b₂)=0.29, p(b₃)=0.41, p(b₄)=0.25,

Найдём энтропию источника сообщений:

Найдём энтропию приёмника:

Совместная энтропия источника и приёмника:

Найдём информационные потери:

,где k=N=>

ТЕМА 3. ВЫЧИСЛЕНИЕ ИНФОРМАЦИОННЫХ ПОТЕРЬ ПРИ ПЕРЕДАЧЕ СООБЩЕНИЙ ПО КАНАЛАМ СВЯЗИ С ШУМАМИ

Задача8

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

?

Решение

Найдём безусловные вероятности источника и приёмника:

p(a₁)=0.2, p(a₂)=0.3, p(a₃)=0.5,

p(b₁)=0.4, p(b₂)=0.3, p(b₃)=0.3;

Находим условные вероятности видов p(A/B) и p(B/A) и строим соответствующие матрицы условных вероятностей:

Найдём энтропию источника сообщений:

Найдём энтропию приёмника:

Условные энтропии:

Пропускная способность:

ТЕМА 5. ОПРЕДЕЛЕНИЕ ИЗБЫТОЧНОСТИ СООБЩЕНИЙ. ОПТИМАЛЬНОЕ КОДИРОВАНИЕ.

Задача 15

Первичный алфавит имеет следующие вероятности появления букв в текстах: A₁=0,02; A₂=0,5; A₃=0,03; A₄=0,15; A₅=0,04; A₆=0,12; A₇=0,04; A₈=0,1. Построить ОНК методом Шеннона - Фано и методом Хаффмана. Сравнить Эффективность полученных кодов.

Решение

№1Строим ОНК методом Шеннона-Фано.

А	Вероятность		Число знаков в кодовом слове	pili
A2	0.5	0					1	0.5
A4	0.15	1	0	0			3	0.45
A6	0.12			1			3	0.36
A8	0.1		1	0			3	0.3
A7	0.04			1	0	0	5	0.2
A5	0.04					1	5	0.2
A3	0.03				1	0	5	0.15
A1	0.02					1	5	0.1

Определим среднюю длину кода(l_ср), энтропию (H) и коэффициент относительной эффективности (K_о.э):

№2 Строим ОНК методом Хаффмана:

- 2 -

А	Вероятность	код	Число знаков в кодовом слове	pili
A2	0.5	1	1	0.5
A4	0.15	001	3	0.45
A6	0.12	011	3	0.36
A8	0.1	010	3	0.3
A7	0.04	00011	5	0.2
A5	0.04	00010	5	0.2
A3	0.03	00001	5	0.15
A1	0.02	00000	5	0.1

Определим среднюю длину кода(l_ср) и коэффициент относительной эффективности (K_о.э):

3) Сравним эти два метода; методы будут равноэффективными, если выполнится условие: .

и рассчитаны в предыдущем пункте. Таким образом, проверяем условие: 2.2458<2.26=2.26. Условие выполняется. Метод Хаффмана и метод Шеннона - Фано равноэффективные; кроме того, и коэффициенты относительной эффективности в обоих методах равны т.е. коды равноэффективны.

ТЕМА 6. ОБНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК В СООБЩЕНИЯХ

Задача 4

1. Чему равно кодовое расстояние между комбинацией 10010111 и комбинациями 11111111, 00000000, 00010111?

Решение

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

Задача 16

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

Решение

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

Число столбцов матрицы С равно длине кода n:

n=n_И+n_К ,

где n_k - число корректирующих разрядов; d₀ =3;

,

тогда n=11+4=15

Минимальная простота дешифратора достигается при минимальном количестве сумматоров по модулю 2 в декодере, что возможно при минимальном весе комбинаций проверочной матрицы П; вес каждой комбинации проверочной матрицы П: W_П ? d₀ - 1; W_П ?2; выбираем четырёхзначные двоичные комбинации весом W=2, 3, 4, и используем те комбинации, в которых содержится меньшее число единиц, а именно: 0011; 0101; 0110; 1001; 1010; 1100; 0111; 1011; 1101; 1110; 1111.Искомая матрица имеет вид:

ТЕМА 7. ОБНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК ПРИ ПЕРЕДАЧЕ И МЕХАНИЗИРОВАННОЙ ОБРАБОТКЕ ИНФОРМАЦИИ НА СТАНДАРТНОЙ АППАРАТУРЕ С ПРИМЕНЕНИЕМ СТАНДАРТНЫХ НОСИТЕЛЕЙ.

Задача 1

Какие из приведенных ниже кодовые комбинации содержат ошибку, если известно, что они передавались стандартным телеграфным кодом №3: 0101010; 1101001; 1011100; 1000110; 1110100?

Решение

Необходимым условием отсутствия ошибки, в стандартном телеграфным коде №3, является соблюдение соотношения 3:4(три единицы и четыре нуля).

Задача 6

Построить кодовые комбинации для цифр: 16, 18, 20, 21, 22 таким образом, чтобы в них был предусмотрен контроль по модулю 7.

Решение

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

В качестве делителя следует использовать простые числа 2, 3, 5, 7, 11, 13, … . Запись соответствия числа заданному условию по признаку делимости имеет вид

(модуль М).

Читается эта запись так: число А сравнимо с числом К по модулю М[1]

Подставим наши значения:

Передаваемые цифровые коды будут иметь вид соответственно:

162; 184; 206; 210;221.

Задача 7

Модуль, на который должна без остатка делиться сумма цифр в принятом сообщении, равен 10. Используя метод контроля по сумме, определить, какие из приведенных ниже кодов содержат ошибки: 24510; 32195; 27435; 53724; 57350.

Решение

№	Принятое сообщение	Информационная часть	Сумма	Проверочный разряд
				какой должен быть	какой есть
1	24510	2451	2+4+5+1=12	8	0
2	32195	3219	3+2+1+9=15	5	5
3	27435	2743	2+7+4+3=16	4	5
4	53724	5372	5+3+7+2=17	3	4
5	57350	5735	5+7+3+5=20	0	0

Соответственно, ошибка присутствует в 1, 2, 3 кодах.

ТЕМА 8. СЖАТИЕ ИНФОРМАЦИИ

Задача 6

Восстановить исходный массив чисел по следующему ниже сжатому массиву:

2 4 6 8 1 3 5 7

7 2

1

Решение

Сжатый массив:

2 4 6 8 1 3 5 7

7 2

1

Промежуточный этап

развёртывания массива:

Исходный массив:

1. Задача 7

Сжать приведенный ниже массив, используя знак раздела и знак конца строки К:

6 3 1 8 1 2 7

6 3 1 8 1 8 6

2 1 1 8 1 2 4

3 1 1 8 1 2 9

4 1 1 8 1 2 9

4 1 1 8 1 2 9

5 1 1 8 1 2 9

Решение

Исходный массив:

Сжатый массив: