nikolas_osu 0 6 ноября, 2009 Опубликовано 6 ноября, 2009 · Жалоба Необходимо аппроксимировать 400 точек полиномом 11 степени, потом полиномы 11 степени будут передаваться по медленному каналу связи... Есть ли какие-нибудь готовые алгоритмы для этого?.. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Xenia 42 6 ноября, 2009 Опубликовано 6 ноября, 2009 · Жалоба Необходимо аппроксимировать 400 точек полиномом 11 степени, потом полиномы 11 степени будут передаваться по медленному каналу связи... Есть ли какие-нибудь готовые алгоритмы для этого?.. На платформе AVR, как и на любой другой, можно запрограммировать любые вычисления, если ... хватит места под данные. Особеность тут только та, что МК этой платформы не имеют аппаратного умножения чисел с плавающей точкой, а с использованием эмуляции сложный расчет может занять порядочное время. Полином 11-ой степени уже не подарок, т.к. расчет в лоб потребует инвертирования матрицы, которая к тому же очень плохо определена (близка к матрице Гильберта). Поэтому такой расчет на AVR лучше не делать, а если и посылать в него данные, то не коэффициенты полинома, а уже готовую обращенную матрицу, чтобы тот только множил на нее вектор данных и больше ни о чем не заботился. А ту матрицу пусть хоть писюк посчитает. Только при этом нужно учесть, что такая матрица-сомножитель для вашего случая будет иметь размерность 400x11=4400 элементов, а если каждый по 4 байта (тип float), то выйдет 17.6 килобайт. Уже многонько, не каждая AVR-ка потянет. А с точностью double потребуется еще вдвое больше памяти. Да и само умножение получится не быстрым при такой большой матрице и медленной реализации умножения. А если говорить об алгоритмах, то тут, полагаю, надо попытать расчет коэффициентов через полиномы Чебышева. Кажется где-то есть такой способ, отличающийся устойчивостью. Однако в любом случае AVR придется делать одну и ту же операцию умножения вектора длиной 400 на матрицу размером 400х12. А алгоритмы будут различаться между собой только тем, как такая матрица вычисляется. В любом случае вычислять ее надо будет не на AVR, а засылать ему уже готовую. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
_Pasha 0 6 ноября, 2009 Опубликовано 6 ноября, 2009 · Жалоба Необходимо аппроксимировать 400 точек полиномом 11 степени Какое время выделяется на обсчет? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
nikolas_osu 0 6 ноября, 2009 Опубликовано 6 ноября, 2009 · Жалоба Какое время выделяется на обсчет? 0.7 секунды Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Oldring 0 6 ноября, 2009 Опубликовано 6 ноября, 2009 · Жалоба Необходимо аппроксимировать 400 точек полиномом 11 степени, потом полиномы 11 степени будут передаваться по медленному каналу связи... Аппроксимировать полиномом 11-й степени? Вы уверены, что это действительно хорошая идея? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Builder 1 6 ноября, 2009 Опубликовано 6 ноября, 2009 · Жалоба Необходимо аппроксимировать 400 точек полиномом 11 степени, потом полиномы 11 степени будут передаваться по медленному каналу связи... Есть ли какие-нибудь готовые алгоритмы для этого?.. А Вы для начала алгоритм в том-же матлабе или просто на С/С++ уже промоделировали? Всё устойчиво и хорошо опраксимирует? Что-то подсказывает что будут проблемы с точностью опраксимации, уж очень много точек на один полином. Если только у точек не какой хитрый закон, которых хорошо ляжет на полином. Если у Вас на руках есть алгоритм, как делали? Неужели там нет много матриччных вычислений? Давно что-то похожее делал, подробности забыл, но для нахождения параметров полинома использовались множители Лагранжа. Так помнится были проблемы, часто после апроксимации, при проверке качества апроксимации результат был плохой. Хотя у меня было много граничных условий, в Вашем случае может всё лучше будет работать. После чего участо разбивался на 2 части, и для них всё считалось одельно. И так дробил отрезок, покуда не получал нужной точности апроксимации. Возможно этот алгоритм не очень хорошо работал, но тем не менее, есть сомнненя что 400 точек лягут на один полином. Ну а по теме, 0,7 секунды на AVR для 400 точек, IMHO не реально, у вас будут большие матрыцы, не позубам так быстро считать для AVR. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
_Pasha 0 6 ноября, 2009 Опубликовано 6 ноября, 2009 · Жалоба Ну а по теме, 0,7 секунды на AVR для 400 точек, IMHO не реально, у вас будут большие матрыцы, не позубам так быстро считать для AVR. +1 Не успеет :( Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Xenia 42 6 ноября, 2009 Опубликовано 6 ноября, 2009 · Жалоба Вообще-то за 0.7 сек можно спокойно передать эти 400 точек даже по самому медленному из существующих каналов. И не мучить АВРку. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Tanya 4 7 ноября, 2009 Опубликовано 7 ноября, 2009 · Жалоба Аппроксимировать полиномом 11-й степени? Вы уверены, что это действительно хорошая идея? Я уверена в обратном. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
aser 0 7 ноября, 2009 Опубликовано 7 ноября, 2009 · Жалоба В мобильнике считается полином 10 степени и от ~ 270 точек, квантованных на 8000 Гц. На обсчет полинома тратится где-то 1% времени 16-битного микропроцессора с производительностью 20MIPS. Так что AVR, если будет только полином считать, то может и успеет. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Oldring 0 7 ноября, 2009 Опубликовано 7 ноября, 2009 · Жалоба В мобильнике считается полином 10 степени и от ~ 270 точек, квантованных на 8000 Гц. На обсчет полинома тратится где-то 1% времени 16-битного микропроцессора с производительностью 20MIPS. Так что AVR, если будет только полином считать, то может и успеет. Ну еще полином 255-й степени в общеупотребимых кодах Рида-Соломона вспомни. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
_pv 69 9 ноября, 2009 Опубликовано 9 ноября, 2009 · Жалоба Алгоритм нелинейной регрессии для AVR Есть ли какие-нибудь готовые алгоритмы для этого?.. http://www.google.ru/search?&q=polynomial+fitting только почему она нелинейная-то? На платформе AVR, как и на любой другой, можно запрограммировать любые вычисления, если ... хватит места под данные. Особеность тут только та, что МК этой платформы не имеют аппаратного умножения чисел с плавающей точкой, а с использованием эмуляции сложный расчет может занять порядочное время. А ту матрицу пусть хоть писюк посчитает. Только при этом нужно учесть, что такая матрица-сомножитель для вашего случая будет иметь размерность 400x11=4400 элементов, а если каждый по 4 байта (тип float), то выйдет 17.6 килобайт. Ну матрица будет всего 11х11, не так уж и много. Если даже по Гауссу занулять, за секунду вроде можно успеть, да и операции с плавающей запятой наверное можно ускорить немного, от точности зависит, никто же соответствия ieee-754 не требует. Однако, целесообразность сего действа действительно крайне сомнительна. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
vvs157 0 9 ноября, 2009 Опубликовано 9 ноября, 2009 · Жалоба Ну матрица будет всего 11х11, не так уж и много. Если даже по Гауссу занулять, за секуну вроде можно успеть, да и операции с плавающей запятой наверное можно ускорить немного, от точности зависит, никто же соответствия ieee-754 не требует.Но только еще эту матрицу надо заполнить суммами. Плюс отдельный вопрос про вычислительную устойчивость алгоритма. В общем случае если использовать метод "в лоб" при 32 битных float может терять устойчивость при степенях полинома >6 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Oldring 0 10 ноября, 2009 Опубликовано 10 ноября, 2009 · Жалоба Но только еще эту матрицу надо заполнить суммами. Плюс отдельный вопрос про вычислительную устойчивость алгоритма. В общем случае если использовать метод "в лоб" при 32 битных float может терять устойчивость при степенях полинома >6 По поводу вычислительной устойчивости на самом деле вопросов нет. Число обусловленности для матрицы составленной из векторов полиноминального базиса до 10 порядка для интервала 0-1 составляет порядка 22 миллионов. В такой ситуации о вычислительной устойчивости алгоритма говорить не приходится. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
aser 0 10 ноября, 2009 Опубликовано 10 ноября, 2009 · Жалоба Ну еще полином 255-й степени в общеупотребимых кодах Рида-Соломона вспомни. Это была оценка вычислительной сложности.Конкретнее следующее. Если взять какой-нибудь стандарт компрессии речи типа G721, то там есть Си-программки, в том числе и нахождение АР-модели кадра речи - ее можно взять за основу и даже странслировать в AVR. Правда, степень полинома нужно будет увеличить с10 до 11. В стандарте программа сделана очень профессионально -есть чему поучиться. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
