How to detect errors in a multiplier

How to detect errors in a multiplier

Post by Thomas Gutzle » Fri, 26 Sep 2003 15:18:28



Hi,

I'm not sure, if this is off topic, but I'll try :)

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.

Any ideas?
I don't want to detect single faults - if an error occurs, it will occur
forever.

Cheers,
  Tom

 
 
 

How to detect errors in a multiplier

Post by Nick Maclar » Fri, 26 Sep 2003 21:54:28



|>
|> 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.

Regards,
Nick Maclaren.

 
 
 

How to detect errors in a multiplier

Post by Thomas Gutzle » Fri, 26 Sep 2003 16:05:07





> |>
> |> 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.

Tom

 
 
 

How to detect errors in a multiplier

Post by Nick Maclar » Fri, 26 Sep 2003 22:28:11



|> > |>
|> > |> 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.

 
 
 

1. Detect Error Frames

Hello
I wonder if there is any metod to detect error frames from a
application using a CAN controller?

The Can controller is an Intel 82527. driver is made for VxWorks.
I have a bus analyze software that are able to detect and also to
transmit error frames.
So I could easy generate an error frame on the bus.
I would like to calculate number of error frames on the bus, from the
application.

//Kristoffer

2. Books & Examples

3. Looking for modified UART virtual peripheral [SX microcontrollers] (parity bit/parity decode, framing error detect)

4. FAQ? (was -- Re: xdm)

5. 5-bit CRC polynomial or better way to detect errors?

6. IDE won't find my files.

7. Hierarchical Hypercube Multicomp. INs

8. Run DOS filter from OS/2 window ?

9. 8150, 3270, INS info wanted..

10. Tiramisu:Read error in sector...FDISK:write protect error writing fixed disk

11. error frequency stats from error-correcting coded media?

12. Error Correction Codes & Disk Errors