Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-06-01
2002-05-07
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06385752
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to a method and apparatus for puncturing a convolutionally encoded bit stream. More particularly it relates to improved puncture matrices for use in TDMA (time division multiple access) and GSM (Global System for Mobile Communications) applications such as EDGE (enhanced data rate for GSM evolution).
BACKGROUND OF THE INVENTION
Many communication systems process a block of data for transmission by first convolutionally encoding it to produce an encoded block, then puncturing the convolutionally encoded block by removing a certain number of bits to produce a punctured encoded block which has a proper size for interleaving, and finally by interleaving the punctured encoded block.
For example, EDGE is a next generation GSM TDMA standard in which, before being transmitted in bursts, 20 ms blocks of data are convolutionally encoded, punctured, and rectangularly interleaved over four bursts.
The conventional approach to performing such puncturing for GSM has been to spread the puncture locations uniformly throughout the encoded bursts, puncturing a single bit at each location, never puncturing consecutive bits. The thought process historically has been that puncturing consecutive bits would produce more errors and as such inferior performance.
Other approaches for performing puncturing which are not tailored to a GSM environment are taught in U.S. Pat. No. 5,438,590 which issued Aug. 1, 1995 to Tzukerman et al. In this example, the puncturing is performed after the interleaving for a completely different purpose. Several puncturing matrices are proposed which include consecutively punctured bits, but the consecutively punctured bits are not evenly spaced, and the number of consecutively punctured bits is unrelated to the rate of the convolutional code. The puncturing is optimized for a very particular application unrelated to the problem at hand.
U.S. Pat. No. 5,668,820 which issued Sep. 16, 1998 to Ramesh et al. teaches a coder with a convolutional coding circuit of rate k
to produce a convolutionally coded output, and a puncturing circuit for puncturing the convolutionally coded output to achieve a punctured code rate of z/q, where z=&ggr;k. The puncturing circuit punctures the convolutionally coded output according to a deleting pattern chosen to have a bit length of L=p&ggr;n, where p>=2. The puncturing circuit outputs a punctured output at a punctured code rate of z/q. The purpose of the puncturing is to output data at a coded rate which is larger than the convolutional code rate and to thereby improve throughput.
U.S. Pat. No. 5,511,082 which issued Apr. 23, 1996 to How et al. teaches three very specific punctured convolutional encoders. In these encoders, a rate ½ code is punctured to rates ¾, ⅘ and {fraction (6/7)} respectively using various specific puncturing maps.
It would be desirable to have a method and system for performing puncturing, for example in the GSM environment, which leads to performance improvements over existing methods.
SUMMARY OF THE INVENTION
It is an object of the invention to obviate or mitigate one or more of the above identified disadvantages.
According to a broad aspect, the invention provides a method of puncturing a convolutionally encoded bit stream consisting of an input bit stream which has been convolutionally encoded at a coding rate of k
to produce the convolutionally encoded bit stream such that for each k-bit block of data to be encoded, an n-bit block in the convolutionally encoded bit stream is produced, where k>=1, and n>k. The method involves puncturing the convolutionally encoded data in only clusters of n consecutive bits each. Preferably, each cluster is aligned with a respective one of the k-bit blocks.
The puncturing is done in a manner which punctures sufficient bits from input blocks of L bits such that blocks of M bits each remain, where M is a required block size for interleaving. Preferably, the clusters are equally spaced throughout each L-bit block of bits.
In preferred embodiments, the new methods are applied to encoding schemes in accordance with existing EDGE standards for PCS-4 and PCS-5, but with modifications to the puncturing matrix used.
For PCS-5 in one case, the blocks to be punctured have a size of L=2422, and these need to be punctured such that M=1384 bits remain. A puncturing matrix is preferably defined by P(n)=1 ∀n In except for n=14k+2, 14k+3, 14k+6, 14k+7, 14k+10, 14k+11, k&egr;
0
, . . . , 172 where P(n)=0 where P(n)=1 means the nth bit location in the L-bit block is not punctured and P(n)=0 means the nth bit location in the L-bit block is punctured.
For PCS-5 in another case, the blocks to be punctured have a size of L=2306, and these need to be punctured such that M=1384 bits remain. A puncturing matrix is preferably defined by P(n)=1, ∀n except for n=10k+4, 10k+5, 10k+8, 10k+9k&egr;0, . . . , 229, and n=2304,2305 where P(n)=0 where P(n)=1 means the nth bit location in the L-bit block is not punctured and P(n)=0 means the nth bit location in the L-bit block is punctured.
For PCS-4, the blocks to be punctured have a size of L=2076 and M is again 1384. Preferably the puncturing matrix is defined by P(n)=1, ∀n except for n=12k+2, 12k+3, 12k+8, 12k+9 k&egr;0, . . . , 172 where P(n)=0.
According to another broad aspect, the invention provides an apparatus having a transmission mask circuit which punctures bits from L-bit blocks so as to produce M-bit blocks, where L,M are integers and M<L, and having a puncturing matrix memory defining a series of bit locations to puncture, the bit locations to puncture consisting of clusters of n consecutive bit locations each where n>=2.
The apparatus may further include a convolutional encoder for encoding an input bit stream at a rate k
to produce a bit stream containing the L-bit blocks, where k<n, and/or an interleaver for performing interleaving on the M-bit blocks.
REFERENCES:
patent: 5438590 (1995-08-01), Tsukerman et al.
patent: 5511082 (1996-04-01), How et al.
patent: 5668820 (1997-09-01), Ramesh et al.
patent: 6170076 (2001-01-01), Kim
patent: 6209116 (2001-03-01), Hammons, Jr. et al.
patent: 0643510 (1994-09-01), None
Matsuoka et al., adaptive modulation system with punctured convolutional code for high quality personal communication systems, IEEE, p. 22-23, 1995.*
Pirhonen et al., Single slot 14.4K bit/s service for GMS, IEEE, p. 943-947, 1996.
Chase Shelly A.
De'cady Albert
Nortel Networks Limited
LandOfFree
Method and apparatus for puncturing a convolutionally... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for puncturing a convolutionally..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for puncturing a convolutionally... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2875128