detecteur de parité ou assimilé

Lesquels choisir ? Comment les utiliser ?

Postby iso14000 » Mon Feb 25, 2013 12:00 am

salut à todos , voilà le topo

je suis en train de faire un petit générateur pseudo aléatoire avec un tiny15 (un monstre!) en assembleur.

je me suis choisi une méthode : LFSR linear feedback shift register.
le registre est sur 8 bits. Le polynome est x8+x6+x5+x4+x0
pour vite et court, je ne veux pas faire 7 décalages et 5 xor.

il y a une super instruction de manipulation de bit (sans le e, hein! on est pas des cochons) qui permet en deux cycles de transférer un bit d'un registre vers un bit d'un autre registre.

appliquer au même registre ça permet de judicieusement déplacer la valeur de x0 vers x7.
je me retrouve alors avec 5 bits contigües sur un registre dont il faut faire le xor entre eux : s'il y a un nombre pair de 1 le résultat est nul sinon c'est 1

question : comment faire?

A vous
tant qu'un auteur sera aussi un modérateur ici (et donc plaignant et juge) je serais un Troll assumé
iso14000
 
Posts: 3083
Joined: Fri Jan 03, 2014 1:55 pm

Postby ymasquel » Wed Feb 27, 2013 12:00 am

Bonjour Florent,

La solution la plus simple pour tester si un nombre de bits d'un octet est pair ou impair est encore la méthode "bêtem" (bête et méchante).

Initialiser à zéro un compteur puis utiliser en séquence les instructions de test de bit sur chaque bit de l'octet et incrémenter le compteur pour chaque bit ON. En fin de séquence tester le bit de poids faible du compteur qui est ON si le nombre de bits est impair.

Cela coûte 2 instructions par bit testé donc très peu coûteux en cycles machine et sans boucle.

Amicalement, Yves.
Amicalement,
Yves.
ymasquel
Site Admin
 
Posts: 3387
Joined: Thu Jan 02, 2014 10:44 am
Location: Oise (60)

Postby jjm » Wed Feb 27, 2013 12:00 am

Bonjour,

5 bits, ça ne fait que 32 possibilités : pourquoi pas une table pré-calculée (nbre de bits à 1 dans les nombres de 0 à 31 ) ?

En pseudo-C code, ça ferait (si val est ton registre avec qqchose
dans les bits de 7 à 3) un truc du style:

static char pre_xor[32]={ 0,1,1,0, ... , 1 }; /* 0,1,2,3 ... 31 */
resultat = pre_xor[val>>3];

En assembleur, 'lpm' permet d'aller chercher des valeurs dans une
table indexée par 'Z'. Tu devrais pouvoir avoir un résultat en quelques cycles.

JJ
jjm
 
Posts: 4
Joined: Fri Jan 17, 2014 4:43 pm

Postby iso14000 » Wed Feb 27, 2013 12:00 am

salut vous deux et merci de vos réponses.

Ce qui me rassure c'est que bien que n'ayant plus fait d'assembleur depuis un lustre j'ai pu m'y remettre sans trois de CC sur les neurones.

en fait j'avais effectivement pensé à ces deux méthodes : la force brute et la table de lookup (merci l'instruction lpm des tiny ... c'est trop bien)

alors à la demande générale voici ma soluce.

et d'une je me suis poutré dans le polynome c'est X^4 que je dois déplacer

alors voici le code.

mov Scratch,LFSR
bst Scratch,3;T<=Scratch(bit #3)
bldScratch,6;Scratch(bit #6)<=T know all bits are together
clr Scratch2;scratch2 count one's in LFSR copy so let's reset it.
rolScratch
brcc BIT7 ;test 1st bit
incScratch2
BIT7:
rolScratch
brcc BIT6 ;test 2st bit
incScratch2
BIT6:
rolScratch
brcc BIT5;test 3rd bit
incScratch2
BIT5:
rolScratch;test 4th bit
brcc THATSALL
incScratch2
THATSALL:
rorScratch2
brccCARRY_CLEAR;is the ones's bit counter odd?
sbi PORTB,OUTRANDOM ;yes set output
rjmp CARRY_CLEAR+1
CARRY_CLEAR:
cbiPORTB,OUTRANDOM;no clear output
rolLFSR

reti

décidément j'aime bien l'assembleur d'atmel après avoir tant souffert sur pic!

merci A++
tant qu'un auteur sera aussi un modérateur ici (et donc plaignant et juge) je serais un Troll assumé
iso14000
 
Posts: 3083
Joined: Fri Jan 03, 2014 1:55 pm

Postby ymasquel » Wed Feb 27, 2013 12:00 am

Bonjour Florent,

Pas besoin de passer par le bit d'overflow, on passe simplement le BYTE dans un registre pour profiter du test de BIT et BRANCHEMENT et le compteur dans un second registre :

bld Scratch,6 ;Scratch(bit #6)<=T Now all bits are together
LD R30, Scratch6
LDI R31,0
SBRC R30,7
INC R31
SBRC R30,6
INC R31
SBRC R30,5
INC R31
SBRC R30,4
INC R31
SBRC R31,0;is the ones's bit counter odd?
sbi PORTB,OUTRANDOM ;yes set output
rjmp CARRY_CLEAR+1
CARRY_CLEAR:
cbi PORTB,OUTRANDOM ;no clear output

C'est juste la partie de test dans ton contexte auquel je ne touche pas. Evidemment il faut une paire de registres libres.

Amicalement, Yves.
Amicalement,
Yves.
ymasquel
Site Admin
 
Posts: 3387
Joined: Thu Jan 02, 2014 10:44 am
Location: Oise (60)


Return to Microcontrôleurs & microprocesseurs

Who is online

Users browsing this forum: No registered users and 1 guest