Abstract:
The invention relates to a system for transmitting data according to the frequency hopping method. The digital data, which is transmitted in suddenly changing transmission frequency hops, is encoded according to a woven code consisting of an interlinked external and internal convolution code. The data to be transmitted by hop is preferably distributed over several parallel hops sent with different frequencies.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application is a national stage application of prior International Application No. PCT/EP01/06276, filed Jun. 1, 2001, which claims the benefit of German application No. 100 29 308.5, filed Jun. 14, 2000, and German application No. 101 14 834.8, filed Mar. 26, 2001, which are incorporated herein by reference. 
     FIELD OF THE INVENTION 
     The invention relates to a system as specified in the preamble of the main claim. 
     In the transmission of digital data by the frequency hopping method, in which the data are transmitted in abruptly changing transmission frequency segments (hops), the signals are generally impaired by noise or other effects, such as fading, Doppler shift and the like. A fading drop or interference result under these circumstances in the suppression of single or even a plurality of frequency segments so that the entire information (user data and FEC redundancy) is lost. For such frequency hopping methods, it is already also known to encode the data symbols in the individual transmission frequency segments according to a so-called concatenated code comprising an outer and inner code. 
     These concatenated codes have the disadvantage that an error burst (but no independent error) is produced after incorrect decoding of the inner code. As a consequence, the decoder of the outer concatenated code generates a plurality of errors since the outer code has, as a rule, poor correction characteristics in regard to such error bursts. 
     The object of the invention is therefore to disclose a system for transmitting data by the frequency hopping method in which these disadvantages are avoided as well as possible and that guarantees as safe a data transmission as possible by the transmission channel even in the event of severe distortions. 
     SUMMARY OF THE INVENTION 
     Proceeding from a system as specified in the preamble of the main claim, this object is achieved by its characterizing features. Advantageous developments emerge from the subclaims. 
     The use of so-called woven codes, such as those described in detail, for example, in Host, S. Johannesson, R. and Zyablov, V.: “A first encounter with binary woven convolutional codes”, in Proc. International Symposium on Communication Theory and Application, Lake District, UK, July 1997 or Host, S. on Woven Convolutional Codes, Ph.D. Thesis, Lund University, 1999, ISBN 91-7167-016-5, http:/www.it.lth.se/stefanh/thesis/, guarantees, even with severe distortions due to the channel, such as fading drops, that the lost information can be recovered in the disturbed frequency segments by the encoding used. In woven codes, the decoding errors mentioned due to error bursts are very largely avoided since the error bursts generated by the decoder are distributed independently of one another between the different inner and outer codes, respectively, which results finally in independent errors in the respective other code (outer or inner code, respectively) as is explained in greater detail below by reference to examples. It has proved particularly advantageous to terminate the encoding within a transmission frequency segment in the respective frequency segment, i.e. the encoding begins with the start of the frequency segment and ends with it. This avoids the possibility that any erased frequency segment falsifies the information at the beginning or at the end of the preceding or subsequent frequency segment, respectively, the encoding in a frequency segment therefore functioning independently of the other frequency segments. The system according to the invention can be applied to all possible transmission channels, for example in the case of a so-called AWGN channel (transmission channel with additive white Gaussian noise) or even in the case of Rayleigh channels. The use of binary convolutional codes makes it possible to use, for the decoding of the outer code, so-called soft decodings or so-called iterative decodings such as are described, for example, in Johannesson R., Zigangirov, K . . . “Fundamentals of Convolutional Coding”, IEEE Press, 1999, ISBN 0-7803-3483-3. 
     In the system specified in the main claim, the entire data of a frequency segment (hop) are transmitted over a frequency segment that is continuous in terms of frequency and, therefore, disturbances, such as fading drops with flat fading or emissions by other transmitters (collisions in the case of CSMA) can erase the entire frequency segment. 
     The latter disadvantages can be eliminated at least partly by the development according to claims  30  and thereafter. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       A better understanding of the present invention can be derived by reference to the appended drawings in conjunction with the description that ensues. 
         FIG. 1  shows a diagram of the transmission of digital data by a frequency hopping method; 
         FIG. 2  shows a diagram of a known woven code; 
         FIG. 3  shows a diagram of a concatenated code; 
         FIG. 4  shows a diagram of a parallel combination of codes; 
         FIG. 5  shows a diagram of a woven code having an outer warp; 
         FIG. 6  is a diagram of a woven code with inner warp; 
         FIG. 7  is a diagram of a woven code with double warp; 
         FIG. 8  is a diagram of an encoder for outer warp, inner warp, and double warp; 
         FIG. 9  is a diagram showing a woven code with outer warp; 
         FIG. 10  shows a system of woven codes with inner warp; 
         FIG. 11  shows a system of woven code with double warp; 
         FIG. 12  shows the general distribution of information symbols and test symbols between the hops and in the hops; and 
         FIG. 13  shows the distribution of data of a frequency segment (hop) over a plurality of parallel frequency segments that are each emitted at different frequencies. 
     
    
    
     The invention is explained in greater detail below by reference to exemplary embodiments on the basis of diagrammatic drawings. 
     DETAILED DESCRIPTION OF THE INVENTION 
       FIG. 1  shows diagrammatically the transmission of digital data by the frequency hopping method. In this method, the data are transmitted in abruptly changing, temporally consecutive transmission frequency segments f 1  to f x , which may repeat in any desired sequence, from the transmitter to the receiver. As a result of fading drops or other distortions, some or a plurality of said frequency segments may be suppressed, as is shown for some segments by hatching in  FIG. 1 . The data to be transmitted are encoded according to an outer convolutional code and an inner convolutional code concatenated therewith according to a known woven code, such as is described in greater detail in the literature by Host described at the outset. The data symbols that are transmitted in a frequency segment may be interpreted mathematically as a column of a matrix, with the result that the transmission can be interpreted as a whole as encoding in the direction of the matrix columns and encoding in the direction of the matrix rows of a semi-infinite matrix. 
       FIG. 2  shows diagrammatically a known woven code comprising the concatenation of an outer and inner convolutional code without buffer. In the case of such a woven code, it is adequate for the correction of an error burst of length L if an interleaving of the L codes, which are capable of correcting an error, is used. If, in this case, each individual code is capable of correcting t-errors, the structure resulting therefrom will correct t error bursts. This is shown diagrammatically in  FIG. 3  for concatenated codes. The encoder of such a structure comprises a parallel combination of codes, as is shown in  FIG. 4 . 
     Generally, such a concatenated code with its generator matrix can be shown by the following formula:
 
 G   c =G           I L .

     This corresponds to the Kronecker product of a generator matrix of the convolutional code G having an identity matrix I of size L. 
       FIG. 5  shows the basic diagram of a so-called woven code having an outer warp, such as is produced by the concatenated combination of two convolutional codes according to  FIG. 2  and, in particular, by replacing the outer code according to  FIG. 2  by the code structure according to  FIG. 4 . The generator matrix of said code according to  FIG. 5  obeys the formula
   G   ow =( G   o               I   Lo )· G   i , 
where G ow  is the generator matrix of the woven code with outer warp, G o  and G i  correspond to the generator matrices of the outer and inner codes, and I LO  is a Lo-order identity matrix.

     This shows that, during the decoding, the error bursts generated by the decoder of the inner code are uniformly distributed between the various outer codes. This results in independent errors in the outer code. 
     If the inner code is replaced by the structure according to  FIG. 4  described in the concatenated combination of the two convolutional codes, the so-called woven code with inner warp in accordance with  FIG. 6  is produced. The generator matrix
 
 G   iw   =G   o ·( G   1               I   Li ),
 
where G iw  is the generator matrix of the woven code with outer warp. G o  and G i  correspond to the generator matrices of the outer and inner codes and I Li  is the Li-order identity matrix.

     Here, again, during the decoding, the error bursts generated by the decoder are independently distributed between the various inner codes. This again results in independent errors in the outer code. 
     If both the inner and the outer codes are replaced by the described structure according to  FIG. 4  in the concatenated combination of the two convolutional codes, the so-called woven code with double warp (twill) according to  FIG. 7  is produced. The generator matrix of said code obeys the formula
 
 G   dw =( G   o               I   Lo )·( G   i             I   Li ,
 
where G dw  is the generator matrix of the woven code with double warp, G o  and G i  correspond to the generator matrix of the outer and inner codes, I Lo  is the Lo-order identity matrix and I Li  is the Li-order identity matrix.

     In each of the said codes of the woven codes, a permutation can be implemented between the encoders of the inner and outer codes. This makes it possible, particularly in AWGN channels, to improve the correction characteristics. The corresponding diagram of the encoders for outer warp, inner warp and double warp is shown in  FIG. 8 . 
     The partitioning of the redundancy of the inner and outer codes between the rows and columns or between the consecutive frequency segments and within the individual frequency segments is explained below for the various revealed types of a woven code. A woven code with the code rate R=⅛ serves as an example of this. In this example, it is assumed that systematic convolutional codes with recursive encoding are used as outer and inner codes in all cases. 
       FIG. 9  again shows the woven code with outer warp. In the drawings, the user information items N are obliquely hatched, the test symbols of the outer code O are horizontally hatched and the test symbols of the inner code I are shown in each case as vertically hatched. 
     From the scheme mentioned at the outset of the woven code, the encoding is first performed with the test information items of the outer code in the frequency segments sent between the user information items N and, specifically, with a convolutional code having the rate R o =¼. All the frequency segments (hops) are then encoded independently of one another with an optionally terminated convolutional code having the rate R i =½. 
     Prior to encoding with the inner code, the symbols can be subjected in each hop to a permutation in various ways. The permutation cycle is T hops, i.e. the i-th hop and the i+T hop are subjected to one and the same permutation. The permutation is described, inter alia, in “Bronstein-Semendjajew Taschenbuch der Mathematik” (Bronstein-Semendjajew Handbook of Mathematics). 
     This type of encoding generates a woven code with an outer warp in modified form in which, as a departure from the classic case, the inner code is terminated in each hop. 
     Simultaneously, puncturing, known per se, of the outer code can be performed, as is described, for example, in J. Hagenauer, “Rate-Compatible Punctured Convolutional Codes (RCPC Codes) and Their Applications”, IEEE Transactions on Communications, vol. 36, No. 4, April 1988, pages 389 et seq. The code rate can be correspondingly increased by such a puncturing, known per se, and specifically to R=(⅙ ¼). 
       FIG. 10  shows the system of woven codes with inner warp. Here, the consecutive frequency segments having a convolutional code with the rate R o =½ are first encoded independently of one another. All the hops having an optionally terminated convolutional code with the rate R i =¼ can then be encoded independently of one another. 
     Further to the encoding with the inner code, the symbols in each hop can again be subjected to a permutation in different ways, the permutation cycle again being T hops. 
     This also again produces a modified woven code with inner warp in which the outer code can be terminated in each frequency segment. Regardless of the termination of the outer code, the resultant code becomes a convolutional code with the rate
 
 R   iw   =R   o   ×R   i =⅛.
 
As in the case of the outer warp, the code rate can be increased by puncturing.
 
     The incorporation of the test symbols in the frequency segments together with the information symbols can be disadvantageous in some cases, for example if frequency segments are completely or partly suppressed by fading and erased. 
     This disadvantage is avoided by the woven code with double warp, shown in  FIG. 11 , in which the test information items of the outer code  0  and the test information items of the inner code I are each transmitted in separate hops between the user information items N. 
     In the case investigated, the information symbols are written cyclically with the cycle 1/R dw  into the hops, R dw  being the rate of this structure. 
     As follows from the diagram of the encoder, the hops having a convolutional code with the rate R o =½ are first encoded independently of one another. 
     The result of such an encoding (test symbols of the outer code) is written cyclically with the cycle 1/R dw  into the corresponding hops. 
     All the hops having a plurality of convolutional codes with the rate R i =¼ are then encoded independently of one another. 
     Prior to the encoding with the inner code, the symbols in each hop can be subjected to a permutation in various ways. The permutation cycle is T hops. 
     As a result of such an encoding, a woven code with double warp is obtained. 
     The code resulting therefrom becomes, regardless of a termination of the outer code, a convolutional code having the rate
 
 R   dw   =R   o   ·R   i =⅛.
 
     As in the case of the outer warp, the code rate can be increased by puncturing. 
     The structure of the woven turbo code is achieved below. The general distribution of the information symbols and test symbols between the hops and in the hops is shown in  FIG. 12 . 
     The information symbols are written cyclically with the cycle 1/R wt  into the hops, R wt  being the rate of said structure. As follows from the diagram of the encoder, the hops having a convolutional code with the rate R o =¼ are first encoded independently of one another in the example. 
     The result of the encoding (test symbols of the outer code) are written cyclically with the cycle 1/R wt  into the corresponding hops. All the hops (only the information symbols) are then encoded independently of one another with a plurality of convolutional codes with the rate R i =⅕. 
     Prior to the encoding with the inner code, the symbols in each hop can be subjected to a permutation in various ways. The permutation cycle is T hops. 
     As a result of such an encoding, we obtain a woven turbo code. All the test symbols of both codes are distributed between the various columns. In addition, each of the individual codes has a lower rate. This is advantageous for transmission in poor channels. 
     The code resulting therefrom becomes a convolutional code with the rate 
     
       
         
           
             
               R 
               wt 
             
             = 
             
               
                 
                   
                     R 
                     o 
                   
                   · 
                   
                     R 
                     i 
                   
                 
                 
                   
                     R 
                     o 
                   
                   + 
                   
                     R 
                     i 
                   
                   - 
                   
                     
                       R 
                       o 
                     
                     · 
                     
                       R 
                       i 
                     
                   
                 
               
               = 
               
                 1 
                 / 
                 8 
               
             
           
         
       
     
     Puncturing of both or optionally of the outer and inner code produces a code with the rates 
     
       
         
           
             R 
             = 
             
               { 
               
                 
                   
                     
                       1 
                       / 
                       7 
                     
                   
                   
                     
                       1 
                       / 
                       6 
                     
                   
                   
                     
                       1 
                       / 
                       5 
                     
                   
                   
                     
                       1 
                       / 
                       4 
                     
                   
                   
                     
                       
                         1 
                         / 
                         3 
                       
                       } 
                     
                   
                 
               
             
           
         
       
     
     In addition to the cyclic and systematic partitioning of information items and test information items, it may also be advantageous, independently of the channel over which the transmission is to take place, to combine temporally hops containing information items and/or test information items. 
     An iterative turbo decoder is used for the decoding. Such decoders are known and described, for example, in Johannesson, R.; Zigangirov, K. “Fundamentals of Convolutional Coding”, IEEE Press, 1999, ISBN 0-7803-3483-3. During the decoding, the structures of the code diagrams or parallelism of the codes (outer warp, inner warp, double warp and woven turbo) and also the use of the permuters in accordance with  FIG. 8  are taken into account. 
     Advantageously, the outer and inner codes are decoded with the aid of the a posteriori probability algorithm (APP). This algorithm is likewise known and is described in Johannesson. Since the receiver knows the code structure used, it can use the knowledge about the termination of the codes to reduce the effort in the decoder. 
     If the APP is used in a sliding window version, the delay in the decoding can be minimized and adapted to the maximum permissible delay for the transmission. 
       FIG. 13  shows the distribution of the data of a frequency segment (hop) over a plurality of parallel frequency segments that are each emitted at different frequencies. 
       FIG. 13  shows this for a woven code with outer warp. The user information items N are transmitted in parallel in two frequency segments (hops) and the test symbols of the inner code of the code rate ½, likewise in two frequency segments. For subsequent considerations, it is assumed that disturbances and fading drops are equally distributed over the range in which the transmission system operates, and are also statistically independent of one another. As a rule, these assumptions apply in the case of sufficiently large frequency ranges. 
     The number of parallel frequency segments can in principle be chosen freely. Owing to the frequency hopping method, however, separate carrier synchronization and symbol clock synchronization has, as a rule, to be performed for each of said parallel frequency segments. Said synchronization requires additional information items that reduce the actual transmission rate. With too many parallel frequency segments, said transmission rate accordingly drops considerably. 
     In the method with outer warp, only an inner code is again used. In the case of transmission in a plurality of parallel frequency segments, all the user information items and the test symbols of the outer codes, which are distributed over the parallel frequency segments, are protected by said inner code. If one of the frequency segments is now disturbed, the user information that is contained in the frequency segments emitted in parallel can be recovered if the inner code has the appropriate error correction facility. This additional correction facility of the inner code generates correspondingly fewer errors in the inner decoding, with the result that the outer codes have to correct fewer errors in total and the performance of the entire arrangement is increased. The structure with outer warp according to the inner coding again corresponds to  FIG. 9 . The user data N or test symbols of the outer code disposed in the column direction are distributed, together with the test symbols of the inner code, over the frequency segments emitted in parallel. 
     In the method with inner warp, the inner codes protect the user information items emitted in the parallel frequency segments and also the test symbols of the outer code. If one of the parallel frequency segments is now disturbed, only a part of the inner code is affected. 
     Accordingly, only the affected part of the inner code has also to correct the additional errors. This helps the outer code during the decoding. The structure with inner warp is shown in  FIG. 10 . The user data disposed in the column direction and the test symbols of the outer code or the test symbols of the inner codes are distributed over the frequency segments emitted in parallel. 
     In the method with double warp, the user information items and also test symbols are transmitted in different hops. Owing to the statistical equipartitioning described above of the fading drops and disturbance, only a part of the outer codes will have to correct disturbed symbols. The structure with double warp is shown in  FIG. 11 . The user data disposed in the column direction or test symbols of the outer and inner codes are distributed over the hops emitted in parallel. 
     In the woven turbo encoding, as in the case of the double warp, the user information items, the test symbols of the outer code and also of the inner codes are transmitted in parallel frequency segments. This structure corresponds to  FIG. 12 . The user data disposed in the column direction or test symbols of the outer code and of the inner codes are distributed over the frequency segments emitted in parallel. 
     For all the code structures, this principle offers advantages over the transmission in a frequency segment that is continuous in terms of frequency. Owing to the code structure of the inner and outer warp, it can, however, be used particularly advantageously here. 
     The individual parallel frequency segments (hops) can be chosen in the frequency range with constant frequency spacing, possibly also equidistantly. If a plurality of transmitters transmit with the same method in the same frequency range and the frequency hop pattern is not orthogonal, all the parallel frequency segments may, however, be disturbed in this case. It is therefore advantageous to use a special algorithm that undertakes the distribution of the parallel frequency segments in the frequency range in such a way that such disturbances are avoided. As a rule, this algorithm will generate temporally dependent arrangements. 
     The distribution of the user and test symbols over the parallel frequency segments can in principle be chosen as desired. The allocation may optionally also be permutated temporally. Thus, for example, in the case of an arrangement with outer warp, the distribution of the user information and of the test symbols of the inner code over the individual frequency segments emitted in parallel may vary temporally. Such a permutation may likewise take place according to a special algorithm. It is also conceivable to distribute the data to be transmitted not over the parallel frequency segments, but to transmit all the data completely and simultaneously in each of the parallel frequency segments. 
     Instead of the partitioning of the data to be transmitted per frequency segment over a plurality of frequency segments sent in parallel, a simplified system is also possible in which all the data of a frequency segment are transmitted in each case on a plurality of parallel frequency segments that are sent at different frequencies. In this case, known methods could then be used in the receiver in order to recombine the data thus transmitted in frequency diversity. Thus, for example, all the parallel frequency segments (hops) could be decoded completely and in parallel and a selection could then be made according to the majority principle. Another possibility is to combine the individual frequency segments according to the principle of the maximum ratio combining and then to decode in a single decoder.