Trouver des ensembles de test minimaux et complets pour les circuits

Question

J'ai joué avec l'analyse des circuits et j'essaie de générer des vecteurs de test. Afin d'exercer le circuit de la manière dont j'en ai besoin, j'ai besoin d'un vecteur qui comprend chaque modification des entrées du circuit où seulement 1 entrée baisse, mais pour être efficace, il doit inclure chaque modification une seule fois et ne doit inclure aucune modification où plus d'une entrée baisse. Les entrées ne peuvent être que la logique élevée (1) ou bas (0). Si ces séquences n'ont pas déjà de nom, je voudrais les appeler Majella Tuples.

Je crois que la longueur de ces tuples Majella doit être ((2 ^ n) * n) + 1 où n est la largeur de l'entrée en bits.

Par exemple (avec tous les 0 modèles de départ):

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

J'ai écrit un peu de code pour génèrent ces codes. Cependant, il commence à lutter à n = 5 (code réel dans une révision de précédente de cette 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

Quelques propriétés:

Je suppose qu'il existe des solutions pour tous les N possibles (entiers positifs). S'il y a une solution pour n, il doit y avoir au moins n! Les solutions comme échangeant l'ordre des entrées n'invalident pas la solution. L'inversion de l'ordre d'une solution ne l'invalide pas non plus.

Dans chaque solution, chaque modèle d'entrée doit être présent n fois (sauf le modèle de départ, qui est présent n + 1 fois). Les modèles de début et de fin seront toujours les mêmes.

Malheureusement, c'est là que mes connaissances s'épuisent.

Existe-t-il un moyen plus efficace de produire une solution valide étant donné n comme entrée?

Peut-il être (facilement) prouvé qu'il existe des solutions pour toutes les valeurs de n?

Éditer:

Je pense qu'il peut être considéré comme un graphique:

   n = 2                   n = 3

                             000
    00                      / | \
   /  \                    /  |  \
  01  10                100  010  001
   \  /                  | \/   \/ |
    11                   | /\   /\ |
                        110  101  011
                           \  |  /
                            \ | /
                             111

La séquence est nécessaire pour traverser chaque bord dans les deux directions, mais dans aucune des directions plus d'une fois.