Forbidden

You don't have permission to access /zzz_siteguard.php on this server.

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ ТАБЛИЧНО- АЛГОРИТМИЧЕСКИМ МЕТОДОМ - Патент РФ 2136041
Главная страница  |  Описание сайта  |  Контакты
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ ТАБЛИЧНО- АЛГОРИТМИЧЕСКИМ МЕТОДОМ
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ ТАБЛИЧНО- АЛГОРИТМИЧЕСКИМ МЕТОДОМ

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ ТАБЛИЧНО- АЛГОРИТМИЧЕСКИМ МЕТОДОМ

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

1. С помощью поисковых систем

   С помощью Google:    

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2136041
Класс(ы) патента: G06F17/17
Номер заявки: 96111307/09
Дата подачи заявки: 04.06.1996
Дата публикации: 27.08.1999
Заявитель(и): Муромский институт Владимирского государственного технического университета
Автор(ы): Чекушкин В.В.
Патентообладатель(и): Муромский институт Владимирского государственного технического университета
Описание изобретения: Изобретение относится к вычислительной технике и может быть применено в специализированных вычислителях.
Известно устройство для вычисления элементарных функций табличным методом с помощью ПЗУ. [1. Б.В.Шевкопляс. Микропроцессорные структуры. Инженерные решения: Справочник. М.: Радио и связь. 1990 г., стр. 476, рис. 8.8]. Достоинством метода является высокая точность и скорость вычислений. Недостатком является резкое увеличения объема памяти ПЗУ при увеличении числа разрядов. Для данного метода погрешность вычислений при симметричном округлении выходного кода функции не превышает±2-1 единицы младшего n-го разряда выходного кода функции.
Наиболее близким к заявляемому устройству по технической сущности является устройство для вычисления нелинейных функций методом кусочно-линейной аппроксимации [1, стр. 477, рис. 8.9].
В данном устройстве вычисление функции, например sin β, осуществляется за счет задания кода sin βj и кода скорости изменения функции kj старших разрядов аргумента угла βст в ПЗУ, интерполяции значения приращения функции kj βмл, определяемого скоростью ее изменения kj и младшими разрядами аргумента угла βмл между узлами интерполяции j на выходе табличного умножителя и суммированием значений функции в узлах интерполяции sin βj со значениями приращения функции kj βмл между узлами интерполяции на сумматоре.
Недостатком данного устройства является увеличение погрешности воспроизведения функции по сравнению с табличным методом, поскольку ее максимальное значение в общем случае определяется выражением

где Δsinβj и Δkj - погрешности воспроизведения функции sin β и коэффициента скорости изменения функции kj для интервалов интерполяции j, обусловленные дискретным представлением информации с конечным числом разрядов;
Δумн - погрешность при выполнении операции умножения, связанная с отбрасыванием младших разрядов произведения,
Δокр - погрешность округления при отбрасывании дополнительных разрядов r при окончательном вычислении значения функции,
δ - погрешность аппроксимации функции полиномом первого порядка, определяется выражением
δ = (β-βj)(β-βj+1)sinβ, (2)
Δsinβj - погрешность вычисления приращения функции за счет меньшего числа старших разрядов , определяющих узлы аппроксимации j.
Определим более точно значения и δ в соответствии с работами автора [2. В. В.Чекушкин. Быстродействующие цифровые функциональные преобразователи для вычисления тригонометрических функций синуса и косинуса. "Измерительная техника", Москва, N 6 или 7, 1996 г. (в печати)].
Если входной параллельный код угла β при изменении его от 0 до 90o определяется выражением

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

то при использовании частного случая линейной интерполяции между узлами интерполяции j получим (принимаем sinβст = sinβj) )
sin(βстмл) = sinβст+kjβмл. (5)
Для этого уравнения максимальная погрешность вычисления функции определяется выражением (1).
Определим дополнительную погрешность вычисления приращения функции sin β между узлами интерполяции, когда число разрядов которое используется для вычисления приращения меньше, чем βст, на значение b.
Приращение функции Δsinβj = kjβмл между узлами интерполяции j, когда для полного представления функции и аргумента от 0 до 90o используется n разрядов, будет равно [2].

Максимальное приращение аргумента βмл между узлами интерполяции в соответствии с выражением (4) при всех βm = 1 в единицах младшего разряда кода угла β
βмл = 2n-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·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-ым разрядом, которые используются только для определения погрешности воспроизведения функции на этапе предварительных вычислений на ЭВМ, а не в устройстве. В заявляемом устройстве практически полностью компенсируется погрешность Δkj, уменьшается или совсем отсутствует значение погрешности Δумн, уменьшается значение погрешности δ.
Поставленная цель достигается тем, что в устройстве для вычисления элементарных функций таблично-алгоритмическим методом, содержащем первый блок памяти, воспроизводящий значения функции в узлах интерполяции, соответствующих старшим разрядам аргумента, блок приращения функции, воспроизводящий приращения функции между узлами интерполяции в соответствии со значениями старших и младших разрядов аргумента, первый сумматор, вход первого слагаемого которого соединен с выходом первого блока памяти, а выход является выходом результата устройства, первый вход устройства, представляющий группу старших разрядов аргумента, соединен с адресными входами первого блока памяти и первым входом блока приращения функции, второй вход устройства, представляющий группу младших разрядов аргумента, соединен со вторым входом блока приращения функции, выход которого соединен со входом второго слагаемого сумматора, приращения значений функции между узлами интерполяции в блоке приращения функции воспроизводятся с учетом знаков и абсолютных величин погрешностей воспроизведения функции в узлах интерполяции в первом блоке памяти, обусловленных дискретным представлением информации с конечным числом разрядов и уменьшенным влиянием на результирующую погрешность вычисления функции на выходе результата устройства погрешности коэффициента скорости изменения функции между узлами интерполяции.
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.
Применение второго блока памяти для непосредственного вычисления всех приращений функции между узлами интерполяции по значениям всех старших разрядов с передачей на выход блока приращения функции приращения функции, определяемого младшими разрядами аргумента на управляющем входе мультиплексора, обеспечивает исключение погрешностей Δkj, Δумн, Δокр, а погрешность Δsinβст и вновь появляющаяся погрешность воспроизведения приращения функции Δsinβn взаимокомпенсируются, поскольку значения приращений функции воспроизводятся с учетом знака и абсолютного значения погрешности Δsinβст. Компенсация состоит в том, что погрешность приращения функции, обусловленная дискретным представлением информации с конечным числом разрядов, как бы будет "спрятана" в погрешности Δsinβст путем применения специального алгоритма прошивки второго блока памяти 8. В данной структуре исключен умножитель и поэтому выше быстродействие.
Сравним различные методы, например, при β = n = 13, g = 11, f = 2, для табличного метода с ПЗУ получим емкость ПЗУ A = 213·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-16n0.
Если в узлах интерполяции значения погрешностей 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умн+Δkj = 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). Применение третьего блока памяти для непосредственного вычисления приращения функции между узлами интерполяции по значениям части старших и всех младших разрядов аргумента обеспечивает исключение погрешностей Δkj и Δумн, исключение умножителя, позволяет на этапе предварительных вычислений с учетом значений погрешности вычисления функции в узлах интерполяции Δ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 по аналогии с предлагаемым выбором констант приращения функции обеспечивает аналогично компенсацию погрешности Δkj в выражении (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 подаются kjβмл и трехразрядный код коррекции погрешности δ. Значит δ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 предложен набор структур для воспроизведения функции, превосходящий прототип.
Результаты работы, в частности, апробированы при рецензировании в журналах "Измерительная техника", "Известия вузов", "Приборостроение". Проведено моделирование на персональной ЭВМ.
Формула изобретения: Устройство для вычисления элементарных функций таблично-алгоритмическим методом, содержащее первый блок памяти значений функции в узлах интерполяции, соответствующих старшим разрядам аргумента, блок приращения значений функции между узлами интерполяции в соответствии со значениями старших и младших разрядов аргумента, первый сумматор, вход первого слагаемого которого соединен с выходом первого блока памяти, а выход является выходом результата устройства, первый вход устройства, представляющий группу старших разрядов аргумента, соединен с адресными входами первого блока памяти значений функции и первым входом блока приращения значений функции, второй вход устройства, представляющий группу младших разрядов аргумента, соединен со вторым входом блока значений приращения функции, выход которого соединен со входом второго слагаемого сумматора, отличающееся тем, что блок приращения значений функции выполнен с возможностью воспроизведения приращения значений функции между узлами интерполяции с учетом знаков и абсолютных величин погрешностей воспроизведения функции в узлах интерполяции, а также взаимокомпенсации дополнительной погрешности вычисления приращения функции и погрешности вычисления приращения функции за счет меньшего числа старших разрядов в блоке приращения значений функции.