Код построен по матрице

РОССИЙСКОЙ ФЕДЕРАЦИИ

ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Факультет прикладной математики и телекоммуникаций

Кафедра радиоэлектронных средств

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

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

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

Вариант 20

Киров 2004

Задание 1.1 Источник сообщения выдает символы из ансамбля А={a_i}. Распределения вероятностей приведены в таблице 1. Найти количество информации, содержащееся в каждом из символов источника при независимом выборе (источник без памяти). Вычислить энтропию и избыточность заданного источника.

Таблица 1

Количество информации в передаваемом символе определяется в битах. Чем меньше вероятность появления того или иного символа, тем больше количество информации извлекается при его получении. Если источник может выдать один из двух независимых символов (а₁ и а₂) и первый из них выдается с вероятностью р(а₁)=1, то символ а₁ не несет информации, ибо он заранее известен получателю.

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

I(a_i)=log₂1/p(a_i)= -log₂p(a_i).

I(a₁)= -log₂0, 01 = 6, 62;

I(a₂)= -log₂0, 1= 3, 32;

I(a₃)= -log₂0, 1= 3, 32;

I(a₄)= -log₂0, 12= 3, 06;

I(a₅)= -log₂0, 35 = 1, 52;

I(a₆)= -log₂0, 2= 2, 32;

I(a₇)= -log₂0, 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.2 Память двоичного стационарного источника с символом 0 и 1 простирается лишь на два соседних символа и, следовательно, дискретная последовательность символов, выдаваемых источником, описывается простой цепью Маркова с матрицей переходных вероятностей:

Р(1/1^′ ) P(1/0^′ )

P(0/1^′ ) P(0/0^′ ),

Где Р(а_i/a_j^′ )-вероятность символа а_i при условии, что ему предшествует символ а_j^′ .

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

Р= 0, 25 0, 65

0, 75 0, 35

Решение:

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

Р(0)=Р(0)Р(0/0^′ )+[1-P(0)]P(0/1^′ )

Переходные вероятности равны:

Энтропия источника:

Избыточность источника:

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

Нmax (А)= - Р(1)log₂ P(1) - P(0)log₂P(0)=

= -0, 464 log₂0, 464 – 0, 536 log₂0, 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Некоторый дискретный источник выдает символы из ансамбля {a_i}, с вероятностями приведенными в таблице 1. Закодировать символы данного ансамбля кодом Хаффмена, кодом Шеннона-Фано и равномерным кодом. Определить среднюю длину кодовой комбинации и сравнить с энтропией сообщения. Показать, какой код является наиболее эффективным.

Решение:

Код Хаффмена:

а₅ 0, 35 0, 59 11

а₆ 0, 20 1, 00 00

а₄ 0, 12 0, 41 001

0, 24

а₇ 0, 12 101

а₂ 0, 10 010

а₃ 0, 10 0, 21 1110

0, 11

а₁ 0, 01 0110

Средняя длина кодовой комбинации данного кода:

Код Шеннона-Фано:

а5 0, 4 } 1 11

а6 0, 18 1 } 0 10

а4 0, 1 } 1 011

а7 0, 1 1 } 0 010

а2 0, 07 } 1 001

а3 0, 06 0 } 1 0001

а1 0, 05 0 0 } 0 0000

При оптимальном двоичном кодированием энтропия сообщения:

Равномерный код:

Число разрядов в кодовых комбинациях равно n=log₂8=3

Граф трехразрядного двоичного кода:

0 1

0 1 0 1

0 1 0 1 0 1 1

а₅ а₁ а₄ а₃ а₇ а₂ а₆

Таблица 2 - Кодовые комбинации:

Средняя длина кодовой комбинации кода Хаффмена отличается от средней длины кодовой комбинации по Шеннону-Фано на:

Средняя длина кодовой комбинации равномерным кодом отличается от средней длины кода по Шеннону-Фано на:

Следовательно код Хаффмена и Шеннона-Фано являются наиболее эффективными

Задание 2.2 Пусть алфавит содержит лишь две буквы а₁ и а₂, появляющиеся с вероятностями р(а₁) и р(а₂) Применив метод Шеннона-Фано закодировать сначала каждую букву по отдельности, затем закодировать двух- и трех- буквенные комбинации. Определить среднюю длину кодовой комбинации для трех случаев и сравнить ее с энтропией сообщения. Определить наилучший результат кодирования.

Таблица 3

Решение:

Закодируем каждую букву по отдельности:

а₂ 0, 5 } 1

a₁ 0, 5 } 0

Средняя длина кодовой комбинации данного кода равна:

Закодируем двухбуквенную комбинацию:

а₂ а₂ 0, 25 1 11

a₁ a₂ 0, 25 0 10

a₂ a₁ 0, 25 1 01

a₁ a₁ 0, 25 0 00

Средняя длина кодовой комбинации данного кода равна:

Закодируем трехбуквенную комбинацию:

а₂ а₂ а₂ 0, 125 1 111

а₂ а₂ а₁ 0, 125 0 110

а₂ а₁ а₂ 0, 125 1 101

а₁ а₁ а₂ 0, 125 0 100

а₁ а₁ а₂ 0, 125 1 011

а₁ а₂ а₁ 0, 125 0 010

а₂ а₁ а₁ 0, 125 1 001

а₁ а₁ а₁ 0, 125 0 000

Средняя длина данной кодовой комбинации равна:

Энтропия сообщения для однобуквенного кода равна:

Энтропия сообщения для двухбуквенного кода равна:

Энтропия сообщения для трехбуквенного кода равна:

Длина для двухбуквенного кода:

Для трехбуквенного кода:

Задача3.1. Сообщения источника, имеющего алфавит с объемом К, кодируется двоичным блочным кодом. Число разрядов в каждой кодовой комбинации п. Какое число информационных и проверочных символов содержится в каждой кодовой комбинации? Сколько разрешенных и запрещенных комбинаций в используемом коде? Определить избыточность и относительную скорость кода.

Решение:

Число информационных символов:

Число проверочных символов:

Число разрешённых комбинаций:

Число запрещённых комбинаций:

Избыточность кода:

Относительная скорость хода:

Задача3.2. Определить минимальное кодовое расстояние для кодов обнаруживающих ошибок и исправляющих ошибок:

Решение:

Минимальное кодовое расстояние:

исправляющий ошибки;

обнаруживающий ошибки;

Задача 3.3. Двоичный код, предназначенный для кодирования п сообщений, содержит кодовые комбинации:

Таблица 4

n

Решение:

Является ли данный код линейным? Найти избыточность и относительную скорость кода.

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

и т.д.

Избыточность кода:

Относительная скорость кода:

Задание 3.4Построить порождающую матрицу для кода с кодовым раcстоянием d_min=3, количеством информационных элементов k=2. Написать правила формирования проверочных элементов для полученного кода. Найти проверочную матрицу. Определить сколько ошибок такой код может обнаружить, сколько ошибок он может исправить. Нарисовать структурную схему кодирующего и декодирующего устройства. Составить таблицу соответствия между местоположением одиночных ошибок и видом синдрома.

Решение:

Число информационных разрядов кода k=2, значит число строк порождающей матрицы G должно быть равным 2. Число столбцов матрицы G равно длине кода, который равен сумме чисел корректирующих и информационных разрядов.

Для расчетов контрольных разрядов с минимальным кодовым расстоянием d_min= 3 воспользуемся следующими выражениями: каждая строка приписанной части единичной матрицы должна содержать d_min-1 единиц, а сумма по модулю 2 не менее d_min-2. Следовательно, число столбцов, содержащих контрольные разряды должно быть равно 3, а общее число столбцов матрицы G равно 5.

Построим порождающую матрицу G:

10 011

G =

01 110

Правила формирования проверочных элементов для полученного кода:

а₃ = а₂; а₄ = а₁ Å а₂; а₅ = а_1.

Проверочная матрица задает правила кодирования линейного кода и определяет схему кодирующего устройства:

Определим, сколько ошибок данный код может обнаружить:

d_min= r + 1 Þ r = d_min – 1 = 3 –1 =2, т.е. число обнаруживаемых ошибок равно 2.

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

d_min= 2t_и + 1 Þ t_и =

t_и = 1, код исправляет одну ошибку.

Рисунок 2 – Схема кодирующего устройства

Рисунок 3 – Схема декодирующего устройства

Таблица соответствия между местоположением одиночных ошибок и видом синдрома:

Таблица 5

Задача 3.5 Определить, какие из приведенных кодовых комбинаций линейного кода содержат ошибку:

а₁=1000100

а₂=1001010

Решение:

Код построен по матрице

1000111

G = 0100011

Найдем правила получения проверочных элементов:

а₅ = а₁ Å а₃ Å а₄ b₁ = a₁ Å a₃ Å a₄ Å a₅

а₆ = а₁ Å а₂ Å а₃ b₂ = a₁ Å a₂ Å a₃ Å a₆

а₇ = а₁ Å а₂ Å а₄ b₃ = a₁ Å a₂ Å a₄ Å a₇

Кодовая комбинация а₁=1000100

b₁ =1 Å 0 Å 0 Å 1 = 0

b₂ =1 Å 0 Å 0 Å 0 ¹ 0

b₃ =1 Å 0 Å 0 Å 0 ¹ 0

Синдром двух кодовых комбинаций не равен нулю, содержит ошибки.

Кодовая комбинация а₂=1001010

b₁ = 1 Å 0 Å 1 Å 0 = 0

b₂ = 1 Å 0 Å 0 Å 1 = 0

b₃ = 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 – Исходный код и кодируемые последовательности.