Multiplex communications – Communication over free space – Repeater
Reexamination Certificate
2000-04-07
2004-06-01
Vu, Huy D. (Department: 2665)
Multiplex communications
Communication over free space
Repeater
C370S335000, C370S342000, C370S441000, C370S477000, C370S479000
Reexamination Certificate
active
06744744
ABSTRACT:
BACKGROUND
It is well known to perform interleaving of data in a communications system using forward error correction (FEC) in order, on deinterleaving, to distribute errors to facilitate their correction. Typically, such interleaving uses a block interleaver to interleave blocks of data. So-called turbo coding (parallel concatenated convolutional coding) uses an interleaver between inputs to two convolutional coders which produce respective parity bits from the input data before and after interleaving. With increasing attention being given to the use of turbo coding, particularly in wireless communications systems, attention has also been given to the form of the interleaver.
So-called 3rd generation CDMA (code division multiple access) wireless communications systems are also being developed which require a channel or inter-frame interleaver which operates to interleave or permute data in blocks corresponding to the radio frame duration, typically 10 ms. In such systems the channel interleaver either precedes or follows a rate matching function which serves to match various data rates to the radio frame rate, and which typically involves puncturing (omission) or repetition of data symbols, in this case data bits. It is desirable to distribute the omitted or repeated bits as evenly as possible, with as great a distance as possible between punctured or repeated bits in the de-interleaved frames, in a manner that is easy to implement and that is relatively independent of variables such as the frame-size, number of frames, and puncturing rate.
The present invention is concerned with rate matching in a manner which can be used with particular advantage for data after channel interleaving as described and claimed in the related application referred to above, but which is also applicable to other forms of interleaved data. This invention also provides improvements in and further applications of such channel interleaving.
SUMMARY OF THE INVENTION
According to one aspect, this invention provides a method of matching a rate of data bits, in a matrix of data bits interleaved by a predetermined interleaving process, to a desired rate by deletion of redundant data bits or repetition of data bits derived from the matrix, including the steps of: determining in a non-interleaved-matrix of said data bits a pattern of bits to be deleted or repeated to provide said desired data rate; decoding an address of each bit in said pattern in a manner inverse to the interleaving process to produce a respective address of the bit in the matrix of interleaved data bits; and deleting or repeating the respective bit in the interleaved data bits in dependence upon the respective address.
It is particularly advantageous, and may be necessary in practice, for the address decoding to be performed in the same manner as a coding of addresses for producing the interleaved data bits from the non-interleaved matrix of said data bits. This is facilitated in preferred embodiments of the method of the invention by the interleaving process comprising permuting rows and columns of a matrix of N
r
rows and N
c
columns, in which data bits to be interleaved are represented row by row, in accordance with:
Row Permutation I
r
(
k
)=[&agr;
r
k+f
c
(
l
)]modN
r
Column Permutation I
c
(
l
)=[&agr;
c
l+f
r
(
k
)]modN
c
where I
r
(k) represents a data bit with a row index k, k is an integer from 1 to N
r
, &agr;
r
is an integer, f
c
(l) is a non-zero function of a column index l, l is an integer from 1 to N
c
, I
c
(l) represents a data bit with the column index l, &agr;
c
is an integer, f
r
(k) is zero or a function of the row index k, and modN
r
and modN
c
represent modulo-N
r
and modulo-N
c
arithmetic respectively, interleaved data bits being derived from the matrix column by column.
It is currently considered optimum to choose f
c
(l)=ml+[N
r
+1]mod
2
, where m is an integer, m approximately equal to N
r
/N
c
, f
r
(k)=2k+[N
c
+1]mod
2
, and &agr;
r
as the largest prime number less than N
r
/log
2
(log
2
(N
r
)).
The invention also provides rate matching apparatus arranged for carrying out a method as recited above.
Another aspect of this invention provides a method of interleaving data bits comprising permuting rows and columns of a matrix of N
r
rows and N
c
columns, in which data bits to be interleaved are represented row by row, in accordance with:
Row Permutation I
r
(
k
)=[&agr;
r
k+f
c
(
l
)]modN
r
Column Permutation I
c
(
l
)=[&agr;
c
l+f
r
(
k
)]modN
c
where I
r
(k) represents a data bit with a row index k, k is an integer from 1 to N
r
, &agr;
r
is an integer, f
c
(l)=ml+[N
r
+1]mod
2
is a non-zero function of a column index l, l is an integer from 1 to N
c
, m is an integer, I
c
(l) represents a data bit with the column index l, &agr;
c
is an integer, f
r
(k)=2k+[N
c
+1]mod
2
, and mod
2
, modN
r
and modN
c
represent modulo-2, modulo-N
r
, and modulo-N
c
arithmetic respectively, interleaved data bits being derived from the matrix column by column.
The invention also provides a data interleaver arranged for carrying out this method.
Another aspect of the invention provides a method of interleaving and rate matching parallel concatenated convolutional coded data by deletion of coded data bits, the coded data bits comprising systematic bits and parity bits, including the steps of interleaving the systematic bits separately from the parity bits, and deleting parity bits from the interleaved parity bits to provide the rate matching.
A further aspect of the invention provides a method of interleaving and rate matching parallel concatenated convolutional coded data by repetition of coded data bits, the coded data bits comprising systematic bits and parity bits, including the steps of interleaving the systematic bits separately from the parity bits, and repeating parity bits of the interleaved parity bits with a greater repetition factor than any repetition of systematic bits of the interleaved systematic bits, to provide the rate matching.
The invention further provides coding, interleaving, and rate matching apparatus arranged to carry out these methods.
Yet another aspect of this invention relates to a method of shuffling interleaved and rate matched data streams in the manner described below with reference to
FIG. 4
of the drawings, and to the recursive application of this method to more than two such data streams.
REFERENCES:
patent: 5689511 (1997-11-01), Shimazaki et al.
patent: 6101626 (2000-08-01), Morelos-Zaragoza et al.
patent: 6147964 (2000-11-01), Black et al.
patent: 6170076 (2001-01-01), Kim
patent: 6370669 (2002-04-01), Eroz et al.
patent: 6430722 (2002-08-01), Eroz et al.
patent: 1 227 596 (2002-07-01), None
patent: WO 99 65148 (1999-12-01), None
European Search Report EP 00 30 3056 dated Nov. 11, 2002.
Baier A, et al—Design Study for a CDMA-Based Third-Generation Mobile Radio System IEEE Journal on Selected Areas in Communications, IEEE INC, New York vol. 12, No. 4,—May 1, 1994 pp. 733-743 XP000572845—Issn: 0733-8716.
Gosne Stephane
Leretaille Catherine
Tong Wen
Mintz Levin Cohn Ferris Glovsky and Popeo P.C.
Nortel Networks Limited
Ryman Daniel
LandOfFree
Rate matching and channel interleaving for a communications... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Rate matching and channel interleaving for a communications..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rate matching and channel interleaving for a communications... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3302963