DE102008029623A1 - Interleaver e.g. intra-row almost rectangular interleaver, for use in e.g. turbo encoder for scrambling information word, has interleaver stage for reading columns, and for arranging digits of row to one another without gap - Google Patents

Abstract

The interleaver has an interleaver stage for line-by-line arrangement of binary digits of information word in multiple rows and columns. Another interleaver stage scrambles the digits of one of the rows with a gap by interchanging two digits of the row, such that a position of the gap remains unchanged, in order to obtain a scrambled row, and to replace the row by the scrambled row. The former interleaver stage reads columns in a column by column manner, and arranges digits of the row to one another without the gap, to obtain a permuted information word. Independent claims are also included for the following: (1) a method for scrambling an information word (2) an index generator for generating an output index based on an input index of a number of columns (3) a computer program having instructions to perform a method for scrambling an information word.

Description

The The present invention relates to interleavers such as, for example in the field of information and coding technology for scrambling to be used by information.

in the For example, interleavers are used in conventional technology used in data transmission. Often there will be Transmit binary digits in the form of transmit symbols, then the transmission, z. B. over a Mobile channel, to be disturbed. Because of a fault mostly several consecutive symbols are affected, man also speaks of so-called bundle errors, scrambling techniques come to Commitment. This means that in an original information word individual places are scrambled so that this at the transmission are no longer consecutive. This As a result, when burst errors occur, and subsequent reverse scrambling, the bundle errors be torn apart, and so on the information word to distribute. These technologies are also used in the Storage of data, eg. B. in audio CDs used. Ideally the burst errors occurring are torn apart and thus lead to individual errors that are correctable. To scramble, or throw back so-called interleaver used.

In communications engineering, error-correcting codes are used to protect against transmission errors. For example, convolutional encoders, block encoders, etc. are used here. Turbo codes are one of the most powerful code classes and their ability to correct transmission errors far exceeds that of convolutional codes, cf. z. B. Claude Berrou, Alain Glavieux, and Punya Thitimajshima: "Near Shannon-Limit Error-Correcting Coding and Decoding: Turbo Codes", Intern. Conf. to Communication, pages 1064-1070, 1993 ,

Turbo code interleavers are an integral part of turbo encoders, as well as the associated turbo decoder. The 11 illustrates a schematic block diagram of such a turbo coder 1100 , The turbo coder 1100 has a 1st component encoder 1105 , a turbo code interleaver 1110 , a 2nd component encoder 1115 and a puncturer 1120 on. An information word, ie a vector consisting of information bits, which can be specified, for example, by an index range from 0 to Infoword_Len-1, where Infoword_Len corresponds to the word length, is encoded by placing a 1st copy directly to the puncturer 1120 , a 2nd copy of the vector to the 1st component encoder 1105 and a 3rd copy of the Turbo code interleaver 1110 is supplied. The turbo code interleaver 1110 permutes the bits of this sector, ie it rearranges these bits or digits, changes their order and gives the thus permuted vector of the same length Infoword_Len to the 2nd component encoder 1115 further.

Both component encoders 1105 and 1115 are usually the same and represent a recursive convolutional encoder which provides at least one parity bit per input bit, possibly even several, at its output or its outputs. In the 11 are each two parity bits for the two component encoders 1105 and 1115 shown.

The 12 shows an example of a component encoder that may be implemented as a convolutional encoder, for example. The 12 shows an example of a recursive convolutional encoder with 2 parity bits per input bit and a memory length of 3. The 12 shows 3 flip-flops 1200 . 1205 and 1210 , which are linked together via summation elements and coupling branches. That in the 12 example shown shows that for an input bit, the input 1215 is present, in each case 2 parity bits at the outputs 1220 and 1225 be issued. Furthermore, the 3 flip-flops correspond 1200 . 1205 and 1210 3 one-bit memories that realize the memory length of 3. Each of the 3 flip-flops 1200 . 1205 and 1210 stores one bit, ie binary "0" or "1", for one time unit and outputs it at the respective output. At the beginning of the next time unit, the bit present at the input of a flip-flop is stored and then output. Thus, the arrangement in the 12 be regarded as a conventional shift register. The plus symbols mark the summation elements, ie those nodes to which binary additions are made, the binary addition corresponding to the binary exclusive-OR operation. In the lower part of the 12 can be a feedback branch 1230 recognize, causing the contents of the shift register to its input 1215 is fed back. The 12 FIG. 3 shows an example of a convolutional encoder which is shown in FIG 11 can be used as a component encoder.

According to the example of 11 become the parity bits of the component encoders 1105 and 1115 , the systematic bits that correspond to the information bits a puncturer 1120 made available. From the 11 can be seen that the puncturer 1120 5 inputs and only one output has. In the puncturer 1120 There is a parallel-serial conversion of the 5 inputs to the one output instead, but also bits that are present at the inputs, can simply be discarded and not passed on to the output. This can be controlled, for example, via a puncturing pattern, which determines which bits of the 5 inputs are passed to the output. For example, the puncturer may forward each systematic bit but only every 2nd bit of the 4 parity bit inputs to the output. Since a total of Infoword_Len bits are present at each of the five inputs for each information word to be transmitted, a maximum of 5 × Infoword_Len bits can be output.

By a suitable puncturing pattern can be achieved set amount of Codeword_Len bits output from the puncturer so that the length of an output codeword, the is composed of the code bits, Codeword_Len is. The relationship from Infoword_Len / Codeword_Len is the code rate of the Turbo code. For the example above, the code rate may be through the puncturer be set between 1/5 and 1.

To the transmission of code bits, d. H. of the codeword, about a transmission channel, for example, in the receiver troubled bits processed there in the form of soft bits may be present. In other words, binary digits shown in the receiver higher resolution be, d. H. for a transmitted binary digit "0" or "1", can have multiple binary digits in a receiver to be used. For example, reliability information can be provided the individual binary digits with in the decoding considered become. A turbo decoder now has the task of transmission errors to correct.

A in the 11 shown turbo coder adapted turbo decoder is in the 13 shown. The turbo decoder includes a de-puncturer 1300 , a 1st component decoder 1305 , a 2nd component decoder 1310 , a turbo code interleaver 1315 and a turbo-code de-interleaver 1320 , Already from the structure of in the 13 shown turbo decoder can be seen that the turbo code interleaver 1315 and the turbo code de-interleaver 1320 play a central role.

A turbo decoder operates iteratively, ie unlike Viterbi decoder codes for convolutional codes, each component decoder is used not once, but once per iteration, with multiple iterations, typically the number of iterations is 3 to 8. The de-puncturer 1300 determines the systematic bits from the received code bits as well as the parity bits of the first component and the second component. The parity bits of the 1st component become the 1st component decoder 1305 , the parity bits of the 2nd component to the 2nd component decoder 1310 fed. In each iteration, the 1st component decoder calculates 1305 on the basis of its inputs, ie on the basis of the parity bits of the 1st component, the systematic bits, and the extrinsic information of the 2nd component, an output signal which can be referred to as extrinsic information of the 1st component.

For each of the Infoword_Len systematic bits there is also extrinsic information, ie this output of the 1st component decoder 1305 is a vector of Infoword_Len extrinsic information. In addition, the 1st component decoder provides 1305 decoded via a second output a vector of Infoword_Len, ie estimated information bits. The two vectors of the systematic soft bits and the extrinsic information of the 1st component are in the turbo code interleaver 1315 permutates, ie each vector is scrambled separately by itself and with the same permutation as in the turbo-encoder, such as in the 11 shown.

Likewise, the 2nd component decoder calculates 1310 based on its inputs as output a vector of Long Infoword_Len of extrinsic information of the 2nd component. This is via the turbo code de-interleaver 1320 back to the 1st component decoder 1305 so that it can start the next iteration. During iterations, the 1st and 2nd component decoders interchange 1305 ; 1310 their respective extrinsic information about the turbo code interleaver 1315 or the turbo code de-interleaver 1320 out. The turbo code de-interleaver 1320 fits in such a way to the turbo code interleaver 1315 that a vector of length Infoword_Len, once with the turbo code interleaver 1315 permutes and the result afterwards with the turbo code de-interleaver 1320 was again identical to the original vector.

The turbo code interleaver 1315 has, among other things, the task of ensuring high distances between the permuted codewords. As a measure, in general, the Hamming distance between codewords may be used, which corresponds to the number of bits in which 2 codewords A and B differ. If code word A is transmitted, the code word B is instead erroneously selected by the receiver if these bits were corrupted by the channel. In fact, it is sufficient if more than half of these bits have been corrupted. Naturally, the probability that a wrong codeword B is selected the smaller, the greater the Hamming distance between A and B, cf. z. B. Todd K. Moon's "Error Correction Coding", Wiley, 2007, ISBN 978-0-471-64800-0 ,

The turbo code interleaver 1100 respectively. 1315 is now to ensure that the distances between each possible codeword A and all other possible codewords B become large. The solution to this problem can be somewhat simplified as follows. The Hamming distance between 2 codewords A and B can be calculated as the Hamming weight of the vector A plus B, the weight meaning the number of ones of the vector. Here, as explained above, the plus symbol represents a binary addition, which corresponds to an Ex-Or operation (exclusive-OR operation) between one bit each of A and B, ie bit 0 of A becomes bit 0 of B linked, bit 1 of A is linked to bit 1 of B, bit 2 of A is linked to bit 2 of B, etc.

turbo Codes are linear, d. H. they possess the property that A plus B is a valid codeword if A and B are valid Are codewords. Therefore, the code vector A may also be the zero vector be adopted as a transmitted codeword. The distances to all other codewords B are then simply the Hamming weights these other codewords. Due to the linearity property is the distance distribution, d. H. the histogram of the occurring ones Distances to all possible codewords B, identical for each code word A, including the null vector. If this is assumed to be codeword A, the distance distribution becomes identical for weight distribution of all possible codewords.

According to the above explanation, there is a turbo-coder, such as in the 11 shown at its output a zero vector when its input is a 0 vector. Based on the above considerations, it is therefore target of the Turbo code interleaver 1110 ; 1315 to make sure that as much weight as possible is produced at the output if there is a vector other than the zero vector at the input.

In particular, the minimum weight d _{min of} all codewords is important, because in a transmission of the zero word, a corruption to the codewords with the minimum weight is most likely. Analogously, in the transmission of any code word A, the probability of a falsification towards a code word B which has a minimum distance from d _min to codeword A is greatest.

It is the minimum distance d _min that also determines the shape of the word error rate curve. In such word error rate curves, the word error rates WER (WER = word error rate, ie the ratio of the incorrectly decoded code words to the total number of transmitted codewords) over a growing signal-to-noise ratio (SNR) for a static non-frequency selective channel with Additive White Gaussian Noise (AWGN = Additive White Gaussian Noise). In the 10a such a curve is represented by a dashed line. If, for example, this line is considered, it can be seen that it has a part between 1.2 and 1.6 dB, in which the WER curve drops steeper, followed by a flatter curve part, referred to as a so-called error floor or error carpet becomes. The position of the error floor is mainly caused by the code words with minimum distance d _min from the transmitted codeword.

For Therefore, commercial systems, it is desirable that a Such error floor is naturally limited, because too high a WER data transfer unreliable makes, d. H. z. B. signal dropouts and also within of the Error Floors even by increasing the SNR the WER not can be significantly reduced.

Therefore, since the advent of Turbo Codes, considerable research has been invested in reducing the error floor, cf. z. B. Marco Breiling, "Analysis and Design of Turbo Code Interleavers", Shaker Verlag, Aachen, 2002 ISBN 3-8322-0302-8 and S. Crozier and P. Guinand: "High Performance Low Memory Interleaver Banks for Turbo Codes", in Proc. of the 54th IEEE Veh. Tech. Conf (VTC'01), Atlantic City, pp. 2394-2398, Oct. 2001 ,

For this purpose, various approaches have also been carried out for the optimization of Turbo code interleavers, for example, there were several suggestions in UMTS standardization (UMTS = Universal Mobile Telecommunication System), cf. Johan Hokfelt, Ove Edfors, and Torleiv Maseng: "Interleaver design for turbo codes based on the performance of iterative decoding", Intern. Conf. to Communications, Communications Theory Mini Conference, pages 93-97, 1999 ,

From the foregoing considerations, it can already be seen that the generation of weight in the turbo coder should be taken into account to the methodology behind the design of Turbo code Interlea vern to make understandable. A codeword with the weight d _min arises at all only if the information word has a low weight, since this enters itself as a systematic part in the codeword with. If the information word is represented by a vector with a single one: 00 ... 010 ... 0, then in the 1st component encoder 1105 following: Before this one in the component encoder 1105 when it is input, it outputs only zeros at its outputs, because the internal shift register of the component encoder 1105 contains only zeros, cf. 12 ,

After the one has reached the component encoder, the shift register no longer contains only zeros, and through the feedback branch 1230 For the rest of this information word, not all flip-flops will be 1200 . 1205 and 1210 be zero at the same time. This means that the component encoder will be at its outputs from the time a single one is input 1220 ; 1225 delivers many ones. The two streams of parity bits are thus usually of great weight, and codewords generated by a single one are accordingly also of great importance.

The situation may be different if there is a vector at the input of a component encoder in which there are two ones which have a certain distance from one another, distance is to be understood here as the distance between the two positions within the vector. The Indian 12 shown component encoder provides a low initial weight for the following input vectors:
00..0100000010..0,
00..01000000000000010..0,
00..010000000000000000000010..0,
ie whenever the distance of the ones is a multiple of 7 positions. The part of the vector between the introductory and the terminating one, including these ones, will be referred to below as the error pattern. This term stems from the fact that these patterns are responsible for codewords that are erroneously output by the decoder when the null codeword is transmitted incorrectly. In each case, the first one causes the shift register to no longer contain only zeros and therefore start outputting nonzero bits, while the final one causes the shift register to again contain only zeros, it returns to the so-called zero state, and that therefore afterwards only zeros are spent.

While 10000001 is an error pattern is 1000001, d. H. the distance between the ones is only 6 positions, or 100000001, d. H. the distance is 8 positions, etc. no error pattern, d. H. here the shift register with the 2nd one does not go to the zero state back and therefore gives more afterwards Ones out.

Accordingly, to increase d _min , a turbo-code interleaver should have as many error patterns as possible at the input of the first component decoder 1305 , which produce parity bits of possibly low weight, permute such that they follow sequences at the input of the second component decoder 1310 which are not error patterns and therefore must generate a high parity weight.

As already explained above, the quality affects of the Turbo code interleaver directly to the error floor of the word error rate curve out. Another important point is the implementability of the Turbo code Interleavers. In principle, every turbo code is interleaver implementable as an address table, d. H. for each input bit the 1st or 2nd component is sequentially represented in a table Address where this bit is read or where it is written from so that the corresponding other component encoder can process it. The process of interleaving can be described as reordering express information bits in memory: if on Information bit before interleaving in address i of a first memory is, it stands after the interleaving in address Addr [i] either also the first or a second memory. For example for 10,000 bits of information would have this address table 10,000 entries, each with 14 bits, to represent Addresses up to 10,000. These addresses can be in their own ROM (ROM = Read Only Memory) or RAM (RAM = Random Access Memory) stored, which is a significant cost implications of the implementation. This problem becomes more critical even if the turbo code support multiple word sizes must, as it is z. B. very common in modern communication systems the case is. In this case would be for every word size a separate table is required, and the RAM or ROM requirement adds up on.

For this reason, there are already efforts in the field of conventional technology to select an algorithmically representable Turbo code interleaver. Here, the permutation address for each information bit is calculated by a rule that can be represented by a few arithmetic operations and the use of a few parameters. These parameters can be used for any word size accept different values and stored in small RAM or ROM tables.

In the early days of turbo codes were often chosen as turbo-code interleaver random permutations, as for example in the 14 is shown. The 14 shows a random turbo code interleaver based on an interleaver length of 1146 bits. The presentation in the 14 shows the bit position of the 1st component on the ordinate, and the bit position of the 2nd component on the abscissa. The respective assignment is represented by a cross, the distribution of the crosses indicating the random nature of the turbo code interleaver. With regard to random interleavers, it can be shown that they almost certainly permute error patterns at the input of the first component decoder into error patterns at the input of the second component decoder, so that a code word of low weight is generated, cf. Sergio Benedetto and Guido Montorsi: "Unveiling Turbo Codes: Some Results to Parallel Concatenated Coding Schemes", IEEE Trans. To Inform. Theory, 42 (2): 409-428, 1996 ,

The WER of a random interleaver is among others in the 10a shown and designated there as a dashed line with the name "random interleaver". Here the Error Floor is clearly recognizable. Another disadvantage of random interleavers is that they can not be represented algorithmically, so that they have to be stored as a table.

Linear Congruente Interleaver are also known in the conventional art. In contrast to random interleavers, these interleavers are mathematically strictly describable. The address Addr [i] of an information bit i can according to the formula Addr [i] = (C × i) mod where mod is the modulo operation, K is the information word size, and C is a constant which must be relatively prime to K and represents the increment between successive addresses. These interleavers have a high error floor, so they are rarely used in practice.

In the early days of the Turbo Codes, Rectangle Interleavers were used instead of random interleavers. An example of a rectangle interleaver is in 15 shown. The 15 shows a rectangular representation with 3 rows and 4 columns, wherein in each case the read or write index is entered. Like from the 15 The information word size must be equal to the product of row and column count. The bits to be permuted are written line by line and read column by column. The performance of these interleavers is also insufficient.

At the extreme examples random interleaver on the one hand and Rectangular interleaver or linearly congruent interleaver on the other side can be seen that both too random as well as too structured a structure of a turbo code interleaver leads to poor performance efficiency of the code.

The literature also discloses s-random interleavers, cf. S. Dolinar and D. Divsalar: "Weight Distributions for Turbo Codes Using Random and Nonrandom Permutations", Jet Propulsion Lab, TDA Prog. Rep., 42-122: 56-65, 1995 , where the permutation is pseudorandom to a certain extent, but here a few restrictions are placed on the randomness with respect to the distances that the positions of 2 arbitrary bits in the 1st and 2nd components may have. With these s-Random interleavers a quite good performance of the turbo code can be achieved. The disadvantage here is, similar to the random interleavers, that no algorithmic calculation formula of the interleaver can be given.

An interleaver, which has many properties of the s-random interleaver, but which is nevertheless algorithmically describable, is the Dithered Relative Prime Interleaver, cf. S. Crozier and P. Guinand: "High Performance Low-Memory Interleaver Banks for Turbo Codes", in Proc. Of the 54th IEEE Veh. Tech. Conf (VTC'01), Atlantic City, pp. 2394-2398, Oct. 2001 , This interleaver is a mixture of pseudorandom and structure, as well as prescribed bit-position spacings. It is based on the Linear Congruent Interleaver with an additional superimposed local permutation to break the rigid structure of the Linear Congruent Interleaver.

Another known interleaver is the UMTS or 3GPP interleaver (3GPP = Third Generation Partnership Project), see W-CDMA 3GPP TS 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Mul tiplexing and channel coding (FDD), and Hirohito Suda and Akira Shibutani: Interleaving method, interleaving apparatus, turbo encoding method, and turbo encoder. European Pa tent 1 030 455 B1 , 1999. The basic principle behind the Turbo Code interleaver, which is used in the 3GPP standard, is a rectangular interleaver, which is referred to as frame interleaver in the following, in which intra- and inter-line interleaving is additionally performed. This means that first in a first step, the information bits are written line by line in a rectangular interleaver. Subsequently, permutation takes place within each line again. Intra-line interleaving, where the permutation is different in each line. In the 3GPP interleaver, this permutation is performed on the basis of cycles generated in a Galois field by exponentiation of a primitive element. The resulting intra-line interleaving can be roughly compared to a pseudorandom permutation.

Subsequently In a 3GPP interleaver, whole lines are interchanged, so-called inter-line interleaving. Having intra and inter-row interleaving are performed, the thus-permuted rectangular-frame interleaver read out column by column.

At the 3GPP interleaver requires extra effort to adapt the interleaver to the word size. Instead, before the permutation dummy bits to the information word appended so that the word thus supplemented is complete fills a rectangle interleaver, the length of the filled input word then results from the Product of row and column number. After the permutation must these dummy bits are removed again, d. H. it becomes a so-called Pruning performed. The permutation of the 3GPP interleaver is thus composed of a series of individual operations.

Of the Disadvantage of the treatment of dummy bits, d. H. their insertion, their share of the permutations and the Remove, is that extra processing time, resource consumption, for example additional memory requirements, and additional Implementation effort, d. H. Complexity, needed becomes.

Around the actual adding and later Removing the dummy bits to the "real" information bits To save, it would be useful to interleave the index Information bits, d. H. after the complete interleave process and reading from the interleaver memory, calculate immediately to be able to. So it would be a calculation rule desirable that the index of an information bit in Interleaveten information word can specify directly as they pass through the o. a. Dummy bit add operation, interleaving and dummy bit removal would result, but without that adding and removing dummy bits really must be performed.

A simple calculation rule can not be specified because the 3GPP interleaver has the following disadvantage: the frame interleaver this standard is always a rectangular interleaver whose number of elements the product of row and column number is. Because the block size is arbitrary, inevitably - like described above - additional dummy bits inserted be removed, and removed after interleaving. All lines of the frame interleaver are after inserting the dummy bits the same length, and all intra-line interleavers work with the same line length. The dummy bits are therefore through the intra and inter-row permutations usually over the whole frame interleaver scattered. In addition, can the number of dummy bits in different lines varies be. The irregular distribution of the dummy bits over the entire frame interleaver does not allow a simple direct calculation for the index of the interleaved information bit (after Intra- and inter-row permutation and readout), since these are irregularities would have to be considered in the formula.

Also for the cdma2000 or 3GPP2 interleaver (see CDMA-2000 3GPP2 C.S0002-C Version 2.0 Physical Layer Standard for cdma2000 Spread Spectrum Systems Revision C, as well as Douglas N. Rowitch and Fuyun Ling: "Turbo Code Interleaver using Linear Congruential Sequence " US Pat. No. 6,304,991 B1 , 1998, and Steven J. Halter: "Random-Access Multi-Directional CDMA2000 Turbo Code Interleaver", US Pat. No. 6,871,303 B2 , 2001), a frame interleaver in the form of a rectangular interleaver is used, in which intra- and inter-line interleaving are performed. Here, the intra-line interleaving is based on a linear congruent interleaving, which is also intended to cause a quasi-random permutation, while inter-line interleaving is achieved by a literal reversal of the bit representation of the respective line index (bit reversal).

The 3GPP2 interleaver also requires additional effort to match the interleaver to the selected word size because the product of row and column counts is typically unequal to the information word size. It is therefore always necessary to generate 2 candidate addresses for an information bit which are between zero and the product of row and column number. If the first candidate address is valid, ie between zero and the information word size, it is used, otherwise it will be ver uses the second candidate address, which in this case is always valid (this can be shown for the algorithm used).

While the frame interleaver of the 3GPP2 standard is always a rectangular interleaver is, the information word size here in certain Levels are selected, and for each information word size There are own parameter sets for the interleaver. The information word sizes are usually unequal the number of elements of the rectangle frame interleaver (product from row and column number). Although in this interleaver design no padding of the frame interleaver with dummy bits necessary is, here is a simple immediate calculation of the address an information bit not possible.

A The peculiarity of the 3GPP2 interleaver is that in the Address calculation rule a counter value occurs, the unequal is the index of the bit to be permuted. Is for example a Block size selected from 378 bits, then the bit index goes from 0-377, while the counter value all values from 0 to 511 are crossed. For the calculation the address of bit with index zero also becomes the counter value zero used, but already for the bit with index 3 will not work more of the counter value 3 but 4 uses, however, the Counter value 3 discarded. This is due to the algorithm of the 3GPP2 standard, the Candidate addresses generated that are invalid for some indexes are. The reason for this is that the inter- and intra-line interleaving always assumes that every line or column is complete and the same length.

Without the above counter and the generation of possibly invalid candidate addresses are not calculated feasible. The disadvantage of this method is just now generating invalid addresses that are discarded which, in turn, require more processing time, respectively higher implementation effort for parallel generation two addresses is necessary.

It The object of the present invention is an improved concept to scramble information words.

These Task is solved by an interleaver according to a of claims 1 or 9, an index generator according to claim 17 and a method according to one of the claims 15, 16 or 22.

The The present invention is based on the core idea that rectangular interleavers, can be used for information words, their length is not the product of row and column count of the rectangle interleaver. embodiments In the following, the present invention will also be described as fast-rectangle interleavers called ("almost" in the sense of "almost"). In particular, these fast-rectangle interleavers can interact with each other be nested in a way that is a good one Interleaver quality results, d. H. that an Error Floor a WER a turbo coding configured correspondingly low is. At the same time, these interleavers can be set to different Block sizes, d. H. Information word lengths without inserting so-called dummy bits, or without dummy addresses, d. H. invalid candidate addresses be generated. Furthermore, the fast-rectangular interleavers provide the Possibility of simple calculation rules between original index of an information bit (before the interleave) and to implement the address after the interleaven, so that comparatively low demands on storage and processing time have to be asked.

One Another core idea of the present invention is that within a fast-rectangle interleaver whose lines z. B. over more fast-rectangle interleavers get scrambled can. In other words, it is a core idea of the present Invention that improved interleaving results by interleaving can be generated by fast-rectangular interleaver, where the other near-rectangle interleavers use an intra-line interleaving of the 1st fast-rectangle interleaver. In Embodiments may include an additional near-square interleaver are used, for. To perform inter-line interleaving. Embodiments of the present invention form thus the advantage that good interleaving results with low Effort and low hardware requirements can be generated.

in the Following are embodiments of the present Invention explained in more detail with reference to the accompanying figures.

It demonstrate

1a an embodiment of a fast-rectangular interleaver;

1b a flowchart of an embodiment of a method for generating an output index;

2 a representation of an index permutation of an embodiment of a fast-rectangular interleaver;

3 an error pattern of an embodiment of a fast-rectangular interleaver;

4 another embodiment of a fast-rectangular interleaver;

5 an embodiment of an intra-line fast-rectangle interleaver;

6 an illustration of an index permutation with an embodiment of a fast-rectangle interleaver;

7 an illustration of an embodiment of an inter-line fast-rectangle interleaver;

8th another illustration of an inter-line fast-rectangle interleaver;

9 an illustration of an index permutation of an embodiment with interlaced fast-rectangle interleavers;

10a Simulation results using an embodiment using word error rates;

10b Simulation results for comparing an embodiment with a 3GPP2 interleaver;

10c further simulation results for comparing an embodiment with a 3GPP2 interleaver;

11 a block diagram of a turbo encoder;

12 a block diagram of a convolutional encoder;

13 a block diagram of a turbo decoder;

14 an index permutation of a random interleaver;

15 an illustration of a rectangle interleaver.

in the Following are embodiments of the present Invention explained in detail.

The function of an exemplary embodiment of a fast-rectangular interleaver will first be explained below. The fast-rectangle interleaver differs from a rectangular interleaver in that, in the case of the fast-square interleaver, the number of bits or digits can be different from the product of row and column numbers, as shown by way of example in US Pat 1a is shown. The 1a shows an arrangement of 3 rows with the indices 0, 1, 2 and 4 columns 0, 1, 2, 3, in which only 10 indices are entered from 0 to 9. It can be seen that in the 1a columns 2 and 3 contain only 2 digits, whereas columns 0 and 1 each have 3 digits. In terms of arid ren words, lines 0 and 1 each have 4 elements, whereas the line 2 has only 2 elements. In the individual cells or elements, in each case a reading index X and a writing index Y are first entered, wherein X and Y are separated by a slash. It can be seen that the fast-rectangle interleaver is first described line by line and then read out column by column.

In the following, embodiments of such interleavers are referred to as fast-rectangular interleavers. These interleavers are written line by line and read column by column like "normal" rectangular interleavers, but the last row or columns may be shorter than the previous ones. In general, in embodiments, columns can also be written and read line by line. In general, the considered vectors, ie, for example, components, elements or locations of an In Formation word brought in a matrix-like form, ie grid-shaped arranged in rows and columns, not all rows and columns must be fully occupied. By transposing, line and columnwise operations can be interconverted. Further, in the following, the terms components, elements, locations will be equivalently used to denote a position in a vector or in a matrix. Components, elements, and locations may include, but are not limited to, one or more binary locations.

In the following, assume that Num_bits is the number of information bits, that is, the number of elements of the interleaver, and Num_Cols is the number of columns. It follows, therefore, that the number Num_Full_Rows of complete lines and the number Num_Rem_Bits of bits in the incomplete, ie last line, if any, can be calculated as follows: Num_Full_Rows = Floor (Num_Bits / Num_Cols), Num_Rem_Bits = Num_Bits mod Num_Cols, the Floor function causes the rounding to the nearest integer less than or equal to the argument. Such a permutation rule is also in the form of an index diagram in the 2 shown. The 2 shows an association between the bit positions of the 2nd component on the abscissa and the bit position of the 1st component on the ordinate, as may be generated in one embodiment. According to the above example, a fast-rectangle interleaver with a length of Num_bits = 1146 bits with Num_Cols = 34 columns is assumed. The 2 shows that the last line is incomplete, as can be seen in the lower right area.

One Fast Rectangle Interleaver Transforms into a Rectangle Interleaver if the last number or columns are complete and thus the number of bits equals the product of line and number of columns.

embodiments Fast Rectangle Interleavers have the big advantage that the error patterns written above are well torn apart can be, d. H. if the distance of the ones in the 1st component is low, so the 1st component encoder only produces a few ones at its output, then the distance of these ones after the permutation, ie at the input of the 2nd component encoder big, and in the 2nd component many ones, i. H. a heavy weight, generated.

In the simulation, however, a single fast-square interleaver in a Turbo code proves to be of little use. Again, an error floor occurs because the minimum distance d _{min is} too low, such as the dash-dotted curve called "fast-rectangle interleaver" in the 10a shows.

The 3 shows a further schematic representation of an embodiment of a fast-rectangle interleaver, which is intended to explain the increase of the error floor using an error pattern in more detail. In the 3 the reason for the increased error floor can be recognized. The information word contains 4 ones, which stand in the near-rectangle interleaver at the corners of a rectangle or a square. If the information word is now written line by line into the interleaver matrix, the error pattern 10000001 is displayed in 2 lines. This error pattern will therefore also occur twice at the input of the 1st component encoder, so that it outputs a sequence of low-weight parity bits. However, this error pattern also appears on 2 columns in this way, which means that it also occurs twice at the input of the 2nd component encoder and likewise produces a low parity weight here. Accordingly, the 4 ones are arranged in the near-rectangle interleaver such that a code word of low weight is generated.

These Negative property has an even stronger effect if this rectangle, whose corners are formed by the 4 ones, is moved arbitrarily within the near-rectangle interleaver, because with each shift an unfavorable arrangement with resulting in low codeword weight arises. These combinations are responsible for the increased error floor. A single fast-rectangle interleaver does not deliver yet the desired performance for Turbo codes and therefore seems less practicable.

Embodiments of the present invention include an interleaver for scrambling an information word, the information word having a plurality of locations to obtain a permuted information word. The interleaver can be a first interleaver stage (frame interleaver) for arranging the locations of the information word in a plurality of first rows and first Columns, wherein the first rows have at least a first row with a gap and the first columns have at least a first column with a gap. Further, the interleaver may comprise a second interleaver stage for scrambling the locations of a first row with the gap by interchanging at least two locations of a first row such that a position of the gap remains unchanged to obtain a first scrambled row and replacing the first row one of the first lines with the first scrambled line. The first interleaver stage can be designed to read out the first columns column-by-column and to consecutively line up the locations of the first columns in order to obtain the permuted information word.

In Embodiments may be the second interleaver stage be trained to pass the digits of a first line through a to scramble linear congruente interleaver rule so that a position of the gap remains unchanged to get the first scrambled line and replace it one of the first lines with the first scrambled Row.

The The second interleaver stage can also be designed to cover the locations of a first row by row in a plurality of second Arrange rows and second columns, and column-wise read the places to get a first scrambled line and replacing one of the first lines with the first one scrambled Row. The first interleaver stage can also be designed to read out the first lines in columns and without gaps, to get the permuted information word.

In In embodiments, the interleaver may further comprise a third interleaver stage, for arranging line by line Row indices of the first rows in third rows and third columns, and for column-wise reading of the row indexes to be scrambled To get line indexes and to swap the first lines or first scrambled lines based on the scrambled ones Row indices. The first interleaver stage can then be formed to be based on the scrambled line indexes exchanged first lines column by column and read out completely, to get the permuted information word.

In Embodiments may be the digits of the information word Softbits or symbols with more than 2 values, d. H. a majority of binary digits per digit or element of the information word include. In other embodiments, each digit of the information word comprise exactly one binary digit.

In Further embodiments, the first Interleaverstufe be formed to the places of the information word in one To arrange number of first rows and a number of first columns, wherein the information word has a number of digits that smaller than the product of the number of first rows and the Number of first columns and the first interleaver stage further is designed to gaps occurring in the column-wise readout to skip, d. H. read out completely.

In Embodiments may also include the second interleaver stage be trained to put the bodies of one of the first lines in a number of second rows and a number of second columns to classify, wherein the one of the first lines a number of digits which is smaller than the product of the number of second lines and the number of second columns and the second interleaver stage is further adapted to occur in the column-wise reading Gaps to skip or gapless read.

In Embodiments may further include the third interleaver stage be formed to the row indexes in a number of third To arrange rows and a number of third columns, the Number of line indices less than the product of the number of third rows and third columns, and the third level of interleaving is further adapted to occur in the column-wise reading Gaps to skip or gapless read.

In Embodiments, the first, the second, or the third interleaver stage to be designed as an information word to scramble a vector of read or write addresses. In other words, embodiments may also be used to appropriate read and write addresses to scramble and thus also interleaver or de-interleaver rules to realize. In other words, instead of one Information word itself reading addresses are scrambled and an interleaver rule by scrambled readout will be realized. A scrambled information word can be reclaimed, d. H. in the original state in the write addresses according to the Indices of the information word are scrambled, and the Adjusting the scrambled information word accordingly written to the scrambled write addresses.

Embodiments of interleavers may also include a first interleaver stage (frame interleaver). for arranging the locations of the information word line by line in a plurality of first rows and first columns. Furthermore, the interleavers may comprise a second interleaver stage for scrambling the locations of one of the first rows by arranging the locations of the one row in a plurality of second rows and second columns row by row, the second rows having at least one second row with a gap and the second rows Columns have at least one second column with a gap, and wherein the second Interleaverstufe may be formed to read the locations of the second columns column by column and without gaps to obtain a first scrambled line, and to replace the one of the first lines the first scrambled line, wherein the first interleaver stage may be configured to read the first columns column by column to obtain the permuted information word.

In Embodiments, the first Interleaverstufe formed be, to line by line arranging the positions of the information word in a plurality of first rows and first columns, wherein the first lines at least a first line with a gap and the first columns having at least one first column have a gap, the first interleaver stage can be designed to read the first columns column by column and the positions of the first columns gapless to rank to get the permuted information word.

embodiment may further comprise a third interleaver stage which is designed for row indices of the row indexes first rows in third rows and third columns, and column by column Reading the row indexes around scrambled line indexes and to swap the first lines based on the scrambled line indices, the first interleaver level is designed to be based on the scrambled Line indexes swapped to read first lines column by column to get the permuted information word.

According to the above Explanation may be the first, second and / or third interleaver stage be formed to an information word to process, where each digit includes a binary digits. The third level of interleaving may be adapted to the row indices in a number of third rows and a number of third columns to arrange, with the number of row indices is smaller than that Product of the number of third lines and the number of third Columns and the third interleaver stage is further formed, to skip gaps when reading columns by column. In other words, any of the first, second and third interleaver stage as a fast-rectangular interleaver be. The first, second and / or third interleaver stage can be formed in order to use a vector of reading or scrambling write addresses.

Embodiments may include an index generator for generating an output index based on an input index, a column number, an element number, and an incomplete line information. The index generator includes means for generating a row index based on the input index and the column number, and means for generating a column index based on the input index and the column number. Further, the index generator includes means for generating a full-line number based on the element number and the column number, and means for generating a residual element number based on the element number and the column number. The index generator may further comprise means for outputting the output index, which is arranged to, in the event that the column index is smaller than the remaining element number, the output index as Initial Index = (full number +1) Column Index + Row Index issue,
and otherwise,
in the event that the information about the incomplete line indicates that there is no incomplete line or the line index is less than or equal to an index of an incomplete line,
the starting index as Initial index = (full-line number + 1) Remaining element number + full-line number (column index - remaining element number) + line index issue,
and otherwise
the starting index as Initial Index = (full-line number + 1) Remainder element number + full-line number (column index - residual element number) + line index - 1 issue.

The Means for generating the row index may be formed around the row index by rounding off a quotient from the input index and to generate the number of columns. The device for generating The column index may be configured to pass through the column index generate a modulo operation of the input index with the number of columns. The means for generating the full-line number may be formed to be the full line number by rounding off a quotient to generate the element number and the number of columns. The device for generating the residual element number may be formed to the Remaining element number by a module operation of the element number with the Generate column number.

1b shows a flowchart of an embodiment of a method for generating an output index. The method generates the output index based on an input index of a column number, an element number, and an incomplete line information. The method comprises a step 110 generating a row index based on the input index and the column number. For example, in one embodiment, the row index may be Row index = floor (input index / column number) are determined, with the function floor (.) Realizes a rounding down to the next lower integer, this is in the 1b indicated by downwardly open brackets.

The step 110 further comprises generating a column index based on the input index and the column number. For example, in one embodiment, the column index may be Column index = input index modulo column number be determined.

The method comprises a step 112 generating a full-line number based on the element number and the column number. For example, in one embodiment, the full-line number may be Full line number = floor (element number / number of columns) are determined, with the function floor (.) Realizes a rounding down to the next lower integer, this is in the 1b indicated by downwardly open brackets. The step 112 further comprises generating a remainder element number based on the element number and the number of columns. For example, in one embodiment, the residual element number may be Remaining element number = element number modulo number of columns be determined.

The method includes several ways of outputting the output index in the event that the column index is smaller than the residual element number, which is in the 1b in step 114 is checked, the output index is called Initial Index = (full number +1) Column Index + Row Index issued, cf. step 116 in 1b , Otherwise, in case the information about the incomplete line indicates that there is no incomplete line or the line index is less than or equal to an index of an incomplete line, cf. step 118 in 1b , the initial index in step 120 when Starting index = (full line number + 1) remaining element number + full line number (Spaltertindex - remaining element number) + line index, and otherwise
when Initial Index = (full-line number + 1) Remainder element number + full-line number (column index - residual element number) + line index - 1 issued, cf. step 122 ,

embodiments can also be found in turbo encoders and turbo decoders be used.

embodiments Further, a frame interleaver, i. H. a first Interleaf stage comprising a near-square interleaver has several lines, the lowest of which is not complete is. The intra-line interleavers, d. H. the second interleaver stage, All lines are linear congruent, with the gaps of the last line will not be with interleavet. The constant C every Linear Congruent Intra-Lines Interleavers can be set individually be.

One Embodiment of a turbo-code interleaver is explained in detail below. The embodiment is based on a recursive use of embodiments of fast-rectangle interleavers. In this embodiment becomes a fast-rectangle interleaver both as a frame interleaver as well as on underlying levels for intra and inter-row permutations used.

The to be permuted information bits of the information word first line by line into a frame interleaver, d. H. written in a first interleaver level. The following is the Intent "frame" also omitted. The first interleaver stage is in this embodiment as a fast-rectangle interleaver formed with a predetermined number Num_bits of bits and number of columns Num_Cols, where the number Num_Full_Rows is more complete Lines and the number Num_Rem_bits of bits in the incomplete last line from these two values.

For example, could
Num_Bits = 22
Num_Cols = 8
→ Num_Full_Rows = 2
→ Num_Rem_Bits = 6.

The 4 illustrates an embodiment with 22 digits arranged in rows 0, 1 and 2 as well as in columns 0-7. In the 4 It can be seen that the last line is not quite complete, or that columns 6 and 7 have only two elements, whereas all the other columns have three elements. The elements in this case show the original positions of the positions in the information word, ie they can be regarded as indices or addresses of the actual information word locations or elements. In the 4 It can be seen that the first interleaver stage is designed to arrange the locations of the information word line by line in a plurality of first rows and first columns.

Furthermore, in the 4 to recognize that all rows have Num_Cols_bits, only the last, incomplete row contains Num_Rem_Bits if this value is ever greater than 0 and an incomplete row exists.

The The following second interleaver stage is used for permutation per line. Again, there is a fast-rectangle interleaver in the present embodiment for use. For each of the lines becomes, so to speak, an intra-line interleaver used. In the following, the term "Intra" always means Parameters related to such an intra-row interleaver, i. H. belong to the second Interleaverstufe. The element number Num_Intra_Bits of the intra-line interleaver, d. H. the second interleaver stage, is equal to Num_Cols if the line is complete is or Num_Rem_Bits for the last line, in case it is incomplete is.

The second interleaver stage is arranged to arrange the elements of one of the first rows in a plurality of second rows and second columns in rows. The number of columns, which is also called Num_Intra_Cols of the intra-line interleaver in the following, is freely selectable. This results in the number Num_Full_Intra_Rows of full lines and the number Num_Rem_Intra_Bits of bits in the incomplete last line. The following is carried out for each line of the frame interleaver, ie the first interleaver stage: The associated intra-line interleaver, ie the second interleaver stage, is written line by line and read out column by column. Thus, a permuted line, ie a first scrambled line is obtained, which then replaces the corresponding line. To return to the previous example, for example, in the first line:
Num_Intra_Bits = Num_Cols = 8
Num_Intra_Cols = 3
Num_Full_Intra_Rows = 2
Num_Rem_Intra_Bits = 2

Second line:
Num_Intra_Bits = Num_Cols = 8
Num_Intra_Cols = 2
→ Num_Full_Intra_Rows = 4
→ Num_Rem_Intra_Bits = 0

Third line:
Num_Intra_Bits = Num_Rem_Bits = 6
Num_Intra_Cols = 2
→ Num_Full_Intra_Rows = 3
→ Num_Rem_Intra_Bits = 0.

The 5 illustrates this approach based on the example of 4 , The 5 shows the arrangement of the indices of the first row of the first interleaver stage 4 in second rows and second columns. The 5 shows that the indices of the first line of the 4 now in second lines and second columns have been written, in a next step, the indexes of 5 now read column by column and back into the lines of 4 written. Such an example is in the 6 which now shows the scrambled lines of the 4 shows that from the column-wise readout of the second Interleaverstufe the 5 result. In the 6 It is easy to see that within each line the elements were only scrambled, but the lines were not scrambled among each other.

When next step, an inter-row permutation is performed based on a third interleaver stage. The third interleaver stage is designed to line by line indices one of the first lines to arrange in third rows and third columns and column by column Reading the row indexes, scrambled row indexes and to swap the first lines based on the scrambled line indexes. In other words here whole lines of the frame interleaver, d. H. the first interleaver level, with each other reversed. The permutation between these lines is in the present Embodiment again by a fast-rectangular interleaver whose number of elements Num_Inter_Elems equals the number of lines, complete or incomplete, of Frame interleavers, d. H. the first interleaver stage, i. H. either Num_Full_Rows or Num_Full_Rows + 1.

The Number of columns Num_Inter_Cols of inter-line interleaver can However, be chosen freely, and this results in the Number of Num_Full_Inter_Rows full lines and the Number Num_Rem_Inter_Elems of elements of the last incomplete Line, if available. The elements of the inter-line interleaver are not single digits or bits, but whole lines, written line by line and read column by column, for example represented by the respective line indices.

Returning to the above example, this would mean:
Num_Inter_Elems = Num_Full_Rows + 1 = 3
(an incomplete line)
Num_Inter_Cols = 2
Num_Full_Inter_Rows = 1
Num_Rem_Inter_Elems = 1.

The associated fast-rectangle interleaver, ie the third interleaver stage of the embodiment, for the inter-row permutation is shown in FIG 7 shown. The 7 shows the arrangement of the row indices in third rows and third columns. In the 7 "i" denotes a whole line i as in the frame interleave after the intra-line permutation, ie after the second interleaver step aver, ie in the first interleaver stage. The third interleaver stage with the row indexes is now read out column by column, and the rows of the first interleaver stage are sorted accordingly. The frame interleaver, ie, the first interleaver stage, becomes during the inter-row permutation and after the intra-row permutation as in FIG 8th displayed, rearranged. The 8th now shows the first interleaver stage, after the line interleaving through the third interleaver stage.

When last step are now based on the first interleaver level on the according to the scrambled line indices exchanged first lines, these columns read out to the to get permuted information word. In other words the thus rearranged frame interleaver is read column by column, missing Elements in the incomplete line can be skipped become.

The permuted information bits are thus output in the following order of the original index:
0, 16, 8, 3, 18, 10, 6, 20, 12, 1, 17, 14, 4, 19, 9, 7, 21, 11, 2, 13, 5, 15.

At In this example, it can be seen that exemplary embodiments the interleaver is a mixture of structure and apparent Disorder, reminiscent of pseudo-coincidence, represents, as it does for example Turbo encoder is advantageous.

Instead of perform the permutation as described above, in which permutes the information bits within an interleaver which contains the elements in an internal memory, An address generator can also be used for every bit of information at the turbo-code interleaver's output Address or index calculated in the input vector at which this bit before the permutation according to the o. g. Rule is. This Address generator thus provides a read address, so that during of reading the o. g. Permutation is performed.

Analogous In addition, in embodiments, an address generator used for each information bit at the input of the interleaver, d. H. at the entrance of the embodiment, whose address or index in the output vector calculates where this Bit corresponding to the o. G. Regulation is permuted. embodiments may thus include address generators having a write address so that while writing the o. g. permutation is carried out. This includes embodiments also corresponding de-interleavers.

in the Next, another embodiment will be considered.

For the following embodiment applies:
Num_Rem_Bits is the number of elements in the shorter (incomplete) line (0 if not present).

Num_Full_Rows Let be the number of complete lines.

Short_Row_Idx (counted from 0) let the line index be the shorter one Line after the inter-line permutation. If not incomplete Line is Short_Row_Idx = Num_Full_Rows (that is, a non-existent line index).

It becomes an element i of the information word at the input of the interleaver considering the address to which it is to be calculated write the interleave process in memory (i.e. in the 1st component, this element was in position i and calculated becomes the position in the 2nd component).

Ilvd_Col_Idx (counted from 0), let the column index be after the intra-row permutation.

Ilvd_Row_Idx (counted from 0) let the row index be after the inter-row permutation.

Then a calculation rule of the address of the interleaved element i can be specified:

With The above embodiment is it is thus possible for an element with index i am Input of the interleaver to calculate a write address directly, d. H. without adding, processing and removing dummy bits and without the generation of possibly invalid candidate addresses. Except the o. A. The calculation rule will only be the regulations to calculate Ilvd_Col_Idx and Ilvd_Row_Idx from position i needed directly from the definition of fast-rectangle interleavers is specifiable.

In the following embodiment, the determination of the row and column indices will also be explained in detail. The embodiment includes an index generator for generating an output index based on an input index. In the following embodiment, for an optional bit index (input index), its write address is generated (output index). This calculation is given as a sequence of calculation steps. There is also a recursive use of the same functions (Fast_Rect_Write_To_2D () and Fast_Rect_Read_From_2D ()) for both the frame and intra and Inter-row permutation conceivable in further embodiments. In addition, a valid write address is generated for each valid bit index, so that no signaling on the validity of the generated write address is necessary.

For the equivalent process that the index generator for generate a bit index of the second component read addresses, so while reading an external memory the Interleaving or the scrambling is done leaves also indicate themselves in the form of a closed program No invalid read addresses can and can not be generated carried out analogously.

embodiment can be a particularly cost-effective implementation when the write or read addresses are generated sequentially be, d. H. if the input variable, namely the bit index 1st or 2nd component, always increased in increments of 1 becomes. In particular, in these embodiments the calculation of the rounded quotient and the remainder at all Divisions are saved.

in the The following will be the embodiment for a Generator for generating write addresses (output index) for an optional index of a bit (input index) before interleaving specified. Writing this bit to the generated address is equivalent for interleaving the bit for the set interleaver parameters. The embodiment is in the notation of language Matlab drafted.

In a further embodiment, the parameters are chosen as follows:
Num_Bits = 1146
Num_Cols = 191
Num_Full_Rows = 6
Num_Rem_Bits = 0 (no incomplete rows)
→ for all 6 lines Num_Intra_Bits = 191;

The other parameters are then given as shown in the following table, which shows the structure of this turbo-code interleaver: Row index Num_Intra_Cols Num_Full_Intra_Rows Num_Rem_Intra_Bits 0 17 11 4 1 12 15 11 2 26 7 9 3 37 5 6 4 14 13 9 5 21 9 2

In a further embodiment, the parameters are chosen as follows:
Num_Bits = 12282
Num_Cols = 2047
Num_Full_Rows = 6
Num_Rem_Bits = 0 (no incomplete rows)
→ for all 6 lines Num_Intra_Bits = 2047;

The other parameters are then given as shown in the following table, which shows the structure of this turbo-code interleaver: Row index Num_Intra_Cols Num_Full_Intra_Rows Num_Rem_Intra_Bits 0 39 52 19 1 54 37 49 2 30 68 7 3 47 43 26 4 66 31 1 5 35 58 17

9 FIG. 12 is a diagram showing the assignment of the positions of the first and second components for an embodiment having a block length of 1146 bits. The per mutation of an embodiment shown there corresponds to a recursive use of fast-rectangular interleavers in the three interleaver stages.

The 10a shows simulation results for word error rates WER (WER) over Eb / N0 in dB, ie bit energy Eb over noise power density N0. The simulation results are given for three different interleavers in conjunction with the turbo coder and turbo decoder considered above for a word length of 1146 bits. The upper curve, indicated by the dashed line and labeled "Random Interleaver," was generated with a random interleaver. The second curve, indicated by a dash-and-dot line, corresponds to a single fast-square interleaver and is called a "fast-rectangular interleaver". The curve obtained with the above-described embodiment of the three interleaver stages is indicated by a solid line and designated by "exemplary embodiment".

The 10a shows the performance of a pseudo-random interleaver and a simple fast-rectangle interleaver in length 1146 with 34 columns, as well as the WER curve of the interleaver presented above. In each case, a turbo-code interleaver with a code rate of 1/2 with component codes of memory length 3 is used. As can be seen, the performance of the exemplary embodiment is significantly better than that of the two other turbo-code interleavers. Also, in contrast to the other two interleavers no significant Error Floor can be seen, which clearly highlights the advantage of the embodiment over the conventional interleavers.

10b shows simulation results for comparing an embodiment with a 3GPP2 interleaver based on their word error rates (WER). The waveform of the WER for the embodiment is labeled "Embodiment", the course of the WER of the 3GPP2 interleaver is designated "3GPP2 ilv." The comparison was carried out for a code rate of 1/4. In the 10b It can clearly be seen that the embodiment generates a significantly lower error floor. The embodiment provides an error floor that is lower by about a factor of 2, or provides 0.2 dB gain in SNR for the same WER. 10c shows further simulation results for the comparison of an embodiment with a 3GPP2 interleaver in the same representation as already described with reference to FIG 10b was explained. The 10c shows a comparison at a code rate of 2/3. The exemplary embodiment is approximately as good as the 3GPP2 interleaver; at the operating point WER = 2 × 10 -3, it can gain approximately 0.1 dB in SNR compared to 3GPP2. Thus, it can be seen that for both very low and high code rates, embodiments are at least as good as 3GPP2 and even exceed its performance.

embodiments offer further advantages over the 3GP22 interleaver in terms of flexible configurability. The use of a Linear Congruent Permutation (3GPP2 interleaver) for the Intra-line interleaving does not allow arbitrary increments (constant C in Linear Congruent calculation rule), but only those which are relatively prime to the interleaving length. embodiments a fast-rectangle interleaver, on the other hand, always allow a free one Choice of the number of columns, so also for the number There is a wide choice of lines available. Because of the greater freedom of choice exists here a higher potential, suitable parameters for to find a good performance.

Embodiments also offer the advantage that they can be implemented with less effort. For example, the 3GPP2 interleaver generates candidate addresses that are sometimes invalid. Thus, these interleavers require a special strategy to safely obtain a valid address every clock cycle, cf. z. Steven J. Halter, "Random-Access Multi-Directional CDMA2000 Turbo Code Interleaver", US Pat. No. 6,871,303 B2 , 2001. For this purpose, two candidate addresses are generated in each clock cycle. Therefore, feedback from one part of the algorithm checking the validity to another part is needed, which increments the counter and based on these two candidate addresses testifies.

At the Embodiments of fast-rectangular interleavers come no invalid candidate addresses, the algorithm needs no feedback and can be optimally pipelined be, d. H. it can be executed sequentially and no feedback is required. That's why Embodiments by this calculation rule in principle allow higher clock rates of the circuit as, for example, the 3GPP2 algorithm. embodiments thus offer the advantage of having good performance provided with low complexity and low memory requirements can be.

Especially It is noted that depending on the circumstances the inventive scheme also implemented in software can be. The implementation can be done on a digital storage medium, in particular a floppy disk, a flash memory, a CD or a DVD with electronically readable control signals, which can interact with a programmable computer system that the corresponding procedure is carried out. Generally Thus, the invention also exists in a computer program product with program code stored on a machine-readable carrier for carrying out the inventive Procedure when the computer program product runs on a computer. In other words, the invention can thus as a computer program with a program code for execution of the method realized when the computer program product runs on a computer.

1100

Turbo encoder

1105

first Component encoder

1110

Turbo code interleaver

1115

second Component encoder

1120

puncturer

1200

Flip-flop

1205

Flip-flop

1210

Flip-flop

1215

entrance

1220

output

1225

output

1230

Feedback path

1300

depuncturing

1305

first Component decoder

1310

second Component decoder

1315

Turbo code interleaver

1320

Turbo code deinterleaver

QUOTES INCLUDE IN THE DESCRIPTION

This list The documents listed by the applicant have been automated generated and is solely for better information recorded by the reader. The list is not part of the German Patent or utility model application. The DPMA takes over no liability for any errors or omissions.

Cited patent literature

• - EP 1030455 B1 [0037]
• US 6304991 B1 [0043]
• US 6871303 B2 [0043, 0143]

Cited non-patent literature

• - Claude Berrou, Alain Glavieux, and Punya Thitimajshima: "Near Shannon-Limit Error-Correcting Coding and Decoding: Turbo Codes", Intern. Conf. to Communication, pages 1064-1070, 1993 [0003]
• Todd K. Moon "Error Correction Coding", Wiley, 2007, ISBN 978-0-471-64800-0 [0014]
• Marco Breiling, "Analysis and Design of Turbo Code Interleavers", Shaker Verlag, Aachen, 2002 ISBN 3-8322-0302-8 [0021]
• - S. Crozier and P. Guinand: "High Performance Low Memory Interleaver Banks for Turbo Codes", in Proc. of the 54th IEEE Veh. Tech. Conf (VTC'01), Atlantic City, pp. 2394-2398, Oct. 2001 [0021]
• - Johan Hokfelt, Ove Edfors, and Torleiv Maseng: "Interleaver design for turbo codes based on the performance of iterative decoding", Intern. Conf. to Communications, Communications Theory Mini Conference, pages 93-97, 1999 [0022]
• Sergio Benedetto and Guido Montorsi: "Unveiling Turbo Codes: Some Results to Parallel Concatenated Coding Schemes", IEEE Trans. To Inform. Theory, 42 (2): 409-428, 1996 [0030]
• Dolinar and D. Divsalar: "Weight Distributions for Turbo Codes Using Random and Nonrandom Permutations", Jet Propulsion Lab, TDA Prog. Rep., 42-122: 56-65, 1995 [0035]
• - S. Crozier and P. Guinand: "High-performance low-memory interleaver banks for turbo-codes", in Proc. Of the 54th IEEE Veh. Tech. Conf (VTC'01), Atlantic City, pp. 2394-2398, Oct. 2001 [0036]

Claims (25)

Interleaver for scrambling an information word, wherein the information word has a plurality of locations to to obtain a permuted information word with the following features: one first interleaver stage for arranging the locations of the Information word in a plurality of first lines and first Columns, where the first lines have at least a first line with have a gap and the first columns at least have a first column with a gap; and one second interleaver stage for scrambling the digits of the a first line with the gap by swapping at least two places of a first line, so that a position of Gap remains unchanged to a first scrambled Line and replace one of the first lines with the first scrambled line; the first one Interleaver stage is designed to split the first columns read out and the places of the first columns gapless to string together to get the permuted information word. Interleaver according to claim 1, at the second interleaver stage is formed around the locations a first line through a linearly congruent interleaver rule to scramble, leaving a position of the gap remains unchanged at the first scrambled line and to replace one of the first lines with the first scrambled line. Interleaver according to one of the claims 1 or 2, in which the second interleaver stage is formed, to the line by line Arranging the locations of one of the first rows in a plurality of second rows and second columns, and column-wise readout the places to get a first scrambled line and replacing one of the first lines with the first one scrambled Line, wherein the first Interleaverstufe is adapted to the based on the first scrambled line replaced first Line by column and read out completely to the permuted To get information word. Interleaver according to one of the claims 1 to 3, further comprising a third interleaver stage formed is for arranging line indexes of the first lines by line in third rows and third columns, and for column-wise readout scrambled the line indices by. To get row indexes and swapping the first lines based on the scrambled ones Row indices, wherein the first interleaver stage is formed, to swap based on the scrambled line indexes first lines column by column and read out completely, um to get the permuted information word. Interleaver according to one of the claims 1 to 4, wherein the first, second and / or third interleaver formed is to process an information word in which each digit includes a binary digits. Interleaver according to one of the claims 1 to 5, wherein the second Interleaverstufe is formed to the Make a first line in a number of second lines and a number of second columns, the one first line has a number of digits smaller than that Product of the number of second lines and the number of second Columns, and the second Interleaverstufe further formed is, in the column-wise readings occurring gaps to skip. Interleaver according to one of the claims 4-6, wherein the third interleaver stage is formed around the row indexes in a number of third rows and a number of third Columns, where the number of row indexes is smaller as the product of the number of third lines and the number of third columns and the third interleaver stage further formed is, in the column-wise readings occurring gaps to skip. Interleaver according to one of the claims 1 to 7, wherein the first, second and / or third Interleaverstufe is designed to provide as information word a vector of reading or scrambling write addresses. An interleaver for scrambling an information word, the information word having a plurality of locations to obtain a permuted information word, comprising: a first interleaver stage for arranging the locations of the information word in a plurality of first rows and first columns; and a second interleaver stage for scrambling the locations of one of the first rows by arranging the locations of the one row in a plurality of second rows and second columns row by row, the second rows having at least one second row with a gap and the second columns at least one second Have gaps with a gap, and wherein the second Interleaverstufe is formed to read the locations of the second columns column by column and to line up seamlessly to a first scrambled line and for replacing the one of the first lines with the first scrambled line, wherein the first interleaver stage is adapted to read the first columns column by column to obtain the permuted information word. Interleaver according to claim 9, in which the first interleaver stage is designed to be line by line Arranging the locations of the information word in a plurality of first rows and first columns, with the first rows at least have a first row with a gap and the first one Columns have at least one first column with a gap, wherein the first interleaver stage is designed to be the first Columns column by column and the digits of the first columns to string together seamlessly to the permuted information word to obtain. Interleaver according to one of the claims 9 or 10, further comprising a third interleaver stage formed is for arranging line indexes of the first lines by line in third rows and third columns, and for column-wise readout the row indexes to get scrambled line indexes and swapping the first lines based on the scrambled ones Row indices, wherein the first interleaver stage is formed, to swap based on the scrambled line indexes first column by column to read the permuted information word to obtain. Interleaver according to one of the claims 9 to 11, wherein the first, second and / or third Interleaverstufe is configured to process an information word in which each digit comprises a binary digits. Interleaver according to one of the claims 9 to 12, wherein the third interleaver stage is adapted to the row indices in a number of third rows and a number of third Columns, where the number of row indexes is smaller as the product of the number of third lines and the number of third columns and the third interleaver stage further formed is, in the column-wise readings occurring gaps to skip. Interleaver according to one of the claims 9 to 13, wherein the first, second and / or third Interleaverstufe is designed to provide as information word a vector of reading or scrambling write addresses. Method for scrambling an information word, wherein the information word has a plurality of locations to to obtain a permuted information word, with the following steps line by line Arranging the locations of the information word in a plurality of first rows and first columns, with the first rows at least have a first row with a gap and the first one Columns have at least a first column with a gap; scrambling the places of a first line with the gap through Swap at least two digits of the first line, so that a position of the gap remains unchanged, to get a first scrambled line; Replace one of the first lines with the first scrambled Row; and Columnwise read out and the places of the first Rows without gaps to the permuted To get information word. Method for scrambling an information word, wherein the information word has a plurality of locations to to get a permuted information word with the following steps: line by line Arranging the locations of the information word in a plurality of first rows and first columns; Scrambling the bodies one of the first lines by arranging the positions line by line a first row in a plurality of second rows and second columns, wherein the second rows at least a second row with a gap and the second columns at least have a second column with a gap; column-wise Reading the digits of the second columns; Uninterrupted Line up the digits of the second columns to a first one to get scrambled line; Replace one the first lines with the first scrambled line; column-wise Reading out the first columns, around the permuted information word to obtain. An index generator for generating an output index based on an input index of a column number, an element number, and an incomplete line information, comprising: means for generating a line index based on the input index and the column number; means for generating a column index based on the input index and the column number; means for generating a full-line number based on the element number and the column number; means for generating a residual element number based on the element number and the column number; means for outputting the output index, which is arranged to, in the case where the column index is smaller than the residual element number, use the output index as Initial Index = (Full Time +1) Column Index + Row Index and otherwise, in the event that the incomplete line information indicates that there is no incomplete line or the line index is less than or equal to an index of an incomplete line, the source index is Initial index = (full-line number + 1) Remaining element number + full-line number (column index - remaining element number) + line index and otherwise the output index as Initial Index = (full-line number + 1) Remaining element number + full-line number (column index - residual element number) + line index-1 issue. Index generator according to claim 17, wherein the means for generating the row index is formed, around the row index by rounding off a quotient from the input index and to generate the number of columns. Index generator according to one of Claims 17 or 18, wherein the means for generating of the column index is adapted to the column index by a Modulus operation of the input index with the number of columns to generate. Index generator according to one of Claims 17 to 19, wherein the means for generating the full-line number is formed by the full-line number Rounding off a quotient of the number of elements and the number of columns to generate. Index generator according to one of Claims 17 to 20, wherein the means for generating the residual element number is formed by the residual element number by to generate a module operation of the element number with the number of columns. A method of generating an output index based on an input index of a column number, an element number, and an incomplete line information, comprising the steps of: generating a row index based on the input index and the column number; Generating a column index based on the input index and the column number; Generating a full-line number based on the number of elements and the number of columns; Generating a residual element number based on the element number and the column number; Output the output index, in case the column index is smaller than the residual element number, than Initial Index = (Full Time + 1) Column Index + Row Index and otherwise, in case the information about the incomplete line indicates that there is no incomplete line or the line index is less than or equal to an index of an incomplete line, when Starting index = (full number of lines + 1) remaining element number + full line number (column index - remaining element number) + line index, and otherwise than Initial Index = (full-line number + 1) Remainder element number + full-line number (column index - residual element number) + line index - 1. Computer program with a program code for execution one of the methods according to one of the claims 15, 16, or 22 if the program code is running on a processor becomes. Turbo coder with an interleaver according to a of claims 1 to 14 or an index generator according to a of claims 17 to 21. Turbo decoder with an interleaver according to a of claims 1 to 14 or an index generator according to a of claims 17 to 21.