HK1053550A - Slotted mode decoder state metric initialization - Google Patents

Description

Metric initialization of slotted mode decoder states

Technical Field

The present invention relates to wireless communication systems. More particularly, the present invention relates to the initialization of convolutional decoders that have lost a portion of a stream of consecutive coded symbols.

Background

A wireless communication system may include a plurality of remote units and a plurality of base stations. Fig. 1 illustrates an embodiment of a terrestrial wireless communications system having 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, a portable computer remote unit 10B and a fixed location unit 10C (such as may be found in a wireless local loop or meter reading system) installed in a car 10A. The remote units may be any type of communication unit such as a handheld personal communication system unit, a portable data unit such as a personal data assistant, or a fixed location data unit such as a meter reading device. Fig. 1 shows a forward link 14 from a base station 12 to a remote unit 10 and a reverse link 16 from the remote unit 10 to the base station 12.

Communication between the remote unit and the base station over the wireless channel may be accomplished using one of a variety of multiple access techniques that 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). The industry Standard for CDMA IS set forth in the TIA/EIA provisional Standard entitled "Mobile Station-Base Station Compatibility Standard for Dual-ModeWideband Spread Spectrum Cellular System", TIA/EIA/IS-95 and its successors (collectively referred to herein as IS-95), the contents of which are incorporated herein by reference in their entirety. Additional information regarding CDMA COMMUNICATION SYSTEMs is disclosed in U.S. patent No. 4901307 entitled SPREAD spectrum COMMUNICATION SYSTEM USING SATELLITE transmitter OR TERRESTRIAL REPEATERS (the' 307 patent), which is assigned to the assignee of the present invention and is hereby incorporated by reference in its entirety.

In the' 307 patent, multiple access techniques are disclosed, with a large number of mobile telephone system users, each having a transceiver, communicating through a base station using CDMA spread spectrum signals. The CDMA modulation techniques disclosed in the' 307 patent provide many advantages over other modulation techniques used in wireless communication systems, such as TDMA and FDMA. For example, CDMA allows the frequency spectrum to be reused multiple times, thereby increasing system user capacity. Moreover, the use of CDMA techniques allows the special problems of the terrestrial channel to be overcome by mitigation of the negative effects of multipath (such as fading), while still further exploiting its advantages.

In a wireless communication system, a signal may travel several different propagation paths as it travels between a base station and a remote unit. Multipath signals resulting from the characteristics of the wireless channel present challenges to the communication system. One characteristic of a multipath channel is the introduction of time spreading in the signal transmitted through the channel. For example, if an ideal pulse is transmitted through a multipath channel, the received signal appears as a stream of pulses. Another characteristic of a multipath channel is that each path through the channel may result in a different attenuation factor. For example, if an ideal pulse is transmitted over a multipath channel, each pulse of the received pulse stream typically has a different signal energy than the other received pulses. Yet another characteristic of a multipath channel is that each path through the channel may result in a different phase on the signal. For example, if an ideal pulse is transmitted over a multipath channel, each pulse of the received pulse stream will generally have a different phase with respect to the other received pulses.

In a wireless channel, multipath paths are created by reflections of signals from obstacles in the environment, such as buildings, trees, cars, and people. Thus, the wireless channel is typically a time-varying multipath channel due to the relative motion of the structures that create the multipath. For example, if an ideal pulse is transmitted over a time-varying multipath channel, the received pulse stream varies in time delay, attenuation, and phase as a function of the time at which the ideal pulse is transmitted.

The multipath characteristics of the channel may affect the signal received by the remote unit and cause fading of the signal, among other things. Fading is a result of the phase characteristics of the multipath channel. Fading occurs when the multipath vectors add destructively, producing a received signal that is smaller in magnitude than either vector alone. For example, if a sinusoidal waveform is transmitted over a multipath channel having two paths, a first path having an attenuation factor of XdB, a time delay of δ, and a phase shift of Θ radians, and a second path having an attenuation factor of XdB, a time delay of δ, and a phase shift of Θ + π radians, no signal is received at the output of the channel because the two signals of the same magnitude and opposite phase cancel each other out. Thus, fading has a severe negative impact on the performance of the wireless communication system.

Typically, modern communication systems use coding to improve the immunity to interference and radio channel noise. In addition, encoding may increase system capacity and improve security. The information signal is typically first converted into a form suitable for efficient transmission over the wireless channel. The conversion or modulation of the information signal involves varying the carrier waveform parameters based on the information signal such that the spectrum of the resulting modulated carrier is confined within the channel bandwidth. At the remote unit, the initial message signal is replicated from the form of the modulated carrier wave received following propagation over the wireless channel. Such copying is typically accomplished by using the reverse operation of the modulation process used by the base station.

The field of data communication relates in particular to optimizing the data throughput of transmission systems with limited signal-to-noise ratio (SNR). The use of error correction circuits (such as encoders and decoders) allows the system to make tradeoffs. For example, a particular wireless channel may maintain the same Bit Error Rate (BER) with a smaller SNR or a higher data rate.

One type of encoder is known as a convolutional encoder. As is well known in the art, a convolutional encoder converts a sequence of input data bits into a codeword based on the convolution of the input sequence with itself or with another signal. Convolutional encoding of data in conjunction with convolutional decoders are well known techniques for providing error correction encoding and decoding of data. One type of decoder that is commonly used is the Viterbi decoder.

The code rate, constraint length and generator polynomial are used to define a convolutional decoder. The code rate (k/n) corresponds to the code symbol (n) generated for a given number of input bits (k). The constraint length (K) is defined as the length of the shift register used in the data convolutional encoding. 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 the modulo adder to form the desired generator polynomial.

Fig. 2 is a block diagram of convolutional encoder 20. The encoder 20 is shown to contain a shift register 22 tapped at different positions 23A to 23N. The tap of the shift register is connected to one or more forming generator functions g₀And g₁Modulo-2 adders 24 and 25. By selecting which tap endsConnected to modulo-2 adders to form different generator polynomials.

The bit enters the encoder at its input 26 one bit at a time. The output of the generator function is the encoded output symbol C₀And C₁. These two generator functions g₀And g₁Produces an output symbol for each input bit, which corresponds to a code rate of 1/2. For an encoder with three generator functions, the code rate is 1/3, while a code rate of 1/n requires n generator functions.

1/2, although other code rates may be used. A constraint length of 9 (K-9) is most commonly used in convolutional coding methods. The convolutional encoder can be viewed as a finite impulse response filter with binary coefficients and a length of K-1. This filter is generated to have a value of 2^K-1A symbol stream of possible states.

The basic principle of the Viterbi algorithm is to employ a convolutionally encoded data stream transmitted over a noisy wireless channel and use a finite state machine to efficiently determine the most likely sequence transmitted. A Viterbi decoder with K-9 may be seen as a decoder that may be at every 256 (2) for a given accepted symbol hypothesis^(K-1)) Which of the possible states. The probability of the encoder transitioning from each of those states to the next set of 256 possible encoder states is determined. The probability is represented by a quantity called a measure, which is proportional to the negative logarithm of the probability. The sum of this measure is therefore equal to the inverse of the probability product. Thus, a smaller metric corresponds to a higher probability of an event.

There are two measures: state metrics (sometimes referred to as path metrics) and branch metrics. The state metric represents the probability that the accepted symbol set leads to its associated state. The branch metric represents the probability that a transition from one state to another occurs given the actually accepted symbol assuming that the starting state is actually the correct state.

In a rate 1/N encoder, there are two possible states leading to any other state, each corresponding to the occurrence of a 0 or 1 in the rightmost bit in the convolutional encoder shift register. The decoder determines which is the most likely state by an Add Compare Select (ACS) operation. The addition involves adding the state quantity of each previous stage to the two branch quantities of the branch that allowed the branch to branch. The comparison involves comparing the pair of metric sums for the paths into a state (node) at a particular stage. Selection involves selecting the smaller of the two and discarding the other. In this way, only the better branches (i.e., the branches with the highest probability) are maintained at each node, along with the node state quantities. If the two quantities compared are equal, either branch can be selected, in either case the probability of a wrong selection is the same.

The Viterbi algorithm is to update the best state and from 2 possible^K-1An efficient method for the conditional probability calculation of the maximum possible bit sequence for a state transmission. To calculate this probability, all 2's must be calculated^K-1Each bit of a state. The final determined bit from each of these calculations is stored as a single bit of the path memory.

A reverse link operation (reverse of the encoding operation) is performed in which the output bits are selected using C determination bits, where C is the reverse link distance. After many branches, it is very confident that the most likely path is selected. This path memory depth must be long enough to be dominated by the signal-to-noise ratio, rather than the length of the reverse link memory.

While it is not necessary to analyze the coding characteristics or the performance of the optimal decoder, it is useful to understand both to show the coding on the trellis diagram. The phrase "lattice" is a phrase describing a tree in which branches are not only split into two or more branches but in which two or more branches merge into one. The trellis diagram is an infinite copy of the encoder state diagram. The transition of a branch corresponding to an input bit reaches a node (state) of a stage in the trellis from a node state of a previous stage, as determined by the state diagram. Any codeword of a convolutional code corresponds to a symbol along a path (including consecutive branches) in the trellis.

The encoding of FIG. 2 is illustrated in FIG. 3A simple embodiment of the device. Fig. 3 illustrates a convolutional encoder with code rate 1/2 and constraint length 3. As shown in fig. 3, the convolutional encoder has three taps 31, 32, and 33. Tap termination to form generator function g₀＝5₁₀And g₁＝7₁₀Two modulo-2 adders 35 and 36. The outputs of the generator functions become respectively coded output symbols C₀And C₁。

Fig. 4 is a trellis diagram showing possible paths of the convolutional encoder illustrated in fig. 3. Assume that the encoder starts in the zero state. Each possible state is displayed in the grid graph by the node 42. In each state, the next input bit into the encoder may be either a 0 or a 1 and a corresponding symbol group is produced in each generator function. In fig. 4, the input bit 44 at each state is represented on its associated path. The output code symbols C0 (denoted 46) and C1 (denoted 47) resulting from each bit input are represented in the graph on the correlation path. As illustrated in this simple example, each set of code symbols accepted at the remote unit is affected by the previous input data bits at the encoder. Thus, in conventional operation, a convolutional decoder accepts a continuous uninterrupted stream of code symbols, each of which is affected by previous input data.

In a conventional CDMA communication system, remote units only occasionally establish two-way communication with a base station. For example, a cellular phone remains idle for a long period of time when there is no ongoing call. To ensure that any messages directed to the remote unit are accepted, the remote unit must continuously monitor the communication channel even while idle. For example, while idle, the remote unit monitors the forward link channel from the base station to detect an incoming call. During such idle periods, the cell phone continuously expends power to maintain the components necessary to monitor the signals from the base station. Many remote units are portable and powered by internal batteries. For example, Personal Communication Systems (PCS) handsets are almost exclusively battery powered. The drain on battery power by the remote unit when in idle mode reduces the battery power available to the remote unit when placing or accepting a call. It is therefore desirable to reduce the energy consumption of the remote unit in the idle state and thereby increase battery life.

A METHOD FOR REDUCING energy consumption by remote units IN a COMMUNICATION system is disclosed IN U.S. Pat. No. 5392287 entitled "APPARATUS AND METHOD FOR REDUCING POWER SUPPORTION IN A MOBILE COMMUNICATION RECEIVER" ("287 patent"). Which is assigned to the assignee of the present invention and is incorporated herein by reference in its entirety. In the' 287 patent, techniques are disclosed for reducing energy consumption in a remote unit operating in an idle mode (i.e., a remote unit that is not in two-way communication with a base station). In the idle state, each remote unit periodically enters an "active" state during which it prepares and receives messages on the forward link communication channel. During the time period between successive active states, the remote unit enters an "inactive" state. During the inactive state of the remote unit, the base station does not send any messages to the remote unit, although it may send messages to other remote units in the system that are active.

As disclosed in the 287 patent. The base station broadcasts a message that is received on a "paging channel" by all remote units within the coverage area of the base station. All idle remote units within the coverage area of the base station monitor the paging channel. The paging channel is divided into successive "slot" streams in the time dimension. Each remote unit operating in slotted mode monitors only certain slots that are allocated as active (allocated) slots for that unit. The paging channel continuously transmits convolutionally encoded messages in finite time slots, for example repeating a sequence of time slots every 640 time slots. When the remote unit enters the coverage area of a base station, or if the remote unit is initially powered up, it informs a preferred base station of its presence communication. It is generally preferred that the base station be the base station with the strongest pilot signal as measured by the remote unit.

The preferred base station, along with a plurality of geographically adjacent neighboring base stations, assigns a time slot or multiple time slots to monitor for remote units within their respective paging channels. The base station uses the time slots in the paging channel to transmit control information to the remote unit, if necessary. The remote unit can also monitor the timing signal from the preferred base station, which causes the remote unit to align the base station slot timing in the time dimension. By aligning the base station slot timing in the time dimension, the remote unit can determine when the paging channel slot sequence begins. Thus, knowing when the paging channel slot sequence starts, which slots are allocated to it for monitoring, the total number of slots in the repeating paging channel slot sequence, and the duration of each slot, the remote unit can determine when its allocated slots occur.

Typically, a remote unit is in an inactive state when the base station transmits on the paging channel in a time slot that is not within the remote unit's assigned group. While in the inactive state, the remote unit does not monitor the timing signals transmitted by the base station, and maintains slot timing using an internal clock source. In addition, when in the inactive state, the remote unit may remove power and clocks from selected circuitry (e.g., circuitry monitoring the wireless channel and decoder). Using internal timing, the remote unit passes through its active state a short time before the next occurrence of the assigned time slot.

When transitioning to the active state, the remote unit applies power to circuitry that monitors the wireless channel. After the remote unit reacquires the base station, the remote unit begins accepting the coded symbol stream and clocking the coded symbol stream into the decoder. The decoder continues to construct the trellis stored in the decoder using the encoded symbols. However, since the encoded symbol stream has been interrupted, there is no correlation between the symbol code received by the remote unit and the symbols that make up the trellis stored within the decoder. The remote unit must therefore accept enough code symbols before its assigned slot to ensure that proper decoding of the code word is complete. For example, the paging channel used in IS-95 IS continuously encoded with a convolutional code of constraint length 9. A decoder used to decode the IS-95 paging channel may need to decode 116 data bits to properly initialize its state quantity and ensure valid data IS output from the decoder.

When the remote unit enters the active state, it may receive messages on the paging channel on its assigned time slot and respond to instructions from the base station. For example, the remote unit may be instructed to open a "traffic" channel to establish a two-way communication link for subsequent voice communications in response to an incoming call. If there is no message from the base station or no instruction requesting that the remote unit remain active, the remote unit returns to the inactive state at the end of the assigned time slot. In addition, the remote unit immediately returns to the inactive state if commanded to do so by the base station.

Accordingly, there is a need in the art for a method and apparatus that reduces the number of code symbols required to properly decode an interrupted stream of code words.

Summary of The Invention

The present invention addresses these and other needs by providing a system and method that improves the convergence characteristics of convolutional decoders. In one aspect of the invention, a remote unit comprising a convolutional decoder receives an interrupted stream of code symbols. Prior to decoding the symbols, state metrics of a trellis diagram present 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 accepted code symbols is known. The state quantities of the trellis diagram are then biased towards the valid state only if the previous code symbol has been accepted. The remaining invalid state is initialized with a high state metric. Therefore, during decoding, the decoder is biased toward the active state.

In another aspect of the invention, the metrics for all states in the trellis present in the encoder are initialized to 0 or some other constant. Thus, there is no bias towards any particular state within the grid map.

Brief Description of Drawings

The features, nature, and advantages of the present invention will become more apparent from the detailed description set forth below when taken in conjunction with the drawings in which like reference characters identify correspondingly throughout and wherein:

fig. 1 is a representation showing a typical modern wireless communication system.

Fig. 2 is a block diagram of a convolutional decoder.

Fig. 3 is a block diagram of a convolutional encoder with code rate of 1/2 and constraint length of 3.

Fig. 4 is a grid diagram showing possible paths of the convolutional encoder illustrated in fig. 3.

Fig. 5 is a representation illustrating a transition from an inactive state to an active state at an assigned time slot of a remote unit in a slotted mode communication system.

Fig. 6 is a block diagram of a remote unit embodiment.

Fig. 7 is a representation illustrating a convolutional encoded sequence such as that produced by the encoder in fig. 3.

Fig. 8 is a trellis diagram illustrating the accepted sequence coding illustrated in fig. 7.

FIG. 9 is a grid diagram illustrating one embodiment of the present invention.

FIG. 10 is a flow chart illustrating the method of operation of one embodiment of the present invention.

Detailed Description

Fig. 5 is a representation illustrating a transition from an inactive state to an active state at an assigned time slot of a remote unit in a slotted mode communication system. The upper part 51 represents a sequence of consecutive time slots passing from left to right in time. The lower portion 52 represents events that occur during transitions between remote unit active and inactive states in a slotted mode communication system, where slot 5 is the assigned slot. The lower time scale has been extended to enable a more detailed display of the state transitions.

In particular, the lower portion 53 of FIG. 5 shows the transition from the inactive state 50 to the active state 52. In the active state 52, the remote unit monitors the base station for a portion of time slot 5. Before the beginning of time slot 5, the remote unit transitions from the inactive state 50 to the active state 52 through a transition state 54. As described above, in the inactive state 50, selected circuitry in the remote unit is unpowered, which reduces energy consumption and increases the battery life of the remote unit. For example, power may be removed from the receiver during the inactive state 50.

In the transitional state 54, the selected circuitry of the remote unit is powered up again. For example, if the receiver is not powered up, power is reapplied in the transition state. The duration of the transition state 54 is sufficient to allow the remote unit to power up the circuitry and initiate functions to make the remote unit functional so that it can receive and decode the code word at the end of the transition state 54.

Following the transition state 54, the remote unit enters the active state 52. The active state 52 consists of two parts: a preparation time 56 and an assigned slot time 58. In preparation time 56, an initial search is made to reacquire the pilot signal of the preferred base station to prepare the remote unit to monitor the paging channel at the assigned slot time 58. The allocated slot time 58 begins at the beginning of slot 5.

During the assigned slot time 58, the remote unit receives a message from the preferred base station on the paging channel. Nominally, the allocated slot time 58 and active state 52 at the end of slot 5 terminates and the remote unit enters the inactive state 50. To further reduce the remote unit's power consumption, the base station may command the remote unit to enter the inactive state 50 before slot 5 is completed. Alternatively, if the base station is unable to transmit a message in slot 5, the base station may command the remote unit to remain in the assigned slot time 58 after slot 5 is completed. The base station then commands the remote unit to enter the inactive state 50. The remote unit stops receiving the transmitted data as soon as it enters the inactive state 50, thus interrupting the continuous stream of convolutionally encoded symbols.

Fig. 6 is a block diagram showing a portion of remote unit 60. The receiver 61 receives the wireless link signal. Receiver 61 provides for reception and downconversion of the radio link signal and also provides despreading and other demodulation functions in a CDMA environment. The receiver 61 provides a series of digital values at its output.

According to well-known wireless link protocols, such as IS-95, data IS divided into a series of packets before being transmitted over the wireless link. The packets are rearranged in time so that the order of the packets is non-sequential when transmitted over the wireless link. This method of transmitting packets is referred to as interleaving, and the process of rearranging packets is referred to as deinterleaving. The deinterleaver 62 performs a deinterleaving operation. A deinterleaver 62 receives samples from the receiver 61 and accumulates a series of packet data. When receiving the entire group of packets, the deinterleaver 62 rearranges the packets in time sequence and outputs them to the decoder 63.

In one embodiment, decoder 63 is a convolutional decoder. One common form of convolutional decoder is the Viterbi decoder. As discussed above, the Viterbi decoder generates soft decision data from the data set. When the decoder buffer contains sufficient data, the data is passed to the message parser 64. The message analyzer 64 performs the operations of: collecting bits in the message, calculating and identifying any cyclic redundancy or other error correction codes, converting the message to an internal format, copying the converted message into a buffer, and placing the converted message into a queue for the appropriate protocol task. In summary, the processes of the decoder 63 and the message analyzer 64 are controlled by the controller 65. The controller may be configured to bias the encoder toward a particular state or not toward any state upon entering the active state.

In one embodiment, the decoder may be implemented on an ASIC. In one embodiment, the decoder may be a Field Programmable Gate Array (FPGA), discrete logic, microprocessor, or other control circuitry. In another embodiment, both decoder 63 and controller 65 may be formed on the same ASIC. In other embodiments. The configuration of the hardware in remote unit 60 may be controlled by firmware, allowing the remote unit to be updated in the field by downloading new firmware.

In general, the operation of remote unit 60 is controlled by the configuration of hardware and software implemented on controller 65. The hardware configuration may be established by firmware, software, hardwiring of discrete devices, or any combination thereof.

As described above, convolutional encoding of the input data at the base station results in the accepted code symbols being affected by the previous bits in the data stream. The result of convolutional encoding when the accepted code symbol stream is interrupted is discussed below.

Fig. 7 illustrates a simple example of a convolutional code sequence, such as that produced by the encoder of fig. 3. Fig. 7 illustrates input data 71. In this example, assume that the convolutional encoder begins in its "00" state before accepting input data 71. When input data 71 enters the encoder, the transmitted sequence 72 is generated by the encoder. Since the code rate of the convolutional encoder of fig. 3 is 1/2, each bit in the information sequence entering the encoder produces two symbol codes C₀And C₁Labeled 73 and 74, respectively. The sequence of code symbols is transmitted over a wireless channel where it may be corrupted by noise and fading.

In the remote unit 60, the transmitted sequence 72 is received by the receiver 61. The received sequence of code symbols may be represented by the received sequence 75 of fig. 7 due to the effects of the wireless channel on the transmitted sequence, such as noise and fading. In this example, the received signal is completely corrupted. Three of the received symbols 76, 77 and 78 have different polarities than the corresponding transmitted symbols. In addition, there is a deletion 79 when no data is received.

The received sequence 75 is sampled at the remote unit receiver 61. For example, receiver 61 integrates the energy received during the code symbols. In one embodiment, the magnitude of the energy received during the code symbol may be converted to a voltage level in the range of +7 to-7 volts. In this example, a strong "1" and a weak "1" are represented as different values. The positive sign corresponds to a binary "1" and the negative sign corresponds to a binary "0". The magnitude of the voltage level is a measure of the confidence that the received symbol is the same as the transmitted symbol. For example, a strong binary "0" represents a sign and a large magnitude, and a weak binary "1" represents a positive sign and a small magnitude. As an example, a first binary "1" in the input data 71 enters the encoder at the base station to produce the transmitted symbol code sequence 73, 74. The code symbols are transmitted over a wireless channel. Code symbols are received at the remote unit at confidence levels +3, -2 (illustrated by reference numerals 80 and 76, respectively). These confidence levels of the received symbols are used by the decoder in the remote unit to make soft decisions (i.e., predict the most likely path through the trellis).

Fig. 8 is a trellis diagram illustrating the coding of received sequence 75 illustrated in fig. 7. While the trellis has been simplified for ease of illustration, it will be appreciated that the principles described herein are not limited to such a simple example and may also be applied to more complex decoders and trellis. When the remote unit initially powers up, the state magnitudes in the Viterbi decoder are initialized to arbitrary random values. For example, the initial state quantity values of states 00, 10, 01, and 11 are 0, 123, 4, and 511, respectively, in fig. 8. After the code symbol packets are received and passed to the decoder, the metric or confidence level for each possible state is calculated by the trellis.

For example, if the encoder remains in state 00 at level 1 after the encoder begins at state 00 at level 0 and the data bits enter the encoder on a clock tick, then the data bits must be a binary "0" that produces a code symbol binary 00. In the example illustrated in fig. 8, the received symbol codes are +3 (representing a binary "1") and-2 (representing a binary "0"). The path metric is calculated by adding the magnitude of the confidence level opposite in polarity to the desired code symbol. Thus, the path metric for the transition from the initial 00 state to the 00 state of stage 1 in fig. 8 is equal to 3. Referring again to fig. 4, a second path to the level 100 state occurs if the encoder is initially in state 01 and a binary 0 data bit has entered the encoder on a clock tick. The encoder generates code symbols binary 11. If a code symbol binary 11 is transmitted, the metric for this branch will be 2. The metric for the 00 state at level 1 is calculated by adding the branch metric to the state metrics from the previous states, respectively. For the example illustrated in fig. 8, the state metric for level 1 state 00 is either (0+3) or (4+ 2). Lower metric values correspond to a higher probability of correct paths, and only the path that yields the lowest metric remains. Thus, in FIG. 8, only the path from level 0 state 00 to level 1 state 00 is retained, which corresponds to a state metric of 3. This process continues until a trellis diagram is established that represents the entire data packet present in the decoder.

Once the trellis is complete, the decoder proceeds to the "reverse link," which tracks the path with the lowest state metric value. The decoder adapts the code symbols along the "reverse link" to determine the most likely transmitted sequence. In fig. 8, the decoded sequence ending with state metric 8 has the highest probability of being the transmitted sequence. The reverse link through the trellis produces decoded output symbols 88 corresponding to decoded bits 89. The decoded bits 89 are an accurate representation of the transmitted bits as shown at 71 in fig. 7.

For example, if the remote unit is commanded to enter its inactive state after reaching stage 9, the encoder stops receiving code symbols. When the remote unit re-enters its active state and begins decoding the received code symbols, the new code symbols have no correlation with the existing paths in the decoder since no code symbols have been received for the elapsed period of time. However, the state metrics are still present in the encoder and thus bias the decoding reverse link process.

In fig. 9, the same grid map as illustrated in fig. 8 is built from the previous data. At level 9 the remote unit enters its inactive state. Upon re-entering the active state, the metrics present in the decoder are initialized. For example, the metrics for states 00 and 10 may be set to 0. The metrics for the remaining states 01 and 11 may be set to 511 or some other value corresponding to the maximum metric value. In this case, the trellis state quantity is biased toward states 00 and 10. Biasing toward the trellis diagram state quantities will facilitate the path for communicating these states during the reverse link.

In another embodiment (e.g., according to the embodiment of IS-95), a convolutional encoder with constraint length 9 and code rate 1/2 IS used to encode the data. This produces a grid containing 256 possible states. In an IS-95-B based system, if the start of the paging channel message coincides with the start of the paging channel slot, a minimum of four 0's are sent at the end of the previous paging channel half-frame. Thus, a minimum of four 0 s are sent at the end of the previous paging channel half-frame. Although the remote unit will not receive a previous data packet containing a minimum of four 0 s at the end of the packet, only 16 of the 256 states are possible if code symbols corresponding to four consecutive 0 s have been entered into the trellis diagram of the decoder. In one embodiment, the 16 possible state metrics are initialized to a value of 0. The remaining 240 paths will be at a higher value, such as value 511 or a maximum value. This biases the trellis towards the more likely past state there.

In another embodiment, if the start of the paging channel message coincides with the start of the paging channel slot, a different fixed pattern of bits may be transmitted at the end of the previous paging channel half-frame. Thus, different initialization values may be selected accordingly. For example, if eight 0 s are sent at the end of the previous paging channel half-frame, then 256 states are possible with only one state. This initializes one state to bit 0 and the remaining states to a larger value, such as 511.

As illustrated by the above example, the performance of the decoder can be improved by using the encoded message characteristics. As illustrated, if it can be determined what code symbols were received without interrupting the code symbol stream, the decoder is biased to the active state and away from the inactive state based on the characteristics of the code symbols actually received. Biasing the decoder in this manner provides a better prediction of the maximum likelihood path through the trellis diagram with less processed data than would otherwise be required.

The foregoing can provide a significant improvement over systems that leave the state metric in whatever state the remote unit is in when it enters its inactive state. Biasing the trellis state quantities in the decoder towards the active state and away from the inactive state improves convergence of the reverse link through the trellis reverse maximum likelihood path.

In another embodiment, all state metrics are initialized to 0. Thus, when the remote unit begins receiving new code symbols and continues on the trellis diagram of fig. 9, there is no bias towards the previous path through the decoder. In another embodiment, the state quantities may be initialized to different values.

Fig. 10 is a flow chart showing a process of initializing a decoder. This process may be implemented using the remote unit described in fig. 6, and may be accomplished through hardware or software. Flow begins at block 100. In block 102, the remote unit enters an active state. In block 104, code symbols are received by the remote unit. Flow then continues to block 106 where the code symbols are accumulated in a deinterleaver. In block 108, it is determined whether the symbols of the full frame are accumulated in the deinterleaver. If the symbols of the full frame are not accumulated in the deinterleaver, flow continues to block 104 and additional code symbols are received. Referring again to block 108, if the symbols of the full frame are accumulated in the deinterleaver, flow continues to block 109. In block 109, it is determined whether the encoder state metrics are initialized. If the encoder state metrics are initialized, flow continues to block 114. If the encoder state metrics have not been initialized, flow continues to block 110.

For example, in block 109, it may be determined that the state metrics have not been initialized if a handoff to a new preferred base station has occurred or the received code symbol is from the first paging channel frame after the remote unit's assigned slot boundary, as described below. Alternatively, if enough active code symbols, e.g., 232 active code symbols (representing 116 bits), are received by a code rate 1/2 constrained length 9 decoder, the state metric will be initialized.

In block 110, it is determined whether the code symbol is from the first paging channel frame after the slot boundary. If the code symbols are from the first paging channel frame after the remote unit boundary, flow continues to block 112. The state metrics are initialized in block 112. The state metrics may be initialized to any of the biases described above, e.g., all metrics set to 0, some metrics set to 0 and others set to a maximum, or other combination. Referring again to block 110, if the code symbol is not from the first paging channel frame following a slot boundary or following state metric initialization, flow continues to block 114. Alternatively, the state metrics may be initialized at any time at block 110, and then flow continues to block 114.

In block 114, the decoder computes branch and state metrics. After the branch and state metrics are computed in block 114, flow continues to block 116. In block 116, the decoder performs the reverse link through the trellis, determines the maximum likelihood path through the trellis and outputs the corresponding decoded bits. Flow continues to block 118. In block 118, the remote unit determines whether it has entered its inactive state. If the remote unit is to continue to remain in its active state, then flow continues to block 104 and additional code symbols are received. If the remote unit is to enter its inactive state, flow continues to block 120 where the remote unit enters its inactive state. Flow then continues to block 102 where the remote unit remains in its inactive state until it re-enters the next active state.

The foregoing description details certain embodiments of the invention. It will be understood, however, that no matter how detailed the foregoing appears, the invention may be embodied in other specific forms without departing from its spirit or essential characteristics. For example, although a particular decoder with constraint layer 3 and code rate 1/2 is described. These principles apply to other encoders such as constraint length of 9 and code rate of 1/2 or other configurations. The described embodiments are to be considered in all respects only as illustrative and not restrictive, and the scope of the invention is, therefore, indicated by the appended claims rather than by the foregoing description. All changes which come within the meaning and range of equivalency of the claims are to be embraced within their scope.

Claims (27)

1. A method of decoding convolutionally encoded data, the method comprising:

receiving symbols of a stream of interrupted successive convolutional encoded codewords;

accumulating the symbols until a complete frame of symbols is received;

initializing metrics of a final node of a trellis diagram within a convolutional decoder to a first set of predetermined values if the symbol in the full frame is from a first paging channel frame after a slot boundary;

communicating the complete set of symbols to the convolutional decoder, wherein the convolutional decoder continues to construct the trellis diagram using the symbols;

computing a metric for each node on the trellis diagram in response to the received symbols;

generating coded bits in response to the metric values.

2. The method of claim 1, further comprising:

if the symbol in the full frame is not from the first paging frame after a slot boundary, then the metrics of the final node of the trellis diagram within the convolutional decoder are initialized to a second set of predetermined values.

3. The method of claim 1, further comprising:

initializing metrics of a final node of a trellis diagram within a convolutional decoder to said first set of predetermined values if said symbol in said complete frame is not from a first paging frame after a slot boundary.

4. The method of claim 1, wherein initializing a metric at each end node of the trellis comprises setting each of the metrics to 0 at each end node.

5. The method of claim 1, wherein initializing metrics at each end node of the trellis comprises setting a desired number of said metrics to 0 at each end node and setting a desired number of each of said metrics to a saturation value.

6. The method of claim 4, wherein said desired number to set said metric to 0 is 16.

7. The method of claim 4, wherein said desired number of setting said metric to a saturation value is 240.

8. A method of decoding a continuous stream of convolutionally encoded data for a remote unit in a slotted mode wireless communication system, wherein the remote unit receives only a portion of said continuous stream of convolutionally encoded symbols during an active state of said remote unit and does not receive said stream during an inactive state, the method comprising:

receiving symbols of a stream of interrupted successive convolutional encoded codewords;

accumulating the symbols until a complete frame of symbols is received;

initializing metrics at each final node of a trellis diagram within a convolutional decoder to a predetermined value if the symbol in the full frame is from a first paging channel frame after a slot boundary;

passing the complete set of symbols to the convolutional decoder, wherein the convolutional decoder continues to construct the trellis diagram using the symbols;

computing a metric for each node on the trellis diagram in response to the received symbols;

generating coded bits in response to the metric values.

9. The method of claim 8, wherein initializing a metric at each end node of the trellis comprises setting each of the metrics to 0 at each end node.

10. The method of claim 8, wherein initializing metrics at each end node of the trellis comprises setting a desired number of said metrics to 0 at each end node and setting a desired number of each of said metrics to a saturation value.

11. The method of claim 8, wherein said grid map comprises 256 possible states.

12. The method of claim 8, wherein said desired number to set said metric to 0 is 16.

13. The method of claim 8, wherein said desired number of setting said metric to a saturation value is 240.

14. A remote unit for a communication system, the remote unit comprising:

a receiver configured to receive a wireless link signal;

a deinterleaver configured to receive samples from the receiver and accumulate the samples into a series of data packets arranged in a time sequential order;

a decoder configured to receive the data packet string arranged in time series order, continue to construct a trellis stored in the decoder to decode the data packets and output decoded data;

a controller configured to determine whether the series of data packets is from a first paging channel frame after a slot boundary and, if so, to initialize a metric value at each final node of the trellis before the decoder continues to construct the trellis stored in the decoder.

15. The remote unit of claim 14 wherein said decoder is a Viterbi decoder.

16. The method of claim 14, wherein initializing a metric value at each final node of the trellis comprises setting each of said metric values to 0.

17. The method of claim 14, wherein said grid map comprises 256 possible states.

18. The method of claim 14, wherein initializing a metric value at each final node of the trellis comprises setting a desired number of the metric values to 0 and setting a desired number of the metric values to a saturation value.

19. The method of claim 18, wherein said desired number to set said metric to 0 is 16.

20. The method of claim 18, wherein said desired number of setting said metric to a saturation value is 240.

21. A method of decoding a convolutionally encoded codeword, the method comprising:

means for receiving symbols of an interrupted stream of consecutive convolutionally encoded code words;

means for accumulating the symbols until a complete frame of symbols is received;

means for determining whether said symbols in said complete frame are from the first paging channel frame after a slot boundary and if so initializing metrics within the convolutional decoder at each final node of the trellis;

means for transmitting said complete set of symbols to said convolutional decoder, wherein said convolutional decoder continues to construct said trellis diagram using said symbols;

means for calculating a metric for each node on the trellis diagram in response to the received symbols;

means for generating coded bits in response to the metric values.

22. The method of claim 21, wherein said grid map comprises 256 possible states.

23. The method of claim 21, wherein initializing a metric at each final node of the trellis comprises setting each of the metrics to 0 at each final node.

24. The method of claim 21, wherein initializing metrics at each final node of the trellis comprises setting a desired number of the metrics to 0 at each final node and setting a desired number of each of the metrics to a saturation value.

25. The method of claim 21 wherein said desired number to set said metric to 0 is 16.

26. The method of claim 21 wherein said desired number of setting said metric to a saturation value is 240.

27. The method of claim 21 wherein said convolutional decoder is a Viterbi decoder.