I have been playing around with analysis of circuits and am trying to generate test vectors. In order to exercise the circuit in the manner I require, I need a vector that includes every change in the circuit's inputs where only 1 input toggles, but in order to be efficient, it must include each change only once and must not include any changes where more than one input toggles. Inputs can be only logic high (1) or low (0). If these sequences don't already have a name I would like to call them Majella tuples.
I believe the length of these Majella tuples to be ((2^n) * n) + 1 where n is the width of the input in bits.
for example (with all 0 starting patterns):
n = 1:
0 1 0
n = 2:
00 10 11 01 11 10 00 01 00
n = 3:
000 100 110 010 110 111 011 001 101 001 011 111 101 111 110 100 101 100 000 010 011 010 000 001 000
I have written a bit of code to brute force generate these codes. However, it starts to struggle at n = 5 (actual code in a prev. revision of this question).
FUNCTION gen IF height of stack == ((2^bit_width) * bit_width) PRINT ZERO_PATTERN RETURN TRUE IF the change between the value at the top of stack and value does occur between other values on the stack RETURN FALSE PUSH value to stack WHILE shift < bit_width IF RECURSE with value as (value XOR (1 << shift)) returns TRUE PRINT value RETURN TRUE shift = shift + 1 RETURN FALSE SET stack to an empty list SET bit_width to n CALL gen with value as 0
I would guess that there are solutions for all every possible n (positive integers). If there is a solution for n, there must be at least n! solutions as swapping the order of the inputs does not invalidate the solution. Reversing the order of a solution also does not invalidate it.
In each solution each input pattern should be present n times (except the starting pattern, that is present n + 1 times). The start and end patterns will always be the same.
Unfortunately this is where my knowledge runs out.
Is there a more efficient way of producing a valid solution given n as an input?
Can it be (easily) proven that there are solutions for all values of n?
I think it can be viewed as a graph:
n = 2 n = 3 000 00 / | \ / \ / | \ 01 10 100 010 001 \ / | \/ \/ | 11 | /\ /\ | 110 101 011 \ | / \ | / 111
The sequence is required to traverse each edge in both directions, but in neither direction more than once.