finalprojectcommented.c

Schifra Reed-Solomon Error Correcting Code Library http://www.schifra.com Copyright (c) 2000-2007

void DecoderBCH()
{
	char i, j;
	char k=0;
	char delta[7];
	char Syndromes[32];
 	//Lambda is an array of 7 GF32 polynomials structs
	//Note: Lambda/T arrays can be small (i.e length 4) if rewrite multiply/divide, etc.
	struct Poly32 lambda[7];
	struct Poly32 T[7];
	struct Poly32 temp;

	GF32Init(Syndromes);
	// Create Syndrome Polynomial
	for (i=0; i<2*t; i++)
		Syndromes[i+1] = (char)GF32Evaluate(i+1, EncMsgArray);

	if (display_toggle & detail_toggle)
	{	
		printf("\nSyndromes:\r\n");
		GF32PrintArray(Syndromes);
	}
		
  	/* 1  - Initialization */
   	// add 1 to S(x) and initialize Berlekamp's Algorithm
	Syndromes[0] = 0;

	//Init Lambda[i] polynomials
	for (i=0; i<7; i++)
		for (j=0; j<32; j++)
		{
			lambda[i].p[j]=ZERO;
			T[i].p[j]=ZERO;
		}

	// lambda_0 (x) = 1
	lambda[0].p[0] = 0;
    	// T_0 (x) = 1
    	T[0].p[0] = 0;
	
	while( k < t )
	{
      /* Berlekamp Algorithm */

	  /* 2 */    // Delta[2k] = coeff. of x^(2k+1) in the product Lambda[2k](x) * [1 + Syn(x)]
			 GF32Multiply(lambda[2*k].p, Syndromes, &temp);
			 delta[2*k]  = (char)temp.p[2*k+1];
			   
	  /* 3 */ 	 // Lambda[2k+2](x) = Lambda[2k](x) + Delta[2k]*(x*T[2k](x))
			 multiplyX(1, T[2*k].p, &temp);
			 multiplyConstant(delta[2*k], temp.p, &temp);
			 GF32Add(lambda[2*k].p, temp.p, &lambda[2*k+2]);
          
	  /* 4 */     
			 if (delta[2*k] == ZERO || (char)GF32FindDegree(lambda[2*k].p) > k)
				multiplyX(2, T[2*k].p, &T[2*k+2]);
			 else
			 {
				multiplyX(1, lambda[2*k].p, &temp);
				multiplyConstant((char)(31-delta[2*k]), temp.p, &T[2*k+2]);
			 }

			 if (display_toggle & detail_toggle)
			 {
		 	 	printf("\nDelta2k: %d\r\n",delta[2*k]);
			 	printf("\nLambda2k+2:\r\n");
			 	GF32PrintArray(lambda[2*k+2].p);
			 	printf("\nT2k+2:\r\n");
			 	GF32PrintArray(T[2*k+2].p);
			  }
			 
	  /* 5 */     k++; // Increment for next iteration
        }
	
	  CorrectErrors(lambda[2*k].p);	// Correct the errors as determined by the locator
}							// Lambda polynomial

//** Concatenate **//
// Concatenates two 8bit numbers into a 16bit message
// Since it's a (31,16) code
unsigned long Concate(unsigned char num1, unsigned char num2)
{
	unsigned long temp=0;
	
	temp = temp | num1;	// Or in the num1 and shift it up
	temp = temp << 8;
 	temp = temp | num2;	// Or in num2
	
	return temp;
}

//** Find Degree of a Polynomial in GF2 **//
// Simply finds the first index of a 32bit number that is not zero
// And that is the degree+1 of the polynomial
unsigned char GF2FindDegree(unsigned long num)
{
	char i=0;
	
	num = num << 1;	// Shift left since top bit is ignored in algorithm
	for(i=0; i<30; i++)
	{
		if (num & 0x80000000)	// Mask the current top bit, to see if it's a one
			return (30-i);	// if so, that's the degree
		num = num << 1;		// otherwise, keep shifting
	}
}

//** Polynomial Addition in GF2 **//
// Simply executes Modulo 2 addition
unsigned long GF2Add(unsigned long a, unsigned long b)
{
        return (a^b);	// simply xor the bits (GF2 addition for polynomials)
}

//** Polynomial Multiplication in GF2 **//
// Executes Multiplication in GF2 for polynomials
unsigned long GF2Multiply(unsigned long a, unsigned long b)
{
    unsigned long mul = 0;
    unsigned long add;
        
	char i;
	
	add = b;
		
 	for(i=0; i <= GF2FindDegree(a); i++) // loop while not to the end of the poly
	{
		if(getBit(a, i) == 1)		// If coeff. is a one, then add multiplicand
			mul ^= add;
		add = add<<1;			// and shift the multiplicand up one
  	}

    return mul;
}

//** Polynomial Long Division in GF2 **//
// Executes Long Division in GF2 for polynomials
// The remainder (qr[1]) is equal to the final dividend (qr[0])
// Degree of qr[1] should be smaller than degree of divisor (the break condition in the loop)
void GF2Divide(unsigned long a, unsigned long b, unsigned long *qr)
{
	unsigned long dividend;
	unsigned long divisor;

	unsigned long q;
 	int deg = 0;

	dividend = a;
	divisor = b;
	qr[0] = 0;
		
	while(1)	// Keep doing this until break is activated
	{
		// Subtract degrees to find what the degree of each term in the quotient
		deg = (int)(GF2FindDegree(dividend) - (int)GF2FindDegree(divisor));

		if (deg < 0) 	// If negative, then you are done
		{
			qr[1] = dividend;		// return the dividend as the remainder
			return ;
		}

		if (deg > 0)	// otherwise find the appropriate degree for the term
			q = (unsigned long)pow((float)2,(float)deg)+1;
		else
			q = 1;
		qr[0] = GF2Add(qr[0], q);	// and add the term to the quotient
		// finally, reduce (i.e add mod 2) the divided by (term*divisor)
		dividend = GF2Add(dividend, (GF2Multiply(q, divisor)));
	}
	qr[1] = dividend;		// Return the remainder
}

//** Polynomial Modulo in GF2 **//
// Simply executes GF2Divide to find remainder of two polynomials
unsigned long GF2Mod(unsigned long a, unsigned long b)
{
	unsigned long qr[2] = {0,0};
	GF2Divide(a, b, &qr[0]);
	return qr[1];
}

//** Get a bit from a Long **//
// Returns the bit i of the long r
unsigned char getBit(unsigned long r, char i)
{
        unsigned char ret;
	  
	  // Shifts and Masks to get the appropriate bit
        ret = ((r<<(32-i-1))>>31)& 0x00000001;
        return ret;
}

//** Long to Array convertor **//
// Takes a polynomial in GF2 (long) and coverts it into a polynomial in
// GF32 (a byte array)
void Bits2Bytes(unsigned long num, char *p)
{
	char i=0, temp=0;
	
 	for(i=0; i<32; i++)
	{
		temp = num % 2;
		if (temp == 0)
			p[i] = ZERO;	// -1 is ZERO, i.e. coeff = 0
		else
			p[i] = 0;		// alpha**0, i.e. coeff = 1
		num = num >> 1;		// shift for next iteration
	}
}
 
//** GF32 Initialize **//
// Simply initializes a GF32 array to all ZERO's
void GF32Init(char *p)
{
	 char i=0;
	 
	 for (i=0; i<32; i++)
		 p[i]=ZERO;
}

//** GF32 Initialize **//
// Prints a 32-element array
void PrintArray(char *p)
{
	char i=0;
	
	for(i=0; i<32; i++)
	{
		if (i%8 == 0) printf("  ");	// Space every 8 elements for clarity
		if (p[31-i] == ZERO)	// i.e. if ZERO, print 0
			printf("%d ", 0);
		else
			printf("%d ", 1);	// otherwise it's a one
	}
	printf("\r\n");
}

//** GF32 Polynomial Print **//
// Prints a 32-element array as a formatted GF32 polynomial
void GF32PrintArray(char *p)
{
	char i=0;
	char alpha=224;	// Ascii definition for alpha
	
	for(i=0; i<32; i++)
	{
		if (p[31-i] != ZERO)	// I.e. print as polynomial with coeff. in GF32
			printf("%c^%d*x^%d + ", alpha, p[31-i], 31-i);	// 0 is alpha**0 = 1
	}										// -1 is coeff = ZERO
	printf("0\r\n"); // to make the last '+' term be sensical
}

//** Add Two Alpha Coeff. in GF32 **//
// Uses the precomputed lookup tables to add powers of alpha mod 32
char GF32add2alpha(char a, char b) 
{
        if ((a == ZERO) && (b == ZERO))	// ZERO+ZERO=ZERO
            return ZERO;
        if (a == ZERO)				// ZERO is additive identity
            return b;
        else if (b == ZERO)
            return a;
        else					// Simply XOR and use lookup
            return reverseLookup[lookup[a]^lookup[b]];
}
 
//** Find Degree of GF32 Polynomial **//
// Returns the index of the first non-ZERO element
char GF32FindDegree(char *p)
{
        char i = 32;
        while(--i > 0)
            if (p[i] != ZERO) return i;
        return 0;
}

//** GF32 Polynomial Evaluation **//
// Evaluates the result of a polynomial defined over GF32 evaluated
// with an element from GF32
char GF32Evaluate(char a, char *p)
{
	char ret = ZERO, i=0;
	char pow=0;

      for(i=0; i <= GF32FindDegree(p); i++) // evaluate over the length of the polynomial
	{
          if (p[i] != ZERO)
	    {
                pow = (char)((p[i]+a*i) % 31); // index is the degree, multiply exponents
                if (pow < 0)
                	pow = (char)(31+pow); // Evaluate mod 32
                ret = GF32add2alpha(ret, pow);	// exponent multiplication = add
            }
        }
        return ret;
 }
 
//** GF32 Add Two Polynomials **//
// Adds two GF32 polys using the lookup tables for each pairwise coeff.
void GF32Add(char *a, char *b, struct Poly32 *powers)
{
	char i=0;

        for (i=0; i < 32; i++)
            powers->p[i] = GF32add2alpha(b[i], a[i]);
}

//** GF32 Polynomial Multiplication **//
// Multiplies two GF32 polynomials and returns the result by reference.
void GF32Multiply(char *a, char *b, struct Poly32 *mul)
{
	struct Poly32 add;
	char i,j;
	
	for(i=0; i<32; i++)	// Initialize the arrays
	{
		mul->p[i]=ZERO;
		add.p[i]=ZERO;
	}

      for(i=0; i <= GF32FindDegree(a); i++)
	{
          if(a[i] != ZERO )	// multiply only non-zero terms
	    {
            for(j=0; j <= GF32FindDegree(b); j++) // add then shift
		{
                    if(b[j] != ZERO)
                        add.p[j+i] = (char)((a[i]+b[j]) % 31);
            }
            GF32Add(mul->p, add.p, mul);
            GF32Init(add.p);
          }
      }
}

//** Multiply GF32 Polynomial by x^power **//
// Simply executes a cyclic shift (mod 32) by the power of x
void multiplyX(char x_power, char *p, struct Poly32 *ret)
{
	char i;

        for(i=0; i<32; i++)
            ret->p[(i+x_power) % 32] = p[i];	// cyclic shift mod 32
}
 
//** Multiply GF32 Polynomial by Constant **//
// Simply multiplies each coeff. by an element from GF32, mod 32
void multiplyConstant(char c, char *p, struct Poly32 *ret)
{
	 char i;
	 
      // if multiplying by zero, return zero
      if(c == ZERO)
	{	
		GF32Init(ret->p);
		return ;
	}

      for (i = 0; i < 32; i++)
	{
            if(p[i] != ZERO )
                ret->p[i] = (char)((p[i]+c) % 31); // add the constant exponent, mod 32
            else
                ret->p[i] = ZERO;
      }
}

//** Correct the Errors in the Encoded Message **//
// Corrects the encoded message according to the errors detected by the locator
// polynomial, Lambda which is passed as p - i.e. the roots of Lambda
// are the locations of the errors
void CorrectErrors(char *p)
{
	char i;

	// evaluate roots of lambda[2*k] and flip the received code word bits accordingly
	for(i=0; i<32; i++)
	{
     		if (GF32Evaluate(i, p) == ZERO )	// Find the roots of Lambda
	  	{
       		if (display_toggle)
	       		printf("\r\nError at index: %d\r\n", (31-i));
         		if (EncMsgArray[31-i] == ZERO)	// Simply flip the bits
         			EncMsgArray[31-i] = (char)0;
         		else
         			EncMsgArray[31-i] = ZERO;
     		}
   	}
}

//** Convert GF32 polynomial (array) to a GF2 polynomial (long) **//
// Simply Or-in the appropriate bits, and shift up
unsigned long Bytes2Bits(char *p)
{
	char i;
	unsigned long ret=0;
	
	for(i=0; i<31; i++)
	{
		ret = ret | (p[31-i] == 0); // if 0, or in a 1, if ZERO, or in a 0
		ret = ret << 1;	// and then shift it up
	}
	ret = ret | (p[0] == 0);	// shift up the last one - since only 31 elements
	
	return ret;
}

//** De-Concatenate **//
// Returns the bottom 16 bits of a long as 2 chars
void deConcate(unsigned long a, unsigned char *ret)
{
	a = a << 1;
	ret[0] = (unsigned char)((a & 0xFF000000) >> 24);
	ret[1] = (unsigned char)((a & 0x00FF0000) >> 16);
}


//** User Help menu **//
// Displays help menu options for User, while taking into
// account the appropriate status toggles
void HelpMenu()
{
	printf("\r\n\n-=- Help Menu -=-\r\n\n");
	if (Add_Error)
		printf("--Noise Module is ON: Seed %d\r\n", seed);
	if (display_toggle & detail_toggle)
		printf("--Detailed Display is ON\r\n");
	if (display_toggle)
		printf("--Display is ON\r\n\n");
	else
		printf("\n");
	printf("(O)utput Original Message to the Screen.\r\n");
	printf("(R)un Encode/Decode and Display.\r\n");
	printf("(G)eneral Display - Toggle On/Off.\r\n");
	printf("(N)oise Module - Toggle On/Off.\r\n");	
	printf("(D)etailed Display of Intermediate Steps - Toggle On/Off.\r\n");
	printf("(?)Display Help Menu.\r\n\n");
}

//** Get Command Initialize **//
// Initializes the UART for recieving a command from the user
void get_cmd_init()
{
	char_count = 0;
	char_ready = 0;
	UCSRB.7 = 1;
	cmd_ready = 0;
}

//** Print a long as 4 chars **//
// For use with Hyperterm, since it cannot display longs
void PrintLong(unsigned long a)
{
	unsigned char b,c,d,e;

	b = (unsigned char)((a & 0xFF000000) >> 24)+50;
	c = (unsigned char)((a & 0x00FF0000) >> 16)+50;
	d = (unsigned char)((a & 0x0000FF00) >> 8)+50;	
	e = (unsigned char)((a & 0x000000FF))+50;
	printf("%c%c%c%c\r\n",b,c,d,e);
}

//** Random Noise Module **//
// Generates a random number of errors in random locations in the 
// encoded message. Essentially simulates a variably noisy channel over
// which the encoded message would be transmitted.
void ErrorModule(char *p, char numerrors)
{
	char i, val;
	for (i=1; i<=numerrors; i++)	// NumErrors is random and seeded by the user
	{
		val = (int)(rand() * (32.0) / (RAND_MAX + 1.0)) + 1; 	//random integer in 1-32 range
		if (display_toggle)
			printf("%d ", val-1);
		if (p[val-1] == ZERO)	// Flip the appropriate bits
			p[val-1] = 0;
		else
			p[val-1] = ZERO;
	}
}

//** UART Recieve Interrupt **//
// Captures the serial keyboard input from the user via the UART
interrupt[USART_RXC] void UARTReceive()
{
	char c;
	c = UDR;
	UDR = c;

	if(c != '\r')
		cmd_str[char_count++] = c;
	else
	{
		putchar('\n');
		cmd_str[char_count] = 0;
		cmd_ready = 1;
		UCSRB.7 = 0;
	}
}