WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 | 2 || 4 | 5 |   ...   | 14 |

Особенности выполнения преобразования Фурье Для того чтобы получить достаточную для определения басовых полутонов частотную разрешающую способность при преобразовании Фурье, количество исходных элементов должно быть приблизительно равно 8192. Ввиду того что подавляющее большинство музыкальных композиций в цифровом формате распространяется с частотой сэмплирования 44 100 Гц, исходный массив будет отражать промежуток в 1/5 секунды. Данный временной интервал является неприемлемо большим, поскольку в него могут попасть звуки, которые в данный момент не слышны. Во избежание этого в исходный массив заносится меньшее колиСборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ чество элементов, а остальная часть массива дополняется нулями. Подобный метод несколько изменяет результаты преобразования, но на практике это оказалось некритичным.

Преобразование Фурье является трудоемкой операцией, однако относительно небольшой размер массива исходных данных и скорость функционирования библиотеки FFTW позволяют выполнять его с намного большей скоростью, чем требуется. Фактически на компьютере устаревшей конфигурации полный цикл аудиовизуализации при проверке выполнялся около 400 раз в секунду, в то время как теоретически необходимо всего 24 раза в секунду, чтобы можно обновлять изображение в соответствии с воспринимаемой человеческим глазом частотой обновления кадров. На практике частота обновления изображения равна 12 кадрам в секунду ввиду архитектурного ограничения аппаратной части. Для формирования эстетически приятного визуального ряда достаточно и такого небольшого значения, однако внимательный зритель может заметить, что некоторые ноты визуализируются с некоторой задержкой.

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

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

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

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

ЛИТЕРАТУРА 1. Frigo M., Johnson S. FFTW User's Manual, 2003 [Электронный ресурс]: .

2. История развития учения о цвете, 2011 [Электронный ресурс]: .

Сборник трудов молодых ученых и сотрудников кафедры ВТ 20 ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ 3. Способин И. В. Элементарная теория музыки: Учебник для музыкальных учебных заведений. М.: Гос. музыкальное изд-во, 1963. 202 с.

4. Puckette M. The Theory and Technique of Electronic Music, 2006 [Электронный ресурс]:

.

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

E-mail: mikhail.avkhimenia@gmail.com Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ УДК 621.3.АЛГОРИТМ ГЕНЕРАЦИИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЕ БРЕЙНА И. Д. Захаров Предложен алгоритм формирования последовательностей де Брейна заданной степени на основе одноименных графов, который может быть положен в основу построения кодированных масок цифровых преобразователей угла.

Ключевые слова: кодовая шкала, последовательность де Брейна.

Введение В работе [1] рассмотрены псевдослучайные кодовые шкалы (ПСКШ), которые строятся с применением линейных рекуррентных двоичных последовательностей (ЛРП) и имеют одну информационную кодовую дорожку (КД). В качестве ЛРП, используемой для построения кодирующих масок ПСКШ, применяются псевдослучайные двоичные последовательности максимального периода (М-последовательности). Традиционно псевдослучайные двоичные последовательности максимального периода используются в навигационных системах, системах связи и системах криптографической защиты информации.



Число М-последовательностей NM =(M ) / n, где (M ) — функция Эйлера, M = 2n -1, а n — степень примитивного полинома, положенного в основу построения Мпоследовательности. В свою очередь, число М-последовательностей определяет множество разнообразных кодирующих масок ПСКШ.

В статье [2] приведены принципы построения псевдорегулярных кодовых шкал (ПРКШ). Такие шкалы строятся на основе нелинейных рекуррентных двоичных последовательностей (НРП) и имеют две информационные КД. Применяемые в ПРКШ нелинейные рекуррентные последовательности строятся на основе ЛРП, число которых равно числу Мпоследовательностей.

Известны двоичные последовательности де Брейна [3], число которых для заданного n-значения n NDB = 22 -n. В таблице приведено число М-последовательностей и последовательностей де Брейна для различных значений n.

n NM NDB 2 1 3 2 4 2 5 6 … 10 60 Анализ таблицы показывает, что последовательностей де Брейна несоизмеримо больше по сравнению с М-последовательностями, что при одинаковом значении n дает дополнительные возможности для построения кодирующих масок ПРКШ.

Из работ [4, 5] известны алгебраические алгоритмы нахождения последовательностей де Брейна определенной степени, однако они либо не дают их полного множества, либо малоэффективны и ресурсоемки. В настоящей работе рассмотрен быстрый и легко адаптируемый под вычислительную технику алгоритм получения полного множества последовательностей де Брейна для заданного значения n.

Сборник трудов молодых ученых и сотрудников кафедры ВТ 22 ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ Описание алгоритма Одним из представлений последовательностей де Брейна являются одноименные графы.

Это направленные графы, в вершинах которых находятся все возможные слова длины n, составленные из заданного алфавита (для двоичного алфавита — всего 2n вершин). Пример графа де Брейна для n=3 приведен на рисунке.

Визуальная интерпретация графа де Брейна весьма наглядна для восприятия, однако на практике в алгоритмах чаще всего используется матрица смежности. Квадратная матрица A размерности 2n2n называется матрицей смежности графа де Брейна степени n, когда каждый ее элемент отражает наличие связи между соответствующими вершинами. Между двумя вершинами графа x=(x0,…,xn-1) и y=(y0,…,yn-1) есть направленная связь xy тогда и только тогда, когда xi=yi+1; i=0,…,n–2.

vv4 v100 vvvv110 vТак, например, если элемент aij матрицы A равен единице, значит, есть ребро от вершины vi в вершину v, иначе направленной связи между вершинами нет. Матрица j смежности графа де Брейна для n=3 приведена ниже.

0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 A3 = 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 Алгоритм состоит из двух этапов. На первом этапе формируется матрица смежности соответствующего графа де Брейна, а на втором этапе по полученной матрице смежности находятся собственно последовательности.

Первый этап алгоритма (заполнение матрицы смежности A) можно представить следующим образом (n=3).

Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ 1. Сформировать маску слова (mask) длины n mask := 2. Для каждой вершины i Например, i = 6 : v6 = (110) — Сдвинуть значение слова вершины на один разряд влево 1 1 1 1 0 — Получить значение индекса j, поразрядно умножив полученное на предыдущем шаге 1 1 0 слово на маску из шага & 0 1 1 1 0 — Значение j, полученное на предыдущем шаге, 1 0 j = записать в матрицу смежности в виде aij = a6, 4 = — Записать в матрицу смежности значение j + j +1 = в виде ai, j+1 = a6, 5 = 3. Обнулить элементы матрицы смежности a0,0 = a0,0 = 0 и a2 -1,2 -1 = n n a7,7 = Второй этап алгоритма представляет собой рекурсивную процедуру над строкой i матрицы смежности A, полученной ранее. Он может быть представлен следующим образом.

Для каждого столбца j строки i 1. Если aij=— Добавить i в выходную последовательность — Обнулить строку i — Обнулить столбец i — Обнулить столбец j — Перейти на строку j, запустив данную процедуру для нее 2. Иначе (если в строке не осталось единиц) — Сохранить выходную последовательность, если ее длина равна 2n — Перейти на предыдущий уровень рекурсии Выполнив данный алгоритм для n=3 на основе матрицы смежности A, получим следующие результаты:

result1 = {1,2,5,3,7,6,4,0}; result2 = {1,3,7,6,5,2,4,0}.

Осуществив деление по модулю 2 десятичных чисел, для всех полученных результатов найдем искомые двоичные последовательности де Брейна для n= 3:

result1 = {1,2,5,3,7,6,4,0} 10111000 ;

result2 = {1,3,7,6,5,2,4,0} 11101000.

Полученные последовательности могут быть использованы при построении кодирующих масок ПРКШ, методы синтеза которых подробно рассмотрены в статье [2].

Заключение Преимущество рассмотренного алгоритма в сравнении с аналогами заключается в относительной простоте и возможности использования промежуточных результатов.

Сборник трудов молодых ученых и сотрудников кафедры ВТ 24 ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ЛИТЕРАТУРА 1. Ожиганов А. А. Псевдослучайные кодовые шкалы // Изв. вузов. Пpибоpостроение. 1987.

Т. 30, № 2. С. 40—43.

2. Ожиганов А. А., Прибыткин П. А. Псевдорегулярные кодовые шкалы для цифровых преобразователей угла // Науч.-техн. вестн. СПбГУ ИТМО. 2011. № 1 (71). С. 67—72.

3. De Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v.

Wetenschappen. 1946. Bd 49. S. 758—764.





4. Lempel A. On a Homomorphism of the de Bruijn Graph and Its Applications to the Design of Feedback Shift Registers // IEEE Transactions on Computers. 1970. Vol. C-19, N 12. P. 1204— 1209.

5. Abbas M. A. A simple combinatorial algorithm for de Bruijn sequences // The American Mathematical Monthly. 2010. Vol. 117, N 8. October. P. 728—732.

Сведения об авторе Захаров Илья Дмитриевич — аспирант; Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, кафедра вычислительной техники; E-mail: zakharov_ilya@hotmail.com Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ УДК 004.АНАЛИЗ РЕАЛИЗАЦИЙ ФАЙЛОВЫХ СИСТЕМ В АДРЕСНОМ ПРОСТРАНСТВЕ ПРИЛОЖЕНИЙ Е. Ю. Иванов, Б. Д. Тимченко Рассмотрены вопросы структурной организации операционных систем при выполнении кода файловых систем в адресном пространстве приложений. Рассмотрены перспективы перехода к системам данного типа.

Ключевые слова: операционные системы, файловые системы, микроядро, Linux FUSE, NetBSD Rump, MINIX 3.

Введение В последние годы в исследовательских работах по операционным системам (ОС) заметен рост интереса к вопросам их организации. Предпосылки к этому существовали, собственно, еще со времени появления в середине 1960-х гг. первых полноценных ОС с монолитными, т. е. слабоструктурированными, ядрами. Классическим примером может служить OS/360, имевшая первоначально фактически одноуровневое ядро. При создании и последующем развитии таких ОС выявились острые проблемы тестирования, модификаций, поддержки и самое главное — надежности функционирования. В структуре UNIX и в иерархической организации, присущей последующим системам, были достигнуты значительные успехи. Дальнейший пересмотр архитектуры часто связывают с Mach OS, считающейся началом движения к микроядерной структуре [1]. Ключевым в этой концепции является создание ОС с компактным, по сути монолитным, ядром, и реализация основного функционала в форме системных процессов, работающих в режиме приложений.

Считается, что переход к микроядерной структуре обеспечивает такие высокоуровневые требования, как переносимость, унификация интерфейсов, надежность и ряд других [2].

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

Авторами настоящей статьи проведена оценка основных подходов к разработке ФС, работающих вне ядер ОС, предложена общая нотация для представления их организации и изучены перспективы развития. В выводах использован также опыт, полученный одним из соавторов при реализации проекта FUSE для MINIX 3 в университете Амстердама (Нидерланды), выполнявшегося под руководством Томаса Веермана.

Файловые системы в адресном пространстве пользователя Можно выделить следующие файловые системы:

— специально разработанные для микроядерных операционных систем, таких как MINIX 3, GNU HURD и L4. Благодаря наличию поддержки взаимодействия модулей, такие ФС, часто в контексте микроядра называемые «истинными» (native), обладают наибольшей производительностью и реализуются значительно проще;

— работающие в АПП в операционных системах с монолитным ядром. Такие ФС используют специальные модули ядра, которые обеспечивают интерфейс взаимодействия системы с различными подсистемами ядра, в частности с виртуальной файловой системой (VFS) и низкоуровневым вводом—выводом. Например, такой подход применяется в Linux FUSE (Filesystem in Userspace) и в NetBSD PUFFS (Pass-to-Userspace Framework File System);

Сборник трудов молодых ученых и сотрудников кафедры ВТ 26 ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ — код которых выполняется в АПП без модификаций посредством использования специальных механизмов. Это сравнительно новый подход, достоинством которого является возможность использовать десятки хорошо отлаженных реализаций файловых систем. На сегодняшний день единственной значимой реализацией является NetBSD Rump [3];

— реализованные для FUSE, но перенесенные (портированные) в микроядерные системы. Примером служит поддержка FUSE в MINIX 3.

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

Linux FUSE Linux FUSE на сегодняшний день является наиболее распространенным фреймворком для реализации файловых систем в АПП [4]. Под FUSE работает значительное число ФС:

NTFS, ext2, FAT и др. Кроме того, FUSE доступен во многих операционных системах:

FreeBSD, NetBSD, Mac OS и MINIX 3. Благодаря этому одна и та же реализация ФС, например fuse-ntfs-3g, работает во всех перечисленных выше системах.

В Linux FUSE имеет следующую структуру:

1) модуль ядра, отвечающий за взаимодействие с VFS и ввод—вывод;

Pages:     | 1 | 2 || 4 | 5 |   ...   | 14 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.