Built-in self tests for large multiplier, adder, or subtractor

Claim 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 2d permutations of integer i and integer j, wherein i and j are from the range from 0 to 2 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 2d permutations of integer i and integer j, wherein i and j are from the range from 0 to 2 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 2d permutations of integer i and integer j, wherein i and j are from the range from 0 to 2 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 2d permutations of integer i and integer j, wherein i and j each are from the range from 0 to 2 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.

Claim 2

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 2d permutations of integer i and integer j, wherein i and j are from the range from 0 to 2 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 2d permutations of integer i and integer j, wherein i and j are from the range from 0 to 2 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 2d permutations of integer i and integer j, wherein i and j are from the range from 0 to 2 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 2d permutations of integer i and integer j, wherein i and j each are from the range from 0 to 2 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.

Claim 11

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 d values of integer i, wherein i takes on values in the range of 0 to 2 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 d values of integer i, wherein i is in the range from 0 to 2 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 d values of integer i, wherein i is in the range from 0 to 2 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 d values of integer i, wherein i is in the range from 0 to 2 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.

Claim 12

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 d values of integer i, wherein i takes on values in the range of 0 to 2 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 d values of integer i, wherein i is in the range from 0 to 2 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 d values of integer i, wherein i is in the range from 0 to 2 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 d values of integer i, wherein i is in the range from 0 to 2 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.

Claim 20

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

Claim 21

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

Claim 32

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 d-1 permutations of d-1-bit integer i, wherein i is from the integer range from 0 to 2 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 d-1 permutations of d-1-bit integer i, wherein i is from the integer range from 0 to 2 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.

Claim 33

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 d-1 permutations of d-1-bit integer i, wherein i is from the integer range from 0 to 2 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 d-1 permutations of d-1-bit integer i, wherein i is from the integer range from 0 to 2 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.

Claim 44

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

Claim 45

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

Claim 56

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 d-1 permutations of d-1-bit integer i, wherein i is from the integer range from 0 to 2 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 d-1 permutations of d-1-bit integer i, wherein i is from the integer range from 0 to 2 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.

Claim 57

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 d-1 permutations of d-1-bit integer i, wherein i is from the integer range from 0 to 2 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 d-1 permutations of d-1-bit integer i, wherein i is from the integer range from 0 to 2 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.