A BCH code can be used for correcting error bits in input data. The BCH code is used in satellite communication links, optical networks, and similar applications where error correction can be employed to mitigate the effects of noise interference. Such a code, however, requires complex encoding and decoding algorithms. In prior art, the complex encoding and decoding algorithms have been typically implemented using special-purpose devices.

An encoder produces a parity word (i. e. , redundancy information) from an input information word. The parity word together with the input information word form the codeword, which is transmitted to the destination through a communication channel. The notation for computing the parity word is based on calculating the remainder of the division of the input polynomial by a generator polynomial. Mathematically, this can be described as a"modulo operation"as follows: R (x) = f (x) xM mod g (x); (1) where R (x) is the reminder polynomial with degree M-1, f (x) is the input information polynomial with degree K-l, and g (x) is the. generator polynomial with degree M. The polynomials R (x), f (x), and g (x) are binary polynomials. The resulting codeword is of length N, where N=K+M.

The mathematics underlying the BCH encoding are known to those skilled in the art of error coding, and are described in detail in"Error Correcting Codes"by W. Wesley Peterson and E. J. Weldon Jr. , MIT 1972, pages 224-230 and 269-278.

Reference is now made to Fig. 1, which shows an exemplary diagram of a prior art BCH encoder 100. Encoder 100 is a serial implementation of the modulo operation, R (x) = f (x) xM mod g (x). Encoder 100 includes multipliers 110, shift registers 120, and exclusive-or (XOR) gates 130. The number of multipliers 110, shift registers 120, and XOR gates 130 is equal to the degree of the generator polynomial g (x). Each multiplier 110 includes an array of AND gates for a general serial encoder. In a practical case whereas the

generator polynomial is provided, each multiplier 110 is replaced by a direct connection if the polynomial generator's coefficient (i. e. gi) equals to one, and eliminated if it equals to zero. In order to calculate the reminder R (x), the polynomial f (x) that has an information word as its k polynomial's coefficient is shifted into encoder 100. high order first, until the last coefficient is shifted in. After a total of K shifts, encoder 100 outputs the entire quotient on its output, and the reminder R (x) is present in shift registers 120.

This approach, however, is not suitable for parallel input and output data. To overcome this problem, suitable codewords have also been generated by look-up table encoding schemes, which serve to map the K bits of the input information to M parity bits.

These M parity bits are then appended to the K bits of the input information to form a codeword uniquely associated with each input stream. Standard look-up table encoding, however, requires memory devices with 2K address locations. Such encoding schemes are thus impractical for medium length input words, and prohibitively complex and expensive when K is large.

In addition, implementation of an encoder circuit at high speeds is extremely difficult, mainly because the propagation delay of the combinational logic. The high rate encoders found in the art are usable only for data rates of up to 1 Giga bits per second (Gbps), while only relatively short codewords are employed. An example for such an encoder is provided in US Patent number 5,040, 179, entitled"High Rate BCH Encoder", to Carson Chen. The encoder suggested by Chen includes storage means (e. g. , read only memory (ROM) ) to hold a parity matrix derived from the BCH generator matrix (i. e. , the generator polynomial), a logical shift function, and a XOR gate tree. The parity matrix is of a number of rows equal to the codeword size N, and a number of columns equal to the number of parity bits M. Each clock, a column of the parity matrix is ANDed with the input bit, and the result is fed into the XOR gate tree. The XOR gate tree consolidates the N bits by combinational logic into a single bit, producing as an output a serial bit stream corresponding to the parity word of the codeword. After M clocks, the complete codeword is output. This encoder, however, uses a serial implementation, does not provide parallel output data other than through storage in a shift register, and it is not useful with long codewords. The address space required for ROM in such solutions is the code length multiplied by the redundancy length.

References relevant to prior art include US Patents Nos. 4,312, 069,4, 623,999, 5,040, 179 5,359, 610,5, 699,368 and 5,912, 905.

In view of the limitations of the conventional approaches to the handling of the BCH encoding problem, it is apparent that what is needed is an approach to encode any length BCH and similar codes at speeds that are limited by the redundancy length and not by the conventional memory limitations that correspond to the code length as described in some of the above references. Furthermore, there is a need to develop encoders capable of processing data for BCH encoding at rates of lOGbps and above, in particular for the purpose of supporting the new and upcoming speeds of OTNs.

SUMMARY OF THE INVENTION According to the present invention there is provided a high rate parallel encoder for encoding an error correction code and for producing redundancy information, comprising: a first adder operative to perform a first logical operation, a quotient computation logic (QCL) connected to the first adder and operative to estimate an intermediate quotient value, a remainder computation logic (RCL) coupled to the QCL and operative to calculate an intermediate reminder, a second adder coupled to the RCL and operative to perform a second logical operation and to output second adder bit values, and a register coupled to the second adder and the RCL and operative to store the calculated intermediate reminder, whereby the encoder is operative to encode a Bose-Chaudhuri-Hocquenghem error correcting code and to produce redundancy information.

According to the present invention there is provided a parallel encoder designed to reduce the propagation delay when encoding an error correction code, the encoder capable of producing redundancy information, the encoder comprising a first adder operative to perform a first logical operation, a quotient computation logic (QCL) connected to the first adder and operative to estimate an intermediate quotient value, a buffer connected to the QCL, a remainder computation logic (RCL) coupled to the buffer and operative to calculate an intermediate reminder, a second adder coupled to the RCL and operative to perform a second logical operation and to output second adder bit values, and a register coupled to the second adder and the RCL and operative to store the calculated reminder, whereby the encoder is operative to reduce the propagation delay when encoding a Bose-Chaudhuri-Hocquenghem error correcting code and to produce redundancy information. According to the present invention there is provided an optical network device for high-rate parallel encoding, comprising a first adder coupled to an input channel and configured to receive at least one input information block through the input channel, a quotient computation logic (QCL) connected to the first adder and capable of computing an intermediate quotient, a remainder computation logic (RCL) coupled to the QCL and capable of computing an intermediate reminder, a second adder coupled to the RCL and capable of performing logical exclusive OR (XOR) operations, and a register coupled to both the RCL the second adder and configured to output an encoded output information word to an output channel, whereby the optical network device is capable of producing redundancy information correlated with the at least one input information word.

According to the present invention there is provided a method for high. rate parallel encoding comprising the steps of receiving an input information word that includes a plurality of data words in a first adder, and, for each data word, performing a first logical operation in the first adder, estimating an intermediate quotient value in a quotient computation logic (QCL) connected to the first adder, calculating a intermediate reminder value in a remainder computation logic (RCL) coupled to the QCL, performing a second logical operation in a second adder coupled to the RCL, the second logical operation resulting in output second adder bit values, and storing the intermediate calculated reminder in a register coupled to the second adder and the RCL, whereby the method can be used to encode a Bose-Chaudhuri-Hocquenghem error correcting code and to produce redundancy information.

BRIEF DESCRIPTION OF THE DRAWINGS The invention is herein described, by way of example only, with reference to the accompanying drawings, wherein: Figure 1-is an exemplary diagram of serial implementation of a BCH encoder (prior art); Figure 2-is an exemplary block diagram of a BCH encoder in accordance with one embodiment of this invention ; Figure 3-is an exemplary flowchart describing the method for BCH encoding in accordance with one embodiment of this invention ; Figure 4-is a diagram of the matrix representations of g (x) and g-l (x); Figure 5-is a step-by-step example of the encoding method and the corresponding matrices G and G-i that represent the implementation of the multiplication by polynomials g (x) and g (x)-l ; Figure 6-is an exemplary block diagram of a BCH encoder in accordance with another embodiment of this invention; DESCRIPTION OF THE PREFERRED EMBODIMENTS Reference is now made to Fig. 2, which shows a schematic block diagram of a BCH encoder 200, in accordance with one embodiment of this invention. Encoder 200 is a high speed encoder, which is capable of operating at speeds of 10 Gbps and beyond. Higher bit rates might be supported with the progress of silicon design technology. The design is suitable for any code length and generator length of size of at least 1,000 bits.

Encoder 200 is designed to perform parallel encoding of BCH codewords, unlike prior art BCH encoders, e. g. that disclosed in Carson (IJS patent number 5,040, 179). That is, encoder 200 is a parallel implementation of the modulo operation, R (x) = f (x) x3+ mod g (x). Encoder 200 produces the parity word after receiving the entire input information word. The input information word is received as'n'consecutive words of'p'bits each, hence, encoder 200 outputs the parity word, i. e. , the redundancy information after only'n' cycles. In comparison, in prior art solutions it would take at least'nxp'cycles to reach the same result.

In order to understand the operation of encoder 200, a brief explanation of the underlying mathematics of the encoding scheme is helpful. The aim of encoder 200 is to calculate the remainder (hereinafter"R (x) ") resulting from dividing the input polynomial

(hereinafter"f (x)") by the generator polynomial (hereinafter"g (x) "), i. e., performing the modulo operation described in equation (1).

Assume for the purpose of this invention that f (x) comprises'n'input words uo (x), ul (x),..., un l (x). The length of ui (x) is'p', the length of f (x) is pxn', the length of R (x) is M, and the degree of g (x) is M. Since in each cycle encoder 200 receives'p'bits in parallel, the present invention uses a different approach than the prior art approach. In the first step, an intermediate quotient (hereinafter"qi (x) ") is estimated using the current input word (hereinafter"ui (x) ") and the'p'most significant bits (MSBits) of the previously calculated R (x) (hereinafter "Ri-1 (x) "). Then, in the second step, the reminder Ri (x) is updated by multiplying between qi (x) and g (x), followed by adding the'M-p'MSBits of the result to the M-p least significant bits (LSBits) of the previously calculated Ri-1 (x). This process is repeated'n'times, i. e. , for"i"starting at zero and ending at'n-1'. Mathematically, this approach can be described by the following steps: The estimation of qi (x) is calculated by using the equation: qi (x) = {us (x) + r (x)} *g'\x) Jp. MSBits (2) where the polynomial r (x) includes the p-MSBits of the previously calculated R (x) as its coefficients. The sign'*'denotes polynomial modulo-2 multiplication. The'p-1'degree binary polynomial g-' (x) is the reciprocal polynomial of the generator polynomial g (x). The coefficients of the polynomial g-1(x) are derived from the polynomial g (x) and are constant.

The g-' (x) coefficients are predetermined using the equation: g 1 (X) *g (x) IP-MSBits = X (3) The reminder is calculated by using the equations: Ri (x) = qi (x) *g (x) #M-LSBits (4) and, Ri (x) = [R (x) i#(M-p)MSBits # Ri-1(x)# (M-p)LSBits]#xp # Ri(x)#p-LSBits (5) where Ri-1 (x) represents the previously calculated R (x).

Encoder 200 includes: a first adder 230 for performing XOR logical operations involving MSBits of R (x) and'p'bits of current input word ui (x); a quotient computation logic (QCL) 210 connected to first adder 230 for estimating intermediate quotient qi (x); a remainder computation logic (RCL) 220 connected to QCL 210 and used for calculating reminder Ri (x); a second adder 240 connected to RCL 220 and used for performing XOR logical operations involving (M-p) LSBits of a previous Ri-, (x) and (M-p) MSBits of a new R ; (x) ; and a register 270 connected to RCL 220, second adder 240 and first adder 230 and used for saving the (M-p) MSBits resulting from second adder 240 along with the p LSBits resulting from RCL 220. QCL 210 and RCL 220 include combinational logic of XOR gates. First adder 230 includes an array of'p'XOR gates, while second adder 240 includes an array of'M-p'XOR gates. At startup, register 270 is set to zero value. First adder 230 receives the p-MSBits of the previously calculated Ri-, (x) from register 270 together with 'p'input bits of ui (x), and performs a bit-by-bit XOR operation between these quantities.

QCL 210 estimates the quotient qi (x) by multiplying the output of adder 230 by g~l (x), namely, QCL 210 implements equation (2) above. The coefficients of the polynomial g-l (x) are predetermined according to equation (3) and thus determine the combinational logic of XOR operations within QCL 210. The coefficients of g-l (x) may be represented by a matrix as shown in Fig. 4A. RCL 220 calculates R (x) by modulo-2 multiplication between the output of QCL 210 (i. e., qi (x) ) and the coefficients of g (x). Namely, RCL 220 implements equation (4). The coefficients of the g (x) are provided from the BCH code definition, and thus determine the combinational logic of XOR operations within RCL 220. The coefficients of g (x) may be represented as a'G'matrix shown in Fig. 4B. As mentioned, the (M-p) MSBits of the newly calculated Ri (x) are XORed with the (M-p) LSBits of the previously calculated Ri-, (x) by means of adder 240. The result is inserted into register 270 as its (M-p) MSBits. The p-LSBits resulting from the calculation performed by RCL 220 are inserted into register 270 as its p-LSBits. Now, register 270 includes the updated reminder as a result of the division of us (x) by g (x). After'n'cycles, register 270 holds the reminder of the division operation of the entire input polynomial f (x) by g (x), i. e. , the redundancy bits.

Reference is now made to Fig. 3, which shows an exemplary flowchart 300 describing the method for parallel encoding by encoder 200, in accordance with one embodiment of this invention. Each cycle encoder 200 receives'p'bits of u ; (x) and produces a temporary redundancy information. An index"i"and the content of register 270

are both set to zero in a step 305. In a step 310, encoder 200 receives the current ui (x) to process. In a step 320, the'p'MSBits of the previously calculated R (x) are XORed with the 'p'bits of us (x), using adder 230. In a step 330, encoder 200 calculates qi (x) by multiplying between the output of adder 230 and the polynomial g~l (x). In the embodiment of Fig. 4A, the polynomial g-l (x) may be represented as a matrix (G-1) having'p'rows and'p' columns, where the matrix elements are composed from the coefficients of g-, (X). The result is a p-bit vector of qi (x). In a step 340, qi (x) and g (x) are multiplied. The M-LSBits of the multiplication provide the M bits of the intermediate reminder Ri (x). In the embodiment of Fig. 4B, g (x) may be represented as a matrix"G"having'M'rows and'p'columns, where the matrix's elements are composed from the g (x) polynomial coefficients. In a step 350, a XOR operation is performed between the'M-p'LSBits of the previously calculated Ri-, (x) and the'M-p'MSBits results from the calculation performed in step 340. In a step 360, the outcome of adder 240 is saved into register 270 as its'M-p'MSBits, and furthermore, the'p'LSBits of the result received in step 340 are saved into register 270 as its'p'LSBits. In a step 365, the index"i"is increased by one. In a step 370, it is determined whether there are more input words u ; (x) to process, i. e. , if the index"i"equals n-1. If there are more input words, i. e. "i"is smaller than'n', the method continues to step 310, otherwise the method continues to a step 380. In step 380, after receiving the entire input information word encoder 200 outputs the content of register 270 as redundancy bits, i. e. the resulting reminder.

Reference is now made to Fig. 5, which shows a step-by-step example of the encoding procedure. Here, M=10, p=4, n=3, and the length of the input information word 'K'equals 12. The input data includes three input blocks uo = 1101, ul = 1101, and U2 = 0011. Each 4-bit input block uses MSBit (left bit) first notation. The generator polynomial g (x) is x10+x8+x3+1, and the computed g-' (x) polynomial is X3+X. Fig. 5A shows the content of register 270 after each cycle. QCL 210 multiplies between its input and the Gel matrix shown in Fig. 5B. The multiplication is done according to qj= [G-l] wj modulo-2, where qi and w ; are column vectors holding the coefficients of qi (x) and wi (x) polynomials respectively. The vector w ; holds the result of the operation performed by adder 230. The coefficient representing the LSBit of the polynomial is the first (upper) element in the respective column vector, while the coefficient representing the MSBit of the polynomial is the last (bottom) element in the respective column vector. RCL 220 multiplies between its input and the G (x) matrix shown in Fig. 5C. The multiplication is done according to Ri =

G qi modulo-2. Here qi and Ri are column vectors holding the coefficients of the qi (x) and Ri (x) polynomials respectively. The coefficient representing the LSBit of the polynomial is the first (upper) element in the respective column vector, while the coefficient representing the MSBit of the polynomial is the last (bottom) element in the respective column vector.

After three cycles, register 270 contains the transmitted redundancy information which is (MSBit Ist) : 1010 0010 10.

One of the problems faced in the implementation of systems having a high clock rate utilizing a generator polynomial with a high degree, is the propagation delay. The propagation delay is the time required for a signal to flow through a combinational logic.

For example, if a combinational logic consists of"c"logic gates in series, then the propagation delay is"c"times the delay of a single logic gate, while for a tree structure connection the propagation delay is log2 (c) times the delay of a single logic gate. Reducing the propagation delay can be achieved by using a pipeline implementation. Reference is now made to Fig. 6, which shows an exemplary block diagram of a BCH encoder 600, designed to reduce the propagation delay. Encoder 600 includes the elements of encoder 200, and further includes a buffer 680. Buffer 680 buffers between a QCL 610 and a RCL 620, allowing the operation of logical circuits QCL 610 and RCL 620 to act as a pipeline process. Firstly, encoder 600 estimates the quotient qi (x) and stores the result in a buffer 680. Secondly, encoder 600 calculates the reminder Ri (x) using the previously calculated quotient i. e., qi-i (x). The value of q ; _1 (x) is obtained from buffer 680. The calculation of qi (x) and Ri (x) are described in detail above. However, in this embodiment, QCL 610 multiplies between'2p'coefficients of g (x)-l, and thus qi (x) includes'2p'bits. Therefore, 'p'is replaced by'2p'in the calculation of g 1 (x). The coefficients of g-' (x) determine the logic of QCL 610 and are derived using the following equation: g-' (x) *g (x) ! 2. p-MSBits=X. -' (6) Using this approach, the propagation delay is the time required to output reminder R (x), which is equal to max (tl, t2). The time ti is the propagation delay of a first adder 630 and QCL 610. In some cases, the time tl includes the propagation delay results from the interfaces of encoder 200 components. The time t2 is the sum of the propagation delays of RCL 620 and a second adder 640, as opposed to encoder 200, where the propagation delay equals to the sum of propagation delay time of encoder 200, adder 230, QCL 220, RCL 210 and adder 240.

The inventors wish to point out that adding more pipeline stages, i. e. adding additional buffers, reduces the propagation delay at the expense of increased hardware size This invention may have a particular use as a BCH encoder described in co-pending PCT patent application filed December 10,2002,"An Apparatus for Processing OTN Frames Utilizing an Efficient Forward Error Correction"in the name of Optix Networks Ltd. , which is hereby incorporated by reference.

Encoder 200 in used in the apparatus to produce the redundancy information residing in an optical transport network (OTN) frame. Encoder 200 receives two input information words"A"and"B"and produces the redundancy correlated with these information words. For processing the input word"A", each cycle encoder 200 receives.

128 bits of word"A"and after 120 cycles outputs 1,015 bits of the redundancy information.

For processing the input word"B", each cycle encoder 200 receives 128 bits of word"B" and after 119 cycles outputs 1,015 bits of the redundancy information. The lengths of input information words"A"and"B"are 128*120 (i. e. , 15,360) bits and 128*119 (i. e. , 15,232) bits respectively.

Encoder 200 described herein is designed to encode input information when the length of the generator polynomial (i. e., M) is greater than the length of the current input word (i. e. , p). However, a person skilled in the art could easily adapt encoder 200 to operate when the M is smaller than, or equal to, p.

The invention has now been described with reference to specific embodiments. Other embodiments will be apparent to those of ordinary skill in the art. For example, the invention has been described with respect to a BCH code. The invention can be modified to apply to special cases of error correcting codes having similar characteristics, such as Reed-Solomon codes, which are non-binary subsets of BCH codes. In addition, the invention applies to a wide variety of linear cyclic invariant codes whose generator polynomials can be factored.

All publications, patents and patent applications mentioned in this specification are herein incorporated in their entirety by reference into the specification, to the same extent as if each individual publication, patent or patent application was specifically and individually indicated to be incorporated herein by reference. In addition, citation or identification of any reference in this application shall not be construed as an admission that such reference is available as prior art to the present invention.