Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья, 2001
Издание:
IEEE Trans. Inform. Theory, vol.47, no. 1, 2-22
Авторы: Левенштейн В.И.
Efficient reconstruction of seguences
Аннотация:
В статье вводятся и решаются новые задачи эффективного восстановления неизвестной последовательности фиксированной длины с помощью ее образцов, искаженных ошибками заданного типа. Эти образцы могут рассматриваться как выходные последовательности при многократной передаче исходной последовательности по комбинаторному каналу с максимальным допустимым числом одиночных ошибок или по дискретному вероятностному каналу. Эффективность восстановления понимается в смысле минимизации числа N ошибочных образцов, которые достаточны для однозначного восстановления любой неизвестной последовательности или ее восстановления с допустимой точностью и/или вероятностью. Здесь также учитывается существование простого алгоритма восстановления. Приводятся полные решения для комбинаторных каналов при некоторых типах ошибок, характерных для теории кодирования, а именно, замены, транспозиции, выпадений и вставок символов. В общем случае эта задача для комбинаторных каналов сводится к новой задаче восстановления вершины графа с помощью минимального числа вершин в ее метрическом шаре заданного радиуса. Для дискретных каналов без памяти найдено асимптотическое поведение минимального числа повторных передач, которое достаточно для восстановления любой последовательности длины n в пределах расстояния Хэмминга d с вероятностью ошибки ε, когда d/n и ε стремятся к 0 при n → ∞ . Подобный результат для непрерывного канала с дискретным временем и белым гауссовым шумом также получен.
Ключевые слова:
восстановление, последовательности, оптимизация, алгоритмы, графы, метрика ощибок, комбинаторные и вероятностные каналы, повторная передача, приводимые восстановители, асимптотическое поведение.
Язык публикации: английский,  страниц: 20
Направление исследований:
Математические вопросы и теория численных методов
Полный текст на английском языке:
Экспорт ссылки на публикацию в формате:   RIS    BibTex
Сведения об авторах:
  • Левенштейн Владимир Иосифович,  ИПМ им. М.В. Келдыша РАН