Browse Prior Art Database

EFFICIENT SYNDROME COMPUTATION FOR BINARY BCH CODES

IP.com Disclosure Number: IPCOM000006546D
Original Publication Date: 1992-Aug-01
Included in the Prior Art Database: 2002-Jan-14
Document File: 3 page(s) / 157K

Publishing Venue

Motorola

Related People

Jane Kellenberger: AUTHOR

Abstract

This paper presents an e&ient method of comput- ing the syndrome of a binary BCH code which takes advantage of the fact that consecutive integer powers of a' are needed in the syndrome computations and uses the post increment by N and module addressing capa- baities of the DSP56001 to perform the arithmetic over a Galois field. The method presented here is an improve- ment over the obvious implementation because it, in effect, performs the exponent multiplication, modulo checking, and element fetching all in one. step.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 38% of the total text.

Page 1 of 3

0 M

MOTOROLA INC. Technical Developments Volume 16 August 1992

EFFICIENT SYNDROME COMPUTATION FOR BINARY BCH CODES

by Jane Kellenberger

where n is the block length and k is the number of infor- mation bits. AU of the coefficients of g(x) and v(x) arc from the Galois Field GF(2), i.e. their value is either 1 or 0. An important property of g(x) and v(x) is that they have as their roots


d, a', al,. ., LIZ,

ABSTRACT

  This paper presents an e&ient method of comput- ing the syndrome of a binary BCH code which takes advantage of the fact that consecutive integer powers of a' are needed in the syndrome computations and uses the post increment by N and module addressing capa- baities of the DSP56001 to perform the arithmetic over a Galois field. The method presented here is an improve- ment over the obvious implementation because it, in effect, performs the exponent multiplication, modulo checking, and element fetching all in one. step.

INTRODUCTION

  Error control coding is an important part of mod- em digital communication systems. By adding redun- dancy, encoding improves the reliability of a digital link. The redundant bits, called parity bits, allow errors intro- duced to the transmitted signal in the communication channel to be detected and corrected at the receiver. There are many classes of error correcting codes. One widely used class is the BCH codes. BCH codes are multiple error correcting, cyclic, block codes and pro- vide a large selection ofblock lengths, code rates, alpha- bet sizes, and error correcting capabilities. While BCH codes outperform all other block codes of the same block length for large block lengths, they have the disadvan- tage of requiring complex decoders. This paper describes an efficient means of performing one of the steps in the decoding of a BCH code, namely the step of computing the syndrome from the received code word. In particu- lar, this paper describes a method of efficient syndrome computation for binary BCH codes using the features ofthe DSP56001.

  The mathematics evolved in decoding a bi.BCH code is well documented and will only be described very briefly here. At the transmitter, the generator polyno- mial for an (n,k) code
g(x) = g"-a"" + + gtx + go
is used to generate the code word

V(X)=v"x"+...V,X+Va

94


where

          Si = r(d) ; 1 c i 5 2t. To reduce the amount of computation in calculating S: it is common practice to first divide r(x) by g(x).
r(x) = q(x) g(x) + b(x)
where q(x) is the quotient and b(x) is the remainder. b(x) will be equal to 0 if and only if v(x) is a valid code word. The syndrome components then become

Si = r(a;)

I;;@; g(a') + b(a')

        = bn-*a'"-*)' +. . .+ b@ + bza' + bo since g(x) has a' as a root. The number of computations is reduced since the order of b(x) is only n-k compared to the order of r(x) which is n. This division can be easily accomplished using the DSP56001 since the divi- sion requires only arithmetic over GF(2), i.e. module 2. The diiculty comes when substituting the a...