Coded data generation or conversion – Digital code to digital code converters – With error detection or correction
Reexamination Certificate
1999-11-23
2002-03-05
Wamsley, Patrick (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
With error detection or correction
C714S746000, C714S790000
Reexamination Certificate
active
06353400
ABSTRACT:
CROSS REFERENCE TO RELATED APPLICATIONS
BACKGROUND OF THE INVENTION
1. Field of the Invention.
This invention relates to communications equipment, and more particularly to encoding and decoding data transmissions from and to such equipment, and still more particularly to testing such equipment transmissions including such encoding and decoding.
2. Prior Art
There is a continuing need for simple, low cost apparatus for testing cellular mobile phones or base stations, where the testing equipment is connected in such a way that very high signal-to-noise ratios exist, no multipaths exist, and little interference is present. To enable this testing often requires decoding convolutionally encoded data streams with methods that accommodate minimum complexity, but which still accommodate puncturing and blind rate determination. Present methods have complexities that are orders of magnitude greater than the encoder complexity. Under these testing conditions, the convolutionally coded data bits that are sent may be detected very reliably and allow negligible detection errors, but the decoding equipment is complex and expensive.
It is well known that most unpunctured convolutional codes can be instantaneously decoded with simple circuitry. (See for example, Linear Sequential Machines, Chapter 15, Switching and Finite Automata Theory, Zvi Kohavi, McGraw-Hill, 1970.) However, to control the data rate, the codes may be punctured. Puncturing removes selected coded data bits to increase the effective code rate of the code, and the prior art simple methods of decoding are no longer useful in codes with puncturing.
A second problem is that some systems send different amounts of data in successive frames. For example, some will send data at full rate, half rate, quarter rate, and eighth rate. This data rate is not to be confused with the code rate effected by the encoder and puncturing. The receiver does not know the amount of data sent in a particular data frame. It is expected to decode for all the possible data rates and, from decoder metrics for each decode attempt, determine the rate that was most likely sent. The decoded data from this decode is then presented as the transmitted data. This technique is referred to as blind-rate determination.
The present art is well established in this area. For full decoding in the presence of noise and interference, Viterbi maximum-likelihood algorithms are almost universally employed.
Recognizing the need for limited correction capability, abbreviated algorithms have been developed. The number of gates that implemented this was about 25,000 plus some memory to hold the trellis states.
For some applications this number of gates is still prohibitively expensive. A new and improved solution for the problem has long been needed in, for example, testing, and this need has become more urgent with time.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a Radically Abbreviated Decoding (RAD) method and apparatus that can operate in the presence of puncturing and can support blind-rate determination for a fast convolutional decoder. The examples given assume two arms for the code, but it will be obvious to those with ordinary skills in the art to extend the invention to include more aims. In addition, while the examples relate to rate 1/N codes, this method may be extended to rational encoders, rate M/N, with the use of linear algebra to solve for the M incoming bits.
Faced with the need for a lower cost, simpler way of decoding symbols, it has been determined that reversing the encoding method as disclosed, together with means for handling punctured codes, can be used where accurate data decisions are available.
This method and apparatus is limited in that it has no tolerance for decision errors in the decoded data, only to erasures (punctured bits). A single bit error would propagate causing errors to occur throughout the remainder of the frame due to the recursive nature of the decoder. For this reason it is not applicable where very reliable symbol decisions are not available, and is intended primarily for situations with reliable symbol decisions such as testing. It will be clear to those skilled in the art that such capability could be added, if needed; with some incremental change in complexity and cost. The preferred embodiment is for testing, where such capability is not needed, the effort to develop such capability was not required and not expended.
The present invention may be simply extended to additional arms, for example, rate {fraction (1/3 )}codes or to non-instantaneously decodable codes. Other objects, features and advantages of the present invention and equivalents to the invention will be apparent to those with ordinary skill in the art, and form a part of this invention. For example, many of the elements of this invention, such as shifting data, while described in terms of hardware, might be implemented in software.
REFERENCES:
patent: 5029331 (1991-07-01), Heichler et al.
patent: 5668820 (1997-09-01), Ramesh et al.
patent: 5878085 (1999-03-01), McCallister et al.
patent: 6166667 (2000-12-01), Park
Agilent Technologie,s Inc.
Wamsley Patrick
LandOfFree
Radically abbreviated decoding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Radically abbreviated decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Radically abbreviated decoding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2854835