In the field of digital communications, turbo codes are a class of high performance error correction codes used to achieve maximal information transfer over a limited-bandwidth communication link, particularly in the presence of data-corrupting noise.
3GPP LTE (Long Term Evolution) is a name given to a project within the Third Generation Partnership Project (3GPP) to improve the UMTS (Universal Mobile Telecommunications System) mobile telephony standard, in order to cope with future requirements, such as improving efficiency, lowering costs, improving services, etc. Although the LTE is not a standard, per se, it is anticipated that a majority of modifications and extensions defined in the LTE, if not all of them, will be included within release 8 of the UMTS system. One such modification is the use of turbo codes for the channel coding scheme for transport blocks.
FIG. 1 illustrates an example of a turbo decoder 100, as is known in the art. The turbo decoder 100 is arranged to receive three sub-blocks of bits. The first sub-block of bits (xk) comprises an m-bit block of payload data (dk). The second sub-block comprises n/2 parity bits (Y1k) for the payload data, computed using a first recursive systematic convolutional (RSC) coder. The third sub-block comprises n/2 parity bits (Y2k) for a known permutation of the payload data, also computed using a second RSC coder. For the illustrated example, the second and third sub-blocks are received as a concatenated block. (Yk), and separated into their separate sub-blocks (Y1k) and (Y2k) by demultiplexing mechanism 110. The decoder 100 comprises two elementary decoders 120, 130, serially interconnected with an interleaver 140 located between the two decoders 120, 130 for de-interleaving data bits within received data blocks.
As is known in the art, an interleaver, such as the interleaver 140 illustrated in FIG. 1, receives a stream of data comprising m bit blocks of data, re-orders the data bits within each block according to some scheme, criteria, function, etc, and outputs the re-ordered data bits. A conventional method for performing such a task comprises receiving the m-bit data block to be interleaved and storing all m bits of data in a first buffer. Once all m bits of data have been received, they can then be stored in a second buffer in the new order, and once all the data bits have been re-ordered in the second buffer, the interleaved data block can be outputted.
Such a conventional method of performing interleaving suffers from the problems of requiring two buffers to store the block of m data bits, and having to wait until all m bits of data have been received before the data block can be re-ordered. As a result, such a conventional method is inefficient in terms of the time taken to perform the interleaving, since it must wait until all m bits of data have been received and stored within the first buffer before commencing the re-ordering.
One known method for bypassing the need for a second buffer comprises writing the received data into a buffer in the order in which it is received, and then reading it from the buffer in the order in which the data is to be interleaved. However, this technique is not feasible when the operation of turbo decoding is performed by multiple processors, whereby received data block are divided into a plurality of segments, each segment being decoded by a different processor. In this case reading data from the first buffer (which has yet to be de-interleaved) requires multiple instances of the same interleaver, one for each segment or processor, where each interleaver instance reads data from a different position within the buffer. As will be appreciated by a skilled artisan, this is much more complicated than simply writing the received data to the first buffer, and then interleaving the data and writing it to a second buffer prior to decoding. Accordingly, such a solution significantly increases the cost and complexity of development.
As previously mentioned, one modification proposed in the 3GPP LTE is the use of turbo codes for the channel coding scheme for transport blocks. In particular, the 3GPP LTE proposes the use of the Quadratic Permutation Polynomial (QPP) function:Pi(x)=(f1x+f2x2)% M where M, f1 and f2 are parameters, sets of which are predefined within the 3GPP LTE.
In an article entitled ‘On Quadratic Inverses for Quadratic Permutation Polynomials over Integer Rings’ by Jonghoon Ryu and Oscar Y. Takeshita from the department of Electrical and Computer Engineering of The Ohio State University, submitted as a Correspondence to the IEEE Transactions on Information Theory on Apr. 1, 2005 (and revised Nov. 15, 2005) (http://arxiv.org/pdf/cs.IT/0511060), it is proposed to use quadratic inverse functions for some of the parameter sets for the QPP function defined in the 3GPP LTE.
As will be appreciated, the use of an inverse function enables a location of a data bit within the re-ordered/interleaved data block to be determined as the data bit is received. Accordingly, the data bit may be stored directly into its interleaved location within an interleaved buffer. For example, in a case where a block of data bits (b0, b1, b2, b3, b4) is to be interleaved according to an interleaving function f defining the new order of the data bits as being (2, 3, 4, 0, 1), the data bits are reordered to (b2, b3, b4, b0, b1). The inversed interleaving function f−1 defines the relative position of the data bits within the reordered block for each bit (3, 4, 0, 1, 2). Thus, b0 may be stored directly into position ‘3’ of the buffer, b1 may be stored directly into position ‘4’ of the buffer, b2 may be stored directly into position ‘0’ of the buffer, etc.
In this manner, it is not necessary to wait until all data bits within an interleaving block have been received before the interleaving can be performed, since the interleaving is performed ‘on the fly’.
However, a problem with the use of quadratic inversions is that such inversions are not readily available for all of the parameter sets for the QPP function defined in the 3GPP LTE. Accordingly, this does not provide a practical solution for interleavers that are required to perform interleaving of a data stream for each of the parameter sets for the QPP function defined in the 3GPP LTE.