Задание 1 – «Циклическое кодирование 4-х разрядных сообщений»

Стр 1 из 2Следующая ⇒

ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ

Федеральное государственное образовательное бюджетное учреждение

высшего профессионального образования

«ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ»

Кафедра информационных систем и технологий

А.С. Овсянников

КОДИРОВАНИЕ СООБЩЕНИЙ ДИСКРЕТНЫХ ИСТОЧНИКОВ И ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ

Методические указания по выполнению лабораторных работ

САМАРА 2016

УДК 681.323

БКК

Рекомендовано к изданию методическим советом ПГУТИ,

протокол № , от 00.00.2014 г.

Рецензенты:

Зав. каф. ИСТ Самарского национального исследовательского университета им.акад. С.П. Королёва, д.т.н., проф. С.А. Прохоров

Доцент каф. ПОВТиАС ПГУТИ, к.т.н., доц. В.В. Камышников

Овсянников А.С.

О Исследование методов кодирования сообщений дискретных источников и циклического помехоустойчивого кодирования информационных сигналов: методические указания по выполнению лабораторных работ по дисциплине “Теория информационных процессов и сетей”, часть 1/ А.С. Овсянников. - Самара: ПГУТИ, 2016.- 13 с.

Методические указания предназначены для студентов второго ускоренного и третьего полного курса факультета информационных систем и технологий ПГУТИ, обучающихся по специальности 09.03.02 “Информационные системы и технологии” в рамках специализации “Информационные системы и технологии”, изучающих дисциплину “Теория информационных процессов и систем”. Составлены применительно к действующему учебному плану по специальности 09.03.02 “Информационные системы и технологии”.

В указаниях учтены требования стандартов и нормативных документов, регламентирующих многоуровневую подготовку специалистов по направлению 09.03.02 Информационные системы и технологии.

Разработаны на кафедре информационных систем и технологий Поволжского государственного университета телекоммуникаций и информатики.

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

ISBN

©, Овсянников А.С., 2016

Лабораторная работа №1

“Исследование методов кодирования сообщений дискретных источников”

Цель работы

Изучить особенности и методы построения эффективных кодов и расчёт их информационных характеристик.

Литература

1. Овсянников А.С. Теория информационных процессов и систем: В 2 ч., Ч.1. Теоретические основы информационных процессов: Учеб. пособие / Поволж. гос. ун-т. телеком. и информ. Самара, 2016.- 131 с.

2. Овсянников А.С. Теория информационных процессов и систем:В 2 ч. Ч.1. Теоретические основы информационных процессов: Допущено Уч.-метод. объедин. вузов по политехн. образов. в качестве учебного пособия для студентов спец. 071900-“Информационные системы и технологии” Самарск.гос.арх.-строит.ун-т. Самара,2005. -100 с.

3. Передача дискретных сообщений: Учебник для вузов / Под ред. В.П.Шувалова.- М.:Радио и связь,1990, стр.146-155.

Выполнение работы

1. апустить программу SourceCode.exe.

2. При запуске программы появляется диалоговое окно первого шага исследований - равномерного кодирования, состоящее из четырёх окон и одной клавиши. В первом окне (нумерация окон – “сверху слева – направо вниз…”) в левом столбце заданы уникальные вероятности сообщений дискретного источника X= , N=8, задаваемые автоматически программой. Эта совокупность вероятностей является своеобразным вариантом выполнения лабораторной работы.

В последующие окна проставляются 1 и 0 в соответствии с алгоритмом равномерного кодирования.

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

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

3. В диалоговом режиме выполнить второй шаг - кодирование по методу Шеннона-Фано.

4. В диалоговом режиме выполнить третий шаг - кодирование по методу Хаффмена.

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

Контрольные вопросы

1. В каких условиях целесообразно применять эффективное кодирование?

2. Преимущества и недостатки эффективных кодов.

3. До какого предела может быть уменьшена средняя длина кодовой комбинации эффективного кода?

4. Как определяется средняя длина кодовой комбинации эффективного кода?

5. Сущность кодирования по методике Шеннона-Фано.

6. Алгоритм кодирования по методу Хаффмена.

7. Какой эффективный код называется префиксным?

8. Дайте определение понятию избыточности кода (коэффициент статистического сжатия).

9. Что называется коэффициентом относительной эффективности?

10. Чему равна минимальная длина двоичных кодовых комбинаций для 32 буквенного алфавита, если буквы в тексте встречаются с равными вероятностями?

11. Алфавит источника содержит шесть сообщений, передаваемых независимо друг от друга с вероятностями: Р₁= 0,4; Р₂= 0,3; Р₃= 0,1; Р₄= 0,08; Р₅= 0,07; Р₆= 0,05. До какого предела может быть уменьшена средняя длина кодовой комбинации эффективного кода?

12. Первичный алфавит состоит из четырёх равновероятных символов. Рассчитать коэффициент относительной эффективности.

13. Какой код позволяет минимизировать среднюю длину передаваемой кодовой комбинации?

Лабораторная работа №2

«Исследование методов циклического помехоустойчивого кодирования информационных сигналов»

Общие указания

Задание на лабораторную работу составлено в 100 вариантах. Значения параметров выбираются по двум последним цифрам номера студенческого билета по таблице 1.

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

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

Для успешной защиты лабораторной работы необходимо:

- внести исправления по замечаниям преподавателя, ответить (письменно или устно в зависимости от требований преподавателя) на поставленные вопросы;

- уметь полностью объяснить ход выполнения лабораторной работы, обосновать правильность использования расчётных формул, понимать смысл входящих в них величин и символов, их размерность.

Индивидуальные данные приведены в таблице 1

Таблица 1 – Индивидуальные данные

Заданный параметр		Предпоследняя цифра номера студенческого билета
Заданный параметр		0 0	I	2	3	4	5	6	7	8	9
4-х разрядное сообщение	k	0001	0010	0011	1100	0101	0110	0111	1000	1001	1010
	P_r	1011	1110	1010	1011	1110	1010	1011	1110	1010	1011
	K	0	1	2	3	4	5	6	2	3	4
5-ти разрядное сообщение	k	00011	00101	00111	01001	01011	01101	01111	10001	10011	10101
	P_r	10011	11101	10011	11101	10011	11101	10011	11101	10011	11101
	K	0	1	2	3	4	5	6	7	8	7
Т_пер		300	320	600	500	380	400	540	580	460	360
Заданный параметр		Последняя цифра номера студенческого билета
Заданный параметр		0 0	I	2	3	4	5	6	7	8	9
n		7 0	9	10	11	12	13	14	15	16	17
t_и.ош.		I	2	3	4	I	2	3	4	2	3

Цель работы

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

Литература

2. Овсянников А.С. Теория информационных процессов и систем: Теоретические основы информационных процессов: Допущено Уч.-метод. объедин. вузов по политехн. образов. в качестве учебного пособия для студентов спец. 071900-“Информационные системы и технологии” Самарск.гос.арх.-строит.ун-т. Самара,2005. -100 с.

3. Передача дискретных сообщений: Учебник для вузов / Под ред. В.П.Шувалова.- М.:Радио и связь,1990, стр.146-155.

Выполнение работы

1. Запустить программу Ciclic Code.exe.

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

3. В диалоговом режиме выполнить следующие задания:

a. – циклическое кодирование 4-х разрядных сообщений;

b. – циклическое кодирование 5-ти разрядных сообщений;

c. – определение образующего полинома циклического кода при двойной и тройной ошибке.

4. Составить отчёт по работе.

Содержание отчёта

1. Цель работы.

2. Screen Shot последовательности “окон” процесса выполнения работы.

3. Необходимые пояснения и расчёты.

4. Выводы по результатам выполнения заданий.

5. Для подготовки к теоретическому зачёту ответить на все контрольные вопросы.

Контрольные вопросы

1. В каких условиях целесообразно применять помехоустойчивое кодирование?

2. Преимущества и недостатки помехоустойчивого кодирования.

3. Определение помехоустойчивого кода.

4. Сформулировать условие обнаружения (исправления) на приеме ошибок.

5. Понятие простого кода. Расстояние Хемминга, вес кодовой комбинации и кодовое расстояние.

6. Условия обнаружения и исправлении ошибок, формулы кратности обнаружения и исправления ошибок помехоустойчивым кодом.

7. Классификация помехоустойчивых (корректирующих) кодов.

8. Основные показатели (формулы) эффективности применения кор-ректирующих кодов.

9. Основные понятия и свойства теории множеств: группа, поле Галуа.

10. Определение линейного кода. Алгоритм синтеза (построения) линейного кода. Образующая (производящая матрица). Понятие систематического кода.

11. Проверочная матрица и синдром линейного кода. Алгоритм обнаружения ошибки линейным кодом.

12. Структурные схемы кодера (передатчика) и декодера (приёмника) с обнаружением ошибок для кода (7,4).

13. Операция нахождения синдрома и структурная схема приёмника (декодирования) с исправлением ошибок для кода (7,4). Понятие вектора ошибок.

14. Простейший линейный код — код с одной проверкой на четность.

15. Коды Хэмминга.

16. Основное свойство (определение ) циклического кода. Общее свойство, синдром, описание и построение циклических кодов.

17. Порождающие (производящие, образующие) полиномы циклических кодов и их свойства. Выбор образующего многочлена (полинома).

18. Базис циклического кода, формирование кодовых комбинаций.

19. Синдром циклического кода и его свойства.

20. Алгоритм обнаружения и исправления ошибок на основе остатков от деления принятой кодовой комбинации на синдром.

21. Алгоритм обнаружения и исправления ошибок основанныё на анализе веса остатка остатков от деления принятой кодовой комбинации на синдром.

22. Коды БОУЗА - ЧОУДХУРИ – ХОКВИНГЕМА.

23. Алгоритм синтеза (построения) кодов БОУЗА - ЧОУДХУРИ – ХОКВИНГЕМА

Порядок выполнения работы

Для того чтобы приступить к выполнению работы необходимо пройти тест для получения допуска к выполнению работы, для чего необходимо “кликнуть” по пункту меню “Вопросник” (рис.1) При неудачном тестировании изучить теорию помехоустойчивого кодирования по учебному пособию.

Рис.1 – главное меню программы

Задание 1 – «Циклическое кодирование 4-х разрядных сообщений».

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

- информационная тчасть кодовой комбинации;

- выберете образующий полином.

Рис. 2 – Меню задание 1 – «Циклическое кодирование 4-х разрядных сообщений»

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

Кодовая комбинация циклического кода получается путем сложения по модулю 2 семи- разрядного вектора ошибки (см. [1]), определяемого заданным полем меню (рис. 2) и остатка от деления полученной промежуточной кодовой комбинации на заданный образующий полином (см. рис.2):

Для продолжения исследования необходимо ввести кодовую комбинацию циклического кода – в окно ввода (см. рис.2) и нажать кнопку «Расчет циклического кода».

Необходимо установить разряд, в котором произошла ошибка в соответствующем окне (см. рис.2) и нажать на кнопку "Подтверждения принятия кодовой комбинации".

Алгоритм обнаружения и исправления ошибки, ( см. Пример 3.13 [1]):

1. Делим принятую кодовую комбинацию на образующий полином.

2. Если вес остатка равен единице то ошибка обнаружена.

3. Если вес остатка неравен единице, то осуществляем циклический сдвиг кодовой ком6инации на один разряд влево.

4. Делим полученную кодовую комбинацию на образующий полином, в зависимости от веса остатка.

5. Складываем кодовую ком6инатщю с остатком от деления по модулю 2.

6. Осуществляем циклический сдвиг вправо на такое количество

разрядом, сколько раз мы осуществляли сдвиг влево.

В соответствии с алгоритмом делим принятую кодовую комбинацию на образующий полином.

Вводим остаток от деления в окно ввода и нажимаем на кнопку

«Проверка принятой кодовой комбинации».

Если вес остатка не равен единице, переходим к третьему, четвёртому и т.д. шагам до тех пор, пока вес остатка не будет равен единице - ошибка обнаружена.

Для продолжения исследования, согласно алгоритму, производим сложение кодовой комбинации с остатком от деления:

Необходимо ввести полученную после сложения кодовую комбинацию в окно «Введите информационную часть кодовой комбинации», находящееся в нижней части экрана и нажать на кнопку «Исправить принятую кодовую комбинацию».

Затем на экран выводятся два сообщения.

Рис. 3 – Выводимые сообщения по завершении выполнения 1 задания.

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

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

«Продолжение исследования ».

Задание 2 – "'циклическое кодирование 5-ти разрядных сообщений"

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

- информационную часть кодовой комбинации;

- выберете образующий полином.

Рис. 4 – Меню задания 2 – «Циклическое кодирование 5-х разрядных сообщений»

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

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

Полученную кодовую комбинацию циклического кода необходимо ввести в окно ввода (Рис. 4) и нажать на кнопку «Расчет циклического кода».

Необходимо установить разряд (в соответствии с вариантом), в котором произошла ошибка в соответствующем окне (см. рис.4) и нажать на кнопку "Подтверждения принятия кодовой комбинации".

. Затем ввести остаток от деления и нажать на кнопку «Подтверждение принятой кодовой комбинации»

Алгоритм обнаружения и исправления ошибки:

1. Делим вектор ошибки, в котором разряд (в соответствии с вариантом), в котором произошла ошибка равен единице, а все остальные равны нулю. Запоминаем остаток от деления.

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

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

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

5. При равенстве остатка полученного на первом шаге с остатком

полученным в ходе повторения шагов два и три и т.д. приступаем к

исправлению кодовой комбинации циклического кода.

6. Считаем сколько раз мы добавляем нулевой разряд – в таком разряде мы и имеем ошибку. Если разряд нулевой, то заменяем 0 на 1 и наоборот.

Для продолжения исследования необходимо ввести полученный остаток от деления в окно ввода и нажать на кнопку «Подтверждение принятой кодовой комбинации». Запомним полученный остаток от деления.

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

Вводим полученный остаток от деления в окно ввода и нажимаем на кнопку «Сравнение остатков от деления»

Остатки, полученные на первом и втором шагах алгоритма не равны, переходим к третьему, четвёртому и т.д. шагам до тех пор, пока остаток, полученный на данном шаге не будет равен остатку, полученному на первом шаге. Для исправления принятой кодовой комбинации необходимо нажать на кнопку «Исправить принятую кодовую комбинацию».

Рис.5 – Сообщение программы при завершении задания 2.

Переходим к последнему шагу алгоритма. Нулевой разряд к остатку мы добавляли один раз, поэтому по алгоритму

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

Ошибка обнаружена и успешно исправлена. Для продолжения исследования необходимо нажать на кнопку «Продолжение исследования».

Дата добавления: 2018-04-04; просмотров: 970; Мы поможем в написании вашей работы!
Поделиться с друзьями:

12 Следующая ⇒

Мы поможем в написании ваших работ!