Definitions, Terms, Elements
Address: Location of a bit value corresponding to frame. Bit: Single value of either 0 or 1 related to voltage values 0 and Vcc. Block Size: Block size of the input frame, according to 3GPP LTE standards.
eNB: Enhanced node B (Base Transceiver Station ) Encoder: Device, which encodes original data to avoid error in transmission due to noise
Decoder: Device, which decodes encoded data to original data FEC: Forward error correction FPGA: Field Programmable Gate Array LTE: Long Term Evolution. LUT: Look up table
Modulo: A modulo operation finds the remainder of division of one number by another.
Multiplier: Hardware construct to multiply two values Permutation: Refers to the interchange of data according to predefined rule
Quadratic permutation polynomial (QPP): Permutation, which uses
Polynomial of the form
(Ax2+Bx+C) modulo N RAM: Random Access Memory ROM: Read only memory SISO: Soft Input Soft Output UE: User Equipment. UMTS: Universal Mobile Telecommunications System

Introduction
Field of Invention
The present disclosure relates to generally to mobile communication systems, specifically to channel coding and particularly to the design of interleavers for turbo coding.
Background of Invention
The advent of modern communication system has established a good deal of emphasis of reliable and on time delivery of data with minimum errors as possible. The basis of the reliable communication system is the FEC block. In his breakthrough paper on information theory, Shannon [8] provided us with a law which provides a relation between the channel bandwidth and the information that can be transmitted in that channel for a given signal to noise ratio. In order to achieve the theoretical limits (Also known as Shannon limit), we need effective coding techniques. Various coding techniques have been invented to achieve the channel capacity namely Reed-Solomon, convolution and Low density parity codes.
Turbo codes is the latest class of these coding schemes developed in 1993, which provides a near Shannon limit performance [7].
Turbo codes make it possible to increase data rate without increasing the power of a transmission, or they can be used to decrease the amount of power used to transmit at a certain data rate.
In its simplest form turbo code comprises of two parallel-concatenated systematic convolution encoders, separated by an interleaver.
Interleaving is a key component of many digital communication systems involving forward error correction (FEC) coding. Interleaving the encoded symbols provides a form of time diversity to guard against localized corruption or bursts of errors. In the past the interleaving strategy was usually only weakly linked to the selected FEC scheme. Exceptions are concatenated FEC schemes

such as concatenated convolutional and Reed-Solomon codes. In this case, the interleaving parameters are usually carefully selected to match the error correcting capabilities of the codes involved. Recently, interleavers have become an even more integral part of the code design itself. Such is the case for Turbo and Turbo-like codes. The problem of finding good interleavers for such codes is an on-going area of research. Recently QPP interleavers have been proposed which offers good performance and infuse low computational complexity.
Patents in this field deal with improvising the performance, offering less computational complexity, efficient utilization of memory and less gates to implement the system (since almost all Turbo codes are implemented in hardware) and at last but not the least is increased operational frequency.
US patent number 6339834B1 named Interleaving with Golden section Increments disclose a method to reduce the size of memory to store the QPP interleaver parameters. The scope of this document is restricted to only to reduce the memory size but not computational complexity.
US patent number 20080115034A1 named QPP interleaver/De-interleaver for Turbo Codes discloses a method of interleaving wherein claimed that the computational complexity of QPP is reduced by removing multiplication and modulo operation and hence reducing the complexity of hardware. The process is explained as below.
pi(«) = [fi(i) + f2(i)A2]modK (1)
pi(i+1) = [ f,(i+1) + f2(i+1)A2 ] mod K (2)
pi(i+1) = [ (f!*i+ f2*iA2) + (f1+f2+2*f2*i) ] mod K (3)
pi(i+1) = [pi(i) + g(i)]modK (4)
Where pi(i) denotes interleaved addresses for different index i (i = 0 to K), ^ and f2 are parameters designed to give good performance for input block length K.


This reduces the number of comparisons but is still utilizes considerable number of arithmetic operations making the implementation slower on logic constraint systems such as FPGAs. Our current invention is an improvement over this by utilizing the inherent periodicity and modified table of constants. This invention also increases the operational frequency, reduces computational complexity and hence the gates utilized. Due to reduction in logic gates, hardware cost is reduced.
Brief Description Of The Figures and Tables
Figure 1: General block diagram of turbo encoder.
Figure 2: General block diagram of turbo decoder.
Figure 3: Block diagram of QPP interleaver.
Figure 4: Internal Block diagram of LUT.
Figure 5: Architectural view of Address generator for QPP interleaver.
Table 1: Derived Table of constants
Detailed Description Of Preferred Embodiments
The present invention generally involves turbo codes, hence anonymously used in this disclosure. Figure 1 shows a typical turbo encoder, which consists of two-recursive systematic convolution (RSC) encoder separated by a QPP interleaver. The turbo encoder processes a block of K information bits each time. The first RSC encoder, B12 takes the block of data as input S11 and produces K parity bits S12. The interleaved version S15 (output of QPP interleaver) of the same input block K is fed into the second RSC encoder B13, which produces another block of K parity bits S14. Typically, the output of a turbo encoder is the multiplexed, punctured, modulated and transmitted.

Figure 2 shows a typical Turbo Decoder block diagram. Turbo decoder mainly consists of two soft input soft output decoders, SIS01 (B21) and SIS02 (B22) respectively, QPP interleavers (B24 and B23) and de-interleaver (B25).
The function of the turbo decoder is to detect and correct errors. Those skilled in the art know that the data stream S21, S22, S24 will be affected by noise. The first decoder B21 operates on S21, S22 and S28 and produces the first extrinsic information S25. Similarly second decoder B22 operates on S23, S24 and S26, which produce the second extrinsic information S27. Where S26 is the interleaved version of S25. S27 is de-interleaved and fed to B21, since it is an iterative.decoding, the two decoders, for better bit error performance repeatedly process S28 and S27.
Turbo encoder and Decoder of Figurel and Figure2 respectively gives better performance when QPP interleaver is used (Block B24, B23 & B11). Quadratic permutation polynomial interleavers are a subset of polynomial interleavers [3] and are emphasized due to the ease of implementation. The performances of the Quadratic permutation polynomials (QPP) are better compared to other interleavers and can be efficiently implemented on FPGA.
Quadratic permutation polynomial (QPP) is the interleaving scheme for 3GPP LTE. LTE is the upcoming global standards for mobile communication, within third generation partnership project, to improve the UMTS mobile phone standard to cope with future technology evolutions. Quadratic permutation polynomials are used for the design of interleaver and de-interleaver. The general form of 3GPP specified QPP interleaver is given in equation 1.
Figure 3 shows the block diagram of QPP interleaver. The system takes input from an input port (S31) and both interleaved (S34) and non-interleaved data (S33) are the outputs of the system. Remaining signals are used to control the flow of data. The values of h and f2, they are presented in 3GPP LTE specifications 36.212[6].
Figure 3 shows the top-level architectural view of QPP interleaver, which mainly comprises memory unit (B31), address generator (B32), LUT (B33) and a control unit (B34). The Control unit (B34) issues all the control signals required for the other modules. LUT (B33) stores the values of f,+f2 mod K, 2*f2 mod K and

periodicity-1 in B331, B332 and B333 respectively as shown in Figure 4. Address generator (B32) reads the corresponding inputs and generates the original and interleaved address. Based on the original and interleaved address, the input data stored in Memory unit (B31) is fetched and provided as Original data (S33) and interleaved data (S34) outputs respectively.
The current implementation is an improvement over the previous low complexity implementation explained in prior aft. There are two important inventions. Namely,
1.Modified ROM tables
2.Periodicity
Modified ROM tables
Here in this implementation, the values of f, and f2 are not stored. Instead derivative values f,+f2 mod K and 2*f2 mod K are stored in the ROM B331 and B332 respectively. This reduces the calculations by four adders and two comparators during on the fly computation of QPP. The storing of the modified table is compatible with the original table and interoperability issues do not arise.
Along with these tables, a table consisting of periodicity-1 for each block length is also stored. Table 1 shows the f,+f2 mod K value, 2*f2 mod K value and Periodicity value to be stored in ROM:
Periodicity
The other part of invention is targeted at the periodicity that exists in the calculation process of interleaved address. The Periodicity is not in the values of interleaved address, but in the values of g (i), where g (i) is given from equation 5. For a given block size, the values for g (i) periodically repeats. The condition for this periodicity to take place is dependent on a defined value which intern depends on three parameters.

1. Block size.
2. f, value.
3. f2 value
For given values of Block size, f, value, f2 value and previous value of g (i), the algorithm for periodicity is as follows
Algorithm:
If (Block Size + f, value - f2 value) = Previous value of g (i)
Present value of g (i) = ^ value + f2 value
Else
Present value of g (i) = [Previous value of g (i) + 2*f2 value] mod Block size
No values of f, value and f2 value are stored in the Modified ROM tables. In order to calculate the value Block Size + f, value - f2 value we use the 2*f2 value and f,+f2 value as follows.
Block Size + f) value - f2 value = Block Size + ^ value - f2 value + f2 value - f2 value
= Block Size + (fi value + f2 value) - (f2 value + f2 value) = Block size + (ft + f2 value) - (2*f2 value)
From the above calculation We don't occupy any extra resources other than what is require in case if U value and f2 value are used.
Storage of calculated values of g (i) to RAM:
From the invention of periodicity, it is found that periodicity is not same for all the block sizes ranging from 40-6144. Although some block sizes have same periodicity, on whole the periodicity is spread uneven. But the maximum periodicity is found out to be 56.
The calculation of g (i) is done at the time of reading inputs to inputs storage RAM (B31). Since the g (i) values are calculated prior to calculation of interleaved address, a RAM (B324) is needed to store all these calculated g (i)

values. Since the maximum periodicity is 56 and each g (i) value is almost 13 bits, a RAM (B324) with size 56x13 bits is used.
All the 56 location are filled with the calculated values of g (i) even if the values repeat under the condition of periodicity. Once the RAM (B324) is filled, the calculation of g (i) is stopped and the RAM (B324) is disabled.
Periodicity ROM:
Prior to calculation of interleaved address, it is to be noted that the periodicity values for all corresponding block sizes in the range 40-6144 are stored into a ROM (B331) and should be retrieved at the time of g (i) read from the RAM (B324). The size of the ROM (B331) is 188x6 bits that correspond to 188 block sizes with its periodicity represented in 6 bits. In order to reduce some combinational logic (periodicity -1) values are stored instead of periodicity itself.
Table 1 shows the values stored in periodicity ROM (B331).
Reading the g (i) values from RAM:
Based on the periodicity-1 value, the read address for the RAM (B324) that stored g (i) values resets to zero indicating periodicity. The depth of the RAM (B324) read depends on the periodicity-1 value. The whole RAM (B324) i.e., 56 locations of g (i) are read for the block size with periodicity 56.
The values of g (i) read from the RAM (B324) are used for calculation of interleaved address efficiently.
Industrial applicability
Since the interleaver is the block determining the frequency in encoder operation in uplink chain of the LTE system eNB and UE, use of this technique will improve the performance of the overall FEC module for LTE uplink systems.
The use of the modified tables and the technique does not alter the interoperability because the table values are a derivation of the original and are compatible to other standards specific interleaver for 3GPP LTE 36212.830.

Claims
1: An apparatus for interleaving for 3GPP-LTE, which involves QPP, wherein the system uses a hardware implementation of the periodic property inherent in the QPP interleaver.
2: An apparatus of claim 1 wherein the QPP interleaver comprises of memory for storing modified values QPP co-efficients.
3: An apparatus of claim 1 wherein the QPP interleaver comprises of memory for storing periodicity.
4: An apparatus of claim 2 and 3 wherein the g (i) values are computed during reading input data into memory.
5: An apparatus of claim 2 and 3 is reduction in the number of arithmetic operations compared to prior art.
6: An apparatus of claim 5 reduces the calculations by four adders and two comparators during on the fly computation of QPP.
7: An apparatus of claim 6 is noted to have an increase in the operating frequency by decreased computational delay.
8: An apparatus of claim 6 reduces the number of gates.
9: An apparatus of claim 3 wherein storing the periodicity values reduces computational overhead by limiting the address computation up to periodicity.

Publication Background
1. O. Y. Takeshita and D. J. Costello, Jr,"On deterministic linear
interleavers for turbo-codes,"Proc. of 35th Annual Allerton Conference on Communication, Control and Computing, pp.711-712, Sept. 1997.
2. O. Y. Takeshita and D. J. Costello, Jr., "New deterministic
interleaver designs for turbo-codes," IEEE Trans. Inform. Theory,
vol. 46, no. 6, pp. 1988-2006, Sept. 2000.
3. S. Dolinar and D. Divsalar, "Weight distributions for turbo codes
using random and nonrandom permutations," TDA Progress Report
42-122, August 15, 1995.
4. S. Crozier, J. Lodge, P. Guinand and A. Hunt, "Performance of
Turbo Codes with Relative Prime and Golden Interleaving
Strategies," Proceedings of the 6th International Mobile Satellite
Conference (IMSC '99), Ottawa, Ontario, Canada, pp. 268-275,
June 16-18, 1999.
5. O. Y. Takeshita and D. J. Costello, Jr," New classes of algebraic
interleavers for turbo-codes,"Proc. 1998 IEEE International
Symposium on Information Theory, Boston, p. 419, Aug 16-21,
1998.
6. 3GPPLTE documentation (36212 v820)
7. Near Shannon limit error-correcting and decoding: Turbo codes
C Berrou, A Glavieux, P Thitimajshima - Proc. IEEE Int. Conf.
Commun, 1993
8. Claude E. Shannon, A Mathematical Theory of Communication
Urbana, ILUniversity of Illinois Press, 1949 (reprinted 1998).