Валидация поведения передатчика в канале частичного стирания в случае отсутствия абсолютно различимых символов

doi:10.17223/20710410/67/4

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
Валидация поведения передатчика в канале частичного стирания в случае отсутствия абсолютно различимых символов	682 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/67/4

#скрытые каналы

#канал частичного стирания

#абсолютно различимые символы

#Беллмана-Форда алгоритм

#проверка отсутствия аномалий 2-го рода

Title: Валидация поведения передатчика в канале частичного стирания в случае отсутствия абсолютно различимых символов
Creator: Казаков, Илья Борисович
Date: 2025
DOI: 10.17223/20710410/67/4
Description: Работа принадлежит циклу работ, посвященных каналу частичного стирания, где были введены понятия структуры частичного стирания, канала частичного стирания, правильной функции и корректного протокола. Структура частичного стирания — это тройка, состоящая из алфавита A, семейства его разбиений и множества вероятностей, приписанных этим разбиениям. Символы a1, a2 ∈ A называются абсолютно различимыми в структуре частичного стирания, если не существует такого разбиения, что они принадлежат одному его классу. Канал частичного стирания функционирует следующим образом: Алиса посылает Бобу символ a∈A, но Боб узнает только, какое выбрано разбиение и какому классу принадлежит отправленный Алисой символ. Поведение передатчика в канале частичного стирания задается функцией F : S* → A*, где S — алфавит входной ленты, с которой передатчик считывает информацию. Функция F однозначно определяет детерминированную функцию F^ : S* → A*: для любого слова s^ ∈ S*, s^ = s1...sm, положим F^(s^) = F(Λ)F(s1)F(s1s2)...F(s1...sm), где Λ — пустое слово. Функция F^ может быть представлена в виде автомата с входным алфавитом S и выходным алфавитом A*. Автомат задается графом, вершины которого соответствуют состояниям, а ребра имеют две подписи: s ∈ S и α ∈ A*. Для существования корректного протокола, включающего в себя функцию F поведения передатчика, необходимо и достаточно принадлежности функции F к классу правильных. Функция является правильной тогда и только тогда, когда отсутствует аномалия 2-го рода, не являющаяся также и аномалией 1-го рода. Под аномалией 2-го рода понимается пара слов (s^1, s^2), такая, что |s^2| = |s^1| + 1, |F^(s^2)| ≤ |F^(s^1)|; под аномалией 1-го рода — пара слов (s^1. s^2), для которой найдtтся индекс i, что символы F^(s^1)[i] и F^(s^2)[i] абсолютно различимы в структуре частичного стирания. В важном частном случае отсутствия абсолютно различимых символов аномалии 1-го рода не могут существовать и условие правильности упрощается до отсутствия аномалий 2-го рода. Показано, что проверка отсутствия аномалий 2-го рода сводится к проверке отсутствия путей (начинающихся в выделенной вершине) отрицательного веса в автомат-квадратном графе, которая может быть выполнена с помощью алгоритма Беллмана — Форда. Общая сложность такой проверки составляет O(|Q|4|S|2) по времени и O(|Q|2|S|2 ln |Q| ln L ln |S|) по памяти, где |Q| — количество состояний автомата, представляющего функцию F^, и L — максимальная длина передаваемого Алисой слова.