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

Computer Arithmetic of Geometrical Figures. Algorithms and Hardware Design

Самиздат: [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь|Техвопросы]
Ссылки:
Школа кожевенного мастерства: сумки, ремни своими руками
 Ваша оценка:
  • Аннотация:
    This book describes various versions of processors, designed for affine transformations of many-dimensional figures - planar and spatial. This processors is oriented to affine transformation of unstructured geometrical figures with arbitrary points distribution. The type of data presentation used in this book is non-conventional, based on a not well-known theory of vectors and geometrical figures coding. The problems of affine transformation are used widely in science and engineering. The examples of their application are computer tomography and data compression for telecommunication systems. The book covers the figures coding theory - the codes structure, algorithms of coding and decoding for planar and spatial figures, arithmetical operations with planar and spatial figures. The theory is supplemented by numerous examples. The arrangement of several versions of geometrical processor is considered - data representation, operating blocks, hardwares realization of coding, decoding and arithmetic operations algorithms. The processor"s internal performance is appraised.
  
  For free download call PDF-1MB. It will open in a new window.
  You can of prospectus or buy the printed version in Publisher Lulu.Ltd. It also opens in a new window.
  
  Contents
  1. Introduction \ 8
  2. Prototypes \ 13
  2.1. Data Representation \ 13
  2.2. The Simplest Arithmetic Unit \ 14
  2.3. Arithmetic Unit with Rectangular Codes \ 17
  3. Foundations of Computer Arithmetic for Complex Numbers and Vectors \ 19
  3.1. Coding Method for Complex Numbers \ 19
  3.2. Special Algebra in Vector Space \ 21
  3.2.1. Algebra in 3-dimensional vector space
  3.2.2. Component-wise multiplication
  3.2.3. Vector product
  3.2.4. Scalar product
  3.2.5. The turning of a vector
  3.2.6. Centroaffine transformation
  3.2.7. Many-dimensional space
  3.3. Two Methods of Multidimensional Vectors Coding \ 25
  3.3.1. Method 1
  3.3.2. Method 2
  3.4. Algebraic addition of M-codes \ 29
  3.4.1. Multidigit circuits for M-codes
  3.4.2. M-code Inverter
  3.4.3. M-codes Inverse Adder
  3.4.4. M-code Adder
  3.4.5. M-code Subtractor
  3.4.6. Sign Determinant M-code
  3.5. Multiplication of Many-dimensional Vectors \ 36
  3.5.1. Multiplication Method of Many-dimensional Vectors
  3.5.2. Multiplication by Base Function to the Radix (3.3.10)
  3.5.3. Multiplication by Base Function to the Radix (3.3.7)
  3.5.4. Multiplication of the Whole Codes of Vectors to the Radix (3.3.10)
  3.5.5. Multiplication of the Whole Codes of Vectors to the Radix (3.3.7)
  3.5.6. Componentwise Multiplication of Many-dimensional Vectors
  3.6. Scalar and Vector Multiplication \ 41
  3.6.1. Scalar Product
  3.6.2. Vector Product
  3.6.3. Carries in Scalar Multiplication
  3.6.4. Carries in Vector Multiplication
  3.7. Algoritms and Devices for Coding\Decoding of Complex Numbers and Vectors \ 48
  3.7.1. Coding of Complex Number in System 1
  3.7.2. Decoding of Complex Number in System 1
  3.7.3. Coding of Complex Number in System 2
  3.7.4. Decoding of Complex Number in System 2
  3.7.5. Coder of Positive M-code into P-code
  3.7.6. Decoder of M-code into P-code
  3.7.7. Full Decoder of M-code into P-code
  3.7.8. Precoder of P-code into M-code
  3.7.9. Partitioning Unit for Parts of the Code
  4. Vector Processor \ 57
  4.1. Data Representation and Vector Arithmetic Unit \ 57
  4.2. Comparisons \ 61
  5. Figure Coding theory \ 65
  5.1. Primary Geometrical Codes \ 68
  5.1.1. Data Representation
  5.1.2. Arithmetic operations with geometrical codes in a real radix
  5.1.2.1. Introduction
  5.1.2.2. Writing of Base Code
  5.1.2.3. Transpositions
  5.1.2.4. Addition of Geometrical and Basic Codes when r=2
  5.1.2.5. Algebraic Addition of Geometrical and Basic Codes when r=2
  5.1.2.6. Algebraic Addition of Geometrical and Basic Codes when r=-2
  5.1.2.7. Multiplication of Geometrical and Basic Codes
  5.1.2.8. Division of Geometrical Code by Basic Code
  5.1.2.9. Rounding-off of Geometrical Code
  5.1.3. Geometrical codes in a complex radix
  5.1.3.1. Algebraic Addition of Geometrical and Basic Codes
  5.1.3.2. Multiplication of Geometrical and Basic Codes
  5.1.4. Coding and transformation of planar figures
  5.1.4.1. Method of coding
  5.1.4.2. Carry \ 95
  5.1.4.3. Centroaffine transformation
  5.1.4.4. Affine transformation
  5.1.5. Coding and Transformation of Spatial Figure
  5.2. Attribute Geometrical Codes \ 106
  5.2.1. Data Representation
  5.2.2. AGC in a real radix
  5.2.2.1. Writing of a given Number
  5.2.2.2. Writing of a given Value
  5.2.2.3. Reading the value of the path with the given number
  5.2.2.4. Addition of AGC to the basic code when r=2
  5.2.2.5. Inverse addition of AGC to the basic code when r= -2
  5.2.2.6. Inversion of AGC when r= -2
  5.2.2.7. Algebraic addition of AGC
  5.2.2.8. Search for the Next Open Path, its Number and it's Value
  5.2.2.9. Multiplication of AGC by the basic code
  5.2.3. Attribute geometrical codes in a complex radix
  5.2.3.1. Inverse addition with the basic code
  5.2.3.2. Invertion
  5.2.3.3. Deformation
  5.2.4. Attribute Geometrical Codes of Spatial Figures
  5.2.5. Contracted attribute geometrical codes
  6. Geometrical Processor \ 115
  6.0. Data Presentation \ 115
  6.1. Full Specific Random-access Memory \ 118
  6.2. Fragmentary Specific Random-access Memory \ 119
  6.3. Maximal Arithmetic Unit of Geometrical Figures \ 123
  6.4. Fragmentary Arithmetic Unit of Geometrical Figures \ 124
  6.5. Processor with a Maximal Arithmetical unit \ 126
  6.6. Processor with Fragmentary Arithmetic Unit \ 129
  6.7. The Main Procedures \ 132
  6.7.1. Affine Transformation
  6.7.2. Rounding
  6.7.3. Rough rounding
  6.7.4. Attributes Correction
  6.7.5. Attributes Calculation
  6.7.6. Coding a Figure
  6.7.7. Decoding a Figure
  6.8. Operational units \ 136
  6.8.1. Writing unit for the number with the given code
  6.8.2. Writing unit for the value with the given code
  6.8.3. Reading unit for path value with the given number
  6.8.4. Inverse adder
  6.8.5. Search unit for the first open path, its numbers and its values
  6.8.6. Reading unit for the number and value of the path with the given terminal vertex
  6.8.7. Next terminal vertex search unit
  7. Comparative Analysis \ 143
  References \ 149
  Designation \ 150
  List of Examples \ 152
  List of Tables \ 153
  List of Figures \ 155
  
  1. Introduction
  This book is concerned with a full theory, not well known, and with patented engineering solutions for computer arithmetic of geometrical figures - planar and spatial. This theory is directed to the affine transformation of unstructured geometrical figures with arbitrary way of pints distribution. The transformation is aimed at this structure"s identification. That"s why the observed object may be defined only as a space in which a point has certain characteristics. The problems concerned with affine transformation of space are widely used in science and engineering - in medicine, in data processing and visualization, in astronomy, in seismology etc. Most striking and well-known examples of affine transformation applications are computer tomography (see for instance [1]) and information compression for telecommunication systems (see [2]).
  This book describes affine transformations (displacements, turns, scaling, shifts) of n-dimensional figures, where n=2,3,4. Usually the above-mentioned transformations are performed by calculating the coordinates of the points of the transformed figure according to the known coordinates of the points of the initial figure. However this method takes up a great deal of computer time since the calculation of coordinates is performed sequentially for every point and requires several operations per point (for instance, in order to calculate the new coordinates during an affine transformation of a planar figure, 4 operations each of addition and multiplication are required).
  The above problems include operations with complex numbers since a point on a plane can be represented by a complex number. In this case operations of the same name can be performed simultaneously with a set of complex numbers. Processors with SIMD (Single Instruction, Multiple Data) architecture are used to solve problems of this type. However these processors operate with real numbers, and each operation with complex numbers requires several operations with real numbers - the real and imaginary parts of these complex numbers. Similarly, geometrical transformations in a three-dimensional space operate with three-dimensional vectors - sets of three real numbers. And each operation with vectors demands even more operations with real numbers. All this increases the calculation time substantially. In addition, set of complex numbers and vectors describing a figure takes up a great deal of memory. Thus there is a need for a method and system for effective SIMD calculations with a set of complex numbers and vectors that describe a figure. These calculations must be efficient as to calculation time and memory requirements.
  The solution of the above problems can be greatly accelerated with special coding of sets of complex numbers. Due to that, reviewed further will be a method of representing a set of complex numbers and vectors by a so-called geometrical code, and then various operations with them will be described, as well as the hardware support of these operations. The geometric codes were first put forward in [3, 4] and were considered also in [5-11]. In the construction of a geometrical code a method of complex numbers and vectors representation by a single binary code [11, 12, 13] is being used.
  By this method the set of binary codes of complex numbers and of the vectors is represented by a single binary code. Its volume is considerably smaller that the total volume of the initial binary codes array. The comparative volume reduction depends on the amount of numbers being coded and increases as this amount grows. The coded set of complex numbers is NOT structured. We can say that the set is a random one. The coded complex numbers and vectors are a coordinate set (which is significant) that the calculations are to be performed with.
  Any additional information about the points (for instance, their color), if it does not take part in the calculations, is not subject to coding, and should be saved in a separate array -an attribute array. Geometrical code saves (in addition to the coordinates) also the information about every point"s connection with its attributes.
  All arithmetic operations may be performed with geometrical code (complex numbers and vectors algebraic addition, multiplication, affine transformation). These operations are equivalent to group operations with the coordinates of all points simultaneously.
  It is significant that the performance time of an operation with geometrical code is equal to the performance time of the same operation with a pair of numbers, if only the whole geometrical code may be placed in the operative register of arithmetic unit.
  It is assumed that the initial codes were codes with fixed point (for example, the coordinates of the point on the screen).
  A method of geometrical code fragmentation is also proposed, allowing to operate with separate fragments of the geometrical code, if the arithmetic units register"s dimension is not sufficient to hold the whole code.
  It is important that geometrical code permits to operate with a geometrical figure as a whole, single object. So the data volume (coordinate codes) is reduced. However (and it should be emphasized to avoid mistakes), geometrical code does not compress geometrical figures themselves. It is assumed that the coded geometrical figure is described by a random set of points and does not have any special structure, which is typical for raster images.
  In general, application of GC reduces data volume n times, where n - digit capacity of linear codes. The group operations performance speed is many times higher than the same operations speed for group operation with complex codes array. General computations time is also reduced due to data access time reduction.
  Next we shall consider three types of arithmetic units -
   Traditional, operating with the proposed vector codes and containing several calculators, working simultaneously.
   Vectorial, operating with the proposed vector codes and also containing several calculators, working simultaneously, and
   Geometrical, operating with geometrical codes of figures.
  We shall also consider a specialized random-access memory unit based on the geometrical figures coding method.
  A comparison between the performances of these units is given. It appears reasonable to describe the device"s performance by a ratio between the unit"s volume and the number of certain procedures performed by the unit in a time unit. Let us call this ratio relative volume of a unit. A standard procedure for arithmetic units is affine transformation. For random-access memory units such standard procedures are either search for a point with given coordinates in an unordered array, or plain access, or a mixture of these procedures.
  To compare the variants of random-access memory realization let us assume that in a given problem the reading/writing operations are Н time more frequent than operations of search by given coordinates. It is shown that the relative volume of specialized RAM is (~M/10H) times smaller than the relative volume of traditional RAM unit.
  
  The book consists of 7 chapters, including the present introduction.
  The second chapter is concerned with known devices for figure transformation - with one or several calculators.
  The third chapter presents foundations of computer arithmetic for complex numbers and vectors -theory and hardware solutions. This chapter is essential, since in coding and decoding the geometrical figure code, we have to make use of the codes of complex numbers and vectors.
  In the fourth chapter a vector arithmetic unit is discussed, which is based on vector computer arithmetic, stated in the previous chapter.
  In the fifth chapter the theory of figures coding is described - the structure of codes, coding and decoding algorithms for planar and spatial figures, arithmetic operations with planar and spatial figures. The theory is supplemented by numerous examples.
  The sixth chapter deals with the arrangement of raster geometric processor - data representation, operational units, technical realization of coding, decoding and arithmetic operations algorithms; the operating speed of this processor is also appraised.
  The seventh chapter is dedicated to the characteristics comparison between arithmetic units and random-access memory units designed for operations with figures. The traditional units, described in the previous chapters, are being compared with the vector arithmetic units and geometrical figures arithmetic units.
  
  The book is designed for students, engineers and developers, who intend to use the computer arithmetic of geometrical figures in their own research and development in the field of specialized processors. With that in view the book includes
   Theory of coding,
   Operations algorithms,
   Examples of coding, decoding and computations,
   Description of several versions of processors,
   A system of commands for them,
   Schemes of operational units,
   Comparative analysis.
  
  Algorithms and units described in this book are developed into models in VHDL and FPGA. We shall welcome any kind of cooperation proposals sent to the address:
  solik@netvision.net.il
  
 Ваша оценка:
Связаться с программистом сайта.

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

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

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