Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

ФУ(y``,y`)³ ФX(j(у``),j(y`)).

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

Обычно уточняют структуру абстрактных множеств Y`, X`, а также уточняют определение искажений в канале связи, то есть конкретизируют «функции искажений» Ф_Х, Ф_У.

Ниже приводится такие конкретизации и уточнения для описания помехоустойчивых шифров расшифрования в случае Х= Х`=Y`=У= W*, где W - конечный алфавит. При этом (в условиях эндоморфных шифров) математическая задача описания помехоустойчивых шифров сводится к задаче описания инъективных отображений W* в W*, не размножающих искажений определенных типов.

Приводимые ниже результаты посвящаются памяти выдающегося математика Андрея Андреевича Маркова. Они инициированы одним полученным в 1956 году результатом А. А. Маркова о биективных преобразованиях множества слов в конечном алфавите , сохраняющих длины слов и не увеличивающих расстояния Хемминга между словами одной длины, то есть не размножающих искажений типа замены букв в словах. Рассмотренная А. А. Марковым задача имеет много различных вариаций. В частности, представляют интерес не только биективные но и инъективные отображения, наряду с искажениями типа замены букв могут происходить искажения других типов, например, пропуски букв, по разному может определяться понятие близости слов и т.д. Некоторые из таких вариаций и рассматриваются ниже. В параграфе 3 на основе идей А. А. Маркова описано множество всех инъективных отображений , сопоставляющих словам одинаковой длины слова также одинаковой длины и не увеличивающих расстояние Хемминга между словами. В качестве следствия этого описания получается и упомянутый выше результат А. А. Маркова, частный случай которого в иной формулировке опубликован в [1], стр.248 и [2], теорема 9. В параграфе 4 рассматривается задача описания множества инъективных отображений , не размножающих искажений типа пропуска букв. Однако из них полностью описаны лишь биективные преобразования. В параграфе 5 полностью описано пересечение множеств и . В параграфе 6 в качестве меры близости произвольных слов (а не только слов одинаковой длины) рассматривается обобщенное расстояние Хемминга, функция , совпадающая с на парах слов одинаковой длины и принимающая значение на парах, в которых одно слово получается из другого удалением букв. Доказывается что при множество всех инъективных отображений, не увеличивающих значений функции , совпадает с пересечением множеств и хотя непосредственно из определений включение в каждое из этих множеств не усматривается. Заметим, что функция не является метрикой: она не удовлетворяет известному свойству треугольника.