Учебное пособие: Методические указания для выполнения курсовой работы по информатике для студентов специальностей 220100 Вычислительные машины, комплексы, системы и сети

Калининградский Государственный Технический Университет

Методические указания

для выполнения курсовой работ ы

по информатике

для студентов специальностей

220100 – Вычислительные машины, комплексы, системы и сети

220200 – Автоматизированные системы обработки информации и управления

Калининград

200 3

УДК 621.38

УТВЕРЖДЕНО

Ректором Калининградского

государственного технического

университета

Автор – Топоркова О.М ., к.т.н., доцент кафедры систем управления и вычислительной техники Калининградского государственного технического университета

Методические указания рассмотрены и одобрены кафедрой систем управления и вычислительной техники 24 декабря 2003 г, протокол № 4

Рецензент – кафедра систем управления и вычислительной техники Калининградского государственного технического университета

©Калининградский государственный технический университет, 2003 г.

Введение

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

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

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

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

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

Часть 1. Кодирование дискретного сигнала

1.1 Кодирование кодами по образцу

Задание 1. Прямые коды

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

Указания по выполнению задания 1

Пусть фамилия, имя и отчество студента Петров Иван Васильевич. Тогда исходным текстом является текст

петровиванвасильевич, (1)

а алфавит А - это множество символов, {п, е, т, р, о, в, и, а, н, с, л, ь, ч}, т.е.

А = {п, е, т, р, о, в, и, а, н, с, л, ь, ч}. (2)

Для построения прямых кодов выполним следующую последовательность действий:

1) множество А упорядочим по алфавиту (графа 1 табл.1),

2) пронумеруем символы алфавита А, начиная с нуля (графа 2 табл.1),

3) определим мощность N алфавита А (т.е. число символов алфавита):

N = 13 (3)

4) используя комбинаторный подход к измерению информации, рассчитаем требуемый размер кода, достаточный для кодирования всех символов исходного алфавита А, по формуле:

l = [log_h N ] , (4)

где h – число символов, используемых для кодирования,

скобки [ ] означают округление результата до ближайшего большего целого числа.

Для нашего примера h = 2 (поскольку строится двоичный код), поэтому

l = [log₂ 13 ] = [3,7] = 4 , (5)

5) каждый номер символа представим четырехразрядным (как следует из шага 4) двоичным числом - получим код постоянной длины (графа 3 табл.1).

Таблица 1

Кодирование исходного текста дает (для простоты закодируем отдельно фамилию, имя, отчество)[1] :

петров 0111 0010 1010 1000 0110 0001

иван 0011 0001 0000 0101 (6)

васильевич 0001 0000 1001 0011 0100 1100 0010 0001 0011 1011

Задание 2. Коды, учитывающие частоту символов

Построить для алфавита А, полученного в задании 1, двоичные коды, учитывающие частоту символов. Расчет частоты выполнить по исходному тексту . Закодировать полученным кодом исходный текст .

Указания по выполнению задания 2

Для построения требуемых кодов выполним следующую последовательность действий:

1) для расчета частот символов из алфавита А (графа 1 табл. 2) определим число появлений m_i каждого i-го символа алфавита А в исходном тексте (графа 2 табл. 2),

Таблица 2

2) для определения размера кода вновь используем формулу l = [log_h N ] при N = 13, h = 2. Получаем:

l = [log_h 13 ] = [3,7] = 4 , (7)

3) используя комбинаторный подход к измерению информации, определим, сколько кодовых комбинаций можно получить из 4 двоичных разрядов, заполняя их нулями и единицами теми способами, которые показаны в графе 2 табл. 3. Чтобы решить эту задачу, установим, прежде всего, способ комбинирования символов двоичного алфавита (h = 2). Анализ кодов из табл. 1 показывает, что это перестановки с повторениями, для которых верно соотношение:

где П^п (h ) – число перестановок из h элементов с повторениями r_i ,

i – символ из множества символов, используемых для кодирования (у нас это множество {0,1}).

Теперь рассчитаем число кодовых комбинаций для каждого способа заполнения кодовых разрядов (графа 4 табл. 3).

Таблица 3

Суммирование полученного числа кодовых комбинаций (1+4+6+4+1=16) показывает, что для кодирования символов исходного алфавита А с заданной мощностью N достаточно принятых способов заполнения разрядов кода, поскольку 16>(N =13),

4) упорядочим список символов алфавита А по убыванию частоты. Получим табл. 4 (графы 1,2),

5) назначим символам коды постоянной длины, число единиц в которых тем больше, чем меньше частота символа (графа 4 табл. 4).

Таблица 4

Кодирование исходного текста полученным кодом дает результат (отдельно закодированы фамилия, имя и отчество):

петров 0110 0100 1100 0101 1001 0000

иван 0001 0000 0010 1010 (9)

васильевич 0000 0010 0011 0001 1000 1101 0100 0000 0001 1011

Задание 3. Коды Грея

Для символов алфавита А (из задания 1) построить код Грея. Закодировать полученным кодом исходный текст .

Указания к выполнению задания 3

Для построения кода Грея выполним следующие шаги:

1) исходя из мощности множества А, определим размер nxm таблицы для построения кода Грея, где n – число строк, m – число столбцов таблицы. Для этого будем последовательно наращивать число столбцов и число строк, начиная с одной строки и одного столбца, каждый раз проверяя, не достигнут ли требуемый размер таблицы. При этом схема наращивания числа строк и столбцов будет определяться следующим образом: число столбцов на каждом шаге итерации равно или на 1 превышает число строк (табл. 5).

Таблица 5

Поскольку на седьмом шаге итерации удалось достичь требуемого размера таблицы, определение ее размеров закончено. Таким образом, получена таблица размером 4х4,

2) строки и столбцы таблицы пронумеруем двоичными числами из множества {00, 01, 10, 11}, элементы которого сами являются кодами Грея (затушеванные ячейки табл. 6),

Таблица 6

3) разместим в ячейках таблицы упорядоченные по алфавиту символы исходного множества (см. графу 1 табл.1) в направлении, указанном стрелками в табл.6,

4) для формирования кода Грея по каждому символу объединим номера строки и столбца ячейки, в которой находится символ. Получим графу 2 табл. 7.

Таблица 7

Кодирование исходного текста полученным кодом дает результат:

петров 0100 0011 1111 1100 0101 0001

иван 0010 0001 0000 0111 (10)

васильевич 0001 0000 1101 0010 0110 1010 0011 0001 0010 1110

1.2. Криптографическое кодирование дискретного сигнала

Задание 4. Метод простой подстановки

Выполнить криптографическое кодирование исходного текста методом простой подстановки. Исходным алфавитом принять множество А (из задания 1). В качестве символов кодирования принять l -разрядные двоичные кодовые комбинации (величина l определена в задании 1), значение которых находится в пределах от 0 до двоичного эквивалента числа N -1, где N – мощность алфавита А.

Указания по выполнению задания 4

1) для построения кода составим таблицу соответствия между символами исходного алфавита А (графа 1 табл. 8) и произвольными 4-разрядными кодами (графа 3 табл.8). Для упрощения процедуры используем произвольный номер символа алфавита А в пределах от 0 до 12 (графа 2 табл. 8) (назначение номера выполнено бессистемно):

Таблица 8

2) для кодирования исходного текста используем табл.8. Получаем:

петров 0000 1100 0100 0010 0111 1011

иван 0001 1011 1001 0110 (11)

васильевич 1011 1001 0011 0001 1010 1000 1100 1011 0001 0101

Задание 5. Метод Вижинера

Выполнить криптографическое кодирование исходного текста методом Вижинера. Исходным алфавитом принять множество А (из задания 1). В качестве ключа кодирования использовать имя собственное. В качестве символов кодирования принять l -разрядные двоичные кодовые комбинации (величина l определена в задании 1), значение которых находится в пределах от 0 до двоичного эквивалента числа N -1, где N – мощность алфавита А.

Указания по выполнению задания 5

1) для построения кода пронумеруем символы исходного алфавита, начиная с 0, и каждому десятичному номеру сопоставим двоичный эквивалент размером l . Получим таблицу соответствия (табл.9),

Таблица 9

2) для кодирования выполняем шаги:

- выписываем исходный текст (строка 1 табл. 10),

- формируем номера символов исходного текста из табл. 9 (строка 2 табл. 10),

- многократно записываем ключ под исходным текстом (строка 3 табл. 10),

- заполняем номера символов ключа из табл. 9 (строка 4 табл. 10),

- складываем по модулю 13 (это мощность множества А) номера символов (строка 5 табл. 10),

- заменяем полученные числа символами исходного алфавита из табл. 9 (строка 6 табл. 10). Таким образом, получаем строку, соответствующую исходному тексту:

тиоасеиоиовньлллнеии , (12)

Таблица 10

- заменяем символы строки (12) двоичными номерами из табл. 9. Получаем результат (отдельно закодирована фамилия, имя и отчество):

петров 1010 0011 0110 0000 1001 0010

иван 0011 0110 0011 0110 (13)

васильевич 0001 0101 1100 0100 0100 0100 0101 0010 0011 0011

1.3. Эффективное кодирование дискретного сигнала

Задание 6. Метод Шеннона - Фано

Выполнить кодирование исходного текста методом Шеннона-Фано. Частоты символов алфавита А, из которых состоит исходный текст , рассчитать по исходному тексту.

Указания по выполнению задания 6

1) для построения эффективного кода выполним следующие шаги:

- определим размер (в символах) исходного текста (переменная L ) – он равен 20,

- определим частоты f_i появления каждого символа в исходном тексте по формуле:

f_i = m_i /L , (14)

где m_i – число появлений i-го символа в исходном тексте из табл. 2. Имеем графу 3 табл.11,

Таблица 11

- упорядочим список символов алфавита А по не возрастанию частот. Получим графы 1 и 2 табл. 12,

- выполним последовательное деление списка символов в соответствии с алгоритмом Шеннона-Фано (графа 3 табл.12) и назначим символы 0 или 1 элементам списка символов – кодируем элементы. Процесс деления списка символов представлен также в виде двоичного дерева рис. 1, вершины которого равны суммарным частотам отрезков списка,

- «соберем» символы 0 и 1 слева направо в графе 3 для каждого символа алфавита А. Получим графу 4 табл.12.

Таблица 12

1

0,55 0,45

I

0,3 0,25 0,25 0,2 (в)

II

0,15 0,15 0,15 0,1(е) 0,1 (а) 0,15 (и)

Ш

0,1 0,05(т) 0,1 0,05(п) 0,1 0,05(л)

IV

0,05(ь) 0,05(ч) 0,05(с) 0,05(р) 0,05(о) 0,05(н) V

Этапы деления списка

символов из табл. 12

Рис. 1. Двоичное дерево, изображающее деление списка частот символов

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

петров 1100 100 1110 11010 10111 00

иван 010 00 011 10110 (15)

васильевич 00 011 11011 010 1010 11111 100 00 010 11110

Задание 7. Метод Хаффмена

Выполнить кодирование исходного текста методом Хаффмена. Частоты символов алфавита А заимствовать из задания 6.

Указания по выполнению задания 7

1) для построения кода выполним следующие шаги:

- используем в качестве исходных данных графы 1 и 2 табл. 12, расположив их в графах 1 и 2 табл. 13,

- выполним последовательное объединение частот в соответствии с методом Хаффмена (графа 3 табл.13),

Таблица 13

- построим бинарное дерево и закодируем его ребра (рис. 2, коды ребер заключены в окружности),

- начиная с корня дерева, «соберем» коды ребер и сформируем коды символов исходного алфавита (табл. 14),

Таблица 14

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

петров 0001 1101 0010 0000 10110 01

иван 111 01 100 10111 (16)

васильевич 01 100 0011 111 1010 11000 1101 01 111 11001

1

0,6 XI

0,4 X

0,2(в )

0,35 IX

0,15(и )

0,25 VIII

0,1(а )

0,2 VII

0,1(е )

0,2 VI

0,15 V

0,05(л )

0,1 IV

0,05(н ) 0,05(о )

0,1 III

0,05(п ) 0,05(р )

0,1 II

0,05(с ) 0,05(т )

0,1 I

0,05(ч ) 0,05(ь )

этапы объединения частот

из табл.13

Рис. 2. Кодовое бинарное дерево для задания 7

1.4. Помехозащитное кодирование дискретного сигнала

Задание 8. Построение кода для обнаружения ошибок

Построить помехозащитный код для обнаружения ошибок кратности 1 для символов алфавита А (из задания 1). Выполнить кодирование исходного текста и продемонстрировать помехозащитные свойства построенного кода.

Указания по выполнению задания 8

1) для кода с указанной корректирующей способностью кодовое расстояние d должно удовлетворять соотношению: d ³ 2. Для построения кода используем схему построения кода Грея и коды символов исходного алфавита из табл. 7. Используем указанные коды для нумерации строк таблицы для кода Грея (табл. 15), а столбцы пронумеруем как 0 и 1. Размещение символов алфавита А по строкам обеспечивает минимальное расстояние между кодовыми комбинациями в 1, а принятая нумерация столбцов позволит увеличить это расстояние еще на 1: для этого размещенные в смежных строках символы надо помещать в разные столбцы. Тогда требуемые коды формируются как последовательная запись номера строки и номера столбца (графа «Полученные коды» табл.15).

Таблица 15

Для проверки требуемой корректирующей способности рассчитаем кодовое расстояние полученного кода. Для этого определим расстояния d_ij между всеми парами кодовых комбинаций i, j (табл. 16):

Таблица 16

Тогда d = min {d_ij } = 2, а, значит, корректирующая способность кода отвечает требуемой,

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

петров 01001 00110 11110 11000 01010 00011

иван 00101 00011 00000 01111 (17)

васильевич 00011 00000 11011 00101 01100 10100 00110 00011 00101 11101

3) для проверки корректирующей способности кода предположим, что на передаваемую кодовую комбинацию 00011 (символ в ) накладывается ошибка кратности 1, искажающая младший разряд:

00011 Å 00001 = 00010. (18)

Полученный код не принадлежит кодовым комбинациям из табл.15, поэтому определяется как искаженный.

Задание 9. Построение кода для исправления ошибок

Построить помехозащитный код для исправления ошибок кратности 1 для символов алфавита А (из задания 1). Продемонстрировать помехозащитные свойства построенного кода.

Указания по выполнению задания 9

1) для кода с указанной корректирующей способностью кодовое расстояние d должно удовлетворять соотношению: d ³ 3. Для построения кода используем схему построения кода Грея, коды символов исходного алфавита из табл. 15 и саму схему решения задачи из задания 8.

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

Таблица 17

Для проверки требуемой корректирующей способности рассчитаем кодовое расстояние полученного кода. Для этого определим расстояния d_ij между всеми парами кодовых комбинаций i, j (табл. 18):

Таблица 18