Студопедия  
Главная страница | Контакты | Случайная страница

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

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

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

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

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

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

 


Дата добавления: 2014-12-20; просмотров: 10 | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2018 год. (0.008 сек.)