Finding minimal and complete test sets for circuits

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 wh

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.

StackExchange Computer Science Q#62666, answer score: 3