Summing of field elements. Weighting algorithm.

This algorithm has the same principle as work of pipeline vertical summator. Summing of field elements is performed for source filed INF with capacity INCAP. We need to sum with shift INCAP partial sums ( weights ), calculated as quantities of on-bits in slices of source field. For this purpose auxiliary filed SUM is formed in which first INCAP elements are "weights", shifted by necessary number of bits ( lower bits of weights are placed along main diagonal of field ), other elements are zeroes. This way in SUM field all bits below main diagonal are zeroes and bits above diagonal are equal to zero if they are placed far than LOG2 N positions to it ( N number of filed elements ). If we take the SUM filed as source and continue to repeat this procedure than as a result all bits will be zeroes except main diagonal - this number will be the result of whole operation

procedure SUMF2( refer slice outs, inf[ ]; index incap );

const

maxincap = 32,

orf = 14;{ Slicelen = N - quantity of filed elements }

index

outcap, flag, i, w[ maxincap + lg2 Slicelen ];

slice

sum[ ];

begin

outcap := incap + lg2 Slicelen;{ Result capacity }

slice sum[ outcap ];

for i := 0 to outcap-1 do{ Initialization of field sum }

begin

if i < incap then COPY( sum[ i ], inf[ i ] ) else CLEAR( sum[ i ] );

end;

flag := 1;

while flag <> 0 do{ Work until weight of each slice will decrease to 1 }

begin

flag := 0;

for i := 0 to outcap-1 do{ Write weights to array w }

begin

WEIGHT( sum[ i ], w[ i ] );{ Weight slice }

CLEAR( sum[ i ] );{ Clear }

if w[ i ] > 1 then flag := 1{ Check convergence }

end;

for i := 0 to outcap-1 do{ Put weights in field }

begin

CLEAR( Y );

MOVSCALAR( Y, w[ i ] );{ Put w in Y }

ROT( Y, Y, i );{ Shift }

SETWORD( sum[ 0 ], Y, i ){ Writing with rotation }

end

end;

CLEAR( outs );{ Get result from main diagonal }

for i := 0 to outcap-1 do LOGF( outs, outs, sum[ i ], orf );

end;{ End of SUMF2 }