finalprojectcommented.c

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

/*******************************************************************
 *                             	
 *	ECE 476 - Final Project - 5/5/04	
 *
 *	(31,16) BCH Triple Eroor Correcting Code.
 *			Version 9.0 - Final
 *
 *	Alexander Krol & Cezar Serban
 *
 */

#include <Mega32.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>		// For use of power function


/** Note: Must be compiled with "char is unsigned" **//

//** Variable Definitions **

//UserStateMachine states
enum {start, original, EncodeDecode, adderror, DisplayToggle, DetailToggle, help};

// Various vars for user input and command control with HyperTerm
unsigned char char_count, char_ready, cmd_str[8], cmd_ready;

//User State Machine state
unsigned char UserState;

// Message to be encoded/decoded (stored in flash due to its large size)
// Note - could easily be a 'stored' file that is to be transmitted
// Note the '\r' terminators at the end of the message
flash char Message[] = "This is the Message to be Encoded and Decoded with a (31,16) BCH Triple-Error Correcting Code.\r\r\r";

//Global Vars
unsigned long EncodedMessage=0;	// Encoded Message as a long
char EncMsgArray[32];			// Encoded Message in Array format
char n=31, k=16, t=3;			// BCH Code definitions
unsigned long GeneratorPoly = 36783;	// Generator Polynomial: 107657 in octal
char seed=0;				// Random seed for Error module
//Counters to keep track of errors for BER calculations
int trans_error_count=0,rec_error_count=0;
int enc_message_bits;


// Flags for Display and Error Module
bit detail_toggle=0, display_toggle=0, Add_Error=0;

// Struct for use in Berlekamp Decoding, allows for arrays of Poly32's
// Note that all GF32 arrays contain the POWERS of alpha as their data,
// not the actual GF32 element - hence multiplication is actually addition
struct Poly32
{
	char p[32];
};


// Define GF32 - ZERO as negative one since a zero would
// zero out various multiplications
#define ZERO -1

// Efficient lookup tables for GF32
// Alpha exponents - computed as powers of 2
// Where alpha is from the Galois Field(32)
flash char lookup[] = {
                1,  // a^0  = 0
                2,  // a^1  = 1
                4,  // a^2  = 2
                8,  // a^3  = 3
                16, // a^4  = 4
                5,  // a^5  = 2 0
                10, // a^6  = 3 1
                20, // a^7  = 4 2
                13, // a^8  = 3 2 0
                26, // a^9  = 4 3 1
                17, // a^10 = 4 0
                7,  // a^11 = 2 1 0
                14, // a^12 = 3 2 1
                28, // a^13 = 4  3 2
                29, // a^14 = 4 3 2 0
                31, // a^15 = 4 3 2 1 0
                27, // a^16 = 4 3 1 0
                19, // a^17 = 4  1 0
                3,  // a^18 = 1 0
                6,  // a^19 = 2 1
                12, // a^20 = 3 2
                24, // a^21 = 4 3
                21, // a^22 = 4 2 0
                15, // a^23 = 3 2 1 0
                30, // a^24 = 4 3 2 1
                25, // a^25 = 4 3 0
                23, // a^26 = 4 2 1 0
                11, // a^27 = 3 1 0
                22, // a^28 = 4 2 1
                9,  // a^29 = 3 0
                18, // a^30 = 4 1
                1   // a^31 = 0
            };

flash char reverseLookup[] = {
                ZERO, // a^0
                0,  // a^1
                1,  // a^2
                18, // a^3
                2,  // a^4
                5,  // a^5
                19, // a^6
                11, // a^7
                3,  // a^8
                29, // a^9
                6,  // a^10
                27, // a^11
                20, // a^12
                8,  // a^13
                12, // a^14
                23, // a^15
                4,  // a^16
                10, // a^17
                30, // a^18
                17, // a^19
                7,  // a^20
                22, // a^21
                28, // a^22
                26, // a^23
                21, // a^24
                25, // a^25
                9,  // a^26
                16, // a^27
                13, // a^28
                14, // a^29
                24, // a^30
                15  // a^31
            };

/** Function Prototypes **/
// Note: For GF2 unisgned longs can be used since only two elements
// in the field.  For GF32, byte arrays needed to be used since there
// are 32 elements.

// State machine definition for the user menu options
void UserStateMachine();

// Initialization function
void Initialize();

// Displays a helpmenu for command definitions
void HelpMenu();

// Initializes the UART interrupt and flags for reading commands
void get_cmd_init();

// Main Encoding/Decoding System
void System();

// All encoding for BCH ECC is done here - accepts 2 char message
void EncoderBCH(unsigned char a, unsigned char b);

// All encoding for BCH ECC is done here
void DecoderBCH();

/** Helper Functions **/

// Concatenates 2 chars into a long
unsigned long Concate(unsigned char num1, unsigned char num2);

// Finds the degree of a polynomial encoded as a long in GaloisField2
unsigned char GF2FindDegree(unsigned long a);

// Adds 2 polynomials encoded as a long - GF2
unsigned long GF2Add(unsigned long a, unsigned long b);

// Polynomial Multiplication for longs in GF2
unsigned long GF2Multiply(unsigned long a, unsigned long b);

// Polynomial Division for longs in GF2
void GF2Divide(unsigned long a, unsigned long b, unsigned long *qr);

// Polynomial Modulo for longs in GF2
unsigned long GF2Mod(unsigned long a, unsigned long b);

// Retrieves a specified bit from a long
unsigned char getBit(unsigned long r, char i);

// Converts a long into a 32 length byte array
void Bits2Bytes(unsigned long num, char *p);

// Initializes GF32 arrays to ZERO
void GF32Init(char *p);

// Prints an Array byte by byte
void PrintArray(char *p);

// Prints an array in GF32 polynomial format
void GF32PrintArray(char *p);

// Adds two alpha coefficients in GF32
char GF32add2alpha(char a, char b);

// Finds the degree of a GF32 polynomial
char GF32FindDegree(char *p);

// Evaluates the result of a GF32 Polynomial for some x
char GF32Evaluate(char a, char *p);

// Adds all alpha coefficients pairwise in 2 Arrays in GF32
void GF32Add(char *a, char *b, struct Poly32 *powers);

// Polynomial Multiplication for longs in GF32
void GF32Multiply(char *a, char *b, struct Poly32 *mul);

// Multiplies a GF32 polynomial with some power of x
void multiplyX(char x_power, char *p, struct Poly32 *ret);

// Multiplies a GF32 polynomial by a constant
void multiplyConstant(char c, char *p, struct Poly32 *ret);

// Corrects the detected errors in an encoded message
void CorrectErrors(char *p);

// Converts an array of bytes into a long
unsigned long Bytes2Bits(char *p);

// Parses the lower 16bits of a long into 2 chars
void deConcate(unsigned long a, unsigned char *ret);

// Prints a long as 4 chars
void PrintLong(unsigned long a);

// A random error module that corrupts an encoded message
void ErrorModule(char *p, char numerrors);


// The Entry point to the ECC unit
// Simply initializes and then runs the UserStateMachine forever
void main()
{
	Initialize();
	while (1)  
	{
		UserStateMachine();
	}
}

// The user interface: allows the user to select what it
// is he wants to do.
void UserStateMachine()
{
	char i, input;

	switch (UserState)
  	{   
		case start: 		// Inital State
			if (cmd_ready == 1)	// Check if a command has been entered
			{
				input = cmd_str[0];	// if so, grab it
				
				if ((input == 'O') || (input == 'o')) // Print out the original message
					UserState = original;
				else 
					get_cmd_init();			// Else, re-init for more user input
			    
				if ((input == 'N') || (input == 'n')) // Toggle Noise Module On/Off
				{
					UserState = adderror;
				 	get_cmd_init();			// Check for user-inputted random seed
				 	if (!Add_Error)			// only if module is being turned on
						printf("Enter Random Seed for Noise Module (1-9): ");
				}
				else 
					get_cmd_init();

				if ((input == 'R') || (input == 'r'))	// Start Encoding/Decoding
					UserState = EncodeDecode;
				else
					get_cmd_init();

				if ((input == 'G') || (input == 'g'))	// Main Display Toggle
					UserState = DisplayToggle;		// Displays only partial info
				else
					get_cmd_init();

				if ((input == 'D') || (input == 'd'))	// Detailed Display Toggle
					UserState = DetailToggle;		// Can only be activated if Main
				else							// Display is on
					get_cmd_init();

				if ((input == '?'))				// User Help Menu
					UserState = help;
				else
					get_cmd_init();					
			}
		break;

		case original:	// Print original message
			i=0;
			printf("\r\n--Original Message: ");
			while (Message[i] != '\r')	// Simply run trhough message until terminator
			{					// is reached
				printf("%c",Message[i]);
				i++;			
			}
			printf("\r\n");
			get_cmd_init();			// Re-init command input
			UserState = start;		// and go back to initial state
		break;
			
		case EncodeDecode:			// Run Encoder/Decoder System
			printf("\r\n--Encoding/Decoding of Message: ");
			System();				// Run the system
	  		get_cmd_init();
	  		UserState = help;  		// Display Help Menu before
		break;					// going back to initial state
			
		case adderror:		// Error Module Toggle
			if (Add_Error)	// If it's on, turn it off
			{
				 Add_Error=0;
				 printf("--Noise Module is OFF\r\n");
				 get_cmd_init();
				 UserState = start;
			}
			
			if (cmd_ready == 1)	// Otherwise, turn it on and grab
			{				// the user-inputted seed
				seed = cmd_str[0]-48;
				Add_Error = 1;
				printf("--Noise Module is ON: Seed %d\r\n", seed);
				get_cmd_init(); 				
				UserState = start;
			}
		break;			

		// Note that display toggles are used, since so much is displayed
		// to HyperTerm, that the speed of encoding/decoding is comprimised
		// and it is difficult to interpret the whole message

		case DisplayToggle:		// Main Display toggle
			display_toggle ^= 1;	// Switch it on and off with XOR
			if (display_toggle)
				printf("--Display is ON\r\n");
			else
				printf("--Display is OFF\r\n");
			get_cmd_init(); 				
			UserState = start;
		break;
			
		case DetailToggle:		// Detailed Display Toggle
			if (display_toggle)	// Can only be activated if
			{				// Main Display is ON
				detail_toggle ^= 1;	// Switch it On/Off
				if (detail_toggle)
					printf("--Detailed Display is ON\r\n");
				else
					printf("--Detailed Display is OFF\r\n");
			}
			else
				printf("--Display is NOT on\r\n");
			get_cmd_init(); 				
			UserState = start;
		break;
			
		case help:	// Simply displays the help menu
		    HelpMenu();
		    get_cmd_init();   
		    UserState = start;
		break;
  	}
}

//**Initialize**
//Sets up vars, timers, and Mega32 registers
void Initialize()
{
	//Initialize the USART registers
	UCSRB = 0x18; // enable RX/TX interrupts
	UBRRL = 103;  // baud rate = 9600

	//Initialize the state variables
	UserState = start;

	n=31; k=16; t=3;	// Initialize BCH Code parameters to (31,16)
	EncodedMessage=0;
	GeneratorPoly = 36783; // Init the Generator polynomial
	
	// Initialize the toggles and the random seed to No Errors
	display_toggle=0;
	detail_toggle=0;
	Add_Error=0;
	seed=0;

	// Initialize the Error Counters for BER
	trans_error_count=0;
	rec_error_count=0;		
	enc_message_bits=0;		// The # of bits in the Full encoded msg
	
	get_cmd_init(); //start the RXC interrupt for keypad input.
	HelpMenu(); // Run the help menu for User cmds
	
	// Fire up the ISR's
	#asm
		sei
	#endasm
}

//**Encode/Decode System**
// High level system for the encoding and decoding operations for
// the entire message to be transmitted
void System()
{ 	
	unsigned char out[2], a, b;
	unsigned int CurrIndex = 0;	// Keeps track of where we are in the Message
	unsigned long decoded_bits;	// Final decoded message of 2 chars

	a = Message[CurrIndex];	// Initialize the first 2 chars to be encoded
	b = Message[CurrIndex+1];

	while ((a != '\r') && (b != '\r'))	// Loop throught the message until terminator chars are reached
	{
		if (display_toggle)	// In general, only disply if display toggles are ON
		{
			printf("\r\n========================================================================");
			printf("\r\nOriginal Message: %c %c\r\n", a, b);
		}
		EncoderBCH(a,b);	// Run the encoder on the first 2 chars of Message
		DecoderBCH();	// and Decoded the resulting encoded message
		decoded_bits = Bytes2Bits(EncMsgArray);
		deConcate(decoded_bits, out);	// Parse out the 2 chars


		if (display_toggle)
		{
			printf("\nCorrected Message Array:\r\n");
			PrintArray(EncMsgArray);
			printf("\r\nMessage: %c %c\r\n\n", out[0], out[1]);
		}
		else
			printf("%c %c ", out[0], out[1]);	// if no display toggle, just print decoded
									// message
	 	CurrIndex += 2;		// Increment to grab the next 2 chars to be Encoded/Decoded
		a = Message[CurrIndex];
		b = Message[CurrIndex+1];
		enc_message_bits += 31;		// Every iteration, 31 bits are encoded
	}
	printf("\r\n\nBER of Transmitted Message: %f", (float)trans_error_count/enc_message_bits);
	printf("\r\nBER of Recieved Message: %f\r\n", (float)rec_error_count/enc_message_bits);
}

//**16 bit Message Encoder**
// Grabs a 16 bit message, and encodes it according to the BCH algorithm
// with a specified generator polynomial
void EncoderBCH(unsigned char a, unsigned char b)
{
	char numerrors;	// Random number of errors to introduce into the message
				// from 0 - user selected seed
	// Calculates the number of errors
	numerrors = (char)(rand() * ((float)(seed+1)) / (RAND_MAX + 1.0));

	trans_error_count += numerrors;	// Internal counter to keep track of errors
	if (numerrors > 3)			// Errors in decoded message only for 4 or more
		rec_error_count += numerrors;

	// Systematic encoding as follows:
	// (m(x) * x^(n-k)) mod g(x) + (m(x) * x^(n-k))
	
	// Shift by x^(n-k) = x*15
	EncodedMessage = Concate(a, b);	// Concatenates the two chars to a 16bit message
	EncodedMessage = EncodedMessage << (n-k);	// Multiply by x^(n-k)
	
	EncodedMessage = GF2Add(GF2Mod(EncodedMessage, GeneratorPoly), EncodedMessage);

//	EncodedMessage ^= 0x20010008;	// Errors can be manually added to message for debugging
	
	GF32Init(EncMsgArray); // Initialize to ZERO's
	Bits2Bytes(EncodedMessage, EncMsgArray);	// Convert to a GF32 polynomial

	if (display_toggle)
	{
		printf("\nEncoded Message Array:\r\n");
		PrintArray(EncMsgArray);
	}
	
//	printf(" NumErrors: %d\r\n",numerrors);

	// Execute the Error Module only if it is activated	
	if (Add_Error)
	{
		if (display_toggle)
			printf("\nRandom Index Errors:  ");
		ErrorModule(EncMsgArray, numerrors);	// Execute it
		if (display_toggle)
		{
			printf("\r\n\nEncoded Message Array with %d Errors:\r\n", numerrors);
			PrintArray(EncMsgArray);
		}
	}
}

//** 32 bit BerleKamp Decoder for BCH Codes **
// Decodes an encoded 32 bit message, and corrects for any detected errors
// according to the Berlekamp algorithm. See the writeup for details.