Автор – Топоркова О.М., к.т.н., доцент кафедры систем управления и вычислительной техники Калининградского государственного технического университета
Методические указания рассмотрены и одобрены кафедрой систем управления и вычислительной техники 24 декабря 2003 г, протокол № 4
Рецензент – кафедра систем управления и вычислительной техники Калининградского государственного технического университета
©Калининградский государственный технический университет, 2003 г.
ВведениеКурсовая работа по информатике выполняется во втором семестре обучения, когда студенты изучили методы кодирования и измерения информации в дискретном сигнале.
В настоящих методических указаниях приведены задания по различным способам кодирования дискретного сигнала – по образцу, криптографическому, эффективному, помехозащитному. Решение этих задач связано с измерением информации, так что обе проблематики – кодирование и измерение – тесно переплетаются при решении практических задач и им посвящены первые две части заданий.
В третьей части приведено задание по моделированию действия арифметико-логического устройства, выполняющего сложение двух операндов в обратных кодах.
В четвертой части сформулированы задания по кодированию алгоритмов. Тематика задач связана с теми проблемами, которые решались в предыдущих частях настоящих методических указаний. Строго говоря, кодирование алгоритмов также относится к задаче кодирования дискретного сигнала, но тематика заданий, о которой упоминалось выше, регламентировала именно такое местоположение этих заданий.
По всем задачам даны подробные указания к их выполнению, оформленные в виде решений конкретных аналогичных задач. Приведены также правила оформления пояснительной записки.
Часть 1. Кодирование дискретного сигнала 1.1 Кодирование кодами по образцу Задание 1. Прямые кодыДля алфавита А, используемого при формировании Вашей фамилии, имени, отчества (далее - исходного текста), построить прямые двоичные коды постоянной длины и закодировать ими исходный текст (т.е. фамилию, имя и отчество). Для простоты игнорировать регистр и пробелы между словами.
Указания по выполнению задания 1Пусть фамилия, имя и отчество студента Петров Иван Васильевич. Тогда исходным текстом является текст
петровиванвасильевич, (1)
а алфавит А - это множество символов, {п, е, т, р, о, в, и, а, н, с, л, ь, ч}, т.е.
А = {п, е, т, р, о, в, и, а, н, с, л, ь, ч}. (2)
Для построения прямыхкодов выполним следующую последовательность действий:
множество А упорядочим по алфавиту (графа 1 табл.1),
пронумеруем символы алфавита А, начиная с нуля (графа 2 табл.1),
определим мощность N алфавита А (т.е. число символов алфавита):
N = 13 (3)
используя комбинаторный подход к измерению информации, рассчитаем требуемый размер кода, достаточный для кодирования всех символов исходного алфавита А, по формуле:
l = [logh N] , (4)
где h – число символов, используемых для кодирования,
скобки [ ] означают округление результата до ближайшего большего целого числа.
Для нашего примера h = 2 (поскольку строится двоичный код), поэтому
l = [log2 13] = [3,7] = 4, (5)
каждый номер символа представим четырехразрядным (как следует из шага 4) двоичным числом - получим код постоянной длины (графа 3 табл.1).
Таблица 1
| Символ алфавита А | Номер по порядку | Код постоянной длины |
| 1 | 2 | 3 |
| а | 0 | 0000 |
| в | 1 | 0001 |
| е | 2 | 0010 |
| и | 3 | 0011 |
| л | 4 | 0100 |
| н | 5 | 0101 |
| о | 6 | 0110 |
| п | 7 | 0111 |
| р | 8 | 1000 |
| с | 9 | 1001 |
| т | 10 | 1010 |
| ч | 11 | 1011 |
| ь | 12 | 1100 |
Кодирование исходного текста дает (для простоты закодируем отдельно фамилию, имя, отчество)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 табл. 2) определим число появлений mi каждого i-го символа алфавита А в исходном тексте (графа 2 табл. 2),
Таблица 2
| Символ алфавита А | Число появлений mi |
| 1 | 2 |
| а | 2 |
| в | 4 |
| е | 2 |
| и | 3 |
| л | 1 |
| н | 1 |
| о | 1 |
| п | 1 |
| р | 1 |
| с | 1 |
| т | 1 |
| ч | 1 |
| ь | 1 |
для определения размера кода вновь используем формулу l = [logh N] при N = 13, h = 2. Получаем:
l = [logh 13] = [3,7] = 4, (7)
используя комбинаторный подход к измерению информации, определим, сколько кодовых комбинаций можно получить из 4 двоичных разрядов, заполняя их нулями и единицами теми способами, которые показаны в графе 2 табл. 3. Чтобы решить эту задачу, установим, прежде всего, способ комбинирования символов двоичного алфавита (h = 2). Анализ кодов из табл. 1 показывает, что это перестановки с повторениями, для которых верно соотношение:
(ri)!
П(ri!)
Пп(h) = , (8)где Пп(h) – число перестановок из h элементов с повторениями ri,
i – символ из множества символов, используемых для кодирования (у нас это множество {0,1}).
Теперь рассчитаем число кодовых комбинаций для каждого способа заполнения кодовых разрядов (графа 4 табл. 3).
Таблица 3
| № п/п | Способы заполнения кодовых разрядов | Обозначение в формуле (8) | Число кодовых комбинаций |
| 1 | 2 | 3 | 4 |
| 1 |
1 все нули | r0 = 4, r1 = 0 | (4+0)! 4! 4!*0! 4! |
| 2 |
4 1 единица, 3 нуля | r0 = 3, r1 = 1 | (1+3)! 4! 2*3*4 1!*3! 2*3 6 |
| 3 |
6 2 единицы, 2 нуля | r0 = 2, r1 = 2 | (2+2)! 4! 2*3*4 2!*2! 2*2 4 |
| 4 | 3 единицы, 1 ноль | r0 = 1, r1 = 3 | аналогично второму способу, т.е. 4 |
| 5 | все единицы | r0 = 0, r1 = 4 | аналогично первому способу, т.е. 1 |
Суммирование полученного числа кодовых комбинаций (1+4+6+4+1=16) показывает, что для кодирования символов исходного алфавита А с заданной мощностью N достаточно принятых способов заполнения разрядов кода, поскольку 16>(N=13),
упорядочим список символов алфавита А по убыванию частоты. Получим табл. 4 (графы 1,2),
назначим символам коды постоянной длины, число единиц в которых тем больше, чем меньше частота символа (графа 4 табл. 4).
Таблица 4
| Символ алфавита А | Число появлений mi | Способы заполнения кодовых разрядов | Код | Число кодовых комбинаций2 |
| 1 | 2 | 3 | 4 | 5 |
| в | 4 | все нули | 0000 | 1 |
| и | 3 | 1 единица, 3 нуля | 0001 | 4 |
| а | 2 | 1 единица, 3 нуля | 0010 | |
| е | 2 | 1 единица, 3 нуля | 0100 | |
| л | 1 | 1 единица, 3 нуля | 1000 | |
| н | 1 | 2 единицы, 2 нуля | 1010 | 6 |
| о | 1 | 2 единицы, 2 нуля | 1001 | |
| п | 1 | 2 единицы, 2 нуля | 0110 | |
| р | 1 | 2 единицы, 2 нуля | 0101 | |
| с | 1 | 2 единицы, 2 нуля | 0011 | |
| т | 1 | 2 единицы, 2 нуля | 1100 | |
| ч | 1 | 3 единицы, 1 ноль | 1011 | 2 |
| ь | 1 | 3 единицы, 1 ноль | 1101 |
Кодирование исходного текстаполученным кодом дает результат (отдельно закодированы фамилия, имя и отчество):
петров 0110 0100 1100 0101 1001 0000
иван 0001 0000 0010 1010 (9)
васильевич 0000 0010 0011 0001 1000 1101 0100 0000 0001 1011
Задание 3. Коды ГреяДля символов алфавита А (из задания 1) построить код Грея. Закодировать полученным кодом исходный текст.
Указания к выполнению задания 3Для построения кода Грея выполним следующие шаги:
исходя из мощности множества А, определим размер nxm таблицы для построения кода Грея, где n – число строк, m – число столбцов таблицы. Для этого будем последовательно наращивать число столбцов и число строк, начиная с одной строки и одного столбца, каждый раз проверяя, не достигнут ли требуемый размер таблицы. При этом схема наращивания числа строк и столбцов будет определяться следующим образом: число столбцов на каждом шаге итерации равно или на 1 превышает число строк (табл. 5).
Таблица 5
| Номер шага | Число столбцов m | Число строк n | Размер таблицы nxm |
| 1 | 2 | 3 | 4 |
| 1 | 1 | 1 | 1 |
| 2 | 2 | 1 | 2 |
| 3 | 2 | 2 | 4 |
| 4 | 3 | 2 | 6 |
| 5 | 3 | 3 | 9 |
| 6 | 4 | 3 | 12 |
| 7 | 4 | 4 | 16 > 13 |
Поскольку на седьмом шаге итерации удалось достичь требуемого размера таблицы, определение ее размеров закончено. Таким образом, получена таблица размером 4х4,
строки и столбцы таблицы пронумеруем двоичными числами из множества {00, 01, 10, 11}, элементы которого сами являются кодами Грея (затушеванные ячейки табл. 6),
Таблица 6
| 00 | 01 | 11 | 10 | |
| 00 | а | в | е | и |
| 01 | п | о | н | л |
| 11 | р | с | т | ч |
| 10 | ь |
разместим в ячейках таблицы упорядоченные по алфавиту символы исходного множества (см. графу 1 табл.1) в направлении, указанном стрелками в табл.6,
для формирования кода Грея по каждому символу объединим номера строки и столбца ячейки, в которой находится символ. Получим графу 2 табл. 7.
Таблица 7
| Символ алфавита А | Код Грея |
| 1 | 2 |
| а | 0000 |
| в | 0001 |
| е | 0011 |
| и | 0010 |
| л | 0110 |
| н | 0111 |
| о | 0101 |
| п | 0100 |
| р | 1100 |
| с | 1101 |
| т | 1111 |
| ч | 1110 |
| ь | 1010 |
Кодирование исходного текстаполученным кодом дает результат:
петров 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 табл. 8) и произвольными 4-разрядными кодами (графа 3 табл.8). Для упрощения процедуры используем произвольный номер символа алфавита А в пределах от 0 до 12 (графа 2 табл. 8) (назначение номера выполнено бессистемно):
Таблица 8
| Символы исходного алфавита | Произвольный номер символа | Коды |
| 1 | 2 | 3 |
| а | 9 | 1001 |
| в | 11 | 1011 |
| е | 12 | 1100 |
| и | 1 | 0001 |
| л | 10 | 1010 |
| н | 6 | 0110 |
| о | 7 | 0111 |
| п | 0 | 0000 |
| р | 2 | 0010 |
| с | 3 | 0011 |
| т | 4 | 0100 |
| ч | 5 | 0101 |
| ь | 8 | 1000 |
для кодирования исходного текста используем табл.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для построения кода пронумеруем символы исходного алфавита, начиная с 0, и каждому десятичному номеру сопоставим двоичный эквивалент размером l. Получим таблицу соответствия (табл.9),
Таблица 9
| символы исходного алфавита | а | в | е | и | л | н | о | п | р | с | т | ч | ь |
| десятичные номера символов | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| двоичные номера символов | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 |
для кодирования выполняем шаги:
выписываем исходный текст (строка 1 табл. 10),
формируем номера символов исходного текста из табл. 9 (строка 2 табл. 10),
многократно записываем ключ под исходным текстом (строка 3 табл. 10),
заполняем номера символов ключа из табл. 9 (строка 4 табл. 10),
складываем по модулю 13 (это мощность множества А) номера символов (строка 5 табл. 10),
заменяем полученные числа символами исходного алфавита из табл. 9 (строка 6 табл. 10). Таким образом, получаем строку, соответствующую исходному тексту:
тиоасеиоиовньлллнеии , (12)
Таблица 10
| Номер строки | Результаты выполнения кодирования | |||||||||||||||||||
| 1 | п | е | т | р | о | в | и | в | а | н | в | а | с | и | л | ь | е | в | и | ч |
| 2 | 7 | 2 | 10 | 8 | 6 | 1 | 3 | 1 | 0 | 5 | 1 | 0 | 9 | 3 | 4 | 12 | 2 | 1 | 3 | 11 |
| 3 | и | в | а | н | и | в | а | н | и | в | а | н | и | в | а | н | и | в | а | н |
| 4 | 3 | 1 | 0 | 5 | 3 | 1 | 0 | 5 | 3 | 1 | 0 | 5 | 3 | 1 | 0 | 5 | 3 | 1 | 0 | 5 |
| 5 | 10 | 3 | 10 | 0 | 9 | 2 | 3 | 6 | 3 | 6 | 1 | 5 | 12 | 4 | 4 | 4 | 5 | 2 | 3 | 3 |
| 6 | т | и | о | а | с | е | и | о | и | о | в | н | ь | л | л | л | н | е | и | и |
заменяем символы строки (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для построения эффективного кода выполним следующие шаги:
определим размер (в символах) исходного текста (переменная L) – он равен 20,
определим частоты fi появления каждого символа в исходном тексте по формуле:
fi = mi/L, (14)
где mi – число появлений i-го символа в исходном тексте из табл. 2. Имеем графу 3 табл.11,
Таблица 11
| Символ алфавита А | Число появлений mi | Частота символа fi |
| 1 | 2 | 3 |
| а | 2 | 0,1 |
| в | 4 | 0,2 |
| е | 2 | 0,1 |
| и | 3 | 0,15 |
| л | 1 | 0,05 |
| н | 1 | 0,05 |
| о | 1 | 0,05 |
| п | 1 | 0,05 |
| р | 1 | 0,05 |
| с | 1 | 0,05 |
| т | 1 | 0,05 |
| ч | 1 | 0,05 |
| ь | 1 | 0,05 |
упорядочим список символов алфавита А по не возрастанию частот. Получим графы 1 и 2 табл. 12,
выполним последовательное деление списка символов в соответствии с алгоритмом Шеннона-Фано (графа 3 табл.12) и назначим символы 0 или 1 элементам списка символов – кодируем элементы. Процесс деления списка символов представлен также в виде двоичного дерева рис. 1, вершины которого равны суммарным частотам отрезков списка,
«соберем» символы 0 и 1 слева направо в графе 3 для каждого символа алфавита А. Получим графу 4 табл.12.
Таблица 12
| Символ алфавита А | Частота символа fi | Этапы деления списка символов | Результирующие коды | ||||
| 1 | 2 | 3 | 4 | ||||
| I | II | III | IV | V | |||
| в | 0,2 | 0 | 0 | - | 00 | ||
| и | 0,15 | 1 | 0 | - | 010 | ||
| а | 0,1 | 1 | - | 011 | |||
| е | 0,1 | 1 | 0 | 0 | - | 100 | |
| л | 0,05 | 1 | 0 | - | 1010 | ||
| н | 0,05 | 1 | 0 | 10110 | |||
| о | 0,05 | 1 | 10111 | ||||
| п | 0,05 | 1 | 0 | 0 | - | 1100 | |
| р | 0,05 | 1 | 0 | 11010 | |||
| с | 0,05 | 1 | 11011 | ||||
| т | 0,05 | 1 | 0 | - | 1110 | ||
| ч | 0,05 | 1 | 0 | 11110 | |||
| ь | 0,05 | 1 | 11111 | ||||
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. Двоичное дерево, изображающее деление списка частот символов
для кодирования исходного текста используем табл. 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 и 2 табл. 12, расположив их в графах 1 и 2 табл. 13,
выполним последовательное объединение частот в соответствии с методом Хаффмена (графа 3 табл.13),
Таблица 13
| Символ алфавита А | Частота символа fi | Этапы объединения частот | |||||||||||
| 1 | 2 | 3 | |||||||||||
| I | II | III | IV | V | VI | VII | VIII | IX | X | XI | XII | ||
| в | 0,2 | 0,2 | 0,2 | 0,2 | 0,2 | 0,2 | 0,2 | 0,2 | 0,25 | 0,35 | 0,4 | 0,6 | 1 |
| и | 0,15 | 0,15 | 0,15 | 0,15 | 0,15 | 0,15 | 0,2 | 0,2 | 0,2 | 0,25 | 0,35 | 0,4 | - |
| а | 0,1 | 0,1 | 0,1 | 0,1 | 0,1 | 0,15 | 0,15 | 0,2 | 0,2 | 0,2 | 0,25 | - | - |
| е | 0,1 | 0,1 | 0,1 | 0,1 | 0,1 | 0,1 | 0,15 | 0,15 | 0,2 | 0,2 | - | - | - |
| л | 0,05 | 0,1 | 0,1 | 0,1 | 0,1 | 0,1 | 0,1 | 0,15 | 0,15 | - | - | - | - |
| н | 0,05 | 0,05 | 0,1 | 0,1 | 0,1 | 0,1 | 0,1 | 0,1 | - | - | - | - | - |
| о | 0,05 | 0,05 | 0,05 | 0,1 | 0,1 | 0,1 | 0,1 | - | - | - | - | - | - |
| п | 0,05 | 0,05 | 0,05 | 0,05 | 0,1 | 0,1 | - | - | - | - | - | - | - |
| р | 0,05 | 0,05 | 0,05 | 0,05 | 0,05 | - | - | - | - | - | - | - | - |
| с | 0,05 | 0,05 | 0,05 | 0,05 | - | - | - | - | - | - | - | - | - |
| т | 0,05 | 0,05 | 0,05 | - | - | - | - | - | - | - | - | - | - |
| ч | 0,05 | 0,05 | - | - | - | - | - | - | - | - | - | - | - |
| ь | 0,05 | - | - | - | - | - | - | - | - | - | - | - | - |
построим бинарное дерево и закодируем его ребра (рис. 2, коды ребер заключены в окружности),
начиная с корня дерева, «соберем» коды ребер и сформируем коды символов исходного алфавита (табл. 14),
Таблица 14
| Символ алфавита А | в | и | а | е | л | н | о | п | р | с | т | ч | ь |
| Код | 01 | 111 | 100 | 1101 | 1010 | 10111 | 10110 | 0001 | 0000 | 0011 | 0010 | 11001 | 11000 |
для кодирования исходного текста используем табл.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для кода с указанной корректирующей способностью кодовое расстояние d должно удовлетворять соотношению: d 2. Для построения кода используем схему построения кода Грея и коды символов исходного алфавита из табл. 7. Используем указанные коды для нумерации строк таблицы для кода Грея (табл. 15), а столбцы пронумеруем как 0 и 1. Размещение символов алфавита А по строкам обеспечивает минимальное расстояние между кодовыми комбинациями в 1, а принятая нумерация столбцов позволит увеличить это расстояние еще на 1: для этого размещенные в смежных строках символы надо помещать в разные столбцы. Тогда требуемые коды формируются как последовательная запись номера строки и номера столбца (графа «Полученные коды» табл.15).
Таблица 15
| Номера столбцов | Полученные коды | ||
| Номера строк | 0 | 1 | |
| 0000 | а | 00000 | |
| 0001 | в | 00011 | |
| 0011 | е | 00110 | |
| 0010 | и | 00101 | |
| 0110 | л | 01100 | |
| 0111 | н | 01111 | |
| 0101 | о | 01010 | |
| 0100 | п | 01001 | |
| 1100 | р | 11000 | |
| 1101 | с | 11011 | |
| 1111 | т | 11110 | |
| 1110 | ч | 11101 | |
| 1010 | ь | 10100 | |
Для проверки требуемой корректирующей способности рассчитаем кодовое расстояние полученного кода. Для этого определим расстояния dij между всеми парами кодовых комбинаций i, j (табл. 16):
Таблица 16
| в | и | а | е | л | н | о | п | р | с | т | ч | ь | |
| в | 2 | 2 | 2 | 4 | 2 | 2 | 2 | 4 | 2 | 4 | 4 | 4 | |
| и | 2 | 2 | 2 | 2 | 4 | 2 | 4 | 4 | 4 | 2 | 2 | ||
| а | 2 | 2 | 4 | 2 | 2 | 2 | 4 | 4 | 4 | 2 | |||
| е | 2 | 2 | 2 | 4 | 4 | 4 | 2 | 4 | 2 | ||||
| л | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | |||||
| н | 2 | 2 | 4 | 2 | 2 | 2 | 4 | ||||||
| о | 2 | 2 | 2 | 2 | 4 | 4 | |||||||
| п | 2 | 2 | 4 | 2 | 4 | ||||||||
| р | 2 | 2 | 2 | 2 | |||||||||
| с | 2 | 2 | 4 | ||||||||||
| т | ght: none; padding-top: 0in; padding-bottom: 0in; padding-left: 0.08in; padding-right: 0in;"> | 2 | 2 | ||||||||||
| ч | 2 | ||||||||||||
| ь |
Тогда d = min {dij} = 2, а, значит, корректирующая способность кода отвечает требуемой,
для кодирования исходного текста используем табл.15. Имеем (для простоты закодируем отдельно фамилию, имя и отчество):
петров 01001 00110 11110 11000 01010 00011
иван 00101 00011 00000 01111 (17)
васильевич 00011 00000 11011 00101 01100 10100 00110 00011 00101 11101
для проверки корректирующей способности кода предположим, что на передаваемую кодовую комбинацию 00011 (символ в) накладывается ошибка кратности 1, искажающая младший разряд:
00011 00001 = 00010. (18)
Полученный код не принадлежит кодовым комбинациям из табл.15, поэтому определяется как искаженный.
Задание 9. Построение кода для исправления ошибокПостроить помехозащитный код для исправления ошибок кратности 1 для символов алфавита А (из задания 1). Продемонстрировать помехозащитные свойства построенного кода.
Указания по выполнению задания 9для кода с указанной корректирующей способностью кодовое расстояние d должно удовлетворять соотношению: d 3. Для построения кода используем схему построения кода Грея, коды символов исходного алфавита из табл. 15 и саму схему решения задачи из задания 8.
Поскольку кодовое расстояние, равное 2, получено ранее, номера строк табл. 17 – это коды, обеспечивающие данное кодовое расстояние. Для достижения дополнительного кодового расстояния, равного единице, обозначим столбцы табл. 17 кодами Грея для символов алфавита А, полученными в задании 3. Получаем табл. 17.
Таблица 17
| Номера столбцов | Полученные коды | |||||||||||||
| Номера строк | 0000 | 0001 | 0011 | 0010 | 0110 | 0111 | 0101 | 0100 | 1100 | 1101 | 1111 | 1110 | 1010 | |
| 00000 | а | 000000000 | ||||||||||||
| 00011 | в | 000110001 | ||||||||||||
| 00110 | е | 001100011 | ||||||||||||
| 00101 | и | 001010010 | ||||||||||||
| 01100 | л | 011000110 | ||||||||||||
| 01111 | н | 011110111 | ||||||||||||
| 01010 | о | 010100101 | ||||||||||||
| 01001 | п | 010010100 | ||||||||||||
| 11000 | р | 110001100 | ||||||||||||
| 11011 | с | 110111101 | ||||||||||||
| 11110 | т | 111101111 | ||||||||||||
| 11101 | ч | 111011110 | ||||||||||||
| 10100 | ь | 101001010 | ||||||||||||
Для проверки требуемой корректирующей способности рассчитаем кодовое расстояние полученного кода. Для этого определим расстояния dij между всеми парами кодовых комбинаций i, j (табл. 18):
Таблица 18
| в | и | а | е | л | н | о | п | р | с | т | ч | ь | |
| в | 4 | 3 | 3 | 7 | 4 | 3 | 4 | 7 | 4 | 7 | 7 | 7 | |
| и | 3 | 3 | 3 | 4 | 7 | 4 | 7 | 8 | 7 | 4 | 3 | ||
| а | 4 | 4 | 7 | 4 | 3 | 4 | 7 | 8 | 7 | 4 | |||
| е | 4 | 3 | 4 | 7 | 8 | 7 | 4 | 7 | 4 | ||||
| л | 3 | 4 | 3 | 4 | 7 | 4 | 3 | 4 | |||||
| н | 3 | 4 | 7 | 4 | 3 | 4 | 7 | ||||||
| о | 3 | 4 | 3 | 4 | 7 | 8 | |||||||
| п | 3 | 4 | 7 | 4 | 7 | ||||||||
| р | 3 | 4 | 3 | 4 | |||||||||
| с | 3 | 4 | 7 | ||||||||||
| т | 3 | 4 | |||||||||||
| ч | 3 | ||||||||||||
| ь |
Тогда d = min {dij} = 3, а, значит, корректирующая способность кода отвечает требуемой,
для проверки корректирующей способности кода выполним следующие действия:
а) предположим, что на передаваемую кодовую комбинацию 000110001 (символ в) накладывается ошибка кратности 1, искажающая младший разряд:
000110001 000000001 = 000110000 , (19)
выявление ошибки: поскольку полученный код не принадлежит кодовым комбинациям из табл.17, он определяется как искаженный,
исправление ошибки:
рассчитываются расстояния между разрешенными кодовыми комбинациями и искаженным кодом (табл. 19),
Таблица 19
| Искаженный код | в | и | а | е | л | н | о | п | р | с | т | ч | ь |
| 000110000 | 1 | 3 | 2 | 4 | 6 | 5 | 4 | 3 | 6 | 5 | 8 | 7 | 6 |
по табл. 19 определяется тот символ, для которого расстояние между соответствующими кодами равно 1, поскольку именно такова кратность ошибки, которую данный код должен исправлять. Это символ в. Таким образом, принятая кодовая комбинация заменяется на правильную:
000110000 000110001 , (20)
б) предположим, что на передаваемую кодовую комбинацию 000110001 (символ в) накладывается ошибка кратности 2, искажающая два младших разряда:
000110001 000000011 = 000110010 , (21)
выявление ошибки: поскольку полученный код не принадлежит кодовым комбинациям из табл.17, он определяется как искаженный,
исправление ошибки:
определяются расстояния между кодовыми комбинации из числа разрешенных (табл. 17), и искаженным кодом из (21) – табл. 20,
Таблица 20
| Искаженный код | в | и | а | е | л | н | о | п | р | с | т | ч | ь |
| 000110010 | 2 | 2 | 3 | 3 | 5 | 4 | 7 | 4 | 7 | 6 | 6 | 6 | 6 |
делается попытка по табл. 20 определить тот символ, для которого расстояние между соответствующими кодами равно 1. Поскольку такой символ не находится, принятая кодовая комбинация не может быть заменена на правильную, поэтому исправление ошибки не происходит (в таком случае на практике принимающая сторона запрашивает повторную передачу искаженной кодовой комбинации).
Таким образом, построенный код способен исправлять ошибки кратности 1.
Часть 2. Измерение дискретного сигнала Задание 10. Анализ эффективности кодированияОпределить эффективность кодирования символов исходного алфавита А (из задания 1) разными кодами, построенными в предыдущих заданиях.
Указания по выполнению задания 10Для решения задачи измерим количество информации, содержащейся в 1 кодовой комбинации построенных в предыдущих заданиях кодов:
для кодов постоянной длины (задания 1 – 5, 8, 9) используем геометрическую меру. Для этого подсчитаем число двоичных разрядов в построенных кодах. Получим:
l1 = l2 = l3 = l4 = l5 = 4 двоичных символа, (22)
l8 = 5 двоичных символов; (23)
l9 = 9 двоичных символов, (24)
для эффективных кодов (задания 6, 7) используем среднее число двоичных разрядов lср, применяемое для кодирования символов исходного алфавита, которое рассчитывается по формуле:
, (25)
где fi – частота символа,
ni– число двоичных разрядов в коде i– го символа,
N – число символов в исходном алфавите А,
для задания 7 (см. табл. 12):
lср = 0,2*2+0,15*3+0,1*3*2+0,05*4*3+0,05*5*6=3,55 бита , (26)
для задания 8 (см. табл. 13 и 14):
lср = 0,2*2+0,15*3+0,1*3+0,1*4+0,05*4*5+0,05*5*4=3,55 бита, (27)
для определения общей эффективности кодов применим статистическую меру измерения информации, содержащейся в одном символе исходного алфавита А: это значение определит lпр предельное количество двоичных разрядов, достаточное для кодирования символов исходного алфавита. Для расчета используем формулу:
. (28)
Тогда получим (см. частоты в табл. 11):
lпр = -(2*(0,1* log20,1) + 0,2* log20,2 + 0,15*log20,15 + 9*(0,05*log20,05)) = 3,48418 бита.
(29)
Таким образом, все построенные коды являются избыточными. Однако минимальной избыточностью обладают эффективные коды: они минимально отличаются от предельного значения числа двоичных разрядов.
Часть 3. Формы представления чисел Задание 11. Сложение в обратных кодахВыполнить сложение в обратном коде двух отрицательных чисел, сформированных из пятиразрядного номера зачетной книжки по правилу:
целая часть первого числа образуется из первых трех разрядов, дробная часть – из оставшихся разрядов;
целая часть второго числа совпадает с дробной частью первого числа, а его дробная часть совпадает с целой частью первого числа.
Например:
а) номер зачетной книжки равен 01234;
б) первое число равно –12,34; (30)
в) второе число равно –34,12.
Разрядная сетка имеет структуру 6х10, где 6 – число разрядов порядка, 10 – число разрядов мантиссы. При переводе дробной части слагаемых ориентироваться на необходимость заполнения разрядной сетки мантиссы.
Результат сложения перевести в десятичную систему счисления и сравнить с тем, что должно было бы получиться.
Указания по выполнению задания 11перевод слагаемых в двоичную систему счисления:
перевод целой части выполним на примере числа 34 последовательным делением делимого на 2:
Таблица 21
| Номер шага | Делимое | Целая часть частного | Остаток |
| 1 | 34 | 17 | 0 |
| 2 | 17 | 8 | 1 |
| 3 | 8 | 4 | 0 |
| 4 | 4 | 2 | 0 |
| 5 | 2 | 1 | 0 |
Получаем:
34 = 1000102. (31)
перевод дробной части выполним на примере числа 0,12 последовательным умножением множимого на 2. При этом перевод заканчивается, когда сумма двоичных разрядов целой части и дробной будет равна 9 (т.е. количеству разрядов для мантиссы минус 1 разряд на знак), или число разрядов дробной части будет равно 3 (по тем же соображениям):
Таблица 22
| Номер шага | Множимое | Целая часть произведения | Дробная часть произведения |
| 1 | 0,12 | 0 | 24 |
| 2 | 0,24 | 0 | 48 |
| 3 | 0,48 | 0 | 96 |
Поскольку число двоичных разрядов (см. целые части произведения в табл. 22) равно 3, процедура перевода дробной части заканчивается. Таким образом:
0,12 = 0,0002. (32)
Перевод второго слагаемого дает:
12,34 = 1100,010102 (33)
нормализация двоичных чисел и размещение их в разрядных сетках:
нормализация
-100010,000 -0,100010000Е+110 (34)
-1100,01010 -0,110001010Е+100 (35)
размещение в разрядных сетках
порядок мантисса
|
(36) -34,12 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| -12,34 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
знаковые разряды
определение большего порядка путем вычитания из одного порядка другого и анализа разности: 110 – 100. Поскольку в решении задачи участвуют отрицательные числа, выполним перевод вычитаемого в обратный код и произведем сложение порядков по правилам сложения чисел в обратном коде:
| Прямые коды слагаемых | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | |
|
(37) Обратные коды слагаемых | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 | 1 | |
| Сумма | 0 | 0 | 0 | 0 | 1 | 0 |
Поскольку сумма положительна, большим является первый порядок (у слагаемого –34,12), а потому на следующем шаге работа ведется со вторым слагаемым –12,34;
выравнивание порядков и сдвиг мантиссы для слагаемого с меньшим порядком:
выравнивание порядков
|
(38) Прямые коды слагаемых | 0 | 0 | 0 | 1 | 0 | 0 | ||||||
| 0 | 0 | 0 | 0 | 1 | 0 | |||||||
| Сумма (второй порядок) | 0 | 0 | 0 | 1 | 1 | 0 | ||||||
сдвиг мантиссы
|
(39) 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
Т
(40)
(41)
(42)
аким образом, второе слагаемое (с меньшим порядком) приобретает вид:| -12,34 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
сложение мантисс. Поскольку обе мантиссы отрицательны, сложение выполняется в обратных кодах:
| Прямые коды слагаемых | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | |
| Обратные коды слагаемых | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | |
| Сумма | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
Поскольку результат отрицателен, он представлен в обратном коде. Выполняется перевод в прямой код. Получаем:
| 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 |
перевод результата в десятичную систему счисления:
-0,101110010Е+6= -101110,01= -(1*25+1*23+1*22+1*21+1*2-2) =
-(32+8+4+2+0,25) = -46,25. (43)
Часть 4. Кодирование алгоритмов Задание 12Разработать алгоритмы решения задач из приведенных ниже вариантов, а также определить входные, выходные и промежуточные данные. При этом использовать методы: нисходящее проектирование, модульность, структурное программирование. Для представления алгоритмов применить язык графических символов. При представлении блок-схем придерживаться требований ГОСТ. Выбор варианта задания выполнять по своему порядковому номеру в списке учебной группы (уточнить у преподавателя).
Варианты заданий:
задан текст, не имеющий пробелов. Сформировать алфавит А, т.е. множество символов, из которых составлен текст (см. преобразование (1) в (2));
задан текст, не имеющий пробелов. Сформировать алфавит А, т.е. множество символов, из которых составлен текст (см. предыдущее задание), определить его мощность N (см. (3)) и рассчитать требуемый размер l прямого двоичного кода постоянной длины (см. (4) и (5));
задан исходный алфавит А, размер l прямого двоичного кода постоянной длины (см. (4)) для кодирования этого алфавита. Сформировать для символов алфавита А двоичный код постоянной длины размером l с начальным номером по порядку, равным нулю (см. графы 2 и 3 табл. 1);
задан исходный текст, не имеющий пробелов, и известен код постоянной длины для алфавита, в котором составлен текст (графы 1 и 3 табл. 1). Закодировать исходный текст (см. (6));
задан исходный текст, не имеющий пробелов. Сформировать алфавит А, т.е. множество символов, из которых составлен текст (см. задание 00), и рассчитать число появлений каждого символа алфавита А в исходном тексте (см. графу 2 табл. 2);
задан размер кода l. Рассчитать общее число кодовых двоичных комбинаций, получаемых при заполнении l двоичных разрядов методом перестановок с повторениями разными способами (см. табл. 3);
задан алфавит А, его мощность N, частота символов алфавита А, размер кода l. Заданы количества кодовых комбинаций, получаемых при заполнении l двоичных разрядов разными способами (см. табл. 3). Сформировать двоичные коды для символов алфавита А с учетом частоты символов (см. табл. 4);
задана мощность N множества А. Определить размер таблицы для построения кода Грея для элементов множества А (см. шаг 1 выполнения задания 3);
задан размер таблицы для построения кода Грея - nxm. Сформировать нумерацию строк и столбцов этой таблицы (см. шаг 2 выполнения задания 3);
задано упорядоченное по алфавиту множество А. Определен размер таблицы для построения кода Грея nxm и сформирована нумерация строк и столбцов этой таблицы. Получить код Грея для символов алфавита А (графа 2 табл. 7);
задан исходный алфавит А. Задать символам алфавита А произвольные десятичные номера в пределах от 0 до N-1, где N - мощность алфавита А (использовать функцию получения случайного числа) (см. графу 2 табл. 8);
задан исходный текст и ключ кодирования К. «Выписать» ключ под исходным текстом (см. строки 1 и 3 табл. 10);
заданы две числовые десятичные последовательности длиной L (см. строки 2 и 4 табл. 10). Выполнить сложение элементов этих последовательностей по модулю N (см. строку 5 табл. 10);
задан размер исходного текста L, алфавит А, из которого составлен текст, и число появлений каждого символа mi. Рассчитать частоты символов fi по формуле (14) (графа 3 табл. 11). При этом добиваться того, чтобы сумма частот была равна 1 (путем увеличения самой большой частоты или уменьшения самой маленькой частоты);
задан упорядоченный по невозрастанию список частот мощностью N. Выполнить его итерационное деление на N одноэлементных подмножеств, каждый раз в цикле проводя деление очередного подмножества на 2 части, руководствуясь при этом примерным равенством частот обоих подмножеств. Окончание процесса деления подмножества на две части определить по одноэлементности подмножества (см. графы 2 и 3 табл. 12);
модифицировать алгоритм из задания 14, формируя в процессе деления исходного множества частот результирующие коды Шеннона-Фано (см. графу 4 табл. 12);
задан упорядоченный по невозрастанию список частот мощностью N. Выполнить объединение частот в соответствии с алгоритмом Хаффмена (см. табл. 13). Результат представить в виде матрицы размером Nx(N-1);
модифицировать алгоритм задания 16, указывая связи между исходными и объединенными частотами (см. стрелки в табл. 13);
модифицировать алгоритм задания 17, «нагружая» связи между исходными и объединенными частотами символами 1 и 0;
задано кодовое дерево, подобное изображенному на рис. 2. Сформировать по нему коды для каждого символа, расположенного в «листе» дерева (см. табл. 14);
задан эффективный код, содержащий N кодовых комбинаций. Определить, является ли он префиксным;
заданы кодовые таблицы, построенные методами Шеннона-Фано и Хаффмена, для символов алфавита А. Известны частоты символов алфавита А. Дан размер прямого кода постоянной длины l для символов алфавита А. По формуле (17) определить эффективность кодирования каждым методом и установить, какой из методов наиболее эффективен;
задана кодовая таблица эффективного кода (например, подобная табл. 12). Задана кодовая последовательность, представляющая некоторый текст, закодированный в этом коде. Раскодировать заданный текст;
задан исходный алфавит А и коды Грея для него. Построить помехозащитный код для обнаружения ошибки кратности 1 (см. табл. 15);
задан помехозащитный код (см. табл. 15). Определить расстояния между всеми парами кодовых комбинаций (табл. 16);
заданы расстояния между всеми парами кодовых комбинаций некоторого помехозащитного кода. Определить минимальное кодовое расстояние и кратность ошибки, которую этот код может обнаруживать и/или исправлять;
задан l-разрядный помехозащитный код. Построить алгоритм искажения его составляющих ошибкой заданной кратности q (см. (18));
задана искаженная кодовая комбинация и некоторый помехозащитный код. Построить алгоритм обнаружения ошибки;
задана искаженная кодовая комбинация и некоторый помехозащитный код. Построить алгоритм исправления ошибки (или диагностировать невозможность исправления);
задано С двоичных последовательностей, о каждой из которых известно, каким методом из описанных в заданиях 1 – 9 настоящих методических указаний она закодирована. Определить наиболее короткую последовательность и метод, которым она была получена;
задан исходный алфавит А и частоты символов, его составляющих. Рассчитать предельное значение размера кода по формуле (29);
дано 5-значное целое число. Сформировать из него 2 отрицательных вещественных числа по правилу, приведенному в задании 11 (см. (30));
дана десятичная дробь. Перевести ее в двоичную систему счисления с точностью р разрядов;
дано десятичное вещественное число. Представить его в нормализованной экспоненциальной форме;
даны целое двоичное число со знаком и разрядная сетка размером р двоичных разрядов, старший разряд зарезервирован под знак числа. Разместить двоичное число в разрядной сетке;
даны нормализованная мантисса двоичного числа со знаком и разрядная сетка для ее размещения размером р двоичных разрядов, старший разряд зарезервирован под знак мантиссы. Разместить мантиссу в разрядной сетке;
дано двоичное число, помещенное в разрядную сетку размером р двоичных разрядов в виде прямого кода. Старший разряд зарезервирован под знак числа. Построить обратный код числа;
дано двоичное число, помещенное в разрядную сетку размером р двоичных разрядов в виде обратного кода. Старший разряд зарезервирован под знак числа. Построить дополнительный код числа;
даны два отрицательных двоичных числа, помещенных в разрядные сетки размером р двоичных разрядов в виде обратных кодов. Старший разряд зарезервирован под знак числа. Выполнить сложение слагаемых. Результат представить в виде обратного кода;
даны два отрицательных двоичных числа, помещенных в разрядные сетки размером р двоичных разрядов в виде дополнительных кодов. Старший разряд зарезервирован под знак числа. Выполнить сложение слагаемых. Результат представить в виде дополнительного кода;
дано двоичное число, помещенное в разрядную сетку размером р двоичных разрядов в виде обратного кода. Старший разряд зарезервирован под знак числа. Построить прямой код числа;
дано двоичное число, помещенное в разрядную сетку размером р двоичных разрядов в виде дополнительного кода. Старший разряд зарезервирован под знак числа. Построить обратный код числа;
дано двоичное число, помещенное в разрядную сетку размером р двоичных разрядов. Старший разряд зарезервирован под знак числа. Выполнить сдвиг числовых разрядов на к разрядов вправо.
Указания по выполнению задания 12В качестве примера рассмотрим решение следующей задачи: разработать алгоритм для перевода заданного положительного целого десятичного числа в двоичную систему счисления. Представить алгоритм в виде блок-схемы и использовать при его составлении методы нисходящего проектирования, модульности, структурного программирования.
Решение:
определим входные, выходные и промежуточные данные, их типы и обозначения в блок-схеме. Очевидно, исходное и результирующее число можно определить как простые переменные. Сложнее дело обстоит с другими данными. Как показывает анализ известной схемы перевода (см., например, табл. 21), для решения задачи требуется «знать» все остатки от деления на 2. Для их хранения введем промежуточную переменную, которую опишем как одномерный массив. Кроме того, в каждом шаге перевода (суть деления очередного частного на 2) делимое меняет значение. Для его хранения можно использовать простую переменную. Важно также отметить, что в силу циклического характера схемы перевода в каждом шаге частное от деления становится делимым. Таким образом, введенные переменные сведены в табл. 23:
Таблица 23
| Вид данных | Характеристика данных | Обозначение |
| входные | целое десятичное число, простое данное | А |
| выходные | целое двоичное число, простое данное | Z |
| промежуточные | частное от деления на 2 или делимое, простое данное остаток при делении на 2, массив | B C |
в соответствии с принципом нисходящего проектирования представим вначале в виде блок-схемы обобщенный алгоритм перевода (рис. 3).
1
Нет
Да
2
3
4
5
Рис. 3. Укрупненная блок-схема перевода
В задачу включена проверка необходимости перевода (блок 2): очевидно, перевод десятичного целого числа в двоичную систему счисления необходим, если переводимое число не меньше 2. Так, например, если исходное десятичное число (переменная А) равно 5, управление переходит на блок 4, в котором начинается сам перевод. Если же исходное число равно, например, 1, управление передается блоку 3, в котором результирующая переменная Z приравнивается исходному числу: т.е. результат совпадает с входными данными. В этом случае алгоритм перевода заканчивает свою работу. В соответствии с принципом модульного проектирования блок Перевод в силу сложности задачи перевода показан как предопределенный процесс и требует отдельной разработки. Оставшиеся шаги (анализ, ввод и вывод) могут быть реализованы как отдельные операторы произвольного языка программирования, потому дальнейшей конкретизации не подлежат;
в соответствии с принципом нисходящего проектирования представим в виде блок-схемы блок, реализующий задачу перевода (рис. 4).
1
2
3
4
5
6
НетДа
Рис. 4 . Блок-схема задачи перевода
В блоке 1 определяется частное от деления исходного числа на 2. Его значение присваивается переменной В.
В блоке 2 рассчитывается первый остаток. Его значение присваивается первому элементу одномерного массива С.
В блоке 3 задается условие выполнения цикла: перевод числа продолжается, пока частное остается не меньше 2 (эта проверка аналогична той, что проводилась в блоке 2 блок-схемы рис. 3). Если условие нарушается, управление передается на блок 6, в котором из полученных ранее остатков и последнего частного «собирается» результат. Очевидно, это сложная задача, поэтому блок 6 в соответствии с принципом модульного проектирования представлен как предопределенный процесс.
Если же в результате анализа в блоке 3 определена необходимость продолжения перевода, управление передается на блок 4. В этом блоке последовательно формируется одномерный массив, в котором в результате сохраняются все остатки от делений. Очевидно, этот блок в силу сложности задачи первоначально следует представить как предопределенный процесс.
В блоке 5 «подготавливается» новое выполнения цикла: как отмечалось ранее, на очередном шаге цикла бывшее частное становится делимым. Эта замена формально представляется той подменой, которая и выполняется в этом блоке. Управление передается блоку 3, в котором уже в роли делимого выступает бывшее на предыдущем шаге частное.
в соответствии с принципом нисходящего проектирования представим в виде блок-схемы задачу формирования С (рис. 5).
1
2
первоначально I = 1
Рис. 5. Блок-схема формирования массива остатков С
В блоке 1 выполняется переход к очередному элементу массива с остатками от деления. В блоке 2 рассчитывается остаток от деления. Его значение присваивается очередному элементу массива С;
представим в виде блок-схемы задачу формирования Z (рис. 6);
1
2
3
Рис. 6. Блок-схема задачи формирования Z
В блоке 1 переменной Z присваивается последнее частное.
В блоке 2 организуется цикл для обращения ко всем элементам массива С, начиная с последнего, имеющего номер I, и кончая первым. Каждый элемент массива С приписывается к цепочке Z (операция означает приписывание).
Взаимосвязь модулей показана на рис. 7.
Рис. 7. Взаимосвязь модулей задачи перевода
Рассмотрим теперь на примере, как работает полученный алгоритм. Это требуется для анализа его корректности. Зададимся положительным целым десятичным числом, например, равным 5, и выполним его перевод в двоичную систему счисления по приведенному алгоритму. В силу свойства дискретности алгоритма представим перевод в виде таблицы (табл. 24).
Таблица 24
| Шаг алгоритма | Выполняемое действие | Значения переменных | ||
| до выполнения шага алгоритма | после выполнения шага алгоритма | |||
| Модуль | Блок | |||
| 1 | Основной | 1 | А не определено | А=5 |
| 2 | Основной | 2 | А=5 | не меняется |
| 3 | Перевод | 1 | В не определено | В=целая часть (5/2) = 2 |
| 4 | Перевод | 2 | С(1) не определено | С(1) = 5-2*2 = 1 |
| 5 | Перевод | 3 | В=2 | не меняется |
| 6 | Формирование С | 1 | I=1 | I = 2 |
| 7 | Формирование С | 2 | С(2) не определено | С(2) = 2- целая часть (2/2)*2 = 0 |
| 8 | Перевод | 5 | В = 2 | В = целая часть (2/2) = 1 |
| 9 | Перевод | 3 | В = 1 | не меняется |
| 10 | Формирование Z | 1 | Z не определена | Z = 1 |
| 11 | Формирование Z | 2 | J не определена | J = 2 |
| 12 | Формирование Z | 3 | Z = 1 | Z = 1C(2) = 10 = 10 |
| 13 | Формирование Z | 2 | J = 2 | J = 1 |
| 14 | Формирование Z | 3 | Z = 10 | Z = 10C(1) =101 = 101 |
| 15 | Формирование Z | 2 | J = 1 | J = 0 |
| 16 | Основной | 5 | Z = 101 | не меняется |
Оформление курсовой работы должно быть выполнено аккуратно, текст пояснительной записки подготовлен с помощью текстового процессора WinWord (все текстовые абзацы оформлять в едином стиле), отпечатан на принтере на листах формата А4, снабжен титульным листом (оформление см. далее).
По заданиям 1 - 11 представить только данные (таблицы, рисунки, формулы), описывающие ход решения задачи, аналогичные тем, которые приведены в указаниях по выполнению заданий (см. табл. 25). По заданию 12 представить блок-схемы, выполненные в WinWord.
Таблица 25
| № задания | №№ формул | №№ рисунков | №№ таблиц |
| 1 | (1) - (3), (5), (6) | - | 1 |
| 2 | (7), (9) | - | 3, 4 |
| 3 | (10) | - | 6, 7 |
| 4 | (11) | - | 8 |
| 5 | (12), (13) | - | 9, 10 |
| 6 | (15) | 1 | 11, 12 |
| 7 | (16) | 2 | 13, 14 |
| 8 | (17) | - | 15, 16 |
| 9 | - | - | 17 – 20 |
| 10 | (22) - (24), (26), (27), (29) | - | - |
| 11 | (30) – (43) | - | 21, 22 |
| 12 | - | 3 - 7 | 23, 24 |
Калининградский государственный технический университет
Кафедра систем управления и вычислительной техники
Курсовая работа по информатике
Работу принял: Работу выполнил:
_________________________ ст. гр._______________
(ученая степень, звание преподавателя) (номер учебной группы)
_____________________________________ _____________________________
(Ф.И.О. преподавателя) (Ф.И.О. студента)
_____________________________________
(оценка)
Подпись:__________________ Подпись:_____________
Дата:_____________________ Дата:_________________
Калининград
_________ г.
ОглавлениеКалининградский Государственный Технический Университет 1
Методические указания 1
для выполнения курсовой работы 1
по информатике 1
для студентов специальностей 1
220100 – Вычислительные машины, комплексы, системы и сети 1
220200 – Автоматизированные системы обработки информации и управления 1
Калининград 2
2003 2
УДК 621.38 3
УТВЕРЖДЕНО 3
Ректором Калининградского 3
государственного технического 3
университета 3
Введение 4
Часть 1. Кодирование дискретного сигнала 5
1.1 Кодирование кодами по образцу 5
Задание 1. Прямые коды 5
Указания по выполнению задания 1 5
Задание 2. Коды, учитывающие частоту символов 6
Указания по выполнению задания 2 6
Задание 3. Коды Грея 9
Указания к выполнению задания 3 9
1.2. Криптографическое кодирование дискретного сигнала 10
Задание 4. Метод простой подстановки 10
Указания по выполнению задания 4 11
Задание 5. Метод Вижинера 11
Указания по выполнению задания 5 12
1.3. Эффективное кодирование дискретного сигнала 13
Задание 6. Метод Шеннона - Фано 13
Указания по выполнению задания 6 13
Задание 7. Метод Хаффмена 15
Указания по выполнению задания 7 15
1.4. Помехозащитное кодирование дискретного сигнала 17
Задание 8. Построение кода для обнаружения ошибок 17
Указания по выполнению задания 8 18
Задание 9. Построение кода для исправления ошибок 19
Указания по выполнению задания 9 19
Часть 2. Измерение дискретного сигнала 23
Задание 10. Анализ эффективности кодирования 23
Указания по выполнению задания 10 23
Часть 3. Формы представления чисел 25
Задание 11. Сложение в обратных кодах 25
Указания по выполнению задания 11 25
Часть 4. Кодирование алгоритмов 29
Задание 12 29
Указания по выполнению задания 12 33
Часть 5. Правила оформления курсовой работы 39
Оглавление 41
1 Здесь и далее между кодовыми комбинациями введены пробелы только для удобства восприятия
2 Не должно превышать значения из графы 4 табл. 3