Размещено на http://www.allbest.ru/

Министерство образования Республики Беларусь

БГУИР

Факультет заочного обучения

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

по дисциплине: «Теория преобразования и передачи измерительной информации»

Выполнил студент гр. 102502

Специальности ТОБ

Цыба М.Ю.

Проверил: Рак А.О.

2015

Содержание

• Задание 1
• Задание 2
• Задание 3
• Задание 4
• Задание 5
• Классификация кодов и их реализация
• Литература
• Задание 1
• С использованием алгоритмов Хаффмана и Шеннона-Фэно произвести эффективное кодирование сообщения. При кодировании распределение вероятностей различных букв сообщения определить из анализа сообщения.
• Кодируемое сообщение: АЛГОРИТМЫ ПРЕОБРАЗОВАНИЯ.
• Проанализируем данное сообщение.
• Буква А, Р и О встречаются 3 раза, И - 2 раза, остальные буквы встречаются по 1 разу. Всего в сообщении 24 символа
• По методике Хаффмана, это сообщение будет выглядеть следующим образом:
• 110110100101001000011011000000111001000101000001101001000000 010011111010011011100100011110101
• Эффективное кодирование с использованием алгоритма Шеннона - Фэно: кодирование шифрование полиномиальный сообщение
• По этой методике код строится следующим образом. Буквы алфавита сообщений выписываются в таблицу в порядке убывания вероятностей. Затем они разделяются на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы. Всем буквам верхней половины в качестве первого символа приписывается 1, а всем нижним - 0. Каждая из полученных групп разбивается на две подгруппы с одинаковыми суммарными вероятностями и т. д. Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.

Буква	Частота	1	2	3	4	5	Код
А	3/24	0 0 0 0 0	0 0	0			000	1	0,16
О	3/24			1			001	2	0,24
Р	3/24		1 1 1	0			010	3	0,36
И	2/24			1 1	0		011	4	0,48
Б	1/24				1		1000	5	0,4
В	1/24	1 1 1 1 1 1 1 1	0 0 0	0	1		1001	6	0,48
Пробел	1/24			1 1	0		1010	7	0,28
Г	1/24				1		1011	8	0,32
Е	1/24		0 0	0 0 0	0		1100	9	0,36
З	1/24				1 1	0	11010	10	0,4
М	1/24		0			1	11011	11	0,44
Л	1/24		1 1	0			1110	12	0,48
П	1/24			0	0		11110	13	0,52
Т	1/24	1	1	0	1		11111	14	0,56
Ы	1/24	1	1	1	0			15
Я	1/24	1	1	1	1			16

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

Задание 2

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

Кодируемое сообщение: АЛГОРИТМЫ ПРЕОБРАЗОВАНИЯ.

Записываем кодируемое сообщение в строки по 4 символа, затем считываем его по столбцам.

А	Л	Г	О
Р	И	Т	М
М	Ы	П	Р
Е	О	Б	Р
А	З	О	В
А	Н	И	Я

Зашифрованное сообщение: «АРМЕААЛИЫОЗНГТПБОИОМРРВЯ»

Задание 3

Используя шифрование с ключом, закодировать сообщения, используя в качестве ключа слова АЛГОРИТМ, РАЗРЯД, КОДИРОВАНИЕ.

Кодируемое сообщение: АЛГОРИТМЫ ПРЕОБРАЗОВАНИЯ.

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

А	Л	Г	О	Р	И	Т	М	Ы	П	Р	Е	О	Б	Р	А	З	О	В	А	Н	И	Я
1	13	4	16	18	10	20	14	29	17	18	6	16	2	18	1	9	16	3	1	15	10	33
А	Л	Г	О	Р	И	Т	М	А	Л	Г	О	Р	И	Т	М	А	Л	Г	О	Р	И	Т
1	13	4	16	18	10	20	14	1	13	4	16	18	10	20	14	1	13	4	16	18	10	20
2	26	8	32	36	20	40	28	30	30	22	22	34	12	38	15	10	29	7	17	33	20	53
Б	Ш	Ж	Ю	В	Т	Ё	Ъ	Ь	Ь	Ф	Ф	А	К	Д	Н	И	Ы	Ё	П	Я	Т	Р

А	Л	Г	О	Р	И	Т	М	Ы	П	Р	Е	О	Б	Р	А	З	О	В	А	Н	И	Я
1	13	4	16	18	10	20	14	29	17	18	6	16	2	18	1	9	16	3	1	15	10	33
Р	А	З	Р	Я	Д	Р	А	З	Р	Я	Д	Р	А	З	Р	Я	Р	А	З	Р	Я	Д
18	1	6	18	33	5	18	1	9	18	33	5	18	1	9	18	33	18	1	9	18	33	5
19	14	10	34	51	15	38	15	38	35	51	11	34	3	27	19	42	34	4	10	33	43	38
С	М	И	А	О	Н	Д	Н	Д	Б	О	Й	А	В	Щ	С	З	А	Г	И	Я	И	Д

А	Л	Г	О	Р	И	Т	М	Ы	П	Р	Е	О	Б	Р	А	З	О	В	А	Н	И	Я
1	13	4	16	18	10	20	14	29	17	18	6	16	2	18	1	9	16	3	1	15	10	33
К	О	Д	И	Р	О	В	А	Н	И	Е	К	О	Д	И	Р	О	В	А	Н	И	Е	К
12	16	5	10	18	16	3	1	15	10	6	12	16	5	10	18	16	3	1	15	10	6	12
13	29	9	26	36	26	23	15	44	27	24	18	32	7	28	19	25	19	4	16	25	16	45
Л	Ы	З	Ш	В	Ш	Х	Н	Й	Щ	Ц	Р	Ю	Ё	Ъ	С	Ч	С	Г	О	Ч	О	К

Задание 4

Дополнить по строкам и столбцам информационные двоичные блоки проверочными битами четности.

Проверочный бит четности равен сумме всех информационных символов по модулю 2.

1	1	0	1	1	1
1	1	1	0	0	1
0	0	1	0	0	1
1	1	0	0	0	0
1	1	0	1	1

Выходная последовательность: 100010, 111001, 011101, 010010, 010100

Задание 5

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

Образующий многочлен Q(x) = 1000100;

Производящий многочлен g(x)= x⁴+x³+x+1.

Представляем информационную часть кодовой комбинации длинной k в виде полинома Q(x):

Q(x) = 1000100=x⁶+x²

g(x)= x⁴+x³+x+1 (r=4)

Умножаем Q(x) на одночлен x^r:

Q(x)x^r= (x⁶+x²)x⁴=x¹⁰+x⁶

Делим полином Q(x)x^r на порождающий полином g(x) степени r, при этом получаем частное от деления С(х) такой же степени, что и Q(x):

x10+x6	x4+x3+x+1
x10+x9+x7+x6	x6+x5+x4+x2+x
x9+x7
x9+x8+x6+x5
x8+x7+x6+x5
x8+x7+x5+x4
x6+x4
x6+x5+x3+x2
x5+x4+x3+x2
x5+x4+x2+x
x3+x

Частное от деления

C(x)=x⁶+x⁵+x⁴+x²+x

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

R(x)=x³+x;

Для получения полиномиального кода остаток помещается на место пустых разрядов Q(x)x^r:

F(x)= Q(x)x^r + R(x)

F(x)= x¹⁰+x⁶+ x³+x > 10001001010

Классификация кодов и их реализация

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

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

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

Все корректирующие (избыточные) коды делятся на два больших класса: блочные и непрерывные коды (рис. 5.2).

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

В разделимых кодах всегда можно выделить информационные символы, содержащие передаваемую информацию, и контрольные (проверочные) символы, которые являются избыточными и служат исключительно для коррекции ошибок. Неразделимые коды не имеют четкого разделения кодовой комбинации на информационные и проверочные символы. К ним относятся коды с постоянным весом и коды Плоткина [2].

Разделимые блочные коды, в свою очередь, делятся на несистематические и систематические. Наиболее многочисленный класс разделимых кодов составляют систематические коды. Основная их особенность в том, что проверочные символы образуются как линейные комбинации информационных символов. К систематическим кодам относятся коды с проверкой на четность, коды с повторением, корреляционный, инверсный, коды Хэмминга, Голея, Рида-Маллера, Макдональда, Варшамова, с малой плотностью проверок на четность, итеративный код [2].

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

Разновидностью систематических кодов являются циклические коды. Кроме всех свойств систематического кода, циклические коды имеют следующее свойство: если некоторая кодовая комбинация принадлежит коду, то получающаяся путем циклической перестановки символов новая комбинация также принадлежит данному коду. К наиболее известным циклическим кодам относятся простейшие коды, коды Хэмминга, Боуза-Чоудхури-Хоквингема, мажоритарные, коды Файра, Абрамсона, Миласа-Абрамсона, Рида-Соломона, компаундные коды.

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

Литература

1. Теория преобразования и передачи измерительной информации: метод. указ. и контр. задания для студ. спец. 1-38 02 03 «Техническое обеспечение безопасности» заоч. формы обуч. / сост. В.Е. Галузо [и др.]. - Минск: БГУИР, 2007. - 34 с. : ил.

2. Кузьмин, И.В. Основы теории информации и кодирования/ И.В. Кузьмин. - Минск: Выш. Шк., 1986

3. Лидовскнй. В. И. Теория информации / В. И. Литовский. - М: Высш. шк., 2002.

Размещено на Allbest.ru

...