Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-04-26
2003-07-29
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06601214
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a system and method employing a rate matching algorithm for providing optimized puncturing patterns for turbo encoded data in a communications network. More particularly, the present invention relates to a system and method employing a rate matching algorithm for providing an optimized pattern for puncturing parity bits of a turbo encoded data word of a given rate to produce a turbo encoded data word of a desired lower rate.
2. Description of the Related Art
Many communications devices, such as those used in satellite-based or terrestrial telecommunications networks, employ encoders for encoding data prior to transmission to increase the integrity of the transmitted data and thus reduce data receipt errors. One type of encoder suitable for use in data transmitters is referred to as a turbo encoder. A turbo encoder typically includes one or more constituent encoders which insert in the outgoing data stream one or more parity bits for each information-bearing data bit (information bit).
The number of parity bits per data bit in the outgoing data stream indicates the rate at which the outgoing data stream is encoded. For example, a rate ⅓ systematically-encoded data stream includes the input information-bearing data bits, as well as two parity bits per each information bit. In other words, the length of a data stream that is rate ⅓ encoded is increased by a factor of three. Similarly, a rate ½ systematically-encoded data stream includes one parity bit per each real information bit in the data stream. Hence, the length of a data stream that is rate ½ encoded is increased by a factor of two.
Due to data capacity limitations that may be present in certain communications networks, it is often necessary to decrease the rate and hence, the length, of a rate encoded data stream. For example, many communications networks transmit data in data packets or frames of a fixed size, which are transmitted in a time-division multiple access (TDMA) transmission scheme. Due to the fixed length of a data frame, a rate ⅓ data stream may be too long to fit within one data frame. However, the length of a data frame may be sufficient to contain a shorter rate ½ data stream. Hence, it may be desirable to decrease a rate ⅓ data stream to a rate ½ data stream so the data stream can be transmitted within one data frame.
One method of decreasing the rate of a data stream is referred to as puncturing the data stream. When a data stream is punctured, certain bits of the data stream are eliminated from the data stream transmission. For example, if a rate ⅓ data stream having a length of 3000 bits is punctured to a rate ½ data stream having a length of 2000 bits, 1000 bits of the rate ⅓ data stream are not transmitted.
In many systems employing convolutional coding, puncturing is ordinarily performed as a part of channel encoding so that optimal or nearly optimal puncturing patterns can be applied. In certain code-division multiple access (CDMA) systems employing convolutional encoding, the puncturing is performed by a generic “rate matching” function apart from the encoder, in order to simplify multiplexing of many disparate data streams onto a common set of physical channels. In such an environment, the available payload would not be known at the encoder and the required puncturing patterns would be complex. For rate ⅓ turbo codes, in which the turbo encoder produces two parity bits for every systematic information bit as discussed above, it is preferable to avoid puncturing any of the systematic bits and to spread the puncturing between constituent encoders as evenly as possible. However, known rate matching algorithms for systems using convolutional codes fail to meet the above mentioned turbo code puncturing guidelines.
Therefore, a need exists for a method and system for providing an algorithm for evenly puncturing parity bits of a turbo encoded data stream without puncturing any systematic data bits of the data stream.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a system and method employing a rate matching algorithm for providing optimized puncturing patterns for turbo encoded data in a communications network.
Another object of the present invention is to provide a system and method employing a rate matching algorithm for providing an optimized pattern for puncturing parity bits of a turbo encoded data word of a given rate to produce a turbo encoded data word of a desired lower rate, to thus eliminate bits from said turbo encoded data word to be transmitted by a transmitter.
A further object of the present invention is to provide a system and method employing a rate matching algorithm for providing optimized patterns for puncturing parity bits that have been inserted into a turbo encoded data word by different encoders so that substantially the same amount of parity bits provided by each encoder are punctured.
These and other objects of the present invention are substantially achieved by providing a system and method for puncturing bits of an encoded data word to reduce a total number of bits in the encoded data word to be transmitted by a transmitter of a communications system. The bits include information bits and parity bits. The system and method operate to determine a final desired number of bits to be transmitted in the encoded data word, and to determine a respective number of parity bits associated with each respective number of information bits. The system and method establish a first variable for identifying positions of the information bits in the data word, and establish a respective parity variable associated with each respective number of parity bits. For example, if the encoded data word is rate ⅓ encoded, two parity bits are associated with each information bit. Therefore, the system and method will establish two parity variables.
The system and method then operate to eliminate certain parity bits from transmission in the encoded word based on values of the first variable and each respective parity variable so that the final desired number of bits remain in the encoded data word. In doing so, the system and method organizes the bits into a systematic group and one or more parity groups. The system and method selects certain groups based on the final number of bits and eliminates at least one parity bit from each of the selected groups. To do this, the system and method periodically changes the values of the first variable and each respective parity variable based on at least one constant which has been determined based on the final amount, and determines whether to eliminate any of the parity bits of a particular group during each period in which the values of the first variable and each respective parity variable are changed.
REFERENCES:
patent: 5910182 (1999-06-01), Dent et al.
patent: 5970085 (1999-10-01), Yi
patent: 5987057 (1999-11-01), Song
patent: 6370669 (2002-04-01), Eroz et al.
patent: 6519732 (2003-02-01), Li
patent: WO 00/41343 (2000-07-01), None
LGIC, “Puncturing Algorithm for Turbo”, 3GPP/TSG/RAN/WG1#4 TDOC 338/99, Apr. 19-20, 1999, pp. 1-6, Yokohama, Japan, p. 1, line 1—p. 6, last line; figure 2.
Baker Stephen M.
Hughes Electronics Corporation
Sales Michael
Whelen John T.
LandOfFree
System and method employing a rate matching algorithm for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method employing a rate matching algorithm for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method employing a rate matching algorithm for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3015775