From: sardella@strfleet.gsfc.nasa.gov (Thomas E. Sardella)
Subject: Re: BCH code help seeked
Followup-To: comp.protocols.misc
Organization: NASA/Goddard Space Flight Center/Code 532
Date: Tue, 6 Oct 1992 21:41:29 GMT

In article <1992Oct6.133559.15329@seas.gwu.edu>, lai@seas.gwu.edu (William
Y. Lai) wrote:
> 
> I am tasked to implement the following BCH code:
> 
> Block length: 63
> Data Length : 56
> Generator Polynomial:  x^7 + x^6 + x^2 + 1
> 
> The closest one I can find in Lin & Costello is a (n=63, k=57, t=1) code.
> Can anyone help?  It has been years since I took my coding class, and I
> am embarass to admit I don't remember very much... :-(
> 
> Also, is there any efficient method in implementing the encoding/decoding
> of BCH codes, or any cyclic does in general (given a correct generator
> polynomial is located) ?  Is there any Table Look-Up algorithm like those
> used with CRC-32?  Any pointers, algorithms, and codes is greatly
> apprecitaed!
> 
> Regards,
> 
> William Lai
> -- 
> email: lai@seas.gwu.edu | "I want to do everything.  I want to have everything.
> Dept. of Electrical Eng.|  I have a wonderful, wonderful life.  But there's so
> George Washington Univ. |  much more out there.  Do I have it all?  Yes.  Do I
> Washington, D.C.        |  want more?  Yeah, sure."     -Demi Moore        


We implemented a BCH decoding algorithm in "C" for CCSDS Spacecraft command
data.  I'll have to check further to see if we have an encoding algorithm. 
The parameters look exactly the same as what you're asking for (same
polynomial, 56 data bits, 7 check bits).  You wouldn't happen to be doing
something similar with CCSDS, would you?

Here's the code we used.  It uses a table lookup.  I'm not familiar with it
myself, but can get you help if you need it.


     Tom Sardella
     NASA/Goddard Space Flight Center/Code 532.2
     Greenbelt, MD
     sardella@strfleet.gsfc.nasa.gov


(Included code)


unsigned char ccsds_poly[] =  { 
                              0x00, 0x8A, 0x9E, 0x14, 0xB6, 0x3C, 0x28,
                              0xA2, 0xE6, 0x6C, 0x78, 0xF2, 0x50, 0xDA,
                              0xCE, 0x44, 0x46, 0xCC, 0xD8, 0x52, 0xF0,
                              0x7A, 0x6E, 0xE4, 0xA0, 0x2A, 0x3E, 0xB4,
                              0x16, 0x9C, 0x88, 0x02, 0x8C, 0x06, 0x12,
                              0x98, 0x3A, 0xB0, 0xA4, 0x2E, 0x6A, 0xE0,
                              0xF4, 0x7E, 0xDC, 0x56, 0x42, 0xC8, 0xCA,
                              0x40, 0x54, 0xDE, 0x7C, 0xF6, 0xE2, 0x68,
                              0x2C, 0xA6, 0xB2, 0x38, 0x9A, 0x10, 0x04,
                              0x8E, 0x92, 0x18, 0x0C, 0x86, 0x24, 0xAE,
                              0xBA, 0x30, 0x74, 0xFE, 0xEA, 0x60, 0xC2,
                              0x48, 0x5C, 0xD6, 0xD4, 0x5E, 0x4A, 0xC0,
                              0x62, 0xE8, 0xFC, 0x76, 0x32, 0xB8, 0xAC,
                              0x26, 0x84, 0x0E, 0x1A, 0x90, 0x1E, 0x94,
                              0x80, 0x0A, 0xA8, 0x22, 0x36, 0xBC, 0xF8,
                              0x72, 0x66, 0xEC, 0x4E, 0xC4, 0xD0, 0x5A,
                              0x58, 0xD2, 0xC6, 0x4C, 0xEE, 0x64, 0x70,
                              0xFA, 0xBE, 0x34, 0x20, 0xAA, 0x08, 0x82,
                              0x96, 0x1C, 0xAE, 0x24, 0x30, 0xBA, 0x18,
                              0x92, 0x86, 0x0C, 0x48, 0xC2, 0xD6, 0x5C,
                              0xFE, 0x74, 0x60, 0xEA, 0xE8, 0x62, 0x76,
                              0xFC, 0x5E, 0xD4, 0xC0, 0x4A, 0x0E, 0x84,
                              0x90, 0x1A, 0xB8, 0x32, 0x26, 0xAC, 0x22,
                              0xA8, 0xBC, 0x36, 0x94, 0x1E, 0x0A, 0x80,
                              0xC4, 0x4E, 0x5A, 0xD0, 0x72, 0xF8, 0xEC,
                              0x66, 0x64, 0xEE, 0xFA, 0x70, 0xD2, 0x58,
                              0x4C, 0xC6, 0x82, 0x08, 0x1C, 0x96, 0x34,
                              0xBE, 0xAA, 0x20, 0x3C, 0xB6, 0xA2, 0x28,
                              0x8A, 0x00, 0x14, 0x9E, 0xDA, 0x50, 0x44,
                              0xCE, 0x6C, 0xE6, 0xF2, 0x78, 0x7A, 0xF0,
                              0xE4, 0x6E, 0xCC, 0x46, 0x52, 0xD8, 0x9C,
                              0x16, 0x02, 0x88, 0x2A, 0xA0, 0xB4, 0x3E,
                              0xB0, 0x3A, 0x2E, 0xA4, 0x06, 0x8C, 0x98,
                              0x12, 0x56, 0xDC, 0xC8, 0x42, 0xE0, 0x6A,
                              0x7E, 0xF4, 0xF6, 0x7C, 0x68, 0xE2, 0x40,
                              0xCA, 0xDE, 0x54, 0x10, 0x9A, 0x8E, 0x04,
                              0xA6, 0x2C, 0x38, 0xB2 
                              };



int check_bch( codeblock, BCH_error )

unsigned char  *codeblock;
int   *BCH_error;
                  
   {
   int old_bch;
   int            i;
   unsigned char  *tmp;
   char           *tptr;
   unsigned int   lookup;
   unsigned char  a1,a2,r1;
   
   if (  ( *(int *)((int)codeblock - 8) == 0x55555555 ) && 
         ( *(int *)((int)codeblock - 4) == 0x55555555 )    )
      return( 1 );
   else
      {
      tmp = codeblock - 8;
      tptr = (char *)&ccsds_poly[0];
      old_bch = (int)*(tmp+7);
      *(tmp+7) = 0;
      lookup = 0;
      lookup = *tmp++;        /*    the most significant byte of the      
*/
      a1 = *tmp++;            /*    accumulator is your offset into the   
*/
      tptr = tptr + lookup;   /*    skip first byte of table (only xoring 
*/
                              /*    2 bytes at a time)                    
*/

      a1 = a1 ^ *tptr;
      a2 = a1;
      for (i = 1;i <= 6;++i)
         {
         tptr = (char *)&ccsds_poly[0]; /*point to beginning of lookup
table */
         lookup = a2;
         a1 = *tmp++;

         tptr = tptr + lookup ;  /*    skip first byte                    
*/
         r1 = *tptr;
         a2 = a1 ^ r1;
         }
      *BCH_error = (int)( ((a2 & 0x000000FE) ^ 0xFE) != old_bch );
      return( 0 );
      }
      
   }
Xref: sparky comp.protocols.misc:750 comp.protocols.ibm:756