 |
Claims  |
|
|
What is claimed is:
1. A method of testing a multiplier taking first and second N-bit input
mantissa operands and producing a 2N-bit mantissa output, the method
comprising the steps of:
selecting a digit size d, such that d evenly divides into N;
allocating each of the first and second N-bit input mantissa operands into
N/d input digit fields, the input digit fields of the first operand being
A(0) through A(N/d-1), the input digit fields of the second operand being
B(0) through B(N/d-1);
allocating the 2N-bit mantissa output into 2N/d output subchunks each
having d bits, the output subchunks being S(0) through S(2N/d-1);
for each of 2.sup.2d permutations of integer i and integer j, wherein i and
j are from the range from 0 to 2.sup.d- 1, inclusive,
loading all even digit fields A(0) through A(N/d-2) of the first operand
with i;
loading all odd digit fields A(1) through A(N/d-1) of the first operand
with 0;
loading the least significant digit field B(0) of the second operand with
j;
loading the more significant digit fields B(1) through B(N/d-1) of the
second operand with 0;
performing a multiplication;
comparing N/2d even output subchunks S(0) through S(N/d-2) for equality;
comparing N/2d odd output subchunks S(1) through S(N/d-1) for equality;
continuing if the comparing steps detected equality;
reporting test failure if either of the comparing steps detected
inequality;
for each of 2.sup.2d permutations of integer i and integer j, wherein i and
j are from the range from 0 to 2.sup.d -1, inclusive,
loading all even digit fields A(0) through A(N/d-2) of the first operand
with 0;
loading all odd digit fields A(1) through A(N/d-1) of the first operand
with i;
loading the most significant digit field B(N/d-1) of the second operand
with j;
loading the less significant digit fields B(0) through B(N/d-2) of the
second operand with 0;
performing a multiplication;
comparing N/2d even output subchunks S(N/d) through S(2N/d-2) for equality;
comparing N/2d odd output subchunks S(N/d+i) through S(2N/d-1) for
equality;
continuing if the comparing steps detected equality;
reporting test failure if either of the comparing steps detected
inequality;
for each of 2.sup.2d permutations of integer i and integer j, wherein i and
j are from the range from 0 to 2.sup.d- 1, inclusive,
loading digit field A(1) of the first operand with j;
loading digit fields A(0) and A(2) through A(N/d-1) of the first operand
with 0;
loading all even digit fields B(0) through B(N/d-2) of the second operand
with 0;
loading all odd digit fields B(1) through B(N/d-1) of the second operand
with i;
performing a multiplication;
comparing N/2d even output subchunks S(2) through S(N/d) for equality;
comparing N/2d odd output subchunks S(1) through S(N/d-1) for equality;
continuing if the comparing steps detected equality;
reporting test failure if either of the comparing steps detected
inequality;
for each of 2.sup.2d permutations of integer i and integer j, wherein i and
j each are from the range from 0 to 2.sup.d- 1, inclusive,
loading digit field A(N/d-2) of the first operand with j;
loading digit fields A(0) through A(N/d-3) and A(N/d-1) of the first
operand with 0;
loading all even digit fields B(0) through B(N/d-2) of the second operand
with 0;
loading all odd digit fields B(1) through B(N/d-1) of the second operand
with i;
performing a multiplication;
comparing N/2d even output subchunks S(N/d) through S(2N/d-2) for equality;
comparing N/2d odd output subchunks S(N/d-1) through S(2N/d-3) for
equality;
continuing if the comparing steps detected equality;
reporting test failure if either of the comparing steps detected
inequality; and
reporting test passing if none of the above comparing steps detect
inequality.
2. A method of testing a multiplier as in claim 1,
wherein all 2.sup.2d permutations of integers i and j are sequentially
generated by a 2d-bit test counter having a test counter carry output.
3. A method of testing a multiplier as in claim 2,
wherein the integer i is the least significant d output bits of the test
counter; and
wherein the integer j is the most significant d bits of the test counter.
4. A method of testing a multiplier as in claim 3,
wherein the 2d-bit test counter is a Johnson counter, which performs a
single-bit counter output transition each increment cycle.
5. A method of testing a multiplier as in claim 3,
wherein the test counter carry output enables a two-bit step counter.
6. A method of testing a multiplier as in claim 1,
wherein the first and second N-bit input mantissa operands are writeable by
external software, and the 2N-bit mantissa output is readable by external
software, and
wherein the loading and comparing steps are performed by external software.
7. A method of testing a multiplier as in claim 1,
wherein the first and second N-bit input mantissa operands are not
writeable by external software, and the 2N-bit mantissa output is readable
by external software, and
wherein the loading steps are performed by internal test hardware, and the
comparing steps are performed by external software.
8. A method of testing a multiplier as in claim 1,
wherein the first and second N-bit input mantissa operands are not
writeable by external software, and the 2N-bit mantissa output is not
readable by external software, and
wherein the loading and comparing steps are performed by internal test
hardware.
9. A method of testing a multiplier as in claim 1,
wherein N is 256; and
wherein d is 4.
10. A method of testing a multiplier taking first and second N-bit input
mantissa operands and producing a 2N-bit mantissa output, the method
comprising the steps of:
selecting a digit size d, such that d evenly divides into N;
allocating each of the first and second N-bit input mantissa operands into
N/d input digit fields, the input digit fields of the first operand being
A(0) through A(N/d-1), the input digit fields of the second operand being
B(0) through B(N/d-1);
allocating the 2N-bit mantissa output into 2N/d output subchunks each
having d bits, the output subchunks being S(0) through S(2N/d-1);
for each of 2.sup.d values of integer i, wherein i takes on values in the
range of 0 to 2.sup.d -1, inclusive,
loading all even digit fields A(0) through A(N/d-2) of the first operand
with i;
loading all odd digit fields A(1) through A(N/d-1) of the first operand
with 0;
loading the least significant digit field B(0) of the second operand with
the one's complement of i;
loading the more significant digit fields B(1) through B(N/d-1) of the
second operand with 0;
performing a multiplication;
comparing N/2d even output subchunks S(0) through S(N/d-2) for equality;
comparing N/2d odd output subchunks S(1) through S(N/d-1) for equality;
continuing if the comparing steps detected equality;
reporting test failure if either of the comparing steps detected
inequality;
for each of 2.sup.d values of integer i, wherein i is in the range from 0
to 2.sup.d -1, inclusive,
loading all even digit fields A(0) through A(N/d-2) of the first operand
with 0;
loading all odd digit fields A(1) through A(N/d-1) of the first operand
with i;
loading the most significant digit field B(N/d-1) of the second operand
with the one's complement of i;
loading the less significant digit fields B(0) through B(N/d-2) of the
second operand with 0;
performing a multiplication;
comparing N/2d even output subchunks S(N/d) through S(2N/d-2) for equality;
comparing N/2d odd output subchunks S(N/d+1) through S(2N/d-1) for
equality;
continuing if the comparing steps detected equality;
reporting test failure if either of the comparing steps detected
inequality;
for each of 2.sup.d values of integer i, wherein i is in the range from 0
to 2.sup.d -1, inclusive,
loading digit field A(1) of the first operand with the one's complement of
i;
loading digit fields A(0) and A(2) through A(N/d-1) of the first operand
with 0;
loading all even digit fields B(0) through B(N/d-2) of the second operand
with 0;
loading all odd digit fields B(1) through B(N/d-1) of the second operand
with i;
performing a multiplication;
comparing N/2d even output subchunks S(2) through S(N/d) for equality;
comparing N/2d odd output subchunks S(1) through S(N/d-1) for equality;
continuing if the comparing steps detected equality;
reporting test failure if either of the comparing steps detected
inequality;
for each of 2.sup.d values of integer i, wherein i is in the range from 0
to 2.sup.d -1, inclusive,
loading digit field A(N/d-2) of the first operand with the one's complement
of i;
loading digit fields A(0) through A(N/d-3) and A(N/d-1) of the first
operand with 0;
loading all even digit fields B(0) through B(N/d-2) of the second operand
with 0;
loading all odd digit fields B(1) through B(N/d-1) of the second operand
with i;
performing a multiplication;
comparing N/2d even output subchunks S(N/d) through S(2N/d-2) for equality;
comparing N/2d odd output subchunks S(N/d-1) through S(2N/d-3) for
equality;
continuing if the comparing steps detected equality;
reporting test failure if either of the comparing steps detected
inequality; and
reporting test passing if none of the above
comparing steps detect inequality.
11. A method of testing a multiplier as in claim 10,
wherein 2.sup.d permutations of integers i and the one's complement of i
are sequentially generated by a d-bit test counter having a test counter
carry output.
12. A method of testing a multiplier as in claim 11,
wherein the integer i is the output bits of the test counter; and
wherein the one's complement of i is the logical inverse of the output bits
of the test counter.
13. A method of testing a multiplier as in claim 12,
wherein the d-bit test counter is a Johnson counter, which performs a
single-bit counter output transition each increment cycle.
14. A method of testing a multiplier as in claim 12,
wherein the test counter carry output enables a two-bit step counter.
15. A method of testing a multiplier as in claim 10,
wherein the first and second N-bit input mantissa operands are not
writeable by external software, and the 2N-bit mantissa output is readable
by external software, and
wherein the loading steps are performed by internal test hardware, and the
comparing steps are performed by external software.
16. A method of testing a multiplier as in claim 10,
wherein the first and second N-bit input mantissa operands are not
writeable by external software, and the 2N-bit mantissa output is not
readable by external software, and
wherein the loading and comparing steps are performed by internal test
hardware.
17. A method of testing a multiplier as in claim 10,
wherein N is 256; and
wherein d is 4.
18. A method of testing an adder taking first and second N-bit input
operands and producing an N-bit output, the method comprising the steps
of:
selecting a digit size d, such that d evenly divides into N;
allocating each of the first and second N-bit input operands into N/d input
digit fields, the input digit fields of the first operand being A(0)
through A(N/d-1), the input digit fields of the second operand being B(0)
through B(N/d-1);
allocating the N-bit output into N/d output chunks each having d bits, the
output chunks being C(0) through C(N/d-1);
for each of 2.sup.2(d-1) permutations of d-1-bit integer i and d-1-bit
integer j, wherein i and j are from the integer range from 0 to 2.sup.d-1
-1, inclusive,
loading the less significant d-1 bits of all digit fields A(0) through
A(N/d-1) of the first operand with i;
loading the most significant bit of all digit fields A(0) through A(N/d-1)
of the first operand with 0;
loading the less significant d-1 bits of all digit fields B(0) through
B(N/d-1) of the second operand with j;
loading the most significant bit of all digit fields B(0) through B(N/d-1)
of the second operand with 0;
performing an addition;
comparing the N/d output chunks C(0) through C(N/d-1) for equality;
continuing if the comparing step detected equality;
reporting test failure if the comparing step detected inequality; reserving
r least significant bits in each of the first and second input operands
and the N-bit output, r being in from the range from 1 to d-1, inclusive,
the r least significant bits being set to zero, thereby defining first and
second N-r bit shifted input operands and an N-r bit shifted output;
allocating each of the first and second N-r bit shifted input operands into
N/d-1 shifted input digit fields, the shifted input digit fields of the
first shifted operand being AS(0) through AS(N/d-2), the shifted input
digit fields of the second shifted operand being BS(0) through BS(N/d-2);
allocating the N-r bit shifted output into N/d-1 shifted output chunks each
having d-1 bits, the shifted output chunks being CS(0) through CS(N/d-2);
for each of 2.sup.2(d-1) permutations of d-1-bit integer i and d-1-bit
integer j, wherein i and j are from the integer range from 0 to 2.sup.d-1,
inclusive,
loading the less significant d-1 bits of all digit fields AS(0) through
AS(N/d-1) of the first shifted operand with i;
loading the most significant bit of all digit fields AS(0) through
AS(N/d-1) of the first
shifted operand with 0;
loading the less significant d-1 bits of all digit fields BS(0) through
BS(N/d-1) of the second shifted operand with j;
loading the most significant bit of all digit fields BS(0) through
BS(N/d-1) of the second shifted operand with 0;
performing an addition;
comparing the N/d-1 shifted output chunks CS(0) through CS(N/d-2) for
equality;
continuing if the comparing step detected equality;
reporting test failure if the comparing step detected inequality; and
reporting test passing if none of the above comparing steps detect
inequality.
19. A method of testing an adder as in claim 18,
wherein all2.sup.2(d-1) permutations of integers i and j are sequentially
generated by a 2(d-1) bit test counter having a test counter carry output.
20. A method of testing an adder as in claim 19,
wherein the integer i is the least significant d-1 output bits of the test
counter; and
wherein the integer j is the most significant d-1 bits of the test counter.
21. A method of testing an adder as in claim 20,
wherein the 2(d-1) bit test counter is a Johnson counter, which performs a
single-bit counter output transition each increment cycle.
22. A method of testing an adder as in claim 20,
wherein the test counter carry output enables a one-bit step counter.
23. A method of testing an adder as in claim 18,
wherein the first and second N-bit input operands are writeable by external
software, and the N-bit output is readable by external software, and
wherein the loading and comparing steps are performed by external software.
24. A method of testing an adder as in claim 18,
wherein the first and second N-bit input operands are not writeable by
external software, and the N-bit output is readable by external software,
and
wherein the loading steps are performed by internal test hardware, and the
comparing steps are performed by external software.
25. A method of testing an adder as in claim 18,
wherein the first and second N-bit input operands are not writeable by
external software, and the N-bit output is not readable by external
software, and
wherein the loading and comparing steps are performed by internal test
hardware.
26. A method of testing an adder as in claim 18,
wherein N is 256; and
wherein d is 4.
27. A method of testing an adder as in claim 18,
wherein r is 1.
28. A method of testing an adder as in claim 18,
wherein r is d-1.
29. A method of testing an adder taking first and second N-bit input
operands and producing an N-bit output, the method comprising the steps
of:
selecting a digit size d, such that d evenly divides into N;
allocating each of the first and second N-bit input operands into N/d input
digit fields, the input digit fields of the first operand being A(0)
through A(N/d-1), the input digit fields of the second operand being B(0)
through B(N/d-1);
allocating the N-bit output into N/d output chunks each having d bits, the
output chunks being C(0) through C(N/d-1);
for each of 2.sup.d-1 permutations of d-1-bit integer i, wherein i is from
the integer range from 0 to 2.sup.d-1 -1, inclusive,
loading the less significant d-1 bits of all digit fields A(0) through
A(N/d-1) of the first operand with i;
loading the most significant bit of all digit fields A(0) through A(N/d-1)
of the first operand with 0;
loading the less significant d-1 bits of all digit fields B(0) through
B(N/d-1) of the second operand with the one's complement of
i;
loading the most significant bit of all digit fields B(0) through B(N/d-1)
of the second operand with 0;
performing an addition;
comparing the N/d output chunks C(0) through C(N/d-1) for equality;
continuing if the comparing step detected equality;
reporting test failure if the comparing step detected inequality;
reserving r least significant bits in each of the first and second input
operands and the N-bit output, r being in from the range from 1 to d-1,
inclusive, the r least significant bits being set to zero, thereby
defining first and second N-r bit shifted input operands and an N-r bit
shifted output;
allocating each of the first and second N-r bit shifted input operands into
N/d-1 shifted input digit fields, the shifted input digit fields of the
first shifted operand being AS(0) through AS(N/d-2), the shifted input
digit fields of the second shifted operand being BS(0) through BS(N/d-2);
allocating the N-r bit shifted output into N/d-1 shifted output chunks each
having d-1 bits, the shifted output chunks being CS(0) through CS(N/d-2);
for each of 2.sup.d-1 permutations of d-1-bit integer i, wherein i is from
the integer range from 0 to 2.sup.d-1 -1, inclusive,
loading the less significant d-1 bits of all digit fields AS(0) through
AS(N/d-1) of the first shifted operand with i;
loading the most significant bit of all digit fields AS(0) through
AS(N/d-1) of the first shifted operand with 0;
loading the less significant d-1 bits of all digit fields BS(0) through
BS(N/d-1) of the second shifted operand with the one's complement of i;
loading the most significant bit of all digit fields BS(0) through
BS(N/d-1) of the second shifted operand with 0;
performing an addition;
comparing the N/d-1 shifted output chunks CS(0) through CS(N/d-2) for
equality;
continuing if the comparing step detected equality;
reporting test failure if the comparing step detected inequality; and
reporting test passing if none of the above comparing steps detect
inequality.
30. A method of testing an adder as in claim 29,
wherein 2.sup.d-1 permutations of integer i and the one's complement of i
are sequentially generated by a d-1-bit test counter having a test counter
carry output.
31. A method of testing an adder as in claim 30,
wherein the integer i is the output bits of the test counter; and
wherein the one's complement of i is the logical inverse of the output bits
of the test counter.
32. A method of testing an adder as in claim 31,
wherein the d-1-bit test counter is a Johnson counter, which performs a
single-bit counter output transition each increment cycle.
33. A method of testing an adder as in claim 31,
wherein the test counter carry output enables a one-bit step counter.
34. A method of testing an adder as in claim 29,
wherein the first and second N-bit input operands are writeable by external
software, and the N-bit output is readable by external software, and
wherein the loading and comparing steps are performed by external software.
35. A method of testing an adder as in claim 29,
wherein the first and second N-bit input operands are not writeable by
external software, and the N-bit output is readable by external software,
and
wherein the loading steps are performed by internal test hardware, and the
comparing steps are performed by external software.
36. A method of testing an adder as in claim 29,
wherein the first and second N-bit input operands are not writeable by
external software, and the N-bit output is not readable by external
software, and
wherein the loading and comparing steps are performed by internal test
hardware.
37. A method of testing an adder as in claim 29,
wherein N is 256; and
wherein d is 4.
38. A method of testing an adder as in claim 29,
wherein r is 1.
39. A method of testing an adder as in claim 29,
wherein r is d-1.
40. A method of testing a subtractor taking first and second N-bit input
operands and producing an N-bit output, the method comprising the steps
of:
selecting a digit size d, such that d evenly divides into N;
allocating each of the first and second N-bit input operands into N/d input
digit fields, the input digit fields of the first operand being A(0)
through A(N/d-1), the input digit fields of the second operand being B(0)
through B(N/d-1);
allocating the N-bit output into N/d output chunks each having d bits, the
output chunks being C(0) through C(N/d-1);
for each of 2.sup.2(d-1) permutations of d-1-bit integer i and d-1-bit
integer j, wherein i and j are from the integer range from 0 to 2.sup.d-1
-1, inclusive,
loading the less significant d-1 bits of all digit fields A(0) through
A(N/d-1) of the first operand with i;
loading the most significant bit of all digit fields A(0) through A(N/d-1)
of the first operand with 1;
loading the less significant d-1 bits of all digit fields B(0) through
B(N/d-1) of the second operand with j;
loading the most significant bit of all digit fields B(0) through B(N/d-1)
of the second operand with 0;
performing a subtraction;
comparing the N/d output chunks C(0) through C(N/d-1) for equality;
continuing if the comparing step detected equality;
reporting test failure if the comparing step detected inequality;
reserving r least significant bits in each of the first and second input
operands and the N-bit output, r being in from the range from 1 to d-1,
inclusive, the r least significant bits being set to zero, thereby
defining first and second N-r bit shifted input operands and an N-r bit
shifted output;
allocating each of the first and second N-r bit shifted input operands into
N/d-1 shifted input digit fields, the shifted input digit fields of the
first shifted operand being AS(0) through AS(N/d-2), the shifted input
digit fields of the second shifted operand being BS(0) through BS(N/d-2);
allocating the N-r bit shifted output into N/d-1 shifted output chunks each
having d-1 bits, the shifted output chunks being CS(0) through CS(N/d-2);
for each of 2.sup.2(d-1) permutations of d-1-bit integer i and d-1-bit
integer j, wherein i and j are from the integer range from 0 to 2.sup.d-1
-1, inclusive,
loading the less significant d-1 bits of all digit fields AS(0) through
AS(N/d-1) of the first shifted operand with i;
loading the most significant bit of all digit fields AS(0) through
AS(N/d-1) of the first shifted operand with 1;
loading the less significant d-1 bits of all digit fields BS(0) through
BS(N/d-1) of the second shifted operand with j;
loading the most significant bit of all digit fields BS(0) through
BS(N/d-1) of the second shifted operand with 0;
performing a subtraction;
comparing the N/d-1 shifted output chunks CS(0) through CS(N/d-2) for
equality;
continuing if the comparing step detected equality;
reporting test failure if the comparing step detected inequality; and
reporting test passing if none of the above comparing steps detect
inequality.
41. A method of testing a subtractor as in claim 40,
wherein all 2.sup.2(d-1) permutations of integers i and j are sequentially
generated by a 2(d-1) bit test counter having a test counter carry output.
42. A method of testing a subtractor as in claim 41,
wherein the integer i is the least significant d-1 output bits of the test
counter; and
wherein the integer j is the most significant d-1bits of the test counter.
43. A method of testing a subtractor as in claim 42,
wherein the 2(d-1) bit test counter is a Johnson counter, which performs a
single-bit counter output transition each increment cycle.
44. A method of testing a subtractor as in claim 42,
wherein the test counter carry output enables a one-bit step counter.
45. A method of testing a subtractor as in claim 40,
wherein the first and second N-bit input operands are writeable by external
software, and the N-bit output is readable by external software, and
wherein the loading and comparing steps are performed by external software.
46. A method of testing a subtractor as in claim 40,
wherein the first and second N-bit input operands are not writeable by
external software, and the N-bit output is readable by external software,
and
wherein the loading steps are performed by internal test hardware, and the
comparing steps are performed by external software.
47. A method of testing a subtractor as in claim 40,
wherein the first and second N-bit input operands are not writeable by
external software, and the N-bit output is not readable by external
software, and
wherein the loading and comparing steps are performed by internal test
hardware.
48. A method of testing a subtractor as in claim 40,
wherein N is 256; and
wherein d is 4.
49. A method of testing a subtractor as in claim 40,
wherein r is 1.
50. A method of testing a subtractor as in claim 40,
wherein r is d-1.
51. A method of testing a subtractor taking first and second N-bit input
operands and producing an N-bit output, the method comprising the steps
of:
selecting a digit size d, such that d evenly divides into N;
allocating each of the first and second N-bit input operands into N/d input
digit fields, the input digit fields of the first operand being A(0)
through A(N/d-1), the input digit fields of the second operand being B(0)
through B(N/d-1);
allocating the N-bit output into N/d output chunks each having d bits, the
output chunks being C(0) through C(N/d-1);
for each of 2.sup.d-1 permutations of d-1-bit integer i, wherein i is from
the integer range from 0 to 2.sup.d-1 -1, inclusive,
loading the less significant d-1 bits of all digit fields A(0) through
A(N/d-1) of the first operand with i;
loading the most significant bit of all digit fields A(0) through A(N/d-1)
of the first operand with 1;
loading the less significant d-1 bits of all digit fields B(0) through
B(N/d-1) of the second operand with the one's complement of i;
loading the most significant bit of all digit fields B(0) through B(N/d-1)
of the second operand with 0;
performing a subtraction;
comparing the N/d output chunks C(0) through C(N/d-1) for equality;
continuing if the comparing step detected equality;
reporting test failure if the comparing step detected inequality;
reserving r least significant bits in each of the first and second input
operands and the N-bit output, r being in from the range from 1 to d-1,
inclusive, the r least significant bits being set to zero, thereby
defining first and second N-r bit shifted input operands and an N-r bit
shifted output; allocating each of the first and second N-r bit shifted
input operands into N/d-1 shifted input digit fields, the shifted input
digit fields of the first shifted operand being AS(0) through AS(N/d-2),
the shifted input digit fields of the second shifted operand being BS(0)
through BS(N/d-2);
allocating the N-r bit shifted output into N/d-1 shifted output chunks each
having d-1 bits, the shifted output chunks being CS(0) through CS(N/d-2);
for each of 2.sup.d-1 permutations of d-1-bit integer i, wherein i is from
the integer range from 0 to 2.sup.d-1 -1, inclusive,
loading the less significant d-1 bits of all digit fields AS(0) through
AS(N/d-1) of the first shifted operand with i;
loading the most significant bit of all digit fields AS(0) through
AS(N/d-I) of the first shifted operand with 1;
loading the less significant d-1 bits of all digit fields BS(0) through
BS(N/d-1) of the second shifted operand with the one's complement of i;
loading the most significant bit of all digit fields BS(0) through
BS(N/d-1) of the second shifted operand with 0;
performing a subtraction;
comparing the N/d-1 shifted output chunks CS(0) through CS(N/d-2) for
equality;
continuing if the comparing step detected equality;
reporting test failure if the comparing step detected inequality; and
reporting test passing if none of the above comparing steps detect
inequality.
52. A method of testing a subtractor as in claim 51,
wherein 2.sup.d-1 permutations of integer i and the one's complement of i
are sequentially generated by a d-1-bit test counter having a test counter
carry output.
53. A method of testing a subtractor as in claim 52,
wherein the integer i is the output bits of the test counter; and
wherein the one's complement of i is the logical inverse of the output bits
of the test counter.
54. A method of testing a subtractor as in claim 53,
wherein the d-1-bit test counter is a Johnson counter, which performs a
single-bit counter output transition each increment cycle.
55. A method of testing a subtractor as in claim 53,
wherein the test counter carry output enables a one-bit step counter.
56. A method of testing a subtractor as in claim 51,
wherein the first and second N-bit input operands are writeable by external
software, and the N-bit output is readable by external software, and
wherein the loading and comparing steps are performed by external software.
57. A method of testing a subtractor as in claim 51,
wherein the first and second N-bit input operands are not writeable by
external software, and the N-bit output is readable by external software,
and
wherein the loading steps are performed by internal test hardware, and the
comparing steps are performed by external software.
58. A method of testing a subtractor as in claim 51,
wherein the first and second N-bit input operands are not writeable by
external software, and the N-bit output is not readable by external
software, and
wherein the loading and comparing steps are performed by internal test
hardware.
59. A method of testing a subtractor as in claim 51,
wherein N is 256; and
wherein d is 4.
60. A method of testing a subtractor as in claim 51,
wherein r is 1.
61. A method of testing a subtractor as in claim 51,
wherein r is d-1. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the testing of integrated circuits and, in
particular, to a built in self test (BIST) technique for determining the
existence of "stuck at faults" in multiplier, adder, or subtractor
implementations by pseudo-exhaustively exercising all permutations of
inputs and outputs. The technique is scalable to any size.
2. Discussion of the Related Art
In a production testing environment, the testing of semiconductor devices
is performed to separate good devices from bad devices. Data collected
from a test program may be used for yield enhancement. This is done by
finding marginal areas of the device design or in the fabrication process
and then making improvements to raise yields and therefore lower cost. The
basis for all testing of complex integrated circuits is the comparison of
known correct output patterns to the response of a device under test. The
simulation of the device design is typically done with input stimuli which
fully exercise the design and therefore verify the correctness of the
design. After fabrication of the design, often the same stimuli (also
called test vectors) are presented to each device under test to separate
good devices from defective devices. Comparisons are made cycle by cycle
with an option to ignore certain pins, times, or patterns. If the device
response and the expected response are not in agreement, the devices are
usually considered defective.
Built-In Self-Testing (BIST) is the implementation of logic built into the
circuitry to do testing without the use of an external tester for pattern
generation and comparison purposes. An external tester is still needed to
categorize failures and to separate good units from bad units. In this
case, the external tester supplies clocks to the device and determines
pass/fail from the outputs of the device. The test vectors are generated
and input to the device under test, and a resulting signature is
generated. The signature can be a simple pass or fail signal presented on
one pin of the part, or the signal may be a polynomial generated during
the self-testing. Usually, if a polynomial is used, it has some
significance to the actual states of the part.
Self-testing capability can be implemented on virtually any size logic
block. However, there are tradeoffs between the extra logic added to
implement the self-testing capability and the inherent logic of the block
to be tested. Often, the self-test logic adds not only extra hardware to
the design, but also adds latency to the logic block having the self-test
even under normal operations.
Many Built In Self Test (BIST) arrangements deal with embedded memory
structures like Random Access Memories (RAMs). These arrangements usually
tend to be implementation dependent and have rather complicated
arrangements for generating data and predicting failures. In many cases, a
signature is collected for analysis after a series of stimuli has been
applied to the block being tested. Many BIST arrangements do not have the
flexibility to be implemented with either software alone or hardware alone
or a mixture of both. FIG. 2 depicts a typical self-test circuit. The
logic block under test 201 has N independent logic inputs. An N-bit
counter sequentially steps through all 2.sup.N unique input permutations.
However, if it is desired for the self-test time to be less than about one
second, N is typically limited to about twenty. The logic block under test
has M output bits. An M-bit flip-flop 203 latches the output of after the
first set of stimuli have been applied. Each subsequent M-bit output of
the logic block is exclusive ORed with the contents of the flip-flop 203
such that at the end of the self-test, an M-bit signature is available as
the output of the flip-flop 203. An exclusive OR 204 or exclusive NOR
function is typically used because the its output value is always
dependent upon all of the inputs. Therefore, if any single output of the
logic block under test is incorrect, the final signature will be
incorrect. (In contrast, a two-input AND function, for example, does not
produce the same input-output dependence. For example, if one input of the
AND function is zero, then the value of the other input does not influence
the output at all.)
Direct access testing is alternative to direct access testing whereby an
external tester gains access to a device logic block by bringing signals
from the block to the outside world via multiplexors. Input test vectors
are directly supplied to the logic block by the external tester, and then
the outputs are directly measured by the tester. This is one of the
simplest methods for checking devices for logical functionality. Often,
direct access testing supplements previous testing methods by allowing the
user to impose input data patterns directly on large blocks of logic which
would not otherwise be directly accessible. Using direct access testing,
entering a special test mode would force certain logic blocks via
multiplexors to gain access to the outside pins of the part, and to
measure the access, status, and logical functionality of the block
directly.
Fault grading is a measure of test coverage of a given set of stimuli and
responses for a given circuit. This figure of merit is used to ensure that
the device is fully testable and measurable. Typically, once the test
patterns are developed for the device, artificial faults are put into the
design via simulation to ensure that the part is fully testable and
observable.
A "stuck-at fault" may be caused by a variety of conditions, although the
defining characteristic of a stuck-at fault is that a circuit node is
undesirably immovable from certain logic value (either zero or one)
regardless of any circuit conditions. FIG. 1 illustrates a single
stuck-at-one fault 104 injected into a simple logic circuit with an
exhaustive set of input data patterns for fully checking the functionality
of the logic circuit. Even though the stuck-at-one fault 104 exists at an
internal node which is not directly observable, the stuck-at-one fault 104
shows up on at the output Z of the circuit. Gaining high fault coverage is
a very desirable method for ensuring that the tested devices will function
correctly in a system. Ideally, all internal nodes should be tested for
stuck-at-zero and stuck-at-one faults.
Although fault grading using single stuck-at-zero and single-stuck-at-one
faults covers many types of semiconductor failures, it does not cover all
of them. For example, bridging faults and intermittent faults are two
other common types of faults which occur in semiconductor devices.
Data patterns that were generated during simulation are often converted
into a functional production test program. The cost of production testing
is very much related to test time per device. In production, package
handlers, wafer probe equipment, people, and often a computer network are
needed to run production tests.
One effective way to test a circuit 100 for single stuck-at faults is to
exhaustively check all outputs of the circuit for correctness for all
possible input permutations. For the circuit shown in FIG. 1, this is a
relatively straightforward procedure which requires only sixteen separate
operations of the circuit. In general, for a circuit having N inputs,
2.sup.N operations of the circuit are required to exhaustively test the
circuit using all possible input permutations. This is feasible for
smaller circuits; however, because the number of input permutations
increases exponentially with N, exhaustively testing all 2.sup.N input
permutations becomes prohibitively time consuming.
As feature sizes for semiconductor manufacturing processes become smaller,
bus widths become larger. Thirty-two and sixty-four bit internal busses
are commonplace today. Similarly, the widths of the arithmetic units and
mathematical functions become larger. Hardware multipliers, dividers,
square root modules, adders, and subtractors supporting thirty-two and
sixty-four-bit operands currently are available.
Moreover, in the field of cryptography, there is demand for specialized
hardware to support asymmetric encryption/decryption algorithms such as
the RSA algorithm. (See, for example, U.S. Pat. No. 4,405,829 for a
description of the RSA algorithm.) Such encryption algorithms typically
require many multiplications of very large numbers. If very large
multipliers are implemented in hardware, the testing of those multipliers
offers significant challenges. For example, if it is assumed that a
multiplication requires 1 nanosecond regardless of the size of the
operands (a generously low estimate), an exhaustive test of a 8-bit
multiplier requires only 65.5 microseconds, an exhaustive test of a 16-bit
multiplier requires only 4.3 seconds, but an exhaustive test of a 32-bit
multiplier would require about 584.9 years, while an exhaustive test of a
256-bit multiplier would require about 10.sup.146.6 years. This is
approximately 10.sup.136.6 times greater than the estimated age of the
universe (assuming that the age of the universe is 10 billion years). This
demonstrates that an exhaustive test of mathematical functions in a manner
such as shown in FIG. 1 is totally infeasible.
It is clear from the above discussion that there is a need for testing
semiconductor circuits implementing math functions such that all internal
nodes are checked for stuck-at faults without performing an exhaustive
test of all possible input permutations.
SUMMARY OF THE INVENTION
One object of the present invention is to provide a method of exhaustively
testing a multiplier, an adder, or a subtractor for stuck-at faults
without exhaustively sequencing through all permutations of inputs.
Another object of the present invention is to provide a scalable method of
testing a multiplier, an adder, or a subtractor such that stuck-at faults
can be located in a fixed number of steps regardless of the size of the
multiplier, adder, or subtractor.
The methods of performing built-in self tests according to the present
invention are used to determine if there are any "stuck at faults" in
large multipliers, adders, or subtractors by pseudo-exhaustively
exercising all permutations of inputs and outputs. The methods are
scalable to any size and are applied to a multiplier, an adder, and a
subtractor.
The built-in self-test capability according to the present invention can be
invoked at any time, for example, by the user setting a self-test control
bit. Setting the self-test control bit will cause the built-in self test
operation to be executed a cycle after the control bit is set. If at any
time during the built-in self test, the self-test detects an error, an
error status bit will be set. The end of the self-test operation is
indicated by an interrupt being issued. The user, which may be a test
program or a production tester, can then determine if the self-test was
successful by interrogating the status register containing the status bit
and checking whether or not the error status bit is set. If the error bit
set is set, a flaw has been detected.
The implementations of the built-in self-test methods according to the
present invention are highly flexible. For example, a total hardware
solution, a total software solution, or a solution using a mixture of
hardware and software can be utilized to implement the built-in self-test
according to the present invention. The method of testing a multiplier, an
adder, or a subtractor according to the present invention is to logically
partition the operation into several smaller but identical independent
| | |
