GB2369274A

GB2369274A - Interleaving by data permutation without a matrix

Info

Publication number: GB2369274A
Application number: GB0028099A
Authority: GB
Inventors: Paul Cook
Original assignee: Ubinetics Ltd
Current assignee: Aeroflex Cambridge Ltd
Priority date: 2000-11-17
Filing date: 2000-11-17
Publication date: 2002-05-22
Also published as: GB0028099D0; WO2002041501A1; AU2002223828A1

Abstract

Prior art de/interleavers load data into a matrix permute the rows and/or columns of the matrix and then read out the contents of the matrix as the de/interleaved data stream. The invention implements an interleaver or a deinterleaver that reorders an input data sequence into an de/interleaved output data sequence by reading out the data items of the input data sequence in the requisite order to produce the output data sequence, without recourse to loading the data into a matrix for manipulation therein. The order in which the data is output may emulate the prior art matrix based systems.

Description

DATA PERMUTATION The invention relates to data permutation and, in particular, to data interleaving and deinterleaving in communications systems.

Interleaving is used to provide enhanced error recovery. In a transmitter, a stream of data bits to be transmitted are interleaved, i. e. permuted from their original order. The interleaved data is then transmitted to a receiver, which deinterleaves the received stream of data bits by applying a permutation which is the inverse of the permutation applied by the transmitter. If the received data stream contains an error of several bits in length, then after deinterleaving into the original order, the error bits are dispersed through the

datastream, and these isolated errors can be corrected more easily.

Generally speaking, an interleaver takes a block of K data elements x (0), x (l),...... x (K-l) (represented generically as x (k), where k=0 to K-1) and permutes them resulting in an interleaved set of data elements y (O), y (l),........ y (K-l) (represented generically as y (z), where z=0 to K-1) which contain the same set of data values but in a different order. In a known interleaver, the permutation is achieved in the following way.

The data x (k) is written into a rectangular matrix Ml. Ml has elements MIl), where i and j denote, respectively, the row and column of an element. Where MI has R rows and C columns, i=O to R-1 and j =0 to C-1. The data is written into Ml beginning with entry Mloo, then Mlol, M102, and working from left to right until row zero is full and then proceeding to store data elements into row 1 beginning at Mlio. This process continues from row to row until all of the K data elements have been placed into Ml. It will be apparent that there is a possibility that K will be less than, as opposed to equal to, RC (the number of elements in M1), meaning that some of the final rows (i=R-l, R-2,.....) of Ml will be incomplete. If this is the case, then the empty entries at the end of the final row are packed with blanks.

MI then undergoes an inter-row permutation function, P, to produce a new matrix M2 having entries M2ab where a and b denote, respectively, the row and column of an element. The permutation function P has the effect that the entry Ml, j is transferred to M2ab such that a=P (i) and j=b (the entry remains in the same column).

M2 is then subjected to a series of intra-row permutation functions Qr to produce a matrix M3 having elements M3nm, where n and m denote, respectively, the row and column of the elements. The index r indicates the intra-row permutation function applicable to the rIb row of M2, where r=0 to R-1. Each of the permutation functions Qr reorders the elements within its corresponding row. The permutation function Qr has the effect that the entry M2ab is transferred to M3mn such that n=a=P (i) (the entry remains in the same row) and m=Qa (b) = Qp (J).

The interleaved data sequence y (z) is then read column-by-column out of M3, beginning with the leftmost column and reading down each column, i. e. starting at n=0, ni=0, then n=l, m=O, progressing to n=R-l, m=0 and then to n=0, m=l, and so on until the task is completed by reading out the entry at n=R-1, m=C-1. Note that where the size of the matrix RC is larger than the length K of the input data sequence x (k), the process of reading out y (z) from M3 must skip over the blanks inserted in the final rows of Mi, meaning that the interleaver must keep track of the positions to which the added blanks have migrated in M3.

The invention seeks to provide improved methods and apparatus for data permutation.

According to one aspect, the invention provides a method of interleaving the data values of a data sequence, comprising reading out data items from a first data sequence in an interleaved order as an interleaved data sequence.

According to another, and related, aspect, the invention also provides apparatus for interleaving the data values of a data sequence, comprising means for reading out data items from a first data sequence in an interleaved order as an interleaved data sequence. According to a further aspect, the invention provides a method of deinterleaving the data values of a data sequence, comprising reading out data items from an interleaved first data sequence in a deinterleaved order as a deinterleaved data sequence.

According to another, and related, aspect, the invention also provides apparatus for deinterleaving the data values of a data sequence, comprising means for reading out data items from an interleaved first data sequence in a deinterleaved order as a deinterleaved data sequence.

Hence, the invention provides the output data sequence directly from the first data sequence. This means that the invention does not need to employ the memory intensive and time consuming techniques of known interleavers and deinterleavers, e. g. loading the first data sequence into a matrix, and creating and storing modified matrices.

The invention also extends to a program for implementing the data sequence permutation methods of the invention.

In a preferred embodiment, the inventive data sequence permutation methods and apparatus are used in a communications systems for processing received and transmitted signals. For example, the deinterleaving and interleaving techniques can be applied to received and transmitted signals, respectively, in a Turbo code interleaver used for channel coding in 3G mobile telephones. A Turbo code interleaver operates on data sequences of up to around 5000 bits in length and may be used to interleave/deinterleave bit-rate data for uplink and downlink channels respectively.

By way of example only, an embodiment of the invention will now be described.

The interleaver of the embodiment can be implemented either as dedicated hardware in the form of an integrated circuit or in the form of software that can be executed using data processing and data storage resources. The interleaver achieves the conversion of an input data sequence x (k) into an output sequence y (z) as performed by the described prior art without creating the matrices Ml, M2 and M3. The interleaver reads the data elements in the order y (z) directly from the order x (k).

In the prior art interleaving process, the input data sequence x (k) was loaded into matrix MI. The position of an element x (k) in Ml was Mol,, where i = k div C and j = k mod C, where div and mod denote standard integer division and remainder, respectively, and C

denotes the number of columns in Ml. From these equations, one obtains k = iC + j. Given that, in the prior art approach, the position of j in M3 is M3mn where n = P (i) and m = Q p (,) (j) n then i = polen) and j = Qn-' (m). P''is the inverse function of P and Qn'is the inverse function of Qn This gives the result that : k = iC + j = C P-' (n) + Qn-' (m) (Eq. 1) I In the prior art interleaver, the sequence y (z) was produced by reading down each of the columns of M3, commencing with column n==0 and finishing with column n = C-1. Within each column, the entries are read from m=O to R-1. By incrementing n and m in the same way, the interleaver of the embodiment uses equation 1 to produce a value of k for each pair of n, m values. Provided that k < K, the corresponding value of the input sequence x (k) is provided as the next value of y (z). This step is equivalent to reading out the values in M3 in the prior art and skipping over values which correspond to blanks packed into the final entries of MI. Thus, the interleaver of the embodiment produces the sequence y (z) directly from the sequence x (k).

The process of generating y (z) from x (k) is best illustrated by the following pseudo-code listing: 1) z=O 2) loop for m = 0 to C-l 3) loop for n = 0 to R-l 4) let k = C P-1(n) + Qn-1(m) 5) if k < K 6) copy x (k) to y (z) 7) z=z+1 8) end if 9) loop n 10) loop m The invention can also carry out deinterleaving. In the exemplary embodiment, deinterleaving can be performed simply by swapping k and z in line (6).

Claims

CLAIMS 1. A method of interleaving the data values of a data sequence, comprising reading out data items from a first data sequence in an interleaved order as an interleaved data sequence.
2. A method of deinterleaving the data values of a data sequence, comprising reading out data items from an interleaved first data sequence in a deinterleaved order as a deinterleaved data sequence.
3. A method according to claim 1 or 2, wherein the order in which the data items are read out from the first sequence is equivalent to loading the data items of the first sequence into a matrix in a first manner and reading the data items out of the matrix in a second manner.
4. A method according to any one of claims 1 to 3, wherein the order in which the data items are read out from the first sequence is equivalent to loading the data items of the first sequence into a matrix, permuting at least some of the rows and/or at least some of the columns of the matrix, and reading the data values out of the matrix.
5. A program for performing the method of any one of claims 1 to 4.
6. Apparatus for interleaving the data values of a data sequence, comprising means for reading out data items from a first data sequence in an interleaved order as an interleaved data sequence.
7. Apparatus for deinterleaving the data values of a data sequence, comprising means for reading out data items from an interleaved first data sequence in a deinterleaved order as a deinterleaved data sequence.
8. Apparatus according to claim 6 or 7, wherein the means for reading out data items is arranged to read out data items from the first sequence in an order equivalent to loading the data items of the first sequence into a matrix in a first manner and reading the data items out of the matrix in a second manner.
9. Apparatus according to any one of claims 6 to 8, wherein the means for reading out data items is arranged to read out data items from the first sequence in an order equivalent to loading the data items of the first sequence into a matrix, permuting at least some of the rows and/or least some of the columns of the matrix and reading the data values out of the matrix.
10. Apparatus for interleaving a data sequence, substantially as hereinbefore described.
11. Apparatus for deinterleaving a data sequence, substantially as hereinbefore described.
12. A method of interleaving a data sequence, substantially as hereinbefore described.
13. A method of deinterleaving a data sequence, substantially as hereinbefore described.