«СЕКЦИЯ 1 ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ Среда, 21 апреля 2004 г., читальный зал преподавателей (ауд.232), гл. корпус МГТУ им.Н.Э.Баумана. Начало в 10.00. Председатель: профессор, д.т.н. Норенков И.П. Руководитель экспертной ...»

СЕКЦИЯ 1

ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ

Среда, 21 апреля 2004 г., читальный зал преподавателей (ауд.232), гл. корпус МГТУ

им.Н.Э.Баумана.

Начало в 10.00.

Председатель: профессор, д.т.н. Норенков И.П.

Руководитель экспертной комиссии: к.т.н., доцент Федорук В.Г.

Ученый секретарь: к.т.н., доцент Власов А.И.

Экспертная комиссия:

к.т.н., доцент БОЖКО А.Н., к.т.н., доцент ВОЛОСАТОВА Т. М., к.т.н., доцент ЖУК Д. М., к.т.н., доцент МАНИЧЕВ В. Б., к.т.н., доцент МАРТЫНЮК В. А., к.т.н., доцент ТРУДОНОШИН В. А., ст. преподаватель ГРОШЕВ С. В., ст. преподаватель КНЯЗЕВА С. ст.

преподаватель РОДИОНОВ С. В., ст. преподаватель ФЕДОРУК Е. В., ст. преподаватель ШЕСТАКОВ С. А., к.т.н., доцент ПИВОВАРОВА Н. В., к.т.н., доцент КАМЫШНАЯ Э.Н., ассистент КОЛОСКОВ С.В., ассистент ОЯ Д.Р.

1. CRM - СИСТЕМЫ УПРАВЛЕНИЯ ВЗАИМООТНОШЕНИЯМИ С КЛИЕНТАМИ.

ЧТО? КАК? ЗАЧЕМ?

Шаповалов А.Ю., Решетников Р.И.

МГТУ им. Баумана, кафедра ИУ4.

2. МЕТОД СКРЫТИЯ ДАННЫХ В НЕПОДВИЖНЫХ ИЗОБРАЖЕНИЯХ

Фомичева А.М.

МГТУ им. Баумана, кафедра РК6.

3. ИССЛЕДОВАНИЕ ВЕЙВЛЕТ-ВОССТАНОВЛЕНИЯ СИГНАЛОВ В ПАКЕТЕ

WAVELET TOOLBOX СКМ MATHWORKS MATLAB 6.5 R 13.

Учамприн А. В., Кручинин Д. А.

МГТУ им. Баумана, кафедра РК6.

4. ИССЛЕДОВАНИЕ КРИПТОАЛГОРИТМА «RIJNDAEL»

Ильницкий А.О.

МГТУ им. Баумана, кафедра РК6.

5. МЕТОД И ПРОГРАММА ДЛЯ СКРЫТИЯ ТЕКСТОВ

Еранова Е.В.

МГТУ им. Баумана, кафедра РК6.

6. КОДИРОВАНИЕ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ

Волокитин Д.В.

МГТУ им. Баумана, кафедра РК6.

7. ЛОГАРИФМИЧЕСКИЕ МЕТОДЫ КОДИРОВАНИЯ ЗВУКА

Соболева Ю.М.

МГТУ им. Баумана, кафедра РК6.

8. ПОСТРОЕНИЕ МОДУЛЯ МОНИТОРИНГА В ПРОГРАММНОЙ СИСТЕМЕ НА

ОСНОВЕ АКТИВНОЙ БАЗЫ ДАННЫХ

Костра В.В.

ИТМ НАН Украины, Днепропетровск, Украина

9. ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА БПФ

Лукьянец С.В.

МГТУ им. Баумана, кафедра РК6.

10. РАЗРАБОТКА АЛГОРИТМА ОБОБЩЕНИЯ ИНФОРМАЦИИ,

ОСНОВАННОГО НА ТЕОРИИ ПРИБЛИЖЕННЫХ МНОЖЕСТВ

Куликов А.В.

МЭИ (ТУ)

11. РАЗРАБОТКА СИСТЕМЫ УПРАВЛЕНИЯ ПРЕДПРИЯТИЕМ НА ОСНОВЕ

СОВРЕМЕННЫХ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

Иванцов И. С.

ЗАО «Мидаус»

12. СИСТЕМА МОДЕЛИРОВАНИЯ ПРОЦЕССА ЛИТЬЯ ВЫЖИМАНИЕМ В СРЕДЕ

САПР.

Носенко А.Г.

МГТУ им. Баумана, кафедра РК6.

13. ВОПРОСЫ РАЗРАБОТКИ ПРОГРАММНОГО КОМПЛЕКСА МОДЕЛИРОВАНИЯ

ДИНАМИКИ ТЕХНИЧЕСКИХ СИСТЕМ НОВОГО ПОКОЛЕНИЯ.

Алиев Е., Баженов С., Пузырев М.

МГТУ им. Баумана, кафедра РК6.

14. РЕАЛИЗАЦИЯ БЫСТРЫХ ПРЕОБРАЗОВАНИЙ ФУРЬЕ

НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ УСТАНОВКАХ

Берчун Ю.В.

МГТУ им. Баумана, кафедра РК6.

15. РАЗРАБОТКА КОНЦЕПЦИИ МОДУЛЯ ДИСКРЕТНОГО МАШИНОСТРОИТЕЛЬНОГО

ПРОИЗВОДСТВА В РАМКАХ ERP СИСТЕМЫ.

Бондарь Ю.А.

МГТУ им. Баумана, кафедра РК6.

16. СИСТЕМА МОДЕЛИРОВАНИЯ ПРОЦЕССОВ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

Беломойцев Д.Е.

МГТУ им. Баумана, кафедра РК6.

17. СРАВНЕНИЕ ПОДХОДОВ К ПРОЕКТИРОВАНИЮ ПРОГРАММНЫХ СИСТЕМ

Андронов А.В.

МГТУ им. Баумана, кафедра РК6.

18. ИССЛЕДОВАНИЕ РЕШЕНИЯ ИНТЕГРАЛЬНЫХ УРАВНЕНИЙ МЕТОДОМ

РЕГУЛЯРИЗАЦИИ ТИХОНОВА

Воронов А.В.

МГТУ им. Баумана, кафедра РК6.

19. ДВУХУРОВНЕВОЕ МОДЕЛИРОВАНИЕ ОПТИКОЭЛЕКТРОННЫХ СИСТЕМ

Трудоношин И.В.

МГТУ им. Баумана, кафедра РК6.

20 МЕТОД АНАЛИТИЧЕСКОЙ НАСТРОЙКИ НЕЙРОННЫХ СЕТЕЙ В ЗАДАЧЕ

КОНТЕКСТНОЙ КЛАССИФИКАЦИИ ТЕКСТОВ

Цыганов И.Г.

МГТУ им. Баумана, кафедра Иу4.

21. МЕТРИКИ ТЕКСТОВ В АВТОМАТИЗИРОВАННЫХ СИСТЕМАХ ОБРАБОТКИ

ИНФОРМАЦИИ

Руденко М. И., Цыганов И.Г.

МГТУ им. Баумана, кафедра Иу4.

22. КОМПЬЮТЕРНОЕ АДАПТИВНОЕ ТЕСТИРОВАНИЕ. АЛГОРИТМ И ТЕХНОЛОГИЯ

СОЗДАНИЯ ТЕСТОВ.

Мигунов В.О.

МГТУ им. Баумана, кафедра Иу4.

23. ТЕХНОЛОГИИ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ

Аксенов А.В.

МГТУ им. Баумана, кафедра РК6.

24.ТРЕНАЖЕР ДЛЯ ПОДГОТОВКИ ОПЕРАТОРОВ ПОДВОДНЫХ АППАРАТОВ

Н. Буйда, М. Григорьев, А. С. Медведев, Кошель Р.

МГТУ им.Н.Э.Баумана, СМ11.

25. ВОПРОСЫ ВИЗУАЛЬНОГО МОДЕЛИРОВАНИЯ СИСТЕМ В ТРЕНАЖЕРАХ

ПОДВОДНЫХ ТЕЛЕУПРАВЛЯЕМЫХ КОМПЛЕКСОВ

А.Гнеломедов, С. Медведев МГТУ им.Н.Э.Баумана, СМ11.

26. ВОПРОСЫ МОДЕЛИРОВАНИЯ ОБЪЕКТОВ ВИРТУАЛЬНОГО ПОДВОДНОГО МИРА

В ТРЕНАЖЕРАХ ПОДВОДНЫХ ТЕЛЕУПРАВЛЯЕМЫХ КОМПЛЕКСОВ

Н.Буйда, Кошель Р., М. Григорьев МГТУ им.Н.Э.Баумана, СМ11.

27. МЕТОД ФОРМИРОВАНИЯ МОДЕЛИ ДИНАМИКИ ПОДВОДНОГО АППАРАТА В

ТРЕНАЖЕРНЫХ СИСТЕМАХ

С.Медведев, А.Гнеломедов, Климов Е.

МГТУ им.Н.Э.Баумана, СМ11.

28. СИСТЕМНОЕ КОГНИТИВНОЕ МОДЕЛИРОВАНИЕ КТР ЭВС

Кутаков С. В.

CRM - СИСТЕМЫ УПРАВЛЕНИЯ ВЗАИМООТНОШЕНИЯМИ С КЛИЕНТАМИ.

CRM - CUSTOMER RELATIONSHIP MANAGEMENT SYSTEMS.

Scientific adviser: candidate of technical science, docent Vlasov A. I.

Moscow State Technical University named after N.E. Bauman, Moscow, Russia.

Аннотация В докладе описываются основы концепции CRM (Customer Relationship Management – Управление взаимоотношениями с клиентами). Отражены следующие составляющие концепции: история, структура, необходимость применения, стратегия бизнеса и развития предприятия на основе CRM решений.

Показаны цели внедрения CRM системы на предприятии, ее функции и возможности по доработке стандартных модулей. Приводится анализ эффективности внедрения CRM. Особое внимание уделяется отраслевым решениям на базе стандартных модулей на примере радиотехнического предприятия и телекоммуникационной компании. В заключении приводится обзор решений, представленных в России и тенденции развития CRM систем. http://crm.iu4.bmtu.ru.

Abstract The Client Relationship Management (CRM) conception fundamentals are described in this report. The CRM conception constituents, such as history, structure, application necessity, business strategy and CRM based enterprise development are presented here. The aims of the CRM introduction and integration, CRM functionality and standard modules revision possibility are demonstrated. Efficiency analysis is also considered.

Special consideration is given to the CRM branch decisions, based on the standard modules, by the example of the radio engineering enterprise and telecommunicational company. In conclusion CRM decisions presented in Russia are reviewed; CRM development tendency is presented.

CRM (Customer Relationship Management – Управление взаимоотношениями с клиентами) - это не программный продукт и не технология. Это даже не набор продуктов.

CRM - это направленная на построение устойчивого бизнеса концепция и бизнес стратегия, ядром которой является "клиенто - ориентированный" подход.

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

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

На уровне технологий CRM – это набор приложений, связанных единой бизнес логикой и интегрированных в корпоративную информационную среду компании (часто в виде надстройки над ERP) на основе единой базы данных. Специальное программное обеспечение позволяет провести автоматизацию соответствующих бизнес - процессов в маркетинге, продажах и обслуживании. Как результат, компания может обратиться к "нужному" заказчику в "правильный" момент времени, с наиболее эффективным предложением и по наиболее удобному заказчику каналу взаимодействия.

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

С точки зрения управления бизнесом эффект от внедрения CRM проявляется в том, что процесс принятия решения за счет автоматизации переносится на более низкий уровень и унифицируется. За счет этого повышается скорость реакции на запросы, растет скорость оборота средств, снижаются издержки.

Наконец, CRM включает себя идеологию и технологии создания истории взаимоотношений клиента и фирмы, что позволяет более четко планировать бизнес и повышать его устойчивость Ключевыми функциями CRM-систем являются следующие моменты:

1. Сбор информации. Система позволяет сотруднику организации удобным способом вводить информацию о клиенте в базу данных, либо же самому клиенту вводить эту информацию. В CRM-систему вводится вся доступная информация о клиенте.

Естественно, учитывается информация, которая относится к взаимодействию клиенткомпания. Также в систему вводится личная информация по клиенту (возраст, семейное положение, ежегодный доход, имущество и пр.). Вся данная информация заносится и обновляется при каждом взаимодействии компании с клиентом, т.е. при любом контакт между двумя сторонами, будь то личное посещение компании клиентом, телефон, почта, факс или интернет.

2. Хранение и обработка. Система позволяет сохранять и ранжировать полученную информацию, в соответствии с заданными критериями. Причем вся информация хранится в стандартной для корпорации форме. Также CRM-система в соответствии с заданными параметрами может анализировать полученную информацию, для последующего экспорта этой информации.

3. Экспорт информации. Предоставление информации CRM-системой является ее главной функцией. Информация, хранящаяся в системе, может быть затребована разными подразделениями и в разном виде. Например, система CRM может определить, какой товар лучше предложить определенному клиенту, на основе экстраполяции исторических данных, или, например, клиент является постоянным покупателем и система напомнит, что клиенту полагается скидка. Также сотруднику компании может просто понадобиться информации об исторических контактах клиента с фирмой, и система позволяет предоставить эту информацию в наглядном виде. Естественно, система позволяет выводить информацию, как по отдельному клиенту, так и по целевой группе в целом. Если для сотрудника отдела продаж наиболее важна информация по определенному клиенту, то для отдела маркетинга, скорее, важна агрегированная информация по определенной группе.

Существует множество проблем, для решения которых компании внедряют эти системы, всех их можно, так или иначе, свести к следующим:

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

2. Мультиканальность взаимоотношений. Контакт между клиентом и фирмой может осуществляться разными способами - телефон, факс, web-сайт, почта, личный визит.

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

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

Многими компаниями предел качества и минимизации издержек уже достигнуты (в том числе от использования ERP) и клиенты больше обращают внимание на сопровождающие моменты покупки и обслуживание.

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

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

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

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

Таким образом, концепция CRM весьма многогранна. Хотя ее отдельные элементы культивировались и раньше (например, уже давно делается акцент на обеспечении наивысшего качества продукта и сервиса), сами по себе они не достаточны.

Суть же концепции CRM в том, что наиболее желанный и прибыльный клиент имеет право на первоочередное и эксклюзивное обслуживание. Кроме того, концепция CRM ориентирует компанию на длительные взаимоотношения с клиентом.

Главная идея в том, чтобы учиться у своего клиента, иметь обратную связь и работать так, как клиент хочет.

1. Норенков И.П. Основы автоматизированного проектирования: Учеб. для вузов/ И.П.

Норенков. - М.: Изд-во МГТУ им. Н.Э.Баумана, 2002 --ISBN 5-7038-2090-1.

2. Шахнов В.А "Конструкторско-технологическое проектирование электронной аппаратуры". Издательство: МГТУ им. Баумана 2002.

3. spklabs.com.

4. cfin.ru.

5. www.e-commerce.ru.

МЕТОД СКРЫТИЯ ДАННЫХ В НЕПОДВИЖНЫХ ИЗОБРАЖЕНИЯХ

научный руководитель: к.т.н., доцент Волосатова Т.М.

METHOD OF DATA HIDING IN STILL IMAGES

The scientific chief: Ph.D., senior lecturer Volosatova T.M.

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

Abstract In the report one of methods of introduction of a digital watermark in still image is considered. This method modifies blue color component of pixel in such a manner that changes are not appreciable for the person, but are easily found out by numerical methods. According to this algorithm the program having successful results has been written.

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

Слово «стеганография» имеет греческие корни и буквально означает «тайнопись».

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

Развитие средств вычислительной техники в последнее десятилетие дало новый толчок развитию компьютерной стеганографии.

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

Можно выделить две причины популярности исследований в области стеганографии в настоящее время: ограничение на использование криптосредств в ряде стран мира и появление проблемы защиты прав собственности на информацию, представленную в цифровом виде. Первая причина повлекла за собой большое количество исследований в духе классической стеганографии (то есть скрытие факта передачи информации), вторая – еще более многочисленные работы в области так называемых водяных знаков. Цифровой водяной знак (ЦВЗ) – специальная метка, незаметно внедряемая в изображение или другой сигнал с целью контролировать его использование.

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

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

Существованием практически значимой задачей защиты фотографий, картин, видео от незаконного тиражирования и распространения;

Относительно большим объемом цифрового представления изображений, что позволяет внедрять цифровые водяные знаки (ЦВЗ) большого объема либо повышать робастность внедрения, то есть повышать устойчивость ЦВЗ к различным преобразованиям, производимым над файлом-контейнером;

Заранее известным размером контейнера, отсутствием ограничений, накладываемых требованиями реального времени;

Слабой чувствительностью человеческого глаза к незначительным изменениям цветов изображения, его яркости, контрастности, содержанию в нем шума, искажениям вблизи контуров;

Хорошо разработанными в последнее время методами цифровой обработки изображений.

Надо отметить, что последняя причина вызывает и значительные трудности в обеспечении робастности ЦВЗ: чем более совершенными становятся методы сжатия, тем меньше остается возможностей для встраивания посторонней информации. Развитие теории и практики алгоритмов сжатия изображений привело к изменению представлений о технике внедрения ЦВЗ. Если первоначально предлагалось вкладывать информацию в незначащие биты для уменьшения визуальной заметности, то современный подход заключается во встраивании ЦВЗ в наиболее существенные области изображений, разрушение которых приведет к полной деградации самого изображения. Не случайно поэтому стегоалгоритмы учитывают свойства системы человеческого зрения (СЧЗ) аналогично алгоритмам сжатия изображений.

В стегоалгоритмах зачастую используются те же преобразования, что и в современных алгоритмах сжатия (дискретное косинусное преобразование в JPEG, вейвлет-преобразование в JPEG2000). При этом существуют, очевидно, три возможности. Вложение информации может производиться в исходное изображение либо одновременно с осуществлением сжатия изображения-контейнера, либо в уже сжатое алгоритмом JPEG изображение.

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

Предложенный алгоритм внедряет ЦВЗ в область исходного изображения. Его преимущество в том, что для внедрения ЦВЗ нет необходимости выполнять вычислительно громоздкие линейные преобразования изображений. ЦВЗ внедряется за счет манипуляций яркостью и цветовыми составляющими (r, g,b).

24-битное изображение имеет RGB-кодировку. Встраивание выполняется в канал синего цвета, так как к синему цвету система человеческого зрения наименее чувствительна.

Рассмотрим алгоритм передачи одного бита секретной информации.

Пусть si – встраиваемый бит, I = {R,G,B} – контейнер, p = (x,y) - позиция, в которой выполняется вложение. Секретный бит встраивается в канал синего цвета путем модификации яркости где q - константа, определяющая энергию встраиваемого сигнала. Ее величина зависит от предназначения схемы. Чем больше q, тем выше робастность вложения, но тем сильнее его заметность.

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

Оценка b получается в виде:

Знак разности и значение определяют значение встроенного бита.

При использовании исходного файла значение встроенного бита определяется знаком разности значений b для закодированного и незакодированного изображения.

Разработанная программа встраивает ЦВЗ в 24-битный bmp-файл, а также извлекает его обоими вышеописанными методами. ЦВЗ представляется в виде вертикальных полос: белые пиксели соответствуют 1, а черные – 0, серые пиксели не содержат информации. В результате раскодирования создаются файлы, отображающие вид встроенного сигнала. В случае использования метода оценки яркости соседних пикселей точность определения ЦВЗ намного ниже, но тем не менее полосы четко различимы на фоне всего изображения. Размер исходного файла при внедрении в него ЦВЗ не изменяется. Программа функционирует в среде Windows 2000, XP.

1. Грибунин В.Г., Оков И.Н., Туринцев И.В. Цифровая стеганография. – М.: СОЛОНПресс, 2002.

2. Bender W., Gruhl D., Morimoto N., Lu A. Techniques for Data Hiding // IBM System Journal. 1996.

3. Мюррей Дж. Энциклопедия форматов графических файлов. 1996.

ИССЛЕДОВАНИЕ ВЕЙВЛЕТ-ВОССТАНОВЛЕНИЯ СИГНАЛОВ В ПАКЕТЕ

WAVELET TOOLBOX СКМ MATHWORKS MATLAB 6.5 R 13.

Научный руководитель: к.т.н., доцент Волосатова Т.М.

МГТУ им. Н. Э. Баумана, кафедра САПР (РК6), Москва, Россия

RESEARCH OF SIGNAL’S WAVELET-RESTORING IN WAVELET TOOLBOX

The scientific chief: Ph.D., senior lecturer Volosatova Tamara Mihajlovna MSTU named after Bauman, RK6 (CAD/CAM/CAE) department, Moscow, Russia [email protected], [email protected], http://blaze.aviel.ru Аннотация В данной работе при помощи пакета расширения системы 6.5 Wavelet Toolbox 2/2.5 исследуется преобразование, фильтрация и вейвлет-восстановление различных сигналов:

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

Abstract By means of using add-on 6.5 of system Wavelet Toolbox 2/2.5, in this research investigates transformation, filtration and Wavelet-restoring of some signals: Wavelet-analysis of signals, continuous plain Wavelet-transformation, discrete plain Wavelet-transformation, reverse Wavelet-transformation, direct reconstruction from plain Wawelet coefficients, multi-level plain Wavelet decomposition, multi-level plain Wawelet reconstruction, reconstruction of a single branch from plain Wavelet coefficients.

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

Термин «вейвлет», введённый впервые Морле (Morlet), в переводе с английского означает «короткая или маленькая волна». Вейвлеты занимают промежуточное положение между крайними случаями – синусоидой и импульсной функцией. Довольно грубо вейвлеты можно представить как некоторые волновые функции, способные осуществлять преобразование Фурье не по всей временной оси, а локально по месту своего расположения.

С помощью вейвлетов сигнал представляется совокупность волновых пакетов - вейвлетов, образованных на основе некоторой исходной (базовой) функции. Эта совокупность, разная в разных частях временного интервала определения сигнала и корректируемая множителями, имеющими вид сложных временных функций, и представляет сигнал с той или иной степенью детализации. Такой подход и называют вейвлет-анализом сигналов.

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

Прямое вейвлет-преобразование означает разложение произвольного входного сигнала на принципиально новый базис в виде совокупности волновых пакетов – вейвлетов, которые:

1) имеют вид коротких, локализованных во времени (или пространстве), волновых пакетов с нулевым значение интеграла.

2) Обладают возможностью сдвига по времени.

3) Способны к масштабированию (сжатию/растяжению).

4) Имеют ограниченный (или локальный) частотный спектр.

По обилию типов вейвлетов и функций для обработки сигналов пакет Matlab 6.0/6. Wavelet Toolbox 2/2.5 является лучшим среди пакетов расширения для систем компьютерной математики (СКМ) в этой области (пакеты расширения по вейвлетам есть и в новых реализациях СКМ Mathcad и Mathematica).

Непрерывное одномерное вейвлет – преобразование Вейвлет-спектрограмма слегка искажённой функции синуса:

Пусть имеется функция, описывающая сигнал вида sin(t)+0.1.*sin(t)^3. Составим программу построения графика этой функции и спектрограммы на основе первых 64 вейвлетов:

Вейвлет-спектрограмма отчётливо выделяет все особенности функции в точках перегиба.

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

В этом примере хорошо видно, что увеличение числа вейвлет-коэффициентов уже не бесполезно – картина спектра для больших по номеру коэффициентов выглядит боле стабильной, чем для малых. Но и здесь увеличение числа вейвлет-коэффициентов выше перестаёт влиять на вид спектра.

Построим временную диаграмму и вейвлет-спектрограмму реального звукового сигнала, загружаемого из файла mtlb c выборкой в 110 отсчётов:

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

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

Как показывают приведённые примеры, вейвлет-спектрограммы наиболее пригодны для анализа тонкой структуры сигналов, содержащих резкие скачки, переходы производных через 0 и т.д. К таким сигналам сейчас относятся звуковые сигналы речи и музыки и сигналы изображений.

Дискретное одномерное вейвлет-преобразование Наряду с непрерывным вейвлет-преобразованием существует дискретное вейвлетпреобразование. Его главным преимуществом является наличие эффективных алгоритмов быстрого вейвлет-преобразования, которое напоминает быстрое преобразование Фурье. В частности, для быстрого вейвлет-преобразования (БВП) может эффективно использоваться пирамидальный алгоритм с прореживанием по частоте. Благодаря этому появляется возможность анализа больших выборок за вполне приемлемое для практических целей время. Но эти возможности реализуются не для всех типов вейвлетов.

Одноуровневое обратное вейвлет-преобразование Таким образом, погрешность реконструкции равна 5,2*10-12, что близко к точности машинных расчётов двойной точности.

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

Применяя в предыдущем случае вейвлет Добеши 'db10' :

Теперь низкочастотная компонента сигнала выглядит как синусоидальная функция (за исключением небольшого участка в конце). Высокочастотная компонента отсеяна.

Снизив уровень восстановления, получим полностью восстановленный сигнал.

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

1. И. Добеши «Десять лекций по вейвлетам». R&C Dynamics, 2. В.П. Дьяконов «Вейвлеты – от теории к практике». Солон – Р, 3. http://www.exponenta.ru

ИССЛЕДОВАНИЕ КРИПТОАЛГОРИТМА «RIJNDAEL»

Научный руководитель: к. т. н., доцент Волосатова Т.М.

RESEARCH OF CRYPTOALGORYTHM «RIJNDAEL»

The scientific chief: Ph.D., senior lecturer Volosatova T.M.

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

Abstract The report describes main features and characteristics of block cryptoalgorythm «RIJNDAEL» and its program realization.

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

Криптоалгоритм «RIJNDAEL» является блочным шифром, который был разработан бельгийскими учёными. В 2002 году по результатам конкурса был выбран за основу американского стандарта шифрования AES.

Этот алгоритм обладает следующими преимуществами:

высокая эффективность на любых платформах высокий уровень защищённости хорошо подходит для реализации в smart-картах из-за низких требований к памяти быстрая процедура формирования ключа хорошая поддержка параллелизма на уровне инструкций поддержка разных длин ключа с шагом 32 бита Недостатки:

уязвим к анализу мощности «RIJNDAEL» - это итерационный блочный шифр, имеющий архитектуру “Квадрат”.

Промежуточные результаты преобразований, выполняемых в рамках криптоалгоритма, называются состояниями (State). Состояние можно представить в виде прямоугольного массива байтов (рис. 1).

Ключ шифрования также представлен в виде прямоугольного массива с четырьмя строками. Число столбцов Nk этого массива рано длине ключа, делённой не 32.

Раунд состоит из четырёх различных преобразований:

Замена байтов SubBytes() – побайтовой подстановки в S-блоках с фиксированной таблицей замен.

Сдвиг строк ShiftRows() – побайтового сдвига строк массива состояния на разное количество байт.

Перемешивание столбцов MixColumns() – умножение столбцов состояния, рассматриваемых как многочлены над GF(2^8), на многочлен третьей степени g(x) по Сложение с раундовым ключом AddRoundKey() – поразрядного XOR с текущим фрагментом развёрнутого ключа.

В таблице 1 приведены данные по времени выполнения RIJNDAEL на процессорах семейства Pentium Pro и Pentium II. Результаты были получены с использованием компилятора Visual C++ (версия 6).

Длина ключа / Количество циклов, необходимых для Производительность шифрования размер блока, разворачивания ключа На основе данного алгоритма была разработана программа «RIJNDAEL», оперирующая блоками в 128 бит с длиной ключа 128 бит. Программный продукт «RIJNDAEL» позволяет зашифровать и в последствии расшифровать любую последовательность байт, представленных в виде файла любого типа. Программа предоставляет удобный интерфейс для операционных систем семейства Windows. Программа может быть легко перекомпилирована под операционную систему семейства Unix с предварительной разработкой интерфейса под конкретную ОС.

1. Баричев С.Г., Гончаров В.В., Серов Р.Е. Основы современной криптографии:

Учебный курс. – 2-е изд., испр. и доп.- М.: Горячая линия – Телеком, 2002. – 175 с.:

2. Зенин О.С., Иванов М.А. Стандарт криптографической защиты – AES. Конечные поля / Под ред. М.А. Иванова – М.: КУДИЦ-ОБРАЗ, 2002.- 176 с. – (СКБ – специалисту по компьютерной безопасности).

МЕТОД И ПРОГРАММА ДЛЯ СКРЫТИЯ ТЕКСТОВ

научный руководитель: к.т.н., доцент Волосатова Т.М.

МГТУ им. Н.Э.Баумана, кафедра РК6, Москва, Россия.

METHOD AND PROGRAMM FOR TEXT HIDING

The scientific chief: Ph.D., senior lecturer Volosatova T.M.

Аннотация В работе представлен метод сокрытия изображений (текстов) и его программная реализация.

Abstract In the document the method for image (texts) hiding and its program realization is considered.

Проблема надежной защиты информации от несанкционированного доступа является одной из древнейших и не решенных до настоящего времени задач. Способы и методы скрытия секретных сообщений известны с давних времен, причем, данная сфера человеческой деятельности получила название стеганография. Это слово происходит от греческих слов steganos (секрет, тайна) и graphy (запись) и, таким образом, означает буквально “тайнопись”, хотя методы стеганографии появились, вероятно, раньше, чем появилась сама письменность (первоначально использовались условные знаки и обозначения).

В современной компьютерной стеганографии существует два основных типа файлов:

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

Контейнер—оригинал (или “Пустой” контейнер) — это контейнер, который не содержит скрытой информации. Контейнер—результат (или “Заполненный” контейнер) — это контейнер, который содержит скрытую информацию. Под ключом понимается секретный элемент, который определяет порядок занесения сообщения в контейнер.

Основными положениями современной компьютерной стеганографии являются следующие:

1. Методы скрытия должны обеспечивать аутентичность файла. Аутентичность предполагает абсолютное совпадение скрываемого и восстановленного текста.

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

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

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

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

1. Защита конфиденциальной информации от несанкционированного доступа.

2. Преодоление систем мониторинга и управления сетевыми ресурсами.

3. Защита авторского права на некоторые виды интеллектуальной собственности.

В настоящее время методы компьютерной стеганографии развиваются по двум основным направлениям:

1. Методы, основанные на использовании специальных свойств компьютерных форматов.

2. Методы, основанные на избыточности аудио и визуальной информации.

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

Один из этих методов был исследован и реализован в данной работе.

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

Этот класс методов является самым старым, он появился еще в "довиртуальную" эпоху и был просто перенесен на компьютеры с учетом их особенностей и возможностей. Данной категории принадлежит очень много алгоритмов. К полностью автоматическим относится, например, форматирование текста количеством пробелов отличным от единицы. Скажем, один пробел соответствует биту "0", а два - "1". Программа получает произвольный текст в качестве контейнера и внедряет в него какое-либо стегосообщение.

Алгоритм встраивания информации в текстовый файл Программа переводит в двоичный код текст встраиваемого сообщения и изменяет количество пробелов между словами в тексте файла-контейнера. При этом «1»-обозначается двумя пробелами, «0»- одним пробелом.

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

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

4. Грибунин В.Г., Оков И.Н., Туринцев И.В. Цифровая стеганография. – М.: СОЛОНПресс, 2002.

5. Bender W., Gruhl D., Morimoto N., Lu A. Techniques for Data Hiding // IBM System Journal. 1996.

6. Moskowitz I.O., Longdon G.E. A new paradigm hidden in Steganography // Proceedings of Workshop “New Security Paradigms”. ACM Press. 2000.

КОДИРОВАНИЕ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ

Научный руководитель: к.т.н., доцент Волосатова Тамара Михайловна

CODING OF DIGITAL IMAGES

Scientific chief: Ph.D.,senior lecturer Volosatova Tamara Mikhaylovna Аннотация В данной работе рассмотрена проблема создания стеганографической системы (стегосистемы) для встраивания текстовой информации в изображение. Стеганография - это метод организации связи, который собственно скрывает само наличие связи.

Abstract Under consideration is the problem of creating of stegosystem for embedding a text information in digital image.

Stegonography is a method of relation’s obtaining which hide presence of relations.

Слово "стеганография" в переводе с греческого буквально означает "тайнопись" (steganos - секрет, тайна; graphy - запись). К ней относится огромное множество секретных средств связи, таких как невидимые чернила, микрофотоснимки, условное расположение знаков, тайные каналы и средства связи на плавающих частотах и т. д.

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

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

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

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

Позднее, на конференции Information Hiding: First Information Workshop в 1996 году было предложено использовать единую терминологию и обговорены основные термины.

Стеганографическая система или стегосистема - совокупность средств и методов, которые используются для формирования скрытого канала передачи данных.

В качестве данных может использоваться любая информация: текст, сообщение, изображение и т. п.

В общем же случае целесообразно использовать слово "сообщение", так как сообщением может быть как текст или изображение, так и, например, аудиоданные. Далее для обозначения скрываемой информации, будем использовать именно термин сообщение.

Контейнер - любая информация, предназначенная для сокрытия тайных сообщений.

Пустой контейнер - контейнер без встроенного сообщения; заполненный контейнер или стего - контейнер, содержащий встроенную информацию.

Встроенное (скрытое) сообщение - сообщение, встраиваемое в контейнер.

Стеганографический канал или просто стегоканал - канал передачи стего.

В данной работе рассмотрен алгоритм[2,3] и разработана программа встраивания информации в изображение. Алгоритм основан на манипулировании яркостью l(x,y) за счет канала синего цвета b(x,y). В зависимости от бита Si, подаваемой на вход встраиваемой информации, модифицируется значение яркости канала синего цвета по следующему алгоритму:

1. Вычисляется яркость пикселя l(x,y) = 0.299r(x,y) + 0.587g(x,y) + 0.114b(x,y), где x, y – координаты пикселя.

2. Каждый пиксель модифицируется в соответствии со схемой где b’(x,y) – модифицированная составляющая пикселя.

3. Декодирование информации происходит путем сравнения исходного изображения со стегоизображением.

Разработанная программа поддерживает работу с 24-битными изображениями в формате BMP. Основным отличием файлов этого формата (DIB) - Device Independent Bitmap (аппаратно-независимый битовый образ) является то, что в них используется кодировка цветов с одной битовой плоскостью. Файлы битовых образов нового формата начинаются со структуры BITMAPFILEHEADER:

struct BITMAPFILEHEADER { word bfReserved1; //не используется word bfReserved2; //не используется dword bfOffbits; //смещение данных битового образа от заголовка в байтах Непосредственно за ней располагается структура BITMAPINFO, со держащая всю информацию о битовом образе. Она делится на две части: структуру BITMAPINFOHEADER, описывающей размеры и цветовой формат битового образа, и массив структур GBQUAD, определяющей цветовую палитру:

struct BITMAPINFO { BITMAPINFOHEADER bmiHeader;

struct BITMAPINFOHEADER { dword biSize; //число байт, занимаемых структурой

//BITMAPINFOHEADER

dword biWidth; //ширина битового образа в пикселах dword biHeight; //высота битового образа в пикселах word biPlanes; //число битовых плоскостей устройства word biBitCount; //число битов на пиксель dword biCompression; //тип сжатия dword biSizeImage; //размер картинки в байтах dword biXPelsPerMeter;//горизонтальное разрешение устройства, пиксел/м dword biYPelPerMeter; //вертикальное разрешение устройства, пиксел/м dword biClrUsed; //число используемых цветов dword biClrImportant; //число "важных" цветов

} BITMAPINFOHEADER;

Более подробно:

biSize - обычно используется для облегчения доступа к таблице цветов.

biPlanes - определяет число битовых плоскостей; однако, по скольку цвет кодируется последовательными битами, это число всег да равно 1.

biBitCount - этим полем определяется число цветов, используемых битовым образом. В зависимости от способа кодирования, может принимать значения:

1 - битовый образ монохромный, и таблица цветов должна содержать два элемента.

Каждый бит в массиве данных кодирует один пиксел. Если значение бита - 0, то пиксел становится первым цветом таблицы; если - 1, пиксел становится вторым цветом таблицы.

4 - битовый образ имеет максимум 16 цветов, и массив bmiColors (таблица цветов) имеет до 16 элементов. Цвет каждого пиксела определяется по таблице цветов при помощи четырехбитного индекса. Например, если первый байт данных имеет значение 3Ah, то при отображении битового образа цвет первого пиксела определяет четвертый элемент таблицы цветов, а цвет второго - одиннадцатый.

8 - битовый образ имеет максимум 256 цветов, и таблица цветов имеет до 256 элементов.

Каждый байт массива данных определяет цвет одного пиксела.

24 - битовый образ имеет максимум 2 в 24-й степени цветов. Таблица цветов пуста, а цвет пикселов определяется пакетами из трех байтов, описывающими цветовые интенсивности красного, зеленого и голубого цветов.

biCompression - тип сжатия. Может принимать значения:

BI_RGB - сжатие отсутствует;

BI_RLE8 - сжатие для формата 8 бит на пиксел;

BI_RLE4 - сжатие для формата 4 бита на пиксел.

biXPelsPerMeter и biYPelsPerMeter - могут использоваться для выбора из списка ресурсов пиктограммы, наиболее подходящей для данного устройства.

biClrUsed - число цветов, используемых данным битовым образом. Если 0, то используются все цвета палитры (указанные в массиве bmiColors).

biClrImportant - используется для управления алгоритмом отображения цветов. Так, если четыре различных приложения отображают на экране по одному битовому образу с цветами каждый, то адаптер, выводящий 256 цветов одновременно, не сможет полностью аутентично отобразить на экране все 4 картинки. В этом случае используется механизм замены цветов - ищется битовый образ с наименьшим приоритетом и его "лишние" цвета заменяются наиболее подходящими.

struct RGBQUAD { byte rgbRed; //интенсивность красного byte rgbGreen; //интенсивность зеленого byte rgbBlue; //интенсивность голубого byte rgbRserved; //не используется После того, как все параметры битового образа определены, в файле идут сами сканстроки битовой плоскости, причем первой скан-строкой в формате DIB считается нижняя скан-строка (т.е. начало координат находится в левом нижнем углу изображения).

1. В.Г. Грибунин, Цифровая стеганография, М., 2002 г.

2. Martin Kutter, Frdric Jordan, and Frank Bossen. Digital signature of color images using amplitude modulation. In Ishwar K. Sethi and Ramesh C. Jain, editors, Proceedings of the SPIE Storage and Retrieval for Image and Video Databases V, volume 3022, pages 518-526, San Jose, California, 1997.

3. Martin Kutter, Frdric Jordan, and Frank Bossen. Digital watermarking of color images using amplitude modulation. 3022(2):326-332, April 1997.

ЛОГАРИФМИЧЕСКИЕ МЕТОДЫ КОДИРОВАНИЯ ЗВУКА

научный руководитель: к.т.н., доцент Волосатова Т.М.

LOGARITHMIC METHODS OF SOUND CODING

The scientific chief: Ph.D., senior lecturer Volosatova T.M.

Аннотация В работе рассмотрены логарифмические методы кодирования звука, а именно Law и A Law.

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

Abstract In the document methods of sound coding ( Law and A Law ) is considered. The program realization allows encoding the audio signal and comparing Не смотря на то, что общепринято различать «сжатые» и «несжатые» звуковые данные, уместнее говорить просто о различных способах «кодирования» звука. Самый простой способ кодировки – это ИКМ. Даже этот простой формат сложнее, чем может показаться, и существует, по крайней мере, четыре формата ИКМ, широко используемые для записи файлов. С помощью алгоритмов компрессии звука ИКМ преобразуют в более компактный формат.

Линейные форматы записи звука, в некотором смысле, являются примитивными. Слух человека устроен так, что мы практически нечувствительны к небольшим искажениям громких звуков, зато очень хорошо замечаем те же искажения в более тихих звуках. Однако при использовании ИКМ уровень погрешности не зависит от величины амплитуды. Один из способов сохранения самых тихих звуков заключается в переопределении уровней с помощью использования нелинейных систем кодирования вместо стандартной линейной ИКМ. Суть данного метода заключается в более эффективном использовании того же количества битов. В результате получается возможность использования большего количества битов для слабых звуков, при записи которых потеря данных более заметна. Эту технологию можно рассматривать как метод компрессии.

У двух наиболее широко используемых нелинейных форматов общих черт больше, чем различий. В методах компрессии как мю-типа ( Law ), так и А-типа ( A Law ), для преобразования линейных отсчётов ИКМ в 8-битные коды применяются логарифмические формулы.

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

Разработанная программа реализует распространённые схемы логарифмической компрессии. Первоначально эти схемы были разработаны для использования в телефонных системах, а позднее были включены в стандарт ITU G.711.

Логарифм числа можно рассматривать как количество цифр в этом числе. В связи с этим отправной точкой для логарифмических форматов является таблица, в которой для каждого из 8-битных значений указано, сколько битов потребуется для записи этого значения.

Так называемая кодировка мю-типа (иногда пишется u Law или mu Law ) наиболее широкое распространение получила в Соединённых Штатах и Японии. Чтобы не усложнять записи формул, будем считать, что все моментальные значения представляют собой дробные числа в диапазоне от -1 до +1.

При работе с 16-битными отсчётами необходимо перед применением формул поделить их на 32768.

Допустим у нас есть выборка s. Тогда соответствующий ей отсчёт мю-типа sm вычисляется по формуле:

Эту формулу проще запомнить, если рассматривать её только для положительных значений. В таком случае она принимает вид Для преобразования выборок мю-типа обратно в линейные отсчёты достаточно воспользоваться обратной формулой:

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

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

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

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

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

Аналогичным образом работает и декодер. Старший бит используется для записи знака, три следующих – для определения, насколько надо сдвинуть 4 младших бита.

Данный вариант записи очень сильно напоминает формат записи 8-битного числа с плавающей точкой: один бит – для знака, три – для экспоненты и четыре – для записи мантиссы. Подобно большинству форматов с плавающей точкой старший бит мантиссы отбрасывается, и при декодировании приходится восстанавливать его, добавляя 16 к мантиссе.

При кодировании данным методом производится смещение 16-битного отсчёта ИКМ на 128, а затем на 4 перед остальным преобразованием. При декодировании эти значения аналогичным образом вычитаются после преобразования. Если рассматривать такие преобразования как аппроксимацию логарифма, то число 128 используется для обхода разрывности основной функции. Если посмотреть на данный алгоритм внимательнее, нетрудно заметить, что используются вообще только 13 старших бит. Добавление четырёх округляет значение до ближайшего, кратного восьми, повышая тем самым точность.

По своей концепции кодирование А-типа аналогично кодированию мю-типа. Как и мюкомпрессия, первоначально этот метод разрабатывался для телефонных систем. Акомпрессия получила широкое распространение в Европе. Подобно мю-компрессии, этот метод кодирования описывается как непрерывной функцией, так и цифровой аппроксимацией.

На самом деле А-компрессия определяет набор кодировок, зависящий от точного значения числового коэффициента А. Чаще всего А даётся значение 87.6. Пусть s - выборка, лежащая в диапазоне от 0 до 1. Тогда значение А-типа sA вычисляется по формуле:

Цифровая аппроксимация аналогична аппроксимации, используемой в мю-кодировке.

Основное отлитие заключается в том, что в выходном коде кодировки А-типа биты инвертируются через один.

Чтобы понять, что происходит при логарифмическом кодировании достаточно рассмотреть, как ведёт себя отношение сигнал/шум.

В случае линейной ИКМ берётся некоторый аналоговый сигнал, и каждое идеально точное моментальное значение округляется до ближайшего целого числа. Таким образом, разница между идеальной выборкой и значением ИКМ никогда не превышает величины младшего разряда. В случае логарифмического кодирования ситуация усложняется: для больших величин выборок ошибка увеличится, для небольших величин – уменьшится.

Такой меняющийся уровень ошибки влияет на её общую мощность. Если исходный звук становится громче, то величина отсчётов возрастает и, соответственно, возрастает ошибка.

То есть при увеличении мощности сигнала возрастает мощность ошибки. В случае же строго логарифмической кодировки отношение сигнал/шум практически постоянно.

7. Кинтцель Т. Руководство программиста по работе со звуком. – М.: ДМК - Пресс, 2000.

8. Гордеев О.В. Программирование звука в Windows. – СПб.: БХВ – Санкт-Петербург,

ПОСТРОЕНИЕ МОДУЛЯ МОНИТОРИНГА В ПРОГРАММНОЙ СИСТЕМЕ НА

ОСНОВЕ АКТИВНОЙ БАЗЫ ДАННЫХ

MODULE OF MONITORING CONSTRUCTION IN PROGRAM SYSTEM ON BASIS OF

ACTIVE DATABASE

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

Abstract The information technology of creation of the module of monitoring on basis of active database is described. It is necessary for observation over objects and processes in given subject domain. Use of the module as part of medical system, provides new feature of the data automatic analysis and output information to the doctor about patient state.

ВВЕДЕНИЕ

В настоящее время технологии создания активной базы данных (АБД), относятся к перспективным направлениям при разработке новых возможностей СУБД [1,2]. В рассматриваемом подходе АБД создается для решения задачи оперативного анализа параметров в структурированных медицинских документах, которые сохраняются в компьютерной медицинской карте пациента (КМК) [3].

На предыдущем этапе системного моделирования компонентов медицинской информационной систем (МИС) [4,5], были реализованы информационные технологии обработки параметров в формализованном медицинском документе [6], в процессе его составления для записи в КМК пациента. При этом сами алгоритмы обработки хранятся отдельно и открыты для доступа [6].

Задачи модуля мониторинга (ММ) : контролировать изменение (добавление) параметров в КМК, по возможности проводить их интерпретацию, сообщить результаты интерпретации заинтересованному пользователю (по запросу или в автоматическом режиме).

При практической реализации предложенного подхода в МИС модуль состоит из двух частей:

- интерпретатор - правил, который реализуется средствами серверной части МИС, самодостаточен и функционирует независимо от работоспособности клиентских частей;

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

Особенностью работы ММ является использование возможностей созданной АБД, которая позволяет выполнять семантические процедуры обработки параметров в БД, заложенных в саму БД, без явных или косвенных указаний пользователя.

ВОЗМОЖНОСТИ АКТИВНОЙ БАЗЫ ДАННЫХ

Информационная ситуация, отражающая состояние объектов наблюдения (пациентов) в МИС, с семиотической точки зрения представляет собой систему отображающих и выражающих ее параметров, находящихся в различных отношениях. В соответствии с основными положениями семиотики каждый параметр можно рассматривать в трех независимых, но взаимосвязанных аспектах: имя, значение, смысл [7]. Первые два аспекта можно реализовать с помощью информационных технологий на основе современных реляционных СУБД: значение - сохраняется в таблице параметров, имя – описывается элементами метаинформации [4,5], которые описывают параметр. Смысл – представляет собой результат процесса понимания параметра, выражающего заложенные в параметр логико-понятийные и образные сущности, и существуют определенные трудности его представления на уровне БД.

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

Структуру "активного" правила представим следующей комбинацией: "событие – условие – действие". Событие - фиксируется в результате выполнения некоторой стандартной операции в БД. Примерами события в реляционной БД могут быть: обновление некоторого поля некоторой таблицы, удаление записи из таблицы, занесение в таблицу новой записи и т.д. Условие - это произвольное логическое выражение, включающее предикаты, определенные над БД. Действие - это произвольный оператор или набор операторов, допускаемых СУБД, а также выполнение специальных функций в программном обеспечении МИС. Выполнение этого действия может явиться событием для некоторого другого правила и т.д. Очевидно, что система, поддерживающая работу АБД, должна обладать некоторой встроенной продукционной системой. Результат выполнения действий, при необходимости может передаваться лицу, принимающему решение, тем самым, реализуя между ним и АБД семантический диалог.

Средствами реализации указанных принципов могут являться: ограничения и утверждения, хранимые процедуры, триггеры, функции определяемые пользователем. Эти, и подобные им технические возможности, имеющиеся в современных реляционных СУБД, позволяют реализовывать различные общие модели АБД.

РАБОТА МОДУЛЯ МОНИТОРИНГА

Общую схему принципа работы модуля в МИС представим следующим примером (диаграмма на языке UML, рис. 1). Пользователь системы или прикладная программа (например, считывания данных с медицинского прибора) выполняют некоторое действие над БД. Например, врач-лаборант добавил в КМК пациента параметры теста "Общий анализ крови". Интерпретатор–правил должен сравнить его значения с известными значениями нормы, которые хранятся в шаблоне теста. При отклонении определенного параметра от пределов нормы этот факт сохраняется в БД, и лечащему врачу, может быть выдано соответствующее сообщение (или возможен вариант добавления в КМК специальной записи с этим сообщением).

Интерпретатор-правил, строиться на основе триггеров и сохраненных процедур, которые должны поддерживаться СУБД (ORACLE, SQL Server, InterBase и др.). Хранимые процедуры могут быть активизированы приложениями, присоединенными к БД, что позволяет осуществлять модульную разработку БД, обеспечивает легкость её сопровождения и повторного использования разработанных ранее процедур. В реализованном подходе хранения исходных данных, все записи всех пациентов хранятся в одной таблице – doc [8].

Для этой таблицы пишется триггер, который инициируется, при выполнении транзакции на добавление новой записи в БД.

Рис.1 Диаграмма состояний и взаимодействий модуля Пример записи триггера для СУБД SQL Server:

CREATE TRIGGER tr_for_insert ON doc

FOR INSERT

DECLARE @code VARCHAR(4) DECLARE @params VARCHAR(50) DECLARE @typz VARCHAR(3) SELECT @code=code,@params=txtz, @typz=typz FROM INSERTED EXECUTE obrab_blood @code @params @typz При добавлении новой записи в БД создается временная таблица inserted (в автоматическом режиме средствами SQL Server), со структурой аналогичной таблице doc. Из нее считываются данные, добавляемой в таблицу doc записи, которые передаются сохраненной процедуре obrab_blood. Пример сохраненной процедуры:

CREATE PROCEDURE obrab_blood @code INT, @params VARCHAR(50), @typz VARCHAR(3) AS DECLARE @param int DECLARE @i INT DECLARE @norm_v INT SET @i=0;

If @code='0005' AND @typz='Isl' BEGIN Param=Expract_param(3) --процедура извлечения необходимого параметра SELECT @norm_v=norm_v FROM Isl0005 WHERE CODE=3 -- верхняя граница нормы IF param > norm_v BEGIN INSERT INTO warnings VALUES('Количество лейкоцитов больше нормы') В процедуре анализируется добавляемая запись, проверяется значение параметра (количество лейкоцитов), если оно больше нормы, то в таблицу warnings записывается интерпретируемое сообщение. Интерпретатор-сообщений обрабатывает записи в этой таблице, и отображает эту информацию врачу, при просмотре КМК пациента. Для передачи автоматического сообщения врачу (если он в этот момент работает с БД), необходимо генерировать сообщение функцией RAISERROR.

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

ЗАКЛЮЧЕНИЕ

Описанная информационная технология реализации и использования модуля мониторинга входит в состав МИС "MedDoc", разработанной автором (под руководством д.т.н.

Алпатова А.П. и к.ф.-м.н. Прокопчука Ю.А.), которая используется в ряде лечебных учреждений Днепропетровской области [9]. Предложенный подход позволил реализовать в системе новые возможности автоматического анализа параметров и выработки оперативной информации врачу о состоянии пациента при работе с МИС. Разработанные активные правила хранятся на серверной части МИС и доступны создания и редактирования средствами СУБД (SQL Server). Ведется разработка удобного интерфейса пользователя для создания "активных" правил с помощью модуля мониторинга.

1. Ершов Н.М., Королев Л.Н., Малютина Э.Э. и др. Применение активных баз данных в прогнозировании. // Вестн.Моск.ун-та. Сер.15, Вычисл.матем. и киберн. 1998, №1 С.32- 2. С.Д. Кузнецов Основы современных баз данных // www.citforum.ru 3. Костра В.В. Информационная модель компьютерной медицинской карты пациента // Всероссийская научн.-технич. конф. молодых ученых и специалистов "БиомедсистемыТезисы докладов.- Рязань,2003.-С.130- 4. Прокопчук Ю.А., Костра В.В. Средства интеллектуализации открытых информационных систем // Докл. междунар. конф. “Информационные средства и технологии” (Москва, 16- октября 2001 г.) в 3-х томах. –М.: Изд-во “Станкин, 2001, Т.2. С.94 – 5. Костра В.В., Прокопчук Ю.А. Модульная технология построения информационных систем // III Молод. науч.-техн. конф. "Наукоемкие технологии и интеллектуальные системы 2001". Сборник докладов.-21-22 марта 2001 г., г. Москва, МГТУ им.Н.Э.Баумана, С.146- 6. Костра В.В., Прокопчук Ю.А. Принципы построения семантического процессора для медицинских информационных систем // IV Молод. научно-технич. конф. "Наукоемкие технологии и интеллектуальные системы 2002". 17-18 апреля 2002 г., г. Москва, МГТУ им.Н.Э.Баумана, С.28- 7. Перспективы развития вычислительной техники: В 11 кн.: Справ. пособие/ Под.ред.

Ю.М.Смирнова. Кн.1: Информационные семантические системы/ Н.М.Соломатин.- М.:

Высш.шк., 1989. – 126 с.

8. Ю. А. Прокопчук, В. В. Костра Анализ моделей данных в госпитальных системах // Информационные технологии и кибернетика на службе здравоохранения: Сборник докладов межд. научно-практ. конференции. – Днепропетровск: ИПК ИнКомЦентра УГХТУ, 2003.С.92- 9. Прокопчук Ю.А., Харченко О.А., Костра В.В. Госпитальные информационные системы:

опыт разработки и эксплуатации // Сборник тезисов IV специализированной выставки и конференции "Информационные технологии в медицине – 2003", Москва, 2003, - С.76-

ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА БПФ

Научный руководитель: к.т.н., доцент Волосатова Т.М.

PARALLEL PROCESSING OF ALGORITHM FFT

Аннотация Рассмотрена задача построения параллельного алгоритма быстрого преобразования Фурье. Описаны проблемы и способы их решения для архитектур с общей и распределенной памятью.

Abstract FFT algorithm development task has been reviewed. Problems and solutions to them for shared and distributed memory architectures have been described.

Алгоритм быстрого преобразования Фурье (БПФ) - это оптимизированный по скорости способ вычисления ДПФ.

Фундаментальное уравнение для получения N-точечного ДПФ выглядит следующим образом:

По отношению к этому уравнению следует сделать некоторые терминологические разъяснения. X(k) (прописная буква X) представляет собой частотный выход ДПФ в k-ой точке спектра, где k находится в диапазоне от 0 до N-1. N представляет собой число отсчетов при вычислении ДПФ.

Значение x(n) (строчная буква x) представляет собой n-ый отсчет во временной области, где n также находится в диапазоне от 0 до N-1. В общем уравнении x(n) может быть вещественным или комплексным.

Основная идея БПФ заключается в двух пунктах.

1. Необходимо разделить сумму из N слагаемых на две суммы по N/2 слагаемых, и вычислить их по отдельности. Для вычисления каждой из подсумм, надо их тоже разделить на две и т.д.

2. Необходимо повторно использовать уже вычисленные слагаемые.

Применяют либо "прореживание по времени" (когда в первую сумму попадают слагаемые с четными номерами, а во вторую - с нечетными), либо "прореживание по частоте" (когда в первую сумму попадают первые N/2 слагаемых, а во вторую - остальные).

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

Пусть имеется N=2T элементов последовательности x{N} и надо получить последовательность X{N}. Прежде всего, нам придется разделить x{N} на две последовательности: четные и нечетные элементы. Затем точно так же поступить с каждой последовательностью. Этот итерационный процесс закончится, когда останутся последовательности длиной по 2 элемента.

В этом заключается первый этап БПФ, который называется предварительной перестановкой.

По сравнению с последующим этапом он занимает мало времени, поэтому способы его параллельной реализации не рассматриваются.

На рисунке проиллюстрирован второй этап вычисления ДПФ. Линиями сверху вниз показано использование элементов для вычисления значений новых элементов. Удобство алгоритма состоит в том, что два элемента на определенных позициях в исходном массиве дают два элемента на тех же местах в преобразованном. Это позволяет обойтись одним массивом данных для исходных данных, результата и хранения промежуточных результатов для всех T итераций.

Именно так, а не иначе: сначала вычисляются элементы с номерами 0 и N/2, во всех ДПФ в количестве Nmax/N штук, потом с номерами 1 и N/2 + 1 и так далее. На рис. показана последовательность вычислений для N = 8. Такая последовательность обеспечивает однократное вычисление.

Величина называется поворачивающим коэффициентом.

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

Наибольшая эффективность в реализации вычислений и обмена достигается в том случае, если число процессоров равно 2m, это связано со спецификой линейного алгоритма БПФ. Так же не рационально использовать число процессоров, превышающее N/2, так как на одном шаге вычислений задействованы сразу 2 элемента массива и для них используется один поворачивающий коэффициент, поэтому 1 процессор за 1 итерацию вычисляет сразу элемента массива.

Для архитектур с общей памятью алгоритм реализован на потоках (threads). В процессе работы каждому потоку отводится своя часть всего массива преобразуемых комплексных чисел. На каждом шаге T (T=1..log2N-1) происходит создание n потоков, каждый из которых в зависимости от своего идентификатора работает с конкретной частью всего массива комплексных чисел. Работа потоков разделена на 2 этапа. На первом этапе происходит независимая работа потоков, так как обрабатываемые части не оказывают влияния на данные в других потоках.

На втором этапе происходит синхронная работа потоков, так как память общая, то каждый поток может обрабатывать loc_size/2 данных, где loc_size – это размер блока данных который выделятся определенному потоку. В связи с тем, что каждый поток обрабатывает только половину своих данных и изменяет часть чужих, то при работе на данном этапе необходима синхронизация работы потоков.

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

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

Для архитектур с распределенной памятью алгоритм реализован на библиотеке MPI.

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

На каждом шаге T после обработки данных осуществляется синхронизация с помощью функции MPI_Barrier. А в конце работы производится сбор обработанных данных.

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

Обратное преобразование практически ничем не отличается, только в процессе вычисления поворачивающего коэффициента необходимо заменить j на –j, а в конце поделить все полученные данные на N, распараллеливание чего не составляет никакого труда, так как данные в этом случае абсолютно независимы.

1. В.В.Воеводин. Информационная структура алгоритмов. М., Изд-во МГУ, 1997 г.

2. В.В.Воеводин, Вл.В.Воеводин. Параллельные вычисления. БХВ-Петербург, 2002 г.

3. MPI – The Complete Reference, The MIT Press, 1996.

4. http://www.parallel.ru 5. http://www.fftw.org 6. Man pages

РАЗРАБОТКА АЛГОРИТМА ОБОБЩЕНИЯ ИНФОРМАЦИИ,

ОСНОВАННОГО НА ТЕОРИИ ПРИБЛИЖЕННЫХ МНОЖЕСТВ

Московский энергетический институт (технический университет)

DEVELOPMENT OF ALGORITHM FOR INFORMATION GENERALIZATION

BASED ON THE ROUGH SET THEORY

Supervisor: doctor of technical sciences, professor Vagin V.N.

Moscow power engineering institute (technical university) Аннотация Рассматривается проблема обобщения объектов с учетом необходимости обработки неполной и противоречивой информации, хранящейся в реальных массивах данных. Для решения проблемы предлагается использовать средства теории приближенных множеств. Предлагается модификация алгоритмов обобщения, направленная на обработку реальных массивов данных. При этом учитываются такие особенности информации, хранящейся в реальных массивах данных, как большой объем, а также неполнота и противоречивость данных. Работа выполнена при поддержке РФФИ (проект № 02-07Abstract The problem of generalization of objects is considered in view of necessity of processing of the incomplete and inconsistent information stored in real databases. For the decision of this problem it is offered to use means of the rough set theory. Modification of algorithms for the generalization, intended for processing of real databases is offered. Here such features of the information stored in real databases, as great size, and also incompleteness and inconsistence of the data are taken into account. This work is supported by the RFBR (grant No. 02-07-90042).

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

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

В общем виде работа алгоритма, основанного на теории приближенных множеств, состоит из следующих шагов: поиск классов эквивалентности отношения неразличимости, поиск верхнего и нижнего приближений, поиск среза информационной системы и построение набора решающих правил. Кроме того, для обработки атрибутов с непрерывной областью значений применяется дискретизация. На этапе дискретизации непрерывная область значений атрибута разбивается на конечное число интервалов. И затем в процессе обобщения значения, лежащие внутри одного интервала, не различаются. Следует отметить, что задачи нахождения оптимального множества таких интервалов (или разграничивающих их делений) и поиска минимального среза NP-сложны, поэтому для их решения необходимы эффективные эвристические алгоритмы. Вычислительная сложность базового и наиболее широко используемого алгоритма дискретизации [1] обладает кубической зависимостью от числа объектов решающей таблицы, что делает его неприменимым для обработки больших баз данных. Далее мы предлагаем эффективную модификацию, решающую эту проблему.

Разработанный алгоритм направлен на снижение затрат времени и памяти, а также на обработку неполноты и противоречивости данных. Он основан на следующих идеях: а) В качестве существенных признаков рассматриваются признаки, входящие в приблизительные срезы достаточно высокого качества. Идею сокращения множества атрибутов можно обобщить путем введения понятия значимости атрибутов, что позволяет отразить степень важности атрибута в решающей таблице. б) Предложено одновременное выполнение дискретизации и поиска приблизительного среза. в) Развита идея итерационного вычисления количества пар объектов, различимых делениями непрерывной области значений количественного атрибута. Первоначально данная идея была предложена в [2], однако она применима лишь при наложении ряда ограничений на решающую таблицу. В предложенной модификации, которая далее будет рассмотрена подробно, эта идея была расширена на случай произвольной решающей таблицы. г) Для обработки неполноты данных, выраженной в наличии отсутствующих значений атрибутов, реализован метод присвоения всех возможных значений атрибута, относящихся к понятию [3].

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

Далее в докладе используются терминология и обозначения теории приближенных множеств, введенные в [1]. В частности решающей таблицей (или решающей системой) будем называть пару S (U, A {d }), где U – непустое конечное множество объектов, называемое обучающим множеством, А – множество условных атрибутов, dA – выделенный атрибут, называемый решением. Кроме того, для изложения предлагаемого алгоритма введем ряд дополнительных обозначений.

Для некоторого деления pta (a, cta ) для атрибута a A, и некоторого подмножества X U будем обозначать:

l X ( pta ) и r X ( pta ) - количество объектов из X, имеющих значение атрибута a, меньшее (большее) cta ;

lqX ( pta ) и rqX ( pta ) - количество объектов из X, имеющих значение атрибута a, меньшее (большее) cta, и принадлежащих q-му классу решения, где q = 1, …, r(d).

Решающую систему, получаемую в результате дискретизации с использованием множества делений P, обозначим S P. Изложим две теоремы, которые позволят нам вычислить значение WP ( pta1 ), зная WP ( pta ), где pta и pta1 - два последовательных деления атрибута a, WP ( p ) - количество пар объектов, не различимых делениями из P, но различимых делениями из P { p}.

Теорема 1. Пусть множеству X U принадлежит N X ( pta, pta1 ) объектов, значения атрибута a которых лежат в интервале (cta, cta1 ). Тогда:

Теорема 2. Пусть имеется K классов эквивалентности отношения неразличимости решающей таблицы S P : X 1, X 2,..., X K, каждому из которых принадлежит N i ( pta, pta1 ) объектов, значения атрибута a которых лежат в интервале (cta, cta1 ). Тогда Теперь представим шаги нашего алгоритма. Назовем его обобщенным итерационным алгоритмом дискретизации (Generalized Iterative algorithm for Discretization, GID).

Алгоритм GID.

Вход: Непротиворечивая решающая таблица S.

Выход: Субоптимальное множество делений P.

Используемые структуры данных: P – субоптимальное множество делений, L = [IND( AP )] – множество классов эквивалентности отношения неразличимости таблицы S P ; A* - множество возможных делений.

1. P := ; L := {U}; A* := начальное множество делений;

2. Для каждого атрибута a A выполнить:

3. Взять в качестве pmax деление с максимальным значением WP ( p ) среди всех 5. Для всех X L выполнить:

Если pmax разделяет множество X на X1 и X2, то удалить X из L и добавить в L 6. Если все множества в L состоят из объектов, принадлежащих единственному классу решения, то Конец, иначе перейти к шагу 2.

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

На шаге 2 в процессе вычисления числа пар объектов, различимых делением p a (a, c a ), выполняются лишь для тех классов эквивалентности X i, хотя бы один объект которых удовлетворяет условию принадлежности значения атрибута a интервалу ( c a1, c a ). Для одного такого класса эквивалентности будет выполнено 3 r(d)+3 описанных операций. Обозначим это число как. Оно не зависит от количества объектов n и количества атрибутов k. Число таких классов эквивалентности не может превышать числа nj объектов, принадлежащих им и значение атрибута a которых лежит в интервале ( c a1, c a ). Следовательно, при вычислении WP ( p a ) для одного деления p a выполняется не более n j операций. Поэтому в ходе обработки делений всех k атрибутов потребуется kn операций. Второй шаг повторяется |P| раз, а значит, его полная вычислительная сложность составляет O(|P| kn).

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

Поскольку всего имеется n объектов, то за весь алгоритм будет выполнено n-1 операций разбиения. Следовательно, вычислительная сложность пятого шага составляет порядка O(n).

Полная вычислительная сложность предлагаемого алгоритма дискретизации равна O(|P| kn) + O(n) = O(|P| kn), что позволяет применять его для обработки больших массивов данных.

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

1. J. Komorowski, Z. Pawlak, L. Polkowski, A. Skowron. Rough Sets: A Tutorial. In Pal, S. and Skowron, A., editors, Rough Fuzzy Hybridization, pp. 3-98. Springer-Verlag, 1999.

2. S.H. Nguyen, H.S. Nguyen. Some efficient algorithms for rough set methods. In: BouchonMeunier, Delgado, Verdegay, Vila, and Yager, 1996, pp. 1451-1456.

3. J.W. Grzymala-Busse, M. Hu. A Comparison of Several Approaches to Missing Attribute Values in Data Mining. Rough Sets and Current Trends in Computing 2000, pp. 378-385.

РАЗРАБОТКА СИСТЕМЫ УПРАВЛЕНИЯ ПРЕДПРИЯТИЕМ НА ОСНОВЕ

СОВРЕМЕННЫХ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

ENTERPRISE CONTROL SYSTEM DEVELOPMENT ON THE BASIC OF MODERN

INFORMATION SYSTEMS

Аннотация В работе приводится общая концепция автоматизации современного промышленного предприятия и рассматривается модель АСУП, ее модули и решаемые этими модулями задачи. Описывается реализация системы на примере конкретного предприятия. А также решение проблемы контроля технологического цикла с использованием конечных автоматов.

Abstract This article contains general concept of modern industrial enterprise automation as well as a basic model of CAM system with description of its modules and their functions. The main part of the work is dedicated to implementation of the mentioned system by the example of existing enterprise. Besides, a solution of a problem of technology circle control with the use of finite state automaton is given in the article.

На нашем предприятии была реализована и успешно функционирует один из модулей системы автоматического управления производством. Модуль предназначен для автоматического сбора данных и расчета параметров выпускаемой продукции. В состав системы входят:

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

- станции обработки и расчета параметров датчиков, ядром которых являются локальные базы данных (передача данных с испытательных участков реализована - центральный сервер СУБД для архивирования данных.

Система сбора данных и расчетов функционирует следующим образом: датчики испытывают на нескольких температурах, полученные результаты сохраняются в выходные файлы. Так как производственный цикл испытаний имеет продолжительность более одного дня, файлов с испытаниями группы датчиков несколько. Далее файлы передаются на компьютер обработки результатов испытаний. Ядро системы расчета - СУБД Paradox. Таким образом, для параллельной обработки оператору требуется переносить данные на разные машины, следить за их непротиворечивостью и целостностью. Наряду с этим в базе данных Paradox имеются проблемы с индексами при больших размерах базы.

Т. е., при том, что данная система позволяет автоматически снимать данные испытаний и рассчитывать параметры датчиков, она имеет ряд ограничений:

- локальные базы данных не обеспечивают одновременную работу нескольких пользователей, что критично при увеличении объема выпускаемой продукции.

- недостаточная надежность локальных баз требует архивации данных.

- локальные базы не позволяют интегрировать производство и базы данных Для устранения вышеупомянутых недостатков отдел автоматизации нашего предприятия решает следующие задачи:

- модернизация модуля автоматического съема параметров выпускаемых датчиков и расчета их характеристик.

- реализация модуля контроля технологического процесса - интеграция производственной части и бухгалтерии Наиболее рациональным решением по обеспечению корректного доступа к данным нескольких пользователей является реализация базы данных на ядре MS SQL Server.

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

Хранение данных, получаемых с установок системы автоматического съема параметров, решено оставить в файлах, поскольку установки автоматического съема параметров должны работать в независимости от сервера, СУБД или коммуникационного оборудования.

Структуру файлов решено изменить по типу COFF формата исполняемых файлов из-за легкости добавления нового блока данных и наличия контрольной суммы.

Для эффективной реализации данной АСУП наш отдел изучил существующие системы управления предприятием и разработал свою концепцию построения этих систем в рамках нашего производства.

На рисунке 1 представлена упрощенная модель промышленного предприятия. Цифрами обозначены зависимости различных систем модели: