Method and apparatus for syndrome calculation

This invention relates to a method, and an associated apparatus, for calculating the syndromes of received codewords, in a communications system.

In many communications systems, in which digital data is transmitted over a communications channel, error correcting codes are used. That is, in an encoder located within the transmitter, parity bits are added to each block of useful data that is intended for transmission. The useful data bits plus the added parity bits together form a codeword, and only a small proportion of the possible combinations of bits represent valid codewords. In other error correction systems, for example convolutional coding systems, the user data is changed rather than parity data being appended. The codeword formed in the encoder is then transmitted over a transmission channel, which may have the effect of causing errors to be introduced into the transmitted data bits.

The receiver therefore includes a decoder, which uses error correction techniques to correct for any errors introduced by the transmission channel. With a well designed system, it can be assumed that, if a received codeword is one of the valid codewords used in the system, then there were no errors introduced by the transmission channel. Moreover, provided that only an acceptably small number of bit errors are introduced by the transmission channel, the fact that only a small proportion of the available bit combinations represent valid codewords can be used to determine which of those valid codewords must have been transmitted, and therefore the errors in the transmitted data can be corrected.

Error correction codes that are well known and in widespread use include the

Reed-Solomon (RS) codes, which are a subclass of Bose-Chaudhuri-Hocquenghem (BCH) codes. In BCH codes, including RS codes, in order to detect the presence of errors in the received data, and as a first step in correcting for any detected errors, the decoder must calculate a number of syndromes, this number being equal to the number of parity symbols added in the encoder.

US2003/0229842 discloses a method of calculating the syndromes for a received codeword. If the first half of the syndromes are all zero, it is inferred that all of the syndromes are zero, or that there are more transmission errors than can be corrected by this particular code, and the computation is stopped. WO2004/059487discloses an apparatus and a method for parallel calculation of syndromes, with separate calculators for calculating different syndrome coefficients of a received codeword in parallel.

Nevertheless, when data is being transmitted from the transmitter to the receiver at high data rates, the computation of the syndromes places a high computational burden on the processing capability of the receiver, and also consumes significant power in the receiver.

It would therefore be advantageous to be able to compute the syndromes in a way which reduces the computational burden and the power consumption.

According to a first aspect of the present invention, there is provided a method of calculating a plurality of syndromes for received codewords, the method comprising: receiving first and second codewords; calculating a first set of syndromes for the first received codeword, and calculating a second set of syndromes for the second received codeword, wherein the first and second sets of syndromes are mutually exclusive consecutive syndromes that together form a complete set of syndromes; and if the calculated first set of syndromes for the first received codeword are all zero, then inferring that all of the syndromes for the first received codeword are zero, and otherwise calculating the second set of syndromes for the first received codeword; and if the calculated second set of syndromes for the second received codeword are all zero, then inferring that all of the syndromes for the second received codeword are zero, and otherwise calculating the first set of syndromes for the second received codeword.

According to a second aspect of the present invention, there is provided an apparatus for calculating a plurality of syndromes for received codewords, the apparatus comprising: first and second inputs for receiving first and second codewords respectively; a first syndrome set calculation block for calculating a first set of syndromes; a second syndrome set calculation block for calculating a second set of syndromes, wherein the first and second sets of syndromes comprise mutually exclusive consecutive syndromes that together form a complete set of syndromes;

summing circuitry for forming the sums of the first set of syndromes and of the second set of syndromes; a first controllable switching circuit, for applying the first codeword to the first syndrome set calculation block and the second codeword to the second syndrome set calculation block, or for applying the first codeword to the second syndrome set calculation block and the second codeword to the first syndrome set calculation block; and control circuitry, for determining whether the sums of the first set of syndromes and the second set of syndromes are zero, and wherein the control circuitry is adapted: if the sum of the first set of syndromes is not zero, to apply the codeword previously applied to the first syndrome set calculation block to the second syndrome set calculation block, and if the sum of the second set of syndromes is not zero, to apply the codeword previously applied to the second syndrome set calculation block to the first syndrome set calculation block.

Reference will now be made, by way of example, to the accompanying drawings, in which: Fig. 1 is a block schematic diagram of a communications system in accordance with the present invention.

Fig. 2 is a more detailed block schematic diagram showing the form of the decoder in the receiver of the system of Fig. 1.

Fig. 3 is a schematic illustration of a first element of the decoder of Fig. 2. Fig. 4 is an illustration of a second embodiment of the first element of the decoder of Fig. 2.

Fig. 5 is a block schematic diagram showing in detail the form of a second element of the decoder of Fig. 2.

Fig. 6 is a flow chart illustrating the method of operation of the syndrome calculator in the decoder of Fig. 2.

Fig. 1 is a block schematic diagram of a communications system in accordance with the present invention.

Such Communications systems are extremely well known to a person skilled in the art, and will be described herein, only so far as is necessary for an explanation of the present invention.

Input data is provided to a transmitter 10, which includes an encoder 12. The encoded data is transmitted across a transmission channel 20 to a receiver 30, which includes a decoder 32, and output data is provided from the receiver 30.

The communications channel 20 can take any form, and in particular it may be either wired or wireless. It will of course be appreciated that the transmitter 10 includes many other components besides the encoder 12, and that the receiver 30 similarly includes many other components besides the decoder 32.

The present invention is described with reference to the use of Reed- Solomon (RS) codes, which are widely used in a variety of communications systems.

There are a large number of available RS codes, whose suitability for a particular application depends on various factors, such as the required data transmission rate and the probability that errors will be introduced in the communications channel. In general terms, the encoder receives blocks of k input symbols and adds (n-k) parity symbols to form a block of N symbols for transmission, and this is referred to as an (N,k) RS code. For such a code, the decoder 32 is able to correct errors in the received data, provided that the number of symbol errors in each block of N symbols does not exceed (N-k)/2, which is represented by t. Figure 2 is a block schematic diagram illustrating the form of the error correction decoder 32. Specifically, received data is passed to a divider 40, in which it is divided into two streams and passed to a syndrome calculator 42. As will be described in more detail below, the calculated syndromes are passed to a key equation solver 44, the output of which is passed to a Chien searcher 46 and a Forney solver 48, in order to determine the location of any error in the received data, and the required correction.

The details of the key equation solver 44, Chien searcher 46 and Forney solver 48 are well known to the person skilled in the art, and will not be described further herein.

As will be discussed in more detail below, the syndrome calculator 42 receives the received data divided into two parallel bitstreams. In some systems, the received data may already have been divided into two suitable bitstreams by earlier components of the receiver, in which case these parallel bitstreams can be applied directly to the syndrome calculator 42. However, where this is not the case, the divider 40 is provided.

Figure 3 illustrates a first possible implementation of the divider 40. In Figure 3, an input bitstream 60 is supplied to a demultiplexer 62, which is controlled by a clock signal 64, such that alternate codewords are written to the first and second Fifo blocks 66, 68.

Figure 4 illustrates an alternative implementation of the divider 40. Specifically, a pair 70 of symbols from the main buffer 72 are read at the same time, and written into respective Fifo blocks 66, 68.

Figure 5 is a block schematic diagram showing in more detail the form of the syndrome calculator 42.

In Figure 5, the first Fifo block 66, shown in Figures 3 and 4, is shown to be formed from respective first and second Fifo memories 80, 82, each of which can contain at least one received codeword. Similarly the second Fifo block 68 is shown to comprise respective first and second Fifo memories 84, 86, each of which again can contain at least one received codeword.

The outputs of the Fifo memories 80, 82 of the first Fifo block 66 are supplied to a first multiplexer 88, while the outputs of the Fifo memories 84, 86 of the second Fifo block 68 are applied to a second multiplexer 90.

A controller 92 provides a first control signal ol to control the second multiplexer 90, and provides a second control signal o2 to control the first multiplexer 88.

The output of the first multiplexer 88 is applied to the input of a first demultiplexer 94, and the output of the second multiplexer 90 is provided to the input of a second demultiplexer 96. The first demultiplexer 94 is connected such that it can supply an output either to a third multiplexer 98 or to a fourth multiplexer 100. The second demultiplexer 96 is connected such that it too can provide an output either to the third multiplexer 98 or to the fourth multiplexer 100. The controller 92 provides a third control signal o3 to control the operation of the second demultiplexer 96 and the fourth multiplexer 100, and provides the inverse of the third control signal o3 to control the operation of the first demultiplexer 94 and the third multiplexer 98.

As is well known to the person skilled in the art, in order to be able to detect and correct errors in the received data, it is generally necessary to calculate a number of syndromes, with that number being equal to the number of parity symbols added in the encoder, namely 2t.

In accordance with the present invention, these 2t syndromes are calculated in two separate blocks. Specifically, as shown in Figure 5, the output of the third multiplexer 98

is applied to a first syndrome set calculation block 102, while the output of the fourth multiplexer 100 is connected to the input of a second syndrome set calculation block 104.

Each of the syndrome set calculation blocks 102, 104 calculates a respective set oft consecutive syndrome coefficients, such that all of the 2t syndrome coefficients are calculated between the two blocks 102, 104. Thus, one of the syndrome set calculation blocks calculates the syndromes S ₁ , S ₂ , ..., S _t , while the other syndrome set calculation block calculates the syndromes S _t + _l5 S _t +2, •••, S2t, or more generally one of the syndrome set calculation blocks calculates the syndromes S _j ,..., S _j - _H-1 , for some value of j such that 1 <j < t, while the other syndrome set calculation block calculates the remaining syndromes, for example S _j+t , S _j+ t ₊₁ , ..., S _2t , S ₁ , ..., Sj _-1 .

The invention can perhaps be described most simply if it is assumed that the first syndrome set calculation block 102 calculates the first half of the syndrome coefficients, while the second syndrome set calculation block 104 calculates the second half of the syndrome coefficients. That is, for example, in the case where t = 8, the first syndrome set calculation block 102 calculates the syndrome coefficients S ₁ -S ₈ , while the second syndrome set calculation block 104 calculates the syndromes S ₉ -S ₁₆ . However, this is not essential or, necessarily, preferred.

The syndromes calculated in the first syndrome set calculation block 102 are summed in an adder 106, with the result, si, being supplied to the controller 92. Similarly, the syndromes calculated by the second syndrome set calculation block 104 are summed in an adder 108, and the result, s2, is supplied to the controller 92.

The syndromes calculated by the first syndrome set calculation block 102 are applied to a third demultiplexer 110, the outputs of which are connected to first and second buffer memories 112, 114. The syndromes calculated by the second syndrome set calculation block 104 are applied to a fourth demultiplexer 116, the outputs of which are connected to third and fourth buffer memories 118, 120. The first and second buffer memories 112, 114 are connected to the inputs of a fifth multiplexer 122, while the third and fourth buffer memories 118, 120 are applied to the inputs of a sixth multiplexer 124.

A fourth control signal o4 is applied from the controller 92 to control the fourth demultiplexer 116, and is applied inverted to control the third demultiplexer 110. A fifth control signal o5 is applied from the control line 92 to control the fifth and sixth multiplexers 122, 124. The outputs of the fifth and sixth multiplexers 122, 124 are applied to a syndrome calculator output 126 and, as shown in Figure 2, the resulting output can then be applied to the key equation solver 44, as is well known to the person skilled in the art.

The operation of the syndrome calculator shown in Figure 5 will now be described in more detail, with reference to the flow chart given in Figure 6.

As shown in step 140 of the process illustrated in Figure 6, first and second codewords are received in the first and second Fifo memory blocks 66, 68 respectively. Specifically, it can be assumed for the purposes of this example that a first codeword is stored in the first Fifo memory 80 of the first Fifo block 66, while a second codeword is stored in the first Fifo memory 84 of the second Fifo block 68. As will be described further below, the process must also operate on codewords stored in the second Fifo memory 82 of the first Fifo block 66, and in the second Fifo memory 86 of the second Fifo block 68. At this time, the control signals ol and o2 are set such that the first and second codewords are applied from the Fifo memories 80, 84 respectively through the first and second multiplexers 88, 90 respectively to the first and second demultiplexers 94, 96 respectively. Also, the control signal o3 is set to the value 1, such that the first codeword is applied from the first demultiplexer 94 through the third multiplexer 98 to the first syndrome set calculation block 102, while the second codeword is applied from the second demultiplexer 96 through the fourth multiplexer 100 to the second syndrome set calculation block 104. Thus, in steps 142, 144 of the process, the first syndrome set calculation block 102 calculates the first syndrome set for the first codeword, and the second syndrome set calculation block 104 calculates the second syndrome set for the second codeword. In step 146 of the process, the value of the signal si is tested, to determine whether the sum of the first syndrome set, calculated in the first syndrome set calculation block 102 for the first codeword, equals zero. In step 148, it is determined from the signal s2 whether the sum of the second syndrome set, calculated in the second syndrome set calculation block 104 for the second codeword, equals zero. The present invention proceeds from the realization that, if any set of t consecutive syndrome coefficients, out of the available 2t syndrome coefficients, are all zero, then it can be determined that all of the 2t syndrome coefficients are zero, and hence that the codeword is in fact a valid codeword. In accordance with conventional error correction decoding, in a well-designed system, it can then usually be assumed with an acceptable degree of safety that a received valid codeword indicates the absence of errors in the received codeword.

Therefore, if it is determined in steps 146 and 148 that the sum of the first syndrome set for the first codeword equals zero, then it is determined that the first codeword is a valid codeword. Similarly, if it is determined in step 148 that the sum of the second

syndrome set for the second codeword equals zero, then it is determined that the second codeword is a valid codeword.

If it is determined in steps 146 and 148 that the first and second codewords are both valid codewords, then the process passes to step 150. Since it has been determined that the first and second codewords are both valid codewords, they do not need to be processed further and, in step 150, the process returns to the start, and two new codewords are input, for example by toggling the value of the control signals ol and o2, such that the new codewords are input from the second Fifo memory 82 of the first Fifo block 66, and the second Fifo memory 86 of the second Fifo block 68. If it is determined in steps 146 and 148 that the sum of the first syndrome set of the first codeword, and the sum of the second syndrome set for the second codeword, are both non-zero, the process passes to step 152. In step 152, the fourth control signal o4 is set to a first specific value, for example 1, such that the output from the first syndrome set calculation block 102 is stored in the first memory 112 as Set Ia, while the output of the second syndrome set calculation block 104 is stored in the fourth memory 120 as Set 2b.

Then, in step 154 of the process, while the first and second control signals ol, o2 are left unchanged, such that the first and second codewords are still passed to the first and second multiplexers respectively, the third control signal o3 is toggled, for example to 0, such that the first codeword is passed from the Fifo 80 to the second syndrome set calculation block 104, while the second codeword is passed from the Fifo 84 to the first syndrome set calculation block 102.

Then, in step 156, the first syndrome set calculation block 102 calculates the first syndrome set for the second codeword, while the second syndrome set calculation block 104 calculates the second syndrome set for the first codeword. The resulting calculated syndrome sets are then buffered. Specifically, in step 158, the fourth control signal o4 is toggled to the opposite value to that set in step 152, such that the calculated first syndrome set for the second codeword is directed by the demultiplexer 110 into the second memory 114 as Set Ib, while the calculated second syndrome set for the first codeword is directed by the second demultiplexer 116 into the third memory 118 as Set 2a. Now that the complete syndrome set has been calculated for each of the first and second codewords, a conventional error correction decoding process can be performed. First, in step 160, the fifth control signal o5 is set to a first specific value, for example 0, such that the first syndrome set for the first codeword (Set Ia) is directed by the fifth multiplexer 122 from the first memory 112 to the syndrome calculator output 126, while the second

syndrome set for the first codeword (Set 2a) is directed by the sixth multiplexer 124 from the fourth memory 120 to the syndrome calculator output 126.

Then, in step 162, the complete syndrome set for the second codeword can be processed. Specifically, the fifth control signal o5 is toggled, such that the first syndrome set for the second codeword (Set Ib) is directed by the fifth multiplexer 122 from the second memory 114 to the syndrome calculator output 126, while the second syndrome set for the second codeword (Set 2b) is directed by the multiplexer 124 from the third memory 118 to the syndrome calculator output 126.

Following steps 162 and 164, the conventional error correction decoding processes can be performed on the first and second codewords, respectively. When these codewords have then been fully processed, new codewords can be processed. That is, the control signals ol, o2 are both toggled, such that the codewords from the opposite Fifos 82, 86 are applied to the first and second multiplexers 88, 90, and the process can begin again.

If it is determined in steps 146 andl48 that one of the calculated syndrome sets equals zero, but that the other is non-zero, then the other syndrome set must be calculated for the codeword with the non-zero syndrome set.

Thus, if it is determined that the sum of the first syndrome set for the first codeword does not equal zero, but the sum of the second syndrome set for the second codeword equals zero, the process passes to step 166, in which the fourth control signal o4 is set to 1, such that the calculated first syndrome set for the first codeword is directed by the third demultiplexer 110 to be stored in the first memory 112 as Set Ia.

Since the first codeword must still be operated upon, the second control signal o2 is left unchanged but, in step 168, the first control signal ol is toggled, such that a new codeword stored in the Fifo 86 is applied by the second multiplexer 90 to the second demultiplexer 96.

In step 170, the third control signal o3 is toggled, such that the first codeword is now applied to the second syndrome set calculation block 104, while the new codeword is applied to the first syndrome set calculation block 102. Thus, in step 172, the second syndrome set calculation block 104 calculates the second syndrome set for the first codeword, while the first syndrome set calculation block 102 calculates the first syndrome set for the new codeword. In step 174, the fourth control signal o4 is set to 0, such that the second syndrome set for the first codeword is directed by the fourth demultiplexer 116 into the third memory 118 as Set 2a. Then, in step 176, the fifth control signal o5 is set to zero, such that the calculated first syndrome set for the first codeword is applied by the fifth

multiplexer 122 to the syndrome calculator output 126, while the calculated second syndrome set for the first codeword is applied by the sixth multiplexer 124 from the third memory 118 to the syndrome calculator output 126.

A conventional error correction decoding process can then be applied to the first codeword.

Meanwhile, the first syndrome set has been calculated for the new codeword, and it is determined in step 178 whether the sum of the first syndrome set equals zero. If it does equal zero, then, as before, it can be determined that the new codeword is a valid codeword, and no further processing is required. In that case, the process proceeds to step 180, in which two new codewords are input, by appropriate control of the first and second multiplexers 88, 90.

On the other hand, if it is determined in step 178 that the sum of the first syndrome set for the new codeword does not equal zero, then the process passes to step 182. In that case, it is necessary to calculate the second syndrome set for that new codeword, but at the same time a further new codeword can be input from the first Fifo block 66 by appropriate control of the first and second multiplexers 88, 90, and the process then continues by analogy with the process as described above from steps 168 onwards.

By contrast, if it is determined in steps 146 and 148 that the sum of the first syndrome set for the first codeword equals zero, but the sum of the second syndrome set for the second codeword is non zero, the process passes to step 184. In step 184, the fourth control signal o4 is set to 1, such that the calculated second syndrome set for the second codeword is directed by the fourth demultiplexer 116 to be stored in the fourth memory 120 as Set 2b.

Since the second codeword must still be operated upon, the first control signal ol is left unchanged but, in step 186, the second control signal o2 is toggled, such that a new codeword stored in any Fifo from the Fifo block 66 is applied by the first multiplexer 88 to the first demultiplexer 94.

In step 188, the third control signal o3 is toggled, such that the new codeword is applied to the second syndrome set calculation block 104, while the second codeword is now applied to the first syndrome set calculation block 102. Thus, in step 190, the second syndrome set calculation block 104 calculates the second syndrome set for the new codeword, while the first syndrome set calculation block 102 calculates the first syndrome set for the second codeword.

In step 192, the fourth control signal o4 is set to 0, such that the first syndrome set for the second codeword is directed by the third demultiplexer 110 into the second memory 114 as Set Ib. Then, in step 194, the fifth control signal o5 is set to 1, such that the calculated first syndrome set for the second codeword is applied by the fifth multiplexer 122 to the syndrome calculator output 126, while the calculated second syndrome set for the second codeword is applied by the sixth multiplexer 124 from the fourth memory 120 to the syndrome calculator output 126.

A conventional error correction decoding process can then be applied to the second codeword. Meanwhile, the second syndrome set has been calculated for the new codeword, and it is determined in step 196 whether the sum s2 of the second syndrome set equals zero. If it does equal zero, then, as before, it can be determined that the new codeword is a valid codeword, and no further processing is required. In that case, the process proceeds to step 180, in which two new codewords are input, by appropriate control of the first and second multiplexers 88, 90.

On the other hand, if it is determined in step 196 that the sum of the second syndrome set for the new codeword does not equal zero, then the process passes to step 198. In that case, it is necessary to calculate the first syndrome set for that new codeword, but at the same time a further new codeword can be input from the first Fifo block 68 by appropriate control of the first and second multiplexers 88, 90, and the process then continues by analogy with the process as described above from steps 186 onwards.

There is therefore disclosed a method and an apparatus that allow efficient processing of received data to calculate the required syndromes. Specifically, where it is found that t consecutive syndromes are zero, the calculation of the remaining syndromes is omitted, thereby reducing the computational load and hence the power consumption.

Moreover, this operation is performed on two codewords in parallel, in such a way that, when the remaining syndromes need to be calculated for one of those two codewords, the apparatus can still operate efficiently.