Re: How to detect errors in a multiplier

In article <[EMAIL PROTECTED]>,
Thomas Gutzler <[EMAIL PROTECTED]> writes:
|> > |> 
|> > |> I'm looking for an error detection method for hardware multipliers. I 
|> > |> found a paper describing parity prediction but this seems to be large 
|> > |> overhead and I'm trying to keep the overhead as small as possible.
|> > |> I also found a paper that sais: take the self-dual complement of a 
|> > |> funcion (multiplication), XOR the results, if the output constantly 
|> > |> changes everything is allright. But in this case I have to have the 
|> > |> functional description of every output bit of, in my case, a 32 bit 
|> > |> multiplier to generate the self-dual complement - I don't have that.
|> > 
|> > What sort of multiplication?  If it is full precision, then you could
|> > check the inputs and output modulo N, for a few small prime N, and
|> > also check the sign and position of the most significant bit.  That
|> > would be pretty reliable.
|> 
|> What would be the relation between input and output ?
|> The parity prediction does something like that:
|> modulo2 sum of parities of operands and parity of carries should be the 
|> same as parity of result.
|> 
|> Would be nice to have a relation between input and ouput without the 
|> need of the carries. Modulo calculations seem to be a good way to do 
|> that. I just don't know how to relate input and output.

If A |M| = a and B |M| = b, then A.B |M| = a.b |M|.

While it would take a fair amount of circuitry to do, it could be
done in parallel.  Oh, it works for addition and subtraction, too.
It's all basic number theory.

The great advantage of it is that using a prime M (> 2) means that
it is very unlikely that a typical hardware error will be the sort
that maintains the moduli.

The downside is that, if your parity calculation is too expensive,
it will be far too expensive.


Regards,
Nick Maclaren.