Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-02-18
2002-01-29
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06343368
ABSTRACT:
BACKGROUND
The present invention generally relates to error handling in the field of communication systems and, more particularly, to decoding signals, which have been transmitted using error correction codes, using a maximum a posteriori (MAP) decoding technique.
The growth of commercial communication systems and, in particular, the explosive growth of cellular radiotelephone systems, have compelled system designers to search for ways to increase system capacity without reducing communication quality beyond consumer tolerance thresholds. One technique to achieve these objectives involved changing from systems, wherein analog modulation was used to impress data onto a carrier wave, to systems wherein digital modulation was used to impress the data on carrier waves.
In wireless digital communication systems, standardized air interfaces specify most of the system parameters, including modulation type, burst format, communication protocol, etc. For example, the European Telecommunication Standard Institute (ETSI) has specified a Global System for Mobile Communications (GSM) standard that uses time division multiple access (TDMA) to communicate control, voice and data information over radio frequency (RF) physical channels or links using a Gaussian Minimum Shift Keying (GMSK) modulation scheme at a symbol rate of 271 ksps. In the U.S., the Telecommunication Industry Association (TIA) has published a number of Interim Standards, such as IS-54 and IS-136, that define various versions of digital advanced mobile phone service (D-AMPS), a TDMA system that uses a differential quadrature phase shift keying (DQPSK) modulation scheme for communicating data over RF links.
TDMA systems subdivide the available frequency band into one or more RF channels, which are further divided into a number of physical channels corresponding to timeslots in TDMA frames. Logical channels are formed of one or several physical channels where modulation and coding is specified. In these systems, the mobile stations communicate with a plurality of scattered base stations by transmitting and receiving bursts of digital information over uplink and downlink RF channels.
The growing number of mobile stations in use today has generated the need for more voice and data channels within cellular telecommunication systems. As a result, base stations have become more closely spaced, with an increase in interference between mobile stations operating on the same frequency in neighboring or closely spaced cells. Although digital techniques provide a greater number of useful channels from a given frequency spectrum, there still remains a need to reduce interference, or more specifically to increase the ratio of the carrier signal strength to interference, (i.e., carrier-to-interference (C/I) ratio).
In order to provide various communication services, a corresponding minimum user bit rate is required. For example, for voice and/or data services, user bit rate corresponds to voice quality and/or data throughput, with a higher user bit rate producing better voice quality and/or higher data throughput. The total user bit rate is determined by a selected combination of techniques for speech coding, error correction (channel coding), modulation scheme and the number of assignable resources (e.g., codes, time slots, frequencies, etc.) per connection.
Of particular interest in this specification are error correction or channel codes. Digital communication systems employ various techniques to handle erroneously received information. Generally speaking, these techniques include those which aid a receiver to correct the erroneously received information, e.g., forward error correction (FEC) techniques, and those which enable the erroneously received information to be retransmitted to the receiver, e.g., automatic retransmission request (ARQ) techniques. FEC techniques include, for example, convolutional or block coding of the data prior to modulation, which coding is intended to permit the correction of errors introduced by noise and interference. FEC coding involves representing a certain number of data bits using a larger number of code bits. Thus, it is common to refer to convolutional codes by their code rates, e.g., 1/2 and 1/3, wherein the lower code rates provide greater error protection but lower user bit rates for a given channel bit rate.
At the receiver side, the received sequence is decoded to allow further processing of the data. Of course, the channel over which the signal has been transmitted makes this decoding process more challenging. This challenge is graphically depicted in FIG.
1
. Therein, a stream of symbols u is input to a convolutional encoder
10
. The encoded symbol stream x is transmitted over a transmission channel
12
, e.g., over an air interface or a wireline, and received by a receiving entity as symbol stream y to reflect the impact of the channel on the transmitted signal. The MAP decoder
14
interprets the received symbol stream y to output symbol stream û, which is an estimate of the original symbol stream u. Note that in order to simplify this discussion, descriptions of various other processes which are well known in the art, e.g., the modulation and demodulation processes performed at the transmitter and receiver side, respectively, have been omitted.
The MAP decoding algorithm which can be employed in decoder
14
, also known as the symbol-by-symbol Maximum-A-Posteriori algorithm or BCJR algorithm, was proposed by Bahl, Cocke, Jelinek and Raviv in “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate”, IEEE Trans. Inform. Theory, Vol. IT-20, pp.284-287, March 1974, the disclosure of which is incorporated here by reference. Variations on the MAP algorithm have also been proposed, which variations are more commercially feasible from an implementation point of view. For example, the Log-Map (processing performed in the logarithmic domain) and Max-Log-Map (a simplified version of Log-Map) algorithms have been described in the literature, e.g., “Iterative Decoding of Binary Block and Convolutional Codes”, to Hagenauer et al., IEEE Trans. Inform. Theory, Vol. IT-42, pp. 429-445, March 1996, the disclosure of which is incorporated here by reference.
Due to their computational complexity and relatively moderate performance increases relative to less complex decoders (e.g., Viterbi decoders) under most conditions, MAP decoders have enjoyed relatively little popularity since their inception in the 1970's. However, as the development of error correction coding has advanced, interest in MAP decoders has been rekindled as Shannon's limit is approached. Those skilled in the art will appreciate that Shannon's limit establishes the smallest ratio of energy per bit to single sided noise density (E
b
/N
0
) for reliable transmission. Although Shannon proved this limit in the late 1940's, error correction codes have still not been developed which provide this theoretically possible performance. However, a recent class of so-called “turbo” codes comes much closer to operating at Shannon's limit. With the advent of these, and other, new types of error correction codes, the MAP decoder has returned to prominence.
The detailed operation of the MAP algorithm is described below, and the metrics involved in the MAP algorithm will be more readily understood upon review of the equations found therein. One possible implementation of a MAP decoder is to simply provide a decoder which implements the MAP algorithm in a straightforward manner. That is, for a received sequence having N symbols, in a first step calculating and storing all of the branch transition metrics and the forward state metrics. After the Nth branch transition metric and Nth forward state metric have been calculated, then calculating all N reverse state metrics. Finally, after the reverse state metrics have been calculated, the likelihood ratios are calculated. However, the processing delay involved in such a straightforward implementation of the MAP decoding process is relatively high even when using powerful process
Chase Shelby A
Chung Phung M.
Telefonaktiebolaget LM Ericsson (publ)
LandOfFree
Method and system for fast maximum a posteriori 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 Method and system for fast maximum a posteriori decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for fast maximum a posteriori decoding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2836164