Научный журнал

Фундаментальные исследования

ISSN 1812-7339

"Перечень" ВАК

ИФ РИНЦ = 1,674

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Булатникова И.Н. 1 Гершунина Н.Н. 1

---

1 ФГБОУ ВПО «Кубанский государственный технологический университет»

Настоящая статья посвящена изложению принципов проектирования так называемых неаналитических алгоритмов. Они характеризуются тем, что строятся не вдоль аналитических выражений сущности преобразования информации, а на основе модельных свойств математических объектов (векторов, итерационных процессов и т.п.). Их появление вызвано широким распространением микропроцессоров, предъявляющих требование к алгоритмам – отсутствие операций умножений и делений (целочисленность алгоритмов). Предложено развитие разностно-итерационных алгоритмов, в том числе известного алгоритма Оранского и Рейхенберга. Произведена его модификация для обеспечения реализации широкого класса функциональных преобразований. Итоговая погрешность таких алгоритмов (точность на уровне 10–12 двоичных разрядов) позволяет успешно их использовать в микропроцессорных устройствах локальной автоматики.

Статья в формате PDF

569 KB

микропроцессоры

быстродействующие целочисленные алгоритмы

устройства локальной автоматики

1. Булатникова И.Н., Ключко В.И. и.др. Информационные технологии с использованием целочисленной арифметики // Аналитический научно-технический журнал «Геоинжиниринг», НИПИ «Инжгео». – 2011. – № 2(11). – С. 54–58.

2. Гершунина Н.Н. Частиков А.П. и др. Автоматизированный информационно-вычислительный пункт экспресс-анализа качества для пиво- и безалкогольных производств // Изв. вузов. Пищевая технология. – 1999. – № 1. – С. 34–36.

3. Оранский А.М. Аппаратные методы в цифровой вычислительной технике. – Минск: Изд-во БГУ, 1977. – 208 с.

4. А.с. 744595 СССР, МКИ2 G06F7/34. Цифровой функциональный преобразователь / А.М. Оранский, А.Л. Рейхенберг. Опубл. 30.06.1980 г. Бюл. № 24.

5. Meggitt J.E. Pseudo division and pseudo multiplication processes // IBM J. Res. And Develop. – 1962. – Vol. 6. – № 2. – Р. 220–226.

6. Volder J.E. The CORDIC trigonometric computing // The Trans. On Electric Corp. – 1959. – Vol. 8. – № 3. – Р. –330–340.

Широкое внедрение микропроцессорной техники потребовало особого алгоритмического и программного обеспечения, имеющего быстродействие, соизмеримое с аппаратным быстродействием самих микропроцессоров (МП). Дело в том, что в феномене МП резко обострились противоречия между машинным характером обработки информации и антропогенностью ее алгоритмов.

Ранее все ЭВМ считали вдоль аналитического выражения реализуемой функции преобразования информации, т.е. повторяли человеческие расчеты по формулам. Отсюда обязательность операций (+ , –, ×, /). Но это не соответствовало идеологии МП (максимум быстродействия при минимуме аппаратурных затрат).

Уже в 60-х годах прошлого столетия появились первые быстродействующие алгоритмы неаналитических вычислений, сокращавших аппаратурные затраты. Это алгоритмы Волдера [6] и Меджитта [5], имевшие в русскоязычной технической литературе название «шаг за шагом» (от английского “step by step”). Они имели исключительно аппаратурное применение в быстродействующих специальных вычислителях (навигация, ракетное дело и др.). При всех преимуществах они имели ограниченный класс функций, реализуемых ими. Их развитие не происходило из-за сложности технической (аппаратурной) реализации. Будучи по сути разностно-итерационными алгоритмами (РИА), они требовали создания методологии проектирования новых функций. Один из авторов подобных РИА, А.М. Оранский, отмечает – «теория РИА разработана недостаточно, и синтез алгоритмов идет эвристическим путем» [3, с. 143].

В основе РИА лежат методы цифрового моделирования какого-либо математического или геометрического объекта (вращающийся вектор, как у [5, 6], или итерационный сходящийся процесс, конечным результатом которого будет искомая функция [3]). В последнем варианте – это будет геометрический объект в виде плоских фигур различной конфигурации.

Методы псевдоповоротов вектора

Это частный случай алгоритмов Волдера [6] и Меджитта [5]. В их основу заложена такая замечательная особенность: два комплексных числа вида (a + jb) и (1 ± j∙2^–i), где i = 0, 1, 2, …, могут быть легко перемножены с применением только линейных операторов, так как умножения на 2^–i заменяются арифметическими сдвигами

(a + jb)∙(1 ± j∙2^–i) = (a ± b∙2^–i) + j∙(b ± a∙2^–i). (1)

Но эту процедуру (1) можно представить так: вектор (а, b) поворачивается на угол ±arctg 2^–i и дополнительно удлиняется в раз.

Организовав слежение за текущим углом поворота вектора, можно получить координаты его конца, пропорциональные косинусу и синусу этого угла. И, наоборот, следя за достижением проекцией конца вектора на оси определенного значения х, можем получить угол, равный arcsin x или arсcos x. Вот этот алгоритм:

Y₀ = y; Y_i = Y_i–1 – E_i–1 2^–(i–1)∙X_i–1; Y_n → 0;

X₀ = x; X_i = X_i–1 – E_i–1 2^–(i–1)∙Y_i–1;

(2)

Q₀ = 0; Q_i = Q^i–1 – E_i–1 2^–(i–1);

где i = 1, 2, …, n – номер итерации; n – разрядность чисел;

Нами разработана модификация РИА (2) для реализации на МП. За основу взят более точный алгоритм Меджитта, а второй этап позаимствован из алгоритма Волдера. Получается более точный и более быстрый РИА:

Y₀ = y; Y_i+1 = 2(Y_i – E_i–1∙X_i); Y_m → 0;

X₀ = x; X_i+1 = X_i + E_i–1 2^–2i∙Y_i;

(3)

Q₀ = 0; Q_i+1 = Q_i + E_i–1 arctg 2^–i;

где i = 0, 1, 2,…, m – номер итерации; m – половинная разрядность чисел .

Обращаем внимание на то, что число итераций сокращено вдвое.

При всех достоинствах РИА (2) и (3) они имеют недостаток – необходимость наличия констант arctg 2^–i.

Простой разностно-итерационный алгоритм

Он называется РИА квазиделения без восстановления остатка и квазиумножения [3]. В немного модернизированном нами (для расширения области сходимости) он имеет такой вид:

q_i–1 = sign W_i–1sign y;

W₀ = w; W_i = W_i–1 – q_i–1∙2^–i+1∙y; W_n → 0;

V₀ = v; V_i = V_i–1 + q_i–1∙2^–i+1∙x;

(4)

где i = 1, 2, …, n – номер итерации; n – разрядность чисел.

Хотя он и называется самым простым, но его основные компоненты (строчки с итерационными выражениями) входят во многие другие более сложные РИА. Например, первая и вторая строки играют роль аддитивного разложения отношения :

(5)

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

Известен и другой – мультипликативный вид разложения (при w > y > 0):

W₀ = 2∙(w – y); W_i+1 = 2∙(W_i – q_i∙Y_i); (6)

Y₀ = y; Y_i+1 = Y_i + q_i∙2^–i∙Yⁱ,

где i = 0, 1, 2..., n – номер итерации; n – разрядность чисел.

В итоге получаем разложения в виде

(7)

которое используется в следующих итерационных выражениях, обеспечивающих различные функциональные преобразования (возведение в целую положительную степень отношения , взятие логарифма и др.).

Алгоритм Оранского и Рейхенберга

Он изобретен [4] для аппаратурной реализации и имеет такой вид (для х > 0, y > 0):

X₀ = x; X_i = X_i–1 – q_i–1∙y∙2^–i;

(8)

Y₀ = y; Y_i = Y_i–1 + q_i–1∙x∙2^–i; Y_n → X_n,

где i = 1, 2, ..., n – номер итерации; n – разрядность чисел.

РИА (8) имеет ограниченную возможность, он вычисляет одну единственную функцию от двух переменных.

С целью расширения области применимости РИА нами были произведены исследования его математической модели и на этой основе – модификация РИА [2].

q_i–1 = sign (X_i–1 – Y_i–1)∙sign (u + w);

X₀ = x; X_i = X_i–1 – q_i–1∙w∙2^–i+1;

(9)

Y₀ = y; Y_i = Y_i–1 + q_i–1∙u∙2^–i+1; Y_n → X_n,

где i – то же самое, что и в (8).

Условие сходимости этого РИА (8) таковы:

(10)

где р (р ≥ 0) – минимальное целое число, обеспечивающее выполнение неравенства

2∙|u∙2^p + w∙2^p| > |x – y|. (11)

Величина, вычисляемая с помощью РИА (9), является средневзвешенной двух величин х и у, взятых с весами u и w. То есть это функция четырех переменных.

Расширение областей применения РИА

Оно состоит в замене исходных значений итерируемых величин некоторыми функциями одного или двух аргументов, которые сами просто вычисляются (т.е. без операций умножения и деления). То есть переходом к сложным функциям (суперпозициям функций) РИА значительно расширяют класс реализуемых функций. Например, простой РИА (4) сможет вычислять не только , но и такую, например, функцию – . Деля ее числитель на знаменатель (как многочлен на многочлен – «уголком»), получаем нужное представление для РИА (4).

(12)

Заменяя u = s + t + 1; w = – (4s + 1); y = s + t; x = t и подставляя их в качестве исходных данных для РИА (4), в итоге получаем сложную функцию

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

Приведем пример таких преобразований для модифицированного РИА (9). Представим x, y, u, w так:

x = k_x∙t + m_x; w = k_w∙t + m_w;

y = k_y∙t + m_y; u = k_u∙t + m_u. (13)

Тогда

(14)

где A = k_x∙k_u + k_y∙k_w;

В = k_x∙m_u + k_u∙m_x + k_y∙m_w + k_w∙m_y;

С = m_x∙m_u + m_y∙m_w;

D = k_u + k_w;

E = m_u + m_w.

Для того чтобы упростить предварительное вычисление x, y, u, w для заданного t, выберем k_i (i Î {x, y, u, w}), равным 0, ±1; ±0,5; ±0,25; …. и т.д. Это позволит заменить умножение k_i∙t арифметическим сдвигом вправо аргумента t c возможностью инвертирования знака результата, если знак у k_i – минус.

Если же требуется решить обратную задачу: назначить такие ki и mi, чтобы Y_n = X_n были равны требуемой функции F(t) на заданном интервале i ∈ (α, β), то находим одну из аппроксимаций F(t) в виде (14), т.е. соответствующий набор коэффициентов А, В, С, D, E.

Опираясь на них, составляем и решаем следующую систему уравнений:

k_x k_u + k_y∙k_w = γ∙A;

k_x∙m_u + k_u∙m_x + k_y∙m_w + k_w∙m_y = γ∙B;

m_x∙m_u + m_y∙m_w = γ∙C; (15)

k_u + k_w = γ∙D;

m_u + m_w = γ∙E,

где γ – технологический коэффициент, сокращающий дробь (14) до значений числителя и знаменателя, удобных для решения системы (15).

Авторами [2] разработан алгоритм и программы решения системы (15) на персональном компьютере с получением k_i и m_i (i ∈ {x, y, u, w}).

Например, для F(t) = tg(t), t ∈ (0, π/4) имеем такой набор коэффициентов k_i и m_i (i ∈ {x, y, u, w}), который позволяет вычислять функцию F(t) (14), максимально приближенную к tg(t) на указанном интервале

k_x = 1; k_y = –1; k_u = 1; k_w = 1/8;

m_x = 0,041332; m_y = 1,000000;

m_u = –1,502386; m_w = 0,060741.

В таблице приведены абсолютные погрешности вычисления функции tg(t).

Библиографическая ссылка