Title of Invention	A METHOD FOR GENERATING AND IMPLEMENTING A RANDOM INTERLEAVER FOR MULTILEVEL INTERLEAVING
Abstract	This patent presents a novel method and technique for designing an interleaver for turbo code, which outperforms the interleavers reported in the literature. The two main issues in the interleaver design are the interleaver size and the interleaver map. The size of the interleaver plays an important role in the trade off between performance and delay. On the other hand the map of the interleaver plays an important role in setting the code performance. Another key role of the interleaver is to shape the weight distribution of the code, which ultimately controls its performance. The invention proposes a Bit reversed interleaver, which optimizes the map and weight distribution. (Fig 1)

Title of Invention

A METHOD FOR GENERATING AND IMPLEMENTING A RANDOM INTERLEAVER FOR MULTILEVEL INTERLEAVING

Abstract

This patent presents a novel method and technique for designing an interleaver for turbo code, which outperforms the interleavers reported in the literature. The two main issues in the interleaver design are the interleaver size and the interleaver map. The size of the interleaver plays an important role in the trade off between performance and delay. On the other hand the map of the interleaver plays an important role in setting the code performance. Another key role of the interleaver is to shape the weight distribution of the code, which ultimately controls its performance. The invention proposes a Bit reversed interleaver, which optimizes the map and weight distribution. (Fig 1)

Full Text	Title A method for generating and implementing a random interleaver for turbo code Background of the invention The present invention is in the filed of communication and coding. It proposes a novel method and technique for designing an interleaver for turbo code which outperforms the interleavers reported in the literature. Turbo coding represents a new and powerful error control technique, allowing communication very close to Shannon capacity. The main component of a turbo code is the interleaver, which determines the efficiency and effectiveness of error correcting capability at very low signal to noise ratio. Interleaving is the process of rearranging the ordering of a symbol sequence. It has been widely used in conjunction with the error control coding for channels exhibit burst error characteristics and in concatenated codes, particularly in the turbo codes. The interleaver in the turbo code is used to permute the input bits such that the constituent encoders are operating on the same set of input bits, but in different order. The basic role of the interleaver design is in the interleaver size and the interleaver map. The size of the interleaver plays an important role in the trade off between performance and delay. On the other hand the map of the interleaver plays an important role in setting the code performance. Another key role of the interleaver is to shape the weight distribution of the code, which ultimately controls its performance. Forward Error Correcting (FEC) codes find applications in almost all fields, especially in Audio, Video and Data communication area. Turbo or interactive codes are the ultimate choice in case of burst error channel performance, with tremendous advantage in coding gain at very low signal to noise ratio. However the performance of the code depends mainly on the constituent encoders and the interleaver. A good interleaver provides considerable weight distribution in the code patterns. The present invention is a novel and improved technique in the design of interleaver. A near random interleaving of data is achieved in this technique. The capability of a random distribution of data is the characteristic of a good interleaver. Summary of the Invention: In the proposed scheme, the successive data are separated far apart in all cases. The separated data are processes as a group and hence at any stage, there is no chance of original data coming together in successive locations. Also there is no performance degradation under different operating conditions. The primary objective of this invention is to propose an innovative method and technique for the design of an interleaver for Turbo code, which outperforms the existing methods. Another objective of the present invention is to design an interleaver based on a deterministic structure and procedure so as to improve the decoding of the code and also to identify a simple hardware for implementing the interleaving process. Brief description of the drawings Figure 1 : Block diagram for the proposed interleaver implementation Detailed description of the invention Interleaving is a way of arranging data in a non-contiguous way in order to increase performance. It is used in time-division multiplexing (TDM) in telecommunications, computer memory and disk storage. Turbo codes are a class of high performance error codes, which provides increase in data rate without increasing the power of transmission. Figure 1 illustrates a block diagram of the proposed interleaver. Item 1 of Figure 1 is the basic memory unit where the data is stored sequentially before interleaving. The memory address is generated by item 2 for storing the data. This address generator is a simple program counter used in any microprocessor system. After storing each data, item 2 increments the address by one and stores the data in this location. This process is continued till all the data are stored in memory. The performance of the proposed interleaver with block interleaver is studied and tabulated below DBI 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 RI 8 11 12 15 16 4 7 14 2 5 3 6 9 10 13 1 BI 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16 Where DBI is the data before interleaving, RI - random interleaving and BI- block interleaving. For random interleaver bit at the 7th position is not changed. But for block interleaver bits at a positions, 6, 11, 16 are not changed. Then we will calculate all values of i-j and JI(i) - JI(j) (for I==l, 2.. 16 and j = 1,2... 16) for both interleaver where JI(i) represents the bit position after interleaving. Block interleaver violates the interleaver design rule three, for 32 times (i.e. I-j and n (i) -JI(j) both should not be a multiple of 'p'. They are shown in the table given below. Table 1 shows data during the interleaving process for a block size of 16. From these we can understand that random interleaver performs better than block interleaver. Similar studies were carried out for other pattern and shows improvement over block interleaver. This is a novel and simple technique for generating an interleaver with randomness property. Encoding and decoding of the proposed interleaver is mathematically tractable and implementation is very simple. The proposed method can be extended to block length, which is a power of 4, 8 etc. and can be used for multilevel interleaving. It reduces the noise floor effect in Turbo codes and the codes generated will have a uniform weight distribution thus optimising error performance. WE CLAIM; 1. A method for generating and implementing a random interleaver for multilevel interleaving wherein the said method is based on deterministic structure comprising the steps of generating the address for storing the data using a counter in a microprocessor system; storing data sequentially in a basic memory unit with the address generated; reading out the stored data and applying it to the constituent encoder wherein the address for reading out data is generated in a bit-reversed order and applied to the memory unit, optimising the map and weight distribution. 2. The method as claimed in claim 1 wherein the encoding and decoding is performed by bit reversing and the message block is a power of 2. 3. The method as claimed in claim 1 wherein the address generated to store successive data are far apart and processed as groups. Dated this 23 day of November 2007

Full Text

Title
A method for generating and implementing a random interleaver for turbo code Background of the invention
The present invention is in the filed of communication and coding. It proposes a novel method and technique for designing an interleaver for turbo code which outperforms the interleavers reported in the literature. Turbo coding represents a new and powerful error control technique, allowing communication very close to Shannon capacity. The main component of a turbo code is the interleaver, which determines the efficiency and effectiveness of error correcting capability at very low signal to noise ratio. Interleaving is the process of rearranging the ordering of a symbol sequence. It has been widely used in conjunction with the error control coding for channels exhibit burst error characteristics and in concatenated codes, particularly in the turbo codes. The interleaver in the turbo code is used to permute the input bits such that the constituent encoders are operating on the same set of input bits, but in different order. The basic role of the interleaver design is in the interleaver size and the interleaver map. The size of the interleaver plays an important role in the trade off between performance and delay. On the other hand the map of the interleaver plays an important role in setting the code performance. Another key role of the interleaver is to shape the weight distribution of the code, which ultimately controls its performance.
Forward Error Correcting (FEC) codes find applications in almost all fields, especially in Audio, Video and Data communication area. Turbo or interactive

codes are the ultimate choice in case of burst error channel performance, with tremendous advantage in coding gain at very low signal to noise ratio. However the performance of the code depends mainly on the constituent encoders and the interleaver. A good interleaver provides considerable weight distribution in the code patterns. The present invention is a novel and improved technique in the design of interleaver. A near random interleaving of data is achieved in this technique. The capability of a random distribution of data is the characteristic of a good interleaver.
Summary of the Invention:
In the proposed scheme, the successive data are separated far apart in all cases. The separated data are processes as a group and hence at any stage, there is no chance of original data coming together in successive locations. Also there is no performance degradation under different operating conditions. The primary objective of this invention is to propose an innovative method and technique for the design of an interleaver for Turbo code, which outperforms the existing methods. Another objective of the present invention is to design an interleaver based on a deterministic structure and procedure so as to improve the decoding of the code and also to identify a simple hardware for implementing the interleaving process.
Brief description of the drawings
Figure 1 : Block diagram for the proposed interleaver implementation

Detailed description of the invention
Interleaving is a way of arranging data in a non-contiguous way in order to increase performance. It is used in time-division multiplexing (TDM) in telecommunications, computer memory and disk storage. Turbo codes are a class of high performance error codes, which provides increase in data rate without increasing the power of transmission.
Figure 1 illustrates a block diagram of the proposed interleaver. Item 1 of Figure 1 is the basic memory unit where the data is stored sequentially before interleaving. The memory address is generated by item 2 for storing the data. This address generator is a simple program counter used in any microprocessor system. After storing each data, item 2 increments the address by one and stores the data in this location. This process is continued till all the data are stored in memory.
The performance of the proposed interleaver with block interleaver is studied and tabulated below

DBI 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
RI 8 11 12 15 16 4 7 14 2 5 3 6 9 10 13 1
BI 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16
Where DBI is the data before interleaving, RI - random interleaving and BI- block interleaving. For random interleaver bit at the 7th position is not changed. But for block interleaver bits at a positions, 6, 11, 16 are not changed. Then we will calculate all values of i-j and JI(i) - JI(j) (for I==l, 2.. 16 and j = 1,2... 16) for both

interleaver where JI(i) represents the bit position after interleaving. Block interleaver violates the interleaver design rule three, for 32 times (i.e. I-j and n (i) -JI(j) both should not be a multiple of 'p'. They are shown in the table given below.

Table 1 shows data during the interleaving process for a block size of 16. From these we can understand that random interleaver performs better than block interleaver. Similar studies were carried out for other pattern and shows improvement over block interleaver. This is a novel and simple technique for generating an interleaver with randomness property. Encoding and decoding of the proposed interleaver is mathematically tractable and implementation is very simple. The proposed method can be extended to block length, which is a power of 4, 8 etc. and can be used for multilevel interleaving. It reduces the noise floor effect in Turbo codes and the codes generated will have a uniform weight distribution thus optimising error performance.

WE CLAIM;
1. A method for generating and implementing a random interleaver for
multilevel interleaving wherein the said method is based on deterministic
structure comprising the steps of generating the address for storing the data
using a counter in a microprocessor system; storing data sequentially in a
basic memory unit with the address generated; reading out the stored data
and applying it to the constituent encoder wherein the address for reading
out data is generated in a bit-reversed order and applied to the memory unit,
optimising the map and weight distribution.
2. The method as claimed in claim 1 wherein the encoding and decoding is
performed by bit reversing and the message block is a power of 2.
3. The method as claimed in claim 1 wherein the address generated to store
successive data are far apart and processed as groups.
Dated this 23 day of November 2007

Documents:

http://ipindiaonline.gov.in/patentsearch/GrantedSearch/viewdoc.aspx?id=vuIKNvVjC1J8gFhwXGlBPQ==&loc=egcICQiyoj82NGgGrC5ChA==

« Previous Patent

Next Patent »

Patent Number

269139

Indian Patent Application Number

2753/CHE/2007

PG Journal Number

41/2015

Publication Date

09-Oct-2015

Grant Date

01-Oct-2015

Date of Filing

23-Nov-2007

Name of Patentee

INDIAN SPACE RESEARCH ORGANISATION

Applicant Address

ISRO HEADQUATERS, DEPARTMENT OF SPACE, ANTARIKSH BHAVAN, NEW BEL ROAD, BANGALORE 560094, INDIA

Inventors:

#	Inventor's Name	Inventor's Address
1	THAKADIYIL JOSEPH APREN	C/O VIKRAM SARABHAI SPACE CENTRE, THIRUVANANTHAPURAM-695 013, KERALA STATE, INDIA
2	ASHOK KUMAR YELLAJOSYULA	C/O VIKRAM SARABHAI SPACE CENTRE, THIRUVANANTHAPURAM-695 013, KERALA STATE, INDIA

PCT International Classification Number

H04L 27/10

PCT International Application Number

N/A

PCT International Filing date

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1			NA