bch_decoder.c

bch encoder+decoder 源代码

/*******************************************************************************
*
*    File Name:  bch_decoder.c
*     Revision:  2.0
*         Date:  March, 2007
*        Email:  [e-mail]
*      Company:  Micron Technology, Inc.
*
*  Description:  Micron NAND BCH Decoder
*
*   References: 
* 		  1. Error Control Coding, Lin & Costello, 2nd Ed., 2004
* 		  2. Error Control Codes, Blahut, 1983
**
*   Disclaimer   This software code and all associated documentation, comments or other 
*  of Warranty:  information (collectively "Software") is provided "AS IS" without 
*                warranty of any kind. MICRON TECHNOLOGY, INC. ("MTI") EXPRESSLY 
*                DISCLAIMS ALL WARRANTIES EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED 
*                TO, NONINFRINGEMENT OF THIRD PARTY RIGHTS, AND ANY IMPLIED WARRANTIES 
*                OF MERCHANTABILITY OR FITNESS FOR ANY PARTICULAR PURPOSE. MTI DOES NOT 
*                WARRANT THAT THE SOFTWARE WILL MEET YOUR REQUIREMENTS, OR THAT THE 
*                OPERATION OF THE SOFTWARE WILL BE UNINTERRUPTED OR ERROR-FREE. 
*                FURTHERMORE, MTI DOES NOT MAKE ANY REPRESENTATIONS REGARDING THE USE OR 
*                THE RESULTS OF THE USE OF THE SOFTWARE IN TERMS OF ITS CORRECTNESS, 
*                ACCURACY, RELIABILITY, OR OTHERWISE. THE ENTIRE RISK ARISING OUT OF USE 
*                OR PERFORMANCE OF THE SOFTWARE REMAINS WITH YOU. IN NO EVENT SHALL MTI, 
*                ITS AFFILIATED COMPANIES OR THEIR SUPPLIERS BE LIABLE FOR ANY DIRECT, 
*                INDIRECT, CONSEQUENTIAL, INCIDENTAL, OR SPECIAL DAMAGES (INCLUDING, 
*                WITHOUT LIMITATION, DAMAGES FOR LOSS OF PROFITS, BUSINESS INTERRUPTION, 
*                OR LOSS OF INFORMATION) ARISING OUT OF YOUR USE OF OR INABILITY TO USE 
*                THE SOFTWARE, EVEN IF MTI HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH 
*                DAMAGES. Because some jurisdictions prohibit the exclusion or 
*                limitation of liability for consequential or incidental damages, the 
*                above limitation may not apply to you.
*
*                Copyright 2007 Micron Technology, Inc. All rights reserved.
*
* Rev  Author			Date		Changes
* ---  ---------------	----------	-------------------------------
* 1.0  ZS		08/07/2006	Initial release
* 2.0  PF		03/05/2007	Fixed bug that caused some codewords
* 					to not be corrected
* 
* 
/*******************************************************************************/

#include "BCH_Global.c"

int bb[rr_max] ;	// Syndrome polynomial
int s[rr_max];		// Syndrome values
int syn_error;		// Syndrome error indicator
int count;		// Number of errors
int location[tt_max];	// Error location
int ttx2;		// 2t
int decode_flag;	// Decoding indicator 
	
void parallel_syndrome() {
/* Parallel computation of 2t syndromes.
 * Use the same lookahead matrix T_G_R of parallel computation of parity check bits.
 * The incoming streams are fed into registers from left hand
 */
	int i, j, iii, Temp, bb_temp[rr_max] ;
	int loop_count ;

	// Determine the number of loops required for parallelism.  
	loop_count = ceil(nn_shorten / (double)Parallel) ;
	
	// Serial to parallel data conversion
	for (i = 0; i < Parallel; i++) 
		for (j = 0; j < loop_count; j++) 
			if (i + j * Parallel < nn_shorten)
				data_p[i][j] = recd[i + j * Parallel];
			else
				data_p[i][j] = 0;
	
	// Initialize the parity bits.
	for (i = 0; i < rr; i++)
		bb[i] = 0;
	
	// Compute syndrome polynomial: S(x) = C(x) mod g(x)
	// S(t) = T_G_R S(t-1) + R(t) 
	// Ref: L&C, pp. 225, Fig. 6.11
	for (iii = loop_count - 1; iii >= 0; iii--) {
		for (i = 0; i < rr; i++) {
			Temp = 0;
			for (j = 0; j < rr; j++) 
				if (bb[j] !=0 && T_G_R[i][j] != 0)
					Temp ^= 1 ;
			bb_temp[i] = Temp;
		}
		
		for (i = 0; i < rr; i++)
			bb[i] = bb_temp[i];
		
		for (i = 0; i < Parallel; i++)
			bb[i] = bb[i] ^ data_p[i][iii];
	}
	
	// Computation 2t syndromes based on S(x)
	// Odd syndromes
	syn_error = 0 ;
	for (i = 1; i <= ttx2 - 1; i = i+2) {
	 	s[i] = 0 ;
		for (j = 0; j < rr; j++)
			if (bb[j] != 0)
				s[i] ^= alpha_to[(index_of[bb[j]] + i*j) % nn] ;
		if (s[i] != 0)
			syn_error = 1 ;	// set flag if non-zero syndrome => error
    	}

	// Even syndrome = (Odd syndrome) ** 2
	for (i = 2; i <= ttx2; i = i + 2) {
	 	j = i / 2;
		if (s[j] == 0)
			s[i] = 0;
		else
			s[i] =  alpha_to[(2 * index_of[s[j]]) % nn];
	}
	
	if (Verbose) {
		fprintf(stdout, "# The syndrome from parallel decoder is:\n") ;
		for (i = 1; i <= ttx2; i++)
			fprintf(stdout, "   %4d (%4d) == 0x%04x (0x%x)\n", s[i],index_of[s[i]],s[i], index_of[s[i]]) ;
		fprintf(stdout, "\n\n") ;
	}
}

void decode_bch() {
	register int i, j, elp_sum ;
	int L[ttx2+3];			// Degree of ELP 
	int u_L[ttx2+3];		// Difference between step number and the degree of ELP
	int reg[tt+3];			// Register state
	int elp[ttx2+4][ttx2+4]; 	// Error locator polynomial (ELP)
	int desc[ttx2+4];		// Discrepancy 'mu'th discrepancy
	int u;				// u = 'mu' + 1 and u ranges from -1 to 2*t (see L&C)
	int q;				//

	parallel_syndrome() ;
	
	if (!syn_error) {
		decode_flag = 1 ;	// No errors
		count = 0 ;
	}
	else {	
		// Having errors, begin decoding procedure
		// Simplified Berlekamp-Massey Algorithm for Binary BCH codes
		// 	Ref: Blahut, pp.191, Chapter 7.6 
		// 	Ref: L&C, pp.212, Chapter 6.4
		//
		// Following the terminology of Lin and Costello's book:   
		// 	desc[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. 
		
		if (Verbose) fprintf(stdout,"Beginning Berlekamp loop\n");

		// initialise table entries
		for (i = 1; i <= ttx2; i++) 
			s[i] = index_of[s[i]];

		desc[0] = 0;				/* index form */
		desc[1] = s[1];				/* index form */
		elp[0][0] = 1;				/* polynomial form */
		elp[1][0] = 1;				/* polynomial form */
		//elp[2][0] = 1;				/* polynomial form */
		for (i = 1; i < ttx2; i++) {
			elp[0][i] = 0;			/* polynomial form */
			elp[1][i] = 0;			/* polynomial form */
			//elp[2][i] = 0;			/* polynomial form */
		}
		L[0] = 0;
		L[1] = 0;
		//L[2] = 0;
		u_L[0] = -1;
		u_L[1] = 0;
		//u_L[2] = 0;
		u = -1; 
 
		do {
			// even loops always produce no discrepany so they can be skipped
			u = u + 2; 
			if (Verbose) fprintf(stdout,"Loop %d:\n", u);
			if (Verbose) fprintf(stdout,"     desc[%d] = %x\n", u, desc[u]);
			if (desc[u] == -1) {
				L[u + 2] = L[u];
				for (i = 0; i <= L[u]; i++)
					elp[u + 2][i] = elp[u][i]; 
			}
			else {
				// search for words with greatest u_L[q] for which desc[q]!=0 
				q = u - 2;
				if (q<0) q=0;
				// Look for first non-zero desc[q] 
				while ((desc[q] == -1) && (q > 0))
					q=q-2;
				if (q < 0) q = 0;

				// Find q such that desc[u]!=0 and u_L[q] is maximum
				if (q > 0) {
					j = q;
				  	do {
				    		j=j-2;
						if (j < 0) j = 0;
				    		if ((desc[j] != -1) && (u_L[q] < u_L[j]))
				      			q = j;
				  	} while (j > 0);
				}
 
				// store degree of new elp polynomial
				if (L[u] > L[q] + u - q)
					L[u + 2] = L[u];
				else
					L[u + 2] = L[q] + u - q;
 
				// Form new elp(x)
				for (i = 0; i < ttx2; i++) 
					elp[u + 2][i] = 0;
				for (i = 0; i <= L[q]; i++) 
					if (elp[q][i] != 0)
						elp[u + 2][i + u - q] = alpha_to[(desc[u] + nn - desc[q] + index_of[elp[q][i]]) % nn];
				for (i = 0; i <= L[u]; i++) 
					elp[u + 2][i] ^= elp[u][i];

			}
			u_L[u + 2] = u+1 - L[u + 2];
 
			// Form (u+2)th discrepancy.  No discrepancy computed on last iteration 
			if (u < ttx2) {	
				if (s[u + 2] != -1)
					desc[u + 2] = alpha_to[s[u + 2]];
				else 
					desc[u + 2] = 0;

				for (i = 1; i <= L[u + 2]; i++) 
					if ((s[u + 2 - i] != -1) && (elp[u + 2][i] != 0))
			        		desc[u + 2] ^= alpha_to[(s[u + 2 - i] + index_of[elp[u + 2][i]]) % nn];
			 	// put desc[u+2] into index form 
				desc[u + 2] = index_of[desc[u + 2]];	

			}

			if (Verbose) {
				fprintf(stdout,"     deg(elp) = %2d --> elp(%2d):", L[u], u);
				for (i=0; i<=L[u]; i++)