Une règle de Golomb est une manière de placer des marques le long d'une ligne de telle manière que chaque paire de marques mesure une distance linéaire unique. Vous avez ici une règle de Golomb avec cinq marques :
| | | | |
0 1 4 9 11
Le nombre sous la marque est la distance depuis le bord gauche. La longueur de cette règle est 11 et elle semble être une des deux plus petites de ces règles à 5 cinq marques. L'autre règle possède des marques avec les positions 0, 3, 4, 9 et 11. (Les images miroir de ces deux règles 0, 2, 7, 10, 11 et 0, 2, 7, 8, 11 sont des règles de Golomb optimales. Habituellement, seul une des paires de chaque image miroir est mentionnée.)
Vous pouvez contrôler que les règles au-dessus soient des Golomb en écrivant une table de toutes les paires de marques et de leurs distances respectives :
Mark1 Mark2 Distance
----- ----- --------
0 1 1
0 4 4
0 9 9
0 11 11
1 4 3
1 9 8
1 11 10
4 9 5
4 11 7
9 11 2
Notez qu'il n'y a pas de distances dupliquée dans la troisième colonne. Il n'y a pas non plus de distance 6 mais c'est normal car les règles de Golomb n'ont pas à mesurer chaque distance, seulement des distances distinctes.
L'objectif de « l'optimisation » des règles de Golomb est de les obtenir aussi courtes que possibles, sans dupliquer les distances mesurées. Les deux règles à 5 marques au-dessus sont optimales.
Les règles de Golomb sont réellment caractérisées par leurs différences plutôt que par les distances absolues comme dans le diagramme ci-dessus. Les règles ci-dessus seraient donc 1-3-5-2 (elles sont quelques fois écrites comme 0-1-3-5-2 mais le zéro de départ est souvent enlevé).
Les règles à 21 marques les plus connues sont les suivantes :
2-22-32-21-5-1-12-34-15-35-7-9-60-10-20-8-3-14-19-4
James B. Shearer a compilé une liste de toutes les règles de Golomb les plus connues jusqu'à 150 marques. Si vous comparez les règles, vous vous apercevrez que les règles à 21 marques listées sur la page de James sont l'image mirroir des celle qui est au-dessus.
L'approche utilisée par le code de recherche OGR est celui d'un arbre transversal récursif qui est creusé. Ce qui suit est une description d'un arbre transversal exhaustif sans optimisations.
À chaque étage, une nouvelle marque est ajoutée à quelque distance de la fin de la règle. Si cette marque crée une duplication de distance mesurée, la marque est déplacée vers la droite d'une unité et est à nouveau contrôlée. Si la marque se déplace trop vers la droite, de telle manière qu'elle ne puisse pas correspondre aux autres marques dans les longueurs restantes (rappelez-vous que nous connaissons déjà la longueur des règles les plus connues), alors la recherche revient vers le niveau précédent. Si la marque nouvellement placée satisfait les obligations de Golomb, la recherche continue sur la marque suivante parmi la règle.
L'optimisation la plus importante est dans le placement de la marque « suivante ». Par le biais d'une manipulation habile de bitmaps représentant des tables de distances, nous n'avons pas besoin de réellement contrôler chaque nouvelle position de marque. Plutôt que les bitmaps nous indiquent où les nouvelles marques peuvent être placées qui satisfassent déjà les obligations de Golomb.
L'autre optimisation importante est la décision de considérer la règle courante comme trop longue ou non. En détectant que la règle ne peut faire partie des règles les plus courtes que celle déjà connues, nous pouvons éliminer beaucoup de recherche inutile.
Le processus de recherche pour une Règle de Golomb Optimale (Optimal Golomb Ruler) diffère de la recherche d'une clé de cryptage. La table suivante compare les aspects différents des deux programmes.
| Clé de Cryptage | Optimal Golomb Ruler |
|---|---|
| La clé est inconnue mais est connue pour exister. | Une règle des meilleure est déjà connue pour toute les longueurs. Il n'y a aucune garantie qu'une meilleure soit trouvée. |
| Chaque unité de travail, le key block, est un nombre fixé de clés. | Chaque unité de travail, le ruler stub, contient un nombre variable de « nodes » qui doivent être contrôlés. |
| Une clé de cryptage nécessite exactement le même nombre de cycles de CPU pour contrôler, à chaque fois. | Le compte de « node » OGR est le nombre d'étages de nodes encontrés dans l'arbre traversal. Le montant de cycles CPU par nodes n'est pas constant. |
| Un ordinateur donné contrôlera toujours le même nomnre de clé/s (en écartant les variations dues aux autres tâches que le CPU peut effectuer). | La performance de nombre de nodes/sec d'un ordinateur pourra varier légèrement en fonction du stub courant sur lequel on travaille. |
| L'espace des clés n'a seulement besoin d'être cherché que jusqu'à ce que la clé soit trouvée. Nous savons qu'il n'y a qu'une clé correcte. | L'espace de la règle doit être cherché complètement. Bien que nous pouvons trouver une règle de Golomb plus courte, il peut encore y en avoir une plus courte pas encore trouvée. |
| Il existe une prime financière pour trouver la bonne clé de cryptage. | Il n'y a (actuellement) aucun prix pour trouver un Optimal Golomb Ruler. |