НЕКОММЕРЧЕСКОЕ АКИОЕНЕРНОЕ ОБЩЕСТВО
АЛМАТИНСКИЙ ИНСТИТУТ ЭНЕРГЕТИКИ И СВЯЗИ
Кафедра автоматической электросвязи
ТЕОРИЯ ИНФОРМАЦИИ
Методические указания к выполнению расчетно-графической работы
(для студентов очной формы обучения специальности 050704 - Вычислительная техника и программное обеспечение)
Алматы 2008
СОСТАВИТЕЛИ: А.Д. Джангозин, К.С. Чежимбаева.
Теория информации. Методические указания к выполнению расчетно-графической работы (для студентов всех форм обучения специальности 050704 - Вычислительная техника и программное обеспечение).- Алматы: АИЭС, 2008.- 15с.
Методические указания содержат задания к двум расчетно-графическим работам с исходными данными более 100 вариантов заданий, а также требования к содержанию и оформлению РГР. Кроме того, дан перечень рекомендуемой литературы.
Методические указания предназначены для студентов специальности 050704 - Вычислительная техника и программное обеспечение.
Предисловие
Дисциплина «Теория информации» относится к числу фундаментальных дисциплин для подготовки бакалавров, владеющих современными методами анализа и синтеза систем и устройств связи различного назначения.
Современный бакалавр, проектируя систему связи, удовлетворяющей конкретным техническим требованиям, должен уметь также оценить, достаточно ли полно в проектируемой системе связи реализуются потенциальные возможности выбранных способов передачи, модуляции, кодирования, и определить пути улучшения характеристик системы связи для приближения их к потенциальным.
Целью курса является изучение основных закономерностей и методов передачи информации по каналам связи, способов приема и повышения верности передачи. В курсе «Теория информации» рассматриваются характеристики сигналов используемых для передачи сообщений, способы математического представления сообщений, сигналов и помех, методы формирования сигналов и их преобразования в электрических цепях, вопросы анализа помехоустойчивости и пропускной способности систем электросвязи, методы помехоустойчивого кодирования, оптимального приема сообщений, принципы многоканальной передачи, вопросы оптимизации систем связи. Курс «Теория информации» составляет теоретическую основу техники связи, изучаемой в последующих дисциплинах.
Дисциплина «Теория информации» изучается студентами на втором курсе в четвертом семестре. В результате изучения этой дисциплины студенты получают знания по построению систем связи, анализу эффективности этих систем, выбору методов передачи и приема сигналов в системах связи, а также по повышению помехоустойчивости их приема.
В четвертом семестре студенты сдают по дисциплине экзамены комплексного вида. Вначале проводится тестирование по 30-ти вопросам, для прохождения которого необходимо правильно ответить на 16 и более вопросов. Студенты, сдавшие тест, могут получить удовлетворительную оценку. Для получения более высокой оценки необходимо сдать письменный экзамен по дисциплине. В экзаменационный билет входят 1 задача и 2 теоретических вопросов. Для получения хорошей оценки необходимо правильно решить задачу и пояснить ее решение письменно. Для получения отличной оценки необходимо письменно ответить на 2 теоретические вопросы и быть готовым дать устные пояснения по их сути, если этого потребует экзаменатор.
По дисциплине «Теория информации» выполняется расчетно-графическая работа.
Расчетно-графическая работа, выполняемая студентами в процессе учебы, поможет студентам более основательно освоить разделы курса.
РГР «Теория информации» позволит получить навыки в решении задач, встречающихся в практике.
РГР включает два задания: в первое задание входит разработка схем кодеров и декодеров циклического кода, во второе – разработка схемы оптимальной системы связи и расчет ее параметров. Совместное их решение раскрывает выполнение основной цели задания – моделирование телекоммуникационных систем. Студенты должны по варианту собрать схему с применением пакета «System View» для моделирования телекоммуникационных систем, кодирующего и декодирующего устройства циклического кода с использованием модуляции и демодуляции. Прежде чем приступить к выполнению заданий по «Теории информации», ознакомьтесь с требованиями к выполнению и оформлению РГР и с порядком выбора варианта.
1 Требования к выполнению и оформлению РГР
1.1 Выбор варианта
Номер варианта соответствует двум последним цифрам (предпоследней и последней) номера зачетной книжки. Например, если номер зачетной книжки 200002, то номер варианта будет 02.
1.2 Требования к выполнению заданий РГР
Решение каждой задачи следует начинать с изучения относящегося к теме задания теоретического материала. В этом поможет учебная литература, приведенная в списке рекомендованной литературы. Выполнять задания нужно вдумчиво, четко представляя ход решения, обосновывая полученный результат.
Проверенная работа должна быть защищена. После допуска к защите студент в назначенное преподавателем время защищает её. Для успешной защиты необходимо внести исправления по замечаниям преподавателя, уметь полностью объяснить ход решения задач, обосновать правильность использования расчетных формул, знать смысл входящих в них символов.
Во время защиты РГР каждый студент должен быть готов дать пояснения по решению задач заданий.
Следует помнить, что РГР, выполненная небрежно, не полностью, или не по своему варианту, не принимается и подлежит переоформлению, доработке или переделке.
1.3 Требования к оформлению РГР
Пояснительная записка расчетно-графической работы составляется и оформляется, согласно фирменному стандарту по учебным работам [11].
1.3.1 Расчетно-графическая работа выполняется на листах белой или в клетку бумаги формата А4. Она должна быть аккуратно оформлена, текст разборчиво написан или напечатан (компьютерный набор) на одной стороне листа. Другая сторона листа предназначена для внесения студентом исправлений и дополнений по результатам проверки работы.
1.3.2 В начале каждого задания приводятся условие задачи и исходные данные для своего варианта.
1.3.3 Страницы текста, рисунки, таблицы и формулы нумеруются. Все вычисления приводятся достаточно полно, чтобы можно было проверить их правильность, и сопровождаются необходимыми пояснениями.
1.3.4 Расчетные формулы записываются в общем виде с расшифровкой буквенных обозначений и указанием размерностей. Все числовые значения необходимо подставлять только в основных единицах.
В тексте работы должны быть краткие пояснения решения задачи, а также ссылки на использованную литературу при приведении формул, схем, теоретического материала.
Расчетно-графическая работа, выполненная без соблюдения перечисленных требований, возвращается на доработку.
2 Задания курсовых работ и методические указания к ним
2.1 Задание №1
Задание 1
Разработать структурные схемы кодера и декодера кода Хэмминга, исправляющего однократные ошибки.
Необходимо:
а) определить параметры (n, k) кода: минимальное кодовое расстояние d0, минимально необходимое число проверочных элементов кода r, позволяющее обеспечить данное кодовое расстояние и общую длину кодовой комбинации n корректирующего кода при заданном количестве информационных элементов – k (таблица 2).
б) для заданной кодовой комбинации простого кода Q(0,1) (таблица 2) составить кодовую комбинацию кода Хэмминга F(0,1).
в) составить образующую (порождающую) и проверочную матрицы кода Хэмминга, а также матрицу синдромов при однократной ошибке в различных разрядах.
г) для декодирования методом вычисления синдрома, проверить, будет ли исправлена на приеме однократная ошибка в i-м разряде (таблица 2) при работе в режиме исправления однократной ошибки и обнаружена двукратная ошибка при ошибках в i-м и j-м разрядах (таблица 2) при работе в режиме обнаружения ошибок.
д) построить схему кодера данного кода.
е) построить схему декодера данного кода при работе в режиме исправления однократной ошибки.
ж) на основе составленной кодовой комбинации кода Хэмминга (пункт б) составить кодовую комбинацию кода Хэмминга с минимальным кодовым расстоянием d0=4, обнаруживающего трехкратные ошибки или обнаруживающего двукратные ошибки и одновременно исправляющего однократную ошибку.
з) составить проверочную матрицу кода Хэмминга с d0=4.
и) для кодовой комбинации кода Хэмминга с минимальным кодовым
расстоянием d0=4 проверить, будет ли исправлена однократная ошибка в i-м разряде и одновременно обнаружена двукратная ошибка (в i-м и j-м разрядах кодовой комбинации), при работе в режиме исправления и обнаружения ошибок.
Т а б л и ц а 1- Исходные данные
|
Последняя цифра номера варианта |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
Первая половина кодовой комбинации |
10 |
110 |
0010 |
00011 |
01 |
011 |
1000 |
11011 |
101 |
10010 |
|
Ошибочные разряды i
j |
1 |
2 |
3 |
5 |
4 |
2 |
4 |
6 |
5 |
7
|
|
3 |
5 |
6 |
7 |
1 |
3 |
2 |
4 |
3 |
6
|
|
|
Предпоследняя цифра номера варианта |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
Вторая половина кодовой комбинации |
10 |
111 |
1001 |
10110 |
11 |
101 |
1010 |
01010 |
1111 |
10000 |
2.2 Методические указания к заданию №1
Для выполнения задания необходимо проработать материал по основам помехоустойчивого кодирования, принципам построения кодов Хэмминга с d0=3 и d0=4, принципу обнаружения и исправления ошибок в кодовых комбинациях кодов Хэмминга, понять смысл основных его параметров [8, стр. 106-110, 124-127; 9, стр. 263], обратив особое внимание на параметры 6.2 [8] и 7.6 [9]:
а) следует уяснить понятия кодового расстояния, минимального кодового расстояния и его связь с кратностью исправляемых ошибок. Необходимо разобраться с соотношением информационных и проверочных элементов в кодовой комбинации в зависимости от требуемого минимального кодового расстояния кода, с правилом выбора образующего полинома кода и с алгоритмом построения кодовых комбинаций циклического кода [8, стр. 104, 114, таблица 6.2, 112-113].
Пункт задания а) следует выполнять в следующей последовательности: определить d0, затем r и n, записать параметры кода (n, к.). Все расчеты следует сопровождать пояснениями.
При определении минимального кодового расстояния' d0 кода, который может исправить tиспр. ошибки, воспользуйтесь выражением (18.4) [7] или (6.6) [8].
Минимальное кодовое расстояние определяется по формуле
(1)
где tиспр. - кратность исправляемых ошибок.
Следует помнить, что только для кода с d0=3 известно точное соотношение для определения количества проверочных элементов r: (6.9) [8], где n = k+r. Здесь k-длина кодовой комбинации простого кода (количество информационных элементов): n- общая длина кодовой комбинации корректирующего кода. Это соотношение можно также представить в виде
2r>k + r+l, или r>log2(k + r+1). (2)
Используя это соотношение, начиная с меньшего значения г, можно путем подбора найти его минимальное значение, которое будет удовлетворять данному соотношению. Общая длина кодовой комбинации циклического кода при этом составит n= k + г.
б) этот пункт задания следует выполнить только в цифровом виде. Вначале составляется таблица синдромов кода, аналогично таблице 6.1 [8, стр. 108]. По ней составляется алгоритм расчета проверочных элементов, аналогично [8, стр. 109], затем проводится их расчет и составление кодовой комбинации кода Хэмминга аналогично примеру 6.2 1 [8, стр. 109-110].
в) матричное представление систематических кодов приведено в [8, стр. 118-123, примеры 6.7, 6.8, стр. 109]. Образующая матрица кода G может быть составлена путем формирования кодовых комбинаций кода Хэмминга на основе кодовых комбинаций простого кода весом W=1. Проверочную матрицу кода можно составить на основе образующей матрицы по выражению их взаимосвязи
Hr.n=RT k,r * Er,r, (3)
где Hr,n- проверочная матрица размером r строк и k столбцов;
Rтk,r- транспонированная проверочная подматрица (размером k строк и r столбцов) образующей матрицы;
Е r, r-единичная квадратная подматрица размером г строк и г столбцов.
Для кода Хэмминга предпочтительнее вначале составить проверочную матрицу по выведенному алгоритму расчета проверочных элементов, а затем построить образующую матрицу кода. Матрица синдромов полностью соответствует таблице синдромов кода, составленной в пункте б) данного задания. Пример проверочной матрицы кода Хэмминга (9,5) приведен в [8, стр. 109];
г) проверить возможность исправления однократной ошибки в i-м разряде кодовой комбинации, при декодировании можно путем внесения ошибки в этот разряд кодовой комбинации и определения синдрома. Совпадение получившегося при этом синдрома с синдромом ошибки в этом разряде (в матрице синдромов) говорит о том, что она может быть исправлена. Порядок декодирования этим методом приведен в [8, стр. 106-108, стр. 109, пример 6.2].
Для проверки возможности обнаружения двукратной ошибки (в i-м и j-м разрядах кодовой комбинации) нужно внести ошибки в эти разряды кодовой комбинации циклического кода и, разделив полученную комбинацию на образующий полином, найти синдром при ошибке в этих разрядах. Совпадение получившегося при этом синдрома с синдромом при однократной ошибке в каком-то одном разряде кодовой комбинации (по матрице синдромов) или отсутствие данного синдрома в матрице синдромов говорит о том, что двукратная ошибка может быть обнаружена (синдром не нулевой), но не может быть исправлена (синдром совпадает с синдромом при ошибке в другом разряде или отсутствует). Можно также найти все виды синдромов при двукратных ошибках в кодовой комбинации. Совпадение синдромов для разных вариантов двукратных ошибок говорит о невозможности их исправления, можно только их обнаружить;
д) схема кодера кода Хэмминга может быть реализована аналогично схеме на рисунке 6.5 [8, стр. 124]. Здесь не требуется составления таблицы состояний ячеек в схеме кодера при кодировании заданной кодовой комбинации простого кода;
е) схема декодера кода Хэмминга реализуется аналогично схеме на рисунке 6.6 [8, стр. 125]. Необходимо составить схему декодера, включая схему определения синдромов, схему дешифратора синдромов и схему исправления однократной ошибки. Здесь не требуется составление таблицы состояний ячеек в схеме декодера при декодировании принимаемой кодовой комбинации кода Хэмминга;
ж) пример составления кодовой комбинации кода Хэмминга с d0=4 приведен в [9, стр. 263, пример 7.6];
з) операция декодирования кода Хэмминга с d0=4 в [9, стр. 263];
и) пример составления кодовой комбинации кода Хэмминга с d0=4 приведен в [9, стр. 263, пример 7.6]. Необходимо внести ошибки в i-й и j-й разряды кодовой комбинации кода Хэмминга с минимальным кодовым расстоянием d0=4, определить синдром и, проведя его анализ, показать, возможность одновременного исправления ошибки в i-м и обнаружения ошибки j-м разрядах кодовой комбинации. Возможность исправления ошибки доказывается соответствием полученного синдрома синдрому ошибки в этом разряде. Для этого необходимо составить матрицы синдромов этого кода при однократных и двукратных ошибках.
2.3 Задание №2
Разработать структурные схемы кодера и декодера циклического кода, исправляющего однократные ошибки.
Алфавит источника дискретных сообщений содержит N знаков (N знаков выбирается как число ближе к варианту), кодируемых кодовыми комбинациями равномерного двоичного кода. Источник сообщений выдает кодовые комбинации со скоростью В. Вероятность появления элемента «1» кодовой комбинации – р(1). Составление кодовой комбинации соответствует двум последним цифрам (предпоследней и последней) номера зачетной книжки.
Т а б л и ц а 2 – Исходные данные
|
Первая буква фамилии |
А Л Х |
Б М Ц |
В Н Ч |
Г О Ш |
Д П Щ |
Е Р Э |
Ж С Ю |
З Т Я |
И У |
К Ф |
|
р(1). |
0.5 |
0.7 |
0.3 |
0.6 |
0.8 |
0.4 |
0.5 |
0.7 |
0.6 |
0.3 |
|
Скорость Модуляции В, Бод |
50 |
100 |
70 |
60 |
80 |
150 |
160 |
200 |
90 |
120 |
Для этого необходимо:
а) определить производительность источника сообщений H/;
б) составить кодовую комбинацию знака (номер зачетной книжки предпоследней и последней), соответствующую параметрам источника сообщений;
в) определить количество информации, содержащейся в кодовой комбинации этого знака – Iзн;
г) если выбранный способ требует использования корректирующего кода, выбрать вид циклического кода, позволяющего достигнуть заданной верности и скорости передачи по каналу. Составить кодовую комбинацию циклического кода F(0,l) этого кода на основе кодовой комбинации простого кода и выбрать образующий полином Р(х).
д) получить схему кодирующего и декодирующего устройства циклического кода данного варианта, а также собрать схему с применением пакета «System View».
2.4 Методические указания к заданию №2
Для выполнения задания необходимо проработать материал по основным понятиям: информация, сообщение и т.д. [9, стр. 12-14].
а) среднее количество информации, выдаваемое источником в единицу времени, называют производительностью источника и определяют по формуле
(4)
где 
б)
Источник информации характеризуется алфавитом
передаваемых символов А. Пусть объем (число символов) этого алфавита 
, а вероятность выдачи
символа 
равна 
и число символов
определяется по формуле
(5)
Составим кодовую комбинацию знака (номер зачетной
книжки предпоследней и последней), соответствующую параметрам источника
сообщений: например: 
.
в) определяем количество информации, содержащейся в кодовой комбинации этого знака – Iзн;
(6)
где 
- количество элементов «1» в кодовой
комбинации знака;
- количество элементов «0» в кодовой
комбинации знака.
г) Для одностороннего канала используем помехоустойчивое кодирование кодом, исправляющим ошибки.
При
определении минимального кодового расстояния'
d0 кода, который
может исправить
tиспр. ошибки,
воспользуйтесь выражением (18.4) [7] или (6.6) [8]. Используем код, исправляющий однократную ошибку-
Минимальное кодовое расстояние определяется по формуле
(7)
где tиспр. - кратность исправляемых ошибок.
Следует помнить, что только для кода с d0=3 известно точное соотношение для определения количества проверочных элементов r: (6.9) [8], где n = k+r. Здесь k -длина кодовой комбинации простого кода (количество информационных символов (пункт б) ): n - общая длина кодовой комбинации корректирующего кода. Это соотношение можно также представить в виде
2r>k + r+l, или r>log2(k + r+1). (8)
Используя это соотношение, начиная с меньшего значения г, можно путем подбора найти его минимальное значение, которое будет удовлетворять данному соотношению. Общая длина кодовой комбинации циклического кода при этом составит n= k + г.
Необходимо выбрать образующий полином и составить кодовую комбинацию циклического кода. Составление кодовой комбинации циклического кода нужно провести как в алгебраическом, так и в цифровом видах.
Кодирование циклическим кодом рассмотрено в примерах 18.5 [7], 6.3 [8].
Образующий полином кода можно выбрать из таблицы 18.1 [7, стр.316] или из таблицы 6.2 [8, стр.114], таблицы 7.2 [9, стр. 268]. В [8, 9] образующие полиномы приводятся в цифровом и в алгебраическом видах. Следует помнить, что степень образующего полинома кода должна быть равна количеству проверочных элементов кода г. Внимательно выбирайте образующий полином, т.к. в некоторых учебниках таблицы полиномов имеют ошибки ([9, таблица 7.2], несоответствие полиномов в алгебраическом и цифровом видах для г=4).
Представление двоичных чисел в цифровом и алгебраическом видах, а также проведение операций сложения и деления над ними пояснено в [7, стр.315; 8, стр. 110-111]. Примеры деления кодовых комбинаций на образующий полином в цифровом и алгебраическом видах приведены в [8, стр. 113, 315, 117, 118]. Пример построения кодовой комбинации циклического кода в алгебраическом и цифровом видах приведен в [8, стр.113-114, пример 6.3].
После составления кодовой комбинации циклического кода F(0,l) проверьте ее правильность. Проверка правильности составления кодовой комбинации циклического кода осуществляется путем ее деления на образующий полином Р(0,1). Получение нулевого остатка (деление без остатка) говорит о правильности составления кодовой комбинации, т. е. что это разрешенная кодовая комбинация циклического кода. Получение же ненулевого остатка (наличие остатка) говорит о неправильном составлении кодовой комбинации, т.е. что это запрещенная кодовая комбинация циклического кода;
д) получить схему кодирующего и декодирующего устройства циклического кода данного варианта, а также собрать схему с применением пакета «System View». Этот пункт выполняется в соответствии с лабораторной работой №4.
Список литературы
1. Скляр Б. Цифровая связь. Теоретические основы и практическое применение: 2-е изд. /Пер. с англ.- М.: Издательский дом «Вильямс», 2003. - 1104 с.
2. Прокис Дж. Цифровая связь. Радио и связь, 2000.-797с.
3. В.К. Душин. Теоретические основы информационных процессов и систем: Учебник. - М.: Издательство – торговая корпорация « Данников и К», 2003.
4. А.Б. Сергиенко. Цифровая обработка сигналов: Учебник для вузов. - М.:-2002.
5. В. Дьяконов. VisSim+Mathad+Matlab - визуальное математическое моделирование.-М.: « Солон- Пресс», 2004.
6. В.И. Карлащук. Электронная лаборатория на IBM PC.-М.,2005.-470с.
7. Панфилов И.П., Дырда В.Е.Теория электрической связи. - М.: Радио и связь, 1991.
8. Емельянов Г.А., Шварцман В.О. Передача дискретной информации.- М.: Радио и связь, 1982.
9. Передача дискретных сообщений/ В.П.Шувалов и др. Под ред. В.П.Шувалова. – М.: Радио и связь, 1990.
10. Фирменный стандарт. Работы учебные. Общие требования к построению, изложению, оформлению и содержанию. ФС РК 10352-1910-У-е-001-2002. – Алматы: АИЭС, 2002.
11. Колесник В.Д., Мирончиков Е.Т.. Декодирование циклических кодов.- М.: Связь, 1968.
12. Теория электрической связи/ Зюко А.Г. и др. Под ред. Д.Д. Кловского.-М.: Радио и связь, 1998.
13. Пенин П.И.. Системы передачи цифровой информации. – М.: Советское радио, 1976.
14. Справочник по специальным функциям с формулами, графиками и математическими таблицами/ под.ред. М. Абромовица и И.Стеган. – М.: Наука, 1979.
15. Аршинов М.Н., Садовкий Л.Е.. Коды и математика. – М.: Наука,1983.
16. Кловский Д.Д.. Теория передачи сигналов. – М.: Связь, 1973.
Содержание
|
Предисловие…………………………………………………………………... |
3 |
|
1 Требования к выполнению и оформлению РГР……………...…………… |
5 |
|
1.1 Выбор варианта……………………………………………………… |
5 |
|
1.2 Требования по выполнению курсовых заданий…………………… |
5 |
|
1.3 Требования к оформлению курсовой работы……………………… |
5 |
|
2 Задания курсовых работ и методические указания к ним……………….. |
6 |
|
2.1 Задание №1…………………………………………………………... |
6 |
|
2.2 Методические указания к заданию №1……………………………. |
7 |
|
2.3 Задание №2…………………………………………………………... |
9 |
|
2.4 Методические указания к заданию №2……………………………. |
10 |
|
Список литературы…………………………………………………………… |
13 |