Быстрое Преобразование Фурье, java

Решил я вплотную подступиться к Цифровой Обработке Сигналов.
Достаточно долгое время не мог понять, как реализовать алгоритм БПФ. Математика была понятна, но просмотрев готовые решения, понять как они работают не удавалось. На какое-то время необходимость в этом отпала, а потом снова появилась.
Ко второму заходу опыта программирования стало уже немного большое, и, наверно, поэтому мне удалось самому написать программу, выполняющую БПФ на java (код без особого труда можно портировать на C++ или C).
Я не буду выводить основные формулы и доказывать, что они верны — с этим справляются на многих сайтах и во многих книжках (по крайней мере лично у меня это не вызвало трудностей).
Основные формулы1

Я просто расскажу о том, как пользуясь этими формулами я писал саму программу, с какими трудностями столкнулся и как их преодолел.
Статья, по сути предназначена для тех кто:
1. Прочитал и понял математику, стоящую за БПФ.
2. Понял алгоритм бит-реверса.
3. Понял почему граф преобразования выглядит именно так

Первое, что я сделал — поставил основную задачу «Разработать программу быстрого преобразования Фурье на java». Затем приступил ко второму этапу: сбору информации. Прочитав доказательства и поняв математику, стоявшую за алгоритмом, я понял, следующие вещи:
1. Алгоритм можно спроектировать пользуясь парадигмой Divide and Conquer.
2. В данной парадигме задачу можно решить рекурсивно или итеративно.
Рекурсивный подход, как мне кажется, в какой-то мере проще в написании и понимании, но приведет к некоторым потерям в скорости из-за вложенных вызовов методов (функций).

Напомню или расскажу тем, кто не в курсе, что парадигма Divide and Conquer (Разделяй и Властвуй) сводится к трем общим этапам.
1. Этап разделения задачи на более простые задачи меньшего размера.
2. Этап решения всех этих задач.
3. Этап объединения результатов всех меньших задач в общий результат.

БПФ же можно разбить на три основных этапа:

1. Перестановка входных отсчетов (значений в массиве). Почему это нужно много рассказывать не буду, но в общем, как я понял, это позволяет сэкономить память, т.к. в таком случае не требуется массив для хранения промежуточных результатов и в целом упрощает написание программы.
2. БПФ основано на том факте, что если N = 2^n (т.е. 1,2,4,...,1024...2^n), то N-точечное ДПФ (т.е. количество отсчетов исходных данных равно числу n) можно разбить на два ДПФ размером вдвое меньше (2^(n-1)). В этом и заключается второй этап парадигмы. Мы разбиваем ДПФ, пока не приходим к базовому случаю — ДПФ от двух отсчетов, которое сводится к сложению и вычитанию двух элементов массива.
3. Объединение результатов каждого из разбиений.

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

i — целое число, в котором надо переставить t-битов.

private static int reverse(int i, int t) {
		// TODO Auto-generated method stub
	    int Shift = t - 1;
	    int LowMask = 1;
	    int HighMask = 1 << Shift;
	    int R;
	    for(R = 0; Shift >= 0; LowMask <<= 1, HighMask >>= 1, Shift -= 2)
	        R |= ((i & LowMask) << Shift) | ((i & HighMask) >> Shift);
	    return R;
	}


А это, собственно, перестановка значений.

for(int i = 1; i < Nmax-1; i++)
		{
		    int J = reverse(i,powerOfTwo);           // reverse ����������� ���� � I � �������� �������
		    if (i >= J)                     // ���������� ��� ��������������
		    	continue;
		    double S = array[i]; array[i] = array[J]; array[J] = S;  // ������������ ��������� xI � xJ
		}


Т.е. здесь мы берем число i, переставляя в нем биты, получаем число J. i и J — это индексы двух элементов массива, которые нужно поменять местами. Ну и меняем их местами. Повторяем эту процедуру пока не пройдемся по всем элеметам массива, т.е. пока i не станет больше или равно Nmax-1.

А дальше начинается самое интересное.

*************************************************************
Статья пока недописана, но публикую, т.к. интересуют комментарии. О чем написать подробнее, что может вызывать вопросы и пр. Любые мнения и помощь приветствуются!

Преобразователь интерфейсов (переходник) USB<=>RS485 (ПИ-5)

Смотри также: Преобразователь интерфейсов (переходник) USB-RS485 с гальванической развязкой (ПИ-5б)

Продолжаю цикл заметок «Проекты-малыши»

Решил поделиться с общественностью одной из возможных реализаций преобразователя USB<=>RS485 на базе микросхемы FT232RL:





Читать дальше

Металлорезист ребята.

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


При тентинг-методе периодически «разгерметизировалось» 1-2 отверстий, предположительно чрезмерное прижатие валков в ламинаторе, фоторезист 40мкм.
Регулировать было неохота, да и не могу я когда нет 100% уверенности в процессе, плюс большие отверстия вроде тоже тентинг не держит.
Комбинированный позитивный метод позволяет получать проводники 0,2мм более стабильно и без большого бокового потрава.


Читать дальше

Постройка квадрокоптера шаг за шагом. Делюсь бесценным опытом 2

Доброго времени суток Сообщество.
Хочу поделиться своим опытом постройки летательного аппарата, под названиям "Квадрокоптер". Да тут уже имеется одна статейка о том как товарищ enq строил свой аппарат. Но опыта много не бывает!



Читать дальше

Изготовление двухсторонней печатной платы при помощи пленочного фоторезиста ПНФ-ВЩ

См. также пример работы с фоторезистом ORDYL Alpha 350

В комментариях к заметке про плату-переходник граждане попросили рассказать о том, как я делаю печатные платы с помощью фоторезиста. Несколько подобных просьб пришли также по асе и на электромыло. Хотя я и считаю, что по теме «Изготовление печатных плат в домашних условиях» материала в Интернете и так предостаточно, всё же решил пойти навстречу людям и накропал-таки заметку про фоторезист (файл .pdf, в акробате доступно содержание (букмарки) слева от текста), в ходе которой описал изготовление вот такой вот двухсторонней платы:





Читать дальше

И все-таки оно светится.

Предупреждение: под катом нубство, грамматические и стилистические ошибки.


Читать дальше

Виртуальная машина и скриптовой движок в MSP430G2553 - проще пареной репы. 4e4th + TI Launchpad

Вот и дождался я своего launchpad'a!
Жажда халявы и широкий пеар в узких кругах сделали свое черное дело :)
Ну да ладно, пора к делу.

Итак,

постановка задачи

Дано:
непонятная красненькая плата со штырьками PLS-ок, USB шнурок и… собственно, всё.
Никаких ардуин на компе, никаких иаров, композеров, и даже MspGCC вне досягаемости.

Требуется написать и разместить в памяти контроллера программу, выполняющую какие-либо полезные действия.
С помощью циркуля и линейки, то есть консоли и терминала.
Страшно?!

Возможно, олдфаги мне скажут — «фигня вопрос, мы-то в советские времена ещё и не такое делали». Пожалуй, соглашусь. Было время, рисовал в клетчатой тетради листинги в машинных кодах (!) Z80, а потом забивал в память с помощью простейшего «загрузчика» INPUT-POKE addr-GOTO 10 (ностальжи :)

Однако, отвлекся. Это ещё не все. Определим, что же будет делать наша программа.
Пусть будет джентльменский набор новичка. То есть:

  1. Измерение напряжений на аналоговых входах. Измерение внутренней температуры.
  2. Управление внешними устройствами
  3. Опрос дискретных входов (кнопка S2)
  4. Вывод на индикатор
  5. Форматный вывод в UART
  6. Командный интерфейс через UART

Но и это ещё не всё.

7. Предоставим пользователю возможность переопределять функции по своему усмотрению через тот же терминал, подключенный к UART-у.

Вот теперь всё.


Читать дальше

Тем кто делает свою паяльную станцию - налетай торопись покупай живопись

Недавно осматривая на сайте www.dealextreme.com поступившие новинки заметил следующий товар на момент покупки фотография товара была одна плохая без надписей на товаре, на текущий момент фотографий уже много и соответствуют товару.
Упаковка

Читать дальше

Жала "Hakko" 900М

Затеял я купить себе парочку жал. сначала хотел купить фирменные Hakko, но не нашел, где! тогда решил купить комплект жал на аукционе ebay! Немного побродив по поиску — наткнулся на этот комплект жал!
Piccy.info - Free Image Hosting


Читать дальше

Лабораторный Блок питания - Часть 2

В первой части этой эпопеи обсуждались преимущества и недостатки моего подхода к конструированию блока питания. Спасибо всем за советы, особенно Vga . Его советы направили мои мысли в правильном направлении и в результате получен некий результат.
UPD:Добавил осцилограммы!
UPD2:Боролся с самовозбуждением. Счет пока 1:1 ))).


Читать дальше