Microprocessor based BCH decoder

Claim 1

An apparatus for decoding a stream of BCH encoded data, said apparatus comprising: a microprocessor for performing said decoding of said stream of said BCH encoded data; means for coupling the stream of BCH encoded data to said microprocessor; and means, coupled to said microprocessor, for converting M successive bits of the input data stream into N-bit finite field elements so that a syndrome representative of the serial stream of data may be calculated by said microprocessor utilizing the N-bit values, where M and N each represent positive integer numbers greater than 1.

Claim 2

An apparatus for decoding a stream of BCH encoded data, said apparatus comprising: a microprocessor for performing said decoding of said stream of said BCH encoded data; means for coupling the stream of BCH encoded data to said microprocessor; and means, coupled to said microprocessor, for converting M successive bits of the input data stream into N-bit finite field elements so that a syndrome representative of the serial stream of data may be calculated by said microprocessor utilizing the N-bit values, where M and N each represent positive integer numbers greater than 1.

Claim 10

A method of decoding a serially occurring stream of BCH encoded data, said method comprising the steps of: calculating syndrome for BCH encoded said data by converting M successive bits of the BCH encoded data stream into N-bit values and manipulating the N-bit values into a syndrome, where M and N represent positive integer numbers greater than 1; generating an inverse error location polynomial utilizing syndrome from said calculating step; detecting roots of the polynomial from said generating step; and inverting bits in the data stream which correspond to roots found in said detecting step.

Claim 11

A method of decoding a serially occurring stream of BCH encoded data, said method comprising the steps of: calculating syndrome for BCH encoded said data by converting M successive bits of the BCH encoded data stream into N-bit values and manipulating the N-bit values into a syndrome, where M and N represent positive integer numbers greater than 1; generating an inverse error location polynomial utilizing syndrome from said calculating step; detecting roots of the polynomial from said generating step; and inverting bits in the data stream which correspond to roots found in said detecting step.

Claim 16

An apparatus for decoding a serially occurring stream of BCH encoded data, said apparatus comprising: a microprocessor; means for coupling the stream of BCH encoded data to said microprocessor; means, coupled to said microprocessor, for converting M successive bits of the input data stream into N-bit values so that I/2 syndromes representative of the serial stream of data may be calculated by said microprocessor utilizing the N-bit values, where I, M, and N each represent positive integer numbers greater than 1; means, coupled to said microprocessor, for generating an inverse error location polynomial utilizing the syndrome, the inverse error location polynomial being characterized as representing a finite field sum of a plurality of products wherein each product represents a finite field multiplication of a coefficient by a variable raised to a power; means, coupled to said microprocessor, for finding roots of the polynomial; and a memory, coupled to said microprocessor, and partitioned into memory portions wherein: I/2 unique correction memory portions are each addressable by the M successive bits of the input data stream and each contains correction data items arranged so that the value of each correction data item equals a finite field addition of M field element products, where each of the M products represents the result of a finite field multiplication between one of the M successive bits of the input data stream and one of M predetermined field elements, and each of the correction memory portions is untilized by said microprocessor to generate one syndrome; a first conversion memory portion contains first conversion data items addressable by binary finite field elements stored therein so that each first conversion data item represents a power form of a binary finite field element which addresses the first conversion data item; a second conversion memory portion contains second conversion data items addressable by power form field elements stored therein so that each second conversion data item represents a binary field element corresponding to the power form field element which addresses the second conversion data item; and a plurality of coefficient memory portions are each addressable by a coefficient of the inverse error location polynomonial and are each programmed to contain coefficient data items which equal D×& i , where D represents the set of all possible coefficient values and i represents the power of the product for which a respective coefficient memory portion applies.

Claim 17

An apparatus for decoding a serially occurring stream of BCH encoded data, said apparatus comprising: a microprocessor; means for coupling the stream of BCH encoded data to said microprocessor; means, coupled to said microprocessor, for converting M successive bits of the input data stream into N-bit values so that I/2 syndromes representative of the serial stream of data may be calculated by said microprocessor utilizing the N-bit values, where I, M, and N each represent positive integer numbers greater than 1; means, coupled to said microprocessor, for generating an inverse error location polynomial utilizing the syndrome, the inverse error location polynomial being characterized as representing a finite field sum of a plurality of products wherein each product represents a finite field multiplication of a coefficient by a variable raised to a power; means, coupled to said microprocessor, for finding roots of the polynomial; and a memory, coupled to said microprocessor, and partitioned into memory portions wherein: I/2 unique correction memory portions are each addressable by the M successive bits of the input data stream and each contains correction data items arranged so that the value of each correction data item equals a finite field addition of M field element products, where each of the M products represents the result of a finite field multiplication between one of the M successive bits of the input data stream and one of M predetermined field elements, and each of the correction memory portions is untilized by said microprocessor to generate one syndrome; a first conversion memory portion contains first conversion data items addressable by binary finite field elements stored therein so that each first conversion data item represents a power form of a binary finite field element which addresses the first conversion data item; a second conversion memory portion contains second conversion data items addressable by power form field elements stored therein so that each second conversion data item represents a binary field element corresponding to the power form field element which addresses the second conversion data item; and a plurality of coefficient memory portions are each addressable by a coefficient of the inverse error location polynomonial and are each programmed to contain coefficient data items which equal D×& i , where D represents the set of all possible coefficient values and i represents the power of the product for which a respective coefficient memory portion applies.