Содержание к диссертации
Введение
ГЛАВА I. Аппаратная реализация кусочно-квадратичной аппроксимации 14
1.1. Общие замечания 15
1.2. Аппаратная реализация метода кусочно-квадратичной аппроксимации (ККА) 17
1.2.1. Итерационный алгоритм на основе метода ККА 17
1.2.2. Структуры таблично-алгоритмического функционального преобразователя (ТАШ) на основе метода ККА 24
1.2.3. Модификация итерационного алгоритма на основе метода ККА 29
1.2.4. Структуры модифицированного ТАШ 33
1.3. Оценка быстродействия и аппаратурных затрат предлагаемых ТАШ для вычисления гиперболических функций 42
1.3.1. Определение значений параметров ТАШ 42
1.3.2. Оценка быстродействия 51
1.3.3. Оценка аппаратурных затрат 56
1.4. Методика проектирования ТАШ для класса гиперболических функций 64
1.5. Сравнительный анализ предлагаемых и известных структур ТАШ 71
Выводы по главе 80
ГЛАВА 2 Матричного типа на основе метода водцера 82
2.1. Исследование метода Волдера для гиперболических функций 83
2.1.1. Геометрическая интерпретация метода Волдера для гиперболических функции и вывод рекуррентных соотношений 84
2.1.2. Сходимость метода Волдера для гиперболических функций 97
2.1.2.1. Синхронный алгоритм 103
2.1.2.2. Асинхронный алгоритм 110
2.1.2.3. Минимальный асинхронный алгоритм 117
2.1.3. Компенсация коэффициента деформации вектора 121
2.2. Матричная реализация гиперболических функций 125
2.2.1. Матричные вычислительные устройства (МВУ) . Общие замечания 125
2.2.2. МВУ для вычисления функций shx ж chx 127
2.2.3. Улучшение характеристик управляющей матрицы МВУ для вычисления Snx и chx 130
2.2.3.1. Исключение ячейки знакового разряда 130
2.2.3.2. Диагональное усечение 133
2.2.4. МВУ для вычисления функций Arfh(y/x) ,Arcih(X/y)
и ]/xz-f 142
2.2.5. МВУ с коррекцией 144
2.3. Оценка быстродействия и аппаратурных затрат МВУ 150
Выводы по главе 154
ГЛАВА 3. Аппаратная реализация таблично -матричного типа на основе метода водцера для функций shxi/ichx 157
3.1. Исследование входно-выходнои зависимости управляющей матрицы 157
3.1.1. Входно-выходная зависимость управляющей матрицы 157
3.1.2. Анализ входно-выходнои зависимости управляющей матрицы 160
3.2. Аппроксимация входно-выходнои зависимости управляющей матрицы 170
3.3. Аппаратная реализация кусочно-линейной аппроксимации управляющей функции 187
3.3.1. Таблично-Матричные устройства для вычисления
функций Shx и chx . 187
3.3.2. Улучшение таблично-матричных устройств с аппрокси
мацией управляющей функции 195
3.4. Алгоритм определения управляющих сигналов с прогнозированием 200
3.5. Таблично-матричные устройства с прогнозированием значений управляющих сигналов 206
Выводы по главе 212
Заключение 214
Литература
- Аппаратная реализация метода кусочно-квадратичной аппроксимации (ККА)
- Модификация итерационного алгоритма на основе метода ККА
- Геометрическая интерпретация метода Волдера для гиперболических функции и вывод рекуррентных соотношений
- Анализ входно-выходнои зависимости управляющей матрицы
Аппаратная реализация метода кусочно-квадратичной аппроксимации (ККА)
Алгоритм вычисления функции u=j(x) на основе метода ККА, описываемый в данном разделе, базируется на следующем способе реализации кусочно-квадратичной аппроксимации с равными подинтервалами /56/.
Принимаем, что для каждого подинтервала в таблице хранятся значения функции на концах подинтервала и значение поправки CLo, величина которой такова, что её добавка к линейному приближению в середине интервала точно компенсирует погрешность линейной аппроксимации: ao-ft- -J— {1 з) где Цн Цк - значения функции в точке начала и конца подинтервала, соответственно; ус - значение аппроксимирующей квадратичной функции в середине подинтервала.
Вычисление искомого значения функции u=j(x) сводится к последовательному делению подинтервала по полам и определению значений функции на концах нового подинтервала с помощью значений функций и поправки предыдущего подинтервала. При этом используется следующее свойство квадратичной поправки: новое значение поправки в четыре раза меньше предыдущего. Описанная последовательность операций повторяется циклически до отработки бит за битом интерполирующей части аргумента
Приведем доказательство вышеуказанного свойства квадратичной поправки (1.3) для второго цикла описанного вычислительного процесса. Рассмотрим элементарный участок функции i=j(x) , аппроксимируемый квадратичной зависимостью (Х)=Ах2+&х+С # докажем, что йі-ОоІЧ (рис.1.1).
Алгоритм вычисления элементарной функции U j(x) , основанный на вышеизложенном способе выполнения кусочно-квадратичной аппроксимации, строится при следующих исходных предпосылках:
1. Рассматривается область задания аргумента Хб [0, і)
2. Интервал задания аргумента разбит на ь- 2 равных участков аппроксимации; длина элементарного участка аппроксимации равняется 11=:2 .
3. Аргумент задан в виде (/Поразрядного двоичного кода: X-Xo,Xi... Хщ , где Хо - знаковый разряд. Алгоритм состоит из 11-ти пунктов.
П.І. По значению старлей части аргумента X определяем значения функции U=-J(X)B точках начала Ш={(Хн) и конца U J(XK) подинтервала и значение квадратичной поправки а. , удовлетворяющей условию:
Замечание. Значения квадратичной поправки могут быть как положительными, так и отрицательными в зависимости от характера графика функции U-j(x), Если функция выпуклая - Сі У О , в случае вогнутой функции - CL 0. П.2. Значение і , определяющее номер цикла, равно нулю. Длина исходного сегмента h= Х -Хц . II.3. Приращение индекса циклов: L -— L + 1 П. 4. Если Х=Хн, то переход к П. 10. П.5. Определяем значение полинома в точке середине подин тервала: Ус - (Цн + у/ + 2а)/2 » П.6. Если X XH+h/2L, то ук: = Ус » Xx .-XH+h/2L и переход к П.8. П.7. Если X ,XH+h/2L, то ун:= Ус , И: XH-hh/2L П.8. Значение квадратичной поправки уменьшаем в четыре раза: П.9. Если l , то переход к П.З. П.10. Результат квадратичной аппроксимации равен значению полинома в начале подинтервала: j(x)- у# П.II. Конец.
Комментарий. Пункты П.2 + П.9 вышеизложенного алгоритма отражают процесс квадратичной интерполяции, в результате которого на основе значения функции в узлах и поправки получаем значение интерполирующего полинома в точке, определенной аргументом X . Символом t-rtl-S обозначено количество циклов процесса квадратичной интерполяции.
Дальше описанный алгоритм выполнения квадратичной аппроксимации функции j(x) подвергается формализации и преобразованию с целью получения алгоритма, наиболее пригодного для аппаратной реализации.
Модификация итерационного алгоритма на основе метода ККА
С Целью более эффективного использования оборудования ТІШ на рис.1.3 и увеличения его быстродействия в данном разделе изыскиваются возможности выделения малоразрядных блоков обработки устройства путем эквивалентных преобразований вышеизложенного алгоритма ККА.
Модификация алгоритма направлена на распараллеливание вычислительного процесса.
Проанализируем процесс вычисления промежуточных результа-тов Uj\ и uji . Как видно из ранее рассмотренного алгоритма, они являются функциями от величин Цц , Цк , CL ж кода Xs+f st Ції = І1 (У« У ,а XSH XS+2 - XS+t Ук = &(ун ук XSH9XS+29...9ZSH) С1-14) Каждая из этих функций представляет собой декомпозицию двух функций: ЬЦн,1}к7ъ ,Хзн - хм)= У2 (ун,Цк %н Хт)+ %2(a;XSH " zri Согласно этому ,в выражениях для промежуточных результатов Uj: и у можно выделить две составляющие, соответствующие функциям if : Ч н = LLH + СІ (1.15) П = L\ + % Запишем рекуррентные соотношения для вычисления промежуточ » ных результатов Цц и ujr с учетом (I.I5). lH_ l(LLH+ )/2+( + 2 2 )/2 , если xi+Sifi (I.I6) {]}»+& . если Xi+SHS К- / к+ » ЄСЛИ i+5ff= " " [(d+ )/2fd+d+2a-2-29/2 , если :г/+5+,=0 где і = 0,1,2,..., (t-1) НУ: н-унЛк=ук,С Сок-0. Результат: $ (x) uHf-1H + CH
Поскольку, как было показано (I.16), определение результата квадратичной интерполяции сводится к нахождению алгебраической суммы величин LH и LH , будем добиваться сокращения вычислений, необходимых для получения этих величин.
Проанализировав механизм образования переменной /.# , нетрудно убедиться, что её значение лежит на прямой, описываемой уравнением:
С учетом h=XK-XH-2 получаем следующую простую зависимость для определения величины LH : & = Ун + (ук-уи 0 х +1Ъ+г - Xs+t -I8) где 0,3CSi.1t..Xs+t - младшая часть аргумента, сдвинутая на 5 разрядов влево.
Определение величины Сн можно упростить, принимая во внимание разрядность Сі, квадратичной поправки U . Если j=entCq,[2J, то после выполнения итераций 0,1,...,J итерационного процесса (I.I6) величина CL.2 выходит за пределы разрядной сетки. Кроме того, CH CK=z0 Что упрощает вычисление С и и Ск .С учетом этих соображений выражения для вычисления С н и С к приобретают следующий вид:
Реализация алгоритма по формулам (1.24) или (1.25) дает большой выигрыш в аппаратурных затратах и по быстродействию, поскольку удается применить малоразрядные матричные умножители, выделить отдельно малоразрядный блок обработки суммарной поправки, а также обеспечить совмещенное выполнение операций.
На рис.1.4 изображена структурная схема ТАШ для вычисления функции U=j(x) на интервале «["0,1) , построенная на базе соотношений (1.24) и (I.I9) (1.22). Б отличие от схемы на рис.1.3 ПЗУ хранить одинарное значение поправки CL вместо 2d. Дополнительные блоки на рис.1.4: 1. Вычитатель Б, формирующий значение разности Чн Цк 2. Матричный умножитель МУ. В качестве умножителя используется величина 3Cs+i-"%s+t $ а. в качестве множимого значение разности Цк Н На выходе умножителя получается дополнительный код произведения, т.к. множитель всегда положителен. 3. Сумматор CM-I на два входа, вычисляющий значение /}н = ЦН + (ук-ун)-0,XS+1... XSft 4. (t -j) сумматоров СМІ, СМ(ЗИ) CM(7V) на два входа, принимающих участие в вычислении величины Сн . 5. j-4 сумматора СМ2 СЩ на три входа, принимающие участие в вычислении величин Сн и С к 6. [2Ї-І) мультиплексора Ш на два входа, принимающие участие в итерациях для вычисления величины Сн .
Геометрическая интерпретация метода Волдера для гиперболических функции и вывод рекуррентных соотношений
Рекуррентные формулы для вычисления гиперболических функций по методу Волдера приводятся во многих работах. Как правило, вывод этих формул обосновывается известной аналогией между тригонометрическими и гиперболическими функциями /11,17,20,21,47,48, 86,91,96/. В /62/ сделана попытка более глубокого анализа этого вопроса, но так как используется главным образом понятийная сторона привлекаемого математического аппарата, выводы имеют интуитивный характер и не являются следствием строго формального доказательства.
При работе над аппаратной реализцией гиперболических функ ций по методу Болдера возникает необходимость в четком и аргументированном обосновании этого метода применительно к данным функциям, а также в строгом доказательстве геометрической интерпретации. Этим вопросам посвящен настоящий раздел.
В последюущем изложении мы воспользуемся понятием гиперболического поворота вектора, в которое вкладывается следующее содержание /28/. Пусть дана равносторонняя гипербола Xz-yh= const и произвольный радиус-вектор (начало радиус-вектора совпадает с началом координатной системы, а конец лежит на гиперболе). Считаем, что радиус-вектор совершает гиперболический поворот на угол 9 , если при вращении он скользит своим концом по гиперболе заметая площадь, равную по абсолютной величине половине "гиперболического угла". Гиперболический поворот вектора с координатами X} и Uj на угол 9 по равносторонней гиперболе можно рассматривать как преобразование, переводящее данный вектор в новое положение с координаатами Х2 и и2 , которые равняются: Х2= xfch9 y sh9 u tXiShQ + chB (2.1) где знак V соответствует направлению движения вектора против часовой стрелки, а знак "-" - по часовой стрелке.
Для обоснования метода Болдера применительно к гиперболическим функциям сформулирована следующая теорема:
Теорема. Касательная к равносторонней гиперболе в точке пересекает вектор, полученный в результате гиперболического поворота радиус-вектора ОМ на угол ±оС , в точке, координаты которой равняются:
Ниже приводится доказательство теоремы. Для наглядности доказательство выполнено по отношению к равносторонней единичной гиперболе хг-иг-1 . Соответствующее построение показано на рис.2.1.
На равносторонней гиперболе хг-и2=1 берем точку М(Хі,ш) В результате гиперболического поворота радиус-вектора Oh с координатами ХА-Сhf, U shWvi модулем на угол об против часовой стрелки получаем вектор ОМ с координатами: xz = ch(y+d) у2 =sh(f-+d) где гиперболические углы, которые равняются удвоенной площади гиперболических секторов ОРМ жОММ , соответственно. В точке А! проводим касательную ML к гиперболе, которая пересекает векторе в точке А (х г, у г).
Мы привели доказательство теоремы только для случая вращения гиперболического вектора против часовой стрелки, так как при гиперболическом повороте в обратное направление доказательство аналогично.
Ниже будет показано, что рекуррентные соотношения метода Болдера для вычисления гиперболических функций проистекают из соотношений (2.1), описывающих гиперболический поворот вектора, а также определяют эквивалентное преобразование.
Рассмотрим определение координат вектора, полученного в результате гиперболического поворота вектора ОМ с координатами X -chf и yf-Sh!f на угол 9 , принимая,что поворот выполняется в виде последовательности поворотов. Представление (2.28) открывает возможность вычисления координат хПн и У пи на базе формул (2.26) и последующего деления на величину Кп , которая зависит от величин промежуточных поворотов cL i , но не зависит от направления вращения и может быть вычислена заранее. Такая схема вычислений реализуется легко, если величины thdl равняются: thol 2 L, где L= 1,2,...,11 , (2.30) - 94 что позволяет заменить операцию умножения на операцию сдвига. При таком допущении величины углов поворота равняются di = Arth 2- (2 3I) Члены последовательности (2.31) удовлетворяют требованию о сходимости к нулю: CimAth2=0. С учетом (2.30) коэффициент дефор І-ЇОО мации вектора принимает вид : Кп= П\/1 2-2І.
Для учета направления поворота вектора введем оператор по ворота б/ , который принимает значение +1 при вращении против ча совой стрелки и -I при вращении по часовой стрелке. Использова ние данного параметра приводит к изменению представления угла & (2.12) и его промежуточных значении 0 через последовательность поворотов Ui :
Анализ входно-выходнои зависимости управляющей матрицы
Для анализа управляющих функций алгоритмов вычисления shx и chx на основе метода Волдера были составлены программы на ФОРГРАНе ЕС ЭВД, моделирующие процесс перевода аргумента из десятичной системы счисления в ареатангенсальную систему счисления (см. Приложение Ш ). Моделирование проводилось при следующих условиях: - область изменения аргумента X - диапазон допустимых положительных значений (первый управляющий сигнал 6о равняется 1,т.е. - способ задания аргумента: Xi+fXi+b-X, ДХ = 0,002; 0,0005; 0,00001 - режим счета в ЭВМ: =представление чисел с плавающей запятой =использование удвоенной разрядной сетки.
Данные, полученные в результате моделирования первого этапа каждого из трех алгоритмов на основе метода Волдера для вычисления элементарных функций shx и chx , использованы для построения графических изображений входно-выходных зависимостей Р= У(х) синхронного, асинхронного и минимального асинхронного алгоритма, которые показаны на рис.3.I, 3.2 и 3.3, соответственно. Как видно из рисунков, входно-выходная зависимость управляющей матрицы имеет прямолинейный скачкообразный вид.
На основе вышеизложенных вычислительной процедуры и таблицы соответствия была составлена программа на ФОРТРАНе ЕС ЭВМ, генерирующая значения абсцисс точек скачков (см. Приложение /72). С помощью этой программы для каждого из трех алгоритмов были получены первые 511 (относящихся к первому по девятый порядкам, с- ) значений аргумента Sf , 1=1,2,...,(2-1), в которых имеет место скачок управляющей функции. В табл.3.1 представлены первые 15 численных значений абсцисс скачков и их выражения через константы ollK-Airth2 lK для синхронного алгоритма, а в табл.3.2 -для асинхронного и минимального асинхронного алгоритмов (вплоть до четвертого порядка места скачков для этих алгоритмов совпадают).
Как видно из табл.3.1 и 3.2 абсциссы скачков являются линейными комбинациями констант Arth2 LK , ІК-1,2,...,П, Для этих значений аргумента X после некоторого числа итераций соответствующая промежуточная переменная Ък обязательно обнуляется, в результате чего в (КН) -ый разряд двоичного представления набора управляющих сигналов заведомо записывается единица (в силу того, что если к 0,6к=1). Для всех значений аргумента OCj , расположенных на оси абсцисс слева от точки скачка, данный разряд соответствующих двоичных представлений Pj имеет нулевое значение, в связи с чем и происходит скачок на графике управляющей функции. Из этих рассуждений можно сделать следующее заключение: наличие скачков связано с рассмотрением набора управляющих с игналов /6 J, который представляет собой изображение аргумента % в ареатан-генсальной системе счисления, в виде двоичного числа OyCLou.i.- CLv-i ( dj=1 , если 6J r / dj=0 , если бу =-/ ) ляющей функции синхронного и асинхронного алгоритма, соответственно, и их левые разности первого порядка Pj Pj l для значений аргумента Xj из малой окрестности точки ,-о4(табл.3.1) и точки ОЦ-СІЇ+ ±2-ЛІ+ ІЦ (табл.3.2).
Величиной скачка будем называть разность между значением управляющей функции в точке скачка и значением управляющей функции в точке, находящейся на малом расстоянии слева от точки скачка. Величины скачков одного порядка приблизительно равны. В табл.3.5 . приведены величины скачков с первого по четвертый порядок для управляющей функции асинхронного алгоритма. В таблице указывается значение .
Линейно-скачкообразный характер графиков управляющих функций, представленных на рис.3.I, рис.3.2 и рис.3.3 и выдвинутое нами требование о простоте технической реализации налагают использование кусочно-линейной аппроксимации для приближенного воспроизведения этих зависимостей. Управляющая функция синхронного алгоритма (рис.3.1) рассматриваться не будет, так как аппроксимация данной зависимости указанным способом не удовлетворяет по точности.
А. Управляющая функция асинхронного алгоритма (число единичных итерационных циклов 11=16, количество управляющих сигналов равняется 22).
