УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ ТАБЛИЧНО-АЛГОРИТМИЧЕСКИМ МЕТОДОМ Российский патент 1999 года по МПК G06F17/17 

Изобретение относится к вычислительной технике и может быть применено в специализированных вычислителях.

Известно устройство для вычисления элементарных функций табличным методом с помощью ПЗУ. [1. Б.В.Шевкопляс. Микропроцессорные структуры. Инженерные решения: Справочник. М.: Радио и связь. 1990 г., стр. 476, рис. 8.8]. Достоинством метода является высокая точность и скорость вычислений. Недостатком является резкое увеличения объема памяти ПЗУ при увеличении числа разрядов. Для данного метода погрешность вычислений при симметричном округлении выходного кода функции не превышает±2^-1 единицы младшего n-го разряда выходного кода функции.

Наиболее близким к заявляемому устройству по технической сущности является устройство для вычисления нелинейных функций методом кусочно-линейной аппроксимации [1, стр. 477, рис. 8.9].

В данном устройстве вычисление функции, например sin β, осуществляется за счет задания кода sin β_j и кода скорости изменения функции kj старших разрядов аргумента угла β_ст в ПЗУ, интерполяции значения приращения функции kj β_мл, определяемого скоростью ее изменения kj и младшими разрядами аргумента угла β_мл между узлами интерполяции j на выходе табличного умножителя и суммированием значений функции в узлах интерполяции sin β_j со значениями приращения функции kj β_мл между узлами интерполяции на сумматоре.

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

где Δsinβ_j и Δk_j - погрешности воспроизведения функции sin β и коэффициента скорости изменения функции kj для интервалов интерполяции j, обусловленные дискретным представлением информации с конечным числом разрядов;
Δ_умн - погрешность при выполнении операции умножения, связанная с отбрасыванием младших разрядов произведения,
Δ_окр - погрешность округления при отбрасывании дополнительных разрядов r при окончательном вычислении значения функции,
δ - погрешность аппроксимации функции полиномом первого порядка, определяется выражением
δ = (β-β_j)(β-β_j+1)sinβ, (2)
Δsinβ_j - погрешность вычисления приращения функции за счет меньшего числа старших разрядов , определяющих узлы аппроксимации j.

Определим более точно значения и δ в соответствии с работами автора [2. В. В.Чекушкин. Быстродействующие цифровые функциональные преобразователи для вычисления тригонометрических функций синуса и косинуса. "Измерительная техника", Москва, N 6 или 7, 1996 г. (в печати)].

Если входной параллельный код угла β при изменении его от 0 до 90^o определяется выражением

и разбивается на группы старших и младших разрядов

то при использовании частного случая линейной интерполяции между узлами интерполяции j получим (принимаем sinβ_ст = sinβ_j) )
sin(β_ст+β_мл) = sinβ_ст+k_jβ_мл. (5)
Для этого уравнения максимальная погрешность вычисления функции определяется выражением (1).

Определим дополнительную погрешность вычисления приращения функции sin β между узлами интерполяции, когда число разрядов которое используется для вычисления приращения меньше, чем β_ст, на значение b.

Приращение функции Δsinβ_j = k_jβ_мл между узлами интерполяции j, когда для полного представления функции и аргумента от 0 до 90^o используется n разрядов, будет равно [2].

Максимальное приращение аргумента β_мл между узлами интерполяции в соответствии с выражением (4) при всех β_m = 1 в единицах младшего разряда кода угла β
β_мл = 2^n-g-1. (7)
Если число разрядов равно g - b, то в соответствии с выражениями (4), (6), (7) получим значение погрешности в единицах младшего разряда

Максимальное значение погрешности при отсутствии дополнительных разрядов в первом блоке памяти и симметричном округлении
Δsinβ_j = 2^-n-1. (9)
Если для представления функции sin β используется при выполнении промежуточных вычислений r дополнительных разрядов, выходящих за n-разрядную сетку результата, то
Δsinβ_j = 2^-n-r-1 (10)
максимальное значение погрешности δ представляется выражением
δ = π²•2^-2g-5. (11)
Погрешность вычисления Δ_умн при отбрасывании дополнительных разрядов, следующих за разрядом r.

Δ_умн = 2^-n-r. (12)
Погрешность Δ_окр определяется выражением
Δ_окр = 2^-n-1-2^-n-r-1. (13)
Значения погрешностей Δsinβ_j и Δ_окр в прототипе отсутствуют, если число разрядов адресации ПЗУ kj соответствует g и если дополнительные разряды r отсутствуют.

Целью настоящего изобретения является уменьшение погрешности вычислений функции, фактически приближающееся к значению ±(2^-1+2^-f) единиц n-го младшего разряда выходного кода функции, а также повышение скорости вычислений. Здесь f обозначает число дополнительных разрядов, следующих за младшим n-ым разрядом, которые используются только для определения погрешности воспроизведения функции на этапе предварительных вычислений на ЭВМ, а не в устройстве. В заявляемом устройстве практически полностью компенсируется погрешность Δk_j, уменьшается или совсем отсутствует значение погрешности Δ_умн, уменьшается значение погрешности δ.

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

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

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

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

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

5. Выход первого блока памяти содержит дополнительно r разрядов.

6. Первый сумматор содержит третий и четвертый сумматоры, входы первого и второго слагаемых третьего сумматора являются соответствующими входами первого сумматора, а выход соединен с первым входом четвертого сумматора, выход которого является выходом результата устройства, а на вход второго слагаемого подана константа, соответствующая 1/2 единицы младшего разряда выходного n-разрядного кода результата.

7. Третий блок памяти содержит дополнительно r разрядов.

Сущность изобретения поясняется фиг. 1 - 6. Устройство для вычисления элементарных функций (фиг. 1) содержит 1 и 2 входы устройства - входы старших β_ст и младших β_мл разрядов аргумента, первый блок памяти 3, блок приращения функции 4, его выход 5, первый сумматор 6, выход результата устройства 7. Блок приращения функции с мультиплексором (фиг. 2) содержит второй блок памяти 8, мультиплексор 9. Блок приращения функции с блоком памяти (фиг. 3) содержит третий блок памяти 10. Блок приращения функции с умножителем (фиг. 4) содержит четвертый блок памяти 11 и умножитель 12. Блок приращения функции с умножителем и блоком коррекции содержит пятый и шестой блоки памяти 13 и 14, умножитель 15, второй сумматор 16. Первый сумматор 6 с дополнительным сумматором (фиг. 6) содержит третий и четвертый сумматоры 17 и 18.

Блоки памяти 3, 8, 10, 11, 13, 14 выполнены, например, на микросхемах ПЗУ типа 556 РТ7, имеющих 11 входных и 8 выходных разрядов, и соединяются по типовой схеме. Сумматоры выполнены на микросхемах сумматоров 133 ИМ3 или арифметико-логического устройства 155 ИП3. Мультиплексор 9 состоит из нескольких адресных мультиплексоров 133 КП5.

Применение второго блока памяти для непосредственного вычисления всех приращений функции между узлами интерполяции по значениям всех старших разрядов с передачей на выход блока приращения функции приращения функции, определяемого младшими разрядами аргумента на управляющем входе мультиплексора, обеспечивает исключение погрешностей Δk_j, Δ_умн, Δ_окр, а погрешность Δsinβ_ст и вновь появляющаяся погрешность воспроизведения приращения функции Δsinβ_n взаимокомпенсируются, поскольку значения приращений функции воспроизводятся с учетом знака и абсолютного значения погрешности Δsinβ_ст. Компенсация состоит в том, что погрешность приращения функции, обусловленная дискретным представлением информации с конечным числом разрядов, как бы будет "спрятана" в погрешности Δsinβ_ст путем применения специального алгоритма прошивки второго блока памяти 8. В данной структуре исключен умножитель и поэтому выше быстродействие.

Сравним различные методы, например, при β = n = 13, g = 11, f = 2, для табличного метода с ПЗУ получим емкость ПЗУ A = 2¹³•13 бит. Для такой реализации требуется 8 микросхем ПЗУ 556 РТ7, погрешность Δsinβ = 2^-14.
Для устройства фиг. 2 определим на этапе предварительных вычислений на ЭВМ вне устройства значения функции sin β_j с числом разрядов n+f и симметричным округлением. Проведем симметричное округление sin β_j при отбрасывании f дополнительных разрядов, для всех значений sin β_j составим таблицу значений погрешностей Δsinβ_j. Значения функции "прошиваем" в первом блоке памяти 3.

Точно такие же действия производим со значениями приращений функции внутри всех узлов интерполяции. Но эти значения не зашиваем сразу во второй блок памяти 8, а проводим предварительную оценку погрешности результата функции по составляющим погрешностей первого блока памяти и погрешностям блока приращения функции по специальному алгоритму. Корректируем приращения функции во втором блоке памяти 8, чтобы результирующая погрешность была
Δsinβ < (2^-1+2^-f)2^-n.
Только после этого осуществим "прошивку" второго блока памяти 8.

Приведем пример сравнительной оценки двух структур прототипа и предлагаемой при β = n = 13, β_ст = g = 11, зададим f = 2. Значения функции sin β_j будут определены в узлах интерполяции j при симметричном округлении с погрешностью 2^-16n₀.

Если в узлах интерполяции значения погрешностей sin β_ст после отбрасывания f дополнительных разрядов будут находиться в интервале
0 ≤ Δsinβ_ст ≤ 0,5•2^-13
и погрешность воспроизведения приращения Δsinβ_n > 0,5•2^-13, то округляем значения приращения функции внутри интервала аппроксимации в большую сторону и тогда значение результирующей погрешности Δsinβ будет отрицательного знака, но по абсолютной величине меньше 0,5•2^-13, составляющие погрешности как бы компенсируют друг друга. Поскольку обе составляющие на этапе предварительных вычислений определены с погрешностью 2^-16, то результирующая погрешность
Δsinβ < (0,5•2^-13+2^-15).
Если же 0 < Δsinβ_n < 0,5•2^-16 , то дальнейшее вычисление приращения определяется таблицей (см. в конце описания).

Число разрядов f на этапе предварительных вычислений можно увеличить. Таким образом, значение погрешности результата
Δsinβ ≤ 0,5•2^-13.
Определим аппаратурные затраты и погрешность для прототипа [1]. С учетом того, что ПЗУ kj можно реализовать на свободных выводах ПЗУ 556 РТ7 функции sin β_ст , а на умножитель (3•2) разряда с симметричным округлением используем одно ПЗУ 556 РТ7, эквивалентно сумматор равен одному ПЗУ 556 РТ7, получим суммарно аппаратные затраты для прототипа: 4 корпуса 556 РТ7.

Суммарная погрешность Δsinβ = Δsinβ_j+Δ_умн+Δk_j = 1,5•2^-13.
В нашем случае (фиг. 2) надо 12 выходов с ПЗУ приращения, чтобы на 4 значения внутри каждого узла интерполяции j в соответствии с выражением (6) иметь трехразрядные приращения. С учетом 5 свободных выходов ПЗУ sin β_ст первого блока памяти 3 на второй блок памяти 8 необходимо дополнительно одно ПЗУ 556 РТ7. Также необходимо 3 микросхемы мультиплексора 133 КП5. Эквивалентные аппаратурные затраты = 4,5 корпуса ПЗУ 556 РТ7. Но мультиплексор, как правило, имеет в 2 раза выше быстродействие. Итак, в нашем случае погрешность преобразования в 3 раза меньше, меньше и время преобразования.

Но такая структура эффективна, когда число младших разрядов изменяется в пределах от 1 до 3, а для структуры фиг. 3 (1 - 6). Применение третьего блока памяти для непосредственного вычисления приращения функции между узлами интерполяции по значениям части старших и всех младших разрядов аргумента обеспечивает исключение погрешностей Δk_j и Δ_умн, исключение умножителя, позволяет на этапе предварительных вычислений с учетом значений погрешности вычисления функции в узлах интерполяции Δsinβ_ст подобрать для ряда точек такие значения приращений функции между узлами интерполяции, что результирующая погрешность вычисления функции для них практически не будет превышать погрешности Δsinβ_ст.

В то же время суммарная погрешность

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

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

При n = 15, g = 11 и b = 3 получим погрешности и аппаратурные затраты без использования дополнительных разрядов r: на реализацию ПЗУ sin β_ст - 2 ПЗУ 556 РТ7, третий блок памяти 10 имеет 8 входов по β_ст , 4 по β_мл и 5 выходных разрядов. Суммарные аппаратурные затраты составят 5 ПЗУ 556 РТ7. Значение погрешности
Δsinβ = (0,5+0,5+0,147)•2^-15 = 1,147•2^-15, поскольку при r = 0, Δ_окр = 0.
Если же сделать один дополнительный разряд r = 1 (аппаратурные затраты не возрастают, поскольку в первом сумматоре имеется возможность на вход переноса из младшего разряда подключить константу 2^-16 для осуществления симметричного округления результата), то получим
Δsinβ = (0,25+0,25+0,147+0,25)•2^-15= 0,897•2^-15.
Здесь Δsinβ_j = Δsinβ_n = Δ_окр = 0,25.
Первый и третий блоки памяти 3 и 4 имеют собственно 16 и 6 выходных разрядов.

При числе младших разрядов более 6 целесообразно использовать умножитель фиг. 4. Выбор константы kj по аналогии с предлагаемым выбором констант приращения функции обеспечивает аналогично компенсацию погрешности Δk_j в выражении (1). В этом отличие прошивки четвертого блока памяти 11 от блока памяти в прототипе. Без дополнительных аппаратурных затрат уменьшаем результирующую погрешность. Еще больше можно уменьшить погрешности, применяя дополнительные разряды. Если число дополнительных разрядов r больше 1, то вводят вместо обычной структуры первого сумматора 6 структуру первого сумматора с дополнительным сумматором, позволяющим производить симметричное округление выходного результата при числе разрядов r больше 1.

При g>n/2 погрешность δ в соответствии с (11) обычно не учитывается. Действительно, пусть n=16, g=9, получим δ_max = 0,3•2^-18.

При числе разрядов β > 20 значение g брать более 11 накладно из-за увеличения аппаратурных затрат. Поэтому вводим структуру блока приращения функции с умножителем и блоком коррекции. Шестой блок памяти 14 воспроизводит приближенное текущее значение погрешности аппроксимации как функции части старших и младших разрядов аргумента. Введение такого блока обеспечивает значительное снижение погрешности δ при g<n/2 примерно на 8 разрядов. Например, при n = 26 примем g = 12. Для прототипа мы бы имели
δ_max = 0,3•2^-24, т.е 1,2•2^-26.
При больших n погрешность возрастет.

У нас же получаются приемлемые аппаратурные затраты, поскольку можно использовать стандартный умножитель 16•16 разрядов. В нашем случае: ПЗУ sin β_ст - 8 ПЗУ 556РТ7, ПЗУ kj - 4 ПЗУ 556 РТ7, шестой блок памяти 14 - 1 ПЗУ 556 РТ7, умножитель 16•16.

Общее число корпусов ПЗУ 556РТ7 примерно 18. Для прототипа надо было брать g = 14, чтобы исключить погрешность δ. Аппаратурные затраты возросли бы более чем в 3 раза. У нас же погрешность δ в соответствии с выражением (2) при 8-разрядном выходном коде легко уменьшить в 10 и более раз. Фактически мы опять корректируем погрешность задания коэффициента kj, что подчеркивает единство изобретения.

Опишем работу устройства по фиг. 1,5 при значении одного дополнительного разряда r. Входной код угла β аргумента, разделенный на группы старших и младших разрядов (всего 26 разрядов, g = 12 разрядов), подается на первый блок памяти 3 и блок приращения функции 4. С первого блока памяти 3 на вход первого слагаемого 6 подается 27-разрядный код функции sin β_j, на вход переноса с младшего разряда 27-разрядного первого сумматора подается константа симметричного округления 2^-27. Пятый блок памяти 13 формирует коэффициент kj с числом разрядов 16. С выходов умножителя (16•14 разрядов) и шестого блока памяти на входы второго сумматора 16 подаются k_jβ_мл и трехразрядный код коррекции погрешности δ. Значит δ_max = 2^-3•2^-26. Если сложим во втором сумматоре 16 два слагаемых с числом дополнительных разрядов r = 2 и симметрично округлим результат, путем подачи на вход переноса второго сумматора 16 константы 2^-28, то получим погрешность приращения функции 0,375•2^-26. Погрешности Δsinβ_j и погрешность округления в первом сумматоре 5 будут равны по 0,25•2^-26. Суммарная погрешность составит 0,875•2^-26. В прототипе ее значение было бы равно 2,7•2^-26.

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

Результаты работы, в частности, апробированы при рецензировании в журналах "Измерительная техника", "Известия вузов", "Приборостроение". Проведено моделирование на персональной ЭВМ.

Устройство осуществляет вычисление функций путем задания опорных значений функций в узлах интерполяции. Интерполяция значений приращения функции осуществляется между узлами интерполяции в блоке приращения значений функций. Технический результат заключается в выполнении взаимной компенсации погрешностей воспроизведения функции на выходе результата устройства, обусловленных дискретным представлением информации в узлах интерполяции и блоке приращений значений функции с конечным числом разрядов и уменьшением влияния на результирующую погрешность вычисления погрешности задания скорости изменения функции между узлами интерполяции полиномом первого порядка. В зависимости от числа разрядов преобразуемого кода n и емкости памяти ПЗУ предлагаются четыре структуры реализации блока приращения функции. Число разрядов n находится в пределах 11-32. Значение погрешности вычисления функции соответствует 0,5-0,75 единицы младшего разряда результата. 6 ил., 1 табл.

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