decode_bch.c

BCH编码与译码程序

#include"stdio.h";

//#include"BCH_var.h"
//#include "../h files/BCH_var.h"
#include "E:\EBS\BCNEN0404\verify_BCH\extern_BCH_var.h"

/*_______________________________________________________
		
函数名：	decode_BCH
功能：		BCH(31,16)与BCH（31，21）解码
作者：		DengBing
初始创建日期：	20060320
最后修改日期：	
_______________________________________________________*/
short decode_bch( short *recd,short cor_number)
/*
 * Simon Rockliff's implementation of Berlekamp's algorithm.
 *
 * Assume we have received bits in recd[i], i=0..(n-1).
 *
 * Compute the 2*t syndromes by substituting alpha^i into rec(X) and
 * evaluating, storing the syndromes in s[i], i=1..2t (leave s[0] zero) .
 * Then we use the Berlekamp algorithm to find the error location polynomial
 * elp[i].
 *
 * If the degree of the elp is >t, then we cannot correct all the errors, and
 * we have detected an uncorrectable error pattern. We output the information
 * bits uncorrected.
 *
 * If the degree of elp is <=t, we substitute alpha^i , i=1..n into the elp
 * to get the roots, hence the inverse roots, the error location numbers.
 * This step is usually called "Chien's search".
 *
 * If the number of errors located is not equal the degree of the elp, then
 * the decoder assumes that there are more than t errors and cannot correct
 * them, only detect them. We output the information bits uncorrected.
 */
{
	
	int n, length,t;
    int	i, j, u, q, t2, count = 0, syn_error = 0;
	int elp[20][20],l[20],u_lu[20],s[20],d[20];
	int root[20], loc[20], reg[20];  //err[102],*/ 
	short flag;
	flag = 0;

  //k=8,
    t=cor_number,length=31,n=31;
//	m=5;
	t2 = 2 * t;
	
	

	/* first form the syndromes */
//	printf("S(x) = ");
	for (i = 1; i <= t2; i++) {
		s[i] = 0;
		for (j = 0; j < length; j++)
			if (recd[j] != 0)
				s[i] = (s[i] ^falpha[(i * j) % n]); //dengbing modify the content 2006-4-4.
		if (s[i] != 0)
			syn_error = 1; /* set error flag if non-zero syndrome */
/*
 * Note:    If the code is used only for ERROR DETECTION, then
 *          exit program here indicating the presence of errors.
 */
		/* convert syndrome from polynomial form to index form  */
		s[i] = findex[s[i]];
//		printf("%3d ", s[i]);
	}
//	printf("\n");

	if (syn_error) {	  /* if there are errors, try to correct them */
		/*
		 * Compute the error location polynomial via the Berlekamp
		 * iterative algorithm. Following the terminology of Lin and
		 * Costello's book :   d[u] is the 'mu'th discrepancy, where
		 * u='mu'+1 and 'mu' (the Greek letter!) is the step number
		 * ranging from -1 to 2*t (see L&C),  l[u] is the degree of
		 * the elp at that step, and u_l[u] is the difference between
		 * the step number and the degree of the elp. 
		 */
		/* initialise table entries */
		d[0] = 0;			/* index form */
		d[1] = s[1];		/* index form */
		elp[0][0] = 0;		/* index form */
		elp[1][0] = 1;		/* polynomial form */
		for (i = 1; i < t2; i++) {
			elp[0][i] = -1;	/* index form */
			elp[1][i] = 0;	/* polynomial form */
		}
		l[0] = 0;
		l[1] = 0;
		u_lu[0] = -1;
		u_lu[1] = 0;
		u = 0;
 
		do {
			u++;
			if (d[u] == -1) {
				l[u + 1] = l[u];
				for (i = 0; i <= l[u]; i++) {
					elp[u + 1][i] = elp[u][i];
					elp[u][i] = findex[elp[u][i]];
				}
			} else
				/*
				 * search for words with greatest u_lu[q] for
				 * which d[q]!=0 
				 */
			{
				q = u - 1;
				while ((d[q] == -1) && (q > 0))
					q--;
				/* have found first non-zero d[q]  */
				if (q > 0) {
				  j = q;
				  do {
				    j--;
				    if ((d[j] != -1) && (u_lu[q] < u_lu[j]))
				      q = j;
				  } while (j > 0);
				}
 
				/*
				 * have now found q such that d[u]!=0 and
				 * u_lu[q] is maximum 
				 */
				/* store degree of new elp polynomial */
				if (l[u] > l[q] + u - q)
					l[u + 1] = l[u];
				else
					l[u + 1] = l[q] + u - q;
 
				/* form new elp(x) */
				for (i = 0; i < t2; i++)
					elp[u + 1][i] = 0;
				for (i = 0; i <= l[q]; i++)
					if (elp[q][i] != -1)
						elp[u + 1][i + u - q] = 
                                   falpha[(d[u] + n - d[q] + elp[q][i]) % n];
				for (i = 0; i <= l[u]; i++) {
					elp[u + 1][i] = (elp[u + 1][i]^elp[u][i]);  //dengbing modify the content 2006-4-4.
					elp[u][i] = findex[elp[u][i]];
				}
			}
			u_lu[u + 1] = u - l[u + 1];
 
			/* form (u+1)th discrepancy */
			if (u < t2) {	
			/* no discrepancy computed on last iteration */
			  if (s[u + 1] != -1)
			    d[u + 1] = falpha[s[u + 1]];
			  else
			    d[u + 1] = 0;
			    for (i = 1; i <= l[u + 1]; i++)
			      if ((s[u + 1 - i] != -1) && (elp[u + 1][i] != 0))
			        d[u + 1] = d[u + 1]^(falpha[(s[u + 1 - i] 
			                      + findex[elp[u + 1][i]]) % n]); //dengbing for modify the content 2006-4-5.
			  /* put d[u+1] into index form */
			  d[u+1] = findex[d[u + 1]];	
			}
		} while ((u < t2) && (l[u + 1] <= t));
 
		u++;
		if (l[u] <= t) {/* Can correct errors */
			/* put elp into index form */
			for (i = 0; i <= l[u]; i++)
				elp[u][i] = findex[elp[u][i]];

//			printf("sigma(x) = ");
//			for (i = 0; i <= l[u]; i++)
//				printf("%3d ", elp[u][i]);
//			printf("\n");
//			printf("Roots: ");

			/* Chien search: find roots of the error location polynomial */
			for (i = 1; i <= l[u]; i++)
				reg[i] = elp[u][i];
			count = 0;
			for (i = 1; i <= n; i++) {
				q = 1;
				for (j = 1; j <= l[u]; j++)
					if (reg[j] != -1) {
						reg[j] = (reg[j] + j) % n;
						q=(q^ falpha[reg[j]]);  //dengbing for modify the content .2006-4-5 .
					}
				if (!q) {	/* store root and error
						 * location number indices */
					root[count] = i;
					loc[count] = n - i;
					count++;
//					printf("%3d ", n - i);
				}
			}
//			printf("\n");
			if (count == l[u])
			{
			/* no. roots = degree of elp hence <= t errors */
				for (i = 0; i < l[u]; i++)
					recd[loc[i]]= (recd[loc[i]]^1);  //dengbing modify content2006-4-4.
			}
			else	/* elp has degree >t hence cannot solve */
			{
//				printf("Incomplete decoding: errors detected\n");
                //输出bfi标志信息
				flag = 1;
			}
		}
	else
		{//set bfi flag//输出bfi标志信息
		flag = 1;
		}
	}

	return flag;
}