У меня стоит задача нормировки потока чисел (поток пикселей изображения) на некоторое переменное значение (например разницу максимальной и минимальной яркости изображения). Соответственно без деления не обойтись. Те алгоритмы, которые используются чаще всего, делятся на два типа: либо тупо LUT с забитой таблицей 1/х, либо итеративные алгоритмы, имитирующие деление в столбик, с различной степенью оптимизации. Еще можно складывать делитель, пока результат не превзойдет делимое и посчитать количество таких операций, но это совсем плохой алгоритм.

Почему никто не использует тупо полиномиальную аппроксимацию 1/х? Вот здесь всего навсего полином 3-й степени, 100 слайсов на 3-ем Спартане и при этом точность 11 бит. Мне так кажется, что я здесь что-то не понимаю, это же так просто, почему так не делают?
Еще и конкретно для моей задачи - даже при точности 11 бит, я мог бы получить приемлемый результат, забив на линейность нормировки.

Спасибо.

..я пользуюсь сдвигом вправо.

Вот например целочисленное деление не подходит?
Какая частота съема пикселей? Разрядность пикселей? Какая плис?
PS в крайнем случае можно сделать pipeline деление...

собственно вот и ответ на ваш вопрос.

ЗЫ. деление в столбик будет делить точно, при конвейере будет 1 слово за такт. и для ваших 11 бит составит немногим больше 100 слайсов.

Частота - 50МГц, 14бит, плис - 7я серия xilinx. На данный момент для деления использую корку DividerGenerator в режиме Radix-2. Хавает более 2000 FF... pipeline нужен обязательно, а вот latency роли не играет, хоть 1000 тактов пойдет. Ваш алгоритм, насколько я понимаю, несколько тактов на деление требует? Я боюсь, что если его конвейеризировать, то слайсов будет прилично занимать...
И все-таки в аппроксимации меня привлекает то, что результат-то можно получать гораздо большей разрядности, чем наихудшую точность (ну как в АЦП - есть разрядность, а есть нелинейность и в плохом АЦП может быть 16 эффективных разрядов, но линейными могут быть только 14). Т.е. можно получить монотонную 16-битную функцию на выходе, у которой только первые 11 бит будут всегда точно соответствовать 1/х, что вполне может сгодиться. Делением в столбик такого не получишь...

думаю будет меньше чем 2000 FF

upd

для 16 битных данных


таймквет показывает частоту выше 300 МГц

Как вариант можно блок деления запустить на частоте эдак 300МГц.

300МГц/50МГц = 6

Ставим 3 (с запасом) модуля и переиспользуем ресурсы.
Таким образом, Вы получаете на 3 модулях pipeline на 3*6=18 тактов
Минимизация ресурсов налицо за счет временного мультиплексирования и переиспользования ресурса (модуля деления)...
------------------------------------------------------------------------------------------------------------------------------------------------------------
Даже если просто (для работы на одной тактовой частоте 50МГц)
85 регистров *16 = 1 360
то и здесь получается экономия

только что увидел у Вас не 16 бит а 14 бит данные, тогда еще больше экономии...

если в a/b делитель не так часто меняется, посчитайте как угодно медленно один раз с=(2^n)/b и потом множьте на него за такт и сдвигайте.

С нормировкой кадра такое прокатит, а вот когда множитель для каждого пикселя меняется (а такое тоже надо) - уже нет

Наверное потому, что x должно быть в пределах от 1 до 2х (в той же статье написано). Может не хватить диапазона.

Да, есть такое. Адекватно аппроксимировать 1/х и возле нуля и на хвосте невозможно... Хотя, как в той же статье, можно попытаться разбить область определения на несколько сегментов и в каждом сегменте использовать свои коэффициенты для полинома... Считать полиномы посложнее будет - надо концы сегментов согласовывать, т.е. решать задачу с закрепленными концами, но все-таки мне кажется такой поход интересным...

Для вычисления 1/x есть еще итерационные алгоритмы, для них характерна очень быстрая сходимость, в том числе и на больших разрядностях

например? (хорошие по Вашему мнению - 32/64 бит)

Ну можно, наверное, методом Ньютона попробовать..

Главное - выбрать правильное начальное приближение..

Например, мы хотим найти частное от деления: A/B = D, где A = 555555, B = 11 и, соответственно, D = 50505.

Тогда:

A/B = [(A*2³²/B)>>32] = D.

Введем обозначение:

x = 2³²/B.

Это равносильно:

2³²/x = B.

Или:

f(x) == 2³²/x - B = 0.

Находим производную:

f'(x) = -2³²/x².

Теперь подставляем всё это в формулу Ньютона и находим:

x_n+1 = x_n - f(x_n)/f'(x_n), или

x_n+1 = x_n + [2³²/x_n - B]/[2³²/x_n²], или

x_n+1 = 2*x_n - B*x_n²/2³², или

x_n+1 = 2*x_n - [(B*x_n*x_n)>>32].

Начальное приближение для x₀ выбираем равным:

x₀ = 2^32-m, где m - максимальная степень двойки в двоичном представлении числа B..

То есть, для B = 11 это дает:

B = 11_d = 1011_b = 1*2³ + 0*2² + 1*2¹ + 1*2⁰.

Откуда находим, что m = 3, и:

x₀ = 2²⁹.

Тогда:

x₁ = 2³⁰ - 11*2²⁶ = 335544320;

x₂ = 2*335544320 - (11*335544320*335544320)>>32 = 382730240;

x₃ = 2*382730240 - (11*382730240*382730240)>>32 = 390298880;

x₄ = 2*390298880 - (11*390298880*390298880)>>32 = 390451513;

x₅ = 2*390451513 - (11*390451513*390451513)>>32 = 390451572;

x₆ = 2*390451572 - (11*390451572*390451572)>>32 = 390451572;

После чего находим:

A/B = [(A*x)>>32] = [(555555*390451572)>>32] = 50505 = D.

Но в целом, все эти "быстро сходящиеся итерации" не слишком то оптимальны для FPGA, КМК..

Как-то так..

спасибо...

PS метод Ньютон работает для нахождения практически любых функций и как Вы правильно заметили для FPGA в чистом виде плохо подходят

я думал, что есть уже какие-то модификации, которые лучше подходят для FPGA и менее итерационные...

Ну вообще Ньютон как раз может и быть интересен. По крайней мере в алгоритме быстрого вычисления обратного корня именно он и используется. Кстати интересно, есть ли готовые корки, реализующие быстрый инверсный корень?