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");
}