ЛАБОРАТОРИЯ № 3

Лаборатория информационных технологий анализа

и защиты данных

Заведующий лабораторией – д.т.н., проф. Зяблов Виктор Васильевич

Тел.: (095) 299-50-96; E-mail: zyablov@iitp.ru

 

Ведущие ученые лаборатории:

к.т.н.

Афанасьев В. Б.

к.т.н.

Сидоренко В. Р.

к.т.н.

Генкин А. В.

д.ф.-м.н.

Сорокин В. Н.

к.т.н.

Гитис В. Г.

к.т.н.

Стенина И. И.

к.т.н.

Давыдов А. А.

к.т.н.

Трушкин А. В.

к.т.н.

Зигангиров Д. К.

к.т.н.

Юрков Е. Ф.

к.т.н.

Переверзев-Орлов В. С.

с.н.с.

Вайншток А. П.

к.ф.-м.н.

Петрова Е. Н.

н.с.

Ващенко Е. А.

к.ф.-м.н.

Пирогов С. А.

н.с.

Чмора А. Л.

 

Направления исследований:

Основные результаты

Помехоустойчивое кодирование и передача информации

Исследования проводились в следующих направлениях:

коды;

Было продолжено исследование общих свойств прямоугольных кодов. (Класс прямоугольных кодов включает все линейные, групповые, а также многие негрупповые коды). При мягком декодировании каскадных кодов возникает задача одновременного декодирования нескольких смежных классов линейного (прямоугольного) кода с помощью метода АПВ (т.е. метода вычисления апостериорных вероятностей). Решение этой задачи для одного смежного класса достигается построением минимальной решетки. В случае нескольких смежных классов предлагается строить кодовую решетку, имеющую несколько финальных вершин вместо одной вершины. Такую решетку называют расщепленной. Получены условия минимальности расщепленной решетки, т.е. минимальности сложности АПВ декодирования нескольких смежных классов. Работа выполнена при поддержке РФФИ (проект № 99-01-00840) и DFG (Германия).

Было продолжено исследование плетенных сверточных кодов. Исследовалась экспонента вероятности ошибки и сложность декодирования этого класса кодов. Показано, что вероятность ошибки экспоненциально убывает с увеличением памяти плетенных кодов при неэкспоненциальном росте сложности декодирования. Более того, были получены асимптотические нижние границы активных расстояний и было показано, что для всех скоростей плетенного кода эти расстояния ограничены снизу линейно растущей функцией со строго положительной производной.

Исследовались импульсные CDMA радио системы множественного доступа. По теоретической оценке количество пользователей системы может быть увеличено на порядок за счет новой технологии по сравнению с обычными системами.

Программа исследования инвариантов кодов, начатая еще в 1997 году, была завершена в текущем году. В частности, применение полиномиальных метода в теории кодирования было распространено на исследование границ кодовых расстояний. Множество новых асимптотических границ было получено для кодов и конструкций в пространствах Хемминга и Джонсона. Эти результаты имеют универсальный характер и могут быть применены для исследования распределения расстояний в любых линейных формах. Применение этой техники было продемонстрировано на получении новых асимптотических оценок радиуса покрытия линейных кодов.

Несколько совместных работ были посвящены доказательству существования кодов, идентифицирующих родительские связи для произвольного числа родителей (ранее это было известно только для двух родителей), вычислению объема сферы в некоторых подмногообразиях в многообразии Грассмана и эти результаты были использованы для вывода границы сферической упаковки в многообразии Грассмана, было построено семейство кодов, декодируемых за линейно растущее с длиной кода время при экспоненциально убывающей вероятностью ошибки для всех скоростей кода меньше пропускной способности канала.

Получила дальнейшее развитие теория покрывающих множеств в проективной геометрии. Была предложена новая концепция для плотности покрытия, и были получены новые бесконечные семейства покрывающих кодов с лучшими параметрами, чем известные.

Построены бесконечные расширения конечных полей Галуа с произвольной скоростью расширения. На этой основе были построены бесконечные башни расширенных полей с почти линейной сложностью арифметики.

Разработан секретный протокол для системы аутентификации биометрических данных. Этот протокол поддерживает реальные сценарии аутентификации биометрических данных и обеспечивает возможность шкалирования и подстройки, необходимых для аутентификации данных через Интернет. Предложенный протокол поддерживает различные сценарии и различные требования к производительности и секретности. Этот протокол предназначен для пересылки аутентифицированных биометрических данных (и не только их) через протоколы IP уровня, а также для решения проблемы распределения ключей для других секретных приложений в Интернете.

В течение 2000 года исследования кооперировалась с университетами Германии, Швеции и Италии. Основные направления исследований поддерживаются на протяжении многих лет. Совместно с Университетом Ульма (Германия) исследуются задачи кодовой модуляции, теория прямоугольных кодов и пропускной способности. Работа поддерживается DFG. Каскадные сверточные конструкции исследуются совместно с университетом Лунда (Швеция). Эти исследования поддерживаются Королевской академией Швеции. Покрывающие коды и их связь с покрывающими множествами в проективной геометрии исследуется совместно с отделением математики Университета Перуджи (Италия).

Некоторые сотрудники лаборатории вовлечены в исследовательские проекты с Research Center of the Bell Labs (USA) , а некоторые участвуют в проекте ЛОНИИС “Развитие принципов использования машинных систем распознавания речи, технологические средства их реализации и создание средств для экспериментальной верификации предложенных решений”.

Геоинформационные технологии и системы

Разрабатываются теоретические и прикладные проблемы геоинформатики. Особое внимание уделяется сетевому аспекту геоинформационных технологий и географических информационных систем (ГИ) для анализа и прогнозирования общественных и природных процессов и явлений.

Аналитические ГИС обрабатывают географическую информацию (ГИ), представленную в форме цифровых моделей. Цифровые модели ГИ включает три основные понятия: сущности, свойства и связи.

Рассматриваются четыре типа сущностей: 1) Объекты (административные единицы, месторождения, эпицентры и очаговые зоны землетрясений и т.д.), 2) Явления (аварии, природные и техногенные катастрофы, социальные взрывы и т.д.), 3) Процессы (социальные и демографические процессы, природные и техногенные процессы и т.д.) и 4) Множества точек пространственно привязанных к регулярной или нерегулярной сетке (эти точки могут представлять систему измерений, геофизические поля и т.д.).

Свойства представляют собой понятия, которые описывают сущности. Существует много способов классификации географических свойств. Наиболее важной для аналитических ГИС является классификация на собственные свойства ГИ, пространственные и временные свойства ГИ.

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

На основе рассматриваемой модели ГИ можно сформулировать задачи, решаемые аналитическими ГИС:

  1. Оценивание, выделение и понимание связей внутри/между собственными, пространственными и временными свойствами ГИ,

  2. Обнаружение, распознавание и понимание отношений внутри/между географическими объектами, явлениями, процессами и множествами точек.

  3. Вывод, экстраполяция и прогнозирование целевых заранее неизвестных свойств ГИ.

  4. Предсказание, распознавание и понимание целевых и заранее неизвестных свойств понятий.

Для решения сформулированных задач разрабатывается технология извлечения существенной информации из пространственно-временных данных когнитивно-графическими и аналитическими методами. Элементы технологии реализуются в разрабатываемых сетевых аналитических ГИС Geo Processor и COMPASS.

Сетевая аналитическая ГИС GeoProcessor предназначена для публикации и комплексного анализа данных о свойствах геологической среды и решения задач геолого-геофизического прогноза (районирование территории по природной опасности, прогноз полезных ископаемых). Система GeoProcessor (http://www.iitp.ru/projects/geo) обеспечивает по сети Internet удаленный доступ к геолого-геофизическим и географическим базам данных и представляет информационные средства обработки, анализа, и извлечения существенной информации из пространственных данных (spatial data mining). Система GeoProcessor помогает оценить свойства среды на основе принципа аналогии с использованием методов принятия решений, базирующихся на правдоподобном выводе: метод сходства с выборкой прецедентов, метод сходства по экспертным высказываниям в конструкциях нечеткой логики, метод функций принадлежности, метод непараметрической регрессии. Система реализована по схеме клиент-сервер на языке Java.

В рамках проекта ”ASPELEA” программы EC Inco-Copernicus средствами средствами системы GeoProcessor БД обработаны данные и созданы WWW приложения (http://www.iitp.ru/projects/geo, http://borneo.gmd.de/and/ geoproces

sor

) по регионам Кресны (Болгария), Коринфский залив (Греция), Центральная Европа: смоделированы растровые поля преобразований геолого-геофизичес-ких данных и исследована взаимосвязь между полями признаков и пространственным распределением сейсмических событий, исследовано пространственно-временное распределение эпицентров землетрясений. Аплет представляет возможность пользователям экспериментировать с представленными данными в интерактивном режиме.

Сетевая аналитическая ГИС COMPASS (Cartography Online Modeling, Presentation and Analysis System) предназначена для представления, моделирования и анализа векторной ГИ. Система поддерживает публикацию многослойной географической информации (ГИ) в Интернет, комплексный интерактивный интуитивно понятный анализ пространственных и пространственно-временных свойств ГИ, интерактивное картографическое представление ГИ. Система COMPASS (http://gis.iitp.ru/compass2) ориентирована на поддержку потребностей различных групп пользователей - от непрофессиональных пользователей сети Интернет до поддержки принятия решения на основе представления и интеллектуального анализа ГИ специалистами таких областей как: экономика, социология, демография, экология, политика, бизнес, административное управление. На основе системы COMPASS разрабатываются два WWW приложения: Демографические показатели России (http://gis.iitp.ru/undp/) и Маркетинговая информационная система (http://gis.iitp.ru/siemens/). Java аплет представляет возможность пользователям экспериментировать с представленными данными в интерактивном режиме.

Исследовались статистические связи между сейсмическими характеристиками (магнитудой и частотой землетрясений) и компонентами приливной силы Луны (шесть компонент собственно приливной силы и три компоненты положения Луны). Анализ связей проводился на уровне глобальных, региональных и локальных данных. Обнаружены статистически значимые, хотя и слабые, зависимости между магнитудой землетрясений и (а) меридиональной компонентой приливной силы (глобальный уровень), (б) амплитудой суточных колебаний приливной силы (для всех уровней анализа данных). Не обнаружено связи между частотой землетрясений и приливной силы Луны (проверка производилась на материале локальных данных). Не обнаружено запаздывающего влияния приливных сил на землетрясения (в пределах двух суток).

Международные контакты, конференции, выставки. Завершен проект AS-PELEA по программе INCO-COPERNICUS, начата работа по заданию проекта “Spatial Mining for Data of Public Interest - SPIN!” (контракт EU IST-10536 SPIN!), продолжалось сотрудничество на основе двустороннего договора с Лабораторией прикладной логики (Венгрия), соглашение с Национальным Геофизическим Исследовательским Институтом включено в программу Российско-Ин-дийского научно-технического сотрудничества.

Результаты докладывались на конференциях и семинарах в Австрии, Германии и России.

Системы GeoProcessor и Compass экспонировались при поддержке Миннауки РФ на международных выставках информационных технологий CeBit’2000 (Германия) и Simo’2000 (Испания) и на выставках в России Модуль’2000 и “Информационные технологии в науке”, ВВЦ, 2000 г. Материалы по системам GeoProcessor и Compass включены в каталог программного обеспечения ГИС-Ассоциации.

ГРАНТЫ:

Партнерские системы

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

Исследуются теоретические вопросы моделирования понятийных структур, решение которых позволяет согласовывать и объединять базы знаний в смежных областях, учитывая, в частности, свойства понятий, описывающих временные процессы.

Начата разработка новой системы анализа неполных и разнородных данных, объединяющая созданные ранее методы и технологии формализации знаний и поиска закономерностей в данных в виде синдромной сети. Система реализует интерактивные процедуры выявления экспертных знаний, уточнения и пополнения базы знаний в результате исследования эмпирических данных.

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

ГРАНТЫ:

 

Теория речевого сигнала

Исследовались методы решения динамической обратной задачи для управлений артикуляторными органами в случае, когда входными сигналами являются движения артикуляторов, измеренные с помощью микролучевого ренгтеноскопа и кинорентгенографии. Критерии оптимальности в виде квази-потен-циальной и квази-кинетической энергии обеспечили погрешность аппроксимации движений артикуляторов, находящуюся в пределах погрешности измерений. Воспроизведены эффекты реорганизации управлений при изменении темпа артикуляции и при фиксации нижней челюсти. Результаты работы являются сильным аргументом в пользу гипотезы внутренней модели в системе управления артикуляции, и указывают на возможные механизмы ее работы. Получены оценки максимальной скорости передачи информации для артикуляторного вокодера. Продолжались исследования акустических и артикуляторных детекторов в модели распознавания речи. Выполнены эксперименты по оценки информативности акустических детекторов и различительной способности артикуляторных детекторов. Проведены предварительные испытания последовательного декодера в системе распознавания числительных. На 90% завершена разметка базы данных числительных для 48 дикторов, двух типов телефонных трубок и трех типов микрофонов.

 

Публикации в 2000 г.

  1. Sidorenko V., Maucher J., Bossert M., and Lucas R. Rectangular Codes in Ite-rative Decoding. Proc. of 3rd ITG Conference Source and Channel Coding, Muenchen, Jan. 2000, p. 215-218.

  2. Sidorenko V., Maucher J., Bossert M. Bases of rectangular codes, Proc. of 2000 IEEE Intern. Symp. on Inf. Theory, Sorrento, Italy, June, 2000, p. 30.

  3. Sidorenko V., Maucher J., Bossert M., and Lucas R. Rectangular Codes in Ite-rative Decoding. Submitted to IEEE Trans.on Communications.

  4. Griesser H., Sidorenko V., Bossert M. A Trellis Based Algorithm for APP Decoding of Cosets, submitted to ISIT 2001.

  5. Ashikhmin A., Barg A., and Litsyn S. Estimates of the distance distribution of codes and designs, preprint (February 2000), IEEE Trans. Inform. Theory, to appear.

  6. Barg A., Justesen J., Thommesen C. Concatenated codes with fixed inner code and outer code randomly selected, preprint (February 2000), IEEE Trans. Inform. Theory, to appear.

  7. Barg A. and Jaffe D. Numerical results on the asymptotic rate of linary codes, "Codes and Association Schemes," AMS (2000), p.25-32.

  8. Barg A. and Nogin D. Bounds on packings of spheres in the Grassmann manifolds, DIMACS report 2000-19 (http://dimacs/rutgers.edu), submitted for publication.

  9. Ashikhmin A., Barg A., and Litsyn S. Estimates of the distance distribution of nonbinary codes, with applications. "Codes and Association Schemes," AMS (2000), p. 287-302.

  10. Ashikhmin A., Barg A., and Litsyn S. A new upper bound on the reliability function of the Gaussian channel, IEEE Trans. Inform. Theory, 46. Also Proc. ISIT-2000, Sorrento.

  11. Ashikhmin A., Barg A., Knill E., and Litsyn S. Quantum error detection, IEEE Trans. Inform. Theory, vol 46, May 2000, Part I: Statement of the problem, p. 778-789, Part II: Bounds, p. 790-801. Also Proc. ISIT-2000, Sorrento.

  12. Barg A. and Kabatiansky G. Codes with the identifiable parent property: the case of mulitple parents, Proc. ACCT-7, Bansko, Bulgaria, June 2000, p. 68-71.

  13. Barg A., Cohen G., Encheva S., Kabatiansky G., and Zemor G. A hypergraph approach to the identifying parent property: the case of multiple parents, DIMACS Report 2000-20 (http://dimacs/rutgers.edu), submitted for publication.

  14. Barg A., On polynomial invariants of codes, matroids and the partition function, Proc. ISIT 2000, Sorrento.

  15. Barg A. and Zemor G. Linear-time decodable, capacity achieving binary codes with exponentially falling error probability (September 2000), submitted for publication.

  16. Ashikhmin A. and Barg A. Bounds on the covering radius of linear codes, preprint (December 2000), submitted for publication.

  17. Barg A. and Litsyn S. Editors, "Codes and Association Schemes," American Mathematical Society, Providence, RI, 2000.

  18. Davydov A.A. and Ostergard P.R.J. "New quaternary linear codes with covering radius 2," Finite Fields and their Applications, vol. 6, 2000, p. 164-174.

  19. Davydov A.A.and Ostergard P.R.J. "On saturating sets in small projective geometries", Europian Journal of Combinatorics, vol. 21, 2000, p. 563-570.

  20. Davydov A.A. and Ostergard P.R.J. "Linear codes with covering radius R=2,3 and codimension tR", IEEE Transactions on Information Theory, to appear.

  21. Wintzell Ola, Zigangirov D.K., Zigangirov K.Sh. "On the capacity of a pulse position hopped CDMA system" IEEE Int Symp Inf.Theory (ISIT'2000), p. 135, Sorento, Italy, 25-30 June, 2000.

  22. Wintzell Ola, Zigangirov D.K., Zigangirov K.Sh. "On the capacity of a pulse position hopped CDMA system", Submitted for publication in IEEE Trans. on Information Theory.

  23. Трушкин А.В. О сравнительной сложности алгоритмов построения синдромной решетки линейного блокового кода // Пробл. передачи информ. 2000. Т. 36. № 2. С. 10-18.

  24. Чмора А.Л. Схема одноразовых паролей с квитированием // Технический отчет. BioLink Technologies International, Inc., Октябрь 1999.

  25. Чмора А.Л. Схема одноразовых паролей с квитированием. Версия 1.1 // Технический отчет. BioLink Technologies International, Inc., Ноябрь 1999.

  26. Чмора А.Л. Схема одноразовых паролей с квитированием. Версия 1.2 // Технический отчет. BioLink Technologies International, Inc., Декабрь 1999.

  27. Чмора А.Л. BDAP версия 1.4. Спецификация // BioLink Technologies International, Inc., 2000.

  28. Andrew Chmora. Versatile Cryptographic Protocol for Biometric Data Authentication. Submitted to Eurocrypt 2001. November, 2000.

  29. Afanassiev V.B. and Davydov A.A. Finite Field Towers: Iterated Presentation and Complexity of Arithmetics // Submitted to Finite Fields and their Applications.

  30. Nielsen J., Afanassiev V., Bach-Andersen J. A Dynamic Model of the Indoor Channel, accepted in Wireless Personal Commnications.

  31. Bezrukov S.L., Piotrowski V.P. Shadows and isoperimetry in bipartite graphs // presented by V.P. Piotrowski at SIAM conf. on Discr. Math., Minneapolis, June 2000.

  32. Bezrukov S.L., Serra O. A local-global principle for vertex-isoperimetric problems // presented by O. Serra at the International Slovenian Conference on Graph Theory in 2000 and at a seminar in the Mathematical Institute of the Hungarian Acad. Sci, September 2000, to appear in Discr. Math.

  33. Bezrukov S.L., Elsaesser R., Monien B., Preis R., Tillich J.-P. New spectral lower bounds for the bisection width of graphs // presented by R. Preis at the International Conference "`Graph-Theoretic Aspects of Computer Science'' (WG2000), Germany, July 2000.

  34. Bezrukov S.L., Elsaesser R. Edge-Isoperimetric Problems for Powers of Regular Graphs // presented by R. Elsaesser at the International Conference ODAS-2000, Rostock, Germany, September 2000.

  35. Bezrukov S.L., Das S., Elsaesser R. An edge isoperimetric problem for powers of the Petersen graph // Annals of Combinatorics, vol. 4, 2000, 153-169.

  36. Bezrukov S.L., Elsaesser R. The spider poset is Macaulay // J. Comb. Theory, vol. A-90, 2000, 1-26.

  37. Bezrukov S.L., Leck U. Some new results on Macaulay posets. In: Numbers, Information and Complexity, I. Althoefer, N. Cai, G. Dueck, L.Khachatrian, M. Pinsker, A. Sarkozy, I. Wegener and Z. Zhang (eds.), Kluwer Academic Publishers, 2000, 75-94.

  38. Bezrukov S.L., Chavez J.D., Harper L.H., Roettger M. U.-P. Schroeder, The congestion of n-cube layout on a rectangular grid // Discr. Math., vol. 213, 2000, 13-19.

  39. Bezrukov S.L., Serra O. A local-global principle for vertex-isoperimetric problems // to appear in Discr. Math.

  40. Bezrukov S.L. Discrete extremal problems // Big Russian Encyclopedia (in Russian)

  41. Bezrukov S.L. Embedding complete trees into the hypercube // to appear in Discr. Appl. Math.

  42. Amendola A., Bayer J., Ermoliev Y., Ermoliev T., Gitis V., Koff G. A System Approach to Modeling Catastrophic Risk and Insurability. "Natural hazards", 21, Netherlands, Kluver Academic Publishers, 2000, 381-393.

  43. Гитис В.Г., Вайншток А.П., Довгялло А.В. Сетевые геоинформационные технологии и системы. – Труды VII Всероссийского форума "Геоинформационные технологии. Управление. Природопользование. Бизнес. Образование". М.: РАГС, 2000, 91-97.

  44. Gitis V. An approach to WWW On-line intelligent geo-reference information analysis. – Abstr. of 2nd Euroconference Risk Global and Catastrophe Risk Management Earthquake Risk in Europe, IIASA, Luxemburg, Austria, 2000, 13.

  45. Gitis V., Osher B., Dovgiallo A., Vainshtok A. COMPASS: Cartography On-line Modeling, Presentation and Analysis System. – Proc. of the 5th EC-GIS Workshop, Stresa, Italy, EC JRC, 2000, 487-497.

  46. Gitis V., Vainchtok A. Final Report on project Assessment of Seismic Potential in European Large Earthquake Areas “ASPELEA”, EC Project INCO-COPERNICUS, 2000, 10 p.

  47. Гитис В.Г., Вайншток А.П., Довгялло А.В., Ошер Б. Сетевые аналитические геоинформационные технологии и системы. – Труды VII национальной конференции по искусственному интеллекту (КИИ'2000), Переславль-Залес-ский, 2000, 741-749.

  48. Юрков Е.Ф. Система анализа характеристик акустического процесса при разрушении образцов горных пород // Вулканология и сейсмология (в печати).

  49. Belikova T.P., Stenina I.I., Yashunskaya N.I. Computer-Aided Methods to Support Image Interpretation in the Case of Uncertainty. In: Procеed. of 14 Int. Congress on Assisted Radiology and Surgery – CARS’ 2000, San-Francisco (USA): Excerpta Medica, Intern. Congess Series V. 1214, p. 1050.

  50. Belikova T.P., Stenina I.I., Yashunskaya N.I. Computer-aided methods to recover strategies for visual search and navigation // SPIE Congress on Medical Imaging. Medical Imaging 2000. San-Diego, USA, Proced. SPIE V. 3981, 2000, p 240-250.

  51. Vitushko M., Gurov N., Pereverzev-Orlov V. "Syndrom" as a method of conceptual modeling // Pattern Recognition and Image Analysis (to print).

  52. Sorokin V.N., Leonov A.S., Trushkin A.V. Estimation of stability and accuracy of inverse prbolem solution for the vocal tract // Speech Communication. 2000. V. 30. No. 1. P. 55-74.

  53. Leonov A.S., Sorokin V.N. Inverse problem for the vocal tract: Identification of control forces from articulatory movements // Pattern Recognition and Image Analysis. 2000, No. 10. P. 110-126.

  54. Leonov A.S., Sorokin V.N. Inversion from articulatory movements to control forces // Proc. 5th Seminar on Speech production, Kloster Seeon, 2000, P. 17-20.

  55. Сорокин В.Н. Концепция внутренней модели в речеобразовании и восприятии речи. – Труды 10 сессии Российского акустического общества. 2000, т. 2, с. 248-256.

  56. Леонов А.С., Сорокин В.Н. Обратная задача для управления артикуляцией // Доклады Академии Наук. 2000. Т. 374. № 6.