ROM $ CORDIC based solving linear systems equations

[Vladimir Baykov]

SOLVING LINEAR SYSTEMS EQUATIONS
BASED ON ROM and CORDIC METHOD

Vladimir Baykov

Solving linear system equations with order m in a form
A X = b may be carried out according to digit by digit (CORDIC)
method [2,4,5].
Recurrence equations are depicted below

W(k+1) =2(W(k) - Aq(k)), ( 1 )
X(k+1) =X(k) + q(k)2**(-k)

Initial values : W(0) = -b , X(0) = 0 .

Final values : X(n) = X , W(n) = 0 .

Here the following designations are used :
W(k) - value of residual vector for k-th iteration;
q(k) - ternary vector with digit set {+1,0,-1};
X(k) - value of result vector of unknowns on k-th iteration.

Note that in equation (1) multiplication to 2 may be
substitute for addition of sum in the brackets with itself or
to the shift operation. The multiplication of matrix A to vector
q(k) is not realy multiplication because absolute values of
the vector q(k) are: {+1,0,-1}.

In equation (1) multiplication of vector q(k) to 2**(-k)
is shift operation or better set of constants 2**(-k) may be calculated
beforehand for all values of k (prestored constants).
Consequently the recurrence formulae (1)
solving linear systems equationse are the multiplication and
division free algorithms that is well suitable for VLSI implementation.

In many cases matrix A for set of LSE is constant.
If the values of the products of matrix A to all
the possible values of vector q(k) in (1) to precompute
(remember,that q(k) = {-1,0,1} ) and to store them in a ROM
like in Distributed Arithmetic Principle [1,3] we could simplify
the architecture of special-purpose processor [2,4,5]
and accelerate the LSE solving. In such case we avoid the
execution of m additions per iteration (m - the matrix order)
and thus reduce an amount of hardware and the execution time.
The ternary vector q(k) should be used to address the ROM.
The total memory capacity is m*3**(m) words. In such case the time
of one iteration is the sum of access ROM time and addition time.

In order to reduce the memory capacity we should represent ternary
vector q(k) as a sum of two vectors: the first one - q0(k) is with
only 0's and +1's components and the second one - q1(k) is
with only 0's and -1's components.
As an example let the order of a matrix m=8, then the column vector
q(k) = 0,1,-1,-1,0,1,-1,1 might be represented as a sum of two vectors:
q0(k) = 0,1,0,0,0,1,0,1
and
q1(k) = 0,0,-1,-1, 0,0,-1,0.
So instead of ternary vector q(k) as an address of 3**(m)
words ROM we use vectors q0(k) and q1(k) as the addresses of two
2**(m) words ROMs.
It is possible further reducing by half of memory capacity if to
access data succesively from the only ROM firstly according
to vector q0(k), then according to vector q1(k) with change of out-
put data sign in the last case. It requires only one additional
access time and the time required for execution of one addition
per iteration.

Further, more considerable, reducing of memory capacity is based
on the partitioning of the original ternary vector q(k) into s
subvectors. If s subvectors are used then ROM capacity is reduced
to m*s*3**(m/s) or for binary vector q(k) - to m*s*2**(m/s) words.
But at the same time it requires execution of (s-1) supplementary addi-
tions per iteration.

For instance if m=16, s=4 we have for basic approach memory
capacity equals to 16*2 = 1 048 576 words. In case of using of
4 subvectors memory capacity is 16*4*2 = 1024 words, i.e.
memory capacity is reduced to 1024 times.
The total required time of LSE solving is proportional to sum of
3 additions times and one access ROM time per iteration. Number of
iteration is proportional to number of required bits of result[2,4,5].

Naturaly restriction of that approach is necessity of
the constancy of matrix A and the volume of ROM.

References

1.Burleson W.P.,Sharf L.L. :"A VLSI design methodology for distri-
buted arithmetic". J.VLSI Signal Processing,1991,vol.2,n.4,
pp.235-252.
2.Ercegovac M.D.:"On-line arithmetic :an overview". Proc.SPIE,
1984, vol.495,pp.86-93.
3.Irwin M.J., Owens P.M.:"Digit pipelined arithmetic as illu
strated by the Paste-Up system". Computer, 1987,vol.20,n.4,
pp.61-73.
4.Baykov V.D., Smolov V.B.:"Special-purpose processors:iterative
algorithms and structures". Moscow, Radio & svjaz,1985, 288p.
5.Baykov .D.,Bulgakova S.D.:"Bit-level pipelined algorithms and
structures for signal processing application". Latvian signal
processing intern. conference LSPIC-90, Riga, 24-26 April,
1990,vol.2,pp.208-212.