ЛАБОРАТОРИЯ № 3
Лаборатория информационных технологий анализа
и защиты данных
Заведующий лабораторией – д.т.н., проф. Зяблов Виктор Васильевич
Тел.: (095) 299-50-96; E-mail: zyablov@iitp.ru
Ведущие ученые лаборатории:
к.т.н. |
Афанасьев В. Б. |
к.т.н. |
Сидоренко В. Р. |
к.т.н. |
Генкин А. В. |
д.ф.-м.н. |
Сорокин В. Н. |
к.т.н. |
Гитис В. Г. |
к.т.н. |
Стенина И. И. |
к.т.н. |
Давыдов А. А. |
к.т.н. |
Трушкин А. В. |
к.т.н. |
Зигангиров Д. К. |
к.т.н. |
Юрков Е. Ф. |
к.т.н. |
Переверзев-Орлов В. С. |
с.н.с. |
Вайншток А. П. |
к.ф.-м.н. |
Петрова Е. Н. |
н.с. |
Ващенко Е. А. |
к.ф.-м.н. |
Пирогов С. А. |
н.с. |
Чмора А. Л. |
Направления исследований:
Основные результаты
Помехоустойчивое кодирование и передача информации
Исследования 1999 года были посвящены решению следующих задач:
Введено семейство активных расстояний для сверточных кодов. Показано, что способность сверточных кодов исправлять ошибки определяется их активными расстояниями. Рассмотрен ансамбль периодических, изменяющихся во времени, полиномиальных сверточных кодов и для кодов этого ансамбля получены асимптотические нижние границы активных расстояний.
Были продолжены исследования плетеных сверточных кодов, предложенных в последние годы. Рассмотрена общая конструкция плетеных сверточных кодов, получившая название “твил”. Частными случаями этой конструкции являются конструкции плетеных сверточных кодов с внешней и внутренней основами. Изучены экспоненты ошибок и сложность декодирования двоичных плетеных сверточных кодов с внешней и внутренней основами. Показано, что для обеих конструкций вероятность ошибки экспоненциально убывает с ростом памяти плетеных кодов, а сложность декодирования при этом растет не экспоненциально. Кроме того, экспонента ошибок для плетеных сверточных кодов с внутренней основой расположена выше соответственной экспоненты ошибок для кодов с внешней основой. Исследованы асимптотические нижние границы активных расстояний плетеных сверточных кодов, показано что их активные расстояния могут быть ограничены снизу линейными функциями, коэффициент пропорциональности которых отличен от нуля для всех скоростей каскадных кодов. Предложены плетеные коды с внешними блочными кодами, показывается, что в этом новом классе плетеных кодов существует конструкция кодов, минимальное расстояние которых вдвое превышает произведение минимальных расстояний составляющих кодов.
Написано введение в теорию обобщенных каскадных кодов. Исследовались свойства CDMA систем с импульсно позиционной модуляцией применительно к задаче множественного доступа, основанной на использовании импульсного радио (система с "прыгающим временем"). Теоретические расчеты показывают, что число пользователей в канале может быть увеличено в десятки раз по сравнению с существующими методами. Предложен алгоритм конструирования синдромной решетки произвольного линейного блокового кода. Алгоритм сразу строит минимальную кодовую решетку без построения лишних вершин, используя метод адресации вершин решетки в соответствующих линейных пространствах.
Экспериментальное исследование итеративного декодирования сверточных кодов в канале с ограниченным по длительности откликом основанное на вычислении апостериорных вероятностей состояний канала и кода показало высокую эффективность этого метода. Исследование было ориентировано на применение в системе магнитной записи с высокой плотностью.
Исследование общих свойств прямоугольных кодов было продолжено. (Класс прямоугольных кодов включает все линейные, групповые, а также многие негрупповые коды). Определена прямоугольная алгебра. Показано, что все базисы t-прямоугольного кода равномощны. В общем случае прямоугольного кода эта задача остается открытой. Получены границы мощности базиса прямоугольного кода. Предложен простой алгоритм, позволяющий построить базис линейного кода на основе его порождающей матрицы. Предложен и исследован ряд процедур итеративного декодирования. Разработан алгоритм построения минимальной решетки множества слов минимального веса линейного кода. Алгоритм строит также прямоугольный базис этого множества, позволяющий хранить множество в компактном виде.
Получена новая нижняя граница функции надежности (экспоненты вероятности ошибки декодирования для наилучшего возможного кода) для Гауссовского канала. Эта граница базируется на новом подходе, развитом в последние годы в работах А. М. Барга. Этот подход расширяет полиномиальные методы теории кодирования для применения к различным инвариантам кодов. По существу, это первое концептуальное продвижение в указанной проблеме после работ Шеннона 1959 и 1967 г.г.
Исследования обнаружения ошибок в квантовом канале дает последовательное определение необнаруженных ошибок в квантовых кодах и доказывает, что существуют квантовые коды для которых вероятность необнаруженных ошибок экспоненциально падает с длиной кода. Получены новые соотношения между полиномиальными инвариантами линейных кодов и некоторыми комбинаторными инвариантами.
Рассмотрены следующие вопросы теории графов: изопирометрические проблемы на ребрах графов, эквивалентность дискретных экстремальных проблем, теорема Крускала-Катоны для линейных решеток, k-разбиения Хэмминговых графов. Получены новые спектральные нижние границы для бисекции ширины графов.
Предложены новые конструкции покрывающих кодов с радиусом покрытия 2-4, использующие идеи проективной геометрии над конечными полями и так называемые “полные множества индикаторов”. Построен ряд новых бесконечных семейств покрывающих кодов с наилучшими в настоящее время параметрами. Рассмотрены насыщающие множества в проективных геометриях и их связи с покрывающими кодами.
Построены бесконечные последовательности неприводимых двучленов вида (x^p^n-c) – над расширенными полями Галуа с произвольным основанием. Они дают итеративное представление бесконечных башен расширенных полей с экспоненциально растущей степенью расширения и почти линейной сложностью арифметики.
Разработан новый криптографический протокол, обеспечивающий конфиденциальную передачу данных и взаимную аутентификацию отправителя и получателя сообщений. Протокол гарантирует защиту от несанкционированного воспроизведения (replay attack) – сохранения данных легальных пользователей, полученных в результате подслушивания (копирования), в целях их дальнейшего использования, например, для получения несанкционированного доступа к ресурсам удаленного компьютера. В основе протокола – идея одноразовых паролей, предложенная компанией Bellcore. В настоящее время протокол проходит патентную экспертизу в США.
В 1999 году была продолжена кооперация с университетами Германии, Швеции и Финляндии, в области задач передачи информации и комбинаторных проблем в векторных пространствах. Совместно с университетом Ульма (Германия) рассматривались задачи кодовой модуляции, пропускной способности мобильных каналов и проблемы теории прямоугольных кодов. Работа поддержана Германским Научным Фондом (Deutsche Forschungs Gemeinschaft). Часть полученных результов составили PhD диссертацию, успешно защищенную J. Maucher (Германия). Совместные исследования в области каскадных сверточных кодов с Лундским Университетом (Швеция) проводятся уже довольно давно и будут продолжены. Эти работы поддержаны Шведской королевской академией. Совместные исследования в области линейных покрывающих кодов и “насыщающих множеств” в проективных геометриях проводились с Техническим университетом Хельсинки (Финляндия). Эти исследования поддержаны Академией Финляндии. Кроме того, некоторые сотрудники лаборатории выполняют совместные исследования с Исследовательским Центром Белл (США).
ГРАНТЫ:
Геоинформационные технологии и системы
Получены существенные теоретические и прикладные результаты в работах по геоинформатике. Разрабатывается технология информационного моделирования пространственно-временных процессов и явлений, происходящих в геологической среде. Разрабатываются сетевые геоинформационные системы.
Информационная модель описывает прогнозируемое событие средствами компьютерно-реализуемых формализмов (баз знаний, баз данных и алгоритмов). Модель включает в себя прогноз, правило его вычисления по признакам, используемый набор исходных данных, растровые признаки и цепочки операторов, преобразующие исходные данные.
Элементы технологии реализованы в сетевой геоинформационной системе GeoProcessor для публикации и комплексного анализа данных о свойствах геологической среды и решения задач геолого-геофизического прогноза (районирование территории по природной опасности, прогноз полезных ископаемых). Система GeoProcessor (http://gis.iitp.ru/geoproc) обеспечивает по сети Internet удаленный доступ к геолого-геофизическим и географическим базам данных и представляет информационные средства обработки, анализа, и извлечения существенной информации из пространственных данных (spatial data mining). Система GeoProcessor помогает оценить свойства среды на основе принципа аналогии с использованием методов принятия решений, базирующихся на правдоподобном выводе: метод сходства с выборкой прецедентов, метод сходства по экспертным высказываниям в конструкциях нечеткой логики, метод функций принадлежности, метод непараметрической регрессии. Система реализована по схеме клиент-сервер на языке Java.
В рамках проекта ”ASPELEA” программы EC Inco-Copernicus средствами системы GeoProcessor обработаны данные и созданы WWW приложения (http://gis.iitp.ru/geoproc, http://alba.jrc.it/gitis/index.html) по регионам Кресны (Болгария), Коринфский залив (Греция), Центральная Европа: смоделированы растровые поля преобразований гелого-геофизических данных и исследована взаимосвязь между полями признаков и пространственным распределением сейсмических событий, исследовано пространственно-временное распределение эпицентров землетрясений. Аплет представляет возможность пользователям экспериментировать с представленными данными в интерактивном режиме.
Начато новое направление работ по созданию векторной сетевой ГИС для представления, моделирования и анализа географической информации. Разработана версия системы COMPASS
(Cartography Online Modeling, Presentation and Analysis System) на языке Java. Система поддерживает публикацию географической информации (ГИ) в Интернет, комплексный интерактивный интуитивно понятный анализ пространственных и пространственно-временных свойств ГИ, интерактивное картографическое представление ГИ. Система COMPASS (http://gis.iitp.ru/compass) ориентирована на поддержку потребностей различных групп пользователей – от непрофессиональных пользователей сети Интернет до поддержки принятия решения на основе представления и интеллектуального анализа ГИ специалистами таких областей как: экономика, социология, демография, экология, политика, бизнес, административное управление. На основе системы COMPASS разрабатываются два WWW приложения: Демографические показатели России (http://gis.iitp.ru/undp/) и Маркетинговая информационная система (http://gis.iitp.ru/siemens/). Аплет представляет возможность пользователям экспериментировать с представленными данными в интерактивном режиме.Разработаны новые методы и развита технология пространственно-временного анализа сейсмотектонических процессов, которые реализованы в системе для информационного моделирования и проверки гипотез о предвестниках землетрясений GeoTime.
Разработаны новые методы и программное обеспечение для моделирования процесса миграции углеводородов и обнаружения залежей.
Международные контакты, конференции, выставки. Продолжалось научное сотрудничество в рамках проекта ASPELEA по программе INCO-COPER-NICUS и на основе двусторонних договоров с Лабораторией прикладной логики (Венгрия) и с Институтом горной механики ЧАН (Чехия), разрабатываемая геоинформационная проблематика включена в Российско-Индийское научно-тех-ническое сотрудничество и в задание по проекту “Spatial Mining for Data of Public Interest – SPIN!” (контракт EU IST-10536 SPIN!).
Результаты докладывались на конференциях и семинарах в Англии, Германии, Греции, Италии. Системы GeoProcessor и Compass экспонировались при поддержке Миннауки РФ на международной выставке по информационным технологиям Simo-99 (Испания).
ГРАНТЫ:
Партнерские системы
Исследования группы связаны с разработкой систем поддержки принятия решений, основанных на методах кооперативной обработки данных и знаний (партнерских систем). Методы ориентированы на анализ больших объемов зашумленных, неполных, нерегулярно распределенных данных и создание больших баз знаний в слабоформализованных областях типа медицины. Используется сетевая форма представления знаний, в соответствии с которой понятие рассматривается как результат вывода на иерархической сети с пороговыми условиями выполнения узлов. Пороговая сеть, названная синдромной, строится на основе интерактивных процедур выявления экспертных знаний, уточнения и пополнения базы знаний в результате исследования эмпирических данных и интеграции баз знаний в смежных областях.
В 1999 году основным направлением работы было исследование проблемы интеграции баз знаний и баз данных из разных источников.
Разработаны алгоритмы поддержки процесса согласования понятийных структур объединяемых баз знаний с привлечением разного типа контекстов их использования в партнерских системах. Показана возможность успешного применения пороговой сети для решения задач автоматического обучения распознаванию образов при непрерывном отклике, динамических данных и обработке изображений. На основе технологий партнерских систем начата разработка интеллектуальной системы поддержки решений врача в Главном военном клиническом госпитале МО РФ. Совместно с сектором цифровой оптики разработана технология поддержки анализа изображений, являющаяся последовательностью применения методов автоматической цифровой обработки и создания решающих правил синдромного типа.
ГРАНТЫ
:
Теория речевого сигнала
Исследованы виды искажений амплитудно-частотных характеристик речевого сигнала для различных типов микрофонов, телефонных трубок, различных видов и уровней шума в окружающей среде и степени влияния реверберации помещения. Разработана нелинейная модификация метода спектральной компенсации для стационарных помех и искажений.
Публикации в 1999 г.