Алгоритм распознавания алфавита векторов, порождающего последовательности с квазипериодической структурой
Автор: Кельманов Александр Васильевич, Хамидуллин
Журнал: Проблемы информатики @problem-info
Рубрика: Теоретическая информатика
Статья в выпуске: 1 (2), 2009 года.
Бесплатный доступ
Рассматривается проблема помехоустойчивого апостериорного (off-line) распознавания алфавита век- торов, порождающего последовательности, включающие квазипериодически перемежающиеся век- тор-фрагменты, совпадающие с элементами из этого алфавита. Исследуется дискретная экстремаль- ная задача, к которой сводится один из вариантов данной проблемы. Обоснован точный полиноми- альный алгоритм решения редуцированной задачи, гарантирующий максимально правдоподобное принятие решения, в случае если помеха аддитивна и является гауссовой последовательностью неза- висимых одинаково распределенных случайных величин, а количество перемежающихся вектор- фрагментов неизвестно. Показано, что предложенный алгоритм имеет существенно меньшую трудо- емкость по сравнению с известным аналогом.
Дискретная экстремальная задача, эффективный алгоритм, числовая последовательность, квазипериодические фрагменты, алфавит векторов, off-line-распознавание, гауссова помеха, максимум правдоподобия
Короткий адрес: https://sciup.org/14319974
IDR: 14319974
Список литературы Алгоритм распознавания алфавита векторов, порождающего последовательности с квазипериодической структурой
- КЕЛЬМАНОВ А.В., ХАМИДУЛЛИН С. А. Об одном варианте задачи распознавания алфавита векторов//Тез. докл. междунар. конф. "Алгоритмический анализ неустойчивых задач", посвящ. 100-летию со дня рожд. В. К. Иванова, Екатеринбург, 1-6 сент. 2008 г. Екатеринбург: Урал. гос. ун-т, 2008. С. 282-283.
- KEL'MANOV A. V., JEON B. A posteriori joint detection and discrimination of pulses in a quasiperiodic pulse train//IEEE Trans. on Signal Proc. 2004. V. 52, N 3. P. 1-12.
- WALD A. Sequential analysis. N. Y.: John Wiley, 1947.
- КЛИГЕНЕ Н., ТЕЛЬКСНИС Л. Методы обнаружения моментов изменения свойств случайных процессов//Автоматика и телемеханика. 1983. № 10. С. 5-56.
- ТОРГОВИЦКИЙ И. Ш. Методы определения момента изменения вероятностных характеристик случайных величин//Зарубеж. радиоэлектрон. 1976. № 1. С. 3-52.
- НИКИФОРОВ И. В. Последовательное обнаружение изменения свойств временных рядов. М.: Наука, 1983.
- ЖИГЛЯВСКИЙ А. А. Обнаружение разладки случайных процессов в задачах радиотехники/А. А.Жиглявский, А. Е. Красковский. Л.: Изд-во Ленингр. гос. ун-та, 1988.
- БАССВИЛЬ М. Обнаружение изменения свойств сигналов и динамических систем/М. Бассвиль, А. Вилски, А. Банвенист и др. М.: Мир, 1989.
- VAN TREES H. L. Detection, estimation, and modulation theory. Pt. 1, N. Y.: John Wiley and Sons Inc., 1968.
- HELSTROM C. W. Elements of signal detection and estimation, Englewood cliffs. New Jersey: Prentice-Hall, 1979.
- ANDERSON B. D. Optimal filtering, Englewood cliffs/B. D. Anderson, J. D. Moore. New Jersey: Prentice-Hall, 1995.
- DUDA R. O. Pattern classification and scene analysis/R. O. Duda, P. E. Hart. N. Y.: John Wiley and Sons Inc., 1973.
- FUKUNAGA K. Introduction to statistical pattern recognition. 2nd ed. N. Y.: Acad. Press, 1990.
- КЕЛЬМАНОВ А. В., ХАМИДУЛЛИН С. А. Об одном варианте задачи распознавания алфавита векторов, порождающего последовательности с квазипериодической структурой//Тр. 14-й Байкал. междунар. шк.-семинара "Методы оптимизации и их приложения", Иркутск, 2-8 июля 2008 г. Иркутск: Ин-т систем энергетики им. Л. А. Мелентьева СО РАН, 2008. Т. 1. С. 421-427.
- КЕЛЬМАНОВ А. В., МИХАЙЛОВА Л. В. Совместное обнаружение в квазипериодической последовательности заданного числа фрагментов из эталонного набора и ее разбиение на участки, включающие серии одинаковых фрагментов//Журн. вычисл. математики и мат. физики. 2006. Т. 46, № 1. С. 172-189.
- КЕЛЬМАНОВ А. В., ХАМИДУЛЛИН С. А. Апостериорное обнаружение заданного числа одинаковых подпоследовательностей в квазипериодической последовательности//Журн. вычисл. математики и мат. физики. 2001. Т. 41, № 5. С. 807-820.
- КЕЛЬМАНОВ А. В., ОКОЛЬНИШНИКОВА Л. В. Апостериорное совместное обнаружение
- КЕЛЬМАНОВ А. В. О некоторых полиномиально разрешимых и NP-трудных задачах анализа и распознавания последовательностей с квазипериодической структурой//Докл. 13-й Всерос. конф. "Математические методы распознавания образов". Зеленогорск, 30 сент. -6 окт. 2007 г. М.: МАКС Пресс, 2007. С. 261-264.
- КЕЛЬМАНОВ А. В. Полиномиально разрешимые и NP-трудные варианты задачи оптимального обнаружения в числовой последовательности повторяющегося фрагмента//Материалы Рос. конф. "Дискретная оптимизация и исследование операций". Владивосток, 7-14 сент. 2007 г. [Электрон. ресурс] Новосибирск: Ин-т математики им. С. Л. Соболева СО РАН, 2007. http://math nsc ru/conference/door07/DOOR_abstracts.pdf.
- KEL'MANOV A. V. Discrete optimization problem in a connection with the off-line noiseproof detection of a repeating fragment in a numerical sequence//Proc. of the 9th Intern. conf. "Pattern recognition and image analysis: new information technologies". Nizhni Novgorod: S. n., 2008. V. 1. P. 273-275.
- KEL'MANOV A. V., MIKHAILOVA L. V., KHAMIDULLIN S. A. QPSLab system for analysis and recognition of signals with a quasiperiodic structure//Proc. of the 9th Intern. conf. "Pattern recognition and image analysis: new information technologies". Nizhni Novgorod: S. n., 2008. V. 1. P. 412-418
