II. Description of the Related Art FIG. 1 is an illustrative block diagram of a variable rate CDMA transmission system 10 described in the Telecommunications Industry Association's Interim Standard TIA/EIA/IS-95-A Mobile Station-Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular System. This transmission system may be provided, for example, within a base station of a cellular transmission system for use in transmitting signals to mobile telephones within a cell surrounding the base station.

An input line 11 provides a speech or data signal which may be analog or digital. In the following example, it will be assumed that the input signal is a speech signal. The input line may be an analog or digital public switched telephone network (PSTN) line or other speech signal source. If the input speech signal is analog, the signal is sampled and digitized by an analog to digital converter (not shown). A variable rate data source 12 receives the digitized samples of the speech signal and encodes the signal to provide packets of encoded speech of equal frame lengths. Variable rate data source 12 may, for example, convert the digitized samples of the input speech to digitized speech parameters representative of the input voice signal using Linear Predictive Coding (LPC) techniques. In one embodiment, the variable rate data source is a variable rate vocoder as described in detail in U. S. Patent No. 5, 414, 796. Variable rate data source 12 provides variable rate packets of data at four possible frame rates 9600 bps, 4800 bps, 2400 bps and 1200 bps, referred to herein as full, half, quarter, and eighth rates. Packets encoded at full rate contain 172 information bits, samples encoded at half rate contain 80 information bits, samples encoded at

quarter rate contain 40 information bits and samples encoded at eighth rate contain 16 information bits. The packets regardless of size all are one frame length in duration, i. e. 20 ms. Other systems may employ other data rates or packet sizes. Herein, the terms"frame"and"packet"may be used interchangeably.

The packets are encoded and transmitted at different rates to compress the data contained therein based, in part, on the complexity or amount of information represented by the frame. For example, if the input voice signal includes little or no variation, perhaps because the speaker is not speaking, the information bits of the corresponding packet may be compressed and encoded at eighth rate. This compression results in a loss of resolution of the corresponding portion of the voice signal but, given that the corresponding portion of the voice signal contains little or no information, the reduction in signal resolution is not typically noticeable. Alternatively, if the corresponding input voice signal of the packet includes much information, perhaps because the speaker is actively vocalizing, the packet is encoded at full rate and the information bits of the packet are not compressed at all.

This compression and encoding technique is employed to limit, on the average, the amount of signals being transmitted at any one time to thereby allow the overall bandwidth of the transmission system to be utilized more effectively to allow, for example, a greater number of telephone calls to be processed at any one time.

The variable rate packets generated by data source 12 are provided to packetizer 13 which selectively appends cyclic redundancy check (CRC) bits and tail bits. The variable rate packets from packetizer 13 are then provided to encoder 14 which encodes the bits of the variable rate packets for error detection and correction purposes. In one embodiment, encoder 14 is a rate 1/3 convolutional serial Viterbi encoder. The convolutionally encoded symbols are then provided to a modulator 16 which generates a modulated signal. An implementation of a CDMA modulator is described in detail in U. S. Patent Nos. 5, 103, 459 and 4, 901, 307. The modulated signal is then provided to digital to analog converter 22 for conversion to an analog signal, then provided to transmitter 24 which upconverts and amplifies the signal for transmission through antenna 26.

FIG. 2 illustrates pertinent components of a mobile telephone 28 or other mobile station receiving the transmitted signal. The signal is received by antenna 30, downconverted and amplified, if necessary, by receiver 31 and demodulated by a demodulator 32 into a stream of symbols which remain convolutionally encoded. The signal is then provided to a serial Viterbi decoder 34 which decodes a convolutionally encoded stream of symbols.

The decoder also subdivides the received signal into packets and determines the corresponding frame rate for each packet. The frame rate may be determined, for example, by detecting the duration of individual bits of the frame. Aspects of an exemplary serial Viterbi decoder are described in co- pending U. S. Patent Application 08/126, 477 filed September 24,1993, assigned to the assignee of the present invention and incorporated by reference herein.

To decode the stream of symbols, decoder 34 employs a branch error metric block 36 which receives symbols from the demodulator and an Add Compare Select block (ACS) 38 which produces decision bits based upon the symbols using two separate RAM's 40 and 41. To generate the decision bits the ACS is configured to emulate the memory elements of the encoder (encoder 14 of FIG. 1) by cycling through all states. To this end the ACS determines from which encoder state metric each new encoder state metric was arrived from. To enhance performance, the decoder chains back from what it considers the best state metric using a chainback block 42 which processes the decision bits received from ACS 38. Ultimately, decoder 34 provides a decoded packet along with a signal identifying a detected frame rate for the packet. Both are forwarded to a frame quality check unit 43 which attempts to verify that no transmission errors or frame rate detection errors occurred. In the exemplary embodiment, frame quality check unit 43 performs a CRC, a symbol error rate check and a Yamamoto metric check.

To perform the symbol error rate check, frame quality check unit 43 re- encodes symbols found in the decoded packet and compares the re-encoded symbols with symbols input to the frame quality check unit to detect any differences. To perform the Yamamoto metric check, frame quality check unit 43 applies the received frames to a trellis path decoder and determines whether a resulting metric is acceptable. Acceptable frames are routed to a speech decoder 44 for conversion back to digitized voice signals. The digitized voice signals are converted to analog signals by a digital to analog

converter (not shown) for ultimate output through a speaker 46 of the mobile telephone such that an operator of the telephone can hear the speech signal that had been originally input to the overall system along line 11 of FIG. 1.

Although not shown, the mobile telephone of FIG. 2 may have additional components for inputting an analog speech signal from the operator of the mobile telephone and for processing and transmitting the signal using CDMA techniques. The additional components of the mobile telephone may be similar to the components shown in FIG. 1. Moreover, although not shown, the transmission system of FIG. 1 may have additional components provided for receiving the transmitted signal from the mobile telephone and for processing and outputting the signal as an analog or digital speech signal, perhaps onto a PSTN line. The additional components of the system of FIG. 1 may be similar to the components shown in FIG. 2.

Thus an important component of the overall system is the serial Viterbi decoder provided for decoding the transmitted symbols. As noted, the decoder employs an ACS which emulates the memory elements of the encoder used to encode the signals by cycling through all states in order from 0 through to 2K-l-1 wherein K is the constraint length of the code employed by the encoder. More specifically, the constraint length K is equal to one more than the number of delay elements in the encoder. The order in which the states are cycled through is functionally irrelevant as long as long as the cycling is consistent. FIG. 3 shows all possible state transitions. The notation x0 as used herein indicates that the least significant bit of the state is 0 while the upper bits are represented by x. Ox indicates that the most significant bit is 0 while the lower bits are x. The incoming information bit determines which transition is made from a given state and will in fact form the most significant bit of the target state. Starting in state 0, it is only possible to transition to states 0 and hex 80. A transition to state 0 means that the input bit is a 0 (the bit that gets shifted into the leftmost bit of the target state), while if the input bit is a 1, then it is only possible to transition to state hex 80 (Ix in FIG. 3. ) As can be seen, due to the manner in which the new state metrics are calculated, states are calculated out of order vs. the order in which the states were read. Hence, the ACS employs the aforementioned separate RAM's 40 and 41 and pages between the two RAM's. As such, the newly calculated metrics are written to a different

memory from the one from which the metrics were read. The next time the metrics are calculated, the function of the two memories are swapped. Each RAM memory must store 2K-' metrics. Alternatively, the serial Viterbi decoder could be configured to use only a single memory storing 2K metrics.

In either case, though, the need to store a total of 2K metrics is an inefficient use of memory that results in a larger amount of circuit area being required for implementation than would otherwise be desirable.

Accordingly, it would be desirable to provide a technique for eliminating the need to store as many metrics and it is to that end that aspects of the present invention are primarily directed. Although described with respect to a CDMA system employing a serial Viterbi decoder with an ACS, similar problems can occur in other systems employing serial Viterbi decoders with ACS's and in related decoder systems as well.

SUMMARY OF THE INVENTION In accordance with the invention, an improvement is provided within a serial Viterbi decoder for decoding a convolutionally encoded stream of symbols using an add-compare-select (ACS) unit configured to store only 2'metrics wherein K is a constraint length previously utilized in encoding the stream of symbols.

In an exemplary embodiment, the serial Viterbi decoder includes a branch error metric block, an ACS, and a chainback block. The ACS generates a plurality of decision bits from a convolutionally encoded stream of symbols received from the branch error metric block during each of plurality of process cycles, wherein one cycle of all encoder states is one process cycle. Each decision bit is representative of an error metric of a corresponding encoder state. The ACS has one or more memories storing state metrics for each of the encoder states and is configured to both read from and write to the memories. The memories collectively store only 2K-1 metrics. To this end, the ACS includes a left rotator for cyclically generating a read address signal specifying addresses to be read from the memories ; a set of delay elements connected to an output of the left rotator for delaying the read address signal to generate a write address signal specifying addresses to be written to within the memories ; and a multiplexor for receiving the read

address signal and the write address signal and generating a single address signal and for applying to an address input of the memories. The left rotator receives an input signal specifying an encoder state and a rotate signal specifying the amount of rotation, wherein the rotate signal is changed each time the ACS has cycled through all encoder states. The rotate signal is equal to the number of the process cycle modulo K-1-log2N wherein N is the number of state metrics stored per memory location. Hence, with differing values of N, a variety of configurations are supported.

In the various exemplary implementations, by providing an ACS which requires storing only 2K-1 metrics, rather than 2K metrics, savings are achieved in circuit area size. Other advantages may be achieved as well.

Both method and apparatus embodiments of the invention are described.

BRIEF DESCRIPTION OF THE DRAWINGS The features, objects, 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 an block diagram illustrating pertinent components of a variable rate CDMA transmission system ; FIG. 2 is an block diagram illustrating pertinent components of a mobile telephone or other mobile station receiving the signal transmitted by the CDMA transmission system of FIG. 1 and decoding the signal using a serial Viterbi decoder having an ACS with two separate RAM's ; FIG. 3 is a state diagram illustrating the permissible state transitions for the ACS.

FIG. 4 is an block diagram illustrating, at a high level, pertinent components of a mobile telephone or other mobile station configured in accordance with an exemplary embodiment of the invention wherein a serial Viterbi decoder having an ACS with only a single state RAM is employed.

FIG. 5 is an schematic illustrating an exemplary embodiment of the ACS with single state RAM of FIG. 4.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS With reference to the remaining figures, preferred and exemplary embodiments of the invention will now be described. The preferred and exemplary embodiments are described with respect to a mobile station of a cellular telephone system employing a serial Viterbi decoder. However, principles of the invention may be exploited within any product employing a serial Viterbi decoder.

FIG. 4 illustrates pertinent components of a mobile telephone 128 or other mobile station receiving a transmitted CDMA signal. Portions of mobile telephone 128 operate in the same manner as the mobile telephone of FIG. 2 and will be only briefly described. The CDMA signal is received by antenna 130, downconverted and amplified, if necessary, by receiver 131 and demodulated by a demodulator 132 into a stream of convolutionally encoded symbols. The convolutionally encoded symbols are then provided to a modified serial Viterbi decoder 134 which decodes the stream of symbols using a branch error metric block 136, an ACS 138, a chainback block 140.

The ACS produces decision bits based upon the symbols received from the branch error metric block. To generate the decision bits the ACS emulates the memory elements of the encoder used to encode the data (e. g. encoder 14 of FIG. 1). To this end, the ACS cycles through all states in order from 0 through to 2K-l-1 and determines the previous encoder state metric from which each new metric was derived.

The ACS includes a single RAM 141 for storing the state metrics by writing new state metrics into the memory locations of the states previously read. As a result, rather than requiring the information for a state to always be located at the same memory location every process cycle as in previous ACS implementations, the new state information is written into a previously read state. The ACS reads the states in a consistent order (e. g. state order). Hence, the ACS first determines where each state is stored. As

will be described below, a process cycle counter is provided within the ACS which increments each time the ACS has cycled through 2 states. The counter is used to rotate the state number of interest to derive the memory address for that state. By using only a single RAM storing 2K-1 metrics, the ACS uses less circuit area as compared to previous implementations requiring either separate RAMS each storing 2K-1 metrics or a single RAM storing 2K metrics.

The state with the lowest error metric generated by the ACS is passed to the chainback block which processes the decision bits received from ACS.

Though not shown, the chainback block may have its own RAM.

Ultimately, decoder 134 provides a decoded packet along with a signal identifying a detected frame rate for the packet a frame quality check unit 143 which attempts to verify that no transmission errors or frame rate detection errors occurred using a CRC, a symbol error rate check and a Yamamoto metric check. Acceptable frames are routed to a speech decoder 144 for conversion back to digitized voice signals. The digitized voice signals are converted to analog signals by a digital to analog converter (not shown) for ultimate output through a speaker 146 of the mobile telephone. Although not shown, the mobile telephone of FIG. 4 may have additional components for inputting an analog speech signal from the operator of the mobile telephone and for processing and transmitting the signal using CDMA techniques. The additional components of the mobile telephone may be similar to the components shown in FIG. 1.

Thus, FIG. 4 illustrates, at a high level, a serial Viterbi decoder having an ACS with only a single RAM storing 2K-1 metrics. The ACS and ACS RAM of FIG. 4 may be implemented using any of variety of specific configurations. Some specific exemplary configurations adapted for use with IS-95 mobile telephone specifications will now be described.

FIG. 5 illustrates an exemplary embodiment of circuitry for implementing an ACS with a single state RAM for IS-95 for K=9 and N=2.

A left rotator 150 (or re-circulating shift register) receives an acs~cycle(7:1) signal identifying the current encoder state of the ACS. (The 7 : 1 refers to all bits of the encoder state except the least significant bit and the current information bit. The state is composed of the bits stored in the K-1 latches and the current data bit. The 7 : 1 thereby strips off the least significant bit (i. e.

the oldest data bit) and the most significant bit (i. e. the newest data bit).

These bits may be removed for an IS-95, K=9, N=2 implementation as a result of optimizations employed therein. In other implementations, the least significant bit and the most significant bit may need to be explicitly processed. ) Left rotator 150 also receives a"rotate by"signal pcycle modulo 7 which is a counter incremented each time the ACS has cycled through all 2K- l states. pcycle thereby tracks the process cycle number. The use of acs~cycle(7:1) and pcycle modulo 7 are appropriate for a IS-95, K=9, N=2 system. In other systems, other values are employed in connection with acs~cycle and pcycle. For example, for a K=9, N=1 system, acsci/cC7;0 is employed instead of acs~cycle(7:1).

Left rotator 150 calculates a read address for reading the correct state metric corresponding the current encoder state from a state RAM 152. The read address is output as a rdaddr signal. Read address signal rdaddr is routed through three delay registers 154,156, and 158 (each driven by an oddclk signal which pulses every other clock cycle) to generate a delayed signal wraddr. Signals rdaddr and wraddr are both routed into a multiplexor 159, the output of which is applied as the actual read or write address-input addr of state RAM 152. The state RAM also receives an acsen signal as its csM input. The acsen signal disables the ACS when the ACS is not in use.

The acsen signal is also routed into a NAND gate 160 which also receives the oddclk signal inverted by an inverter 162. The output of NAND gate 160 is applied to the state RAM as the we~n input. Finally, the state RAM also receives new state metrics as data input din.

A summary of the various signals used in the ACS of FIG. 5 is as follows : acs~cycle is the encoder state that the ACS is cycling through. pcycle is a counter that is incremented each time the ACS has cycled through all 2K-1 states. It keeps track of the process cycle number. acsen simply disables the ACS when the ACS is not in use. oddclk pulses every other clock cycle and causes a read operation from the State RAM when oddclk is high. When oddclk is low, a write operation is performed.

rdaddr is the calculated read address whereas wraddr is the delayed version of rdaddr.

In use, during a first process cycle, all of the state metrics are assumed to be stored in state RAM 152 in their correct state order (i. e. memory location 0 contains state 0's metric, location 1 contains state 1's metric, etc.) and are read from the state RAM in that order. For example, the ACS reads states 00 and 01 and can then calculate new values of states 00 and hex 80.

Then the ACS reads states 02 and 03 and calculates new metrics for states 01 and hex 81. (All state numbers used herein are in hexadecimal format.) Once the value from a memory location has been read from the state RAM, the values therein are no longer needed and the memory location is then available to store a new metric for a different state. As noted, left rotator 150 determines the new memory location for each state. Delay elements 154, 156 and 158 operate to delay writing into the memory locations until after the previous values have been read until after the previous values have been read and the new ones calculated.

As an example, Table I illustrates the states that are present in the state RAM at the beginning of each process cycle. For this example, K=9 so there are 2'or 256 states. This particular architecture also assumes that two consecutive states are stored in each memory location, so that there are actually 128 memory words. During the first process cycle the states are in order, but new state metrics are calculated out of order resulting in the states being ordered as they are for process cycle 1. The states are then read in state order and new metrics are stored resulting in the states being ordered as indicated under process cycle 2. This process continues cyclically until the new metrics are again stored in normal order. For this example, the order of the metrics cycles back to the original order in process cycle 7. SRAMProcessCycle MOD 7 Address0123456 00 00,01 00,01 00,01 00,01 00,01 00,01 00,01 01 02,03 80,81 40,41 20,21 10,11 08,09 04,05 02 04,05 02,03 80,81 40,41 20,21 10,11 08,09 03 06,07 82,83 C0,C1 60,61 30,31 18,19 0C,0D 04 08,09 04,05 02,03 80,81 40,41 20,21 10,11 05 0A,0B 84,85 42,43 A0,A1 50,51 28,29 14,15 06OC,OD06,0782,83CO,C160,6130,3118,19 07 0E,0F 86,87 C2,C3 E0,E1 70,71 38,39 1C,1D 08 10,11 08,09 04,05 02,03 80,81 40,41 20,21 09 12,13 88,89 44,45 22,23 90,91 48,49 24,25 0A 14,15 0A,0B C4,C5 42,43 A0,A1 50,51 28,29 78 F0,F1 78,79 3C,3D 1E,1F 8E,8F C6,C7 E2,E3 79 F2,F3 F8,F9 7C,7D 3E,3F 9E,9F CE,CF E6,E7 7a F4,F5 7A,7B BC,BD 5E,5F AE,AF D6,D7 EA,EB 7b F6,F7 FA,FB FC,FD 7E,7F BE,BF DE,DF EE,EF 7cF8.F97C.7D3E.3F9E,9FCE,CFE6.E7F2.F3 7d FA,FB FC,FD 7E,7F BE,BF DE,DF EE,EF F6,F7 7e FC,FD 7E,7F BE,BF DE,DF EE,EF F6,F7 FA,FB 7f FE,FF FE,FF FE,FF FE,FF FE,FF FE,FF FE,FF TABLE I

Thus FIG. 5 and Table I together illustrate an embodiment wherein two consecutive states are stored in each memory location of the state RAM.

In other implementations, the state RAM may be configured to store more or fewer states in each memory location as needed to permit the ACS to handle limited memory bandwidth or to reduce the number of cycles required to compute 2K-1 states. For example, in one other implementation, the memory is configured to store only half the number of words but where each word contains twice as many bits. In this case, four consecutive states are stored in each memory location. The number of delay stages differs from that of FIG. 5 as appropriate to provide the proper delay to the read address.

In another implementation, rather than delay the read address by three clock cycles using registers 154 -158, circuitry is provided to subtract"3" from the acscycle using a subtractor and to then feed the modified acscycle through a second left rotator to generate the write address. Hence, an additional left rotator and a subtractor are employed rather than registers 154 - 158. Still other circuit variations may be employed as well.

In yet another implementation, illustrated by way of Table II, a single state is stored at each memory address (K=9). Each cell specifies the state # that is stored at the State RAM address provided in the corresponding entry of the left-most column of the table at the beginning of the process cycle shown at the corresponding entry of the top row of the table. For example, for process cycle 0, Table II shows that state 0 is stored at address 0, state 1 is at address 1, etc. When the new state metrics are calculated, the new metrics are written such that they reflect what is shown under Process cycle 1, hence state 0's new metric is written to address 0, state 80's new metric is written to address 1, state 1's new metric is written to address 2, state 81's new metric is written to address 3, etc. SRAM Process Cycle MOD 8 Address01234567 00 00 00 00 00 00 00 00 00 01 01 80 40 20 10 08 04 02 02 02 01 80 40 20 10 08 04 03 03 81 CO 60 30 18 OC 06 04 04 02 01 80 40 20 10 08 05 05 82 41 A0 50 28 14 0A 06 06 03 81 C0 60 30 18 0C 07 07 83 C1 E0 70 38 1C 0E 08 08 04 02 01 80 40 20 10 09 09 84 42 21 90 48 24 12 OA OA 05 82 41 A0 50 28 14 F8 F8 7C 3E 1F 8F C7 E3 F1 F9 F9 FC 7E 3F 9F CF E7 F3 FA FA 7D BE 5F AF D7 EB F5 FBFBFDFE7FBFDFEFF7 FC FC 7E 3F 9F CF E7 F3 F9 FDFDFE7FBFDFEFF7FB FEFE7FBFDFEFF7FBFD FF FF FF FF FF FF FF FF FF

TABLE II Numerous other embodiments are consistent with the invention as well. In general : K is the constraint length of the code (the examples illustrate the case for IS 95 systems wherein K=9). Other values for K are employed in other systems.

N is the number of states stored per memory location. N is dependent on the particular architecture. Faster decoders may need to store more states per memory location.

The number of address words is then = 2Ki °g2N The number of address bits is therefore = K-1-log2N.

The number of possible ways to rotate this address is also K-1-log2N.

Hence, to implement any particular embodiment, a counter is provided that increments for each process cycle but counts modulo K-1-log2N.

(Table I illustrates the case where K=9, N=2, so the process cycle value is modulo 7. Table II illustrates the case where K=9, N=1, so the process cycle value is modulo 8.) The exemplary embodiments have been primarily described with reference to diagrams illustrating apparatus elements. Depending upon the implementation, each apparatus element, or portions thereof, may be configured in hardware, software, firmware or combinations thereof. It should be appreciated that in some cases not all components necessary for a complete implementation of a practical system are illustrated or described in detail. Rather, in those cases only those components necessary for a thorough understanding of the invention have been illustrated and described. Finally, the preceding description of the preferred and exemplary embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art and the generic principles defined herein may be applied to other embodiments without the use of the inventive faculty. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

WHAT IS CLAIMED IS :