registre à décalage à rétroaction linéaire?
https://stackoverflow.com/questions/3735217
-
03-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Dernièrement je me suis cogné à plusieurs reprises dans le concept de LFSR, que je trouve très intéressant en raison de ses liens avec les différents domaines et aussi fascinant en soi. Il m'a fallu un certain effort pour comprendre, l'aide finale était-ce vraiment une bonne , beaucoup mieux que le (au début) cryptique wikipedia d'entrée. Donc, je voulais écrire un petit code pour un programme qui a fonctionné comme un LFSR. Pour être plus précis, qui a montré une certaine façon comment un LFSR fonctionne. Voici la chose la plus propre que je pouvais trouver après quelques tentatives de lenghtier (Python):
def lfsr(seed, taps):
sr, xor = seed, 0
while 1:
for t in taps:
xor += int(sr[t-1])
if xor%2 == 0.0:
xor = 0
else:
xor = 1
print xor
sr, xor = str(xor) + sr[:-1], 0
print sr
if sr == seed:
break
lfsr('11001001', (8,7,6,1)) #example
Je nommé « XOR » la sortie de la fonction XOR, pas très correct. Cependant, cela est seulement destiné à montrer comment les cercles à travers ses états possibles, en fait vous avez remarqué le registre est représenté par une chaîne. Pas cohérence bien logique.
Ceci peut être facilement transformé en un jouet agréable, vous pouvez regarder pendant des heures (au moins je pouvais: -)
def lfsr(seed, taps):
import time
sr, xor = seed, 0
while 1:
for t in taps:
xor += int(sr[t-1])
if xor%2 == 0.0:
xor = 0
else:
xor = 1
print xor
print
time.sleep(0.75)
sr, xor = str(xor) + sr[:-1], 0
print sr
print
time.sleep(0.75)
Alors il m'a frappé, à quoi est ce logiciel d'écriture? Je l'ai entendu peut générer des nombres aléatoires; est-ce vrai? Comment? Donc, ce serait bien si quelqu'un pouvait:
- expliquer comment utiliser un tel dispositif dans le développement de logiciels
- venir avec un code, pour soutenir le point au-dessus ou juste comme le mien pour montrer les différentes façons de le faire, dans toutes les langues
En outre, comme Theres pas de choses didactique autour de cette pièce de la logique et des circuits numériques, ce serait bien si cela pourrait être un endroit pour noobies (comme moi) pour obtenir une meilleure compréhension de ce chose , ou mieux, pour comprendre ce qu'il est et comment il peut être utile lorsque le logiciel d'écriture. Aurait fait un wiki communautaire?
Cela dit, si quelqu'un se sent comme le golf ... vous êtes les bienvenus.
La solution
En fait, des algorithmes basés sur LFSR sont très fréquents. CRC est en fait basé directement sur LFSR. Bien sûr, dans les cours de sciences informatiques les gens parlent de polynômes quand ils parlent de la façon dont la valeur d'entrée est censé être XORed avec la valeur accumulée dans l'ingénierie electornics on parle de robinets à la place. Ils sont la même terminologie juste différent.
CRC32 est très commun. Il est utilisé pour détecter les erreurs dans les trames Ethernet. Cela signifie que lorsque j'ai posté cette réponse mon PC utilisé un algorithme basé LFSR pour générer un hachage du paquet IP afin que mon routeur peut vérifier que ce transmission de c'est pas corrompu.
Zip et les fichiers Gzip sont un autre exemple. Les deux utilisent CRC pour la détection d'erreur. Zip et utilisations CRC32 Gzip utilise à la fois CRC16 et CRC32.
sont essentiellement des fonctions CRCs de hachage. Et il est assez bon pour faire le travail sur Internet. Ce qui signifie LFSRs sont assez bonnes fonctions de hachage. Je ne sais pas si vous le savez mais en bon fonctions de hachage général sont considérés comme bons générateurs de nombres aléatoires. Mais la chose avec LFSR est que la sélection des prises correctes (polynômes) est très important pour la qualité du hachage / nombre aléatoire.
Votre code est généralement le code de jouet car il fonctionne sur une chaîne de uns et de zéros. Dans le travail du monde réel LFSR sur les bits dans un octet. Chaque octet vous poussez à travers le LFSR change la valeur accumulée du registre. Cette valeur est effectivement une somme de contrôle de tous les octets que vous avez poussée à travers le registre. Deux façons habituelles d'utiliser cette valeur comme un nombre aléatoire consiste à utiliser un compteur et pousser une suite de nombres à travers le registre, transformant ainsi la séquence linéaire 1,2,3,4 certaine séquence hachée comme 15306,22,5587, 994, ou pour renvoyer la valeur actuelle dans le registre pour générer un nouveau numéro de séquence apparemment aléatoire.
Il convient de noter que ce faisant depuis peu naïvement à l'aide-tripoter LFSR est assez lent, vous devez bits de processus à la fois. Donc, les gens ont trouvé des moyens à l'aide de tables pré-calculées pour le faire huit bits à la fois ou même 32 bits à la fois. Voilà pourquoi vous voyez presque jamais le code LFSR dans la nature. Dans la plupart du code de production, il se déguise en quelque chose d'autre.
Mais parfois, un peu de LFSR-tripotant simple peut être utile. J'ai écrit un Modbus pilote pour un micro PIC et que le protocole utilisé CRC16. Une table précalculée nécessite 256 octets de mémoire et mon CPU n'avait 68 octets ( Je ne plaisante pas ). Donc, je devais utiliser un LFSR.
Autres conseils
Depuis que je cherchais un LFSR-implémentation en Python, je suis tombé sur ce sujet. Je trouve cependant que le suivant était un peu plus précis en fonction de mes besoins:
def lfsr(seed, mask):
result = seed
nbits = mask.bit_length()-1
while True:
result = (result << 1)
xor = result >> nbits
if xor != 0:
result ^= mask
yield xor, result
Ce qui précède LFSR-générateur est basé sur GF (2 k ) Module de calcul (GF = Galois ). Ayant tout juste de terminer un cours d'algèbre, je vais expliquer la façon mathématique.
Soit Commençons par la prise, par exemple, GF (2 4 ), ce qui équivaut à {a 4 x 4 + un 3 x 3 + a 2 x 2 + a 1 x 1 + a 0 x 0 | a 0 , a 1 , ..., a 4 ? Z 2 } (à préciser, Z < sub> n = {0,1, ..., n-1}, et donc Z 2 = {0,1}, soit un bit). Cela signifie que ceci est l'ensemble de tous les polynômes du quatrième degré avec tous les facteurs étant soit présent ou non, mais ne comportant pas des multiples de ces facteurs (par exemple, il n'y a pas 2x k ). x 3 , x 4 + x 3 , 1 et x 4 + x 3 + x 2 + x + 1 sont tous des exemples de membres de ce groupe.
Nous prenons cet ensemble module un polynôme du quatrième degré (par exemple, P (x) ? GF (2 4 )), par exemple P (x) = x 4 + x 1 + x 0 . Cette opération de module sur un groupe est également notée GF (2 4 ) / P (x). À titre de référence, P (x) décrit les 'robinets' dans le LFSR.
Nous avons également prendre un polynôme aléatoire de degré 3 ou moins (de sorte que ce n'est pas affecté par notre module, nous pourrions tout aussi bien sinon effectuer l'opération de module directement sur elle), par exemple A 0 (x) = x 0 . Maintenant, chaque ultérieur A i (x) est calculée en multipliant par x: A i (x) = A i-1 (x) * x mod P (x).
Puisque nous sommes dans un domaine limité, le fonctionnement du module peut avoir un effet, mais seulement lorsque le résultat A i (x) présente au moins un facteur x 4 (notre plus grand facteur de P (x)). Notez que, puisque nous travaillons avec des numéros dans Z 2 , effectuer l'opération de module lui-même est rien de plus que de déterminer si tout a i devient 0 ou 1 en ajoutant les deux les valeurs de P (x) et A i (x) conjointement (à savoir, 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0, ou 'XOR' ces deux).
Chaque polynôme peut être écrit comme un ensemble de bits, par exemple x 4 + x 1 + x 0 ~ A 10011. La 0 (x) peut être vu comme la graine. L'opération « fois x » peut être considéré comme un décalage à gauche opération. L'opération de module peut être considérée comme une opération de masquage de bit, avec le masque étant notre P (x).
L'algorithme décrit ci-dessus génère donc (un flux infini) valides quatre motifs de bits LFSR. Par exemple, pour notre définie A 0 (x) (x 0 ) et P (x) (x 4 + x 1 + x 0 ) , nous pouvons définir les suivants premier produit des résultats dans GF (2 4 ) (note que A 0 est pas produit jusqu'à ce que, à la fin du premier tour - mathématiques commencent généralement comptage à '1'):
i Ai(x) 'x⁴' bit pattern
0 0x³ + 0x² + 0x¹ + 1x⁰ 0 0001 (not yielded)
1 0x³ + 0x² + 1x¹ + 0x⁰ 0 0010
2 0x³ + 1x² + 0x¹ + 0x⁰ 0 0100
3 1x³ + 0x² + 0x¹ + 0x⁰ 0 1000
4 0x³ + 0x² + 1x¹ + 1x⁰ 1 0011 (first time we 'overflow')
5 0x³ + 1x² + 1x¹ + 0x⁰ 0 0110
6 1x³ + 1x² + 0x¹ + 0x⁰ 0 1100
7 1x³ + 0x² + 1x¹ + 1x⁰ 1 1011
8 0x³ + 1x² + 0x¹ + 1x⁰ 1 0101
9 1x³ + 0x² + 1x¹ + 0x⁰ 0 1010
10 0x³ + 1x² + 1x¹ + 1x⁰ 1 0111
11 1x³ + 1x² + 1x¹ + 0x⁰ 0 1110
12 1x³ + 1x² + 1x¹ + 1x⁰ 1 1111
13 1x³ + 1x² + 0x¹ + 1x⁰ 1 1101
14 1x³ + 0x² + 0x¹ + 1x⁰ 1 1001
15 0x³ + 0x² + 0x¹ + 1x⁰ 1 0001 (same as i=0)
Notez que votre masque doit contenir un « 1 » à la quatrième position pour vous assurer que votre LFSR génère des résultats de quatre bits. Notez également qu'un « 1 » doit être présent à la position zeroth pour vous assurer que votre bitstream ne pas se retrouver avec une configuration binaire 0000, ou que le dernier bit deviendrait non utilisée (si tous les bits sont décalés vers la gauche, vous aussi se retrouver avec un zéro dans la position 0e après un quart de travail).
ne sont pas tous P (x) 'est nécessairement sont générateurs de GF (2 k ) (et non tous les masques de k bits génèrent tous deux k-1 - 1 nombres). Par exemple, x 4 + x 3 + x 2 + x 1 + x 0 génère 3 groupes de 5 polynomals distincts chacun, ou "3 cycles de période 5": 0001,0010,0100,1000,1111; 0011,0110,1100,0111,1110; et 0101,1010,1011,1001,1101. Notez que 0000 ne peut jamais être généré, et ne peut pas générer un autre numéro.
Habituellement, la sortie d'un LFSR est le bit qui est « décalé » out, ce qui est un « 1 » si l'opération de module est réalisée, et un « 0 » quand il est pas. LFSR est avec une période de 2 k-1 -1, aussi appelé pseudo-bruit ou de PN-LFSR, adhèrent aux postulats de caractère aléatoire de Golomb, qui dit autant que ce bit de sortie est « assez » au hasard.
Séquences de ces bits ont donc leur utilisation dans la cryptographie, par exemple dans le A5 / 1 et A5 / 2 normes de cryptage mobiles, ou la norme Bluetooth E0. Cependant, ils ne sont pas aussi sûrs que l'on voudrait: algorithme Berlekamp-Massey peut être utilisé pour désosser la polynomal caractéristique (P (x)) du LFSR. normes de cryptage fort utilisent donc non linéaire FSR 's ou des fonctions non-linéaires similaires. Un sujet lié à ce sont les S-boîtes utilisé en AES.
Notez que je l'ai utilisé l'opération int.bit_length() . Cela n'a pas été mis en œuvre jusqu'à ce que Python 2.7.
Si vous souhaitez seulement comme un modèle binaire fini, vous pouvez vérifier si la graine est égale le résultat puis briser la boucle.
Vous pouvez utiliser mon LFSR méthode dans une boucle for (par exemple for xor, pattern in lfsr(0b001,0b10011)) ou vous pouvez appeler à plusieurs reprises l'opération de .next() sur le résultat de la méthode, un nouveau retour à chaque (xor, result) paire.
Il existe de nombreuses applications de LFSRs. L'un d'eux est générateur de bruit, par exemple, la SN76489 et variantes (utilisé sur le système maître, Game Gear, MegaDrive, NeoGeo Pocket, ...) utiliser un LFSR pour générer un bruit blanc / périodique. Il y a une description vraiment bien de son SN76489 LFSR dans cette page .
Pour le rendre vraiment élégant et Pythonic, essayez de créer un générateur, les valeurs successives yield-tion du LFSR. En outre, la comparaison à virgule flottante 0.0 est inutile et source de confusion.
Un LFSR est juste l'une des nombreuses façons de créer des nombres pseudo-aléatoires dans les ordinateurs. Pseudo-aléatoire, parce qu'il ya chiffres ne sont pas vraiment au hasard - vous pouvez facilement les répéter en commençant par la semence (valeur initiale) et procédure avec les mêmes opérations mathématiques.
Voici une variante de votre code en utilisant des entiers et binaire au lieu de chaînes. Il utilise également le rendement que quelqu'un a suggéré.
def lfsr2(seed, taps):
sr = seed
nbits = 8
while 1:
xor = 1
for t in taps:
if (sr & (1<<(t-1))) != 0:
xor ^= 1
sr = (xor << nbits-1) + (sr >> 1)
yield xor, sr
if sr == seed:
break
nbits = 8
for xor, sr in lfsr2(0b11001001, (8,7,6,1)):
print xor, bin(2**nbits+sr)[3:]
Si nous supposons que les semences est une liste de ints plutôt qu'une chaîne (ou le convertir si ce n'est pas) alors ce qui suit devrait faire ce que vous voulez avec un peu plus d'élégance:
def lfsr(seed, taps) :
while True:
nxt = sum([ seed[x] for x in taps]) % 2
yield nxt
seed = ([nxt] + seed)[:max(taps)+1]
Exemple:
for x in lfsr([1,0,1,1,1,0,1,0,0],[1,5,6]) :
print x
list_init=[1,0,1,1]
list_coeff=[1,1,0,0]
out=[]
for i in range(15):
list_init.append(sum([list_init[i]*list_coeff[i] for i in range(len(list_init))])%2)
out.append(list_init.pop(0))
print(out)
#https://www.rocq.inria.fr/secret/Anne.Canteaut/encyclopedia.pdf
