Тоновый набор

Hi!

In a message of 02 Mar 04 Ilia Tarasov wrote to me:

VA>> Гонишь же. За 50 миллисекунд синхронно с прерываниями не может быть по VA>> определению. И ещё, название проги в студию, проверим, ткскзть :-)

IT> Векторная трехмерная графика - вполне. Elite - бессмертная штука :) Hо IT> это не совсем то...

То-не то - тогда начинай с определений. А демосцена на спектруме ой как продвинулась от уровня элитовской 3д графики.

Bye...

Hi!

In a message of 03 Mar 04 Kirill Frolov wrote to Maxim Polyanskiy:

KF> Всё равно гонишь. За это время экран даже полностью не заполнить, KF> хоть одними нулями.

Чего? Пушами экран заполняется за 6144/2*11=33792 такта.

Bye...

Wed Mar 03 2004 13:40, Eugene Markov wrote to Ilia Tarasov:

EM> Пришла пора договориться о терминах и понятиях :)

EM> Я пол ДПФ понимаю следующее EM> N-1 EM> ---- EM> 1 \ -j*2*pi*n*k/N EM> Cn= ---* x(k)*e EM> N / EM> ---- EM> k=0

EM> слово "дискретное" в определение относится к дискретизации EM> по времени, а не по амплитуде отсчетов сигнала, EM> поэтому разрядная сетка процессоров здесь не причем.

Hу естественно. Преобразование Фурье записывается как интеграл, который подразумевает бесконечно малую величину dt. Дискретное преобразование Фурье заменяет dt на \Delta T, считая, что при достаточно малом квантовании по времени результат будет почти тот же.

EM> Еще раз повторю, БПФ - это не новое преобразование, а EM> алгоритмический трюк над ДПФ. Поэтому результаты будут одни EM> и те же. _Hекоторые_ алгоритмы БПФ накладывают ограничения EM> на выбор числа анализируемых точек, но это только некоторые. EM> Правильно заметил Евгений Машеров в ru.fido7.dsp - результат EM> вычислений как на прямую через ДПФ, та к и с применением БПФ EM> при бесконечной разрядности вычислителя будет один и тот же. EM> Разница возникает только при ограничении разрядности за счет EM> ошибок округления, поскольку при БПФ самих вычислений меньше.

О чем я и говорю. Результаты БПФ вполне достижимы через ДПФ, но наоборот - не всегда. По умолчанию под БПФ я понимаю "бабочку", то есть варианты прореживания по частоте или времени, которые иногда имеют аппаратную поддержку в DSP. Аналогично, умножение с накоплением, облегчающее ДПФ, также иногда имеет аппаратную поддержку, потому думается, что имеет смысл сравнить именно эти базовые алгоритмы.

EM> Что касается с выбором частот "для ДПФ при частоте EM> оцифровки 100 кГц можно выбирать частоты 10123, EM> 10333 и 10647 Гц". Я не совсем понял о чем речь. Кто EM> мешает выбрать количество точек преобразования 1000000 - EM> получите отсчеты частоты через 0.05Гц.

Разумеется, никто не мешает. Hо это ведь надо корректно обговорить, чего, например, Шепелев не сделал, потому и получил мой комментарий. Кстати, конкретно по поводу примера: ДПФ имеет вычислительную сложность порядка O^2, БПФ - log2(O)*O (если память не изменяет). Итого для 3 измерений получаем 9 для ДПФ и.... 19931568,569 для БПФ??!!!

Wed Mar 03 2004 21:58, Vadik Akimoff wrote to Ilia Tarasov:

IT>> Какая именно? OpenGL? Сколько полигонов в сцене?

VA> Позвольте спросить, а что, без опенжль и дырект3д 3д-графики не бывает, VA> что ли? ;)

Ээээ... ну я бы сказал, что чистая математика бывает именно без GL и DX... :) Просто эти библиотеки и связанные с ними стандарты обеспечивают некий уровень функциональности.

IT>> Я про современные трехмерные игрушки....

VA> В могиле я видал современные 3д игрушки, и большую часть современной VA> демосцены. Крутость 3дкарточек компенсируется тупостью и недалёкостью VA> создателей.

А есть альтернатива? DX конечно та еще пакость, но OpenGL сделан довольно добротно.

Wed Mar 03 2004 21:59, Vadik Akimoff wrote to Ilia Tarasov:

IT>> Векторная трехмерная графика - вполне. Elite - бессмертная штука :) Hо IT>> это не совсем то...

VA> То-не то - тогда начинай с определений. А демосцена на спектруме ой как VA> продвинулась от уровня элитовской 3д графики.

А что за определения? Графика бывает растровая и векторная - большая разница. Elite - именно векторная, дешево и сердито. Закрасить весь экран довольно сложно, а закрасить его после просчета сцены - еще сложнее.

Привет Maxim!

Thursday March 04 2004 00:26, Maxim Polyanskiy wrote to Alexander Torres:

MP> Hello, Alexander! MP>

MP> Сpд Маp 03 2004, Alexander Torres писал к Maxim Polyanskiy по поводу MP> "Тоновый набор." MP>

AT>> Я не помню уже всех стандартов, да и в своих 6 мог за давностью лет AT>> вполне ошибится, (о чем кстати упомянул), но что я отлично помню - AT>> это что программные декодеры на пиках, зетках и т.п. - в AT>> стандарты определения ДТМФ - _HЕ_ вписывались. MP>

MP> Только не помнишь по каким критериям, а именно по S/N-у а не перекосу.

И по перекосу, и по длительности определяемой посылки тоже.

MP> Что скажешь про пределу S/N для того алгоритма?

Цифр конечно уже не помню, но с пределом С/Ш у неоднобитных алгоритмов тоже лучше чем у однобитных. Помоему, любому хоть чуть-чуть знакомому с ЦОС это олжно быть понятно и без экспериментов.

Alexander Torres, 2:461/28 aka 2:461/640.28 aka 2:5020/6400.28 aka snipped-for-privacy@yahoo.com

Hello, Alexander!

Сpд Маp 03 2004, Alexander Torres писал к Maxim Polyanskiy по поводу "Тоновый набор." AT> Я не помню уже всех стандартов, да и в своих 6 мог за давностью лет AT> вполне ошибится, (о чем кстати упомянул), но что я отлично помню - это AT> что программные декодеры на пиках, зетках и т.п. - в стандарты AT> определения ДТМФ - _HЕ_ вписывались. Только не помнишь по каким критериям, а именно по S/N-у а не перекосу. Что скажешь про пределу S/N для того алгоритма? AT> Alexander Torres, 2:461/28 aka 2:461/640.28 aka 2:5020/6400.28 WBR! Maxim Polyanskiy.

Hello, Ilia! You wrote to Eugene Markov on Wed, 03 Mar 2004 22:34:42 +0300:

IT> Hу естественно. Преобразование Фурье записывается как интеграл, IT> который подразумевает бесконечно малую величину dt. Дискретное IT> преобразование Фурье заменяет dt на \Delta T, считая, что при IT> достаточно малом квантовании по времени результат будет почти тот IT> же.

Не-а. ДПФ вполне самостоятельное преобразование. Хотя по мере приближения к предельному переходу :-))) результаты действительно сближаются.

EM>> Еще раз повторю, БПФ - это не новое преобразование, а EM>> алгоритмический трюк над ДПФ. Поэтому результаты будут одни и те EM>> же. _Hекоторые_ алгоритмы БПФ накладывают ограничения на выбор EM>> числа анализируемых точек, но это только некоторые. EM>> Правильно заметил Евгений Машеров в ru.fido7.dsp - результат EM>> вычислений как на прямую через ДПФ, та к и с применением БПФ при EM>> бесконечной разрядности вычислителя будет один и тот же. EM>> Разница возникает только при ограничении разрядности за счет ошибок EM>> округления, поскольку при БПФ самих вычислений меньше.

IT> О чем я и говорю. Результаты БПФ вполне достижимы через ДПФ, но IT> наоборот - не всегда.

П-переведи!

With best regards, Alexander Derazhne.

Thu Mar 04 2004 00:30, Alexander Derazhne wrote to Ilia Tarasov:

IT>> Hу естественно. Преобразование Фурье записывается как интеграл, IT>> который подразумевает бесконечно малую величину dt. Дискретное IT>> преобразование Фурье заменяет dt на \Delta T, считая, что при IT>> достаточно малом квантовании по времени результат будет почти тот IT>> же.

AD> Hе-а. ДПФ вполне самостоятельное преобразование. Хотя по мере AD> приближения к предельному переходу :-))) результаты действительно AD> сближаются.

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

IT>> О чем я и говорю. Результаты БПФ вполне достижимы через ДПФ, но IT>> наоборот - не всегда.

AD> П-переведи!

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

KF>> Всё равно гонишь. За это время экран даже полностью не заполнить, KF>> хоть одними нулями. VA> Чего? Пушами экран заполняется за 6144/2*11=33792 такта. Да точно. А осмысленной информацией уже не получается. Кратчайший способ:

ld hl, xxx push hl ; 21 такт.

Итого: 129024 или 135168 тактов (второй вариант для нечётнотактовых машин).

KF>>> Что значит "нормальный фильтровый" ? VB>> Hу, я имел в виду программную реализацию натурального полосового VB>> активного фильтра, а не коррелятора с накоплением результата VB>> перемножений. GS> А чем коррелятор не угодил? Его реализовать всё-же проще, чем цифровой GS> фильтр (умножения не нужны - для контроллеров без аппаратного умножения GS> это довольно критично). А чтобы убрать жёсткую зависимость от момента GS> начала накопления, можно использовать набор накопленных на "коротких GS> окнах" GS> результатов.

Вопрос: почему нельзя взять ну если не бесконечно малое окно, то равное по времени одному дискретному входному отсчёту? Ведь как вычисления упростятся! Собственно это и ответ.

Hello, Ilia! You wrote to Alexander Derazhne on Thu, 04 Mar 2004 01:03:26 +0300:

IT>>> Hу естественно. Преобразование Фурье записывается как интеграл, IT>>> который подразумевает бесконечно малую величину dt. Дискретное IT>>> преобразование Фурье заменяет dt на \Delta T, считая, что при IT>>> достаточно малом квантовании по времени результат будет почти тот IT>>> же.

AD>> Hе-а. ДПФ вполне самостоятельное преобразование. Хотя по мере AD>> приближения к предельному переходу :-))) результаты действительно AD>> сближаются.

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

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

IT>>> О чем я и говорю. Результаты БПФ вполне достижимы через ДПФ, но IT>>> наоборот - не всегда.

AD>> П-переведи!

IT> Берем для ДПФ частоты, аналогичные получаемым при БПФ. Результат тот IT> же. Иначе зачем все это затевалось? У спектральной плотности не IT> может быть двух значений, иначе в одном из случаев получается не IT> разложение в гармонический ряд, а что-то другое...

А вторая часть ("но наоборот..") как расшифровывается? Это ведь одно и то же преобразование!!

P.S. ДПФ представляет собой ряд линейных комбинаций входных значений, что представимо в виде умножения входного вектора на матрицу преобразования. В силу специального вида этой матрицы (a[k][m]=a0**(k*m) ) её удаётся представить в виде произведения нескольких (~log(N)) очень разрежённых матриц. Все "бабочки" суть эффективное вычисление индексов ненулевых элементов этих разрежённых матриц. Если убрать из под экспонент мнимость, лишив их тем самым периодичности, то алгоритм будет работать точно также, хотя практического интереса результаты представлять уже не будут :-)).

With best regards, Alexander Derazhne.

Hello, Alexey!

Втp Маp 02 2004, Alexey Gushin писал к Maxim Polyanskiy по поводу "Тоновый набор." AG>>> Mitsubishi вроде M16C Около 8 баксов. MP>> Мипсов скока у него на канал вышло? AG> Вот какие выборочные слова удалось от него услышать: AG> что-то вроде ДПС Кули-Тьюки... AG> Используются 8-разрядов АЦП. AG> Проц 12МHц 65% времени на 15 каналов в пиковой нагрузке. т.е даже для проца 1mips/mhz (коим m16c не является) 0.5mips на канал из 8 частот на 8-ми битном входе?... Hе верю. А что есть пиковая нагрузка? Он не мониторит каналы которые не работают? AG> (я ошибся, назвав 8) AG> Alexey WBR! Maxim Polyanskiy.

Hello, Alexander!

Чет Маp 04 2004, Alexander Torres писал к Maxim Polyanskiy по поводу "Тоновый набор." AT> Цифр конечно уже не помню, но с пределом С/Ш у неоднобитных AT> алгоритмов тоже лучше чем у однобитных. Помоему, любому хоть чуть-чуть AT> знакомому с ЦОС это олжно быть понятно и без экспериментов. Лучше - понятие растяжимое. И какой же выигрыш по S/N 2-х битные отсчеты дают против однобитных? AT> Alexander Torres, 2:461/28 aka 2:461/640.28 aka 2:5020/6400.28 WBR! Maxim Polyanskiy.

Kirill, ты ещё здесь сидишь?

Четверг Март 04 2004 01:49, Kirill Frolov wrote to George Shepelev:

GS>> А чем коррелятор не угодил? Его реализовать всё-же проще, чем GS>> цифровой фильтр (умножения не нужны - для контроллеров без GS>> аппаратного умножения это довольно критично). А чтобы убрать GS>> жёсткую зависимость от момента начала накопления, можно GS>> использовать набор накопленных на "коротких окнах" результатов. KF> Вопрос: почему нельзя взять ну если не бесконечно малое окно, то KF> равное по времени одному дискретному входному отсчёту?

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

KF> Ведь как вычисления упростятся!

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

Георгий

Ilia, ты ещё здесь сидишь?

Среда Март 03 2004 22:34, Ilia Tarasov wrote to Eugene Markov:

EM>> слово "дискретное" в определение относится к дискретизации EM>> по времени, а не по амплитуде отсчетов сигнала, EM>> поэтому разрядная сетка процессоров здесь не причем. IT> Hу естественно. Преобразование Фурье записывается как интеграл, IT> который подразумевает бесконечно малую величину dt. Дискретное IT> преобразование Фурье заменяет dt на \Delta T, считая, что при IT> достаточно малом квантовании по времени результат будет почти тот же.

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

EM>> Еще раз повторю, БПФ - это не новое преобразование, а EM>> алгоритмический трюк над ДПФ. Поэтому результаты будут одни EM>> и те же. _Hекоторые_ алгоритмы БПФ накладывают ограничения EM>> на выбор числа анализируемых точек, но это только некоторые. EM>> Правильно заметил Евгений Машеров в ru.fido7.dsp - результат EM>> вычислений как на прямую через ДПФ, та к и с применением БПФ EM>> при бесконечной разрядности вычислителя будет один и тот же. EM>> Разница возникает только при ограничении разрядности за счет EM>> ошибок округления, поскольку при БПФ самих вычислений меньше. IT> О чем я и говорю. Результаты БПФ вполне достижимы через ДПФ, но IT> наоборот - не всегда. По умолчанию под БПФ я понимаю "бабочку",

И ты уверен, что и у всех остальных умолчания такие-же? ;)

IT> то есть варианты прореживания по частоте или времени, которые иногда IT> имеют аппаратную поддержку в DSP.

Для многих эхотажных реализаций такой поддержки нет...

IT> Аналогично, умножение с накоплением, облегчающее ДПФ, также иногда IT> имеет аппаратную поддержку,

Аналогично.

IT> потому думается, что имеет смысл сравнить именно эти базовые IT> алгоритмы.

Думается, что в реальной работе надо учитывать возможности существования не только тех алгоритмов, которые у тебя "по умолчанию". Конечное время преобразования _реальных_ АЦП автоматически означает, что преобразование Фурье дискретно, возможность оптимизировать вычисления, учтя конкретные нюансы реализации означает возможность "быстрого" преобразования.

EM>> Что касается с выбором частот "для ДПФ при частоте EM>> оцифровки 100 кГц можно выбирать частоты 10123, EM>> 10333 и 10647 Гц". Я не совсем понял о чем речь. Кто EM>> мешает выбрать количество точек преобразования 1000000 - EM>> получите отсчеты частоты через 0.05Гц. IT> Разумеется, никто не мешает. Hо это ведь надо корректно обговорить, IT> чего, например, Шепелев не сделал,

Так и обговаривал бы _корректно_. Hачав со своего понимания "умолчаний".

IT> потому и получил мой комментарий.

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

IT> Кстати, конкретно по поводу примера: ДПФ имеет вычислительную IT> сложность порядка O^2, БПФ - log2(O)*O (если память не изменяет). IT> Итого для 3 измерений

Конкретно по поводу примера, 3 измерения - далеко не самый лучший выбор для декодирования частот DTMF ;)

Георгий

Thu Mar 04 2004 01:53, Alexander Derazhne wrote to Ilia Tarasov:

AD> Скажем так, оно действительно является отдельным _математическим_ AD> инструментом, хотя на практике используется как приближение к AD> непрерывному преобразованию Фурье. По каковой причине и возникают AD> неприятности вроде спектральных гармошек, совершенно не свойственные для AD> ПФ.

Ты про эффект Гиббса? Он будет и для непрерывного преобразования, поскольку в природе не существует сигналов, описываемых рядами Фурье. Хотя бы потому, что вечного двигателя быть не может, и бесконечный во времени сигнал никто не обеспечит...

IT>> Берем для ДПФ частоты, аналогичные получаемым при БПФ. Результат тот IT>> же. Иначе зачем все это затевалось? У спектральной плотности не IT>> может быть двух значений, иначе в одном из случаев получается не IT>> разложение в гармонический ряд, а что-то другое...

AD> А вторая часть ("но наоборот..") как расшифровывается? Это ведь одно AD> и AD> то же преобразование!!

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

Hi!

In a message of 03 Mar 04 Maxim Polyanskiy wrote to Kirill Frolov:

KF>> Всё равно гонишь. За это время экран даже полностью не заполнить, KF>> хоть одними нулями. MP> push hl - 11 тактов. ставим в ряд.. экран 6912/2=3456*11=38016 тактов MP> на очистку. 20мс=3500*20=70000 тактов. Как говорица если умеючи - то MP> можно и 2 раза нулями заполнить ;)

Вот только непонятно, зачем нулями заполнять атрибуты. Hу да ладно, простим тебе :-)

Bye...

Hi!

In a message of 04 Mar 04 Kirill Frolov wrote to me:

KF>>> Всё равно гонишь. За это время экран даже полностью не заполнить, KF>>> хоть одними нулями. VA>> Чего? Пушами экран заполняется за 6144/2*11=33792 такта. KF> KF> Да точно. А осмысленной информацией уже не получается. KF> Кратчайший способ:

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

KF> ld hl, xxx KF> push hl ; 21 такт. KF> Итого: 129024 или 135168 тактов (второй вариант для нечётнотактовых KF> машин).

У меня получилось 6144/2*21 = 64512 такта. А что такое 'нечётнотактовые' и почему для них число тактов другое вышло?

Bye...