[sci.electronics] Pseudorandom number generators

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