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

На правах рукописи

ЮРИН ОЛЕГ ВАЛЕРЬЕВИЧ

РАЗРАБОТКА И ИССЛЕДОВАНИЕ БЫСТРОДЕЙСТВУЮЩИХ АЛГОРИТМОВ ОТОБРАЖЕНИЯ ИНФОРМАЦИИ В РАСТРОВЫХ ГРАФИЧЕСКИХ ТЕЛЕВИЗИОННЫХ УСТРОЙСТВАХ

Специальность 05.12 04 «Радиотехника, в том числе системы и устройства телевидения»

АВТОРЕФЕРАТ

диссертации па соискание ученой степеии кандидата технических наук

Владимир 2005

Работа выполнена на ОАО «Муромский Завод радиоизмершельиы'х приборов».

Научный руководитель' доктор технических наук, до цент

В.В. Чскушкин

Официальные оппоненты: доктор технических наук, профессор

В.В. Костров

кандидат технических наук, доцент В.М. Тарануха

Ведущая орданизация* ОАО «Всероссийский научно-

исследовательский институт радиотехники»

Защита диссертации состоится «18» января 2006 юла в 14.00 часов на заседании совет Д 212 025 04 при Владимирском государственном университете по адресу 600000, Владимир, ул. Горького, 87, ВлГУ.

Авюрефера! разослан «/£" »

2005 1.

Отзывы в двух экземплярах, заверенные печатью, просим направлять по адресу 600000, Владимир, ул. Горького, 87, ВлГУ

С диссертацией можно ознакомиться в библиотеке ВлГУ

Ученый секретарь совета

доктор технических наук,профессор

А.Г Самойлов

Яо&бА-

—^ ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

Динамичное развитие информационных технологий, снижение стоимости, энергопотребления, массогабаритных характеристик микропроцессоров и микроЭВМ создает предпосылки для компьютеризации всех сфер человеческой дея-1ельнос1и. Важным направлением разит им цифровой вычислительной техники являе]ся компьютерная визуализация информации или машинная графика Совершенствование технологий производства и сравнительно низкая стоимость цифровых интегральных микросхем обеспечили массовое использование растровых графических телевизионных устройств в качестве средств отображения информации в электронных вычислительных системах различного назначения. К настоящему моменту методы и средства растровой машинной графики находят широкое применение в системах компьютерного моделирования, автоматизированного проем ирования, входяI в соыав различных человеко-машинных интерфейсов Например, в ряде модернизируемых и разрабатываемых перспективных радиолокационных станций средств ПВО/УВД производится замена индикатора кругового обзора на растровые 1 рафические дисплеи.

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

Разработке численных методов н алюршмов растровой графики посвящено большое количсспзо рабо) как зарубежных, так и 01счественных исследова/елей Извесшы рабо!ы Д Ьрезенхэма, К. Ву, М. Пнпзвоя, II. Сгефенсона, Ь. Мар-темьянова, II Вельтмандера и др Вместе с тем, ряд используемых алгоритмов имеет потенциальные возможности повышения быстродействия при сохранении структуры алгоритма и точностных характеристик результата. Таким образом, в настоящее время существует актуальная научно-техническая задача - повышение эффективности алюритмов отображения информации растровых фафических телевизионных устройств, решение ко юрой способствует улучшению их технических характеристик и условий труда операторов вычислительных систем.

Цели н задачи исследований

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

1 Повышено быстродействие существующих и разработаны новые быстродействующие алгоритмы растровой рпзвед1тшл1чзеаков прямм*:

2 Разрабомны общие принципы расфЭбойШ^МЙ^ш

библио'

с. петербург 09

ких кривых с по-

вышенным быстродействием; разработаны быстродействующие алгоритмы растровой развёртки дуг окружностей

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

Мсшды исследования

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

Научная новизна полученных результатов заключается в следующем:

1 Разработаны алгоритмы растровой развёртки отрезков прямых с шагом переменной длины и оптимальным деревом решений; показано, что по сравнению с известными /V - шаговыми алгоритмами, достигается сокращение среднего числа выполняемых операций на 20 40% и размера программного ко на па 15. .30%

2 Предложена методика разработки, оптимизации и оценки числа выполняемых операций пошаговых алгоритмов растровой развёртки отрезков прямых

3 Разработаны общие принципы растровой развёртки плоских кривых с ша юм переменной длины, обеспечивающие сокращение числа выполняемых операций 5а счёт гибкого использования изменений первой произвошюй воспронз-водпмой кривой

А Разработаны быстродействующие алгоритмы растровой развертки д\г ок ружностей с шагом переменной длины, в том числе адаптивные алгоритмы, обеспечивающие сокращение числа выполняемых операций на 12 52%

5 Преоло/кена методика расчёт и взаимной компенсации погрешностей быстродействующи* таблично-алт (¡ритмических преобразователей обеспечивающая минимум аппаратурных затрат при заданной погрешности резулыата

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

Практическая значимость полученных результатов заключается в следующем.

1 Разработаны быстродействующие алгоритмы растровой развёртки отрезков прямых и дуг окружностей, обеспечивающие сокращение числа выполняемых управляющих операций и размера программного кода по сравнению с алгоритмами, используемыми в ряде программных продуктов (например, Х\Ушс1о\у)

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

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

На защиту выносятся результаты теоретических и экспериментальных исследований:

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

2 Методика разработки и опенки числа выполняемых операций пошаговых алгоритмов растровой развёртки отрезков прямых

3. Бысфоденствующие адапшвныс шморшмы растровой развёр!кн ду) окружностей

4. Методика расчёта, результаты моделирования быстродействующих кусочно-линейных таблично-алгоритмических преобразователей.

Результаты внедрения

Материалы диссер!анионной работы использованы в учебном процессе при издании межвузовскою учебного пособия в Муромском институте ВлГУ; использованы при выполнении следующих ПИР с ОАО «Муромский завод Радиоизмерительных приборов» (МЗ РИП)

- Исследование 1ехпичссы1\ харамсрнсшк и разрабо1ка предложений по модернизации сосшвных частей изделия 39Н6. В 6-ги кн. Х.д. НИР. Тема № 2585/01. Муром, МИ ВлГУ, каф. РТ, 2002.

- Исследование методов и алгоршмов первичной и вторичной обработки радиолокационной информации Х.д НИР. Тема № 2939/03. Муром, МИ ВлГУ, каф РТ, 2003

Теоретические и практические резулыагы диссертационной работы внедряются в промышленности при разработке ошлных образцов радиолокационных станций на ОАО МЗ РИП

Апробация работы

Основные положения диссертционпоп рабом»! доклацывались и обсужиа-лись на следующих конференциях и семинарах.

1 33-я I [с1\чио-1 ехпнческая конференция преподавателей, сотрудников п аспират он Муромскою инсп-луы ВлГУ по июым работы за 1997 год (Муром 1997, 1 доклад),

2. 34-я Научно-техническая конференция преподавателей, сотрудников и аспирантов Муромского институт ВлГУ по итогам работы за 1999 год (Муром, 1999, 1 доклад);

3 111 Всероссийская научная конференция 'Применение дистанционных радиофизических мсюдов в исследованиях природной среды' (Муром, 1999 г, I доклад),

4 Научно-практическая конференция 'РЛС - 2004' (МЗ РИП, 2004 г, I доклад).

Публикации по работе

По теме диссертации опубликовано 11 печатных работ, в том числе 8 работ в 6-и общегосударственных журналах различного профиля

Струю ура и объем рабоп.1

Диссертация сосюит из введения, четырёх глав, заключения, списка используемой литературы и приложений Общий объем работы составляет 191 страница машинописного текст, включая 38 рисунков, И таблиц, 15 страниц приложений Библиография содержиI 76 наименований, в юм числе 11 работ автора

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Введение содержит обоснование актуальности темы диссертации. Сформулированы цели и задачи исследований, научная новизна и практическое значение, приводится структура диссертации

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

Во второй главе рассматриваются быстродействующие алгоритмы растровой развёртт отрезков прямых Выполнена оптимизация и оценка среднею числа выполняемых операций извеептых N - шаювых алгоритмов растровой развёртки отрезков На каждой итерации N - шатовото алгоритма выполняется анализ значения оценочной функции F, на принадлежность ряду непересекающихся числовых диапазонов, каждому из которых ставится в соответствие определенная /V шаювая комбинация. Обозначая оцениваемое число выполняемых операций алгоритма через 1\ среднее значение Р для всех возможных значений

)иювых коэффициентов кс(-со а) воспроизводимых прямых можно предеia-ви гь в виде

/» ш

tmi/OX7^' '<=!>,- о

/I /1

I не ш чисто поддиапазонов уыовых коэффициентов / общее число воспро-

изветенных отрезков во всех поддиапазонах к 11 и Р, - соответственно число

отрезков, и среднее значение оцениваемою параметра в поддиапазоне / При фиксированном размере проекции отрезков на ось абсцисс хк = const, среднее число выполняемых операций в поддиапазоне ке[к„. кк), 0 <к„< кК <1, равно

__/V 4 Г

^/(xJ-fo/AO^r^^min, (2)

»-I

где W, - относительная частота N - шаговой комбинации / в поддиапазоне ке[к„. ,кк), р, число операций, затраченное при выполнении Л; - шаговой комбинации / По результатам компьютерного моделирования алгоритмов установлено. что при равномерном распределении угловых коэффициентов в поддиапазоне ке[к„ к,), N - шаговые комбинации образуют устойчивое распределение относительных частот {Ж,}, так что задавая значения {/л}, / - 1 I, и используя выражения (I) и (2), можно определить наборы )/;>,}, для которых значения

Р, минимальны Поскольку определение числовою диапазона, содержащею

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

ритма, определяющее значения {/?,} Для ряда значений N=2. 5 получены оптимальные деревья решений алгоритмов, соответствующие минимуму среднею

числа выполняемых ветвлений Ы,, и суммирований /V, . В частности, для УУ = 4,

полученный выигрыш составил 17% для Ыс и 28% для М, ■ По результатам выполненной оптимизации сделаны следующие выводы.

1. Наименьшие значения среднего числа ветвлений И„ и суммирований

Ní получены при использовании сбалансированных бинарных деревьев решений.

2 Для рассмотренных алгоритмов с длиной шага N ~ 2. .5 при оптимальной структуре дерева решений имеет место непропорциональное распределение

среднего числа ветвлений /V, в зависимости от размера поддиапазонов А при

неизменном числе (/V! I) используемых N - шаговых комбинаций Поэтому, гшо-ритмы с постоянной длиной шага обладают избыточностью и не лучшим образом отражают особенности структуры растровой аппроксимации отрезков.

Выполнена разработка и исследование алгоритмов растровой развёртки отрезков с шагом переменной длины не менее Л' Показано, что при ограничении угловых коэффициентов отрезков в диапазоне Ае[0 1///], п> 0, за диагональным шагом алгоритма Крезенхэма следует как минимум (п - 1) аксиальный шаг, а итерация соответствующего алгоритма имеет вид (через '/Г обозначен аксиальный шаг, через '£>' - диагональный).

р =- 2 Ук - Ч,

Пс ш Г > О то { Шаги (щ 1]" '), Г- Гл 2(т, - гД |

иначе | Шаг Л\ Ь = /-" + 2гЛ; } Разработана методика синтеза алгоритмов с шаюм переменной длины не менее И(И> I) с использованием алгоритма (3), включающая следующие шаги. 1. Полагаем п ~ 2.

2 Если п > /V, то остановка процесса

3 Получаем составные шаги длиной не менее N для ке[0 . Мп] посредством комбинирования цепочек итераций итементарного алгоритма (3) для заданного значения п.

4 Выполняем анализ диапазонов Р и к полученных составных шагов и производим распределение составных шагов по поддиапазонам к, выбирая поддиапазоны к, не пересекающиеся (частично пересекающиеся) с диапазоном Ае|0 М{п+\)}

5 В полученных на шаге 4 поддиапазонах к производим проверку возможности наращивания длины шага составной итерации без изменения структуры алгоритма.

6 В случае выявления дополнительных шатов хотя бы для одной из комбинации рассматриваемою поддиапазона к выполняем анализ диапазонов изметтс-

пия оценочной функции для каждой из полученных на шаге 4 комбинаций с целью выявления неиспользуемых многошаговых комбинаций. 7 Увеличиваем п на единицу (п ~ п + 1) и переходим к п 2 Оценка среднего числа выполняемых ветвлений и итераций алгоритмов с шагом переменной длины выполнялась в соответствии с (I) и выражениями для подчиапазонов к-

¿1Х</„, _ ¿5>„„

N„=atxt=-^--х,, Nm„=buxk=^^--(4)

XkL/ XkL/ i дс ö0, ¿о - числовые коэффициенты, q,„ - число ветвлений, необходимое для выбора комбинации типа т, N„„ ~ общее число выполненных комбинаций типа т при воспроизведении отрезка / L, - общее число отрезков в /-м поддиапазоне угловых коэффициентов Значения цт определяются и cooibctctbiih с выбранной структурой дерева решений алгоритма, а А'„„ определялись nyiew кочпькиерною моделирования Выполнена разработка и оценка числа выполняемых операций алгоритмов с шагом переменной длины и оптимальным деревом решений для N ~ Ъ .5. Полученные результаты позволяю! сделать следующие выводы:

1 При оптимизации дерева решений алгоритмов с шагом переменной длины при равномерном распределении vi ловых коэффициентов наименьшие значения

среднею числа ветвлений N,, и суммирований NL получены при использовании сбалансированных бинарных деревьев

2. При использовании алгоритмов с шагом переменной длины, при уменьшении размера поддиапазона к имеет место пропорциональное уменьшение среднего числа вепзнений и. соотвеrciг.спно, числа используемых мпогоша! овы\ комбинации для всех paccxioiрениых случаев А' 3 5

3 При увеличении длины шага А' алюршма. выигрыш в сречнсм числе

вождений Л',. , получаемый oi использования переменной длины шага, возрас-

iасI: если для N-2 вышрыш составил 8.4%, то для N 4 указанное значение равно 22,5%, а для N = 5 - 32%. По четырем точкам (N - 2...5), для постоянной и переменной длины шага, методом покоординатного спуска при минимизации суммы квадратов погрешности, были определены соответственно следующие приближающие функции Na «[0,07 f ехр(-0,1 875A')Jai1 и

N, а [0,0544 ехр(-0,25Л')]х/, позволяющие выполнить предварительную оценку среднего числа ветвлений для заданного значения N Графики, экстраполирующие указанные функции для Ne[2 8] преде гавлены на рис 1

4. Независимо oi значения длины шага N, вышрыш в среднем числе терапий, получаемый при использовании переменной длины шага, для рассмотренных случаев остается постоянным и приблизительно равен -15. 20%.

5 При возрастании значения Nc-\2. 5], выигрыш по общему числу используемых многошаговых комбинаций, получаемый при введении переменной длины шага, увеличивается если для N 3 выигрыш составил 12,5%, го для N 5 число используемых комбинаций сократилось па треть

\

■У N

/Ч ч

г < 1 < <Г " к

Рисунок 1 Заш1Симосп-1 /V, /\-А _ Д/V) для шага переменной и иосюянной

(непрерывная линия) длины

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

В третьей ьпаве проводится разработка и исследование быстродействующих ашоршмов расфовой развёржи ду| окружностей. Выполнено исследование общих принципов и потенциальных возможностей растровой развёртки плоских кривых с шагом переменной длины 11 ус гь аппроксимируемая плоская кривая Да) удовлетворяет одному из условий

х- <- /•'(>) <-1, -1</'Ы£0, 0ИГ(\)<], \<Г(\)<сг (-5)

Положим, чк) для наилучшей расфовой аппроксимации кривой /(*), 0 < | < 1, на интервале ,гб[а ¿], минимизируется величина

|л(л-,,;',| - )'(|->тт, л-( , где пары {х„у,} - целые числа, так

что = [/"(х,)+1/2] Сформулирован ряд свойств растровых аппроксимаций для плоских кривых, удовлетворяющих условиям (5) Сформулирована и доказана 1еорема 1. устанавливающая наименьший размер аксиальной серии, входящей в растровую аппроксимацию кривой Дг), производная которой ограничена в диапазоне /'(л-)6 [0 1/«], и теорема 2 об ограничении на максимальную длину аксиальной серии, входящей в растровую аппроксимацию выпуклой вниз кривой /(г), первая производная которой ограничена в диапазоне /'(л)е[1//7 .1]

Теорема 1 Пусть кривая /(г) непрерывна на интервале ге[о-Д/ Ь+ &.,], при тгом /''(л)е[0 \/п], ,ге[я . Л], где п~> О - целое число, и |а(х, , у, )| £ 1/2

1о1да, если д(\, + у, у, И/2)> 0 . ю |а(|л, + / V, +"],}', +1)| < 1/2 и, если Л(г, I /, у, И/2)<0, то |а([х, -i 1 х, +1/2, /=1 .«. При этом

v,c[o - А/ b - n + Д,], а значения А/,А,. >0 зависят от п и кривой Дх)

*

Теорема 2 Пусть кривая Дх) непрерывна на интервале [а-А/.-.Ь] и выполняются условия /"(х) > 0, /'(х)е[1 /и .1], хе[а .h], тде п > I - целое число.

Пусть также |д(х,, у,)| s 1/2 , дг, е (« — А* .Л-я]. Тогда расстояние

д(\, + и, v,)> 1/2 При эюм величина А/>0 зависи i от функции Дх) и значения

w (таким же образом рассматривается и случай, котла Да) выпукла вверх)

Следствие 1 Из теорем 1 и 2 следует, что, если для кривой Дх) выполняется условие f'{a) = \J(n + \)< J'{x)<\/n = f'{b),a<b, ю длина / xk - xQ + 1 входящей в растровую аппроксимацию /(.г) аксиальной серии с абсциссой начальной *

I очки \0 ; а-А/ и абсциссой конечнойточки x/t < /л А, ,/ е[/?, п t 1J

Сформулирована и доказана теорема 3, устанавливающая наименьший размер диат опальной серии, входящей в растровую аппроксимацию кривой /(v), производная которой ограничена в диапазоне / '(л) е [(»-i)/".. 1), и георема 4 об ограничении на максимальную длину диагональной серии, входящей в растровую аппроксимацию выпуклой вниз кривой /(г), первая производная которой от раннчсна в диапазоне j\x)e [0 (»-!)/«]

Теорема 3. Пусть плоская кривая Дг) непрерывна на интервале \с[<7 Л, Лн Л,], при тюм /'(г) (-. \(п - \)/п .1], 'vcf«. /;]. тде п > 0 целое

число, и ¡а(а', , у, )| < 1/2 . Готда, если д(х, + j, v, + ; -1/2)> U , ю |л(х, н /и, у, + m)j < 1/2 , т = 1 /' и, если Л(х, + /. у, + /' -1/2)i 0 , ю |,\(л, + т. 1, I /п - l| < 1/2 . in /. /?. I - 1 п. При лом л,е|л - Д( h - п л А,\, а величины \I >0 зависят от функшпт/(\) тт значения п

Теорема 4 Пусть кривая/(\) непрерывна на интервале [с/ h i Л( ] и выполняются условия /"(х)> 0, /'(х) 6- (п -\)/п\ \е[« .А], глс я -I целое число Пусть также |д(х,,;',)| < 1/2 , х, е [а., b -п + А*) Тогда расстояние

A(y; + и,у, + n - l)< 1/2 При этом величина А; >0 зависит от функции Дх) и значения п.

Следе тис 2. Из теорем 3 и 4 следует, что если выполняется условие fXa)-(n-\)/n<f'{x)±n/(n*\)=f'(h), а < Ь, то длина / х* - л0 f 1 диаю-

тштьной серии с абсциссой начальной точки \и "-а -Ау и абсциссой конечной

точки хк < h4 А* , 1е\п, /7+1].

С использованием теорем 1 и 3 выполнена разработка п оценка быстродействия одно/двухшагового алгоритма растровой развёртки второю октанта окружности с целочисленными радиусом и коор шпатами центра Показано, что число выполняемых операций одно/двухптаговою алторитма соответствует числу выполняемых операций известного двухшапжого алгоритма Bv и Рокпс при

лом число команд, необходимое для записи одно/двухшагового алгоритма, сокращается вдвое.

Из формулировки теоремы 1, в частности, следует, что для диапазона f'(\) е [-1//7...0] терапия ал!оритма с шагом переменной длины имеет вид

Leun (Л(х, + I, у, - 1/2) > О) то Ы1аг А, иначе Шаги (D[A]" , (6)

поному, для последовательно убывающих целых значении пе{я0, я0 1 ,3,2}, начиная с некоторого начальною значения /70, получаем алгоритм, аппроксимирующий окружность набором единичных аксиальных перемещений и серий последовательно убывающей длины 1 на интервалах

/'(*) е [0.. - !/#»„ M-l/n0 ...-1 /(п0 - l)]u. ,и[-1/3...-1/2] Определена таблица начальных значений [«„,] =/(/?) для п0е\ 1 31] В соответствии с формулировкой теоремы 3, для диапазонов /"'Сл) е [— 1 ..-(/7-1)//;] итерация алгоритма с шагом переменной длины имеет вид

/:счи (Д(\,4 1,з, 1/2) <-0) то Шаг П, иначе Шаги (ä[D\", (7)

гак что при последовательном возрастании целых значений ие{2, 3, 4,...} получаем алгоритм, аппроксимирующий функцию j{x) набором единичных диато-ттачт.ных перемещенпн и серии последовательно возрастающей длины / 1, со ответственно, на интервалах

/'(*)б[- 1/2 -2/3]w[-2/3 -3/4]w ...../(n.....т 1) l],

где /7шт наибольшее значение /? такое, что И/(И(|) \,-(«W">/7 С использованием теорем 1,3 и итераций (6), (7) разработан адаптивный алгоритм растровой разпергки окружностей, использующий серии последовательно убывающих/возрастающих глин п,<- {/70, /7(, - 1, . . 3, 2. 3, , /;„мч - 1. /imjxj Количество машинных комапч необходимых для записи адашпвпою алгоритма, соотвстсг-в\ет известному двухшагоному апгоритму By и Рокпе

Проведена оценка числа выполняемых операции адаптивною алторитма Д тя интервала |/0)lh д^ |/(J число выполняемых единичных аксиа п,-

пых ггеремещений N,ln равно

NujR-4nr7\~(n~+n^ \ )Ц(пл !)г+1 , л > 1. Для интервала \е|0 r/Jï] обгцее число выполняемых серии, включающих диагональный шаг, равно N^ ^ = /?(1 2/V5) Общее число выполняемых аксиальных перемещении N„ равно

R т R

VK+Ô2

1 "о +1

JK^ 1)' +1

rS-2-t

11ри /70—>со получаем N ~ 0,0451 R

Число единичных диатопальных перемещений, выполняемых на интерва ie Г v,. , , , х,. . равно

1 ]/ (» 1)/и 7 п m I) J I

N,

■ R[Jn2+(n-1)2 - {In2)/ Jn2 +{n+\f].

Для интервала v e \R¡41 .../?/л/2] общее число единичных диагональных

перемещении на этом же интервале равно

N

+Кы, - о2

2«„.

V2

При >оо получаем Л',, « 0.0294R

Общее число составных перемещений на интервале х е [R/S .л/л/2] , содержащих аксиальный шаг, равно N^ ^ = R(J2 — з/л/5)

Показано, что при больших значениях радиуса /?—wo. для предельных значений Л',,-- 0,0451 Л и Л',/~ 0,0294/?, оцениваемые показатели равны общее число выполняемых условных/безусловных переходов Л'„ ~ 0,5053/?. число умножений N '-0,1781/?, число двоичных сдвигов iV<_ = 0,3?52/?, число суммирований текущих значений координат {*„.)>,}, непосредственно необходимое для работы алго-ри!ма А^, ~ 0,4602/?, число суммирований Nc ~ 0,858/?.

В большинстве микропроцессоров общего назначения для выполнения операции умножения требуется сравншельно большое число машинных гакюв, поэтому рассмотрен случай, когда длины серий адаптивных алгоритмов (6) и (7) изменяются по убывающим степеням числа 2, re /7,-2'.

е{2'",2'" ,4,2.4, ,2'""") Умножения при лом заменяются двоичными

сдвигами Для предельных (при /?--»<») значений /V„ ~ 0,1136/? и N,¡~ 0,0626/?, рассматриваем!,ie показатели равны N„ ~ 0 7087/? N , - 0,6051 R М w - 0.595 1R и N, ~ 1.0946/? В случае, когда п„ - /7„1-1Ч - 2 адаптивные алгоритмы сокращаются до одно/двух шагового, оцениваемые пока затени для которого равны Л'„ к 1.058 I /?. /V.. 0.7071 /?, Л; к 1,2452R и , * 0 821 8/?

аблица 1 Оценки числа выполняемых управляющих операций алгоритмов

Алгоритм К, К К

Мичнера 1,4142 R 0,7071 R 2,1213 R /? —

2-шаговый By 0,9668/? 0,7081/? 1,2056R 0,5857/? —

Одно/двухшаговый 1,0581/? 0,7071/? 1,2452 R 0,8218/? —

Адаптивный 0,5053 R 0,3252 R 0,8579R 0,4602R 0,1781/?

Адаптивный, = 2' 0,7087/? 0,6051 /? 1,0946/? 0,5951 R —

Проведённые оценки адаптивных алюритмов показывают, чю при единичном изменении длин серий, выигрыш в числе выполняемых управляющих операций, по сравнению с известным двухшаговым алгоритмом, составляет до 31. 52% В случае, когда длина серии изменяется по последовательно убывающим/возрастающим степеням числа 2, выигрыш составляет до 12 33% При этом количество машинных команд, необходимое для записи алюритма. фактически соответствует известном) двухшаговому

В четвертой 1лаве выполнена разработка и анализ быстродействующих кусочно-линейных 1аблично-алгоригмических агшроксимагоров для вычисления элементарных функций, используемых при реализации геометрических преобразований отображаемой информации Пусть значения аргумента х и функции Дх) нормированы и находятся в интервале [0 .1), при этом значения аргумента задаются /7-разрячным линейно-нарастающим двоичным кодом а значения функции предсывлякнся с m двоичными разрядами. Разделим двоичный код apiу-мента на группы старших и младших разрядов, число которых равно к и (и-g) соответственно'

* » * = х,„ = ]Гх,2-'. (8)

/-1 #-),ч|

loi да интервал изменения аргумеша хс[0 1) разбивается на 2" равных чнеизчпмх ночитервалов а значения функции можно предаавить r виае ку-сочно-л иней нон аппроксимации

/(а)«*,л+А, {к,2 ^Cx^'V^+A^J-^x^'Ji/ÎO. (9) где f(\i ,„) = b/ + ]к f1 * , 0 < х.,,2* < 1, j = 0. 2*-1,а кп bt - коэффициенты аппроксимирующего полинома, соопзегспзуюшет /-му частичному подинтерва-лу Т* Гтруюура устройства, реализующего аппроксимацию (9), прелставлена на рис 2 В целях увеличения точности результата внутренние вычисления ве-дугся с / дополнительными разрядами.

Рисунок 2 Структура аппроксимаюра с умножителем

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

|де А,„„ А/, - пофешностн представления значений функции в опорных точках и коэффициентов К, с точностью до (ш ь г) двоичных разрядов соотвс1спзснно, А, - по1 решность преде явления 2(ш - + / 1 I - разрядно! о резулыата умножении с (/>; - х 1 4 О двоичными разрядами, Л, - пшрешносп. усечения (ш ' г) - разрядно! о результа 1а суммирования до ш ра зрядов, А/ по! решность линеаризации

функции /(л), а в = х„,2к , в е [0...1).

Для г > 0 разработаны алгоритмы округления/усечения разрядных сеток операндов в выр. (9), обеспечивающие минимальные абсолютные значения и симметричные максимальные/минимальные значения погрешности результата на выходе устройства. "I аким образом, максимальное абсолютное значение по-

фсшиости на выходе устройства равно |д/"*(л)|<2 "' ' н 2 "' ' 1 + тах^Д,!.

Погрешность линеаризации функции А/ зависит от способа построения аппроксимирующих полиномов крс ^ Ьр а также от числа старших разрядов £ Для полиномов с чебышевскими узлами, минимально необходимое число старших разрядов g, при котором пофешность линеаризации не превышала бы заданное значение та\|Д,|. определяется из выражения

0,5 lo

шах

хИхУтахЫ

&2 г, 10 II1' V "/ i |0 II1

Установлено, что при увеличении числа разрядов результата выигрыш в числе используемых бит памяти, по сравнению с табличным воспроизведением функции, для которою число бит памяти равно Лт = »7x2" бит, возрастае! Пока-iano, что по сравнению с известным методом кусочно-параболической интерполяции, при и <-23 выигрыши от использования кусочно-линейной и кусочно-параболической интерполяции различаются ие более чем в 4 раза

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

/(*) = Д\,„ +-\',„) -= /(д„„) + Д/(л,„,,А>(,), где f(\u„) - значения функции в опорных точках, определяемых старшими разрядами аргумента, а Д/(v,,„. г,,,) - набор приращений для интерполирования функции в интервалах между соседними опорными ючками. Будем использовать один и тот же набор приращений сразу для нескольких опорных точек, определяемых частью старших разрядов xím, имеющих наибольший вес, число которых равно bg При этом диапазон изменения аргумента разбивается на 2Л групп по 2"'1' интервалов размером 2~1', на каждую из которых приходится по одному набору приращений, аппроксимирующих функцию в пределах интервала с шагом 2"" Аналитическую функцию f(x) можно представить в виде разложения в степенной ряд Тейлора в точке xÍU; ' ({к)(х )

/ / \ г, \ V"1 J о / / к *

/ (\,„ +*„,) ~/(*„„)-) > -—---хи1 , |де г, - точка расчета суммы остатка

Í—J А) >

/ I ft

ряда Тейлора для вычисления набора приращений на /-м интервале 2 h (/-1)2 '' <х'0 < /2 h, / -- 1.. 2Л Структура устройства, реализующего вычисление функции по указанному принципу, представлена на рис 3

/ . I

п '

I I

n-g

Рисунок "i Структура с табличным формированием приращении функции

Число двоичных разрядов, необходимое для представления элементов таб-

лицы приращений с точностью до 2 "' '.равно m-g + r-(-

log:

max

г. |0 1)1

J (*)|

Разработана методика расчёта таблиц и анализа погрешности воспроизведения функции для структуры на рис. "5 Погрешность определяется как разность между налонным значением функции /(у) и реальным значением на выходе устройства/ (дг)

АГ(.У)=/(\)-/'(А)--Л, I Л„„+Л, + Д„.

где Лл А„р - погрешности представления значений функции и приращений с конечным числом чвоичных разрядов, Л, погрешность перехода от (т + г) - разрядных вычислений к т - разрядному результату и А,, - ногрешнос!ь метода, обусловленная 0|брасываннем (,<?-/?) старших разряпов аргумента при адресации таблицы приращений Округченнс нспопьзуемых операндов выполняется таким образом чго выполняется условие симметрии максимальных/минимальных значений суммарной погрешности дискрегтнацин операндов

тах(Л^ + Д(|/) + А, ) - |тт(Л) +Л(|/, + А, )| Верхняя граница абсолютного значс-грешпости результата равна: |л/'(х)|<2 "' 1 + 2 "' ' 1

ния поп

+ тах|л, I. Текущее

rJO I)1 1

значение погрешности метода равно

к\

(10)

Оценка верхней границы абсолкн ного зттачения погрешности имеет вид

¡А,, < тах< тах

(П)

I дс (/ 1 )2 '' ^ - /2 h - 2/ ~ 1 2h Значение А,, на интервале 2 К можно скомпенсировать и, таким образом, уменьшить вдвое путём добавления в/(д1(„) величины 0 ^xsgn(A/,) ma\|/\/,| (половины величины потретшюсти с наибольшим на

интервале [хаи хи„ + 2~у] абсолютным значением), рассчитываемой для каждой опорной точки х,„, в соответствии с (10). Число бит, необходимое для хранения таблиц, равно

2«(т + 1) + 2" * * т - £ + г + 1ое, шах /"'(*)

_ г( |0 II 1

Значения % и Ь целесообразно выбирать 1ак, чтобы при заданных значениях ш, п, г и тах|ДЛ|, общий объём используемых таблиц был бы минимален. Приближённые оценки оптимальных значений g и Ь можно получить следующим образом. Если производные функции порядка выше 1 на заданном интервале изменяются незначительно и членами разложения (10) порядка к> 1 фактически

можно пренебречь, то, располагая точки л* в середине интервалов 2 Л, оценка (11) приводится к виду тах^,! ~ 2 'ч' '' ' тах |/"(л)| Тогда, выражая из носледне

гМО I)

ю уравнения Ь или и подставляя полученную зависимость в уравнение для А,ч„ получаем одну из систем, из решения которой определяем требуемые оптимальные значения:

Ь= /'(я)тах|ДА|Х £ - А6,тах|Д,,|).

< А = Ля. Ая тах|Л,|)), пли А = /(/>,/(/>. тах|Д,,|)),. дЛ/дя=- О, £А/0Ь-= 0;

Выигрыш в объёме используемой памяти, по сравнению с табличным воспроизведением функции, определяется величиной тах|/"(х)|: чем меньше диапазон изменения первой производной, тем более 'похожи' соседние учаыки графика /(\). 410 приводит к уменьшению значения Ь и сокращению размеров используемых таблиц Преобразователь с табличным формированием приращений фчнкцпи можно использовать как непосречственно, так и для вычисления первою приближения в комбинированных меюдах, например в комбинациях тина ' 1 абл ица-итсрация'.

Выполнено компьютерное моделирование таблично-алгоритмических преобразователей. По результатам моделирования установлено, что эмпирические значения максимальных погрешностей вычисления функции соответствуют теоретически рассчитанным значениям с точностью 5. 10%, математическое ожидание погрешности можно уменьшить на порядок и более с использованием корректирующих добавок, а дисперсия погрешности фактически соответствует дисперсии погрешности при табличном воспроизведении функции Для структуры с таблицей приращений функции показано, что по отношению к табличному воспроизведению функции, выигрыш в объёмах используемой памяти возрастает при увеличении числа входных/выходных разрядов п преобразователя В частности, для функции Я1п(лх72) при «е[16. 24] выигрыш соответственно составил порядка 10 ..200 раз.

ЗАКЛЮЧЕНИЕ

1 Предложена методика оптимизации и оценки числа выполняемых операций известных /У-шатовых алгоритмов растровой развёртки отрезков прямых. Показано, в частности, что для N - 4 оптимизация обеспечивает сокращение числа выполняемых суммирований па 17% а числа ветвлений на 78% Показана избыточность N - шаговых алгоритмов.

2. Разработаны алюритмы раыровой развёртки офезков прямых с шаюм переменной длины и оптимальным сбалансированным деревом решений; показано, что использование шата переменной длины обеспечивает сокращение среднего числа выполняемых операций на 22 . 32%, числа используемых многошаговых комбинаций на 12 30%

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

4 Разработаны адаптивные алюритмы растровой развёртки дуг окружностей с шагом переменной длины Показано, что использование шага переменной длины обеспечивает сокращение сложности алгоритма при сохранении числа выполняемых операций и сокращение числа выполняемых операций при равной сложности алюритма По сравнению с известным двухшаговым алгоритмом, при использовании адаптивных алгоритмов число выполняемых управляющих операции сокращается па 12...52%

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

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

Список публикаций по теме диссертации

I. В.В. Чекушкин, О.В. Юрин Реализация индикатора кругового обзора на дисплее с телевизионным растром // Радиотехника. — 2002 — №3 - с 86-89

2 В В Чекушкин. О В Юрин Моделирование структур цифровых аппрок-симаторов для воспроизведения функции синуса на персональном компыо1ере // Измерительная техника. - 1999.-№6-с 12-14.

3. В В Чекушкин, О.В. Юрин Анализ быстродействующих алгоритмов деления чисел // Изв. Вузов. Приборостроение. - 2003. - Т. 46. -№8 - с.28-31.

4 О.В. Юрин, В.В. Чекушкин Оптимизация методов дискретной линейной интерполяции // Приборы и системы, управление, контроль, диагностика -2003. №11. е.! 1-16.

5. О.В. Юрин, В.В. Чекушкин Использование переменной длины шага в ип-крементных алгоритмах дискретной линейной интерполяции // Автоматизация и современные технолог ии -2005 №5 с 31-38

6 В В Чекушкин, О В Юрин Погрешности линейной интерполяции по методу оценочной функции // Станки и инструмент. -2000. №8, с. 13-15.

7. В.В Чекушкин, О.В. Юрин Повышение точностных характеристик линейной интерполяции по методу модифицированной оценочной функции // Станки и инструмент. - 2002 №10 с.22-23

8 В В. Чекушкин, О.В. Юрин Совершенствование меюдов преобразования ортогональных составляющих сигнала в амплитуду и фазу // Метрология -2001 №11 с.9-17

9. В В. Чекушкин, О.В. Юрин Преобразователь полярного растра зоны об-юра в телевизионный растр // Тезисы докладов научной конференции Применение дистанционных радиофизических меюдов в исследованиях природной среды Научный cobci РАН гто комплексной проблеме «Распространение радиоволн», 1999-е 204-205

10 В В Чекушкин, МФ Серет ин OB Юрин Цифровые кусочно-полиномиальные аппроксиматоры пулевого и первого порядка дня воспроизведения функций // Научные труды Муромских ученых / Под ред. Н В Чайковской - Владимир, 1998. - С.57-59.

II. В.В. Чекушкин, О.В. Юрин Прецизионный синусно-косинусный таблично-алгоритмический преобразователь // Информационный листок, Владимир, ЦНТИ, 1998,4 с

Юрин Олег Валерьевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ БЫСТРОДЕЙСТВУЮЩИХ АЛГОРИТМОВ ОТОБРАЖЕНИЯ ИНФОРМАЦИИ В РАСТРОВЫХ ГРАФИЧЕСКИХ ТЕЛЕВИЗИОННЫХ УСТРОЙСТВАХ

Специальность 05 12 04 - «Радиотехника, в том числе системы и устройства телевидения»

Подписано и печать 15 12 2005 Формат 60x84/16. 1 ариитура 1аймс Ьумаы для множительной техники 11ечнIт> рт-пшрафия Уел печ л 1,16 Тираж 100 Закат №57 Отпечатано н мштитинот рафпп Ч II Снирилопон В В Адрес 607102, Нижет ородская оол I I Кшашимо, ул Калинина, 27

P- 1 2 67 I

i

ВВЕДЕНИЕ

1 АНАЛИЗ АЛГОРИТМОВ И АППАРАТНЫХ СРЕДСТВ ОТОБРА- 9 ЖЕНИЯ ИНФОРМАЦИИ В РАСТРОВЫХ ГРАФИЧЕСКИХ ДИСПЛЕЯХ

1.1 Архитектуры и аппаратные средства растровых графических дис- 9 плеев

1.2 Обзор и анализ алгоритмов растровой развёртки плоских кривых

1.2.1 Цифровые дифференциальные анализаторы

1.2.2 Структурные алгоритмы растровой развёртки отрезков прямых

1.2.3 Пошаговые алгоритмы

1.2.4 Повышение быстродействия растровой развёртки отрезков прямых

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

Выводы по главе

2 РАЗРАБОТКА И ИССЛЕДОВАНИЕ БЫСТРОДЕЙСТВУЮЩИХ 33 АЛГОРИТМОВ РАСТРОВОЙ РАЗВЁРТКИ ОТРЕЗКОВ ПРЯМЫХ

2.1 Анализ интегральных характеристик погрешности растровых ап- 36 проксимаций отрезков прямых'

2.2 Оценка производительности двух- и двух/трёхшагового алгоритмов

2.3 Оптимизация 4-шагового алгоритма Гилла

2.4 Наращивание длины шага 4-шагового алгоритма Гилла

2.5 Разработка алгоритмов с шагом переменной длины не менее N

2.6 Сравнительный анализ алгоритмов с постоянной и переменной дли- 77 ной шага

2.7 Программная реализация и оценка производительности алгоритмов 81 Выводы по главе

3 РАЗРАБОТКА И ИССЛЕДОВАНИЕ БЫСТРОДЕЙСТВУЮЩИХ 86 АЛГОРИТМОВ РАСТРОВОЙ РАЗВЁРТКИ ДУГ ОКРУЖНОСТЕЙ

3.1 Анализ дискретных дефектов в растровых аппроксимациях окруж- 87 ностей

3.2 Оценка производительности пошаговых алгоритмов

3.3 Растровая развёртка плоских кривых с использованием шага пере- 98 менной длины

3.4 Разработка и анализ одно/двухшагового алгоритма

3.5 Разработка адаптивных алгоритмов

3.6 Оценка числа выполняемых операций адаптивных алгоритмов 128 Выводы по главе

4 РАЗРАБОТКА БЫСТРОДЕЙСТВУЮЩИХ АЛГОРИТМОВ ВЫ- 142 ЧИСЛЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ ДЛЯ ГЕОМЕТРИЧЕСКИХ ПРЕОБРАЗОВАНИЙ ОТОБРАЖАЕМОЙ ИНФОРМАЦИИ 4.1 Расчёт и анализ погрешности кусочно-линейных табличноалгоритмических преобразователей с умножителем

4.2 Расчёт и анализ погрешности преобразователей с табличным фор- 150 мированием приращений функции

4.3 Численное моделирование алгоритмов 156 Выводы по главе 4 162 ЗАКЛЮЧЕНИЕ 163 СПИСОК ЛИТЕРАТУРЫ 165 ПРИЛОЖЕНИЕ 1 Текст программы моделирования таблично- 172 алгоритмического преобразователя с умножителем

Актуальность темы

Динамичное развитие информационных технологий, снижение стоимости, энергопотребления, массогабаритных характеристик микропроцессоров и микро-ЭВМ создаёт предпосылки для компьютеризации всех сфер человеческой деятельности. Важным направлением развития цифровой вычислительной техники является компьютерная визуализация информации или машинная графика. Совершенствование технологий производства и сравнительно низкая стоимость цифровых интегральных микросхем обеспечили массовое использование растровых графических телевизионных устройств в качестве средств отображения информации в электронных вычислительных системах различного назначения. К настоящему моменту методы и средства растровой машинной графики находят широкое применение в системах компьютерного моделирования, автоматизированного проектирования, входят в состав различных человеко-машинных интерфейсов. Например, в ряде модернизируемых и разрабатываемых перспективных радиолокационных станций средств ПВО/УВД производится замена индикатора кругового обзора на растровые графические дисплеи [1.4].

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

Разработке численных методов и алгоритмов растровой графики посвящено большое количество работ как зарубежных, так и отечественных исследователей. Известны работы Д. Брезенхэма, К. By, М. Питтэвэя, П. Стефенсона, Ю. Ситникова, Б. Мартемьянова, П. Вельтмандера и др. Вместе с тем, ряд используемых алгоритмов имеет потенциальные возможности повышения быстродействия при сохранении структуры алгоритма и точностных характеристик результата. Таким образом, в настоящее время существует актуальная научно-техническая задача - повышение эффективности алгоритмов отображения информации растровых графических телевизионных устройств, решение которой способствует улучшению их технических характеристик и условий труда операторов вычислительных систем.

Цели и задачи исследований

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

1. Повышено быстродействие существующих и разработаны новые быстродействующие алгоритмы растровой развёртки отрезков прямых.

2. Разработаны общие принципы растровой развёртки плоских кривых с повышенным быстродействием; разработаны быстродействующие алгоритмы растровой развёртки дуг окружностей.

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

Методы исследования

В процессе выполнения диссертационной работы использованы методы интегрального/дифференциального исчисления, математической статистики, теории приближения функций, математического моделирования.

Научная новизна полученных результатов заключается в следующем:

1. Разработаны алгоритмы растровой развёртки отрезков прямых с шагом переменной длины и оптимальным деревом решений; показано, что по сравнению с известными N- шаговыми алгоритмами, достигается сокращение среднего числа выполняемых операций на 20.40% и размера программного кода на 15.30%.

2. Предложена методика разработки, оптимизации и оценки числа выполняемых операций пошаговых алгоритмов растровой развёртки отрезков прямых.

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

4. Разработаны быстродействующие алгоритмы растровой развёртки дуг окружностей с шагом переменной длины, в том числе адаптивные алгоритмы, обеспечивающие сокращение числа выполняемых операций на 12.52%.

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

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

Практическая значимость полученных результатов заключается в следующем.

1. Разработаны быстродействующие алгоритмы растровой развёртки отрезков прямых и дуг окружностей, обеспечивающие сокращение числа выполняемых управляющих операций и размера программного кода по сравнению с алгоритмами, используемыми в ряде программных продуктов (например, XWin-dow).

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

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

На защиту выносятся результаты теоретических и экспериментальных исследований:

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

2. Методика разработки и оценки числа выполняемых операций пошаговых алгоритмов растровой развёртки отрезков прямых.

3. Быстродействующие адаптивные алгоритмы растровой развёртки дуг окружностей.

4. Методика расчёта, результаты моделирования быстродействующих кусочно-линейных таблично-алгоритмических преобразователей.

Результаты внедрения

Материалы глав 2 и 4 диссертационной работы использованы в учебном процессе при издании межвузовского учебного пособия [17] в Муромском институте ВлГУ. Материалы диссертационной работы использованы при выполнении следующих НИР с ОАО «Муромский Завод радиоизмерительных приборов» (МЗ РИЛ):

- Исследование технических характеристик и разработка предложений по модернизации составных частей изделия 39Н6. В 6-ти кн. Х.д. НИР. Тема № 2585/01. Муром, МИ ВлГУ, каф. РТ, 2002.

- Исследование методов и алгоритмов первичной и вторичной обработки радиолокационной информации. Х.д. НИР. Тема № 2939/03. Муром, МИ ВлГУ, каф. РТ, 2003.

Теоретические и практические результаты диссертационной работы внедряются в промышленности при разработке опытных образцов радиолокационных станций на МЗ РИП.

Апробация работы

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

1. 33-я Научно-техническая конференция преподавателей, сотрудников и аспирантов Муромского института ВлГУ по итогам работы за 1997 год (Муром, 1997,1 доклад);

2. 34-я Научно-техническая конференция преподавателей, сотрудников и аспирантов Муромского института ВлГУ по итогам работы за 1999 год (Муром, 1999, 1 доклад);

3. III Всероссийская научная конференция 'Применение дистанционных радиофизических методов в исследованиях природной среды' (Муром, 1999 г., 1 доклад);

4. Научно-практическая конференция 'PJIC - 2004' (МЗ РИП, 2004 г., 1 доклад).

Публикации

По тематике диссертации опубликовано 11 печатных работ, в том числе 8 работ в 6-и общегосударственных журналах различного профиля. Часть материалов изложена в отчетах по НИР и ОКР.

Структура и объём работы

Диссертация состоит из введения, четырёх глав, заключения, списка используемой литературы и приложений. Общий объем работы составляет 195 страница машинописного текста, включая 38 рисунков, 12 таблиц, 24 страницы приложений. Библиография содержит 76 наименований, в том числе 11 работ автора.

4.4 Выводы по главе 4

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

2. Для структуры с умножителем показано, что по отношению к табличному воспроизведению функции, выигрыш в объёмах используемой памяти возрастает при увеличении числа входных/выходных разрядов п преобразователя и, для яе[16.20], составляет порядка 300.600 раз.

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

4. Для структуры с табличным формированием приращений функции показано, что по отношению к табличному воспроизведению функции, выигрыш в объёмах используемой памяти возрастает при увеличении числа входных/выходных разрядов п преобразователя. В частности, для функции sin(7ur/2) при и е [ 16. .24] выигрыш составил порядка 10. .200 раз.

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

ЗАКЛЮЧЕНИЕ

1. Предложена методика оптимизации и оценки числа выполняемых операций известных N- шаговых алгоритмов растровой развёртки отрезков прямых. Показано, в частности, что для N=4 оптимизация обеспечивает сокращение числа выполняемых суммирований на 17%, а числа ветвлений на 28%. Показана избыточность N - шаговых алгоритмов.

2. Разработаны алгоритмы растровой развёртки отрезков прямых с шагом переменной длины и оптимальным сбалансированным деревом решений; показано, что использование шага переменной длины обеспечивает сокращение среднего числа выполняемых операций на 22.32%, числа используемых многошаговых комбинаций на 12.30%.

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

4. Разработаны адаптивные алгоритмы растровой развёртки дуг окружностей с шагом переменной длины. Показано, что использование шага переменной длины обеспечивает сокращение сложности алгоритма при сохранении числа выполняемых операций и сокращение числа выполняемых операций при равной сложности алгоритма. По сравнению с известным двухшаговым алгоритмом, при использовании адаптивных алгоритмов число выполняемых управляющих операций сокращается на 12. .52%.

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

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

1. Клочков В.В. ВИГИ 17: Автоматизированная система ПВО и УВД // Военный парад. Журнал ВПК. 1996 - май - июнь. с. 158-160.

2. Лианозовский комплекс средств УВД // Информационный листок, Изд. ЗАО «ИПП Русполиграф», 1998, 4 с.

3. Система противовоздушной обороны «Триумф» // Экспортный каталог предприятий РАСУ, 2000, с. 12.

4. Унифицированное рабочее место оператора 486РР01 // Информационный листок, ФГУП Муромский завод радиоизмерительных приборов.

5. ICOS Индустриальные компьютерные системы. Каталог продукции. Выпуск 5.0.

6. Клейн М., Морган Г., Аронсон М. Цифровая техника для вычислений и управления: Пер. с англ. М. Изд-во иностр. лит-ры, 1960. - 386 с.

7. У. Ньюмен, Р. Спрулл Основы интерактивной машинной графики: Пер. с англ. М.: Мир, 1976. - 574 с.

8. Дж. Фоли, А. вэн Дэм Основы интерактивной машинной графики. В 2-х книгах. Пер. с англ. М.: Мир, 1985. - 368 с.

9. Д. Роджерс, Дж. Адаме Математические основы машинной графики, пер. с англ. М.: Мир, 2001. - 604 с.

10. Вирт Н. Алгоритмы и структуры данных. Пер. с англ. М.: Мир, 1989.

11. Воронов А.А. и др. Цифровые аналоги для систем автоматического управления. М.: Л.: АН СССР, 1960. - 196 с.

12. И.С. Березин, Н.П. Жидков Методы вычислений, М.: Издательство физико-математической литературы, 1962, 2т.

13. А.А. Амосов, Ю.А. Дубинский, Н.В. Копченова Вычислительные методы для инженеров, М: Высшая шк., 1994.

14. Шауман A.M. Основы машинной арифметики. Л.: Изд-во Ленингр. ун-та, 1979,312 с.

15. Чекушкин В.В. Методы построения цифровых интеграторов в генераторах радиально-круговой развертки // Вопросы радиоэлектроники, сер. ОТ 1977, вып. 11, с. 96-99.

16. Чекушкин В.В. Анализ ошибок цифрового интегратора с параллельным переносом // Известия ВУЗов СССР. Приборостроение. 1989, №10, с. 39-43.

17. Чекушкин В.В. Реализация вычислительных процессов в системах управления и контроля. Учебное пособие. Муром.: 2001. - 44 с.

18. Байков В.Д., Вашкевич С.Н. Решение траекторных задач в микропроцессорных системах ЧПУ. Под ред. В.Б. Смолова. JL: Машиностроение, 1986.106 с.

19. Ратмиров В.А. Основы программного управления станками.- М.: Машиностроение, 1978. 240 с.

20. Сосонкин В.Л. Программное управление технологическим оборудованием: Учебник для ВУЗов по специальности "Автоматизация технологических процессов и производств". М.: Машиностроение, 1991. - 512 с.

21. Каштальян И.А., Клевзович В.И. Обработка на станках с числовым программным управлением: Справ, пособие. Мн.: Выш. шк., 1989. - 271с.

22. Бугаевский JI.M. Математическая картография: Учебник для вузов. М.: 1998.-400 е.: ил. 65

23. Выгодский М.Я. Справочник по высшей математике. М.: Гос. Изд-во технико-теоретической литературы, 1956.

24. Задачи и упражнения по математическому анализу, под ред. Б. П. Демидо-вича, М.: Наука, 1978,480 е., ил.

25. Абель П. Язык Ассемблера для IBM PC и программирования / Пер. с англ. Ю.В. Сальникова. -М.:Высш. Шк., 1992.-447 е.: ил.

26. В. Б. Бродин, И. И. Шагурин, «Микропроцессор i486. Архитектура, программирование, интерфейс», -М.: Диалог МИФИ, 1993.

27. М. С. Whitton Memory design for raster graphics displays // IEEE Computer Graphics and Applications, Vol. 4, No. 3,1984, pp. 48-65.

28. J.H. Clark and M. Hannah Distributed Processing in a High Performance Smart Image Memory // Lambda, Vol.1, No.3,4-th quarter 1980, pp. 40-45.

29. H. Fuchs and J. Poulton Pixel Planes: A VLSI-Oriented Design for a Raster Graphic Engine // A VLSI Design, Vol. 2, No. 3, 3-d quarter 1981, pp. 20-28.

30. Danielson P.-E. Comments on circle generation for display devices // Computer Graphics and Image Processing, 1978, Vol. 7 №2, pp. 300-301.

31. J.E. Bresenham Algorithm for Computer Controle of Digital Plotter // IBM System Journal, 4(1), July 1965, pp. 25-30.

32. P.L. Gardner Modification of Bresenham's Algorithms for Displays // IBM Tech. Disclosure Bull., Oct. 1975, pp. 1595-1596.

33. J. Boothroyd and P.A. Hamilton Exactly Reversible Plotter Paths // Australian Computer J., Vol 2, No. 1,1970, pp. 20-21.

34. J.E. Bresenham Ambiguities in Incremental Line Rastering // IEEE CGA, May, 1987, pp. 31-43.

35. Y. Suenaga, T. Kamae, T. Kobayashi A High-Speed Algorithm for the Generation of Straight Lines and Circular Arcs // IEEE Transactions on Computers, Vol. TC-28, Oct, 1979, pp. 728-736.

36. R. Brons Linguistic methods for the description of a straight line upon a grid // Computer Graphics and Image Processing, No. 3,1974, pp. 48-62.

37. M.L.V. Pitteway and A. Green Bresenham's algorithm with run-line coding shortcut // The Computer Journal, Vol. 25, No. 1. 1982, pp. 114-115.

38. C.M.A. Castle and M.L.V. Pitteway An Efficient Structural Technique for Encoding 'Best-fit' Straight Lines // The Computer Journal, Vol. 30, No. 2. 1987.

39. A. Rosenfeld Digital Straight Line Segments // IEEE Transactions on Computers, Vol. C-23, No. 12, Dec. 1974, pp. 1264-1269.

40. G.B. Reggiory Digital Computer Transformations for Irregular Line Drawings // Tech. Report 403-22, New York University, New York, Apr. 1972.

41. J.E. Bresenham Run Length Slice Algorithm for Incremental Lines // Fundamental Algorithms for Computer Graphics, Series F, Vol. 17, NATO Advanced Study Instr., R.A. Earnshaw, ed., Springer-Verlag, Berlin, 1985, pp. 59-104.

42. V. Boyer and J.J. Baurdin Auto-Adaptive Step Straight-Line Algorithm // IEEE Computer Graphics and Applications, Sept./Oct. 2000, pp. 67-69.

43. P. Stephenson and B. Litow Why step when you can run? // IEEE Computer Graphics and Applications, Nov./Dec. 2000, pp. 76-84.

44. J.Rokne and Y.Rao Double-Step Incremental Linear Interpolation // ACM Trans. Graphics, Vol. 11, No. 2, Apr. 1992, pp. 183-192.

45. X. Wu and J. Rokne Double-Step Incremental Generation of Lines and Circles // Computer Vision, Graphics, and Image Processing, Vol. 37, No. 3, Mar. 1987, pp. 331-344.

46. X. Wu and J.G. Rokne Double-Step Generation of Ellipses // IEEE Computer Graphics and Applications, Vol. 9(3), May 1989, pp. 56-69.

47. P.Graham and S.Sitharama Iyengar Double- and Triple-Step Incremental Linear Interpolation // IEEE Computer Graphics and Applications, May 1994, pp. 49-53.

48. P. Bao and L.Rokne Quadruple-Step Line Generation // Computers&Graphics, Vol. 13, No. 4, 1989, pp. 461-469.

49. G.W. Gill N-Step Incremental Straight-Line Algorithms // IEEE Computer Graphics and Applications, May 1994, pp. 66-72.

50. J. Bresenham A Linear Algorithm for Incremental Digital Display of Circular Arcs // Communications of the ACM, Vol. 20., No. 2, Feb. 1977, pp. 100-106.

51. B.K.P. Horn Circle Generators for Display Devices // Computer Graphics and Image Processing, No. 5 (1976). pp. 280-288.

52. M. Doros Algorithm for Generation of Discrete Circles, Rings and Disks // Computer Graphics and Image Processing, No. 10 (1979). pp. 366-371.

53. N. Badler Disk Generators for a Raster Display Device // Computer Graphics and Image Processing, Vol. 6, 1977, pp. 589-593.

54. Galton An Efficient Three-Point Arc Algorithm // IEEE Computer Graphics and Applications, Nov., 1989, pp. 44-49.

55. Jordan B.W., Lennon W.J., Holm B.C., An Improved Algorithm for the Generation of Non-parametric Curves // IEEE Transactions on Computers, C-22(12), Dec. 1973, pp. 1052-1060.

56. M. Pitteway Algorithm for Drawing Ellipses or Hyperbolae with Digital Plotter // Computer Journal, 10(3), Nov. 1967, pp. 282-289.

57. M.D. Mcllroy Best Approximate Circles on Integer Grids // ACM Transactions on Graphics, Vol. 2, No. 4. October 1983, pp 273-263.

58. Z. Kulpa On the Properties of Discrete Circles, Rings, and Disks // Computer Graphics and Image Processing, No. 10 (1979). pp. 348-365.

59. M.D. Ercegovac, T. Lang, J.M. Muller, A. Tisserand Reciprocation, Square Root, Inverse Square Root, and Some Elementary Functions Using Small Multipliers // IEEE Transactions on Computers, Vol. 49, July 2000, No. 7, pp. 628637.

60. W.F. Wong, E. Goto Fast Evaluation of the Elementary Functions in Single Precision // IEEE Transactions on Computers, Vol. 44, March 1995, No. 3, pp. 453457.

61. P. M. Farmwald High bandwidth evaluation of elementary functions // Proc. Fifth Symp. Computer Arithmetics, 1981, pp. 139-142.

62. P.T.P. Tang Table-lookup algorithms for elementary functions and their error analysis // Proc. 10th IEEE Symp. Computer Arithmetics, June 1991, pp. 232236.

63. ICOS Индустриальные компьютерные системы. Каталог продукции. Выпуск 5.0.

64. Third-Generation TMS320C30 User's Guide. Texas Instruments.

65. А. В.В. Чекушкин, О.В. Юрин Прецизионный синусно-косинусный таблично-алгоритмический преобразователь // Информационный листок, Владимир, ЦНТИ, 1998, 4 с.