grege@gold.gvg.tek.com (Greg Ebert) (04/02/91)
PRNG's can and should be designed to self-recover from the all-zeros "lockup state". All you do is splice-in another XOR gate. One input to the XOR gate is the most-significant bit (which is always used, anyway). The other input to the added XOR gate is the logical NOR of all bits EXCEPT the MSB. What happens is this: The terminal count is (for ALL PRNG's) all zeros except the last bit, which is a 1. The feedback term becomes zero, thus the next state is all zeros. The feedback term then becomes a 1, and the counter goes to 10000000... on the next cycle, etc. This also converts your counter into a 2**N state counter, instead of (2**N -1) states (yeah, who cares for a 32-bit counter :-] ) Here's a program I wrote to simulate PRNG's : - - - - - - - - Cut here - - - - - #include <stdio.h> main () { FILE *pnfile, *fopen(); int a[32],tap[33]; int size,steps,pstart,domatch,barf; int i,j,k,l; char yorn[],match[33]; printf("\nPseudorandom Number Generator Simulator, Rev 1.0"); if ((pnfile=fopen("png.res","w")) == NULL ) { printf("\n\n Can't open png.res for writing. Bye. \n"); exit (-1); } for (i=0;i<32;++i) { a[i] = 0; tap[i+1]=0; } a[0] = 1; printf("\n\nHow many bits ? "); scanf("%d",&size); printf("\nHow many simulation steps ? "); scanf("%d",&steps); printf("\nDo you want to find the state number of a specified pattern ? "); scanf("%s",yorn); if(yorn[0] != 'y' && yorn[0] != 'Y') { printf("\nStart printing at step number: "); scanf("%d",&pstart); } switch(size) { case 4: tap[3] = 1; tap[4] = 1; break; case 5: tap[3]=1; tap[5]=1; break; case 6: tap[5]=1; tap[6]=1; break; case 7: tap[6]=1; tap[7]=1; break; case 8: tap[4]=1; tap[5]=1; tap[6]=1; tap[8]=1; break; case 9: tap[5]=1; tap[9]=1; break; case 10: tap[7]=1; tap[10]=1; break; case 11: tap[9]=1; tap[11]=1; break; case 12: tap[6]=1; tap[8]=1; tap[11]=1; tap[12]=1; break; case 13: tap[9]=1; tap[11]=1; tap[12]=1; tap[13]=1; break; case 14: tap[4]=1; tap[8]=1; tap[13]=1; tap[14]=1; break; case 15: tap[14]=1; tap[15]=1; break; case 16: tap[4]=1; tap[13]=1; tap[15]=1; tap[16]=1; break; case 17: tap[14] = 1; tap[17] = 1; break; case 18: tap[11] = 1; tap[18] = 1; break; case 19: tap[14] = 1; tap[17] = 1; tap[18] = 1; tap[19] = 1; break; case 20: tap[17] = 1; tap[20] = 1; break; case 21: tap[19]=1; tap[21]=1; break; case 22: tap[21]=1; tap[22]=1; break; case 23: tap[18]=1; tap[23]=1; break; case 24: tap[17]=1; tap[22]=1; tap[23]=1; tap[24]=1; break; case 25: tap[22]=1; tap[25]=1; break; case 26: tap[20]=1; tap[24]=1; tap[25]=1; tap[26]=1; break; case 27: tap[22]=1; tap[25]=1; tap[26]=1; tap[27]=1; break; case 28: tap[25]=1; tap[28]=1; break; case 29: tap[27]=1; tap[29]=1; break; case 30: tap[7]=1; tap[28]=1; tap[29]=1; tap[30]=1; break; case 31: tap[28]=1; tap[31]=1; break; default: printf("\nDuhhh, I can't do that size!\n"); } fprintf(pnfile,"\n Results of %d bit PN counter\n\n",size); fprintf(pnfile,"XORs at bits:"); for(j=0;j<size;j++) { if(tap[j+1] == 1) fprintf(pnfile," %d",j); } fprintf(pnfile,"\n\n"); if(yorn[0] != 'y' && yorn[0] != 'Y') { for (i=0;i<=steps;++i) { if(i>= pstart) { fprintf(pnfile,"%4d ",i); if(i==pstart) printf("\nGenerating report\n"); for (j=0;j<size;j++) fprintf(pnfile,"%d",a[j]); fprintf(pnfile,"\n"); } k=0; for (j=0;j<size;++j) { k = k + a[j]*tap[j+1]; } for (j=size;j>1;j--) { a[j-1] = a[j-2]; } a[0] = k % 2; } } else /* Do the search */ { barf=1; while (barf==1) { printf("\nEnter the pattern you desire, beginning with the LSB."); printf("\nEnter an X for a dont-care.\n"); scanf("%s",match); if(strlen(match) == size) barf=0; else printf("\nWrong size. Enter EXACTLY %d characters.",size); } for (i=0;i<=steps;++i) { k=0; domatch=1; for (j=0;j<size;++j) { if(a[j] == 1 && match[j]=='0') domatch=0; if(a[j]==0 && match[j]=='1') domatch=0; } if (domatch==1) { fprintf(pnfile,"Match for state # %10d ",i); for (j=0;j<size;j++) fprintf(pnfile,"%d",a[j]); fprintf(pnfile,"\n"); } for (j=0;j<size;++j) { k = k + a[j]*tap[j+1]; } for (j=size;j>1;j--) { a[j-1] = a[j-2]; } a[0] = k % 2; } } fclose (pnfile); printf("\nResults are in png.res\n"); }