Форум разработчиков электроники ELECTRONIX.ru

Огурцов

Oct 21 2008, 21:06

Цитата(defunct @ Oct 21 2008, 20:34)

9/2 = 4.5! это только умножение!

Ок, вот вам объективная граница одного порядка - sqrt(10) ~ 3.16 - одинаково далеко отстоит как от единицы, так и от десятки. Для двух порядков, соответственно ~31.6 снизу и ~316 сверху.

Цитата(defunct @ Oct 21 2008, 20:34)

про большинство остальных операций уже упоминалась разница - ровно в 2 раза.

Ну да. Мы еще про деление не говорили. И как-то про 32-разрядное умножение больше не вспоминаем.
А если какой-нибудь sin(x)/x по ходу потребуется - на половине работы камень менять ? Нет уж, лучше перезаложиться, а потом, после решения, оптимизировать, чем сначала мучительно оптимизировать и таки не вписаться. Нет, но я не исключаю, что повезет и AVR хватит.

Цитата(defunct @ Oct 21 2008, 20:34)

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

Жаль. А у меня кодеки на 8kHz без дела валяюцо - как раз для умного выключателя. В сортир. Ну разве что только самому монопольно пользоваться )

Цитата(defunct @ Oct 21 2008, 20:34)

Есть над чем подумать. Метод наименьших квадратов - ресурсоемкий, конечно можно начать с него.

~~Если~~ нужно привести результирующие данные к одному байту, тогда ~~квадрат~~ умножение не страшно. У нас 2500 тактов на семпл и два такта погоды не сделают - в остальных местах затыки ожидаются посерьезней.
Вообще, м.б. нейросеть ? НС по словарю очень хорошо работает.

Petka

Oct 21 2008, 21:20

Цитата(Огурцов @ Oct 22 2008, 01:06)

Ок, вот вам объективная граница одного порядка - sqrt(10) ~ 3.16 - одинаково далеко отстоит как от единицы, так и от десятки. Для двух порядков, соответственно ~31.6 снизу и ~316 сверху.
Ну да. Мы еще про деление не говорили. И как-то про 32-разрядное умножение больше не вспоминаем.
А если какой-нибудь sin(x)/x по ходу потребуется - на половине работы камень менять ? Нет уж, лучше перезаложиться.

1. За оценку слова "порядок"

примерно так себе и представлял.
2. А вот почему Вам нужны именно 32битные операции? почему не 64? почему не 128? 256? а вдруг и 1024 бит не хватит? Для задачи "совпало - не совпало" обычно на выходе надо получать результат не точнее 1%. А это всего 7 бит конечной точности... Как раз по зубам AVR'ке. Другое дело что-бы получить результат точностью 7 бит надо хорошенько пошевелить мозгами над алгоритмом, который из пачки 8 битных значений делает одно 8битное. Глупо считать 32битное DCT, что-бы потом округлить его результат до 8бит. Однако сейчас жизнь такая, что проще поставить "DSP на выключатель". И дешевле (экономия на толковых программистах).

defunct

Oct 21 2008, 21:21

Цитата(Огурцов @ Oct 22 2008, 00:06)

Ок, вот вам объективная граница одного порядка - sqrt(10) ~ 3.16 - одинаково далеко отстоит как от единицы, так и от десятки. Для двух порядков, соответственно ~31.6 снизу и ~316 сверху.

ЗачОт!

Давайте тогда для двух порядков сделаем sqrt(100) будет 10.
Предлагаю не изобретать новых сущностей - на порядок это в 10 раз, и 16 битные операнды не замедлят вычисления на порядок.

Цитата

Ну да. Мы еще про деление не говорили. И как-то про 32-разрядное умножение больше не вспоминаем.

это не нужно.

Цитата

Нет уж, лучше перезаложиться, а потом, после решения, оптимизировать, чем сначала мучительно оптимизировать и таки не вписаться. Нет, но я не исключаю, что повезет и AVR хватит.

Неспортивно. Даже для ARM'а эту задачу уже неинтересно рассматривать, т.к. уже есть рабочие решения. К тому же мы хотим просто оценить - сможет/не сможет конкретно AVR.

Цитата

Жаль. А у меня кодеки на 8kHz без дела валяюцо - как раз для умного выключателя. В сортир. Ну разве что только самому монопольно пользоваться )

А что мешает эти же кодеки пользовать с Fd 3.2? ;>

Цитата

Вообще, м.б. нейросеть ? НС по словарю очень хорошо работает.

Вы серьезно? Реально НС в AVR уложить?

Огурцов

Oct 21 2008, 21:49

Цитата(Petka @ Oct 21 2008, 21:20)

2. А вот почему Вам нужны именно 32битные операции?

Не мне - см. выше. Я говорил про 16x

Цитата(Petka @ Oct 21 2008, 21:20)

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

См. выше - про и был первый пост. Про цену труда даже говорить не приходится. А про цены на камни я сказал - цена одного порядка (с)

Но кстати, я подумал некоторое время назад - даже при одинаковой цене какой-нибудь восьминогий AVR выигрывает, например, в том же выключателе (только не с голоса) - он будет горадо более надежен ввиду низкой тактовой, чем ARM на 200MHz с 200 ногами.

Цитата(defunct @ Oct 21 2008, 21:21)

на порядок это в 10 раз

В природе чаще встречаются дробные величины.

Цитата(defunct @ Oct 21 2008, 21:21)

Неспортивно. Даже для ARM'а эту задачу уже неинтересно рассматривать, т.к. уже есть рабочие решения.

Так зачем искать решение, если оно существует ? (с)

Цитата(defunct @ Oct 21 2008, 21:21)

Вы серьезно? Реально НС в AVR уложить?

Не вопрос, если сможете FFT уложить, так и НС уложится. Более того, настроенную под конкретный словарь НС можно будет развернуть (на PC) в код, который и выполнять на AVR - будет на порядок (с) быстрее, чем работать с данными описывающими НС. Кроме того, на большом словаре наименьшие квадраты и разные другие последовательные алгоритмы будут существенно тормозить, в отличие от параллельной НС. В смысле параллельного поиска решения конечно, а не выполнения инструкций проца.

Rst7

Oct 22 2008, 05:14

Цитата

Думаю возможно, но это будет FCT.

Ну в смысле Fast DCT? Слово Fast даже не обсуждается

Цитата

Глупо считать 32битное DCT

Конечно, никто 32 бита не будет использовать. Видимо, будет 10 бит с гвардом в остальные 6. Это я сегодня покручу.

Цитата

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

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

blackfin

Oct 22 2008, 05:41

Цитата(Rst7 @ Oct 22 2008, 09:14)

Ну в смысле Fast DCT? Слово Fast даже не обсуждается

Кстати, на заметку - blackfin делает Fast DCT для матрицы из 8*8 16-битных чисел за ~300 тактов CPU.

Rst7

Oct 22 2008, 06:27

Цитата

blackfin ... за ~300 тактов CPU.

AVR - больше чем за 3000.

Про DCT32. По быстрому скомпилил, без особой оптимизации. 16тибитный dct32 выходит в 4264 такта. Но там еще править и править, до оптимальности далеко...

Rst7

Oct 22 2008, 08:09

Цитата

3. Для каждой выборки считать FFT в real-time и сравнивать с 25-ю эталонными спектрами.

Слушайте, а мы наверное один момент упустили. После FFT надо получить мощности на каждой частоте, т.е. sqrt(I*I+Q*Q), я прав?

DRUID3

Oct 22 2008, 08:17

Цитата(ATLab @ Oct 19 2008, 04:34)

Ой, ну автор насмешил! На PC эта хрень толком не работает, а он на АВР-ке собрался...

AVRка дает достаточно MIPS 8bit для таких задач...

Цитата(ATLab @ Oct 19 2008, 04:34)

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

Мой совет - поставьте такие мозги на полку... Они не пригодяЦЦо...

А по-делу - если поделить один отсчет функции корреляции на отсчет образованный произведением корней из суммы квадратов корней эталонной и исследуемых функций на интервале(по сути модулей векторов) - получим значение корреляции не зависящее от амплитуды, а лишь от формы функции, и лежащее в интервале [0..1] - т.н. коэффициент корреляции.

Цитата(defunct @ Oct 19 2008, 07:46)

PS: Кстати для DTMF детекта FFT избыточно.

При наличии помех - не так уж...

Цитата(defunct @ Oct 19 2008, 07:46)

Это зависит от метода сравнения. В моем случае 20% - это много.
Грубо не вдаваясь в детали - представим, что спектр входного сигнала отмасштабирован так, что интеграл разности спекторв входного сигнала и эталонного на отрезке от 0 до Fd будет минимальным. Полное совпадение - когда интеграл равен 0. Полное несовпадение - равен X.
20% подобия соотв. - 0.8*X.

Нет уж, вдайтесь в детали. Я тоже занимался таким-же(искал корреляцию через RealFFT), но совсем не так!

И что-то мне подсказывает - Вы не на верном пути...

Цитата(=GM= @ Oct 20 2008, 15:25)

Прошу простить джентльмены, что прерываю вашу высокоучёную беседу(:-), заинтересовало сравнение авр с арм

Неужто 8-битный авр и 32-битный арм различается всего в два раза? Что-то мне сомнительно, хотя Rst7 вроде можно доверять, э?(:-)

А вот интересно, во сколько раз будет разница между 8-битной авр и 32-битным дсп TMS320F2808 на команде, скажем, dmac, которая за один такт перемножает два первых знаковых 16-битных числа, лежащих в памяти, и добавляет это произведение к 32-битному аккмулятору АСС, и в том же такте также делает со вторыми знаковыми 16-битными числами, добавляя результат к 32-битному регистру Р?

Я понимаю, что по-хорошему надо бы написать пгм и посчитать такты, но может у кого-нибудь уже есть двойной МАС для авр?

Блин, что за глупое радиолюбительское хвастовство!?

Поставлена задача. Для AVR она реализуема и точка. К чему этот треп у кого что длинее? Давайте еще SHARC вспомним.

Цитата(zltigo @ Oct 20 2008, 17:49)

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

В этом вопросе Вы ошибаетесь...

P.S.:Кстати, хочу напомнить новичкам, что вейвлеты считаются не в пример быстрее чем FFT! просто вся классика ЦОС либо написана до широкого их развития либо с радиотехническим "уклоном" - а там применение Фурье неизбежно в любом случае ибо частотный ресурс распределяется именно с помощью этого преобразования...

Petka

Oct 22 2008, 08:47

Цитата(Rst7 @ Oct 22 2008, 09:14)

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

Очень спорно. Пример: в оптических мышах используется DSP. Крупные серии позволяют делать масочные бескорпусные DSP "на заказ" при копеечной стоимости (оптические мышки в которых контроллер не самое главное стоят по 150р уже для конечного потребителя и в которых стоимость электроники не основное). Кроме того сделать "дешевле" это задача "китайцев". А у нас есть шанс конкурировать только в высоких технологиях, интеграции, качестве, инновациях.

Цитата(Rst7 @ Oct 22 2008, 12:09)

Слушайте, а мы наверное один момент упустили. После FFT надо получить мощности на каждой частоте, т.е. sqrt(I*I+Q*Q), я прав?

Абсолютно прав. правда sqrt можно не считать. (потом всё-равно в квадрат возводить)

Rst7

Oct 22 2008, 08:51

Цитата

Абсолютно прав.

Я бы, конечно, предпочел ответ от defunct'а. Но если так, то, видимо, DCT пролетает как фанера, из него нельзя получить спектр мощности.

DRUID3

Oct 22 2008, 09:03

Цитата(Rst7 @ Oct 22 2008, 11:51)

Я бы, конечно, предпочел ответ от defunct'а. Но если так, то, видимо, DCT пролетает как фанера, из него нельзя получить спектр мощности.

а зачем Вам спектр мощности? Вы сравниваете силу голоса?

P.S.: аФФтара харош бредить, я признаю ваши(всех) заслуги в других областях, но вы очень сбиваете новичков такими "интеллектуальными забавами".

...частот от 400 до 2400 уже будет достаточно для распознавания (а распознавания команд и того уже). Женский и мужской голос разно тембрально окрашены внутри этого диапазона.

...FFT на 32 точки при 8 ksps распознает фонемы что-ли?

...более-менее приемущества FFT при быстрой одномерной свертке ощущаются начиная с 128 отсчетов. На 32 выгоднее написать FIR в лоб, причем это и на asm элементарно.

Petka

Oct 22 2008, 09:09

Цитата(Rst7 @ Oct 22 2008, 12:51)

Я бы, конечно, предпочел ответ от defunct'а. Но если так, то, видимо, DCT пролетает как фанера, из него нельзя получить спектр мощности.

Ну так категорично тоже нельзя =) Если немного применить мозг DCT тоже годится, только надо его "нетривиально использовать". Всё разжёвывать не буду, подскажу только идею: DCT пренобразовывает в базисы косинусов. т.е. не хватает только второй составляющей Фурье - синусов. Далее: sin(x) = cos(x - pi/2).
ИМХО всё-таки FFT получится проще и быстрее.

DRUID3

Oct 22 2008, 09:14

Цитата(Petka @ Oct 22 2008, 12:09)

Ну так категорично тоже нельзя =) Если немного применить мозг DCT тоже годится, только надо его "нетривиально использовать". Всё разжёвывать не буду, подскажу только идею: DCT пренобразовывает в базисы косинусов. т.е. не хватает только второй составляющей Фурье - синусов. Далее: sin(x) = cos(x - pi/2).
ИМХО всё-таки FFT получится проще и быстрее.

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

Rst7

Oct 22 2008, 09:45

Цитата

а зачем Вам спектр мощности?

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

Давайте все-же подождем defunct'а, пусть он уточнит данные моменты.

Цитата

...частот от 400 до 2400 уже будет достаточно для распознавания (а распознавания команд и того уже).

А возражений и нет. Только у нас границы 50-1600...

Цитата

Ну так категорично тоже нельзя =)

Можно. Как Вы себе видите получить вторую половину спектра? Ту, которая синусная.

Цитата

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

Думать можно что угодно. Вопрос в том, будет ли это оптимальной реализацией?

defunct

Oct 22 2008, 15:38

Цитата(Rst7 @ Oct 22 2008, 11:09)

Слушайте, а мы наверное один момент упустили. После FFT надо получить мощности на каждой частоте, т.е. sqrt(I*I+Q*Q), я прав?

Обязательно! Только я не думаю, что мы упустили этот момент, это предполагалось как само собой разумеющееся.

Цитата

Но если так, то, видимо, DCT пролетает как фанера, из него нельзя получить спектр мощности.

Не совсем, просто это отразится на методе сравнения - придется подстроиться под попугаи.

Цитата(DRUID3 @ Oct 22 2008, 11:17)

Я тоже занимался таким-же(искал корреляцию через RealFFT), но совсем не так!

И что-то мне подсказывает - Вы не на верном пути...

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

Rst7

Oct 22 2008, 15:51

Цитата

Не совсем, просто это отразится на методе сравнения

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

Но то фигня. Я почти сделал быстрый Хартли - то что доктор прописал - никаких мнимых чисел. Завтра доделаю, посмотрим по тактам. Кстати, DCT я дооптимайзил до "меньше 3000", и это еще не конец.

Огурцов

Oct 22 2008, 19:23

Можно я еще встряну ? Вы о каких герцах говорите, о звуке или о частоте преобразования ? Кодек на 8кгц дает полосу до 3кгц, но у него _встроенный_крутой_ фильтр. Если делать то же самое, но на рассыпухе и иметь на входе 1,6кгц, то частота преобразования может оказаться даже выше 8кгц, если не сказать намного выше. И кроме того, пусть высокий женский голос, максимум - 1кгц, но в речи присутсвуют шипящие, звенящие и разные другие звуки, и если урезать полосу ниже 3кгц, скажем пусть 1.6, я думаю, все эти звуки будут сильно искажены. И результат тоже.
Если же быстродействия для обработки 8 килосэмплов не хватит (как на практике показали выше, AVR должна работать в 10 раз быстрее BF ))))) ) можно разделить обработку на несколько корпусов, не в смысле параллельно, а в смысле последователно - в одном, например, делать FFT, в другом искать фонемы, в третьем искать команды. А четвертый будет уже лампочку включать.

Rst7

Oct 23 2008, 10:22

Цитата

Можно я еще встряну ?

Конечно нельзя, что за вопрос! Шютка

Теперь по теме. Сделал я БПХ необходимого размера. 1948 тактов, 1648 байт кода. Что дальше делаем? Получение спектра мощности, его нормирование и поиск ближайшего в заранее заготовленных?

Кстати, для мощности ведь будет только 16 значений, а не 32.

defunct

Oct 23 2008, 11:16

Цитата(Rst7 @ Oct 23 2008, 13:22)

Теперь по теме. Сделал я БПХ необходимого размера. 1948 тактов, 1648 байт кода. Что дальше делаем? Получение спектра мощности, его нормирование и поиск ближайшего в заранее заготовленных?

Да, в заренее заготовленные кстати не забываем положить спектр белого шума, спектр тишины.

Цитата

Кстати, для мощности ведь будет только 16 значений, а не 32.

15 - нижнюю полосу спектра (постоянная составляющая и 50hz фон) можно сразу выбросить.

Rst7

Oct 23 2008, 11:38

Цитата

Да, в заренее заготовленные кстати не забываем положить спектр белого шума, спектр тишины.

все мощности равны максимальной?

Цитата

15

Да, конечно, эта полоса нас не интересует.

Ну и поделитесь уже заготовками (в смысле, готовыми образцовыми спектрами)...

Огурцов

Oct 23 2008, 11:42

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

зы: вспомнил кое-что из буйной молодости. БПФ можно делать не на синусах, а на меандре, т.о. умножения заменяются на сложения/вычитания. ДПФ, по всей видимости, тоже. И это будет выигрыш на порядок. На тот, который проиграли перед этим.

Rst7

Oct 23 2008, 12:01

Цитата

И это будет выигрыш на порядок.

Ну покажите мастерство. 2000 тактов в Вашем распоряжении. Итого, мы хотим увидеть 200.

Rst7

Oct 23 2008, 13:19

Ну что, вычисление мощностей с нормированием - это плюс 3200 тактов. Там, конечно, можно с бубном поплясать, но особо меньше не будет.

Итого пока 5200 тактов. На очереди - сравнение.

Огурцов

Oct 23 2008, 13:38

Цитата(Rst7 @ Oct 23 2008, 12:01)

Ну покажите мастерство. 2000 тактов в Вашем распоряжении. Итого, мы хотим увидеть 200.

Ну эта...я пока еще за вами подсматриваю - самому становиться Александром Матросовым что-то не очень хочется.
А если по существу, тема в общем, мне интересная, но как я уже говорил, сначала хотелось бы видеть задчау решенной, а только после заниматься оптимизацией, в т.ч. загонять такты в AVR. Или еще куда.
А пока вот выкопал из хлама микрофон, нашел рабочие исходники для С# по работе с wavein/waveout (для Delphi я сам когда-то написал, спектроанализатор в т.ч., но Delphi сейчас нет, а переписывать было лениво) - жду когда здесь что-то вменяемое появится, чтобы помоделировать.

Rst7

Oct 23 2008, 13:45

Цитата

Ну эта...

Ну то. Так что, слабо? Давайте, Вы нас тут учили, что такое порядок, вот теперь и покажите его в живую.

Огурцов

Oct 23 2008, 13:50

Цитата(Rst7 @ Oct 23 2008, 13:19)

Ну что, вычисление мощностей с нормированием - это плюс 3200 тактов.

Не понимаю, как вы считаете. Если даже преположить, что после, например, ДПФ будет два слова на выборку вместо одного, то мощность - это два умножения и сложение, т.е. где-то 5 тактов без пересылок для 8 бит, ну или 50 для 16 бит. Нормаирование - одно сравнение и одно умножение. Пусть еще столько же. Как удалось увличить эту цифру в 30 раз ?

Цитата(Rst7 @ Oct 23 2008, 13:45)

Так что, слабо?

На слабо меня не взять. А вот перспективной идеей - можно.

Так что там, есть уже какие наработки ? Или выложить слабо (с) ?

blackfin

Oct 23 2008, 13:51

Цитата(Огурцов @ Oct 23 2008, 17:38)

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

Врачи, как известно, делятся на три категории:

1. Терапевты, - всё обо всём знают, но ничего не умеют..
2. Хирурги, - ничего решительно не знают, но всё умеют..
3. Патологоанатомы, - всё знают и всё умеют, но приходят слишком поздно..

Вы, как я понимаю, "Терапевт"?

Огурцов

Oct 23 2008, 13:59

Если из этих трех - патологоанатом. Наблюдающий.

defunct

Oct 23 2008, 15:07

Цитата(Rst7 @ Oct 23 2008, 14:38)

все мощности равны максимальной?

угу

Цитата

Ну и поделитесь уже заготовками (в смысле, готовыми образцовыми спектрами)...

Попробую поделиться на выходных... (раньше никак

)

Rst7

Oct 23 2008, 18:20

Цитата(Огурцов @ Oct 23 2008, 16:50)

Не понимаю, как вы считаете. Если даже преположить, что после, например, ДПФ будет два слова на выборку вместо одного, то мощность - это два умножения и сложение, т.е. где-то 5 тактов без пересылок для 8 бит, ну или 50 для 16 бит. Нормаирование - одно сравнение и одно умножение. Пусть еще столько же. Как удалось увличить эту цифру в 30 раз ?

Я не считаю. Это результат замера. А вот как Вам удалось получить "30 раз" я не знаю. Даже Ваша прикидка дает (50+50)*15=1500, и еще там одно деление 32 на 32, это 500 тактов, грубо говоря, и еще 15 квадратных корней, у меня получилось 56*15=840.

Итого, 3340, даже больше, чем мой код

Другое дело, там прилично накладных расходов в связи с тем, что данные для каждой частоты расположены на выходе ДПХ не очень удачно для простой обработки. Но это, я думаю, можно будет устранить. Однако, больших чудес ждать не приходится. Ну и с другой стороны, эта часть кода имеет сложность O(n), так что если вдруг будем увеличивать количество точек, общий вес этой части уменьшится.

Цитата

На слабо меня не взять. А вот перспективной идеей - можно.

Зачем Вам идеи? Вы же все знаете и все умеете?

Цитата

Так что там, есть уже какие наработки ? Или выложить слабо (с) ?

Уже готовитесь спереть? Пока выложить могу только эти две функции. Они Вам нужны?

Огурцов

Oct 23 2008, 19:14

8x

Код

:           C = A * A + B * B;
+00000069:   0288        MULS    R24,R24          Multiply signed
+0000006A:   0190        MOVW    R18,R0           Copy register pair
+0000006B:   2411        CLR     R1               Clear Register
+0000006C:   01C9        MOVW    R24,R18          Copy register pair
13:       }
+0000006D:   0F82        ADD     R24,R18          Add without carry
+0000006E:   1F93        ADC     R25,R19          Add with carry

Я насчитал 7

16x

Код

          C = A * A + B * B;
+00000069:   2744        CLR     R20              Clear Register
+0000006A:   FD37        SBRC    R19,7            Skip if bit in register cleared
+0000006B:   9540        COM     R20              One's complement
+0000006C:   2F54        MOV     R21,R20          Copy register
+0000006D:   01CA        MOVW    R24,R20          Copy register pair
+0000006E:   01B9        MOVW    R22,R18          Copy register pair
+0000006F:   940E0085    CALL    0x00000085       Call subroutine
+00000071:   017B        MOVW    R14,R22          Copy register pair
+00000072:   018C        MOVW    R16,R24          Copy register pair
+00000073:   019E        MOVW    R18,R28          Copy register pair
+00000074:   2744        CLR     R20              Clear Register
+00000075:   FD37        SBRC    R19,7            Skip if bit in register cleared
+00000076:   9540        COM     R20              One's complement
+00000077:   2F54        MOV     R21,R20          Copy register
+00000078:   01CA        MOVW    R24,R20          Copy register pair
+00000079:   01B9        MOVW    R22,R18          Copy register pair
+0000007A:   940E0085    CALL    0x00000085       Call subroutine
+0000007C:   01DC        MOVW    R26,R24          Copy register pair
+0000007D:   01CB        MOVW    R24,R22          Copy register pair
+0000007E:   0EE8        ADD     R14,R24          Add without carry
+0000007F:   1EF9        ADC     R15,R25          Add with carry
+00000080:   1F0A        ADC     R16,R26          Add with carry
+00000081:   1F1B        ADC     R17,R27          Add with carry
13:       }
+00000082:   01C7        MOVW    R24,R14          Copy register pair

+00000083:   940C00A4    JMP     0x000000A4       Jump

+00000085:   9F62        MUL     R22,R18          Multiply unsigned
+00000086:   01D0        MOVW    R26,R0           Copy register pair
+00000087:   9F73        MUL     R23,R19          Multiply unsigned
+00000088:   01F0        MOVW    R30,R0           Copy register pair
+00000089:   9F82        MUL     R24,R18          Multiply unsigned
+0000008A:   0DE0        ADD     R30,R0           Add without carry
+0000008B:   1DF1        ADC     R31,R1           Add with carry
+0000008C:   9F64        MUL     R22,R20          Multiply unsigned
+0000008D:   0DE0        ADD     R30,R0           Add without carry
+0000008E:   1DF1        ADC     R31,R1           Add with carry
+0000008F:   9F92        MUL     R25,R18          Multiply unsigned
+00000090:   0DF0        ADD     R31,R0           Add without carry
+00000091:   9F83        MUL     R24,R19          Multiply unsigned
+00000092:   0DF0        ADD     R31,R0           Add without carry
+00000093:   9F74        MUL     R23,R20          Multiply unsigned
+00000094:   0DF0        ADD     R31,R0           Add without carry
+00000095:   9F65        MUL     R22,R21          Multiply unsigned
+00000096:   0DF0        ADD     R31,R0           Add without carry
+00000097:   2799        CLR     R25              Clear Register
+00000098:   9F72        MUL     R23,R18          Multiply unsigned
+00000099:   0DB0        ADD     R27,R0           Add without carry
+0000009A:   1DE1        ADC     R30,R1           Add with carry
+0000009B:   1FF9        ADC     R31,R25          Add with carry
+0000009C:   9F63        MUL     R22,R19          Multiply unsigned
+0000009D:   0DB0        ADD     R27,R0           Add without carry
+0000009E:   1DE1        ADC     R30,R1           Add with carry
+0000009F:   1FF9        ADC     R31,R25          Add with carry
+000000A0:   01BD        MOVW    R22,R26          Copy register pair
+000000A1:   01CF        MOVW    R24,R30          Copy register pair
+000000A2:   2411        CLR     R1               Clear Register
+000000A3:   9508        RET                      Subroutine return

Где-то 108.

Цитата(Rst7 @ Oct 23 2008, 18:20)

и еще там одно деление 32 на 32, это 500 тактов

Да деление, но оно одно на весь результат. Сколько там, на 8 отсчетов, 16 или 32 - сколько берем, еще не определились. Если брать много, то несколько фонем может объединиться, если брать мало, число "фонем" может возрасти, т.к. вроде бы спектр некоторых фонем динамический, и фонема получится состоящая как бы из нескольких частей. Несмотря на свое определение.

Цитата(Rst7 @ Oct 23 2008, 18:20)

и еще 15 квадратных корней, у меня получилось 56*15=840.

А зачем корни ? Какая разница, сравнивать значение или его корень ? И даже с корнем - тоже один корень на выборку.

Цитата(Rst7 @ Oct 23 2008, 18:20)

Уже готовитесь спереть?

Нет, пока думаю, скачивать файл или не скачивать )

Цитата(Rst7 @ Oct 23 2008, 18:20)

Пока выложить могу только эти две функции. Они Вам нужны?

Я ж не один здесь. Надеюсь. Не подойдет мне, может кому другому подойдет.

defunct

Oct 23 2008, 19:54

Цитата(Огурцов @ Oct 23 2008, 22:14)

8x

Код

: C = A * A + B * B;
+00000069: 0288 MULS R24,R24 Multiply signed
...

Я насчитал 7

Чипуха какая-то. Очевидно что для двух * должно быть две команды MUL.
Подозреваю такая же чипуха у вас и в 16x. Теперь понятно откуда у вас берется порядок на 16x.

Огурцов

Oct 23 2008, 20:26

Цитата(defunct @ Oct 23 2008, 19:54)

Чипуха какая-то. Очевидно что для двух * должно быть две команды MUL.

Действительно, косячище. Это мы с другом оптимизатором наоптимизили.

Код

+00000069:   8199        LDD     R25,Y+1          Load indirect with displacement
+0000006A:   8189        LDD     R24,Y+1          Load indirect with displacement
+0000006B:   0298        MULS    R25,R24          Multiply signed
+0000006C:   0190        MOVW    R18,R0           Copy register pair
+0000006D:   2411        CLR     R1               Clear Register
+0000006E:   819A        LDD     R25,Y+2          Load indirect with displacement
+0000006F:   818A        LDD     R24,Y+2          Load indirect with displacement
+00000070:   0298        MULS    R25,R24          Multiply signed
+00000071:   01C0        MOVW    R24,R0           Copy register pair
+00000072:   2411        CLR     R1               Clear Register
+00000073:   0F28        ADD     R18,R24          Add without carry
+00000074:   1F39        ADC     R19,R25          Add with carry
+00000075:   833C        STD     Y+4,R19          Store indirect with displacement
+00000076:   832B        STD     Y+3,R18          Store indirect with displacement

21, из них 12 на загрузку/выгрузку. Итого 9 вместо 7.

Цитата(defunct @ Oct 23 2008, 19:54)

Подозреваю такая же чипуха у вас и в 16x.

Для 16x несколько лучше, в процентном оношении - стало 151, из них 16 на загрузку/выгрузку.

С другой стороны вот это

Код

LDD R25,Y+1 Load indirect with displacement
LDD R24,Y+1

можно будет заменить на

Код

LDD R25,Y+1 Load indirect with displacement
MOV R24,R25

И вообще, с оптимизацие того же ДПФ оптимизатор скорее всего не справится...

=GM=

Oct 23 2008, 22:06

Цитата(Огурцов @ Oct 23 2008, 19:26)

21, из них 12 на загрузку/выгрузку. Итого 9 вместо 7

Вообще 10, если без очистки R1. Но за каким шутом вы его очищаете?

Проще так

Код

     ld   r16,y+
     muls r16,r16
     movw r17,r0
     ld   r16,y+
     muls r16,r16
     add  r17,r0
     adc  r18,r1
     st   y+,r18
     st   y+,r17

16/8

defunct

Oct 23 2008, 22:06

Цитата(Огурцов @ Oct 23 2008, 23:26)

Для 16x несколько лучше, в процентном оношении - стало 151, из них 16 на загрузку/выгрузку.

Моя цифра - 38 (32-х битный результат):

Код

.def  AL = R24
.def  AH = R25

.def  z_reg = R2

.def u32_b0 = R18
.def u32_b1 = R19
.def u32_b2 = R20
.def u32_b3 = R21

; --> ax 16 bit operand
; <-- 32 bit result u32_xx
.MACRO sqr_ax
    mul  ah, ah
    movw u32_b3: u32_b2, r1:r0

    mul  al, al
    movw u32_b1: u32_b0, r1:r0

    mul  ah, al

    add  u32_b1, r0
    adc  u32_b2, r1
    adc  u32_b3, z_reg

    add  u32_b1, r0
    adc  u32_b2, r1
    adc  u32_b3, z_reg
.endmacro

.cseg
    ldi  AL, Low(RAMEND)
    out  SPL, AL
    ldi  AL, High(RAMEND)
    out  SPH, AL

    clr  z_reg

; начинаем счет таков отсюда
;-----> C = A * A + B * B   (a=1234, b=567, c should be 1844245)
    ldi  al, Low(1234)
    ldi  ah, High(1234)
    sqr_ax              ; A * A

    movw r5:r4, u32_b1:u32_b0
    movw r7:r6, u32_b3:u32_b2

    ldi  al, Low(567)
    ldi  ah, High(567)
    sqr_ax              ; B * B

    add  u32_b0, r4
    adc  u32_b1, r5
    adc  u32_b2, r6
    adc  u32_b3, r7     ; A * A + B * B

Результат в u32_xx (b3 - MSB, b0 - LSB).

=GM=

Oct 23 2008, 22:17

Цитата(defunct @ Oct 23 2008, 21:06)

Моя цифра - 44 (32-х битный результат)

Вроде бы надо перемножать знаковые 16-битные числа, разве нет?

defunct

Oct 23 2008, 22:18

Цитата(=GM= @ Oct 24 2008, 01:17)

Вроде бы надо перемножать знаковые 16-битные числа, разве нет?

Уже немного оптимизировал, из 44-х тактов осталось 38.
знаковые/беззнаковые не суть важно. (при возведении в квадрат всегда получаем положительное число, поэтому отрицательные операнды можно предварительно преобразовать в положительные, рез-тат не изменится, а по тактам такое преобразование - чепуха, никак не > 100).

Огурцов

Oct 23 2008, 22:32

Цитата(=GM= @ Oct 23 2008, 22:06)

Вообще 10, если без очистки R1. Но за каким шутом вы его очищаете?

Да что вы, это результат с отключенным мосхом. Compiler only, так сказать.

Цитата(defunct @ Oct 23 2008, 22:18)

Уже немного оптимизировал, из 44-х тактов осталось 38.

Ну вот, это гораздо ближе к прогнозу.
Те вещи, которые можно творить на асме, на це никогда не сделаешь. Обратное тоже верно )

=GM=

Oct 23 2008, 23:07

Цитата(defunct @ Oct 23 2008, 21:18)

Уже немного оптимизировал, из 44-х тактов осталось 38.
знаковые/беззнаковые не суть важно. (при возведении в квадрат всегда получаем положительное число, поэтому отрицательные операнды можно предварительно преобразовать в положительные, рез-тат не изменится, а по тактам такое преобразование - чепуха, никак не > 100).

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

Кстати, спасибо, вы дали ответ на мой вопрос, насколько в данном случае авр уступает дсп по скорости (боюсь, какбы друит не набежал(:-)) - примерно в 38+38 = 76 раз по тактам, а если учесть знаковую конверсию, то вгрубе будет 100.

defunct

Oct 23 2008, 23:34

Цитата(=GM= @ Oct 24 2008, 02:07)

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

Почему два? Положительных составляющих типа не бывает? ;>

Цитата

Возможно оптимальнее будет использовать комбинацию MUL для младших байтов и MULS для старших.

Для младших надо сделать операцию NEG. иначе такое умножение ни к чему хорошему не приведет.

Цитата

учесть знаковую конверсию, то вгрубе будет 100.

Если преобразовывать сразу при расчете, то это сведется к доп. 3-м тактам в худшем случае (к двум в лучшем) на каждую составлющую:

Код

  brpl __store
  com  RxH
  neg  RxL
__store:

в среднем +5 тактов к 38-ми

Rst7

Oct 24 2008, 03:35

Господа, ну вы что, думаете, что я не знаю, как быстро возвести в квадрат на AVR? Конечно знаю.

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

Еще раз повторюсь: там много накладных расходов. Я буду их уменьшать. Но, видимо, потом, потому как необходимо править последний проход БПХ для перетасовывания данных.

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

PS А почему никто не кричит, что 2000 тактов на 32хточечное БПХ - это много?

Rst7

Oct 24 2008, 10:46

Для тех, кому не терпится, выкладываю проект и листинг.

В проекте только DHT и расчет мощностей с нормированием.

Временно выключен inline для того, чтобы проще было читать листинг.

Несмотря на то, что я перетасовал выход DHT для более простой манипуляции с данными в последующем расчете мощностей выигрыша это почти не дало.

Результаты со включенным инлайном:

DHT - 1947
PWRS - 3122

Если есть возражения к коду - велком...

Нажмите для просмотра прикрепленного файла Нажмите для просмотра прикрепленного файла

=GM=

Oct 24 2008, 10:53

Цитата(defunct @ Oct 23 2008, 22:34)

Почему два? Положительных составляющих типа не бывает?

Два, потому что есть действительная и мнимая составляющая спектра, каждую надо проверять на знак.

Загрузку считать надо обязательно, поскольку множители не константы. (Подправил цифры, почему-то считал, что movw выполняется за два такта.)

Вот мой вариант перемножения (a1,a0)*(a1,a0)+(b1,b0)*(b1,b0)->(c3,c2,c1,c0), сделанный на базе ваших макросов, просто отказался от регистров промежуточного хранения r7-r4

Код

    ld    a1,y+
    ld    a0,y+
    ld    b1,y+
    ld    b0,y+

    mul    a1,a1
    movw    c2,r0
    mul    a0,a0
    movw    c0,r0
    mul    a1,a0
    add    c1,r0
    adc    c2,r1
    adc    c3,r2
    add    c1,r0
    adc    c2,r1
    adc    c3,r2

    mul    b1,b1
    add    c2,r0
    adc    c3,r1
    mul    b0,b0
    add    c0,r0
    adc    c1,r1
    adc    c2,r2
    adc    c3,r2
    mul    b1,b0
    add    c1,r0
    adc    c2,r1
    adc    c3,r2
    add    c1,r0
    adc    c2,r1
    adc    c3,r2

Итого 32 такта на вычисления, всего, с загрузкой множителей из рамы, получилось 40 тактов. Ещё можно сэкономить регистры b1, b0, если делать загрузку второго множителя в регистры (a1,a0) непосредственно перед вычислением (b1,b0)*(b1,b0). (Третий раз корректирую, спасибо rst7)

Цитата(defunct @ Oct 23 2008, 22:34)

Если преобразовывать сразу при расчете, то это сведется к доп. 3-м тактам в худшем случае (к двум в лучшем) на каждую составлющую:

Код

  brpl __store
  com  RxH
  neg  RxL
__store:

Хм, загрузка множителя не даёт флагов, надо делать тестирование, а это доптакты. Вы привели неполный код для конверсии. В среднем у вас будет будет 6 тактов, т.е. для вашего кода в среднем будет 38+6=44 на вычисления плюс 8 на загрузку, всего 52.

defunct

Oct 24 2008, 11:08

Цитата(=GM= @ Oct 24 2008, 13:53)

Два, потому что есть действительная и мнимая составляющая спектра.

И они обе отрицательные всегда?

Цитата

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

AVR-студией, код приведен. Загрузка операндов там есть, правда не из RAM а из флеш, но по скорости одинаково.

Цитата

Хм, загрузка множителя не даёт флагов, надо делать тестирование, а это доптакты. Вы привели неполный код для конверсии. В среднем у вас будет будет 6 тактов, т.е. для вашего кода в среднем будет 40+6=46 на вычисления плюс 8 на загрузку, всего 54.

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

i.e.:

1. расчет составляющей
<-- я предлагаю преобразование делать сразу здесь
2. сохранение в массив
3. загрузка из массива
<-- вы предполагаете преобразование делать здесь
4. вычисление мощности

Rst7

Oct 24 2008, 11:29

Цитата

brpl __store
com RxH
neg RxL
__store:

Чтото мне говорит, что такой код работать не будет.

Вот так - будет:

Код

  NEG     Rh
  NEG     Rl
  SBCI    Rh, 0

А вообще я по другому делаю, рекомендую глянуть в проект/листинг.

defunct

Oct 24 2008, 11:58

Цитата(Rst7 @ Oct 24 2008, 14:29)

Чтото мне говорит, что такой код работать не будет.

Точно, еще раз убеждаюсь ночная оптимизация - это зло!

Rst7

Oct 24 2008, 12:04

Цитата

Вот мой вариант перемножения (a1,a0)*(a1,a0)+(b1,b0)*(b1,b0)->(c3,c2,c1,c0),

Тоже не работает. Два произведения есть, а суммы нету

Господа, хватит. IAR делает вполне приемлемый код

DRUID3

Oct 25 2008, 09:37

Господа оптимизаторы. Объясните мне, сирому, зачем:

1) считать спектр мощности при этом теряя всю информацию о фазовой составляющей!!!??? Нафиг тогда FFT вообще???

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

2) Отбрасывать половину спектра... Вернее зачем отбрасывать я понимаю, а вот зачем ее было считать!!!???

. Кстати в FWT это отбрасывание делается лЁгко, и экономит часть расчетов...

Мда уш...

Rst7

Oct 25 2008, 09:54

Цитата

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

Нам фаза сигнала не нужна. Мы сравниваем спектры мощности. Такой у нас алгоритм.

Цитата

Быстрая корреляция методом сравнения спектров мощности это нечто новое вообще.

Тут никто не говорит о вычислении взаимной корреляции.

Цитата

Отбрасывать половину спектра... Вернее зачем отбрасывать я понимаю, а вот зачем ее было считать!!!???

А кто ее отбрасывает и кто ее считает? 32 результата после Хартли суть 15 пар значений, которые определяют мощность каждой спектральной составляющей и постоянку, которую отбрасываем.

Цитата

Кстати в FWT это отбрасывание делается лЁгко, и экономит часть расчетов...

А причем тут вейвлеты?

Отбрасывать надо пол-спектра именно при DFT (Фурье), на входе которого только действительные числа. Тогда спектр зеркально симметричен. Мы же, для оптимизации, пользуем DHT (Хартли), которое именно под это и заточено - под обработку действительных исходных данных.

Цитата

Мда уш...

К Вам это тоже относится