WO2004036759A1

WO2004036759A1 - Method and device for determining a polynomial sum

Info

Publication number: WO2004036759A1
Application number: PCT/EP2002/011581
Authority: WO
Inventors: Jürgen LERZER
Original assignee: Telefonaktiebolaget LM Ericsson AB
Current assignee: Telefonaktiebolaget LM Ericsson AB
Priority date: 2002-10-16
Filing date: 2002-10-16
Publication date: 2004-04-29
Anticipated expiration: 2005-04-16
Also published as: AU2002357456A1

Abstract

The application describes a method and device for determining a polynomial sum in a symbol processing device (such as a syndrome determination in an error correction apparatus) that receives a predetermined number of symbols, where the sum is determined by providing a sequence of n symbols on the basis of the received symbols, n being a natural number greater or equal the predetermined number, and there being a natural number p such that n/p is a natural number, and the sum is determined by consecutive steps of calculating intermediate sums (Formula I) said intermediate sums being determined in a parallel calculation procedure that determines the addends in parallel.

Description

[Title ]

Method and device for determining a polynomial sum

[Field of the invention]

The present invention relates to a method and a device for determining a polynomial sum in a symbol processing device that receives a predetermined number of symbols.

[Background of the invention]

There are many technical applications in which it is necessary to determine a polynomial sum of the form

where Rj_ represents the i-th symbol in a sequence and α represents a predetermined value. In other words, the sum S is derived on the basis of a sequence of n symbols Rj_, where n is a natural number, and on the basis of associated powers of a predetermined value α.

An example where such polynomial sums are calculated, is in the field of decoding, where the received symbols belong to a received word

where the elements v-j_ are the symbols of the received word.

The received word v(x) is the sum of the actual code word c (x) provided by a coder and an error polynomial e (x) due to a transmission of the code word c (x) from the encoder to the decoder over an error prone connection. Therefore: v(x) = c (x) + e (x) .

In the course of determining the elements of the error polynomial e (x) , i.e. in the course of error correction, it is well known to calculate so-called partial syndromes

S_j =v (γ _j ) j =l,...,r (3)

where γι-.._/*γ_r are the zeros of the generator polynomial g (x) used for generating the code word c (x) .

A known way of calculating a polynomial sum of the form shown in equation (1) is by performing an operation indicated by Fig. 4. As can be seen, starting with the lowest symbol ("low" and "high" mean associated with low and high powers in the polynomial sum, respectively) of the sequence R_Q and progressing to the highest symbol R_n_-ι_, the symbols are added to the product of the value held in a memory 41 multiplied by α, and the result of the addition is written into the memory 41. Thereby it takes n shifts to output the total sum S, i.e. after n shifts the result of the addition in adding element 43 is the sum S. [Object of the invention]

The object of the invention is to provide an improved method and device for determining a polynomial sum of the type shown in equation (1) .

[Summary of the invention]

This object is achieved by a method described in claim 1 and a device described in claim 6. Advantageous embodiments are described in the dependent claims .

In accordance with the invention a received number of symbols is arranged into a sequence of n symbols, n being a natural number greater or equal to the received number of symbols, where n is such that a natural number p exists for which n/p is also a natural number. In other words, p is a factor of n. Then the determination of the polynomial sum S indicated above in equation (1) is performed by processing the n symbols of the sequence in p-tuples. In a first step, a first intermediate sum

is determined on the basis of the p highest symbols R_n_p to

^Rn-1 °f the sequence. The term "highest" here refers to those symbols R-j_ of the sequence that are associated with the highest powers in the polynomial. After determining the first intermediate sum, an intermediate calculation value is determined by multiplying the first intermediate sum by αP . Thereafter, a modification procedure is conducted, in which the intermediate calculation value is consecutively modified by adding to the intermediate calculation value to a further intermediate sum representable as

and then multiplying the result by ^p and then storing the multiplication result as a new intermediate calculation value, for descending values of q from q=(n/p-2) to 1. After completing the modification procedure, a final intermediate sum representable as

is added to the intermediate calculation value, and the result is the desired polynomial sum S of equation (1) . All of the intermediate sums are determined in a parallel calculation procedure that determines the addends in parallel.

Therefore, in the present invention, the polynomial sum is determined by processing p-tuples in parallel, which allows a faster processing, but is at the same time not complicated in terms of the hardware and/or software employed.

It may be noted that if the number of received symbols is n' , and n' does not provide the desired factorisation into p, then a sequence of n symbols, where n > n' is provided by setting each of the (n-n' ) highest symbols R_n' to R_n_ι equal to zero. As a consequence, the concept of the present invention is generally applicable to systems having an arbitrary number of received symbols that are to be processed in a polynomial sum.

The present invention is preferably implemented in the context of a decoder, where the received symbols constitute a received word to be decoded, and the polynomial sum is a partial syndrome.

[Brief description of Figures]

The present invention will now be described in more detail with reference to the attached figures, in which

Fig. 1 shows a flowchart of a first embodiment of the method of the present invention;

Fig. 2 shows a flowchart of a second embodiment of the method of the present invention;

Fig. 3 shows an embodiment of the device of the present invention; and

Fig. 4 shows a prior art circuit arrangement for determining a polynomial sum.

[Detailed description of embodiments]

In the following, embodiments of the present invention shall be described, and sometimes reference will be made to the preferred application to a decoder, in which polynomial sums are calculated as partial syndromes. However, it is to be noted that the concept of the present invention is by no means restricted to this application to decoders, and that the present invention can be applied in any signal processor in which a number of symbols is received and a polynomial sum is to be calculated on the basis of the received symbols.

It is to be noted that the application of the present invention to such an arbitrary signal processor or symbol processing device (of which a decoder is only an example) in any case affords the effect for said symbol processing device that the polynomial sum is determined with increased speed, but at the same time without complicating the hardware and/or software of the symbol processing device .

The symbols to be processed can be of any type suitable for operations involved in determining a polynomial sum, and will generally be the elements of an Abelian group, i.e. a group of objects for which an addition and subtraction is defined. Preferably, the symbols are elements of a field, i.e. objects for which addition, subtraction, multiplication and division is defined, more preferably of a Galois Field (GF) . For example, the symbols can belong to GF(2) , e.g. be bits having a possible value of 0 and 1.

In a general way, the concept of the present invention can be explained by rearranging the polynomial sum S of equation (1) as shown in following equation (7) : S =R„ +R,a + ... + R p-\ a p-\ + p-ϊ a" ^■(R_p +R_p+]a + ...+R_2p__]cX ^' + a^p-(R_2p + R_2p+1α + ... + R_3/,_₁α'-^|+

(7) a^p -(R_3p +...

a^p-(R_ll__p+R_ll__p+[ + ...R_n__l ^)))...)

As can be seen, the polynomial sum S is rearranged into intermediate sums having p elements, where p is a factor of n, n being the overall number of symbols R_ in the sequence

Each intermediate sum is in the form

where q = (n/p-1) to 1, and the processing can be conducted started from the innermost intermediate sum

then multiplying said sum by αP, and then adding the next lower intermediate sum, again multiplying by αP etc. Finally, the last intermediate sum

is added, in order to determine the final result of S, The advantage is that the intermediate sums are all calculated in the same fashion, and are always multiplied by the same factor α . This allows a simple hardware and/or software structure for performing the calculation, and especially allows calculating the intermediate sums in a parallel calculation procedure that determines the addends in parallel. As a consequence, a parallelization of degree p can be achieved with at the same time simple software and/or hardware .

As can be seen from above equation (9) , p is a factor of n. If the number of received symbols n' (n' < n) is not suitable for factorisation into a desired p, then it is sufficient to complement the received symbols R_Q to R_n'-1 by (n-n' ) higher symbols (i.e. associated with higher powers in the polynomial sum) R_nr to R_n_ι , where each of said symbols R_n' to R_n_ι is equal to the 0-symbol of the group to which the symbols belong.

Fig. 1 shows a flowchart of a first embodiment of the method of the present invention. In a first step SI, parameters q and S are initialised to initial values of (n/p-1) and 0, respectively. Then, in step S2 , the intermediate sum

p-\

Σ q -p +ι a ( 5 ]

;'=0

is added to S, and the result is held as a new value of S . In the following step S3, S is multiplied by αP , the result again being held as a new value of S. Then, in step S4 , q is decremented by 1, and in the following step S5 it is determined whether q is greater or equal to 1. If it is, then the procedure loops back to step S2 and continues until the results of S5 is negative, i.e. q = 0. In that event, the procedure goes to step S6, in which the intermediate sum

p -\

Σ*. a (6)

;=0

is added to S in order to generate a new value of S, that new value of S being the final result for determining the polynomial sum

Fig. 2 shows a flowchart of a second embodiment of the present invention, which has the same steps SI and S2 as the embodiment of Fig. 1, such that a renewed description is not necessary. However, in contrast to the example of Fig. 1, the example of Fig. 2 has a step S6 following step S2 , said step S6 determining whether the value of q is larger than 0. If it is, the system continues with steps S3 and S4 , said steps being identical to those already described in connection with Fig. 1, and subsequent to step S4 , a loop back to S2 occurs. If the outcome of step S6 is negative, i.e. q is 0, then the procedure ends and the momentary value of S is the result of the polynomial sum.

The present invention can be implemented in the form of hardware, software or any suitable combination of software and hardware . According to a preferred embodiment , the method is implemented in a circuit as shown in Fig. 3. This circuit comprises a receiving unit 36 for receiving the predetermined number of symbols and outputting the symbols as p-tuples in parallel. The p-tuples of symbols output by receiving unit 36 are given to a parallel processing unit 31 that outputs the p addends of the above-mentioned intermediate sums. The p addends output by the parallel processing unit 31 are input into an adding device 32 that outputs the summed result to a memory 33. Furthermore, the output 35 from the memory 33 is also fed back into a multiplying unit 34, for multiplying said output from the memory by αP, and for supplying the multiplication result as an input to adder 32.

The receiving unit 36 is arranged in such a way that it outputs the p-tuples in accordance with the above method i.e. starting with the highest p symbols R_n_p to R_n_ι, and then outputting consecutively lower p-tuples of the symbols R in subsequent shifts. The contents of memory 33 is initialised to 0 before beginning the processing. In this way, the circuit of Fig. 3 is capable of determining the polynomial sum S of equation (1) in only n/p shifts, as opposed to the n shifts required by the circuit of Fig. 4. As a consequence, the circuit of Fig. 3 is capable of high-speed processing of the received symbols R, while at the same time the complexity of the circuit of Fig. 3 is not much greater than that of Fig. 4.

In accordance with the invention, the receiving unit 36 is arranged such that if the number n' of received symbols does not provide the suitable factorisation into p, then n symbols are output, where the (n-n' ) highest symbols R_n' to R_n-i are equal to 0.

In a preferred embodiment, the circuit of Fig. 3 is a part of a decoder, and said received number of symbols constitute a received word to be decoded, and the polynomial sum S is a partial syndrome.

Although the present invention has been described with the help of detailed embodiments, this description of detailed embodiments only serves to provide the skilled person with a thorough understanding of the invention, and is not intended to be restrictive. The scope of the present invention is defined by the appended claims and all equivalents thereof.

Reference signs in the claims are intended to make the claims easier to read and are not limiting.

Claims

1. A method of determining a polynomial sum (S) in a symbol processing device that receives a predetermined number (n, n') of symbols (Ri) , said method comprising:

providing a sequence of n symbols on the basis of said received symbols, n being a natural number greater equal the predetermined number (n, n¹ ) , and there being a natural number p such that n/p is a natural number, said polynomial sum (S) being based on said sequence and being representable as

where Ri represents the i-th symbol in the sequence and represents a predetermined value,

determining (S2) a first intermediate sum representable as

on the basis of the highest p symbols R_n-_P to R_n._x of said sequence,

determining (S3) an intermediate calculation value by multiplying said first intermediate sum by α^p ,

in a modification procedure (S2, S3, S4, S5; S2 , S6, S3, S4) consecutively modifying said intermediate calculation value for descending values of q from

q = to 1 by adding to said intermediate

calculation value a further intermediate sum representable as

and then multiplying the result by α^p, storing the multiplication result as said intermediate calculation value and decrementing q by 1,

after completing said modification procedure (S2, S3, S4, S5; S2, S6, S3, S4) adding a final intermediate sum representable as p-l

∑Rr"'

(=0 to said intermediate calculation value and outputting the result as said polynomial sum (S) ,

where each of said intermediate sums is determined in a parallel calculation procedure that determines the addends in parallel.

2. The method of claim 1, wherein said symbol processing device receives n' symbols (Ri) , n' being a natural number smaller than n, where the sequence of n symbols (Ri) is provided by setting each of the (n-n¹) highest symbols R_n. to R_n_ι equal to zero.

3. The method of claim 1 or 2 , wherein said symbol processing device is part of a decoder, said received number (n, n') of symbols constitute a received word to be decoded, and said polynomial sum (S) is a partial syndrome .

4. A computer program arranged to perform the method of one of claims 1 to 3 when executed on a computer.

5. A computer program product comprising the computer program of claim 4.

6. A device arranged to execute the method of claim 1.

7. A device according to claim 6, comprising:

a receiving unit (36) for receiving the predetermined number (n, n') of symbols (Ri) and outputting p-tuples (R(q₊i)_P-i, ... , Rqp) of said symbols (Ri) in parallel,

a parallel processing unit (31) for processing the p- tuples (R(q₊ι)p-ι, ... ,Rqp) of symbols (Ri) output by said receiving unit (36) in parallel and outputting p addends of said intermediate sums,

an adder (32) for adding the p addends output by said parallel processing unit (31) ,

a memory (33) arranged to store the result output by said adder (32) , and

a multiplying unit (34) arranged to receive the output of said memory (33) and multiply it by α^p, and to provide the multiplication result to said adder (32) .

8. The device of claim 7, wherein said receiving unit (36) receives n' symbols (Ri) , n' being a natural number smaller than n, and said receiving unit (36) is arranged to provide the sequence of n symbols (Ri) by setting each of the (n-n¹) highest symbols R_n* to R_n_ι equal to zero .

9. The device of claim 7 or 8 , wherein said device is a part of a decoder, said received number (n, n') of symbols constitute a received word to be decoded, and said polynomial sum (S) is a partial syndrome.