Pulse or digital communications – Receivers – Particular pulse demodulator or detector
Reexamination Certificate
1998-03-27
2001-08-07
Pham, Chi (Department: 2031)
Pulse or digital communications
Receivers
Particular pulse demodulator or detector
C375S262000, C714S786000, C714S795000
Reexamination Certificate
active
06272187
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of electronic communications. In particular, the present invention concerns optimally decoding data encoded with a cyclic code in communications systems where a convolutional code is applied after the cyclic code during the encoding process.
2. Description of the Related Art
In the field of electronic communications, channel coding is used to ensure the accuracy of data transmitted from one point to another. Channel coding refers to a class of signal transformations designed to improve communications performance by enabling the transmitted signals to better withstand the effects of various communications channel impairments, such as noise, fading, and jamming.
One set of channel coding techniques is referred to as linear block codes, which transform a block of k message bits into a longer block of n codeword bits. Binary cyclic codes are an important subclass of linear block codes. The codes are easily implemented with feedback shift registers in integrated circuits, and the underlying algebraic structure of cyclic codes lends itself to efficient decoding methods. Cyclic Redundancy Checks (CRC) are cyclic codes which are commonly used in communications systems, including cellular applications.
Another set of channel coding techniques is referred to as convolutional codes, which are described by three integers, n, k, and K. The integer K is a parameter known as the constraint length; it represents the number of k-tuple stages in the encoding shift register. An important characteristic of convolutional codes, which is not shared by linear block codes, is that the encoder has memory: The n-tuple emitted by the convolutional encoding procedure is not only a function of an input k-tuple, but also of the previous K−1 input k-tuples. Data which has been convolutionally encoded is often decoded using Viterbi decoders, which generally output decoded data in time reversed order.
Convolutional and linear block coding techniques are often combined, for example in wireless cellular communications systems, resulting in signficantly improved overall performance. Typical communications systems encode data first with a cyclic code for error detection, and then with a convolution code for error correction. A conventional receiver for such a system first uses a Viterbi decoder to decode the convolutional code and correct as many errors as possible. Then, a different decoder is used to decode the cyclic code and determine whether all of the errors were corrected or not.
In Code-Division Multiple Access (CDMA), Time-Division Multiple Access and most other cellular communications systems, data is divided into a number of “frames” including frame quality indicator bits (sometimes called “CRC bits”) generated using a CRC code. The conventional method of calculating CRC bits is using a circuit provided in TIA Standards Proposal #3384, “lersonal Station Base Station Compatibility Requirements for 1.8 to 2.0 GHz Code Division Multiple Access Personal Communications Systems,” and several related TIA Standards. The conventional method requires that the input bits be in normal time order (first bit in first), which is disadvantageous for the following reasons.
In most applications, the CRC bits in a receiver are calculated after a Viterbi decoder. Optimal Viterbi decoding requires a full “traceback” to calculate the input bits, which results in the input bits to the CRC generator being available in time reversed order. If the conventional method of calculating the CRC bits is used, the input bits need to be buffered up and fed into the CRC generator after all of the input bits are generated. It would be preferable to calculate CRC bits from a frame of data that is available in time reversed order (i.e., last bit available first) since this would allow the quality of a frame to be checked simultaneously with the Viterbi decoding, without buffering any bits. This reduces the hardware and other device complexity in implementation.
Therefore, an object of this invention is to provide a circuit which can decode in time reversed order, without buffering any bits, data encoded with a cyclic code in systems where a convolution code is applied after the cyclic code during the encoding process.
SUMMARY OF THE INVENTION
This object is achieved by the present invention, which comprises a device which efficiently decodes data encoded with a cyclic code in communications systems where a convolutional code is applied after the cyclic code during encoding, wherein the device accepts data provided in time reversed order by a Viterbi decoder which decodes the convolutional code. In a preferred version, the device employs linear feedback shift registers having a plurality of feedback paths. A set of multipliers corresponding to a set of coefficients is interposed in the feedback paths such that when data is shifted through the feedback shift registers, the device performs division by x for an input bit equal to 0, and, for an input bit equal to 1, performs division by x and then adds x
k+m−1
. The set of multipliers includes a set of weighting multipliers corresponding to coefficients of a weighting polynomial such that addition of x
k+m−1
is performed for an input bit equal to 1. In another preferred version, the device compares a known initial state to a final state generated by shifting time reversed data through the linear feedback shift registers such that the final state equals the known initial state if there are no errors.
As a result of this novel configuration, the quality of a data frame can be checked simultaneously with Viterbi decoding, without buffering any bits. This reduces the hardware and other device complexity in implementation. These and other aspects, features, and advantages of the present invention will be apparent to those persons having ordinary skill in the art to which the present invention relates from the foregoing description and the accompanying drawings.
REFERENCES:
patent: 5103451 (1992-04-01), Fossey
patent: 5511068 (1996-04-01), Sato
patent: 5920593 (1999-07-01), Perl et al.
patent: 6041433 (2000-03-01), Kamada
Lin et al. Error Correction coding Fundamental and Applications, Chapter 4, 1983.*
Paul H. Young, Electronic Communication Techniques, 2nd Edition pp. 550-557, 1993.
Corrielus Jean B.
LSI Logic Corporation
Pham Chi
LandOfFree
Device and method for efficient decoding with time reversed... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device and method for efficient decoding with time reversed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device and method for efficient decoding with time reversed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2522948