chaitanyakurmala@gmail.co
Guest
Mon Feb 15, 2010 6:32 am
hi all,
lets say there is a system in which there are N -inputs and 1 -
output. lets say N-100 or 1000 etc.
if we want to test it completely we have to give all 2 power N inputs
and examine the functionality which will take more time and impossible
as N goes high.
so my question is how many no of optimum inputs one should give to
test the functionality of such system.
glen herrmannsfeldt
Guest
Mon Feb 15, 2010 8:25 am
chaitanyakurmala_at_gmail.com <chaitanyakurmala_at_gmail.com> wrote:
Quote:
lets say there is a system in which there are N -inputs and 1 -
output. lets say N-100 or 1000 etc.
if we want to test it completely we have to give all 2 power N inputs
and examine the functionality which will take more time and impossible
as N goes high.
In general, no, you don't have to test all 2**N combinations.
You have to know for each system which need to be tested.
Quote:
so my question is how many no of optimum inputs one should give to
test the functionality of such system.
Say, for example, that the system is a 1000 input XOR gate.
If it works with all zeros, and with all combinations of
only one input 1, then it likely works for all. (It might depend
on the exact implementation for XOR.) For memory arrays, the likely
failure modes connect neighboring cells, so the test patterns
have to know the way the address decoders work on the chip.
-- glen
Jonathan Bromley
Guest
Mon Feb 15, 2010 10:35 am
On Sun, 14 Feb 2010 20:32:19 -0800 (PST), "chaitanyakurmala_at_gmail.com"
<chaitanyakurmala_at_gmail.com> wrote:
Quote:
hi all,
lets say there is a system in which there are N -inputs and 1 -
output. lets say N-100 or 1000 etc.
if we want to test it completely we have to give all 2 power N inputs
and examine the functionality which will take more time and impossible
as N goes high.
so my question is how many no of optimum inputs one should give to
test the functionality of such system.
This is a fascinating academic problem that has been addressed
in many ways over the years.
In a seminal study by Marker and Proff [1] it was shown that
at least one solution exists that will globally maximise the
Grade function [2]. Unfortunately, this function must be
uniquely recalculated for each problem, and is also time-
varying, so the existence of a theoretically achievable
maximum is unhelpful in practice.
An alternative heuristic method, which seems to have been
first used by Slacker and Goodtime [3] in their investigation
of alcohol tolerance in the female population, involves
the application of random inputs. However, this approach
is not guaranteed to find a global maximum of the Grade
function and can exhibit instability, causing the solution
to oscillate around a local minimum instead.
From a practical point of view there appear to be three
productive approaches. The first, and least satisfactory,
is to apply the "envelope" cost function of Wonga and
Moolah [$400]. Although they achieved some success in
their original study, time variability of the Grade
function and its sensitivity to the Ethix constraint [5]
have given it a reputation for lack of repeatability.
The second, originally due to Quitter, is to sidestep the
problem entirely by application of the Corse Transformation -
I'm sorry I don't have a reference for that, but you
should be able to find information in any good Social
Studies library. Finally there is Plagia's method of
duplication [7, 8, 9, 10 et al], which has been used
successfully on innumerable studies.
References:
[1] Marker and Proff: "On the minimization of student
interference in real work", J.Edu.Obfusc. 1953
[2] Grade, A: "A new assessment function", J..zzzzz....
--
Jonathan Bromley
Kolja Sulimma
Guest
Mon Feb 15, 2010 3:15 pm
On 15 Feb., 05:32, "chaitanyakurm...@gmail.com"
<chaitanyakurm...@gmail.com> wrote:
Quote:
hi all,
lets say there is a system in which there are N -inputs and 1 -
output. lets say N-100 or 1000 etc.
if we want to test it completely we have to give all 2 power N inputs
and examine the functionality which will take more time and impossible
as N goes high.
so my question is how many no of optimum inputs one should give to
test the functionality of such system.
You can use formal verification to achieve 100% coverage.
The tools are expensive, but they work.
Kolja Sulimma
Brian Drummond
Guest
Mon Feb 15, 2010 3:25 pm
On Sun, 14 Feb 2010 20:32:19 -0800 (PST), "chaitanyakurmala_at_gmail.com"
<chaitanyakurmala_at_gmail.com> wrote:
Quote:
hi all,
lets say there is a system in which there are N -inputs and 1 -
output. lets say N-100 or 1000 etc.
if we want to test it completely we have to give all 2 power N inputs
and examine the functionality which will take more time and impossible
as N goes high.
so my question is how many no of optimum inputs one should give to
test the functionality of such system.
Enough to cover the state space of the system.
Look for "coverage metrics" for more information.
Glenn's answer is good, but I'd add:
- it is best achieved with intimate knowledge of the system under test
(but not necessarily so intimate that the tester shares the designer's
blind spots!)
- don't stop at just one test strategy (e.g. testing one bit at a time
with all others '0') See "Hubble Telescope" for a failure to consider
this...
- Consider and test for pathological cases - e.g. where an internal
counter carries into the next highest bit or rolls over to 0
- test one count either side of such problem areas as well as the problem
case itself - sometimes a problem has been hidden by a quick fix!
- make at least one test deliberately fail, to prove that a "pass" doesn't
mean that reports have been accidentally turned off!
- "constrained random" testing may find errors you didn't consider above.
- some designs CAN be exhaustively tested in a reasonable time.
A 24-bit square root unit can, a 24-bit multiplier (48 inputs) cannot
(for a suitable definition of reasonable time)
In short, there is no one general answer.
- Brian
Chris Abele
Guest
Mon Feb 15, 2010 3:45 pm
On 2/15/2010 4:35 AM, Jonathan Bromley wrote:
Quote:
On Sun, 14 Feb 2010 20:32:19 -0800 (PST), "chaitanyakurmala_at_gmail.com"
chaitanyakurmala_at_gmail.com> wrote:
hi all,
lets say there is a system in which there are N -inputs and 1 -
output. lets say N-100 or 1000 etc.
if we want to test it completely we have to give all 2 power N inputs
and examine the functionality which will take more time and impossible
as N goes high.
so my question is how many no of optimum inputs one should give to
test the functionality of such system.
This is a fascinating academic problem that has been addressed
in many ways over the years.
In a seminal study by Marker and Proff [1] it was shown that
at least one solution exists that will globally maximise the
Grade function [2]. Unfortunately, this function must be
uniquely recalculated for each problem, and is also time-
varying, so the existence of a theoretically achievable
maximum is unhelpful in practice.
An alternative heuristic method, which seems to have been
first used by Slacker and Goodtime [3] in their investigation
of alcohol tolerance in the female population, involves
the application of random inputs. However, this approach
is not guaranteed to find a global maximum of the Grade
function and can exhibit instability, causing the solution
to oscillate around a local minimum instead.
From a practical point of view there appear to be three
productive approaches. The first, and least satisfactory,
is to apply the "envelope" cost function of Wonga and
Moolah [$400]. Although they achieved some success in
their original study, time variability of the Grade
function and its sensitivity to the Ethix constraint [5]
have given it a reputation for lack of repeatability.
The second, originally due to Quitter, is to sidestep the
problem entirely by application of the Corse Transformation -
I'm sorry I don't have a reference for that, but you
should be able to find information in any good Social
Studies library. Finally there is Plagia's method of
duplication [7, 8, 9, 10 et al], which has been used
successfully on innumerable studies.
References:
[1] Marker and Proff: "On the minimization of student
interference in real work", J.Edu.Obfusc. 1953
[2] Grade, A: "A new assessment function", J..zzzzz....
--
Jonathan Bromley
Most illuminating. It brightened my morning to see such an erudite
practitioner sharing his knowledge.
Chris
glen herrmannsfeldt
Guest
Mon Feb 15, 2010 11:44 pm
Brian Drummond <brian_drummond_at_btconnect.com> wrote:
Quote:
On Sun, 14 Feb 2010 20:32:19 -0800 (PST), "chaitanyakurmala_at_gmail.com"
chaitanyakurmala_at_gmail.com> wrote:
lets say there is a system in which there are N -inputs and 1 -
output. lets say N-100 or 1000 etc.
(snip)
Quote:
Glenn's answer is good, but I'd add:
- it is best achieved with intimate knowledge of the system under test
(but not necessarily so intimate that the tester shares the designer's
blind spots!)
That was the point I was (trying to) make: That the best test method
is system specific.
Quote:
- don't stop at just one test strategy (e.g. testing one bit at a time
with all others '0') See "Hubble Telescope" for a failure to consider
this...
That was a specific example for the case of all XOR gates. I believe
it is right for that case, but not for a large number of other cases.
For an actual example of failure to test appropriately, I once used
a system that had some signed comparators. It seesm that no test was
done with values of different sign. It gave the right result comparing
postiive number to positive numbers, and negative numbers to negative
numbers, but not mixed. But that was in the design. I was thinking
in this case the problem was to detect fabrication errors.
Quote:
- Consider and test for pathological cases - e.g. where an internal
counter carries into the next highest bit or rolls over to 0
With the (not necessarily true) assumption that each logic device
is independent, you must test for all the combinations for each device.
For the 'rolls over to zero' case, there is another one to verify.
That is, that the logic gives the right results at the desired
clock rate. It might be, for example, that the counter is too slow
in the roll over case, but does eventually give the right result.
Quote:
- test one count either side of such problem areas as well
- as the problem case itself - sometimes a problem has been
- hidden by a quick fix!
You do have to know the logic very well, but yes. There are, for
example, counters that make the roll over case decision one clock
cycle earlier. (That is, pipeline the roll over.)
Quote:
- make at least one test deliberately fail, to prove that
- a "pass" doesn't mean that reports have been accidentally
- turned off!
I was assuming we were talking about test vectors for fabricated chips.
That might have been an unwarrented assumption, though.
Quote:
- "constrained random" testing may find errors you didn't
- consider above.
In the days of punched cards, one test for compilers was to feed
it cards from the recycle bin. That is, random wrong, but not
too wrong, statements.
Quote:
- some designs CAN be exhaustively tested in a reasonable time.
A 24-bit square root unit can, a 24-bit multiplier (48 inputs)
- cannot (for a suitable definition of reasonable time)
And, as Intel knows, floating point dividers also can't be
exhaustively checked, even at the design level.
-- glen
