Abstract:
A system, method and machine-readable medium for pruning an S-random interleaver starting with an interleaver permutation having N elements and alternating between invalidating the last element of the interleaver permutation and invalidating the last element of a corresponding inverse interleaver permutation until the interleaver permutation has K elements, K being less than N, the method being characterized by the use of a reference vector having N flags and comprising: storing a value in an element of the reference vector corresponding to the value of the each element invalidated in the interleaver permutation.

Description:
BACKGROUND OF THE INVENTION 
   The present invention relates generally to coding systems for digital communications, and particularly to pruning methods for the obtention of S-random interleavers with a reduced size starting from an initial S-random interleaver having a larger size. 
   In the present description, following an already established practice in this field, by “interleaver” it is meant the “interleaver permutation” or “interleaver law” associated with an interleaver device in the proper sense of the word. 
   Interleavers play a crucial role in systems using turbo-codes. 
   Interleavers of the S-random type represent, as it is well-known, an optimum class of interleavers, and differently from many other permutation systems, are sufficiently robust with respect to the specific convolutional codes employed and to the puncturing rate applied to the overall code. 
   Many application systems require a great flexibility in terms of block length and code-rate, and the change of these parameters involves a corresponding modification of the interleaver size. In such cases, it is highly recommendable to obtain, by use of an algorithm, all the needed interleavers from a mother interleaver which exhibits the largest size, avoiding the need to store all the necessary permutation laws. 
   Unfortunately the known pruning techniques disclosed in the literature generally destroy the properties of S-random interleavers. 
   A pruning method is disclosed in EP 1 257 064 A and in M. Ferrari, F. Scalise, S. Bellini, “Prunable S-random Interleavers”, in Proc. IEEE Conf. Communications, Vol. 3, 2002, pages 1711-1715. 
   The pruning method disclosed in said documents provides for discarding all the elements of an initial interleaver which have a value greater than the size of the desired smaller interleaver. That technique allows to store one single interleaver and for the larger interleavers it affords (only) the same spread properties of the smaller interleaver. 
   SUMMARY OF THE INVENTION 
   It is an object of the present invention to propose a pruning method of the initially specified kind, which allows to overcome the limitations of the above-outlined prior art, permitting to obtain in general S-random interleavers with improved spread properties. 
   It can be shown, in an intuitive manner, and by means of simulations and tests, that the pruning method according to the present invention reduces in a quite less dramatic way the spread properties of the shorter interleavers, the pruning method being suitable for employment with a by far wider range of block sizes or lengths, differently from what was possible with the conventional pruning techniques. 
   In the following, different variants of the basic pruning methods will be also disclosed, each variant corresponding to a different trade-off between complexity, latency and memory requirements. 
   The invention also relates to interleaver devices which carry out the above-outlined pruning methods. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Further characteristics and advantages of the invention will become apparent from the detail description which follows, provided merely as a non-limiting example, with reference to the enclosed drawings in which: 
       FIG. 1  is a block diagram of an apparatus which can be used for carrying out a pruning method according to the present invention; 
       FIG. 2  is diagrammatic graphic representation of a start interleaver permutation and the corresponding inverse permutation as well as an associated reference (flag) vector generated in performing a pruning method according to the present invention; and 
       FIGS. 3 and 4  show diagrams comparing the performances of interleavers obtained through the method or process according to the invention, with interleavers according to the prior art. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   The pruning methods according to the invention provide better results with respect to conventional techniques, for every S-random type interleaver. However, these methods provide optimal results if applied to S-random interleavers obtained with a progressive technique of permutation generation invented by the same inventors of this application, which will be now presented herebelow. 
   In European patent application EP 1 257 064 A there was proposed an algorithm for the generation of S-random interleavers or, better stated, interleaver permutations, which, starting from a good S-random interleaver permutation of size K and spread S, creates, by extension, a larger or longer interleaver permutation, say of size N, with the same spread properties of the starting interleaver permutation. Although this may be sufficiently acceptable for a small range of interleaver sizes, this constraint may lead to poor results if one has to construct interleavers in a wide range of sizes, as this leads to poor spreading properties of the larger interleavers. 
   The incremental technique which will be now presented overcomes this limitation. While the algorithm according to the prior art in fact extracts at random an integer representing the position of the new element which is added to the interleaver, the technique which will be now described picks a number from a subset of positions that allows to improve the spread properties. 
   If we start from a K-sized interleaver with a spread S, the next step in the extension process is to add new positions until we reach a spread S+1. Thus we analyze the permutation and see which pairs of positions [i;j] and [Π(i);Π(j)] correspond to the violations that do not permit to reach a spread equal to S+1. 
   One easy way to overcome these violations is to choose an element with Π(K+1)=ψ, ψ∈[min(Π(i), Π(j))+1; max(Π(i), Π(j))], and then update all previous K elements or positions of the interleaver by incrementing of one all those greater than or equal to ψ. 
   To eliminate or break, at each step, the maximum number of violations, an interval vector A is created, which contains all position pairs causing violations of the spread properties. Each pair defines an interval, whose internal numbers are suitable for extraction; then we can use the vector A to build a second vector, defined as the position vector B, which is proportional to the attitude of each position to break spread violations. 
   The vector B is then sorted in descending order and the first element that does not introduce new spread violations is extracted. 
   This technique permits to improve the spread properties in a very fast way, and to construct interleavers with large sizes having very good spreading properties with a computational complexity that may be competitive even with the direct S-random interleaver generation. 
   The improved method for the construction of interleavers described above can be performed essentially by the algorithm disclosed herebelow in a pseudo-code formalism:
     starting from an interleaver permutation Π having a size or length K and a spread S in :
       Set dim=K and S=S in      LOOP UNTIL dim=N
           if dim is even
               build the interval vector A with the (S+1) spread violations; the intervals are [min(Π(i), Π(j))+1; max(Π(i), Π(j))]   build the position vector B   pick ψ from B, such that it does not introduce new spread violations   set Π(dim+1)=ψ   ∀k≦dim, if Π(k)≧ψ, set Π(k)=Π(k)+1   obtain the inverse interleaver Π −1      
               if dim is odd
               build the interval vector A with the (S+1) spread violations; the intervals are [min(i,j)+1; max(i,j)]   build the position vector B   pick ψ from B, such that it does not introduce new spread violations   set Π −1 (dim+1)=ψ   ∀k≦dim, if Π −1 (k)≧ψ, set Π −1 (k)=Π −1 (k)+1   obtain the interleaver Π   
               set dim=dim+1   if there are no more (S+1) spread violations set S=S+1   
           END OF LOOP   
       

   The algorithm above allows to yield a wide range of interleavers with different sizes with good spreading properties. 
   When the system at hand needs to obtain one of them “on the fly”, an easily implementable pruning algorithm is required. 
   For instance, this means that new elements have to be inserted into the interleaver permutation in a way that allows to know their position and discard them very easily. 
   According to the prior method disclosed in EP 1 257 064 A, this can be obtained for instance starting from a created N-sized interleaver and removing its last N-K positions. This, in turn, requires to use the elements of the position vector B to choose the elements Π(K+i), i=1, . . . , N−K. That is in fact the pruning rule suggested in EP 1 257 064 A, and it complies very well with the therein aimed criterion of preserving for the extended interleavers the same spread properties of the shortest interleaver. On the contrary, it has serious drawbacks in other cases and in particular when applied to interleavers having an interleaver permutation or an interleaver law obtained by means of the innovative technique described above or the algorithm presented above. 
   As it will be readily apparent form the following, the pruning method according to the present invention allows to obtain, starting from an initial S-random interleaver permutation stored in memory means and having a size N, i.e. formed of N elements, a final S-random permutation having a smaller size K&lt;N, i.e. formed of K elements, by means of successive pruning operations or steps which, starting from the initial permutation, yield the final permutation through an iterative process carried out by means of electronic processing means with memory. In successive steps of said iterative process elements selected on the basis of predetermined criteria are discarded from the initial permutation. 
   In particular, in the method according to the invention the final permutation is generated by utilizing a reference vector having a size equal to that of the initial permutation and thus comprising N elements; said reference vector being generated by said processing means in such a way that at each pruning step if the element discarded from the initial permutation has been eliminated on the basis of a predetermined criterion, one element of said reference vector is generated such that its value and its position in the reference vector are indicative of the value of the elements discarded from the initial permutation. 
   The method according to the invention can be performed in different variants, which will be described in a more detailed way in the following, to reduce the size of a large initial interleaver, named afterwards Π 0 (x), that is stored in a read-only memory (ROM), to obtain a shorter one, named Π n (x), that is stored in a reserved random-access memory (RAM) area. 
   A good number of methods according to the invention are in general composed by three tasks:
         identification of the elements to be pruned,   re-normalization, namely re-definition (scaling) of the value of part of the valid or surviving elements, and   re-compacting of the interleaver.       

   The basic pruning method according to the invention as defined above can be carried out for instance by means of the apparatus shown in  FIG. 1 , which comprises a microprocessor  1  with associated memory devices  2  and  3 . The memory devices indicated  2  are of the read-only (ROM) kind and serve to store the N-sized initial or start interleaver Π 0  and, possibly, its inverse Π 0   −1 , whereas the memory devices  3  can be either of the read-only (ROM) type or of the random-access (RAM) type and serve to store the reference or auxiliary vector(s), described in the following, and the final interleaver Π n . 
   The microprocessor  1  is coupled to random-access memory (RAM) devices  4  through an address line  5 . Said memory devices are used for implementing the algorithm for decoding the turbo-codes. Said algorithm is based on the iterative performance of a variant of the so-called BCJR algorithm by so-called SISO (Soft Input Soft Output) units: in the case of only two constituent convolutional codes, each iteration is composed of two half-iterations, in the first one of which the data are written and read in natural order from memory  4 , and in the second one of which data are written and read in the order determined by the interleaver permutation or interleaver law. 
   In the pruning methods according to the invention, in those steps which we conventionally define as “odd” steps, i.e. the steps at which a pruning operation is made onto a permutation having an odd size, the elements of the interleaver which have the highest values are discarded, whereas in those steps which we conventionally define as “even” steps, i.e. the steps in which a pruning operation is made onto an interleaver permutation having an even size, the elements having the highest position indices, namely the last elements of the permutation, are eliminated. 
   For a better understanding of the following remarks reference can be made to  FIG. 2  which gives a graphic representation of an initial interleaver permutation, indicated Π, formed of 25 elements, and, therebelow, a representation of the corresponding inverse permutation Π −1 . 
   At the end of the pruning process of the invention, as shown in  FIG. 2 , all the values discarded in the even steps and some of those deleted in the odd steps will form an end or tail group of consecutive deleted elements, while the other eliminated values will be scattered on the rest of the permutation. The pruned elements are distributed in a similar pattern also in the inverse interleaver Π −1 . 
   The thresholds which separate the end or tail groups of consecutive discarded elements in the permutation Π and in the inverse permutation Π −1 , respectively, are denoted as L 1  and L 2 . 
   In various pruning methods according to the invention the main source of complexity lies in the re-normalization and re-compacting operations performed in the innermost loops. It is possible to decrease the number of required operations avoiding to perform the above-mentioned operations for each deleted element. 
   This can be done by keeping track of the deleted elements updating the thresholds L 1  and L 2 , and building a reference or flag vector V f , which has been graphically represented by way of example in  FIG. 2 . 
   The flag vector V f  has a size N and comprises N binary elements or flags assuming each a predetermined value or state (set to “1”, for instance) when their position corresponds to the value of an element discarded from the initial permutation Π as being placed at the last position of a permutation of odd size. Such ‘set’ elements or flags of vector V f  have been indicated “x” in the representation of  FIG. 2 . 
   The values of the thresholds L 1  and L 2 , and the flag vector V f , obtained in a first phase of the pruning method, can be conveniently used in a second and a third phase for performing the re-normalisation of surviving or remaining elements of the permutation. This allows to lower significantly the overall computational complexity. 
   In the following some techniques will be described, which rely on these principles, but differing in the way they exploit the flag vector V f . A preliminary remark is necessary to analyze the average complexity of said techniques: when pruning an N-sized interleaver to obtain a K-sized one, the threshold L 1  and L 2  can be approximated as:
 
 L 1= L 2= √{square root over (KN)}   (1)
 
Algorithm A
 
   A first embodiment of the general method of the invention, that we will call now onward “Algorithm A”, is composed essentially of three main cycles. 
   In the first cycle, the flag vector V f  is computed and the thresholds L 1  and L 2  are updated:
         Set dim=N−1, L 1 =L 2 =N   LOOP UNTIL dim&lt;K   if dim is even:
           Set L 1 −L 1 −1   LOOP UNTIL Π 0  (L 1 )&lt;L 2     Set L 1 =L 1 −1   END OF LOOP   Set V f (Π 0  (LI))=1   
           if dim is odd:
           Set L 2 =L 2 −1   LOOP UNTIL V f (L 2 )=0   Set L 2 =L 2 −1   END OF LOOP   
           Set dim=dim−1   END OF LOOP       

   In the second cycle, after the permutation Π 0  is copied to Π n , the positions of the latter vector are re-normalized with the help of the de-interleaver Π 0   −1  and of the flag vector V f .
         Copy the first L 1  positions of Π 0  to Π n      Set the number of positions to be discarded DP=L 2 −K and i=L 2 −1   LOOP UNTIL DP=0   if V f (i) is set, set DP=DP−1 or else decrease Π n (Π 0   −1 (i)) by DP   Set i=i−1   END OF LOOP       

   Scanning the interleaver as described here is equal to scan it starting from the elements with the highest values and ending with the elements with the lower values. 
   Finally, in the third cycle, the permutation Π n  is re-compacted by eliminating all the elements whose value exceeds K, or, equivalently, L 2 :
         Set cnt=0 and i=0   LOOP UNTIL i=L 1     if Π n (i)&lt;L 2  set Π n (cnt)=Π n (i) and cnt=cnt+1   Set i=i+1   END OF LOOP       

   The complexity of the algorithm A can as a whole be approximated as:
 
 C= 3 N+ 3 K+ 2 √{square root over (KN)}   (2)
 
Algorithm B
 
   A variant of the basic method of the invention, defined “Algorithm B” in the following, applies the same principles of the previous one (Algorithm A), but gets rid of the de-interleaver. The re-normalization step is performed with relatively low complexity, exploiting the computations already performed for the closest previous elements. 
   In fact, the re-normalization is performed decreasing the value of the i-th element of Π 0  by a number equal to the number of “set” flags contained in V f  before the index Π 0 (i). In this case for every of the K elements of the pruned interleaver, one should scan the flag vector V f  for Π 0 (i) positions. 
   Alternatively, if D is an integer greater than zero and lesser than N, we can find amongst the D previously updated elements the one, with index i D , such that Π 0 (i D ) is closest to Π 0 (i). Then the flag vector is to be scanned only for a number of positions equal to the difference between Π 0 (i D ) and Π 0 (i), and decrease the current element of the number of flags in the said interval and of the difference between Π 0 (i D ) and Π n (i D ) 
   Therefore, firstly one has to obtain the thresholds L 1  and L 2  and the flag vector V f , as in the first cycle of the Algorithm A, and then the first L 1  elements of Π 0 , as in the second cycle of the Algorithm A. Then Π n  is re-normalized:
         Set i=0   LOOP UNTIL i=L 1     If Π n (i)&lt;L 2  find in the D previous elements the i D -th element such that Π 0 (i D )&lt;L 2  and that the difference Δ=Π 0 (i D )−Π 0 (i) is minimum.   Set N f =0   if Δ&gt;0
           if Δ&gt;Π 0 (i), count N f , i.e the number of flags in V f  in the interval [0; Π 0 (i)] and set Π n (i)=Π n (i)−N f      if Δ≦Π 0 (i), count N f , the number of flags in V f  in the interval [Π 0 (i); Π 0 (i)+Δ] and set Π n (i)=Π n (i)+N f +Π n (i D )−Π 0 (i D )   
           if Δ&lt;0
           if −Δ&gt;L 2 −Π 0 (i), count N f , i.e. the number of flags in V f  in the interval [Π 0 (i); L 2 ] and set Π n (i)=Π n (i)+N f +K−L 2     if −Δ≦L 2 −Π 0 (i), count N f , the number of flags in V f  in the interval [Π 0 (i)+Δ; Π 0 (i)] and set Π n (i)=Π n (i)   N f +Π n (i D )−Π 0 (i D )   
           Set i=i+1   END OF LOOP       

   Finally, in the third cycle the re-compacting step is performed as already previously described. The overall complexity of this variant of the method can be approximated as: 
   
     
       
         
           
             
               
                 C 
                 = 
                 
                   
                     
                       K 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       N 
                     
                     
                       2 
                       ⁢ 
                       
                         ( 
                         
                           1 
                           + 
                           D 
                         
                         ) 
                       
                     
                   
                   + 
                   
                     2 
                     ⁢ 
                     KD 
                   
                   + 
                   
                     3 
                     ⁢ 
                     N 
                   
                   + 
                   
                     3 
                     ⁢ 
                     K 
                   
                   + 
                   
                     2 
                     ⁢ 
                     
                       
                         K 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         N 
                       
                     
                   
                 
               
             
             
               
                 ( 
                 3 
                 ) 
               
             
           
         
       
     
   
   Unlike Algorithm A, this variant does not need the de-interleaver Π 0   −1  so a memory of 2N is required. 
   Algorithm C 
   This variant of the method according to the invention has a complexity that can be lowered to that of Algorithm A by trading-off a small quantity of additional memory. In the previous variant (Algorithm B) the re-normalization step is performed exploiting the information implicitly present in the updated values of the neighbouring elements. In this variant, defined Algorithm C, we construct a small vector of (NP) elements (with P&lt;&lt;1) named V p : the vector V p (i) contains the number of flags set in V f  in the interval [0; i(1+└L 2 /(NP)┘)], where └x┘ is the integer part of x. Then the flag vector V f  has to be scanned, for each of the K elements of the pruned interleaver, in the worst case for L 2 /NP elements. 
   Then, as in the preceding two algorithms, we have to obtain the thresholds L 1  and L 2  and the flag vector V f  and to copy to Π n  the first L 1  elements of Π 0 . 
   Thereafter in the second cycle we construct the vector V p :
         Set i=0 and N f =0   LOOP UNTIL i=L 2     if V f (i)=1 set N f =N f +1   if (1+└L 2 /(NP)┘) divides i, set V p (i/(1+└L 2 /(NP)┘))=N f      Set i=i+1   END OF LOOP       

   In the successive cycle, the vectors V p  and V f  are exploited to perform the re-normalization step:
         Set i=0   LOOP UNTIL i=L 1     Set N f =0   If Π n (i)&lt;L 2 
           Compute k=Π n (i)/(1+└L 2 /(NP)┘) and round it to the nearest integer m   if m=NP, set m=m−1   if k≧m, compute the number of flags N f  in V f  in the interval (m(1+└L 2 /(NP)┘); Π 0 (i)) and set Π n (i)=Π n (i)−N f −V p (m)   if k≦m, compute the number of flags N f  in V f  in the interval (Π 0 (i); m(1+└L 2 /(NP)┘) and set Π n (i)=Π n (i)+N f −V p (m)   
           Set i=i+1   END OF LOOP       

   In the last loop the usual recompaction steps are carried out. 
   The overall average complexity of the algorithm C is 
   
     
       
         
           
             
               
                 C 
                 = 
                 
                   
                     
                       K 
                       ⁢ 
                       
                         
                           K 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           N 
                         
                       
                     
                     
                       2 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       NP 
                     
                   
                   + 
                   
                     3 
                     ⁢ 
                     N 
                   
                   + 
                   
                     3 
                     ⁢ 
                     K 
                   
                   + 
                   
                     3 
                     ⁢ 
                     
                       
                         K 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         N 
                       
                     
                   
                   + 
                   NP 
                 
               
             
             
               
                 ( 
                 4 
                 ) 
               
             
           
         
       
     
   
   The total memory required by this algorithm amounts to (2+P)N; it is easy to deduce from the above expression of the complexity that if P is increased, i.e. if the memory requirements grow, the complexity becomes lower. 
   Algorithm D 
   If extra cycles, i.e. operations of reading non-valid elements of the initial permutation, are tolerated, the traditional pruning method according to EP 1 257 064 A requires no beforehand computations but only to compare every element of the original interleaver with the new interleaver size. While in the first semi-iteration the SISO module reads and writes data following the natural order of the addresses from the first K positions of the memory device, in the second half-iteration the data are read and written from the said memory device in the order determined by the interleaver and in that phase every element of the initial permutation greater than K is ignored. Clearly, no RAM is required. Since the elements to be discarded are scattered on the whole length of the interleaver, in the worst case all the interleaver has to be scanned in order to perform interleaving. 
   In a first variant of the method according to Algorithm C, denoted as Algorithm D, only the steps necessary to obtain L 1 ,L 2  and the vector V f  are performed, and, while computing V f , also the positions discarded in the odd steps are considered. Thus the elements of the flag vector V f  take a predetermined value (for instance set to “1”) when their position corresponds to the value of an element discarded from the initial permutation. In the first semi-iteration the SISO module reads and writes data following the natural order of the addresses avoiding the i-th position if V f (i) is “flagged”. Similarly, in the second semi-iteration the data are read and written in the order of the initial permutation, avoiding the Π 0 (i)-th address if the corresponding element V f (Π 0 (i)) is “flagged”. 
   It is not necessary to scan the interleaver in its entire length, because, as previously explained, the last elements are discarded, so the number of extra-cycles is somewhat reduced, with respect to the previous case. 
   Algorithm E 
   A further variant of the method defined above as Algorithm C, here denoted as Algorithm E, avoids the computations each time necessary to obtain the flag vector V f , using a vector of N integers, named V aux , stored in a ROM and containing the same information of V f . For each flag set to 1, we store the step, i.e. the interleaver size or length, during which that position was flagged, so that, when writing/reading in natural (scrambled) order, the i-th address is discarded if V aux (i) is greater than K, and, similarly, when writing/reading in scrambled order, the Π 0 (i)-th address is discarded if V aux (Π 0 (i)) is greater than K. 
   We can now summarize the characteristics of the different pruning techniques that we have described so far. Their complexity and their memory requirements are summarised in the following Table. 
   
     
       
             
             
             
             
             
             
           
         
             
                 
             
             
               PRUNING 
                 
               RON 
               RAM 
               RAM 
               Extra- 
             
             
               METHOD 
               COMPLEXITY 
               Integers 
               Integers 
               Bits 
               cycles 
             
             
                 
             
           
           
             
               EP 1 257 064 A 
               N + K 
               N 
               N 
               0 
               0 
             
             
                 
             
             
               Algorithm A 
               
                 
                   
                     
                       
                         3 
                         ⁢ 
                         N 
                       
                       + 
                       
                         3 
                         ⁢ 
                         K 
                       
                       + 
                       
                         2 
                         ⁢ 
                         
                           
                             K 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             N 
                           
                         
                       
                     
                   
                 
               
               2N 
               N 
               N 
               0 
             
             
                 
             
             
               Algorithm B 
               
                 
                   
                     
                       
                         3 
                         ⁢ 
                         N 
                       
                       + 
                       
                         3 
                         ⁢ 
                         K 
                       
                       + 
                       
                         2 
                         ⁢ 
                         
                           
                             K 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             N 
                           
                         
                       
                       + 
                       
                         2 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         kD 
                       
                       + 
                       
                         kN 
                         
                           2 
                           ⁢ 
                           
                             ( 
                             
                               1 
                               + 
                               D 
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               N 
               N 
               N 
               0 
             
             
                 
             
             
               Algorithm C 
               
                 
                   
                     
                       
                         3 
                         ⁢ 
                         N 
                       
                       + 
                       
                         3 
                         ⁢ 
                         K 
                       
                       + 
                       
                         2 
                         ⁢ 
                         
                           
                             K 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             N 
                           
                         
                       
                       + 
                       NP 
                       + 
                       
                         
                           K 
                           ⁢ 
                           
                             
                               K 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               N 
                             
                           
                         
                         
                           2 
                           ⁢ 
                           NP 
                         
                       
                     
                   
                 
               
               N 
               (1 + P) N 
               N 
               0 
             
             
                 
             
             
               EP 1 257 064 A 
               0 
               N 
               0 
               0 
               N − K 
             
             
                 
             
             
               Algorithm D 
               
                 
                   
                     
                       
                         
                           7 
                           ⁢ 
                           N 
                         
                         2 
                       
                       - 
                       
                         
                           3 
                           ⁢ 
                           K 
                         
                         2 
                       
                       - 
                       
                         2 
                         ⁢ 
                         
                           
                             K 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             N 
                           
                         
                       
                     
                   
                 
               
               N 
               0 
               N 
               
                 
                   
                     
                       
                         
                           K 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           N 
                         
                       
                       - 
                       K 
                     
                   
                 
               
             
             
                 
             
             
               Algorithm E 
               0 
               2N 
               0 
               0 
               
                 
                   
                     
                       
                         
                           K 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           N 
                         
                       
                       - 
                       K 
                     
                   
                 
               
             
             
                 
             
           
        
       
     
   
   In the diagram shown in  FIG. 3 , which illustrates the frame error rate (FER) as a function of E b /N 0 , where E b  is the energy per bit and N 0  is the spectral density of the Gaussian white noise, there are compared the characteristics of two S-random interleavers having a length of 640, obtained starting from an S-random interleaver generated by a standard technique with a length of 32768 and a spread S=195, with a standard pruning technique and with the new method, with an interleaver specially designed for that same length, and with the interleaver proposed by the UMTS standard. 
   Similarly, in  FIG. 4  there are compared the features of two S-random interleavers of length 5120 obtained starting from an S-random interleaver generated by the standard technique, with a length of 32768 and a spread S=195, with the standard pruning technique and the new method, with an interleaver specially designed for that length and with the interleaver proposed by the UMTS standard. 
   Naturally, the principle of the invention remaining the same, the form of embodiment and the particulars of construction can be widely modified with respect to what has been described and illustrated by way of non-limiting example, without departing from the scope of the invention as defined in the annexed claims.