Note: Descriptions are shown in the official language in which they were submitted.
`~ 2~03L~g2
DIGI~L VECTCR GæNæRAToR AppARaT~s F~R PR3VIDIN~
MA~I~-TIC~LLY l~ISE VE~SYMME~CAL I~TT
l3a~ OE 1~ IN~IO~
1. Field of the Invention
The invention relates to digital vector generators, specifically
as applied to electronic displays.
2. Descr~etion of the Prior Art
Di~ital vector generators are utilized in the art in various
applications, including electronic displays. For ex~nple, they are u9ed for:
raster sca M ed or caligraphically generated cathode ray tube displays; X-Y
plotters; nurnerically controlled machines; and robotics. Known vector
generation procedures utilize either open-loop or closed-loop curve
generation techniqu~. Open-loop techniques are often advantagecus because
various vector instruction fonmats may be incorporated which shar~ the same
basic hardware. For example, with open-loop techniques, both polar
coordinate and rectangular coordinate vector fornats can be effectively
utili2ed. The execution of polar coordinate v~ctors can greatly simplify
the rotation of symbologyD ~dditionally, the open-loop algorithm penmits
achievi~ constant velocity vector generation, independent of v~ctor
angl~ Constant velocity vector generators can provide for the qeneration
of dotted and da~hed vector patterns that do not change as a function of
vec~or angle~
For ~he rec~angular coordinate system, twa~dim~nsional open loop
vector generation is generally imple~ented utilizing two accumulators for
~he X a~d Y coordinate axes, respectiv~ly, of the vector generation ~ystem.
Tb generate a vector, the a~cumulators are loaded with the X and Y
coordinates of the initial point of the vectorO m e vector is then
generated by adding the incre~ental values o~
2~
--2--
1 DX/N and DY/N to the respective accumulators d~ring each of N clock cycles,
where DX is the X component of the vector and GY is the Y component
thereof~ Generally, each accumulator has an integer portion and a
fractional portion, where the integer portions provide the vector generator
outputs that select the picture elements (pixels) to be illuminated for
displaying the vector. Th-i~ technique of vector generation is denot~d as
open-loop integration. Although the subject invention will b~ described for
the application of two-dimensional vector generation, open-loop vector
qeneration is easily extended to three-dimensional space by the addition of
a third accumulator. It should be appreciated that the improvements of the
invention are also applicable to three-dimensional vector generation.
Open-loop integration generally utilizes either the tangent
algorithm or the sine/cosine algorithm. In the tangent algorithm, the
accumulator corresponding to the axis of the largest vector component is
advanced by one integer unit on every clock cycle and the other accumulator
is advanced by the tangent of the vector angle. In the sine/cosine
algorithm, the X and Y coordinates are advanced on each clock cycle by the
cosine and sine, respectively, of the vector angle. An example of a tangent
algorithm vector generator that may be configured in accordance with the
present invention is disclosed in U.S. Patent 4,115,863; issued SeptEmber
19, 1978; entitled "Digital Stroke Di~play with Vector, Circle and Character
Gbnera~ion Capability". An example of a sine/cosine vector generator that
may be configured in accordance with the present invention is disclosed in
Unlted State~ Patent 4,481,605; issued Nbve~ber 6, 1984; entitl~d "Display
Vector Generator Utili2ing Sine/Cosine Acc~nulation". Said patents
4,11S,863 and 4~481,605 are incorporated herein by reference.
3Z
--3--
1 With vector generation utilizing open-loop integration, truncation
errors in the incremental values that are added to the X and Y accumulators
can result in an accumulation of errors as vectors are generated. Utilizing
open-loop integration results in a compromise to the accuracy of the
displayed symbology causing a degradatlon in display quality. Such
degradation in accuracy results in the illumination of pixels that are not
located on the mathematical locus of the desired vector, resulting in, for
example, line ends that do not meet and open curves that should be closed.
Ihe truncation errors that result in these display anomolies are inherent in
digital vector generation apparatus utilizing open-loop integration.
Truncation errors can be eliminated by utilizing a closed-loop
vector algorithm which is inherently self correcting and in which the
maximum error is inherently bounded. In closed-loop vector generation~ the
error does not increase with vector length. The closed-loop algorithms are,
however, incompatible with vector instructions that utilize the polar
coordinate system to simplify the rotation of symbology. The inherent
advantage of polar vectors for the rotation of symbology can outweigh the
error problems due to truncation and coordinate transformation.
Additionally, as discussed above, constant velocity vector generation cannot
readily be achieved utilizing a closed-loop algorithm.
SUMMaRY OF THE INVENTION
.. ~ .. . _ . .
m e present invention permits vector generation with open-loop
algorithms that is free from the anomolies that non~ally result from
truncation errors. mis is accomplished by presetting the acc~mulator
fractional portions to a value of one-half,or to one-half less 1 LSB, prior
to the generation of each vector, and by limiting the maximum vector length
relative to the accunulator fractional resolution~
2~
--4
1 The presetting of the accumulator fractional portions provides
mathematically perfect vectors in the absence of truncation errors. When
truncation errors are present, the fractional presetting and the limiting of
the maximum vector length restricts the error at the vector end point to the
fractional bits of the accumulator. Presetting of the fractional
accumulator bits prior to the generation of each vector eliminates the
buildup of truncation errors over consecutive vectors. Also, a further
limitation of the maximum vector length ensures the generation of
mathematically perfect vectors utilizing the tangent algorithm.
The present invention also forces the generation of symmetrical
patterns when vectors are concatenated to generate complex symbology.
Symmetry is forced by, in effect, controlling the fractional accumulator
presetting to either one-half or to one-half less 1 LSB. This is achieved
by always presetting to one-half less 1 LSB and then conditionally enabling
the carry input to the accumulators, on the initial clock cycle of a vector,
as a function of the octant in which the vector angle resides.
BRIEF D~9CRIPTION ~ THE D~AWING~
Figure 1 is a schematic block diagram of a vector processor
utilizing open-loop integration implemented in accordance with the present
invention.
Figure lA is a chart illustrating the formats of the various
instructions that can be executed by the hardware of Figure 1 of the present
invention.
Figure 2~ is an illustration of the generation of a vector in
accordance with the prior art.
Figure ZB is an illustration of the generation of a vector
utilizing the present invention.
5-
1 Figure 3A is an illustration of the generation of the letter "V"
in accordance with the present invention with the accumulato~s initialized
to one-half.
Figure 3B is an illustration of the geneLation of the letter 'iV"
in accordance with the present invention with the accumulators initialized
to one-half minus 1 LSB. "
Figure 3C is an illustration of the generation of the letter "V"
in accordance with the invention utilizing a sym~etrical algorithm.
Figure 4 is a diagran of the cartesian coordinate octant
deEinition~ utilized i~ the symmetrical algorithms of the present invention.
Figure 5A is an illustration of the generation, in accordance with
the invention,of an octagon utilizing concatenated vectors without using a
symmetrical algorithm of the present invention.
Figure SB is an illustration of the generation, in accordance with
the invention, of an octagon utilizing concatenated vectors using a
symmetrical algorithm of ~he present invention.
Figure 6 is an annotated octagonal chart useful in explaining ~he
operation of the symmetrical algorith~s of the present invention~
DE9S~IPTION CF THE EtEall~KED ~M~oD~MENTS
The present invention modifies the basic technique of open-loop
vestor generation so as to eliminate the errors that normally result
thereram. A two-dimensional vector in the rectangula~ coordinate system
can be generat~d With two digital accumulators, one for the X axis and one
for the Y axis. A v~tor is generated by adding an incremental value DX/N
to the X accumulator and an incremental val~e DY/N to the Y accumulator on
each of N clock cycles. Since the fraction~l portions of the accumulators
are of a finite size, the DX/N and DY/N values that are added thereto can
include tr~ncation errors. Errors can therefore increase
-6-
1 in the X and Y accumulators over a number of clock cycles until the integer
values thereof, whicb are the vector generator outputs, are in error. Since
the probability of an integer error increases with the number of clock
cycles, errors will be prevalent when vectors are concatenated to generate
extensive complex symbology. The present invention, however, el~minates
error accumulation over the generation of multiple vectors by assuring that
no integer error can occur at the end point of any single vector, and by
resettin9 the fractional portion of each accumulator on the last cluck cycle
of every vector in order to discard any error that has accumulated. The
present invention also generates mathematically perfect vectors using the
tangent algorithm, provided that the fractional resolution of the
accumulators is sufficiently high relative to the length of the genara~ed
vector. A mathematically parfect vector has no integer arror at any point
thereof. The invention also provides additional mKdiications to the open-
loop vector generator that can force the generation of symmetrical patterns
when vectors are concatenated to generate complex symbologyO
In the most general approach to a hardware vector generatcr, using
the technique of open-loop integration, an accumulator device is used for
each vector axis. Thus, two accumulators are required for two-dimensional
v~cto~ genera~ion; and three are required for three-dimensional vector
generation. Input data buffex re~ister~, one for each accumulator, can be
~sed to hold the incremental values that are added to each respective
accumulator on every cl~ck cycle du~lng the generation of a given vector~
In order to control the number of clock cycles that are u~ed in the
generation of a given vector, a counter circuit is also employed.
The hardware circuiSry c~mprising: the set of accumulators; the
input data bufer registers; the length counter; and all required control
logic, tog~thex constitute a vector execution CilCUitCo A low-cost vector
9~
--7--
1 generator system might incorporate a general-purpose microcomputer along
with such a vector execution circuit The microcomputer can execute output
instructions in order to transfer the required data parameters to the vector
execution ci~cuit and to initiate each vector generation operation. This
approach to vector generation is, however, rather limited in its
performance. For high throughput vector generation, a special purpose
processor is often employed~
Figure 1 is a block diagram of a special purpose processor that is
designed to execute vector instructions in accordance with the invention.
It is designed for execution of the instruction types that are illustrated
by Figure lA. The vector processor of Figure 1 is designed for two-
dimensional vectors. Accordlngly, it incorporates two accumulator3. The X
accumulator 30 and the Y accumulator 10 are identical in design. The X
accumulator incorporates a register 31 whose integer and fractional inputs
are derived, respectively, from separate integer 3~ and fractional 33
multiplexers~ Also included in the X accumulator is an adder 34 whose
inputs consist of the X register output 47 and an incremental value that is
derived from the output 35 of an X multiplexer 54 that is external to the X
a w umulator. ~he range of values for the incremental input is generally of
less magnitude than the range of values of the X register output. ~owever,
the val~e 35 from the X mult~plexer 54 can be sign extended so that the
incremental i~put to the adder has the same n~mber of bits as does th2 X
register.
Al~hough the X registPr output 47 incorporat~s both integer arx~
fractional bits, only the integer portion thereof is used as the accumulator
output ~8. Similarly, for the Y accumulator 10, only the integer portion ~8
of the Y register output 27 is used as the accumulato~ output. For the
application of a display symbol generator for a raster scann~d display~ t~e
2~ gz
--8--
1 X 48 and Y 28 outputs are normally used to address a two-dimensional display
imag2 memory for the purpose of writing vectors into said memory. For a
caligraphic CRT display, the X and Y outputs are each converted to an analog
signal. These analog signals then control the position of the electron b~am
of the CRT for directly "writing" vectors onto the CRT display screen.
All the registers and counters of Figure 1 can be loaded or
advanced, as required, on the same edge of a single clock signal, thereby
allowing the use of a single phase clock. Curing an instruction fetch
cycle, the addrass of the instruction to be executed is held in the program
lQ counter 61. The output of the program counter 87 is gated through the
multiplexer 63 to the address input 82 of the progr~n memory 64. At the end
of the instruction fetch cycle, the transition of the single phase clock
signal will increment the program counter so that during the next clock
cycle the program counter will hold the program memory address of the next
sequentially higher location in the memory. Said memory location may
contain the next instruction to be executed or may contain the second word
of the instruction that was just fetched.
Note tha~ each of th~ instruction formats of Figure lA
incorporate~ an operation code field that is always located in the more
significant bit~ of a single-word instruction 120 or in the more significant
bits of ~he first word of a two-word instruction 101. At ~he end of an
instruction ~etch cycle, the instruction word (or the first word of a two-
word instruction) is available on the data output 81 of the progr~n memory
64. The transition of the clock signal at the end of the instruction fetch
cycle loads the entire instruction word into the D regi~ter 59. Also, the
operation code bits of the instruction word 88 are loaded into the OP code
register 52; and the lower bits of the instruction word 89~ that are used
for a length count in the TAN vector instruction 104 and in the POL~R VECTOR
instruction 113, ar~ loaded in'~ tha L counter 53O
_9_
The output 95 of the OP code register 52 is used by the control
logic 51 during each instruction execution sequence in order to derive the
control signals that are required for the proper execution of the
instruction. The control signals required oE the two acc~mulators are shown
in Figure 1. However, in the interest of simplicity, the control signals to
the other blocks of Figure 1 are not depicted. The control signals to the X
accumulator consist of: A carry input 36 to the least significant bit of the
adder 34; A select input 37 to the fractional multiplexer 33 to control
whether the fractional portion 42 of the adder output 40 or the fixed binary
value 43 of .0111... 1 is gated to the multiplexer output 45; A select inp~t
38 to the integer multiplexer 32 to control whether the integer portion 41
of the adder output 40 or the accumulator input 35 is gated to the
multiplexer output 44; and a gated clock signal 39 for conditionally loading
the register 31 of the X accumulator at the end of a given clock cycle. An
alternative to the use of a gated clock signal 39 would be to employ a type
of register that makes use of the primary clock signal, which is active on
every cycle, along with an enable signal that determines the cycles on which
the register is to be loaded.
m e reference n~m~rals 11-28 denote components in the Y
2~ accumulator 10 identical to those describ~d with respect to the X
accumulator 3g.
The preferred embodiment of the invention uses the binary two's
cGmplement number system. The accumulators of Figure 1 incorporate features
that are specifically designed to accommodate the invention. One such
feature is the conditional carry input to the two's complement adder of each
accumulator. Another is the use of the constant value ~01110~1 for the
initial value of the fractional portion of the acc~mulator. Still another
is the use of separate multiplexers for independently selecting the
fractional and integer inputs to be loaded into the accumulator registerO
--10--
1 On the first cycle of either a jump instruction or a subroutine
jump in~truction, the lower bits of the D register output 84, that
correspond to the address field bits of the jump instruction 121 or of the
subroutine jump instruction 123, are gated through the multiplexer 62 to the
input 86 of the program counter 61 and loaded into the program counter at
the end of the first clock cycle of the respective instruction. The second
clock cycle of these instructions is an instruction fetch cycle. It loads
the next instruction that is to be executed, which is located at the program
memory address previously loaded into the program counter. Also, for the
subroutine jump instruction, the output of the program counter 87 is loaded
into the A register 60 at the end of the first clock cycle. This saves, in
register A, the address of the instruction that follows the subroutine ]ump
instruction~ On the first cycle of a return instruction, the A register
output 85 is gated through the multiplexer 62 to the program counter input
86 and is loaded into the program counter at the clock transition occurring
at the end of said first cycle. The second cycle of a return instruction is
an instruction fetch cycle. m e return instruction is therefore followed by
the execution of the instruction that immediately follows the most recently
executed subroutine jump instruction. It should be appreciated that if
multiple levels of subroutines are required (i.e., nested subroutines), then
the A register 60 can be replaced with a last-in-first-out regi3ter stack.
m e load control instruction requires only a single clock cycle
for execution. In addition to being an instruction fetch cycle, this single
clock cycle also loads the V register 65 with the lower bits of the output
84 from the D register~ These bits correspond to the miscellaneous field
119 and the video field 118 of the load control instruction word. The
output of the V register 99 can be used to control the video intensity
-11
an~Qr the color of displayed vectors~ Some of the V register output bits
(e.g., tho5e corresponding to the miscellaneous bits 119) might also be used
to enable/disable a video modulation for the generation of vectors having a
selectable dotted or dashed pattern.
On the first clock cycle of a loaa bias instruction, the second
word o the instruction, which contains the rotation angle 112, is loaded
into the D register from the output 81 of the program memory. The program
co-~ter 61 is also incremented in order to address the next instruction.
The second clock cycle i9 an instruction fetch cycle, and it also loads the
bias register 57 with the output 84 of the D register. The bias register is
u5ed with polar vector instructions to cause a rotation of the generated
vectors.
The load XY instruction is used to load an initial X value 100 and
an initial Y value 103 into the X and Y accumulators, respectively. On the
first clock cycle of the instruction execution, the output 84 of the D
register is gated through the addend logic 58 to the input 92 of the X
multiplexer 54~ It is also gated through the X multiplexer 54 to the input
35 of the integer multiplexer 32, gated through the integer multiplexer to
the integer portion 44 of the input 46 to the register 31 of the X
accunulator, and loaded into thP integer portion of ~aid register 31 at the
end of ~he cycleO Also, the value 001110~1 is gated through the ractional
multiplexer 33 to the fractional portion 45 of the input 46 to the register
31 of the X accumulator, and it is loaded into the fractional portional of
said register at the end o the cycle.
Also on the first clock cycle of the load XY instruction, the
second word of the instruction, which includes the initial value of Y 103t
is transferred from the program m~mory to the D register. The program
counter is also incremented. The second clock cycle is an instruction fetch
2~
1 cycleO Also on the second clock cycle, the D register is gated through the
addend logic 58, the Y multiplexer 50, and the Y integer ~ultiplexer 12, and
is loaded into the integer portion of the register 11 of the Y accumulator.
The value 0.111...1 is also gated through the Y fractional multiplexer 13
S and loaded into the fractional portion of the register 11 of the Y
accumulator.
On the first clock cycle of either the tan vector or the polar
vector instruction, the program counter 61 is incremented and the second
word of the respective instruction is transferred from the program memory to
the D register. Note that the length parameter Eor the tan vector
instruction 104, or for the polar vector instruction 113 "~lich specifies
the number of accumulation cycles to be used in generating the given vector,
would have been loaded into the L counter on the clock cycle that was used
to fetch the respective instruction.
~fter the first clock cycle of the instruction execution sequence,
the incremental values that are to be added to the two accumulators are
generated. The correct incremental value to be added to the X accumulator
is gated through the X multiplexer 54 to the X accumulator input 35.
Similarly, the correct incremental value to be added to the Y accu~ulator is
gated through the Y multiplexer 50 to the Y accumulator input 15. Because
of the time required for these incremental values to be generated and to
become stable at the respective accumulator inputs, the first accumulation
clock cycle will occur at the third clock cycle of the vector instruction
execution~ For a single step vector, which is detenmined by the value in
the L counter 53, this ~hird clock cycle would also be the last clock cycle
of the instruction execution, and would therefore be an instruction fetch
cycle. For vectors with multiple steps, the accumulation clock cycles are
repeated, with the L counter decremented at each said clock cyclè, until the
value in the L counter indicates the occurrence of the last accumulation
clock cycle, which is also an instruction fetch cycle~
-13-
1 For the tan vector instruction, the incremental addend value to at
least one of the accumulators will be either +l or -l.
The octant code 107 for the vector, which is contained in the D register 59
and which is an input 84 to the control logic 51, detenmines whether the X
multiplexer 54 or the Y multiplexer 50, shall gate the fixed value of either
+l or -1 to its respective output. The octant code also detenmines which of
these two values i5 to be gatedD The other of these two multiplexers will
gate the output 92 from the addend logic 58. The slope value 108 consists
of only the ~ractional portion o~ the two's complement incremental value
that is the correct input to the appropriate accumulator. The integer bits
for this input are appended to the fractional bits by the addend logic 58,
and they are a function of the octant code. For most cases, the inteyer
bits will be all ones or all zeroes, according to the sign of the
incremental value as is determined by the octant code. However, the value
of +l or -l is required for v æ tors that are oriented at an angle of exactly
45 from either the X or the Y axis. Note that the octants are defined so
that a given oc~ant includes only one of the three values: 0; ~l; or -1, as
possible slope values. For any of these values, and for only these values,
all of the bits of th~ fractional 510pe 108 are equal to zero. ~he~efore~
th~ cor~ect integer bits can be appended to the fractional slope value by
the addend logic a~ a ~unction of the octant code and a function of whether
or not the fractional slope bits are all equal to zero.
~he polar vector instruction i~ designed to allow the simple
rotation of symbology by automatically rotating ~11 polar vectors by a
rotation angle 112 that is held in the bias register 57 as a result of the
execution of a load bias instruction. The angle 117 of a polar vector is
loaded into the ~ register 59 o~ the first clock cycle of the instruction
9~
-14-
1 execution, and it is then added to the output 90 of the bias register 57 in
the adder 56. The output 91 of the adder 56, which is the correct angle for
the rotated vector, is the input to a SIN/COS generator 55. The SIN/COS
generator can ~e implemented, for example, with read-only-memories, using
the table-look-up te~chnique. For the polar vector instruction, the COS
output 94 of the SIN/COS generator is used for the addend input to the X
accumulator and it i~ therefore gated through the X multiplexer 54O The SIN
output 93 is used for the addend to the Y accumulator, and it is gated
through the Y multiplexer 50. The first accumulation clock cycle for the
polar ve!ctor instruction oc~urs on the third clock cycle of the instruction
execution, as was the case for the Tan inctruction. The last accumulation
clock cycle, as detenmined by the value of the L counter, is also an
instruction fetch cycleO
By loading the fractional value of ~Olllo~l into the fractional
portions of the æcumulator register~ 11, 31 on the load XY instruction, the
invention improves the accuracy of vectors generated with both the tan
vector instruction and the polar vector instruction. The accuracy of
vectors generated with the tan vector instruction are further i~proved by
lo~ding the value of .Oll...l into the fractional portions of the
accum~lator registPrs on the last accunulation clock cycle of each vector,
which also loads the integer portion of the register with the integer
por~ion of the output fron the accumulator adder 14, 34, Because the numbe~
of ~ractional accumulator bits is made large enough relative to the maxlmum
number of accumulation clock cycles for any vector, the effect of the above
technique is to el~minate all errors at the er.d points of vectors that are
drawn with the tan vector instruction. Also, when the fractional resolutior
;s sufficient, errors at any point along a vector are eliminatedO The
39~
-15-
1 invention also forces, or favors, the generation of symmetrical s~mbologyusing concatenated tan vector instructions, by selectively enabling the
carry inputs 16, 36 to the accumulator adders 14, 3~ on only the first
accumulation clock cycle o~ some vectors, whereby said enabling is, for each
accumulator, a ~unction of the octant 107 of the vector.
The program memory 64 of the vector processor is designed to be
time-shared by the vector processor and by a general purpose processor (not
shown). me memory address 83 from general purpose processor can be gated
through the multiplexer 63 to the address input 82 oE the program memory.
Data 80 from the general processor can be written to the program memory so
that the general processor can store a progrlm in the memory for subsequent
execution by the vector processor.
It should be appreciated that various techniques could be used to
improve the per~ormance of the vector processor shown in Figure 1. For
example, two independent program memories might be used so that memory
access conflicts between the vector processor and the general processor
coul~ be eliminatedO Also, the vector execution hardware (i.e., the
accumula~ors, L counter, and required control logic) might be designed
independently from the instruction fetch and format hardware. With bu fer
regi~ters9 or first-in-~irst-out memory, bet~een the hardware of these two
function~, ~he vector execution operation could occur simultaneously with
the f~tching and formatting of new instructions, thereby improving over-all
throughput. m e instruction set of the vector processor, Figu~e lA, might
also be expanded. For example, it could include a SIN/COS type of vector
instructionO General purpose instruction types (e.g., Add, Subtract, Load,
Store) could also be included in the instruc~ion set.
-16-
1 As discussed above, only the integer portions of the X and Y
accumulators are used as outputs. For the application of a raster CRT
display system, the X and Y outputs are utilized to address a two~
dimensional display-image memory. m e vector generator stores a complete
image in the memory by writing the appropriate sequence of vectors. The
memory is then read out in synchronization with the display raster scan in
order to provide the video information to refresh the display. In real-time
applications, two image memories may be utilized so that the vector
generator can update the display lmage in one manory while the second memory
} is utilized to provide the display video information. ~he functions of the
memories are interchanged when the vector generator completes an updated
version of the display image. Eor many other applications, such as for a
caligraphic CRT display or a numerically controlled machine, analoq X and Y
signals are required. In these applications, the integer portions of the X
and Y accumulators are applied as inputs to digital-to-analog converters.
A nominal magnitude of one integer unit is often used for the
incremental step size on each of the N clock cycles utilized to generate a
vector. This requires a minimum range from -l to +1, inclusive, for the
DX/N a~d DY/N input3 to the accumulators of Figure 1. A general purpose
design~ however, may reguire a significantly larg~r range for thesP inputs.
For example, one design may be utilized in several applications that have
different resolution requirements. A low resolution application does not
require the ent~re integer portions of the X and Y accu~ulator~ as outputs,
and may utilize only the more significant bits of these integers. The less
significant integer bits (i.e., those not being used for the X and Y
outputs) are loaded with the value zero when the X and Y ace~mulators are
initi~lizeda The DX/N and DY/N inputs would then be increased in magnitude
2a~ 92
1 for such low-resolution applications in order to achieve an adequate
incremental step size at each clock cycle of a vector. High-resolution
applications, in particular those utiliæing analog X and Y output signals,
can also make use of a larger than normal step size in order to increase the
speed at which vectors are drawn.
For the tangent vector algorithm and the sine/cosine vector
algorithm, two different approaches are normally utilized for determining
the n~mber of clock cycles, N, to be used in generating a vector. For the
tangent algorithm, the value of N is normally provided by the absolute
magnitude of DX or the absolute magnitude of DY, whichever is the larger.
For example, if ¦DX¦ > ¦DY¦, then N is given by: N = ¦DX¦; and the
incremental values added to the X and Y accumulators are, respectively,
DX/IDXl (i.e~, either +l or -1) and DY/IDXl. m e value added to the Y
accumulator in this case is equal in magnitude to the tangent of the acute
angle defined by the intersection of the desired vector with the X axis,
hence the designation of tangent algorithm. Scaled versions of the tangent
algorithm, for example, where N is given by twice the larger of IDXI or IDY
or by approximately 1/2 the larger of IDXI or IDYI, will not be described.
It is appreciated, howaver, that the invention is applicable to such
variations of the tangent vector algorithm.
For the unscal~d tangent algorithm, at least one of the
accumulators i8 advanc~d by exactly one integer unit on each clock cycle of
a vector. For a 45 vector, both accumulators are advanced by one integer
unit on each clock cycle. With the tangent algorithm, the magnitude of the
incremental step size at each clock ~ycle of a vector is a function of the
vector angle. The incremental step size varies from a magnitude of 1, for a
horizontal or vertical vectorr to a magnitude of the square root of 2, for a
45 vector. The magnit~de of the velocity of the generated vector varies
with vector angle in the same manner as does the step size.
-18-
1 The tangent algorithm is inherently more accurate than the
sine/cosine algorithm, and it generally results in more aesthetically
pleasing vectors. Howevert because of the variation in step size that
occurs with the tangent algorithm, the sine/cosine algorithm is more
appropriate for some applications. For example, in some display
applications, dotted or dashed vectors are generated by modulating the video
signal on and off with a pattern that is controlled by the acc~mulator clock
signal. With the tangent algorithm, the distance over which the dot/dash
pattern is repeated, is a function of vector angle. This is due to the
variation in step si2e with vector angle. mis problem does not occur with
the sine/cosine algorithm, since it has a relatively constant step size.
For the unscaled sine/cosine aigorithm, the number of clock cycles
used in generating a vector is nominally given by: [DX2 + DY2]1/2. This
results in a step size of one integer unit regardless of the vector angle.
It is appreciated, however, that the num~er of clock cycles must be an
integer, and the value N is actually derived by rounding off the ~alue of
[DX2 + DY2]1/2 to the nearest integer~
The present invention improves the accuracy of vectors generated
with either the tangent or the sine/cosine algorithms. However, when used
with the inherently more accurate tangent algorithm~ the invention can
generate vec~ors of the highest possible mathema~ical accuracy. Although
the invention is primarily described herein as applied to the tangent
algorithm, it is also applicable to the sine/cosine algorithm.
Prior t~ discussing further details of the invention, a commonly
employed variation in the hardware implementation of the tangent algorithm
will now be described. Instead of utilizing two accumula~ors, as
illu~trated in Figure 1, the tangent vector algorithm may be implemented
--19--
1 with two up/down counters (i.e., one for the X output and one for the Y
output) and on~ accumulator that does not include an integer po~tion, but
only the circuitry required to detect overflow in the adder from the
fractional acc~mulator into the lnteger portion. As described above with
respect to the tangent algorithm; at least one of the outputs (i.e., either
X or Y) advances by exactly one integer unit on each clock cycle of the
generat~d vector. This can be implemented by advancing the corresponding X
or Y counter of thls alternative implementation, either up or down, on each
clock cycle. The other counter is advanced only on clock cycles in which
the fractional accumulator overflow~ into the integer units, which would be
on every cycle in the case of a 45 vector. The values of the X an~ Y
outputs with this alternate implementation are identical to those of ~he
embodiment of Figure 1. In applying the invention to this alternative
implementation, the fractional accumulator is ~reated, for any given vector,
as the accumulator of Figure 1 that corresponds to the axis of the smallest
vector component.
In order to contrast vector generation in accordance with the
prior art and vector generation in accordance with the present invention,
the following Table 1 illustrates the generation of a vector in accordance
with the tangent al~orithm with DX - +3 and DY = -8,
. - _ _ lA lB
CLOCK INITIAL VALUE - 0 INITIAL V~LUE = 0.5
CYCLE ~ ... _ " .... _r_
INITIAL 0 _ 0 ~ 0.5 0.5
1 0-375 -l 0.875 ~ b~
--~r~~~~~~~~~ 0.75 -~- -2 ~_ 1.25 -1.5
3 1.125 _ 3 _ _ _ i.625 -2.5
-5 ------ -------1-.875 ~4 ~ 2 375 -4 5
6 ---- 2.25 -6 ~ ~.75 -5.5
7 _ 2.625 -7 ------3.125 -6.5
8 3-0 -8 3.5 -7.5
-20-
1 Table l delineates the initial values in the X and Y accumulators
of Figure 1 and the values after each of the eight clock cycles utilized to
generate the vector. Table lA provides the X and Y values for the prior art
generation of the vector and Table lB provides the X and Y values for
generating the vector with the fractional portions of the X and Y
accu~ulators initialized to the value of l/2 in accordance with the
invention. Figure 2A illustrates the pixels ill~minated for generating the
vector in accordance with the prior art as delineated in Table lA. Figure
2B illustrates the vector generatèd in accordance with the invention as
delineated in Table lB. It is appreciated that only the integer portions of
the values delineated in Table l are utilized for the outputs that determine
the illuminated pixels of the displayed vectors illustrated in Figures 2A
and 2B. Although the accumulator values in Table 1 are, far convenience,
provaded in decimal,the vectors displayed in Figures 2A and 2B are
predicated on a two's complement binary hardware implementation.
The present invention modifies the prior art vector generator to
improve the accuracy of the resulting symkology. m e first modification i~
to initialize the fractional portion of the accumulators to a value of l/2t
or to a value of l/2 les~ the value of the LS~ of the accumulator (i,e.,
where l/2 ~ ol0~ 0 and 1/2 ~l LSB = .011.o.1, in binary two's
complement)~ For ~he exemplified vector, this modification results in the
accumulator value~ delineated in Table lB above and ~he corresponding vector
illustrat~d in Figure ~B.
The accuracy of the vector of Figure ZB, initialized to the value
2S of 1/2 in accordance with the invention, and the vector of Figure 2A,
initialized to zero in accordance with the prior art, may be compared by
lines 71 and 70 drawn between the respective vector e~d points. ~he lines
%
-21-
1 70 and 71 define the location of the actual vector the hardware is
attempting to generate. The line 71, compared to the line 70, illustrates
that the present invention has generated a more accurate vector than the
prior art. In the absence of truncation errors, the present invention
illuminates only pixels that are within the distance of l/2 the pixel-to-
pixel spacing fram the actual vector. This is the closest representation of
the actual vector that can be achieved with a given display resolution, and
it defines a "mathematically perfect vector". The prior art vector
generator/ which clears the Eractional portions of the accumulators when the
integer portions are loaded, càn illuminate pixels that approach a distance
of a full pixel-to-pixel spacing from the actual vector.
Since the correct value of DX/N or DY/N can ~e an irrational
number, the actual value that is utilized by the vector generator can
incorporate a truncation error. These errors can build up over a number of
clock cycles until the integer value o~ an accumulator is in error. This
problem is most likely to occur when consecutive vectors, including blank
vectors, are used to generate extensive complex sym~ology. The result is a
degradation in the appearance of the symbology.
A further modification to the prior art vector generator can
ho~ever~ prevent this problem. If the accumulator fractions are initialized
to eithe~ l/2 or to 1/2 less 1 LSB, if the number of fractional bits in the
accumulator is K; if the incremental value add æ to the accumulator is
rounded to the nearest LSB (i.e., to the Kth fractional bit); and if the
number of clock cycles used to generate the vector is lLmited to a maximum
value of 2K; then the error at the vector end point will be restricted to
the fractional bits of the accumulator. Therefore, by re-initializing the
fractional bits of the accumulators on the last clock cycle of every
generated vector (i.e~ by loading them with l/2 or l/2 less 1 LSB~, the
build-up of truncation errors over consecutive vectors is elimina~ed~
-22-
1 The previously described modifications to the prior art vector
generator ~uarantee that, for either the tangent or sine/cosine algorithm,
every vector will tenminate precisely at its correct end point.
Mathematically perfect vectors are, however, not necessarily achieved.
Errors can still occur in the integer portions of the accumulators at
intenmediate points along a generated vector. For the tangent algorithm,
these errors can also be eliminated if the fractional resolution of the
accumulators is increased relative to the maximum vector length (i.e., the
vector length as determined by the maxim~m number of clock cycles). For
example, if the acc~mulators have K fractional bits, then mathematically
perfect vectors are generated for all vectors with the number of clock
cycles less than or equal to 2K/2.
Even with mathematically perfect vectors, a problem arises in the
qeneration of symmetrical symbology. When a yiven vector lies exactly
between two pixels, it is mathematically arbitrary which pixel is
illuminated. When, however, vectors are concatenated to form symbols, this
choice is no longer arbitrary if symmetrical symbology is to be generated.
An example of this problem is illustrated by the letter "V" of Figure 3A.
This symbol, which is clearly unsymmetrical, was generated with a vector
having DX = +3 and DY = -8 (as in the previous example), followed by a
vector wi~h DX - t3 and DY = +8. Iable lB delineates the accumulator values
after each clock cycle of the first vector. After clock cycle 4, the
integer values of X and Y are equal to +2 and -4, respectively (i.e , as the
accumulator valuPs are expressed in the binary 2's complement number
system)o At Y = -4, the actual vector is at X = 1.5. Therefore, it is
mathematically arbitrary whether the pixel at X = 1, Y = -4 or the pixel at
X = 2, Y = -4 is illuminated. Similarly, for the second vector it is
arbitrary whether the pixel at X = 4, Y = -g or the pixel at X = 5,
Y = -4 is illuminated.
-23-
1 Figure 3A illustrates the symbol generated with the accumulator
fractions initialized to 1/2. If the accumulator fractions are initialized
to 1/2 less 1 LSB, then the opposite choices are e~fected with xespect to
which of the mathematically arbitrary pixels are illuminated. The symbol
illustrated in Figure 3B is thus generated. If one of the vectors is
initialized to 1/2, and the other initialized to 1/2 less 1 LSB, the
resulting symbol will be symmetrical as illustrated in Figure 3C. ~he
mathematically arbitrary pixel in the first vect~r is denot~d by reference
numerals 75 and 75' and the mathematically arbitrary pixel of the second
vector is denoted by reference numerals 76 and 76'. Thus, a further
advantage of the present invention is illustrated by the co~parison of the
three examples of the generation of the letter "V" depicted in Figures 3A,
3B and 3C.
The present invention generates symmetrical symbology by
initializing th~ accumulator fractions to the value of 1/2 less 1 LSB, a~d
then enabling the acc~mulator carry input (lines 16~ 36 of Figure 1) on the
first clock cycle of some vectors. Enabling the carry input on the first
clock cycle is equivalent to initializing the accunulator fraction to 1/2,
lnstead of to 1/2 les~ 1 LSB, and not enabling the carry inputO The
decision on whether to enable the carry input on the first clock cycle of a
vector i5 predicated on the octant in which-the vector to be generated
resid~s~
Figure 4 illustrates the octant deinitions utilized in generating
symmetrical symbology. The following Table ~ provides two algorithms for
the generation of symmetrical symbology utilizing concatenated vectors with
the tangent vector generation algorithm~
9~
--24--
~sLE 2
- CARRY IN~ ON 1S-L C~CK
A~T~ I AXI S _ CCTANT #
. X _ 11 12 _ ~ ~ __
~1 ' O * * 1- ~ * ~ O -
._ , X * O O' ~ ~ 1 1- -*_
#2 ~ Y _ 1 ~ * __ * * _
_ .
* = DON'T C~RE
1 The algorithms of Table 2 are implemented by a portion of the control logic
51 of the vector processor of Figure 1. The X and Y carry input signals are
applied to the lines 36 and 16, re~pectively.
In the embodiments of the invention heretofore described, the
values DX/N and DY/N are provided by rounding to the LSB bit posltion of the
accumulators~ The aspects of the invention regarding symmetrical symbology,
as discussed, did not consider the effect of truncation errors with respect
to the choice between two mathematically arbitrary pixels~ The possibility
of truncation errors requires that, to guarantee the generation of
symmetrical symbology using concatenated vectors, a different truncation
algorithn must be utilized in providing the DX/N and DY/N signals. For K
fractional bits, symmetrical symbology, as well as mathematically perfect
vectors, can be generated with vectors having up to 2K/? clock cycles.
However, when the number of clock cycles is an even integer, the DX/N or
DY/N value mu~t be truncated for all vectors in octants with the carry input
to the corresponding accumulator disabled on the first clock cycle of the
vector. Also, when the number of clock cycles is an even integer, the D~/N
or DY/N value must be round~d up, when not represented exactly in ~
fractional bits,for all vectors in octants with the carry input to the
corresponding acc~mulator enabled on the first clock cycle of the vector.
For vectors with an odd number of clock cycles, the DXjN and DY/N ~alues are
always rounded to the nearest LSB~
2~
-25-
1 - Alternatively, for K fractional bits, symmetrical symbology is
generated if the maximum n~mber of clock cycles in a vector is limited to
2(K-1)/2, and if the DX/N and DY/N values for all vectors (i.e., ~egardless
of whether the number of clock cycles is an even or odd integer) are
detenmined in the same manner as describe~ above for the vectors having an
even number of clock cycles~
It is appreciated that the software system that establishes the
value for the slope 108 of the tan vector instruction word of Figure lA
accommodate~ the above-described limitation~ so that symmetrical symbology
is generated in the presence of truncation errors.
Referring again to Figures 3A-3C, the advantage of symmetrical
symbology generated in accordance with the present invention is exemplified
by a comparison of Figure 3C, which was generated by algorithm number 1 of
Table 2 above, with Figures 3A and 3B which are non-symmetrical. Referring
to Figures 5A and 5B, the advantages of the symmetrical symbology aspect of
the presen~ invention are further exemplified. Figure 5A illustrates the
generation of an octagon in a counterclockwise directlon with
mathematically perfect concatenated vectors. The accumulator fractions are
initialized to one-half in accordance with the inventionJ The octagon of
Figuxe 5B i~ generated in the counterclockwise direction utilizing
concatenatad vectors with algorithm ~1 o Table 2. The advantage3 of the
present invention regarding the generation of symmetrical sy~bology are
appreciated by comparin~ the appearance of the octagon of Figure 5B with
that of Figure SA.
As previously described, the present invention can utili~e the
sine/cosine vector generation algorithm to ellminate error accumulation when
generating concatenated vectors. ~like the tangent algorithm, however, the
sine/cosine algorithm cannot generate mathematically
2~ 2
-Z6-
1 perfect vectorsO NevertheleSS, the sine~cosine algorithm can be utilized to
g2nera-te sym~etrical symbology with concatenated vectors. The following
Table 3 defines four sym~etry algorithms for sine/cosine vector generation.
~BLE 3
CARRY INP~ CTANT # ~ ~- -
1 =~
1 - ~4 ~ ~
The octant de~inition with respect to Table 3 is illustrated in Figure 4.
It is noted that the algorithms utilized to generate symmetrical symbology
using the sine/cosine technique are similar to those for the tangent
algorithm, except that the accumulator carry inputs on the first clock cycle
are never "Don't Cares", as is the situation in half of the table entries oE
Table 2 above.
Referring to Figure 6, an annotated octagon is illustrated for use
in the develop~ent of the symmetry algorithns. The octagon is drawn with
concatenated vectors in the counterclockwise direction and the numbers
inside th~ octagon denote the octant of each such vector. The notations
outside the ~ctagon provide the ~ and Y directions from each vector toward
the outslde o the octagonO Specifically, the notations outside the octagon
compris~ two notations associated with each vector, one of which is either
X~ or X-, and the other of which is either Y+ or Y-. For each vector, the
notations indicate which X direction (i.e., X~ or X-) and ~hich Y direction,
is on the side of the vector that lies outside of the octagon. Enabling the
carry input on the first clock cycle will bias an accumulator, and the
associated component of the
-27-
1 generated vector, toward the positive direction (i.e., toward the X~ or Y-
~direction). Similarly, by disabling the carry input on the first clock
cycle, the accumulator is biased toward the negative direction (i.e., toward
X- or Y-). S~nnetrical symbology is generated if the carry inputs to the
S accumulators are qelected in,accordance with the bias that i~ 3hown in
Figure 6 to always select betw~en mathematically arbitary pixels such that
the pixel towards the outside of the octagon will be illuminated. Assuming
that the octagon is drawn in the counterclockwise direction, this selection
results in algorithm #l of Table 2, for vectors generated with the tangent
algorithm, and algorithm #1 of Table 3, for vectors generated with the
sine/cosine algorithm. Symmetry will also result if the carry inputs are
selected so that the pixels toward the inside of the octagon are
illuminated. This results in algorlthm #2 in both Tables 2 and 3. It is
noted that algorith~ #l illuminates the pixels that are toward the outside
of the octagon only when the octagon is drawn in the counterclockwise
direction and illurninates the pixels that are toward the inside when the
octagon is drasYn in the clockwise direction. Similarly, algorithm #2
illuninates the inside pixels when drawing the octagon in the
counterclockwise direction, and the outside pixels when drawing in the
clockwise direction.
For the sine/cosine technique, two additional algorithms ar~
provided for the generation of symmetrical symbology. Algorithm #3 of Table
3 results from the selection of the outside pixels for the axis that
corresponds to the shortest component of each vector, a~d the selection of
~he inside pixels ~or the axis that corresponds to th~ longest component of
each vector, when the octagon is generated in the counterclockwise
direction. Similarly, algorithm #4 results fxom the selection of the inside
pixels for the axis that corresponds to thQ shortest component o each
2~0~9~
-28-
vector, and the selection of the outside pixels for the axis that
corresponds to the longest component of each vetor, when the octagon is
generated in the counterclockwise direction. In the manner described above
with respect to Table 2, Table 3 is implemented by a portion of the control
logic 51.
~ s described above, the present invention eliminates truncation
errors at the vector end point. The following is an error analysis for the
correct vector end point and provides a derivation of the maximum error at a
vector end point.
Assume a vector is drawn from point Xl, Yl, to X2, Y2. m en, DX
X2 - Xl and DY = Y2 - Yl, where DX and DY are integers. If a total of N
clock cycles are used to generate the vector, the incremental values that
should be added to the X and Y accumulators at each clock cycle are given by
DX~N and DY/N, respectively. Consider only the error in the Y accumulator.
The analysis is also valid for the X accumulator because of symmetry.
Ihe actual value added to the Y accumulator on every clock cycle
is given by DY/N + e, where the error term, e, is given by:
1) e = Actual Value - Correct Value = [DY/N + e] - DY/N. m e error term
results from the necessity of representing DY/N with a inite number of
fractional bits. If DY/N is an irrational number, then its exact
representation in 2's ccmplement binary requires an infinite number of
fractional bits~ If the accumulator has K fractional bits, the weight of
the Least Significant Bit (LSB~ of the accumulator is equal to 2-K. In the
exact 2's complement representation of DY/N, all the bit positions to the
right of the KTH fractional bit contribu~e scme value, E, to the total
amount o~ DY/N (where E is greater than, or equal to, zero; and is less than
2-K). I~ the value added to the accumulator is derived by dropping (i.e.,
-29-
1 trunc~ting) the value E from the exact representation of DY/N, e will be
given by:
2~ e - -E (for truncation)
If, for the case when E > 1/2 LSB, the value added to the accumulator is
rounded up (i.e , by adding +1 to the LSB and truncating the value E), then
3) e = LSB - E (for rounding up).
The integer portion of the Y acc~mulator is initially loaded with the value
Yl, and the ~ractional portion of the accumulator is inltialized to the
value of 1/2 or to the value 1/2 less 1 LSB. If the initial fractional
value of Y is designated as F, then the value o~ the Y accumulator at ~he
vector end point (i.e., after N clock cycles), is given by:
4) Y = Yl ~ F + [(DY/N) + e]N = Yl + DY ~ F ~ e.N,
where Yl an~ DY are integers and F is the initial value of the fraction. If
no error is allowed in the integer value of the Y ac~umulator, then:
5) 0 < F ~ e.N C 1
Using worst case values of F (i.e, 1/2 for the positive limit and 1/2 less 1
LSB for the n~gative limit), and solving for e, giveso
6) (1/2N) ~ (LSB/N) ~ e ~ 1/2N
m e number of fractional bits in the accumulators must be large
~0 eno~gh ~o that the error tenn in the incremental value added to the
accumulator is within th~ range defined by ineq~ality 6); where N is the
number o clock cycles used to generate a vector, and LSB ls the value of
the lea~t signi~iant bit of the accu~ulator~ This will ensure that the
inte~er valu~ of the accumulator will not be in error at the vector end
point. The ~ractional poxtions of the accumulators can then be initalized
(iOe., loaded with 1/2 or with 1/~ - 1 LSB) on the last clock cycle of every
vector. m is will prevent error build up on consecutive vectors.
2~
-30-
1 If K bits are available to de~ine the value N, then the maximum
number of clock cycles is equal to 2K. (Note that zero length vectors can t
be disallowed. The value of N can then be defined as one greater than the
number defined within the K bits). It will now be shown that with N < 2K, a
total of K fractional bits are sufficient to meet the requirements of 6).
The worst case value of N, relative to inequality 6), is given by
2K-1 (note that e will be 0 for N = 2K). Substituting into 6), with LSB =
2-K, gives:
7) - 1 + 2-K < e <
2~1 -2 ~C~r- ~ 2~ -2
The actual va}ue ~sed for DY/N can include an error value, e, due to the
limitation of K fractional bits. If any number between -l and +l ~ere
possible for the corxect value of DY/N, then by rounding to the closest LSB
(i.e., nearest 2-K), the actual range of e would be given by:
8) - l < e <
2~ ~ 2k~l
If the actual range of e (given by inequality 8) lies within the required
range (given by inequality 7), then K fractional bits would indeed be
suf~icient ~o prevent integer errors at the end point. This is clearly the
ca~e for the positive limits of the inequalities. It is not, however, the
case for the negative limits.
If ineqyalit~ 6) is solved for N = 2K-2, ~hen the result is given by:
9) - l - + 2-R < e ~ 1
2~ 4 2~ -2 ~l _4
It can bs demonstrated that the negative limit of 8) is e~ual to
the negative li~it requirement of 9~. Therefore, K fractional bits are
sufficient to p-event integer errors with vectors having 2K -2, or fewer,
clock cycles~
2~ 39Z
-31-
1 Inequality 8) was derived under the assumption that DY/N could be any value
between -1 and +1. Because this is not precisely true, the negative limit
of inequality 8) is less than the value that can actually occur. The limit
assumed a truncated value, E, that is arbitrarily close to tbut still less
than) the value of 1/2 LSB (where 1/2 LSB = 2 -K-l). A more exact value for
the negative limit of e will noW be detenmined.
If the correct value to be added to the Y accumulator,
DY/N, is divided by the weight of the LSB (i.e.j by 2 K), this has the
effect oE moving the binary point to the right by K bit positions.
Therefore, the fractional poLtion of the result o~ this division will
consist of all the bits to be truncated in deriving the value that will be
used to approximate DY/N (i.e., in deriv-ng the value (DY/N) ~ e). If the
worst case ractional result oE this division ~i.e., the fraction that is
closest to, but still less than, 1/2) is multipli~d by the weight of the
LSB, this will give the magnitude of the worst case negative limit for e.
The previously prescribed division can be expressed as:
10) (DY) . 1 = Q + R
(N) LSB N
where Q is an integer and R is a positive integer that is less than N. m e
largest value of R/N that is less than 1/2 occurs when N is the largest
possible odd integer. It is given by:
llj Eraction = N/2 - 1/2 = N-l
N 2N
The magnitude of the negative error limit can now be determined by
multiplying this ~raction by the LSB (i~e., where LSB = 2-K and N = 2K-l).
The result ;s given by:
12) Neg. limit = - 2K -1-1 (2-K) = - 1 ~ 2-K~l
2(2~ K+l -2 2K~1 -2
Substituting this value for the negative limit of inequality 8) gives:
92
-32-
13) - 1 ~ 2~K+l < e ~ 1
2Ktl -2 2~+1 -2 2K~l
Inequality 13) gives the actual limits in the error term of the value that
is added ~o the accumulator ~i.e, for K fractional bits and 2K maximu~ c}ock
cycles). ~hese limits lie within the required limits that are given by
inequality 7). ~In fact, the negative limits o inequalities 7) and 13) are
equal). Therefore, no error can occur in the integer bits of the
accumulators at the vector end point when:
1) The accumulator fractions are initiali~ed ta either 1/2 or 1/2 - 1 LSB.
2) K fractional bits are available for the accumulators; 3) the value added
to an accumulator is rounded to the nearest LSB (i.e., to the KT~I fractional
bit); and 4) a maximum of 2K clock cycles is used to genexate the vector~
Increasing the fractional resolution of the accumulators beyond
that required for the elimination of vector end-point errors, can, with the
tangent algorithm, result in the generation of mathematically perfect
v~ctors. The following error analysis derives the resolution requir~ments
for mathem~tically perfect vectors. The requirements for combining
symmetrical sym~ology with mathe~atically perfect vectors are also derivedO
Assume a vector is drawn from point Xl, Yl to point X21 Yz.
Let X2 - Xl ~ N, and Y2 - Yl = M. Both N and M are integers. Consider the
~angent algorithm with ¦N¦ clock cycles (iOe., ¦N¦ > ¦M¦.
ChS~ initial value o~ accumulator fraction = 1/2. The "correct" value
for the Y aocumulator a~ter clock cycle "i" (i.e.~ with no truncation
errors) i~ given by:
14) YC(i~ = Yl ~ 1 + M ~ i
2 ~ T - I
~ut the approximate value that is added to the Y accumulator is given by-
~M/IN~) ~ e, where the error term, e; results from truncation (and possibly
-3~-
1 from roundiny). Therefore, the "actual" value of Y after clock cycle i is:
15j YA(i) = Yl + 1 + M . i + e . i
2 IN
Note that e is given by:
16) e = Actual slope value - Correct slope value =
[(M/¦N¦) + e] - M/¦N¦
Therefore, if the value E (as defined above) is dropped (or truncated) from
the correct value to form the actual value used, then:
17) e = -E (for truncation)
If the actual value is derived by rounding up (i.e., by adding +l to the LSB
and then truncating the value E) (i .e., when E > 1/2 LSB), then:
18) e = LSB - E ~for rounding up)
The term, (M/INl).i, in equations 14) and 15) can be expressed as:
19) M . i = Q + R
~ ¦NI
where Q and R are both integers , and IR/NI < 1.
Substituting into equations 14) and 15) gives:
20) YC(i) = Yl + 1 + Q + R
2 ¦N¦
21) YA(i) = Yl ~ 1 + Q R + e.i
2 INI
The highest susceptibility to an error in the integer value of the Y
accumulator occur~ when R/¦N¦ i~ very close to (but not equal to) +1/2 or
-1/2. (When R/IN¦ = + 1/2, either of two integers is a '~athematically"
equivalent approximation to the Y value. Therefore, this case is relevant
to generating symmetrical symbols (e.g., N - 6, M - 1 or 5), but is not a
worst case for generating '~athematically" correct vectors). m~ R/¦N¦ term
will be closest to +1/2 when N is an odd integer, and when N is large. For
these cases,
22) R = + N +
9Z
-34-
1 where N is an odd integer.
Substituting into 20) and 21) gives:
23) YC(i) = Yl + 1 + Q + 1 +
2 2 ~N
24) YA(i) = Yl ~ 1 + Q -~ 1 + 1 + ei
2 2 2N
where the sign of the tenm +1/2 will be the same as the sign of the value
Q, and N is a laxge odd integer.
If YA(i) is to have the same integer value as YC(i) then, from
equations 23) and 24),
25) -I ~ < ei < I ~ , and
lQ ~6) -I 1 1 < e <
I ~ ¦ 2Ni ¦
m e most stringent requirement on e occurs when N is the largest magnitude
odd integer, and when i is given by:
27) i = ¦N¦ -1
(Note that when i = INI, the vector end point is attained and the error
15 ~ sensitivity is very low).
Now, if L bits are available to specify the vector length (i.e., ~he nu~ber
of clock cycles), and if zero length vectors are not allow~dJ then the
naxi~um length is given by 2L, and the maximum odd value is:
28~ N = 2L -1
Substituting 27) and 28) into eg~ation 26) gives:
29) ~ h~1 -2~ -2L~1 +4 < e < 22Ltl -2~ 2L~i *4
It would therefore be su~ficient (but not quite necessary) to require
that:
30) - 1 < e <
-~ZG~ L~-r
in order to prevent errors in the Y inte~er for Ca~e ~1 with the fraction
~0~ 2
-35-
1 initially equal to 1/2. This requirement, which is more stringent than 29),
is the result of rounding the value of MVN to the nearest value that can be
represented with 2L fractional bltso Therefore, '~athematically" perfect
vectors will result with 2L fractional bits, rounded ~lope value~, and
fractions initialized to 1/2. It can be demonstrated that 2L-l fractional
bits would be insufficient for this case (e.g., with N = 55, i = 54, M =
27).
CASE t2- Initial value of accumulator is equal to 1/2 less the LSB of the
accumulator fraction.
This case is of interest primarily for the special case of forcing
symmetrical symbology for concatenated vectors. For vectors that are
exactly between two pixels, the system must control which o~ the pixels is
illuminated if symmetrical symbols are to result.
AS a first step, it will be determined if "mathematically" perfect
vectors will result for the same criteria as for Case #l (i.e., with L-bits
or vector length, 2L fractional accumulator bits, and rounded values of
MVN). The "arbitrary" case of a vector being exaetly between two pixels
will not be considered.
The ~guations for the "Correct" value of Y and the "Actual" value
of Y are given by:
31) YC(i) 3 Yl ~ 1/2 - LS~ + M .i, and
32) YA~i) a Y~ + _ - LSB ~ M ~i + ei, where
33) LSB =
2~L --
Recalling from Case #l ~hat:
19) ~ r . i = Q ~ ~ N r ' gives:
-3~-
1 34) YC(i) = Yl + 1 - LSB + Q + R , and
35) YA(i) = Yl + 1 - LSB + Q + R +ei
The greatest susceptibility to an error in the integer value of Y~(i) occurc
when R/INI is close to (but not equal to) +1/2 or -1/2. (Note that when
R/INI = + 1/2, then the vector will be exactly between two pixels and it is
mathematically arbitrary which pixel is illuminated. This case is not of
immediate interest). l'he R/INI term will be closest to + 1/2 when
22) R = + N + 1 ,
where N is a large odd integer.
Substituting into 34) and 35) gives:
36) YC(i) ' Yl + 1 - LSB + Q + 1 +
37) YA(i) = Yl + 1 - LSB + Q + 1 + 1 ~ ei
2 2 2N
From e~uations 36) and 37)
38) - _ 1 + LSB < ei < 1 + LSB,
2N 2N
if no error is to occur in the integer value of YA.
Solving for e, and substituting 33), 28) and 27) for LSB, N, and i,
respectively, gives:
(2~1~2)(2~_2) 2~G--2L--2) (~L~ 21(2L 2) 22~(2L~2)
The above expression defines the acceptable range of e for the
generation of mathematically perfect vectors. The actual r~nge of e for 2L
~ractional bits with roul~ing of M/N was given by:
30) - 1 ~ e <
L~
Since the acceptable range of e in 39~ has a smaller magnitu~e for the
negative l~mit of the range than for th~ positive limit, it will only be
9;~
-37-
1 necessary to compare the negative limits of 30) and 39). If the magnitude
of the acceptable negative limit of 39) is larger than (or eyual to) the
magnitude of the actual negative limit of 30), then 2L fractional bits are
sufficient for mathematically perfect vectors. mis is shown to be true as
follows
- 1 > ?
~2L+1 -2)(2~-2) 2~L(2L-2) 22L~I
~2L-~1 -2 t2L+1 -2) > ? (2L+1 -2)(2L -2)
(2L~1-2) (2L-2) 2~L~1 - (2 -2) (2 -2j 2
22L+1 -2L+2 +4 >? 22L+1 -2L~2 -2 L~
QED
It has now been demonstrated that '~tathematically" perfect
vectors will result when: the fractional portions of the accumulators are
initialized to either 1/2 or to 1/2 less 1 LSB; the slope value is rounded
to the nearest LSB; and 2L bits are available for the slope and accumulator
fractions (i.e., where L bits define the vector length in terms of the
number of acc~mulator clock cycles). When the desired vec~or lies exactly
between two pixels, it is mathematically arbitrary k~tich pixel is
illuminated. ~owever, if symmetrical symbolo~y is desired when vectors are
concatenated to form symbols, then it i5 no longer arbitrary which of these
mathematically eq~tivalent pixels is illuminated.
If the problem of truncation errors is neglected, then
synntetrical symbols can be generated with chained vectors by using an
algorithm that initializes the accumulator fractions to either 1/2 or to 1/2
less 1 LSB, depending on the direction (i.e~, the octant) of the vector to
be drawn. mis can also be accomplished by always initializing the
fractions to 1/~ less 1 LSB~ and then forcing a carry input to the
z
-38-
1 accumulator/adder on the first clock cycle of vectors that are in selected
octants. men for octants with the carry input enabled (i.e., on the first
clock cycle only), the larger, or more positive, of two mathematically
equivalent integers (pixel locations) will be selected. For octants with
s the carry input disabled, the lesser,or more negativet of two mathematically
equivalent integers is selected. m is approach generates symmetrical
symbology, using chained vectors, when the slope value is exact. When,
however, the slope cannot be represented exactly hy 2L fractional bits, then
a dlE~erent ~pproach to truncation is required (i.e., other than rounding to
~le neares~ LSB).
C~S~ ~3: Symmetrical vectors for octants with carry input enabled.
This case is equivalent to initializing the accunulator fraction
with 1/2 and not enabling the carry input (i.e., as in Case #1). The
e~uations for the correct and the actual values for the Y accumulator were
given by:
20) YC(i) ~ Y~ Q + R
2 fN¦
21) YA(i) = Yl + 1 + Q + R + ei
2 ~
For thP mathematically arbitrary case: R/IN¦ = + 1/2. The carry input was
enabl~d on the first clock cycle in order to force the larger of the
math~matically equiYalent integers for the Y accumulator. Therefore,
considering only the case where R/INl = ~ 1/2, if no error is to be allowed
in the integer value of YA(i), then:
40) O < e . i < 1
Of course, inequality 30) must still be met (iOe., in addition to 40), to
meet the reguircments for mathematically correct vectors. Inequality 40)
requires that, for symmetrical symbology, a simple truncation can no longer
be used on thP slope value of vectors that are in octants that have the
~ z~ g~
-39-
1 carry input enabled on the first clock cycle. If the slope value cannot be
exactly represented, then it must always be rounded up to the next LSB.
Using this method to derive the slope value, and meeting the requirements of
both inequalities 30) and 40), wou}d require a minimum of 2L ~ 1 fractional
bits for the accumulators and the slope value. The slope error would then
be given by:
41) 22L~l -
By separating Case #3 into two distinct "subcases", and by using
different algorithms for detenmining the slope values for these subcases, it
is possible to have mathematically correct vectors ancl syn~etrical sym~ology
with only ~L fractional bits (i.e.~ instead of 2L+l bits).
CAS~ ~3~: Carry input enabled with N an cdd integer
It is noted that a vector can lie exactly between two pixels only
when the term R/N of equations 20) and 21) is given by + l/2. But, since R
and N are integers, this is only possible when N is an even integer.
m ere~ore, when N is odd, the error term can be given by-
30) - 1 < e <
~ 2 Ll-l
as in Case ~1. m is requires 2L bits for the slope value with rounding
to the nearest ~SBo
C~S~ ~33: Carry input enabled with N an even integer
me analysis of Case #l examined the worst case error
susceptibility~ which occurs when N is an odd integer. Therefore, this must
now be considered for the case with N an even integer. Bquations 20) and
21) show that the highest susceptibility to an error in the integer val~e of
YA occurs when R~INl is very close to (but not equal to) ~1/2 or -l/2. (The
case or R~¦N¦ Y ~ l/2 pertains only to symmetrical symbols and results in
the ine~uality o 40)).
5he worst case error susceptibility for the cas~ with N an even
integer occurs when
2~ 2
-40-
l 42) R = + N + l
~ 2 ~
Substituting into equatio s 20) and 21) gives:
) YC(i) = Yl + 1 ~ Q ~
44) YA(i) = Yl + 1 + Q + 1 + 1 + ei
Therefore, to prevent errors in the integer value of Y~(i) requires
that:
45) - 1 < e i <
INI~
The most stringent requirement on e occurs for large values of N and i~
and specifically for
46) N = 2L-2, and
47) i = N - 1,
where L bits are available to specify the vector length. (Recall that N is
an even integer, and note that N = 2L will not result in truncation errors
for the slope value).
Substituting 46) and 47) into 45) and solving e gives:
48) - l _ < e ~ l
-~Zr~ 3-)2L+l + 6 2~ (3)2L+L + 6
It would therefore be sufficient to require that:
49) - l < e <
~ 2~ '~ ' 22~
which could be realized with 2L-l fractional bits with rounding o~ the slope
val~e to the nearest LSB~ If, howeverrsymmetrical symbology is required,
then both 40) and 49) must be met. m is gives:
50) 0 < e <
~ 2 L-~
m is requirement must be met when N is an even integer and the carry is
enabled (on the first clock cycle~, in order to foxce symmetrical
symbology. The requirement is met with 2L fractional bits for the slope.
~hen the slope value is not exact, it must always be rounded up to the next
L5B value~
2~
--41--
- To ccmplete the analy is for sy~ etrical 5yrllbO109y, the case for
octants with the carry input disabled is now examined.
C~SE ~4~ Symmetrical symbology for vectors in octants with the carry input
disabled.
This case is similar.to Case #2 and the equations for Yc and YA were
given by:
34)YC(i) = Yl + 1 - LSs + Q + R
2 ~ - I-NT
35)YA(i) = Yl + 1 - Lss + Q + R -~ ei
2 ¦N¦ -
For the math~matically arbitrary case: R/INI ~ ~ 1/2. If no error is
allowed in the integer value of YA for this case, then:
1 + LSB < e i < 0
(Note that the actual upper limit of "ei < 1 LSB" has been simplified to
"ei<0". These limits are equivalent for all practical purposes due to the
slope resolution of } LSB)
Combining the inequality of 51), required for symmetry, with thP
inequality of 30), required for mathematically correct vectors, gives:
52) - 1 < e C 0
22~
Thi8 range of slope error can be obtained by always truncating, or
dropping, all fractional bit~ of lower significance than the LSB; ar~ by
usin~ a minimum of ~L ~ 1 fractional bits. However, only 2L fractional bits
are required i this case is divided into two subcases, as was Case #3; ar~
different algorithms are used for detenmining the slope valu~s of each
subcase.
casE 4~: Symmetrical symbology; carry input disabled; and N is odd integer.
As noted in Case #3A, the term R/IN¦ cannot equal +1/2 when N is
odd~ Therefore, this case is equivalent to Case ~2. The erro~ lirnits are
given by 30), 2L fractional bits are requir~d, and the slope value must be
rounded to ~he nearest LSB.
--~12--
1 C~SE 4B: Symmetrical symbology, carry input disabled; and N is an even
integer.
AS with Case #3B, the worst case error susceptibility, for N an
even integer, occurs when:
42) R = + N + 1
Substituting 42) into equations 34) and 35) for Yc and YA gives
53) YC(i) ~ Yl + 1 ~ LSB ~ Q ~ 1 +
5g) Y~(i) = Yl + 1 - LSB ~ Q + 1 ~ ei
2 2 N
If no error is allowed in the YA~i) integer, then:
1055) - 1 ~ LSB ~ ei ~ 1 ~ LSB
N N
.~ Substituting for LS~, N, and i in equation 55) (from equations 33), 46)
and 47)) give~:
55~ - 1 + 1 < e < 1 +
(2~-2)(2L-3) 2~L(2~--3) ~ (2L-2)~2L_3) 2~L(2L-3)
It can be shown that more stringent limits are expressed 'oy:
57) - 1 < e <
~2~ _ 2~L
which requires only 2L-l fractional bits with rounding. Combining
41) and 57), ho~ver, gives:
22~- ~
mi5 can b~ met with 2L fractional bits and truncation of the slope value
(i.e., never xounding up).
The following is concluded from the foregoing Error Analysis for
Perfect Vectors and Sy~metrical Symbology.
1~ For "Mathematicall~" Perfect Vectors (Tan~ent Al~orithm)
Fractional portions of accumulators should be initialized to 1/2,
92
-43-
1 or to 1/2 less 1 LSBr when accumulators are loaded (i.e., initial position
instr~ction).
Fractional portions of accumulators should also be loaded with 1/2,
or 1/2 less 1 LSB, on the last clock cycle of every vector. (This
initializes fractions for the execution of consecutive vectors by clearing
any error accumulation).
If the initialization value of 1/2 less 1 LSB is used, then the
adder carry input can be enabled on the first clock cycle of a vector. This
has the same effect as changing the initialization value to 1/2.
The slope value to be added to one of the accumulators should be
rounded off to the nearest LSB.
If K bits are available for the slope and for the accumulator
fractions, then vector lengths of up to 2K/2 clock cycles can be generated
with mathematical perfection. tFor an Accumulator with an ll-bit fraction,
this allows mathematically perfect vectors of ~p to 45 steps).
Vectors that are longer than 2K/~ clock cycles, and therefore might
not achieve mathematical perfection, can also be drawn. However, no vector
longer than 2~ clock cycles should be drawn (where K is the number of
fractional bits in the accumulator and in the rounded slope value). This
restriction is necessary in order to guarantee that no errors will occur in
the integer portions o~ the accumulators at vector end points.
It is noted that "Perfect Vectorsl' illuminate only pixels that lie
within half of the pixel-to-pixel spacing from the actual desired vector.
2. For Sy~metrical_Symbol~Lv
Sy~metrical symbology fr~m chained vectors can be generated by
controlling which of two pixels is illuminated when both are equally distant
from the desired vector. This is achieved by always initializing the
-4~-
1 accunulator fractions to 1/2 less 1 LSB and by enabling the carry input to
an accumulator adder, or to both accumulator adders, on the first clock
cycle of the vectors in certain octants.
Although symmetrical symbology can be achieved with either the
5 SIN/COS or the tan vector ~enerator algorithm, only the tan algorithm also
results in the exclusive generation of mathemtically perfect vectors. The
basic resolution requirement for the accumulator fractions is, in fact, the
same for the generation of symmetrical symbology as for the ~eneration of
mathematically perfect vectors with the tan algorithm. However, a difEerent
algorithm must be used to derive the values that are added to the
accumulators. Two such algorithms are available.
For accumulators having K fractional bits, symmetry can be realized
for all vectors that are generated with a maximum of 2K/2 clock cycles if:
1) the values added to the accumulators are derived by rounding to the Kth
fractional bit for all vectors having an odd number of clock cycles; and 2)
for vectors having an even number of clock cyclPs, the value added to an
accu~ulator having the carry input disabled on all clock cycles is truncated
to K fractional ~its; and 3) also for vectors having an even number of clock
cycles~ th~ value added to an accumulator having the carry input enabled on
only th~ first clock cycle of the vector is rounded up (i.e., by adding 1 to
the Kth fractional bit position) when not represented exactly within the K
ractional bits. No~e that the carry inputs to the accumulators on the
first clock cycl~ of each vector are detenmined by the octant of the
generated vector according to one of the symmetry algorithms of Table 2 or
Tab}e 3~
Again for accumulators having K fractional bits, symmetry can also
be realized for all vectors that are generated with a maximum of 2(K-1)/2
clock cycles if: 1) the value to be added to an accumulator having the
-45-
1 carry input disabled on all clock cycles is truncated to K fractional bits;
and if 2) the value added to an accumulator having the carry input enabled
on only the first clock cycle is rounded up when not represented exactly
within the available K fractional bits.
Neither of these algorithms, for deriving the values to be added to
the accumulators, would normally be used for vectors having more than the
maximum num~er of clock cycles for symmetry. The second algorithm can
result in erxors in the integer bits of the accumulators, at vector end
points, for vectors having more than 2K-l clock cycles.
While the invention has been described in its preferred
embodiments, it is to be understood that the words which have been used are
words of description rather than limitation and that changes may be made
within the purview of the appended claims without departing from the true
scope and spirit of the invention in its broader aspects.
