Multichannel viterbi decoder

ES 2 387 708 T3

DESCRIPTION

Method and apparatus for wireless communication

BACKGROUND OF THE INVENTION

Field of the invention

[0001] The present invention relates generally to digital communications. More specifically, the invention relates to a system in which data is transmitted and received at a variable rate in a communications receiver where the variable rate data is decoded in an efficient, multi-channel, multi-rate data decoder.

Description of the state of the art

[0002] The most advanced communication technology today makes use of spread spectrum modulation or code division multiple access (CDMA) for point-to-multipoint telecommunications. Since the 1950s, CDMA has been used in military applications, due to difficulty in detection and interference in the transmission of communications. This attribute is due to a wireless communication technique that uses a modulated transmission bandwidth much greater than the information bandwidth of the transmitted signal.

[0003] Figure 1 shows a CDMA communication scheme. A single communication channel of a given bandwidth is mixed with a spreading code. The relatively narrow band modulated signal is spread across a sequence to occupy a much wider transmission bandwidth by multiplying with a single spreading code. The spreading code comprises a pseudo-random sequence or noise-like high-speed code that becomes part of the transmitted data. The low-level noise appearance of the resulting transmitted signal is such that it is unlikely to interfere with other users of the spectrum.

[0004] At the receiver, the signal is de-spread by correlating the received broadband signal with a locally generated identical pseudo-random sequence to resolve the data from a plurality of data signals occupying the same transmission bandwidth. This expands the signal back to its original bandwidth and also expands any narrowband radio signals present in the occupied spectrum so that they appear as noise at the receiver. By using many different pseudo-random code sequences, multiple users can be received within the same transmission spectrum.

[0005] The same characteristics that have allowed CDMA communication techniques to be successful in military applications also make CDMA communication systems, particularly Broadband Code Division Multiple Access ™ Code Division multiple access systems. or B-CDMA ™, are interesting for the efficient use of the congested commercial radio frequency spectrum. Among the many attributes of the CDMA system is the unlimited virtual capacity of the system. Since each user in a CDMA communication system transmits and receives signals over the same transmission bandwidth, there are less stringent protection band and channelization requirements. Unlike FDMA and TDMA systems where capacity is limited by the number of separate channels, CDMA systems capacity is limited by interference. Therefore, the number of users able to communicate simultaneously on that given transmission bandwidth is significantly increased.

[0006] In addition to voice information, information other than voice alone or a combination of the two may be transmitted to the receiver. Some communication standards such as Integrated Services Digital Network (ISDN) require a much higher data rate than digitized voice. To optimize the communication system, various data rates are transmitted to increase the signal-to-noise ratio (SNR) to all receivers.

[0007] A measure of spread spectrum performance is the process gain of the system, G_p, which is determined by the channel bit rate relative to the information bit rate, Rc / R_hThe input and output signal to noise ratios correspond as follows

H.H

Equation 1 - = GE -) - N ”h 'aa

ES 2 387 708 T3

It can be seen that the higher the data rate, the more interference occurs and the signal-to-noise ratio will be affected. Reduced interference translates directly into increased capacity.

[0008] Most CDMA telecommunications systems transmit variable rate data to keep the signal-to-noise ratio as high as possible. To achieve this, the speed of the transmission data is either identified in the system level control message that is part of the signal channel or a given receiver must be able to detect the speed of the transmitted data.

[0009] As many users share this same spectral transmission channel, interference can be induced from one user to another when there is not sufficient coded isolation between the users. Also, the data rate must be known before decoding the convolutional error correction at the transmitter or receiver.

[0010] Most prior art receivers use separate single rate convolution decoders to properly reconstruct digital data, once received and de-spread. As the data rate information is transmitted for each frame, the receiver does not have to determine from the received frame of data the rate at which the data was encoded, thus decreasing the complexity of the receiver and increasing the overall speed of the receiver. system. However, the use of dedicated convolutional decoders for each transmitted data rate reduces overall processing efficiency and increases system costs.

[0011] JP-8 195683 A (Oki Electric IND CO LTD) of July 30, 1996 describes a data receiver that receives code data having a variable data rate and is encoded with any one of a plurality of data types and are then repeated according to the respective data rates to thus provide them with the same data rate and restore, frame by frame, the data of the received code into data having the original data rates. The receiver has a data rate sensing circuit that sequentially receives a frame of code data having the same data rate at the same time, and detects the data rate of the assigned code data prior to repetition. A data rate restorer circuit restores, based on the detected data rate, the code data frame for data having the original data rate.

Therefore, there is a need for an efficient convolutional decoder that can handle variable data rates.

SUMMARY DESCRIPTION OF THE INVENTION

The present invention relates to a communication system in which a transmitter encodes the data rate of a given transmission and then uses it to adjust a plurality of convolutional decoders that share a common memory. The system uses common processing resources to provide up to four independent channels with convolutional decoding with multi-speed error correction that results in reduced silicon area and low power operation. The system is capable of supporting voice communications at 8 kbps up to 64 kbps for high-speed ISDN communication. Although the present invention can be used in a variety of communication systems, preferred communication systems include mobile phone, PCS, wireless local loop, and CDMA communication. The present invention can be used in both base station and switchboard receivers.

Accordingly, it is an object of the present invention to provide an efficient multi-rate convolutional decoder for multi-channel applications.

Another object of the invention is to provide a multi-channel convolutional decoder architecture of reduced complexity and higher performance.

[0016] Those skilled in the art will understand other objects and advantages of the system and method after reading the detailed description of the preferred embodiment.

BRIEF DESCRIPTION OF THE DRAWINGS

[001 η

Figure 1 is a block diagram of a typical CDMA communication system according to the state of the art.

ES 2 387 708 T3

Figure 2 is a detailed block diagram of a CDMA communication system.

Figure 3a is the first section of a detailed block diagram of the preferred embodiment.

Figure 3b is the second section of a detailed block diagram of the preferred embodiment.

Figure 4 is an overall block diagram of the preferred embodiment.

Figure 5 is a block diagram of the interface between a main digital signal processor and the preferred embodiment.

Figure 6 is a diagram of the QPSK constellation.

Figure 7 is a detailed block diagram of a sum-compare-select channel.

Figure 8a is the first section of a flowchart of the sum-compare-select sequencer.

Figure 8b is the second section of a flowchart of the sum-compare-select sequencer.

Figure 9 is a detailed block diagram of a sum-compare-select sequencer.

Figure 10 is a flow chart of the tracking process.

Figure 11 is a flow chart of the bit error relationship process.

Figure 12 is a graph of bit error ratio (BER) performance versus signal-to-noise ratio.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

The present invention is described with reference to the figures of the drawings where the same numbers represent the same elements.

The multi-channel, multi-speed Viterbi decoder made according to the present invention is carried out in the context of a CDMA 17 cell phone system. These decoders are used in multi-channel wireless communication stations with the reception of communication signals . System 17, as shown in Figure 2, includes a transmitter 19 and a receiver 21, which can reside in either a base station or a mobile user receiver.

[0020] Transmitter 19 includes a signal processor 23 that encodes voice and non-voice data 25 into frames of various data rates, eg, 8 kbps, 16 kbps, 32 kbps or 32 kbps frame rates. 64 kbps. Signal processor 23 selects a rate depending on the amount of speech activity, whether the data is speech, or in response to a set data rate.

Two steps are involved in generating a transmitted signal in a multiple access environment. First, the input data 25, which can be considered a biphasic modulated signal, is encoded using a direct error correction coding (FEC) 27. As a convolution code R =% is used, the only data signal biphasic modulated signal is converted into two biphasic modulated signals. One signal is designated a phase I channel. The other signal is designated the quadrature Q channel. The biphasic I and Q modulated signals are generally called Quadrature Phase Shift Keying (QPSK). In the preferred embodiment, the tap generator polynomials 29, 31 for a restriction length of K = 7 and a convolutional code rate of R = ½ are:

G₁ = 171_fl and G₂ = 133₈ ;

In the second step, the two biphasic modulated data or symbols 33a, 33b are expanded with QPSK pseudo-random sequences in phase (I) 35a and quadrature (Q) 35b. The resulting expanded signals I 37a and Q 37b are mixed with a carrier frequency 43, combined 45 with other expanded signals (channels) having different spreading codes, and 47 transmitted. Transmission 47 may contain a plurality of individual channels having different data rates.

ES 2 387 708 T3

The receiver 21 includes a demodulator 49a, 49b that mixes the transmitted broadband signal 47 at an intermediate carrier frequency 51a, 51b. Then the QPSK signals are filtered 53 and mixed 55a, 55b with the locally generated QPSK pseudo-random code 35a, 35b that matches the transmitted code. Only the original waveforms that were spread by the same code at transmitter 19 will be efficiently spread. Others will appear as noise on the receiver 21. The data 57a, 57b is then passed to a signal processor 59 where FEC decoding is performed on the convolutionally encoded data.

The present invention 61 performs decoding using an efficient multi-rate, multi-channel Viterbi 61 decoder, as shown in Figures 3a and 3b. The decoder 61 comprises a digital signal processor (PDS) for the interface of the Viterbi decoder 63, a common eudidea distance calculation engine 65, a plurality of sum-compare-select (SCS) channels 67a, 67b, 67c, 67d, a status indicator memory array 69, an SCS sequencer 71, a trace memory array 73, a trace processor 75, and a decoder for the system interface 77. The system as shown in Figures 3a and 3b can be assembled separately or applied as an integrated circuit of specific application efficiency (CIAE) 79.

[0025] In the preferred embodiment, any of the four channels (0, 1, 2, 3) within decoder 61 can process a plurality of data types: 8 kbps, 16 kbps, 32 kbps, or 64 kbps. Other data rates can be used in alternative embodiments. The lowest data rates are obtained by enabling a time diversities combining function that works on redundantly received symbols. This effectively increases the SNR of the signals received with time diversities. For those symbols in frames corresponding to data rates lower than the highest expected data rate, the symbol data is repeated to maintain a constant symbol rate for the frame.

[0026] For the 64 kbps data rate, a QPSK symbol is sent every 15.625 ps. For the data rate of 32 kbps, the corresponding QPSK symbol is sent twice over one channel. Symbols are still sent at the speed of 64 kbps, but with double redundancy thus effectively reducing the information rate to 32 kbps. For a data rate of 16 kbps, the corresponding QPSK symbols are sent through the channel with 4 times diversity. For an 8 kbps data channel, 8 times diversity.

With reference to Figures 3a and 3b, the multichannel decoder 61 shares common resources to minimize silicon area. As shown, status indicator memory 69 and trace memory 73 are static random access memories (SRAM) and are commonly used for each channel. The 65 common Euclidean distance geometry engine, which calculates the square Euclidean distance between the received QPSK symbol and the four possible constellation points in QPSK space for all four channels, further increases the efficiency

The system architecture as shown implements the Viterbi algorithm and decodes the convolutionally encoded data. The corresponding tap generator polynomials for a constraint length of K = 7 and a code rate of R = ½ are Gi = 171₈ (29) and Gz = 133e (31). It should be understood that other tap generator polynomials may be used in alternative embodiments, depending on the different different restriction lengths and rate codes. For example, for a constraint length of K = 9 and a code rate of R = ½. the generating tap polynomials are Gi = 753e and 561e. The use of tap generators is well known to telecommunications experts and is used in the FEC 27 encoder.

[0029] Figure 4 shows a global architecture of the system. A main microcontroller 81 programs a timing and control module (MTC) 83 located in CIAE 79 through data lines from microcontroller 85, address lines 87 and a write marker 89. Microcontroller 81 determines, from the transmitted frame, the time diversity factor for a given channel. The mix of diversities is controlled by selectively asserting and denying the combining signals of the diversities 91a, 91b, 91c, 91d for channels 0 to 3, respectively. A data output 93 leaves a main PDS 95 and carries the I and Q signals for the four channels to the interface of the Viterbi decoder 63. The main PDS 95 that enables signal 97 and address lines 99 is also coupled to the Viterbi 63 decoder interface. The main microcontroller 81 controls the diversity combining signal 91a, 91b, 91c, 91d. The main PDS 95 controls the data of the individual channels 93 entering the interface of the set-top box 63.

The MTC 83 accepts an externally derived high frequency reference signal 103 for overall system timing. The MTC 83 uses the reference signal 103 and derives a high frequency dump 105 and Viterbi clock signals 107. The MTC 83 also produces a global reset of the decoder 149.

[0031] The data rate of a particular channel is reduced by the microcontroller 81 by enabling the respective diversity combining signal 91a, 91b, 91c, 91d. For a data rate of 32 kbps, two adjacent symbols are combined; for a data rate of 16 kbps four symbols are combined and for a data rate of 8 kbps eight symbols are combined.

ES 2 387 708 T3

The preferred embodiment uses time diversity to process the data at various rates. At a data rate of 64 kbps, each individual bit transmitted is used. However, at the lowest data rate, 8 kbps, each bit is doubled by a factor of 8. When processed at the lowest data rate, the redundant symbols are simply added together. As explained in the background of the invention, each time a symbol is sent through a respective channel a certain gain and noise figure is received. Therefore, if the same signal is sent through the channel twice, the SNR ratio is effectively doubled. The reason is that redundant symbols add coherently, while the random noise introduced does not add coherently. From the highest data rate of 64 kbps to the lowest of 8 kbps the signal gain is effectively multiplied by a factor of 8.

[0033] By lowering the data bit rate and using time diversity, the transmit power of the signal can be reduced proportionally since the gain will be recovered when the various symbols are assembled. Using the mix of diversities reaches lower data rates without detrimental effects on lowering SNR ratios.

[0034] For the maximum data rate of 64 kbps, the diversities combiner function must be disabled. This is done by keeping the diversity combining signal 91a, 91b, 91c, 91d high for that particular channel. When the multichannel decoder 61 operates at lower data rates, the diversity combining signal 91a, 91b, 91c, 91d controls which adjacent symbols are combined, when the decoder is enabled, and when the interface 63 is left free for a new set. of symbols.

[0035] As shown in Figure 5, the interface of the decoder 63 accepts two complementary 8-bit I and Q samples on the data bus 93 of the main PDS 95. Data from the main PDS 95 is input through the bus data 93 in an address decoder 111. Data bus 93 is a parallel input bus, however the data arrives sequentially between the 4 channels. The data is then separated into individual in-phase and quadrature components for each channel and sent to each clipping and dump ICs 1131, 113Q, 1151, 115Q, 1171, 117Q, 1191, 119Q, over lines 1211. , 121Q, 1231, 123Q, 1251, 125Q, 1271,127Q, for channels 0-3, respectively. Interface 63 includes 8-bit accumulators that have saturation logic. The maximum positive saturation value is 0x7fie and the maximum negative saturation value is 0x80i6. In the Viterbi 63 decoder interface, the combination of time diversities is performed using two complementary binary operations. All redundant I and Q samples are summed when at the lowest data rates. Similarly, saturation adders are used to eliminate the sign change if there is an overflow. Instead of the diversities combining function residing in a separate PDS IC, the custom feature has been included in the CIAE. After executing the diversities combiner function, the results are sent on lines 1291, 129Q, 1311, 131Q, 1331, 133Q, 1351, 135Q for channels 0-3, respectively. The saturation integrated dump circuits also control the eudide distance calculation engine 65 enabling 137a, 137b, 137c, and 137d for channels 0-3, respectively.

[0037] Referring again to Figures 3a and 3b, all internal processors of multichannel decoder 61 are synchronized with Viterbi clock 107. Main PDS 95 is clocked by its own asynchronous clock (not shown). The PDS clock and the dump signal 105 are resynchronized with the Viterbi clock 107. The decoder 61 requires that the Viterbi clock 107 should be slightly faster than the dump signal 105.

[0038] All channels are coupled from the interface of decoder 63 to the Euclidean distance calculation engine 65 in individual I and Q and enable lines as shown in Figure 4. With reference to Figure 3a, the calculation engine from the Euclidean distance 65 calculates the four squared Euclidean distances between each received I and Q symbol and the four possible points of the constellation QPSK. A common engine calculates the distances for each channel only when it is enabled by its respective channel.

[0039] As shown in Figure 6, the eudidea distance calculation engine 65 compares all the received symbols p per channel assigning them in a QPSK constellation xoo, xoi. xio, Xn- It is necessary to examine each received point p due to corruption during transmission 47 by noise and distortion, either multipath frequency or radio frequency. The geometry engine 65 calculates the four distances doo, doi, dw, dii from the given symbol p and chooses the shortest distance doo.

The enabling mechanism used is based on the speed of the data transmitted for a particular channel. A gain in the overall processing efficiency is obtained as the calculations are performed only on the eudide distance engine 65 if a new I and Q symbol is provided and the geometry engine 65 has been enabled correctly. Ethics increases as you do not lose any computations when data is processed at a lower speed.

ES 2 387 708 T3

Referring back to Figures 3a and 3b, after the Euclidean distances have been calculated, the separate 12-bit outputs 139a, 139b, 139c and 139d for each channel, along with the associated enable signals 143a, 141b, 141c, 141d are coupled in series to four separate SCS circuits 67a, 67b, 67c, 67d, where the Euclidean distances are mapped on an encoder-based trellis diagram. The use of a trellis diagram for decoding convolutionally encoded FEC data is well known to those familiar with the art.

[0042] The present invention normalizes all symbols and calculates the shortest trellis distance using saturation logic. Previous status indicators are added to each recently received transmitted symbol. Each individual data point per channel develops and updates the trellis diagram. The status indicator data is read from a status indicator memory 69. The SCS circuits 67a, 67b, 67c, 67d apply the Viterbi algorithm. The maximum probability decoder is based on the trellis diagram which is an infinite replica of a state diagram. Any codeword in a convolutional code corresponds to the symbols along a path on the trellis diagram. Each state and each level on the trellis involves an SCS operation. The implementation of a decoder based on the Viterbi algorithm requires a storage of two different sets of data. The first storage is for route status or status indicator memory 69 updated for each successive level of the trellis. The second set of data is the selections at each node or state in the trellis called memory for path 73.

In the prior art, each respective decoder or SCS circuit would require individual storage of the two data sets. In the present invention, both arrays of indicator memory 69 and path memory 73 are consolidated into a common memory for each channel in a novel way to significantly reduce the size of the silicon area. Also, the common transfer of data and addresses is combined further increasing efficiency. Status indicator data is written to 143a, 143b, 143c, 143d and read from 145a, 145b, 145c, 145d from status indicator memory 69.

[0044] There are two possible routes on the trellis that end in each state. A scrub operation is performed on the SCS circuits 67a, 67b, 67c, 67d, where the best flag ends up in a certain state. The best indicator is determined by choosing the smallest cumulative trellis distance. The chosen route, upper or lower, is represented by a 0 or a 1 respectively. This information is written to trace memory 73 at lines 149a, 149b, 149c, 149d.

[0045] The trellis diagram is assembled over many received symbols. The preferred embodiment requires 35 symbols at separate times and updates upon receipt of each synchronized symbol. After 35 symbols have accumulated, a determination finds the trellis path that has the smallest error. This decoding method determines which QPSK symbol has been sent. The structure of the trellis diagram introduces redundancy and accumulates the history of the route.

[0046] In Figure 7 an SCS circuit 67a for channel 0 is shown. 139a is entered for each new symbol representing a point of the QPSK constellation. Since each node in the trellis has two paths going in and out, the values ​​are divided and selected based on the current situation on the trellis and what was coded. Each constellation value is entered into separate 4-input 189u and 1891 multiplexers. The 191u, 1911 output of each 189u, 1891 multiplexer is based on the current state in the trellis diagram and the encoder. This decision 153a originates from the SCS sequencer 71, which will be explained later herein. Status flag 145a is read from memory 69 and divided similarly for both upper and lower paths and entered into duplicate 8-bit flip-flops 193u, 1931. Flip-flops 193u, 1931 go out to saturation subtractors 197u, 1971 with the old best indicator 201 and are combined with the new symbol value 191u, 1911, with saturation subtractors 199u, 1991. Both upper and lower paths of each node of the trellis diagram are compared with an 8-bit magnitude comparator 203. Each SCS channel processes 64 states of the trellis diagram for each particular symbol. Each path is examined to determine which distance or path is the shortest. Both upper and lower paths 205u, 2051 are input to a 2 input multiplexer 207 where the shortest distance or status indicator 145a is chosen and stored in memory 209. This value is used with the next symbol input for normalization . The present invention normalizes all inputs a posteriori for each operation.

[0047] Normalization in the prior art is usually done en bloc or after many information symbols have been processed. However, normalizing a posteriori after choosing each metric greatly improves performance. Post-hoc normalization requires saturation logic as the normalization process can lead to overflow. If saturation logic is not used, the number may eventually overflow and the binary number may vary greatly from the desired value. The system cannot determine if the value is realistic. By using saturation logic, the value will ultimately be the limit value.

ES 2 387 708 T3

[0048] As each node in the trellis has two paths ending at it and two paths starting from it, the process must constantly debug. The trellis diagram represents the indicators for two routes where a decision chooses a route based on the shortest distance. The best route or best indicator is stored in status indicator memory 69 and the decision or route bit is stored in trace memory 149a 149b, 149c, 149d.

[0049] At the beginning of a symbol, each SCS channel 67a, 67b, 67c, 67d will receive a start signal from decoder 141a, 141b, 141c, 141d to start the channel. As explained above, the winner of the debug operation that was stored in memory is compared to the first, if the second winner is less than the first then that particular value is chosen as the best indicator. This operation is similar for the remaining 63 outputs of the trellis diagram.

The historical dependence of the symbols as they enter a Viterbi decoder accumulates the energy of the many symbols producing a very large gain. The energy gain is based on the integration of the energy of more than 35 symbols that actually narrow the bandwidth.

The sequencing of the operation of the SCS circuits 67a, 67b, 67c, 67d is controlled by the SCS 71 sequencer through lines 151a, 151b, 151c, 151d. A single SCS 71 sequencer is used to control the individual SCS circuits 67a, 67b, 67c, 67d of each channel being decoded. When a particular channel 141a, 141b, 141c, and 141d has not been enabled, either due to a slower data rate or if the channel is empty, the write operations to flag 69 and path 73 memory for that channel in particular they are inhibited through lines 153a, 153b, 153c, 153d.

[0052] The SCS 71 sequencer controls the entire operation of the present invention. The function of the sequencer of SCS 71 is similar to a state machine. However, instead of using a programmable device and downloading executable code as is normally the case in the state of the art, the SCS 71 sequencer is executed strictly on the hardware offering an unexpected ethic.

The founding of the SCS 71 sequencer is similar to that of a counter driven by a counter and controls the four independent SCS circuits 67a, 67b, 67c, 67d in parallel with a common memory 69. The SCS 71 sequencer also works as a smaller bit modulus array processor. A flow chart for the SCS 71 sequencer is shown in Figures 8a and 8b. After initialization (step 401), the SCS sequencer 71 establishes a base count that is equal to zero (step 403). Since a sequencer is essentially a counter a return path is needed to count up (step 415). A decision (step 405) determines whether the process completes depending on the increment from 0 to 127, matching the read 64 and write 64a operations of the trellis diagram. The sequencer is synchronized at the Viterbi speed that drives addressing (steps 411, 419, 425, 429) and sequencing of addresses, and sequencing of read (steps 413, 421) and write (steps 427, 431) operations. ). The SCS sequencer 71 processes each SCS channel 67a, 67b, 67c, 67d in parallel with a common memory 69.

The status indicator memory array 69 is 64 bits wide and arranged in a ping segment and a pong segment. The first 32-bit segment is the ping and the second 32-bit segment is the 64-bit word pong. Each 8-bit segment of the 32-bit segment represents a different channel (0, 1, 2, 3). When the SCS 71 sequencer is reading from the pong segment, it will be writing to the ping segment sequentially. The sequencer will read from ping and write to pong, and with the next symbol, it will read from pong and write to ping. This shared memory access method is familiar to those familiar with this technique.

[0055] The SCS sequencer 71 handles four channels that can be processing data at different data rates in such a way that the sequencer 71 can be reading from ping for channel 0, reading from pong for channel 1 and not performing any read or write for channel 2 and read from ping for channel 3. This memory access method is extremely flexible. This is accomplished by having each channel an assigned start signal 141a, 141b, 141c, 141d.

The SCS sequencer 71 accesses the memory array of status indicators 69 and each circuit of SCS 67a, 67b, 67c, 67d, examining the base count (step 405) and observing the two least significant bits (LSB) of the base account (step 407). The first two states of the sequence are always read operands (step 413, 421). The last two states in the sequence are the write operands (step 427, 431). Write operations send results to status indicator memory 69.

[0057] As shown in Figure 9, the implementation of the SCS 71 sequencer is done with minimal hardware. The counter 211 provides the base count with the flip flops 213a, 213b, 213c, 213d, 215a, 215b, 215c, 215d, providing the change and write and read operations for the four speed channels.

ES 2 387 708 T3 variable data. A 4-input multiplexer 217 accesses the addresses of the status indicators for all channels.

The status indicator memory array 69 has sufficient storage space for 64 status indicators per channel. To facilitate (reading 145a, 145b, 145c, 145d, and writing 143a, 143b, 143c, 143d in the memory array of status indicators 69, the ping-pong arrangement for memory facilitates both operations during the individual SCS operations coordinated by the SCS sequencer 71 on the ping-pong line 155 and the address bus 157. The total capacity of the SRAM status indicator memory array 69 is 4,096 bits.

[0059] Trace memory matrix 73 is used to record which path survived in each state for each decoded symbol. Since a trellis diagram is an infinite replica of a state diagram, in theory an infinite amount of memory would be required to record all the information for each transmitted symbol. However, the trace history is only kept for 35 consecutive symbols and is overwritten from SCS circuits 67a, 67b, 67c, 67d via lines 149a, 149b, 149c, 149d. Trace memory 73 requires 8,960 bits of SRAM memory arranged in a 32 by 280 matrix. The trace has a depth of 35 symbols, therefore, prior to outputting a decoded symbol there has been an accumulation of 35 symbols of information. The input symbol that produces a given output occurred 35 symbols earlier in time.

The trace memory 73 is arranged as a circular buffer. Each time a new symbol is written to trace memory 73, all previously stored symbols are shifted, discarding the oldest symbol value. The memory required is based on the 5 times rule (at constraint length, so 35 symbols of memory are required for a constraint length K = 7.

[0061] The scan operation is shown in Figure 10. The scan processor 75 is a recurring operation similar to the SCS processor 71 in which a counter is initialized (step 501) and a value of allocation 35 as discussed above (5 times the restriction length). The best indicator value is then assigned (step 505) to the best local indicator. A decision must be made if the tracking count equals 0 (step 507). If the scan count equals 0, the process is complete (step 531) and the path that was most likely is known and the decoder generates a bit (step 529). If the trace count is not 0, the operation is performed again to reach the best indicator.

As four different data rates can be processed, the trace memory 73 is correspondingly consumed, that is, if channel 0 is running at 64 kbps, after 35 symbols on channel 0 the trace memory would fill to that particular channel, however, if channel 2 is running at half speed, that is, 32 kbps, channel 2 would only fill to half the scan memory 73.

[0063] Trace memory 73 is allocated sequentially since one channel may be far behind in relation to another channel. The scan process 75 is unique for each channel as the data that was encoded at the transmitter is unique. Therefore, the scan operation for each of the four channels will be unique. Also, the data rates between the four channels may be different.

[0064] The scanning process is serial and processor 75 operates sequentially for channel 0, then channel 1, then channel 2, and finally channel 3 since the addresses are not common. The storage of trace information is direction dependent and requires segregation of each process for each channel over time. If all four channels are transmitted at full speed, the memory would still require segregation as the data that was encoded at the transmitter created a different pattern or tracking path between each of the four channels. Processing them at different data rates further complicates the process.

Referring to the flowchart in Figure 10, if the trace count is not equal to 0 (step 507) the process must follow the trace through time of the path that is most likely. The processor reads the 9-bit address that includes a field, a byte address, and a bit address. This is done by shifting 4 bits (to the right direction (step 509), then shifting it 1 bit to the right (step 511) and masking (the 3 least significant steaks (step 513)). The best focal indicator is a 7-bit number. The 4 most significant bits will become the byte address, the next 3 bits will become the bit number, and the 4 least significant bits will be ignored. The path bit is examined (step 515) for see if it's a 1 or a 0. If the path bit is 0, the value of the previous best local indicator is shifted to the right by 1 which effectively divides it by 2. If the path bit is equal to 0, the best local indicator is shifted to the right at 1 (step 517). If the path bit is not equal to 0, 64 is added to the best local indicator thus putting the result between a value of 32 and 63. Processor 75 keeps track (steps 521, 523, 525, 527) of all paths and repeats until the coded bit is found.

ES 2 387 708 T3

[0066] The processor finds the path that ends in the 64 states with the minimum energy indicating the minimum error. The trace memory stores the 35 paths associated with the 64 states with one bit indicating whether the path comes from above or below since there are only two paths in a given state. Therefore, a 0 or 1 indicates the way. The associated bit path for the best local indicator is stored together with the byte address and the bit address. Since all information is stored in bytes, a decomposition is performed, since there are 64 states, with 8 bytes, with 8 bits per byte. Since there are 8 bits in the first byte, the 8 bits would indicate states 0 to 7. This indicates that the best local indicator is pointing to these states. The next byte would be for states 8 to 15 and so on until the 63rd state.

[0067] The process always discards the least significant bit of the 7-bit number. The 3 most significant bits, as explained above, point to a particular byte address. The next 3 bits of the 3 most significant bits point to a particular bit in the byte address. That is, the path bit. The path bit is used to modify the best local flag.

[0068] The scan process runs 512 times faster than the maximum throughput speed. The control of the address bus is coordinated between the SCS sequencer 71 and the tracking processor 75. During the SCS phase of the decoder founding, the SCS sequencer controls through lines 151a, 151b, 151c, 151d the bus. address 159, both the status indicator and the trace memories. Upon completion of the SCS operation, control of the trace memory address bus is passed to trace processor 75.

Trace memory 73 is used in a procedure called backtracking or tracing from the last node in the trellis, tracing the dedsion path back from the last dedition to the first. This process determines the decoded symbol to be released as an output 161a, 161b, 161c, 161d- The scanning process for the four channels cannot be performed in parallel within a common SRAM 69, 75 block as the characteristics are expected tracking process routing for separate data channels are independent. The scanning process needs to be sequenced for each individual channel. If a particular channel was not enabled for a particular symbol interval, the scan process for that channel is skipped. The process requires a minimum of 35 clock acids to perform the scanning process for a given channel.

[0070] The present invention also has a performance diagnostic feature that calculates the bit error ratio. Eudide distance engine 55 outputs a hardware definition 163 to trace processor 75. The hardware definition is stored in a 35-symbol first-in-first-out (FIFO) buffer and then compared to the output. of the reconvolutionally encoded symbol 161a, 161b, 161c, 161d, which released the trace processor 75. The bit differences between the two accumulate. After 256 symbols, the accumulator in trace processor 75 empties 165 into a 77 bit error ratio output circuit shown in Figure 7. When a new 8-bit accumulated bit error ratio value ready for the main microprocessor to read, the BER ready signal 167 is enabled for that particular channel.

[0071] As shown in the flow chart in Figure 11, the diagnostic process of the bit error ratio is described. For the calculation of the bit error ratio, the process requires a transmitter portion and a receiver portion. The data will be input (step 601) to the transmitter and subjected to direct error correction coding, QPSK modulation, and quadrature signal expansion. The signal will not undergo transmission but will be inserted directly into the receiver area where the signal will be de-spread. The output of the de-spreading process goes directly to the Viterbi decoder (step 603) and will be delayed for 35 symbols (steps 607, 609, 611) in order to allow the Viterbi decoder to decode the information (step 605). The data that was subjected to the hardware decision (not decoded) will be compared to the output of the Viterbi decoder. This provides an indication of the behavior of the SNR and the processor.

[0072] The performance of the present invention is shown in Figure 12. Figure 12 shows a probability diagram of the bit error ratio with respect to the signal-to-noise ratio comparing non-convolutionally encoded data with encoded data . Two ways of realization of the invention are shown. The first embodiment uses a constraint length of K = 7. An alternative embodiment uses a constraint length of K = 9. As can be seen from the graph, when the signal-to-noise ratio increases to 5, the behavior of the non-convolutionally encoded data exhibits a bit error probability of 0.05%. However, for the same signal-to-noise ratio, convolutely coded data exhibits a drastic performance increase up from one bit error in one million. The graph also shows an improvement over the restriction length of 7 when using an alternative embodiment employing a restriction length of 9.

Instead of assembling a quadruple Viterbi decoder having four input channels, each having two pairs of I and Q signals, a distance calculation engine is used to produce four channels and 10

ES 2 387 708 T3 emit 16 distances. The 16 distances are then coupled to the SCS blocks. The outputs of the Euclidean distance calculation block are then distributed per individual SCS block channel by channel.

[0074] In an alternative embodiment, instead of having four separate SCS blocks for each individual channel, a drastic reduction could be formed with a linear increase in clock speed. The SCS feature incorporating trellis operation can be reduced to two or even one SCS circuit by multiplexing the input data along with increasing the clock speed.

[0075] Although specific embodiments of the present invention have been shown and described, one skilled in the art could make many modifications and variations without departing from the scope of the invention, as defined in the claims.