устройство для вычисления элементарных функций таблично- алгоритмическим методом

Формула изобретения

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

Описание изобретения к патенту

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

Известно устройство для вычисления элементарных функций табличным методом с помощью ПЗУ. [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,52^-13

и погрешность воспроизведения приращения sin_n > 0,52^-13, то округляем значения приращения функции внутри интервала аппроксимации в большую сторону и тогда значение результирующей погрешности sin будет отрицательного знака, но по абсолютной величине меньше 0,52^-13, составляющие погрешности как бы компенсируют друг друга. Поскольку обе составляющие на этапе предварительных вычислений определены с погрешностью 2^-16, то результирующая погрешность

sin < (0,52^-13+2^-15).

Если же 0 < sin_n < 0,52^-16 , то дальнейшее вычисление приращения определяется таблицей (см. в конце описания).

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

sin 0,52^-13.

Определим аппаратурные затраты и погрешность для прототипа [1]. С учетом того, что ПЗУ kj можно реализовать на свободных выводах ПЗУ 556 РТ7 функции sin _ст , а на умножитель (32) разряда с симметричным округлением используем одно ПЗУ 556 РТ7, эквивалентно сумматор равен одному ПЗУ 556 РТ7, получим суммарно аппаратные затраты для прототипа: 4 корпуса 556 РТ7.

Суммарная погрешность sin = sin_j+_умн+k_j = 1,52^-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,1472^-15, поскольку при r = 0, _окр = 0.

Если же сделать один дополнительный разряд r = 1 (аппаратурные затраты не возрастают, поскольку в первом сумматоре имеется возможность на вход переноса из младшего разряда подключить константу 2^-16 для осуществления симметричного округления результата), то получим

sin = (0,25+0,25+0,147+0,25)2^-15= 0,8972^-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,32^-18.

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

_max = 0,32^-24, т.е 1,22^-26.

При больших n погрешность возрастет.

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

Общее число корпусов ПЗУ 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. С выходов умножителя (1614 разрядов) и шестого блока памяти на входы второго сумматора 16 подаются k_jмл и трехразрядный код коррекции погрешности . Значит _max = 2^-32^-26. Если сложим во втором сумматоре 16 два слагаемых с числом дополнительных разрядов r = 2 и симметрично округлим результат, путем подачи на вход переноса второго сумматора 16 константы 2^-28, то получим погрешность приращения функции 0,3752^-26. Погрешности sin_j и погрешность округления в первом сумматоре 5 будут равны по 0,252^-26. Суммарная погрешность составит 0,8752^-26. В прототипе ее значение было бы равно 2,72^-26.

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

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