The invention relates to wireless communications systems. In particular, the invention relates to initialization of a convolutional decoder that has missed a portion of a continuously encoded symbol stream.
A wireless communication system may comprise multiple remote units and multiple base stations. FIG. 1 exemplifies an embodiment of a terrestrial wireless communication system with three remote units 10A, 10B and 10C and two base stations 12. In FIG. 1, the three remote units are shown as a mobile telephone unit installed in a car 10A, a portable computer remote 10B, and a fixed location unit 10C such as might be found in a wireless local loop or meter reading system. Remote units may be any type of communication unit such as, for example, hand-held personal communication system units, portable data units such as a personal data assistant, or fixed location data units such as meter reading equipment. FIG. 1 shows a forward link 14 from the base station 12 to the remote units 10 and a reverse link 16 from the remote units 10 to the base stations 12.
Communication between remote units and base stations, over the wireless channel, can be accomplished using one of a variety of multiple access techniques which facilitate a large number of users in a limited frequency spectrum. These multiple access techniques include time division multiple access (TDMA), frequency division multiple access (FDMA), and code division multiple access (CDMA). An industry standard for CDMA is set forth in the TIA/EIA Interim Standard entitled xe2x80x9cMobile Stationxe2x80x94Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular Systemxe2x80x9d, TIA/EIA/IS-95, and its progeny (collectively referred to here as IS-95), the contents of which are incorporated by reference herein in their entirety. Additional information concerning a CDMA communication system is disclosed in U.S. Pat. No. 4,901,307, entitled SPREAD SPECTRUM MULTIPLE ACCESS COMMUNICATION SYSTEM USING SATELLITE OR TERRESTRIAL REPEATERS, (the ""307 patent) assigned to the assignee of the present invention and incorporated in its entirety herein by reference.
In the ""307 patent, a multiple access technique is disclosed where a large number of mobile telephone system users, each having a transceiver, communicate through base stations using CDMA spread spectrum communication signals. The CDMA modulation techniques disclosed in the ""307 patent offer many advantages over other modulation techniques used in wireless communication systems such as TDMA and FDMA. For example, CDMA permits the frequency spectrum to be reused multiple times, thereby permitting an increase in system user capacity. Additionally, use of CDMA techniques permits the special problems of the terrestrial channel to be overcome by mitigation of the adverse effects of multipath, e.g. fading, while also exploiting the advantages thereof.
In a wireless communication system, a signal may travel several distinct propagation paths as it propagates between base stations and remote units. The multipath signal generated by the characteristics of the wireless channel presents a challenge to the communication system. One characteristic of a multipath channel is the time spread introduced in a signal that is transmitted through the channel. For example, if an ideal impulse is transmitted over a multipath channel, the received signal appears as a stream of pulses. Another characteristic of the multipath channel is that each path through the channel may cause a different attenuation factor. For example, if an ideal impulse is transmitted over a multipath channel, each pulse of the received stream of pulses generally has a different signal strength than other received pulses. Yet another characteristic of the multipath channel is that each path through the channel may cause a different phase on the signal. For example, if an ideal impulse is transmitted over a multipath channel, each pulse of the received stream of pulses generally has a different phase than other received pulses.
In the wireless channel, the multipath is created by reflection of the signal from obstacles in the environment such as, for example, buildings, trees, cars, and people. Accordingly, the wireless channel is generally a time varying multipath channel due to the relative motion of the structures that create the multipath. For example, if an ideal impulse is transmitted over the time varying multipath channel, the received stream of pulses changes in time delay, attenuation, and phase as a function of the time that the ideal impulse is transmitted.
The multipath characteristics of a channel can affect the signal received by the remote unit and result in, among other things, fading of the signal. Fading is the result of the phasing characteristics of the multipath channel. A fade occurs when multipath vectors add destructively, yielding a received signal that is smaller in amplitude than either individual vector. For example if a sine wave is transmitted through a multipath channel having two paths where the first path has an attenuation factor of X dB, a time delay of xcex4 with a phase shift of "THgr" radians, and the second path has an attenuation factor of X dB, a time delay of xcex4 with a phase shift of "THgr"+xcfx80 radians, no signal is received at the output of the channel because the two signals, being equal amplitude and opposite phase, cancel each other. Thus, fading may have a severe negative effect on the performance of a wireless communication system.
Typically, modern communication systems use coding to improve immunity to interference and wireless channel noise. Additionally, coding may increase system capacity and improve security. Generally, an information signal is first converted into a form suitable for efficient transmission over the wireless channel. Conversion or modulation of the information signal involves varying a parameter of a carrier wave on the basis of the information signal in such a way that the spectrum of the resulting modulated carrier is confined within the channel bandwidth. At a remote unit, the original message signal is replicated from a version of the modulated carrier received following propagation over the wireless channel. Such replication is generally achieved by using an inverse of the modulation process employed by the base station.
The field of data communications is particularly concerned with optimizing data throughput of a transmission system with a limited signal to noise ratio (SNR). The use of error correcting circuitry, such as encoders and decoders, allows system tradeoffs to be made. For example, smaller SNRs or higher data rates may be used with a particular wireless channel which maintains the same bit error rate (BER).
One class of encoders is known as a convolutional encoder. As is well known in the art, a convolutional encoder converts a sequence of input data bits to a codeword based on a convolution of the input sequence with itself or with another signal. Convolutional encoding of data combined with a convolutional decoder is a well known technique for providing error correction coding and decoding of data. One type of convolutional decoder typically used is a Viterbi decoder.
Coding rate, constraint length, and generating polynomials are used to define a convolutional decoder. A coding rate (k/n) corresponds to the number of coding symbols produced (n) for a given number of input bits (k). A constraint length (K) is defined as the length of a shift register used in convolutional encoding of data. Convolutional codes add correlation to an input data sequence by using delay elements (i.e., shift registers) and modulo adders. Taps between the delay elements may terminate at modulo adders forming a desired generating polynomial.
FIG. 2 is a block diagram of a convolutional encoder 20. The encoder 20 shown contains a shift register 22 tapped at various positions 23A through 23N. The shift register taps terminate at one or more of the modulo-2 adders 24 and 25 forming generator functions g0 and g1. Different generating polynomials can be formed by the selection of which taps terminate at the modulo-2 adders.
Bits enter the encoder at its input 26 one at a time. The outputs of the generator functions are the encoded output symbols C0 and C1. Each of the two generator functions g0 and g1 produces an output symbol for each input bit, which corresponds to a code rate of xc2xd. For an encoder with three generator functions, the code rate is ⅓ and a code rate of {fraction (1/n )} requires n generator functions. 
A coding rate of xc2xd has become one of the most popular rates, although other code rates may be used. A constraint length of nine (K=9) is typical in convolutional coding schemes. The convolutional encoder can be thought of as a Finite Impulse Response filter with binary coefficients and length Kxe2x88x921. This filter produces a symbol stream with 2Kxe2x88x921 possible states.
A basic principle of the Viterbi algorithm is to take a convolutionally encoded data stream that has been transmitted over a noisy wireless channel and use a finite state machine to efficiently determine the most likely sequence that was transmitted. A K=9 Viterbi decoder can be thought of as a machine that hypothesizes which of each 256 (2(Kxe2x88x921)) possible states the encoder could have been in given the symbols received. The probability that the encoder transitioned from each of those states to the next set of 256 possible encoder states is determined. The probabilities are represented by quantities called metrics, which are proportional to the negative of the logarithm of the probability. The sum of the metrics is therefore equivalent to the reciprocal of the product of the probabilities. Thus, smaller metrics correspond to higher probability events.
There are two types of metrics: state metrics, sometimes called path metrics; and branch metrics. The state metric represents the probability that the received set of symbols leads to the state with which it is associated. The branch metric represents the conditional probability that the transition from one state to another occurred assuming that the starting state was actually the correct state and given the symbol that was actually received.
In a rate {fraction (1/N )} encoder, there are two possible states leading to any other state, each corresponding to the occurrence of a zero or a one in the right-most bit of the convolutional encoder shift register. The decoder decides which is the more likely state by an add-compare-select (ACS) operation. Add refers to adding each state metric at the preceding level to the two branch metrics of the branches for the allowable transitions. Compare refers to comparing the pair of such metric sums for paths entering a state (node) at the given level. Select refers to selecting the lesser of the two and discarding the other. Thus, only the winning branch, i.e., the branch with the highest probability (smallest metric), is preserved at each node, along with the node state metric. If the two quantities being compared are equal, either branch may be selected, for the probability of erroneous selection will be the same in either case. 
The Viterbi algorithm is a computationally efficient method of updating the conditional probabilities of the best state and the most probable bit sequence transmitted from the possible 2Kxe2x88x921 states. In order to compute this probability, all 2Kxe2x88x921 states for each bit must be computed. The resulting decision bits from each of these computations is stored as a single bit in a path memory.
A chain-back operation, an inverse of the encoding operation, is performed in which the C decision bits are used to select an output bit, where C is the chainback distance. After many branches the most probable path will be selected with a high degree of certainty. The path memory depth must be sufficiently long to be governed by the signal-to-noise ratio and not the length of the chain-back memory.
Though it is not necessary for analyzing either the code characteristics or the performance of the optimal decoder, it is useful in understanding both to exhibit the code on a trellis diagram. The term xe2x80x9ctrellisxe2x80x9d is a term which describes a tree in which a branch not only bifurcates into two or more branches but also in which two or more branches can merge into one. A trellis diagram is an infinite replication of the state diagram for an encoder. The nodes (states) at one level in the trellis are reached from the node states of the previous level by the transition through one branch, corresponding to one input bit, as determined by the state diagram. Any codeword of a convolutional code corresponds to the symbols along a path (consisting of successive branches) in the trellis diagram.
A simple embodiment of the encoder of FIG. 2 is illustrated in FIG. 3. FIG. 3 illustrates a convolutional encoder with a code rate of xc2xd and a constraint length of 3. As shown in FIG. 3, the convolutional encoder has three taps 31, 32 and 33. The taps terminate at two modulo 2 adders 35 and 36 forming generator functions g0=510 and g1=710. The output of the generator functions become the encoded output symbols C0 and C1, respectively.
FIG. 4 is a trellis diagram showing the possible paths of the convolutional encoder illustrated in FIG. 3. The encoder is assumed to begin in the zero state. Each possible state is represented in the trellis diagram by a node 42. In each state the next input bit into the encoder may be either a zero or a one and a corresponding set of symbols are generated in each generator function. In FIG. 4, input bits 44 at each state are represented on their associated path. The output code symbols C0, indicated as 46, and C1, indicated as 47, generated from the input of each bit are represented in the diagram on the associated path. As illustrated in this simple example, each set of code symbols received at the remote unit is influenced from previously input data bits at the encoder. Thus, in typical operation, a convolutional decoder receives a continuous uninterrupted stream of code symbols with each symbol influenced by the preceding input data.
In a typical CDMA communication system, remote units only sporadically establish bidirectional communication with a base station. For example, a cellular telephone remains idle for significant periods of time when no call is in process. To ensure that any message directed to a remote unit is received, the remote unit must continuously monitor the communication channel even while it is idle. For example, while idle, the remote unit monitors the forward link channel from the base station to detect incoming calls. During such idle periods, the cellular telephone continues to consume power to sustain the elements necessary to monitor for signals from the base stations. Many remote units are portable and are powered by an internal battery. For example, personal communication system (PCS) handsets are almost exclusively battery-powered. The consumption of battery resources by the remote unit in idle mode decreases the battery resources available to the remote unit when a call is placed or received. Therefore, it is desirable to minimize power consumption in a remote unit in the idle state and thereby increase battery life.
One means of reducing remote unit power consumption in a communication system is disclosed in U.S. Pat. No. 5,392,287, entitled APPARATUS AND METHOD FOR REDUCING POWER CONSUMPTION IN A MOBILE COMMUNICATION RECEIVER (the ""287 patent), assigned to the assignee of the present invention and hereby incorporated in its entirety herein by reference. In the ""287 patent, a technique for reducing power consumption in a remote unit operating in an idle mode (i.e. a remote unit which is not engaged in bidirectional communication with a base station) is disclosed. In idle, each remote unit periodically enters an xe2x80x9cactivexe2x80x9d state during which it prepares to and receives messages on a forward link communication channel. In the time period between successive active states, the remote unit enters an xe2x80x9cinactivexe2x80x9d state. During the remote unit""s inactive state, the base station does not send any messages to that remote unit, although it may send messages to other remote units in the system that are in the active state.
As disclosed in the ""287 patent, a base station broadcast messages which are received by all remote units within the base station coverage area on a xe2x80x9cpaging channel.xe2x80x9d All idle remote units within the base station coverage area monitor the paging channel. The paging channel is divided in the time dimension into a continuous stream of xe2x80x9cslots.xe2x80x9d Each remote unit operating in slotted mode monitors only specific slots which have been assigned to it as active (assigned) slots. The paging channel continually transmits convolutional encoded messages in numbered slots, repeating the slot sequence, such as for example, every 640 slots. When a remote unit enters the coverage area of a base station, or if a remote unit is initially powered on, it communicates its presence to a preferred base station. Typically the preferred base station is the base station which has the strongest pilot signal as measured by the remote unit.
The preferred base station, along with a plurality of geographically near neighboring base stations, assign a slot, or a plurality of slots, within their respective paging channels, for the remote unit to monitor. The base station uses the slots in the paging channel to transmit control information to a remote unit, if necessary. The remote unit may also monitor a timing signal from the preferred base station allowing the remote unit to align, in the time dimension, to the base station slot timing. By aligning in the time dimension to the preferred base station slot timing, the remote unit can determine when a paging channel slot sequence begins. Thus, knowing when the paging channel slot sequence begins, which slots are assigned for it to monitor, the total number of slots in the repetitive paging channel sequence of slots, and the period of each slot, the remote unit is able to determine when its assigned slots occur.
Generally, the remote unit is in the inactive state while the base station is transmitting on the paging channel in slots which are not within the remote unit""s assigned set. While in the inactive state, the remote unit does not monitor timing signals transmitted by the base station, maintaining slot timing using an internal clock source. Additionally, while in the inactive state the remote unit may remove power and/or clocks from selected circuitry, such as, for example, circuits which monitor the wireless channel and the decoder. Using its internal timing, the remote unit transits to its active state a short period of time before the next occurrence of an assigned slot.
When transiting to the active state, the remote unit applies power to circuitry that monitors the wireless channel. After the remote unit has reacquired the base station, the remote unit begins receiving a stream of coded symbols and clocks the coded symbols into the decoder. The decoder uses the coded symbols to continue building a trellis stored in the decoder. However, because the stream of coded symbols has been interrupted, the symbol codes being received by the remote unit have no relationship to the symbols that built the trellis stored within the decoder. Therefore the remote unit must receive sufficient code symbols prior to its assigned slot to ensure that proper decoding of the code word is accomplished. For example, the paging channel used in IS-95 is continuously encoded with a constraint length 9 convolutional code. A decoder used to decode the IS-95 paging channel may need to decode 116 data bits to properly initialize its state metrics and insure valid data is output from the decoder.
When the remote unit enters the active state, it may receive messages in its assigned slots in the paging channel and respond to commands from the base station. For example, the remote unit may be commanded to activate a xe2x80x9ctrafficxe2x80x9d channel to establish a bi-directional communication link for conducting subsequent voice communication in response to an incoming call. If there is no message from the base station, or no command requesting the remote unit to remain active, at the end of the assigned slot the remote unit returns to the inactive state. In addition, the remote unit returns to the inactive state immediately if commanded to do so by the base station.
Therefore, there is a need in the art for a method and apparatus to decrease the number of code symbols required to properly decode an interrupted stream of code words.
The invention addresses these and other needs by providing a system and method wherein the convergence of a convolutional decoder is improved. In one aspect of the invention, the remote unit comprising the convolution decoder receives an interrupted stream of code symbols. Prior to decoding the symbols, the state metrics of the trellis residing within the decoder are initialized.
In one aspect of the invention, when the remote unit receives the interrupted stream of code symbols, the pattern of code symbols transmitted just prior to the code symbols received are known. The state metrics of the trellis are then biased towards states which would have been valid only if the previous code symbols would have been received. The remaining invalid states of the trellis are initialized with a high state metric. Therefore, during the decoding process, the decoder is biased toward the valid states.
In another aspect of the invention, the metrics of all states in the trellis residing in the encoder are initialized to 0 or some other constant value. Therefore, there is not a bias towards any particular state within the trellis.