Хмельник Соломон Ицкович : другие произведения.

Компьютерная арифметика геометрических фигур. Алгоритмы и аппаратура

Самиздат: [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь|Техвопросы]
Ссылки:
Школа кожевенного мастерства: сумки, ремни своими руками
 Ваша оценка:
  • Аннотация:
    В книге рассматриваются различные варианты процессоров, предназначенных для аффинных преобразований многомерных фигур - плоских и пространственных. Эти процессоры ориентированы на аффинное преобразование неструктурированных геометрических фигур с произвольным характером распределения точек. При этом ипользуется нетрадиционная форма представления данных, основанная на малоизвестной теории кодирования векторов и геометрических фигур. Задачи аффинного преобразования пространства широко используются в науке и технике. Примерами их применения могут служить компьютерная томография и сжатие информации для телекоммуникационных систем. В книге описывается теория кодирования фигур - структура кодов, алгоритмы кодирования, декодирования плоских и пространственных фигур, арифметические операции с плоскими и пространственными фигурами. Теория дополняется многочисленными примерами. Рассматривается несколько вариантов геометрического процессора - представление данных, операционные блоки, техническая реализация алгоритмов кодирования, декодирования и арифметических операций. Оценивается быстродействие этих процессоров.
  
  Для бесплатного скачивания вызывайте PDF-1.4MB. Это откроется в новом окне.
  Посмотреть проспект и купить бумажный вариант можно в издательстве Lulu.Ltd. Это также откроется в новом окне.
  
  Оглавление
  1. Введение \ 10
  2. Прототипы \ 16
  2.1. Представление данных \ 16
  2.2. Простейшее арифметическое устройство \ 18
  2.3. Арифметическое устройство с прямоугольными кодами \ 21
  3. Основы компьютерной арифметики комплексных чисел и векторов \ 23
  3.1. Метод кодирования комплексных чисел \ 23
  3.2. Специальная алгебра в векторном пространстве \ 25
  3.2.1. Алгебра в трехмерном векторном пространстве \ 25
  3.2.2. Покомпонентное умножение \ 26
  3.2.3. Векторное произведение \ 26
  3.2.4. Скалярное произведение \ 26
  3.2.5. Поворот вектора \ 26
  3.2.6. Центроаффинное преобразование \ 27
  3.2.7. Многомерное пространство \ 28
  3.3. Два способа синтеза кодов многомерных векторов \ 29
  3.3.1. Способ 1 \ 29
  3.3.2. Способ 2 \ 30
  3.4. Алгебраическое сложение М-кодов \ 33
  3.4.1. Многоразрядные схемы для М-кодов \ 33
  3.4.2. Инвертор М-кода \ 34
  3.4.3. Инверсный сумматор М- кодов \ 35
  3.4.4. Сумматор М- кодов \ 36
  3.4.5. Вычитатель М- кодов \ 37
  3.4.6. Знакоопределитель М- кодов \ 38
  3.5. Умножение многомерных векторов \ 40
  3.5.1. Метод умножения многомерных и векторов \ 40
  3.5.2. Умножение на базовую функцию для векторов по основанию (3.3.10) \ 40
  3.5.3. Умножение на базовую функцию для векторов по основанию (3.3.7) \ 40
  3.5.4. Умножение целых кодов векторов по основанию (3.3.10) \ 42
  3.5.5. Умножение целых кодов векторов по основанию (3.3.7) \ 42
  3.5.6. Покомпонентное умножение многомерных векторов \ 42
  3.6. Скалярное и векторное умножения \ 45
  3.6.1. Скалярное произведение \ 45
  3.6.2. Векторное произведение \ 46
  3.6.3. Переносы при скалярном умножении \ 47
  3.6.4. Переносы при векторном умножении \ 49
  3.7. Алгоритмы и устройства для кодирования и декодирования многомерных векторов \ 52
  3.7.1. Кодирование комплексного числа в системе 1 \ 52
  3.7.2. Декодирование комплексного числа в системе 1 \ 53
  3.7.3. Кодирование комплексного числа в системе 2 \ 53
  3.7.4. Декодирование комплексного числа в системе 2 \ 54
  3.7.5. Кодер положительного P-кода в М-код \ 55
  3.7.6. Декодер М-кода в Р-код \ 57
  3.7.7. Полный декодер М-кода в Р-код \ 59
  3.7.8. Прекодер Р-кода в М-код \ 60
  3.7.9. Распределитель частей кода \ 60
  4. Векторный процессор \ 61
  4.1. Представление данных и векторное арифметическое устройство \ 61
  4.2. Сравнения \ 65
  5. Теория кодирования фигур \ 68
  5.1. Первичные геометрические коды \ 68
  5.1.1. Структура данных \ 68
  5.1.2. Арифметические операции с геометрическими кодами по действительному основанию \ 71
  5.1.2.1. Общие положения \ 71
  5.1.2.2. Запись базисного кода \ 72
  5.1.2.3. Транспонирование \ 73
  5.1.2.4. Сложение геометрического и базисного кодов по основанию (2) \ 73
  5.1.2.5. Алгебраическое сложение геометрического и базисного кодов по основанию (2) \ 76
  5.1.2.6. Алгебраическое сложение геометрического и базисного кодов по основанию (-2) \ 76
  5.1.2.7. Умножение геометрического и базисного кодов \ 79
  5.1.2.8. Деление геометрического кода на базисный код \ 84
  5.1.2.9. Округление геометрического кода \ 84
  5.1.3. Геометрические коды по комплексному основанию \ 85
  5.1.3.1. Алгебраическое сложение геометрического и базисного кодов \ 85
  5.1.3.2. Умножение геометрического и базисного кодов \ 87
  5.1.4. Кодирование и преобразование плоских фигур \ 94
  5.1.4.1. Метод кодирования \ 90
  5.1.4.2. Перенос \ 95
  5.1.4.3. Центроаффинное преобразование \ 95
  5.1.4.4. Аффинное преобразование \ 95
  5.1.5. Кодирование и преобразование пространственных фигур \ 97
  5.2. Атрибутные геометрические коды \ 103
  5.2.1. Структура данных \ 99
  5.2.2. AGC по действительному основанию \ 102
  5.2.2.1. Запись данного номера \ 102
  5.2.2.2. Запись и поиск данного значения \ 102
  5.2.2.3. Чтение значения пути с данным номером \ 103
  5.2.2.4. Сложение AGC с базисным кодом по основанию (2) \ 103
  5.2.2.5. Обратное сложение AGC с базисным кодом по основанию (-2) \ 105
  5.2.2.6. Инвертирование AGC по основанию (-2) \ 107
  5.2.2.7. Алгебраическое сложение AGC \ 108
  5.2.2.8. Поиск следующегого открытого пути, его номера и его значения \ 108
  5.2.2.9. Умножение AGC на базисный код \ 109
  5.2.3. Атрибутные геометрические коды по комплексному основанию \ 110
  5.2.3.1. Обратное сложение AGCC с базисным кодом \ 110
  5.2.3.2. Инвертирование \ 111
  5.2.3.3. Центроаффинное преобразование \ 111
  5.2.4. Атрибутные геометрические коды пространственных фигур \ 116
  5.2.5. Сокращенные атрибутные геометрические коды \ 119
  6. Геометрический процессор \ 121
  6.0. Представление данных \ 121
  6.1. Полная специализированная оперативная память \ 124
  6.2. Фрагментарная специализированная оперативная память \ 125
  6.3. Максимальное арифметическое устройство геометрических фигур \ 129
  6.4. Фрагментарное арифметическое устройство геометрических фигур \ 130
  6.5. Процессор с максимальным арифметическим устройством \ 132
  6.6. Процессор с фрагментарным арифметическим устройством \ 135
  6.7. Основные процедуры \ 138
  6.7.1. Аффинное преобразование \ 138
  6.7.2. Округление \ 138
  6.7.3. Грубое округление \ 139
  6.7.4. Коррекция атрибутов \ 140
  6.7.5. Вычисление атрибутов \ 140
  6.7.6. Кодирование фигуры \ 141
  6.7.7. Декодирование фигуры \ 141
  6.8. Операционные блоки \ 143
  6.8.1. Блок записи номера с данным кодом \ 143
  6.8.2. Блок записи значения с данным кодом \ 144
  6.8.3. Блок чтения значения пути с данным номером \ 145
  6.8.4. Обратный сумматор \ 146
  6.8.5. Блок поиска первого открытого пути \ 147
  6.8.6. Блок чтения номера и значения пути с данной терминальной вершиной \ 148
  6.8.7. Блок поиска следующей терминальной вершины \ 149
  7. Сравнительный анализ \ 150
  Литература \ 156
  Обозначения \ 157
  Список примеров \ 160
  Список таблиц \ 161
  Список рисунков \ 163
  
  1. Введение
  В книге рассматривается полная малоизвестная теория и запатентованные инженерные решения для компьютерной арифметики геометрических фигур - плоских и пространственных. Эта теория ориентирована на аффинное преобразование неструктурированных геометрических фигур с произвольным характером распределения точек. Именно выявление структуры и является целью преобразования. Поэтому наблюдаемый объект может быть определен только как пространство, каждая точка которого имеет некоторые характеристики. Задачи аффинного преобразования пространства широко используются в науке и технике - в медицине, обработке и визуализация данных, астрономии, сейсмологии и т.д. Наиболее яркими и хорошо известными примерами применения аффинного преобразования могут служить компьютерная томография (см., например, [1]) и сжатие информации для телекоммуникационных систем (см., например, [2]).
  В книге рассматриваются аффинные преобразования (перемещения, повороты, масштабирование, сдвиги) n-мерных где n=2, 3, 4. Обычно указанные преобразования фигур выполняются путем вычисления координат точек преобразованной фигуры по известным координатам точек исходной фигуры. Однако такой метод требует много процессорного времени, так как вычисление координат выполняется последовательно для всех точек и требует нескольких операций для каждой точки (например, для вычисления новых координат при аффинном преобразовании плоской фигуры требуется по 4 операции сложения и умножения).
  Указанные задачи включают операции с комплексными числами, так как точка на плоскости может быть представлена комплексным числом. При этом одноименные операции могут выполняются одновременно с множеством комплексных чисел. Для решения подобных задач используются процессоры с архитектурой SIMD (Single Instruction, Multiple Data). Однако эти процессоры оперируют с действительными числами. При этом каждая операция с комплексными числами требует нескольких операций с действительными числами - действительными и мнимыми частями этих комплексных чисел. Аналогично, геометрические преобразования в трехмерном пространстве используют операции с трехмерными векторами - тройками действительных чисел. При этом каждая операция с векторами требует еще больше операций с действительными числами. Все это значительно увеличивает время вычислений. Кроме того, множество комплексных чисел и векторов, описывающих фигуру, занимает большой объем памяти. Имеется, таким образом, потребность в методе и системе для эффективных SIMD вычислений с множеством комплексных чисел и векторов, описывающих фигуру. Эти вычисления должны быть эффективными по времени вычислений и требуемой памяти.
  Решение указанных задач может быть значительно ускорено при специальном кодировании множества комплексных чисел и векторов. В связи с этим далее рассматривается метод представления множества комплексных чисел и векторов так называемым геометрическим кодом, а затем описываются различные операции с ним, а также аппаратная реализация этих операций. Геометрические коды предложены в [3, 4] и рассмотрены также в [5-11]. При построении геометрического кода используется метод представления комплексных чисел и векторов единым двоичным кодом [11, 12, 13].
  Этот метод заключается в том, что координаты двоичных кодов комплексных чисел и векторов изображается единым двоичным кодом. Его объем существенно меньше суммарного объема массива исходных двоичных кодов. Относительное сокращение объема зависит от количества кодируемых чисел и растет с увеличением этого количества.. Кодируемое множество комплексных чисел НЕ структурировано. Можно говорить о их случайном множестве. Кодируемые комплексные числа и векторы являются множеством координат (что существенно), с которыми надо выполнять вычисления. Дополнительная информация о точках (например, цвет), если она не участвует в вычислениях, кодированию не подлежит и должна храниться в отдельном массиве - массиве атрибутов. Геометрический код хранит (помимо координат) также информацию о связях каждой точки с ее атрибутами.
  С геометрическим кодом выполнимы арифметические операции (алгебраическое сложение, умножение комплексных чисел и векторов, аффинное преобразование). Эти операции эквивалентны групповым операциям с координатами всех точек одновременно.
  Важно отметить, что время выполнения операции с геометрическим кодом равно времени выполнения одноименной операции с парой чисел, если весь геометрический код помещается в оперативном регистре арифметического устройства. Предполагается, что исходные коды являются кодами с фиксированной точкой (например, координатами точки на экране).
  Предлагается также метод фрагментации геометрического кода, который позволяет оперировать с отдельными фрагментами геометрического кода, если разрядность регистра арифметического устройства не достаточна для хранения полного кода.
  Важно отметить, что геометрический код позволяет оперировать с фигурой, как с целым, единственным объектом. При этом объем данных (кодов координат) сокращается. Однако (и это важно подчеркнуть для исключения заблуждений) геометрический код не сжимает сами геометрические фигуры. Предполагается, что кодируемая геометричекая фигура описывается случайным набором точек и не имеет какой-либо структуры, что характерно для растровых изображений.
  В общем, применение GC сокращает объем данных в n раз, где n - разрядность линейных кодов. Скорость выполнения групповых операций с геометрическими кодами во много раз превышает скорость таких же операций с массивом чисел. Общее время выполнения вычислений сокращается еще и за счет уменьшения времени доступа к данным.
  Далее рассматриваются три вида арифметических устройств -
   традиционное, оперирующее с действительными числами и содержащее несколько вычислителей, работающих параллельно,
   векторное, оперирующее с предложенными кодами векторов и также содержащее несколько вычислителей, работающих параллельно и
   геометрическое, оперирующее с геометрическими кодами фигур.
  Рассматривается также устройство специализированной оперативной памяти, выполненное на основе метода кодирования геометрических фигур.
  Приводится сравнение качества этих устройств. Естественно характеризовать качество устройства отношением объема устройства к количеству определенных процедур, выполняемых устройством в единицу времени. Будем называть это отношение относительным объемом устройства. Для арифметических устройств типовой процедурой является аффинное преобразование. Для устройств оперативной памяти типовой процедурой является либо поиск точки с данными координатами в неупорядоченном массиве, либо обычный доступ, либо, наконец, заданная смесь этих процедур.
  Для сравнения вариантов исполнения оперативной памяти предположим, что в данной задаче операции чтения\записи встречаются в Н раз чаще, чем операции поиска по данным координатам. Показано, что относительный объем специализированного запоминающего устройства меньше относительного объема традиционного запоминающего устройства в (~M/10H) раз.
  
  Книга содержит 7 глав, включая данное введение.
  Во второй главе рассматриваются известные устройства для преобразования фигур - с одним и несколькими вычислителями. Эта информация используется далее для аналогий и сравнения.
  В третьей главе приводятся основы компьютерной арифметики комплексных чисел и векторов - теория и аппаратные решения. Эта глава необходима, поскольку при кодировании и декодировании геометрического кода фигуры используются коды комплексных чисел и векторов.
  В четвертой главе описывается векторное арифметическое устройство, основанное на векторной компьютерной арифметике, изложенной в предыдущей главе.
  В пятой главе описывается теория кодирования фигур - структура кодов, алгоритмы кодирования, декодирования плоских и пространственных фигур, арифметические операции с плоскими и пространственными фигурами. Теория дополняется многочисленными примерами.
  В шестой главе рассматривается устройство растрового геометрического процессора - представление данных, операционные блоки, техническая реализация алгоритмов кодирования, декодирования и арифметических операций, а также оценивается быстродействие этого процессора.
  В седьмой главе приводится сравнение характеристик арифметических устройств и блоков оперативной памяти, предназначенных для операций с фигурами. Сравниваются рассмотренные в предыдущих главах традиционные устройства, устройства векторной арифметики и устройства арифметики геометрических фигурам.
  Книга ориентирована на студентов, инженеров и разработчиков, которые намерены применять компьютерную арифметику геометрических фигур в собственных разработках специализированных процессоров. С этой целью книга включает
   Теорию кодирования
   Алгоритмы операций
   Примеры кодирования, декодирования и вычислений
   Описание нескольких вариантов процессоров
   Системы команд для них
   Схемы операционных блоков
   Сравнительный анализ
  Предлагаемые в книге алгоритмы и устройства разрабатываются в виде моделей на VHDL и FPGA. Любые предложения о сотрудничестве посылайте по адресу
  solik@netvision.net.il
 Ваша оценка:
Связаться с программистом сайта.

Новые книги авторов СИ, вышедшие из печати:
О.Болдырева "Крадуш. Чужие души" М.Николаев "Вторжение на Землю"

Как попасть в этoт список

Кожевенное мастерство | Сайт "Художники" | Доска об'явлений "Книги"