- •П ример 2.
- •8. Кодирование и декодирование, криптология и криптография, кодирующее устройство.
- •Алфавитное кодирование
- •14. Обнаружение ошибки в кодах Хемминга.
- •15. Конечный автомат. Входной и выходной алфавит, функции переходов и выходов
- •28. Примитивно – рекурсивные и частично – рекурсивные функции. Пример построения рекурсивной функции.
- •Примеры Приведем некоторые примеры частично рекурсивных функций.
- •29. Эквивалентность слов в ассоциативном исчислении. Определения, пример.
- •30. Нормальный алгоритм Маркова.
- •31. Машина Тьюринга. Описание, пример.
Алфавитное кодирование
Пусть существует некий алфавит (множество) , а так же алфавит .
Слово в алфавите - упорядоченный набор элементов из алфавита вида:
S(ℳ) - множество слов алфавита ℳ S(β) - множество слов алфавита β
Суть алфавитного кодирования в том, что каждой букве алфавита ℳ сопоставляется слово из алфавита β согласно схеме кодирования Σ.
10. Префикс и постфикс. Достаточное условие взаимной однозначности алфавитного кодирования.
Пусть слово a имеет вид a1a 2. Тогда a1называется префиксом слова a , а a2 суффиксом a . Если 0<|a1| <|a |, то a1 называется собственным префиксом a , если 0<|a2| <|a |, то a2|– собственный суффикс a .
Схема алфавитного кодирования f обладает свойством префикса, если для любых i и j (1 £ i, j £ m,i ¹ j) элементарный код i v не является префиксом элементарного кода j v .
Если схема обладает свойством префикса, то алфавитное кодирование является взаимно-однозначным. Таким образом, свойство префикса является достаточным условием взаимной однозначности.
Проблема распознавания взаимной однозначности алфавитного кодирования решена Ал.А. Макаровым. Алгоритм распознавания состоит в следующем. Для кода V=(v1,v2,…vn) пусть S – множество слов, обладающих следующим свойством. Слово b является собственным префиксом некоторого элементарного кода vi и одновременно собственным суффиксом некоторого vj. Положим S=Si U {λ} (λ – пустое слово).
Сопоставим коду V ориентированный граф G, вершинами которого являются элементы множества S. Вершины a и b соединяем ориентированным ребром(a,b), если существует элементарный код vj и последовательность элементарных кодов P= vi1,vi2…vik, такие, что vj=avi1,vi2…vikb. При этом P может быть пустой, если a и b оба непустые.
Ребру (a,b) препишем последовательность vi1,vi2…vik. Ребро (λ,λ) присутствует в графе тогда и только тогда, когда существует vj и последовательность P=vi1, vi2…vik(k>=2)б такие, что vj=vi1,vi2…vik/
Алфавитный код V является взаимно-однозначным тогда и только
тогда, когда в графе G отсутствуют ориентированные циклы, проходящие через
вершину λ.
11. Элементарное разложение. Критерий Маркова. Примеры.
12. Двоичное исчисление. Перевод числа из десятичной системы в двоичную и обратно.
13. Код Хемминга. Алгоритм построения.
Коды Хэмминга — наиболее известные и, вероятно, первые из самоконтролирующихся и самокорректирующихся кодов. Построены они применительно к двоичной системе счисления.
Построение кодов Хемминга основано на принципе проверки на четность числа единичных символов: к последовательности добавляется элемент такой, чтобы число единичных символов в получившейся последовательности было четным. знак здесь означает сложение по модулю 2
. - ошибки нет, однократная ошибка. Такой код называется или . Первое число - количество элементов последовательности, второе - количество информационных символов. Для каждого числа проверочных символов существует классический код Хемминга с маркировкой т.е. - . При иных значениях k получается так называемый усеченных код, например международный телеграфный код МТК-2, у которого . Для него необходим код Хемминга , который является усеченным от классического . Для Примера рассмотрим классический код Хемминга . Сгруппируем проверочные символы следующим образом:
знак здесь означает сложение по модулю 2.
Получение кодового слова выглядит следующим образом:
=