HIGH PERFORMANCE INTERLEAVING FOR OFDM The present invention relates to a method of optimizing a spread of sub-carriers within an overall frequency band used to modulate a set of contiguous bits for transmission of a plurality of symbols. Furthermore, the present invention re ^¬ lates to an interleaving device for optimizing the spread of sub-carriers used to modulate a set of contiguous bits for transmission. Such interleaving device can be used in conjunction with an encoder for providing a convolutional code.

High spectral efficiency digital modulation in a multipath environment is commonly implemented using orthogonal fre ^¬ quency division multiplex. This approach divides the avail ^¬ able bandwidth for transmission of the signal into a large number of equi-spaced sub-carriers, wherein the individual sub-carriers are modulated. In a frequency-selective fading multipath environment, some of the sub-carrier frequencies may experience deep fading. This fading is usually mitigated by the applications of forward error correction coding. This is usually accompanied by an interleaver whose purpose is to spread the positions of the errored bit throughout the code, thereby potentially greatly improving its performance. In many OFDM (Orthogonal Frequency Division Multiplex) applica ^¬ tions the channel fading has low correlation across the fre ^¬ quencies while it may have relatively high correlation across the OFDM symbols, particularly if the ends of the link are static or moving slowly relative to the correlation distance of the channel (i.e. related to its wave length) .

Interleavers are desirable that have a good spread of fre ^¬ quency over the "memory" of the code (usually relating to the length of the shift register of the encoder and the rate of the code) whilst providing reasonable time spread, particu ^¬ larly for irregular bursts. Such irregular bursts can arise, for example, when some OFDM symbols contain pilot (a priori known) sub-carriers and others do not.

Previous solutions to the above interleaver design have gen ^¬ erally involved a measure of "hand crafting" and experimenta ^¬ tion to find interleaver structures that provide characteris ^¬ tic that approximate to the requirement. This may be practi- cal where only a small number of different burst structures are required. However, the process can become unwieldy where a large number of burst structures must be provided for.

In view of that the object of the present invention is to provide a method which allows for automatically generating an interleaver for any burst structure.

According to the present invention this object is solved by a method of optimizing a spread of sub-carriers within an over- all frequency band used to modulate a set of contiguous bits for transmission of a plurality of symbols, the overall fre ^¬ quency band being divided into a pregiven number of consecu ^¬ tively positioned frequency sub-bands, and each sub-carrier being assigned to one of said frequency sub-bands, including - step a: providing a plurality of symbol number/sub- carriers cells each assigned to a specific symbol number of said symbols and a specific one of said sub-carriers,

- step b: randomly assigning one of a pregiven number of

bits to one of said symbol number/sub-carriers cells each, thus obtaining a first set of symbol number/sub-carriers cells for the pregiven number of bits, wherein each of said bits has its own specific position within the overall frequency band,

- step c: computing a first metric of spread of the posi- tions of the bits within the overall frequency band for the first set of symbol number/sub-carriers cells, - step d: swapping the symbol number/sub-carriers cell of one of said bits randomly with another one of said symbol number/sub-carriers cells thus obtaining a second set of symbol number/sub-carriers cells for the pregiven number of bits,

- step e: computing a second metric of spread of the posi ^¬ tions of the bits within the overall frequency band for the second set of symbol number/sub-carriers cells,

- step f: using said second set of symbol number/sub- carriers cells if the second metric represents a more uni ^¬ form spread of the sub-carriers within the overall fre ^¬ quency band than the first metric, otherwise using said first set of symbol number/sub-carriers cells. Furthermore, according to the present invention there is pro ^¬ vided an interleaving device for optimizing a spread of sub- carriers within an overall frequency band used to modulate a set of contiguous bits for transmission of a plurality of symbols, the overall frequency band being divided into a pre- given number of consecutively positioned frequency sub-bands, and each sub-carrier being assigned to one of said frequency sub-bands, the interleaving device being designed to carry out the following steps

- step a: providing a plurality of symbol number/sub- carriers cells each assigned to a specific symbol number of said symbols and a specific one of said sub-carriers,

- step b: randomly assigning one of a pregiven number of

bits to one of said symbol number/sub-carriers cells each, thus obtaining a first set of symbol number/sub-carriers cells for the pregiven number of bits, wherein each of said bits has its own specific position within the overall frequency band,

- step c: computing a first metric of spread of the posi ^¬ tions of the bits within the overall frequency band for the first set of symbol number/sub-carriers cells,

- step d: swapping the symbol number/sub-carriers cell of one of said bits randomly with another one of said symbol number/sub-carriers cells thus obtaining a second set of symbol number/sub-carriers cells for the pregiven number of bits,

- step e: computing a second metric of spread of the posi ^¬ tions of the bits within the overall frequency band for the second set of symbol number/sub-carriers cells,

- step f: using said second set of symbol number/sub- carriers cells if the second metric represents a more uni ^¬ form spread of the sub-carriers within the overall fre ^¬ quency band than the first metric, otherwise using said first set of symbol number/sub-carriers cells.

Advantageously the interleaving of the sub-carriers may be performed automatically wherein the spread of the sub- carriers over the total frequency band is optimized. This is accomplished by randomly assigning one of a pregiven number of bits to one of said symbol number/sub-carriers cells each, computing a metric of spread within the overall frequency band for the bits, swapping at least one of the sub-carriers and again computing the metric of spread. If the spread is better before swapping the originally organized symbol num ^¬ ber/sub-carriers cells are taken. If not, the organization with the swapped sub-carrier is taken. Thus, the spread of the sub-carriers is optimized. The steps c to f may be repeated once or several times. Each time these steps are repeated, a further optimization may take place.

According to a specific embodiment for computing the metrics of spread in steps c and e a set of regularly spaced refer ^¬ ence frequencies is provided, the sub-carriers are positioned in a frequency ascending order and the respective metric is computed on the basis of a sum of values relating to dis ^¬ tances, each distance representing the interval between one of said sub-carriers and a corresponding one of said refer ^¬ ence frequencies. Such regularly spaced reference frequencies guarantee that the sub-carriers are spread over the spectrum uniformly . The set of reference frequencies may be provided starting and/or ending with a gap to the respective edge of the over ^¬ all frequency band. This means that the first reference fre- quency and the last reference frequency are not positioned directly at the edge of the overall frequency band. The ad ^¬ vantage of such reference frequency structure is that the structure as such may be shifted for further optimization. Additionally, for obtaining the sum of values a mean of all distances may be subtracted from each distance. Thus, the ab ^¬ solute position of the reference frequencies has less effect.

Moreover, for computing the metrics of spread in steps c and e a mean frequency of said overall frequency band may be pro ^¬ vided and the metric may be computed on the basis of the standard deviation of the sub-carriers from the mean fre ^¬ quency. If the standard deviation is high, the distribution of the sub-carriers is also high. However, the uniformity of the spread may be less than in the above case where regularly spaced referenced frequencies are used. However, the use of the standard deviation only demonstrate that any metric of spread can be utilized for broadly positioning the sub- carriers in the total frequency band.

Specifically, a coding method may include one of the above methods, wherein each sub-carrier is assigned to a separate bit of a code, respectively. Thus, the inventive method of optimizing a spread of actually used sub-carriers can be em- ployed for coding methods, specifically for convolutional codes .

The code may be used for OFDM modulation. Such modulation technique is widely spread in the field of data transmission, e.g. DSL-technique or DVB-T standard. Convolutional codes have a so-called "memory". The method of the present invention can be used to obtain an optimized spread of sub-carriers over the memory of such code. The present invention will now be explained in further detail by referring to the attached figures showing: a diagram for computing metrics of spread for a plurality of entries in a code memory;

a frequency diagram of actually used frequencies for transmitting bits of a symbol;

a diagram of time/frequency indices and

the indices of FIG 3 randomly re-ordered. The following embodiments are preferred examples of the pre ^¬ sent invention.

Commonly orthogonal frequency division multiplex (OFDM) is used for digital modulation in a multipath environment. A convolutional code may be employed for realizing the digital modulation. In the example of FIG 1 the convolutional code has a memory span S equal to 9. One column in FIG 1 repre ^¬ sents the sub-carriers actually used for nine bits of a sym ^¬ bol time. Each column represents another symbol time.

In the present example the number of "symbol number/sub- carrier cells" is 100. Thus, for the convolutional code there are one hundred different symbol times. At symbol time "0" the shift register of the encoder includes bit "0" as well as bit "1" to bit "4" and bit "96" to bit "99". At bit time "1" the shift register includes bit "1" as well as bit "2" to bit "5" and bit "97" to bit "0". The further register entries at later symbol times may be depicted from FIG 1.

A frequency f (j (i) ) , specifically a sub-carrier, is assigned to each bit. The number "i" inside each of the frequency de ^¬ scriptors f (j (i) ) is the index of the bits in the order that they preferably came out of a FEC (Forward Error Correction) encoder. Thus, for example, f (j (4)) is the sub-carrier frequency used to transmit the fifth encoded bit (fifth not fourth, because counting is started at zero) . Function j represents a random function. This means that bit "0" is ran- domly assigned to number 34, for instance. Bit "1" may be randomly assigned to number 78. Function f represents a look up table, for instance. In the look up table each number is assigned to a specific frequency/sub-carrier . For each symbol time k a metric of spread M (k) is calcu ^¬ lated. The goal is now to spread the sub-carriers as uni ^¬ formly as possible.

For this goal an interleaver is proposed which is generated by optimizing an initial interleaver that is generated randomly. The principle is to swap interleaver entries in order to improve the spread of frequencies over the memory of the code. This is accomplished by generating the metric for spread. This metric has an inverse relationship with the spread i.e. the better the spread, the smaller the metric. The generation of the metric is illustrated in FIG 2.

The diagram illustrates a case where 64 "symbol number/sub- carrier cells" 1 are available. All these symbol number/sub- carrier cells 1 are arranged in an overall frequency band available for transmission. Here the overall frequency band starts at minimum frequency sub-band fi and ends at maximum frequency sub-band f e4 . In the present example a spread of the symbol number/sub- carrier cells is desired over a memory period of 8 bits (the memory size of the code is not limited to 9 as in FIG 1 but may have any appropriate size, specifically 8 bits in the ex ^¬ ample of FIG 2) .

At the specific symbol time of FIG 2 sub-carriers fi2, f n , f ₂ 3, f ₂ 9, f42 _/ f49 _/ f59 and 62 are used for bit transmission. They represent the actually used frequencies at the present symbol time, i.e. for the actual symbol number.

A set of reference frequencies 2 has been set up, uniformly spaced, over the range of frequencies shown as vertical thick lines in FIG 2.

The bits are not generally associated with those frequencies in ascending order of frequency. Nevertheless, the metric for spread is computed preferably based on ascending order of frequency. For each actual frequency, i.e each sub-carrier, in turn, its distance, d±, from a corresponding reference frequency in turn is computed i.e. beginning on the left side the distance of the first sub-carrier fi2 from the first ref- erence frequency 2 (most left one) is di . The distance be ^¬ tween the second sub-carrier f _i7 to the second reference fre ^¬ quency 2 is d2 etc.

In the present embodiment the metric for spread is based on the sum square of d± . Other embodiments may use for example the standard deviation from a mean frequency as metric for spread. A refinement subtracts the mean of d± before perform ^¬ ing the sum square. It is straightforward to appreciate that a low value of the metric indicates that the frequencies are well spread over the range of the frequencies, whereas a high value indicates a clustering of frequencies. The basic prin ^¬ ciple is to generate the metrics for bits around every bit position and search for the largest metric. Interleaver positions related to that bit position are swapped with randomly selected alternative bit positions. If the overall largest metric reduces, the swap is accepted. If not, the status quo is restored.

A specific algorithm for optimizing a spread of actually used sub-carriers is presented in more precise terms in the fol ^¬ lowing steps: 1. Create a numbering, i , with elements {O..N - ΐ} , where N is the total number of independent symbol number/sub-carrier cells (N=100 in the example of FIG 1, N=64 in the example of FIG 2 and N=44 in the example of FIGs 3 and 4) . Determine the associated set of sub-carrier frequencies, /, with elements { f(0), f(\)..f(N - \) } in units of number of sub-carriers from the minimum frequency sub-carrier. The ordering is arbitrary but the most convenient ordering runs up through the available sub-carriers SC in the first OFDM symbol S I then up through the available sub-carriers SC in the second OFDM symbol S2, and so on. In the example of FIG 3 , there are 13 sub- carriers SC and 4 OFDM symbols S I to S4. The symbols S I to S4 are arranged in time one after another. Each symbol includes 13 bits and each bit is transported in one symbol number/sub- carrier cell SSC. The first pair of OFDM symbols S I and S2 contain pilots P, shown shaded. The indices count up through the sub-carrier frequencies, jumping over the pilots, passing on from each OFDM symbol to the next. Each index constitutes an address of a symbol number/sub-carrier cell SSC.

2. Pseudo-randomly create a re-ordering, j , of i with elements {j(0), j(\)..j(N - 1) }. From this we can determine the result ^¬ ing order of frequencies, fs with entries

{ ^' (0))>/ ^' (l))"/ ^' (N ^_ 1)) }· I-e. a random ordering, j, is created for the initial interleaver. As an example we have

j = 31, 39, 21, 33, 34, 5, 2, 15, 10, 29, 32, 6, 37, 41, 27, 16, 40, 13, 7, 4, 28, 20, 24, 36, 30, 26, 25, 42, 18, 43, 14, 0, 35, 22, 1, 3, 17, 23, 38, 12, 8, 19, 9, 11 Each successive value of j is the frequency/time index to be used for each successive bit from the encoder.

FIG 4 shows an illustration of the bit indices assigned to each symbol number/sub-carrier cell SSC.

Note that the order of the bit position in frequency and time is the inverse of the order j. Thus we see that, for example, the first bit is assigned to the lowest frequency on the last OFDM symbol (index 0) . We can understand this because, the first value of j is 31. In FIG 3, the position of symbol num ^¬ ber/sub-carrier cell SSC 31 is on the lowest frequency on the last OFDM symbol S4. Similarly, the second bit (index 1) is assigned to the ninth frequency of the last OFDM symbol S4. The third bit (index 2) is assigned to the fourth frequency on the third OFDM symbol S3 and so on.

Taking the sequence of bits in order we can now examine the frequencies and times that they occupy. For example, we con ^¬ sider the first 10 bits, i.e. bit number 0 to 9 (in a later step we consider the 10 bits from bit number 1 to 10, and so on) . The resulting frequencies and times are shown in the following table, where the time value corresponds to the sym ^¬ bol number.

The frequencies are the absolute frequencies - i.e. they cor ^¬ respond to the column of numbers to the right of the fre ^¬ quency arrow in FIG 3 and 4. The frequencies in the column are those frequencies over the 10 bits for which the spread should ideally be as great as possible. When we swap entries for frequencies, we carry with those entries their associated times .

3. We seek to make the spread of frequencies over the period of the memory of the code, S, as uniform as possible. For this we will re-use the generic interleaver over the different bit positions within each QAM symbol so this uniformity must be maximised over all sets of S bits defined cyclically over all available sub-carriers and symbols. Let j _k ^T _s be the set of S indices from j(mod(k - ((S - 1) / 2),N)) to

j(mod(k + ((S - V)/2), N)) , with entries {j _k ^T _s (0)..j _k ^T _s (S -\) } assuming that S is odd. We then obtain the set of frequencies f _ks with elements f{j _k ^T ) {j _k ^T _s {\)..f{j _k ^T _s {S-\)) }. For every value of k, we want to maximise the spread of frequencies in f _ks , where k represents the symbol time.

4. For each value of k, we compute a metric for the spread of frequencies in f _k ^T _s as follows: First sort the frequencies into ascending order to obtain f _k ^T _s ^Sorted . We also define a set ofS frequencies regularly spaced over the full available bandwidth, f _mF . Using this we compute the sum square difference as a frequency spread metric:

■ The smaller the metric value, the more uniformly the frequencies are spread over the interval, S . The complete set of metrics is vector M .

5. Search over all entries in vector M for the largest en- try. This is the position in the interleaver sequence that is currently in the most need of improvement. Once this is found, also find the entry in this expression for M(k) that is largest. For example, M(2) my be the largest metric of all metrics. Within the sub-carriers of symbol time k=2, for ex- ample, the fourth bit has the largest distance to the fourth reference frequency. This is the entry, for which a change could most benefit the spread of frequencies for the selected value of k . Once this has been found, randomly select an ^¬ other entry in the sequence, j and swap their positions e.g. the fourth bit position of the third column in FIG 1, i.e. bit "1" is swapped with randomly determined bit "33" meaning that f(j(l)) is swapped with f(j(33)). Thus, in the wording of the claims a new set of second positions of the sub- carriers is generated. Next re-compute vector * following the change, i.e on the basis of the new set of second posi ^¬ tions of the sub-carriers. Note that it is only necessary to re-calculate the ^s values around both the swapped positions. In the example of FIG 2 distance di is the largest one. Thus, sub-carrier fi2 should be swapped randomly.

6. If the minimum value of vector M has reduced then retain the change. If not then try with a different randomly se ^¬ lected swap-value. Once the minimum value has reduced, the process of step 5 can be repeated for the position of the new minimum value. The above steps should be continued for a large number of repetitions.

The above process is directly applicable to modulation that encodes a single bit in every symbol number/sub-carrier cell. The process can be extended to larger constellation sizes. Suppose we have a constellation size of ^cs . This can encode Q = log ₂ (CS) bits in each symbol. Typically these 0 bits will have different reliabilities depending on the distances be ^¬ tween constellation points that affect each bit. A good in- terleaver will mix the different reliability bits over the period of the memory of the code.

The proposed extension to the interleaver generation procedure to allow for >lbps/Hz modulation is as follows. First perform the previous algorithm based on 1 bit in every symbol number/sub-carrier cell. Also provide an ordering of the bits encoded in each symbol/sub-carrier cell. For example, a good ordering for 64 QAM might be encoded for the bits on the I channel first in order most reliable, least reliable and me ^¬ dium reliable and then repeat the process for the bits on the Q channel. The ordering is then repeated enough times for one bit to be available in each of the symbol/sub-carrier cells.

On a first pass each successive bit at the output of the en ^¬ coder is assigned to successive symbol number/sub-carrier cells from the initial interleaver generation algorithm with a modulation bit position derived from the repeated ordering described above. Upon completion of this process the process is repeated, this time using a bit cyclical rotation of the repeated pattern of bit assignments. This is repeated Q times, until every bit position in every symbol number/sub- carrier cell has been assigned.

This description of the algorithm does not exclude alterna- tives, provided the fundamental principle is retained.

Considered alternatives include:

Generate the metric without subtracting the mean of the distances .

Use a spread of reference frequencies that does not extend to the edges of the available band. This could be benefi ^¬ cial in providing a more uniform spread. However, the preferred approach does not extend to the edges since a large spread may be as important as a uniform spread.

Variation in the selection of the candidate for updating are permitted. For example the algorithm may become

"stuck" searching for an improvement on particular bit position. Modifications to the algorithm to detect this (e.g. exceeding a threshold of unsuccessful attempts to reduce the metric associated with that bit position) might, for example, randomly select from other bit posi ^¬ tions whose metric is either at or close to the maximum metric value.

Advantageously, the method for generating an interleaver de- scribed above provides excellent frequency spread across the memory of the code. It allows the automatic generation of an interleaver for any burst structure regardless of how irregu ^¬ lar .