Finding minimal and complete test sets for circuits

Question

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

some properties:

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?

edit:

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.

Answer 1

Yes. One can construct a Majella sequence of length $n \cdot 2^n + 1$, recursively. It's easy to see you can't do any better than this, so this is optimal.

Definition. I'll say that a sequence $x_0,x_1,\dots,x_m$ of $n$-bit values is a $n$-bit Majella sequence if $x_0=x_m$, and for each $y \in \{0,1\}^n$ and each value $e \in \{0,1\}^n$ with a single bit set, the pair $y,y\oplus e$ appears (consecutively) somewhere in the sequence.

Recursive construction. Let $w_0,w_1,\dots,w_m$ be a $n-1$-bit Majella sequence (for $n-1$-bit values). Consider the following sequence:

$$0w_0, 0w_1,\dots, 0w_{m-1}, 0w_m, 1w_m, 1w_{m-1}, \dots, 1w_1, 1w_0, 0w_0,$$

where $0w$ represents the concatenation of $0$ and $w$. This sequence is not yet a Majella sequence, but we can modify it to be one. In particular, for each value $w \in \{0,1\}^{n-1} \setminus \{w_0\}$, replace the first occurrence of $0w$ in the sequence with $0w,1w,0w$ (increasing the length of the sequence by 2).

After this modification, the result is a $n$-bit Majella sequence.

This construction is inspired by the standard recursive construction of a Gray code, but tweaked slightly to satisfy your particular requirements.

Length of the recursive construction. Let $L(n)$ be the length of the resulting sequence (i.e., the value of $m+1$). It satisfies the recurrence relation

$$L(n) = 2L(n-1) + 2^n - 1$$

with $L(1) = 3$. This solves to

$$L(n) = n \cdot 2^n + 1.$$

Algorithms. I don't know if there are any efficient, low-space algorithms for enumerating through such a sequence, like there are for Gray codes.