Методические указания для выполнения курсовой работы по информатике для студентов специальностей 220100 Вычислительные машины, комплексы, системы и сети (стр. 3 из 10)
Таблица 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 |
2) для кодирования выполняем шаги:
- выписываем исходный текст (строка 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
1) для построения эффективного кода выполним следующие шаги:
- определим размер (в символах) исходного текста (переменная 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