 |
Указания к выполнению задания 3
|
|
|
|
Для построения кода Грея выполним следующие шаги:
1) исходя из мощности множества А, определим размер nxm таблицы для построения кода Грея, где n – число строк, m – число столбцов таблицы. Для этого будем последовательно наращивать число столбцов и число строк, начиная с одной строки и одного столбца, каждый раз проверяя, не достигнут ли требуемый размер таблицы. При этом схема наращивания числа строк и столбцов будет определяться следующим образом: число столбцов на каждом шаге итерации равно или на 1 превышает число строк (табл. 5).
Таблица 5
| Номер шага | Число столбцов m | Число строк n | Размер таблицы nxm |
| 16 > 13 |
Поскольку на седьмом шаге итерации удалось достичь требуемого размера таблицы, определение ее размеров закончено. Таким образом, получена таблица размером 4х4,
2) строки и столбцы таблицы пронумеруем двоичными числами из множества {00, 01, 10, 11}, элементы которого сами являются кодами Грея (затушеванные ячейки табл. 6),
Таблица 6
| 00 | а | в | е | и |
| 01 | п | о | н | л |
| 11 | р | с | т | ч |
| ь |
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
Криптографическое кодирование дискретного сигнала
Задание 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) для кодирования выполняем шаги:
q выписываем исходный текст (строка 1 табл. 10),
q формируем номера символов исходного текста из табл. 9 (строка 2 табл. 10),
q многократно записываем ключ под исходным текстом (строка 3 табл. 10),
q заполняем номера символов ключа из табл. 9 (строка 4 табл. 10),
q складываем по модулю 13 (это мощность множества А) номера символов (строка 5 табл. 10),
q заменяем полученные числа символами исходного алфавита из табл. 9 (строка 6 табл. 10). Таким образом, получаем строку, соответствующую исходному тексту:
тиоасеиоиовньлллнеии, (12)
Таблица 10
| Номер строки | Результаты выполнения кодирования | |||||||||||||||||||
| п | е | т | р | о | в | и | в | а | н | в | а | с | и | л | ь | е | в | и | ч | |
| и | в | а | н | и | в | а | н | и | в | а | н | и | в | а | н | и | в | а | н | |
| т | и | о | а | с | е | и | о | и | о | в | н | ь | л | л | л | н | е | и | и |
q заменяем символы строки (12) двоичными номерами из табл. 9. Получаем результат (отдельно закодирована фамилия, имя и отчество):
петров 1010 0011 0110 0000 1001 0010
иван 0011 0110 0011 0110 (13)
васильевич 0001 0101 1100 0100 0100 0100 0101 0010 0011 0011
Эффективное кодирование дискретного сигнала
Задание 6. Метод Шеннона - Фано
Выполнить кодирование исходного текста методом Шеннона-Фано. Частоты символов алфавита А, из которых состоит исходный текст, рассчитать по исходному тексту.
Указания по выполнению задания 6
1) для построения эффективного кода выполним следующие шаги:
q определим размер (в символах) исходного текста (переменная L) – он равен 20,
|
|
|
q определим частоты fi появления каждого символа в исходном тексте по формуле:
fi = mi / L, (14)
где mi – число появлений i-го символа в исходном тексте из табл. 2. Имеем графу 3 табл.11,
Таблица 11
| Символ алфавита А | Число появлений mi | Частота символа fi |
| а | 0,1 | |
| в | 0,2 | |
| е | 0,1 | |
| и | 0,15 | |
| л | 0,05 | |
| н | 0,05 | |
| о | 0,05 | |
| п | 0,05 | |
| р | 0,05 | |
| с | 0,05 | |
| т | 0,05 | |
| ч | 0,05 | |
| ь | 0,05 |
q упорядочим список символов алфавита А по не возрастанию частот. Получим графы 1 и 2 табл. 12,
q выполним последовательное деление списка символов в соответствии с алгоритмом Шеннона-Фано (графа 3 табл.12) и назначим символы 0 или 1 элементам списка символов – кодируем элементы. Процесс деления списка символов представлен также в виде двоичного дерева рис. 1, вершины которого равны суммарным частотам отрезков списка,
q «соберем» символы 0 и 1 слева направо в графе 3 для каждого символа алфавита А. Получим графу 4 табл.12.
Таблица 12
| Символ алфавита А | Частота символа fi | Этапы деления списка символов | Результирующие коды | |||
| I | II | III | IV | V | ||
| в | 0,2 | - | ||||
| и | 0,15 | - | ||||
| а | 0,1 | - | ||||
| е | 0,1 | - | ||||
| л | 0,05 | - | ||||
| н | 0,05 | |||||
| о | 0,05 | |||||
| п | 0,05 | - | ||||
| р | 0,05 | |||||
| с | 0,05 | |||||
| т | 0,05 | - | ||||
| ч | 0,05 | |||||
| ь | 0,05 |
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(н) 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.
|
|
|
|
|
|
