![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Код построен по матрицеСтр 1 из 3Следующая ⇒
РОССИЙСКОЙ ФЕДЕРАЦИИ ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет прикладной математики и телекоммуникаций Кафедра радиоэлектронных средств
Контрольная работа по дисциплине:
Теория информации и кодирование
Вариант 20
Киров 2004 Задание 1.1 Источник сообщения выдает символы из ансамбля А={ai}. Распределения вероятностей приведены в таблице 1. Найти количество информации, содержащееся в каждом из символов источника при независимом выборе (источник без памяти). Вычислить энтропию и избыточность заданного источника. Таблица 1
Количество информации в передаваемом символе определяется в битах. Чем меньше вероятность появления того или иного символа, тем больше количество информации извлекается при его получении. Если источник может выдать один из двух независимых символов (а1 и а2) и первый из них выдается с вероятностью р(а1)=1, то символ а1 не несет информации, ибо он заранее известен получателю. Количество инфор м ации определяется выражением:
I(ai)=log21/p(ai)= -log2p(ai).
I(a1)= -log20, 01 = 6, 62; I(a2)= -log20, 1= 3, 32; I(a3)= -log20, 1= 3, 32; I(a4)= -log20, 12= 3, 06; I(a5)= -log20, 35 = 1, 52; I(a6)= -log20, 2= 2, 32; I(a7)= -log20, 12= 3, 06;
Энтропия – это среднее количество информации Н(А), которое приходится на один символ:
H(A)=0, 01*6, 62+0, 1*3, 32+0, 1*3, 32+0, 12*3, 06+0, 35*1, 52+0, 2*2, 32+ 0, 12*3, 06=2, 4606 бит/символ.
Избыточность источника зависит как от протяженности статистических связей между последовательно выбираемыми символами, так и от степени неравновероятности отдельных символов.
Р(1/1′ ) P(1/0′ ) P(0/1′ ) P(0/0′ ), Где Р(аi/aj′ )-вероятность символа аi при условии, что ему предшествует символ аj′ . Определить энтропию и избыточность двоичного источника без памяти, если дискретный стационарный источник задан с помощью матриц переходных вероятностей.
Р= 0, 25 0, 65 0, 75 0, 35 Решение: Найдем безусловные вероятности передачи символов из соотношений:
Р(0)=Р(0)Р(0/0′ )+[1-P(0)]P(0/1′ )
Переходные вероятности равны:
Энтропия источника:
Избыточность источника:
Для источника без памяти при тех же безусловных вероятностях передачи символов:
Нmax (А)= - Р(1)log2 P(1) - P(0)log2P(0)= = -0, 464 log20, 464 – 0, 536 log20, 536=0, 996
Задание 1.3 Определите пропускную способность канала. Рисунок 1 – Определить пропускную способность канала.
Составляем уравнение пропускной способности в общем виде:
С=Нmax(A)-Hmin(B|A), где Нmax(A) – максимальная энтропия, Hmin(B|A) – минимальная энтропия. Нmax = log3 Hmin = Y(x) = p(x1)*p(y1|x1)*log p(y1|x1) + p(x2)* p(y1|x2)* log p(y1|x2) + p(x1)* p(y2|x1)* log p(y2|x1) + p(x2)* p(y2|x2)* log p(y2|x2) + p(x1)* p(y3|x1)* log p(y3|x1) + p(x2)* p(y3|x2)* log p(y3|x2) = ½ *(1-p-q)*log(1-p-q) + ½ *(p)*log(p) + ½ *(q)*log(q) + ½ *(q)*log(q) + ½ *(p)*log(p) + ½ *(1-p-q)*log(1-p-q) = (1-p-q)*log(1-p-q) + (p)*log(p) + (q)*log(q) = =
С = log3 -
Задание 2.1Некоторый дискретный источник выдает символы из ансамбля {ai}, с вероятностями приведенными в таблице 1. Закодировать символы данного ансамбля кодом Хаффмена, кодом Шеннона-Фано и равномерным кодом. Определить среднюю длину кодовой комбинации и сравнить с энтропией сообщения. Показать, какой код является наиболее эффективным.
Решение:
а7 0, 12 101
а2 0, 10 010
а3 0, 10 0, 21 1110 0, 11 а1 0, 01 0110
Средняя длина кодовой комбинации данного кода:
Код Шеннона-Фано:
а6 0, 18 1 } 0 10
а7 0, 1 1 } 0 010
а1 0, 05 0 0 } 0 0000
При оптимальном двоичном кодированием энтропия сообщения:
Равномерный код:
Число разрядов в кодовых комбинациях равно n=log28=3
0 1
0 1 0 1
0 1 0 1 0 1 1
а5 а1 а4 а3 а7 а2 а6
Таблица 2 - Кодовые комбинации:
Средняя длина кодовой комбинации кода Хаффмена отличается от средней длины кодовой комбинации по Шеннону-Фано на:
Средняя длина кодовой комбинации равномерным кодом отличается от средней длины кода по Шеннону-Фано на:
Следовательно код Хаффмена и Шеннона-Фано являются наиболее эффективными
Задание 2.2 Пусть алфавит содержит лишь две буквы а1 и а2, появляющиеся с вероятностями р(а1) и р(а2) Применив метод Шеннона-Фано закодировать сначала каждую букву по отдельности, затем закодировать двух- и трех- буквенные комбинации. Определить среднюю длину кодовой комбинации для трех случаев и сравнить ее с энтропией сообщения. Определить наилучший результат кодирования. Таблица 3
Решение: Закодируем каждую букву по отдельности:
а2 0, 5 } 1 a1 0, 5 } 0 Средняя длина кодовой комбинации данного кода равна:
Закодируем двухбуквенную комбинацию:
a1 a2 0, 25 0 10
a2 a1 0, 25 1 01 a1 a1 0, 25 0 00
Средняя длина кодовой комбинации данного кода равна:
Закодируем трехбуквенную комбинацию:
а2 а2 а2 0, 125 1 111 а2 а2 а1 0, 125 0 110 а2 а1 а2 0, 125 1 101 а1 а1 а2 0, 125 0 100
а1 а1 а2 0, 125 1 011 а1 а2 а1 0, 125 0 010 а2 а1 а1 0, 125 1 001 а1 а1 а1 0, 125 0 000
Средняя длина данной кодовой комбинации равна: Энтропия сообщения для однобуквенного кода равна: Энтропия сообщения для двухбуквенного кода равна: Энтропия сообщения для трехбуквенного кода равна: Длина для двухбуквенного кода: Для трехбуквенного кода:
Задача3.1. Сообщения источника, имеющего алфавит с объемом К, кодируется двоичным блочным кодом. Число разрядов в каждой кодовой комбинации п. Какое число информационных и проверочных символов содержится в каждой кодовой комбинации? Сколько разрешенных и запрещенных комбинаций в используемом коде? Определить избыточность и относительную скорость кода.
Решение: Число информационных символов: Число проверочных символов: Число разрешённых комбинаций: Число запрещённых комбинаций: Избыточность кода: Относительная скорость хода:
Задача3.2. Определить минимальное кодовое расстояние
Решение: Минимальное кодовое расстояние:
Задача 3.3. Двоичный код, предназначенный для кодирования п сообщений, содержит кодовые комбинации: Таблица 4
Решение: Является ли данный код линейным? Найти избыточность и относительную скорость кода.
Код не линейный, так как сумма линейного кода по модулю 2, любых его кодовых комбинаций дает разрешенную комбинацию. В качестве примера найдем сумму по модулю 2 комбинаций:
Избыточность кода: Относительная скорость кода:
Задание 3.4Построить порождающую матрицу для кода с кодовым раcстоянием dmin=3, количеством информационных элементов k=2. Написать правила формирования проверочных элементов для полученного кода. Найти проверочную матрицу. Определить сколько ошибок такой код может обнаружить, сколько ошибок он может исправить. Нарисовать структурную схему кодирующего и декодирующего устройства. Составить таблицу соответствия между местоположением одиночных ошибок и видом синдрома.
Решение: Число информационных разрядов кода k=2, значит число строк порождающей матрицы G должно быть равным 2. Число столбцов матрицы G равно длине кода, который равен сумме чисел корректирующих и информационных разрядов. Для расчетов контрольных разрядов с минимальным кодовым расстоянием dmin= 3 воспользуемся следующими выражениями: каждая строка приписанной части единичной матрицы должна содержать dmin-1 единиц, а сумма по модулю 2 не менее dmin-2. Следовательно, число столбцов, содержащих контрольные разряды должно быть равно 3, а общее число столбцов матрицы G равно 5. Построим порождающую матрицу G:
10 011 G = 01 110 Правила формирования проверочных элементов для полученного кода: а3 = а2; а4 = а1 Å а2; а5 = а1. Проверочная матрица задает правила кодирования линейного кода и определяет схему кодирующего устройства: Определим, сколько ошибок данный код может обнаружить: dmin= r + 1 Þ r = dmin – 1 = 3 –1 =2, т.е. число обнаруживаемых ошибок равно 2. Для определения количества исправляемых ошибок применим формулу: dmin= 2tи + 1 Þ tи = tи = 1, код исправляет одну ошибку.
Рисунок 2 – Схема кодирующего устройства
Рисунок 3 – Схема декодирующего устройства Таблица соответствия между местоположением одиночных ошибок и видом синдрома: Таблица 5
Задача 3.5 Определить, какие из приведенных кодовых комбинаций линейного кода содержат ошибку: а1=1000100 а2=1001010
Решение: Код построен по матрице
G = 0100011
Найдем правила получения проверочных элементов: а5 = а1 Å а3 Å а4 b1 = a1 Å a3 Å a4 Å a5 а6 = а1 Å а2 Å а3 b2 = a1 Å a2 Å a3 Å a6 а7 = а1 Å а2 Å а4 b3 = a1 Å a2 Å a4 Å a7
Кодовая комбинация а1=1000100 b1 =1 Å 0 Å 0 Å 1 = 0 b2 =1 Å 0 Å 0 Å 0 ¹ 0 b3 =1 Å 0 Å 0 Å 0 ¹ 0
Синдром двух кодовых комбинаций не равен нулю, содержит ошибки.
Кодовая комбинация а2=1001010 b1 = 1 Å 0 Å 1 Å 0 = 0 b2 = 1 Å 0 Å 0 Å 1 = 0 b3 = 1 Å 0 Å 1 Å 0 = 0
Синдром равен нулю, ошибок нет Задание 3.6. а) Построить код Хэмминга (порождающую и проверочную матрицы), если количество проверочных элементов 3.
Решение: Параметры кодов Хемминга для -длина кодового слова: -длина информационной части: -длина проверочной части: Проверочная матрица кода Хемминга имеет вид: Где первый, второй и четвертый столбцы являются проверочными(т.к. имеют только одну единицу), остальные – информационные.
Порождающая матрица кода Хемминга содержит k строк и n столбцов:
7 элементов задержки, 3 сумматора.
7 элементов задержки, 3 сумматора. Всего 14 элементов задержки, 6 сумматоров.
Код Рида-Маллера. r=1, m=3. Длина кодового слова: Длина информационной части: Проверочная матрица:
8 элементов задержки, 4 сумматора.
к) Сверточный код описываетя полиномами g1 =101, g2 =11: · получить кодер, соответствующий этому коду, · получить диаграмму состояний для этого кода, · определить свободное расстояние этого кода dсв, число исправляющих ошибок tиспр.ош, длину кодового ограничения v.
Задание 4.1 Согласно номеру варианта построить коды и рассчитать их параметры: - эквивалентную мощность сигнала; - коэффициент, характеризующий среднее значение тактовой частоты; - коэффициент, характеризующий минимальное значение тактовой частоты; - коэффициент, характеризующий максимальное значение тактовой частоты; - коэффициент, характеризующий реальное значение тактовой частоты; - коэффициент устойчивости признаков тактовой частоты.
Таблица 6
1 - Исходная последовательность 2 - Код B3ZS 3 - Код PST 4 - Код AMI Рисунок 4 – Исходный код и кодируемые последовательности.
|