Multichannel viterbi decoder
Abstract
A decoder for simultaneously decoding a plurality of encoded data signals received in a convoluted manner, at least two of the encoded signals having a different data rate, the decoder comprising: - a Euclidean Distance Calculation Circuit that has an input configured to receive the non-decoded I and Q symbols of the plurality of encoded data signals and emitting Euclidean distances corresponding to each encoded signal based in part by the received I and Q symbols ; for each data signal, a Sum-Comparison-Selection circuit that has an input configured to receive these Euclidean distances from the channel and arranging these data signal distances on a grid; and - a tracking process circuit to follow the decisions in each data signal reticule to issue the decoding symbols of each data signal.

Term
Term ended
Projected expiry passed 4 March 2018, 8.6 years ago.
- Priority
- Filed
- Published
- Projected expiry
- Today
19 claims: 2 independent, 17 dependent
- 1ES 2 172 486 T3 REIVINDICACIONES 1. Un descodificador para descodificar una pluralidad de señales de datos codificadas recibidas convolucionalmente, cuyo descodificador comprende:medios (65) para recibir símbolos I y Q descodificados de la pluralidad de señales de datos codificadas y que entregan como salidas distancias euclidianas correspondientes a cada señal codificada;caracterizándose el descodificador por: al menos dos de las señales codificadas de datos que tienen una velocidad diferente de transmisión de datos;medios (67 a, 67b, 67c, 67d, 71) para representar las correspondencias de cada una de las distancias de señal de datos en un diagrama trellis;medios (75) para retrolocalizar decisiones en cada diagrama trellis de señal de datos para entregar como salida símbolos descodificados de cada señal de datos usando una memoria común (69);y la memoria común (69) que tiene una memoria de estado de camino y una memoria de valores métricos de estado.
- 2El descodificador de la reivindicación 1, en el que los medios (65) para entregar como salidas distancias euclidianas comprenden un circuito de cálculo de distancias euclidianas;los medios (67 a, 67b, 67c, 71) de representación de correspondencias comprenden una pluralidad de circuitos de suma-comparación-selección;y los medios (75) de retrolocalización comprenden un circuito de proceso de retrolocalización.
- 3El descodificador de la reivindicación 2, en el que cada una de las decisiones de diagrama trellis de señal se basa en un algoritmo de Viterbi.
- 4El descodificador de la reivindicación 2, en el que el circuito de cálculo de distancia euclidiana procesa solamente los símbolos no codificados recibidos I y Q cuando los símbolos no codificados recibidos I y Q se liberan al circuito de cálculo de distancia euclidiana.
- 5El descodificador de la reivindicación 2, en el que la pluralidad de señales codificadas de datos son cuatro.
- 6El descodificador de la reivindicación 5, el que el descodificador es capaz de procesar las señales codificadas de datos que tiene velocidades de transmisión de datos de 64 Kb/s, 32Kb/s, 16 Kb/s y 8 Kb/s.
- 7El descodificador de la reivindicación 1, en el que los medios de representación de correspondencias (67 a, 67b, 67c, 67d, 71) comprenden un circuito (67 a, 67b, 67c, 67d) de suma-comparación-selección, para cada señal de datos.
- 8El descodificador de la reivindicación 1, en el que los medios de representación de correspondencias (67 a, 67b, 67c, 67d, 71) comprenden un circuito (71) de suma-comparación-selección para representar correspondencias de cada señal de datos sobre una base multiplexada de tiempo.
- 9El descodificador de la reivindicación 8, en el que el un circuito (71) de suma-comparación-selección está sincronizado a una velocidad de transmisión mayor que los medios (65) que entregan como salidas distancias euclidianas.
- 10El descodificador de la reivindicación 1, en el que las decisiones trellis de cada señal se basan en un algoritmo de Viterbi.
- 11El descodificador de la reivindicación 1, en el que los medios (65) que entregan como salidas distancias euclidianas procesan solamente los símbolos no codificados recibidos I y Q cuando los símbolos no codificados recibidos I y Q se liberan al circuito de cálculo de distancias euclidianas.
- 12El descodificador de la reivindicación 1, en el que la memoria común (69) está dividida en una pluralidad de secuencias, teniendo cada secuencia un segmento “ping” y un segmento “pong”, cada uno de cuyos segmentos “ping” y “pong” comprenden bits asociados con cada señal de datos, en la que para cada segmento, cuando se lee el “ping”, se escribe el “pong”, y cuando se lee el “pong”, se escribe el “ping”.
- 13El descodificador de la reivindicación 12, en el que cada secuencia es de 64 bits, y cada segmento “ping” y cada segmento “pong” son de 32 bits.
- 14El descodificador de la reivindicación 13, en el que cada segmento “ping” y cada segmento “pong” tienen 8 bits asociados con cada una de las cuatro señales de datos.
- 15El descodificador de la reivindicación 1, que comprende además una memoria de retrolocalización (75) para almacenar datos de retrolocalización asociados con cada señal codificada de datos. ES 2 172 486 T3
- 16Un método para descodificar una pluralidad de señales de datos codificadas recibidas convolucionalmente, cuyo método comprende:recibir símbolos no codificados I y Q de la pluralidad de señales codificadas de datos, cuyo método se caracteriza por: al menos dos de las señales codificadas de datos tienen una velocidad diferente de transmisión de datos;procesar los símbolos no codificados I y Q para entregar como salidas distancias euclidianas correspondientes a cada señal codificada;representar correspondencias de distancias de cada señal de datos en un diagrama trellis;y retrolocalizar decisiones en cada diagrama trellis de señal de datos para entregar como salidas símbolos descodificados de cada señal de datos usando una memoria común, cuya memoria común (69) tiene una memoria de estado de camino y una memoria de valor métrico de estado.
- 17El método de la reivindicación 16, en el que las decisiones de diagrama de trellis de cada señal se basan en un algoritmo de Viterbi.
- 18El método de la reivindicación 16, que comprende además:liberar los símbolos recibidos no codificados I y Q;en el que el proceso de los símbolos recibidos no codificados I y Q se realiza únicamente cuando se han liberado los símbolos recibidos no codificados I y Q.
- 19El método de la reivindicación 16, en el que la pluralidad de señales codificadas de datos son cuatro.
Independent claims19
106 paragraphs in 6 sections, as filed
IS 2 172 486 T3
DESCRIPTION
Multi-channel Viterbi decoder. Background of the invention
Invention field
The present invention relates generally to digital communications. More specifically, the invention relates to a system in which data is transmitted at a variable rate of transmission and received at a communications receiver where the data of variable rate of transmission is decoded in an efficient multi-channel multi-rate data decoder. of transmission.
Description of the prior art
Today's most advanced telecommunications technology makes use of spread spectrum modulation or code division multiple access (hereinafter CDMA) for point-to-multipoint telecommunications. Since the 1950s, CDMA has been used in military applications, due to the difficulty of detecting and disturbing 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.
A simplified CDMA communication scheme is shown in Figure 1. A single communication channel of a given bandwidth is mixed with an extension code. The relatively narrow band modulated signal is sequentially scaled up to occupy a much wider transmitted bandwidth by multiplying with a single scaling code. The spreading code comprises a noise-like high-speed pseudo-random sequence or code, which becomes part of the transmitted data. The low-level noise-like appearance of the resulting transmitted signal is such that it is not likely to interfere with other users of the spectrum.
At the receiver, the signal is reduced by correlating the received broadband signal with an identical locally generated pseudo-random sequence to resolve the data from a plurality of data signals occupying the same transmission bandwidth. This sharply decreases the signal back to its original bandwidth, and also amplifies any narrow-band radio signals present in the occupied spectrum, so that they now appear as noise entering the receiver. By utilizing many different pseudo-random sequences of code, multiple users can be accommodated within the same transmission spectrum.
The same characteristics that have allowed CDMA communication techniques to be successful in military applications have made CDMA communication systems mandatory, particularly B-CDMA systems.<sup>R</sup> Multiple access system with broadband code division for efficient use of the crowded frequency spectrum of commercial radio. Among the many attributes of the CDMA system is its virtually unlimited capacity. Since each user of a CDMA communication system transmits and receives signals over the same transmission bandwidth, there are less stringent channeling and protection band requirements. Unlike FDMA and TDMA systems, whose capacity is limited by the number of discrete channels, the capacity of CDMA systems is limited by interference. Consequently, the number of users capable of communicating simultaneously over that determined transmission bandwidth significantly increases.
In addition to voice information, non-voice information, alone or a combination of the two, can be transmitted to the receiver. Certain communication standards such as Integrated Services Digital Network (hereinafter ISDN) require a much higher data transmission speed than digitized voice. To optimize the communication system, various data rates are transmitted in order to increase the signal-to-noise ratio (hereinafter SNR) to all receivers.
A measure of spread spectrum behavior is the system processing gain, Gp, which is determined by the ratio of the channel bit rate to the information bit rate, Rc / Ri. The signal / noise ratios between the input and the output are determined by:
- = Gp * Í-S1
No \ No / j (Equation 1)
From equation 1 it follows that the higher the data transmission rate, the more interference will occur, which will deteriorate the signal-to-noise ratio. Reduced interference translates directly into increased capacity.
Most CDMA telecommunications systems transmit variable rate data to keep SNR at the highest possible value. To achieve this, either the data transmission rate is identified within the system level control message that is part of the signal channel, or a particular receiver must be able to detect the speed of the transmitted data.
IS 2 172 486 T3
Since there are many users sharing this same spectral transmission channel, interference from one user to another can be induced when there is not enough code isolation between the users. Furthermore, the data transmission rate must be known before convolutional decoding of the error correction at the transmitter or receiver.
Most prior art receivers make use of independent single rate convolution decoders to properly reconstruct the digital data once received and reduced. Since 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, thereby decreasing the complexity of the receiver and increasing the transmission rate. overall system speed. However, the use of dedicated convolutional decoders for each transmitted data rate reduces the overall throughput of the process and increases system costs.
WO-A-95-08888 describes a Viterbi decoder for processing a data stream having an unknown data rate. The decoder simultaneously decodes the data stream at multiple data rates. A processor determines which decoded data rate is the correct data rate.
EP-A-0 712 219 describes a solution for determining a preferred data transmission rate of a channel. Data is transmitted over the channel at four data rates. Four Viterbi decoders decode each data transmission rate. The errors in each received data rate signal are determined, and an optimal data rate is selected for the channel.
The present invention relates to a communication system in which the data rate of a given transmission is encoded by a transmitter and then used to set a plurality of convolutional decoders that share a common memory. The system uses common processing resources to provide up to four discrete channels that have multi-rate convolutional decoding with error correction, resulting in less silicon area and low power operation. The system is capable of supporting voice communication at 8 kb / s up to 64 kb / s for high speed ISDN communication. Although the present invention can be used in a variety of communication systems, preferred communication systems include cellular or portable telephones, PCS, wireless local loop communication, and CDMA communication. The present invention can be used in both base station and consumer unit site receivers.
Accordingly, an object of the present invention is to provide an efficient multi-rate convolutional decoder for multi-channel applications.
A further object of the invention is to provide a lower complexity and better performance multi-channel convolutional decoder architecture.
Other objects and advantages of the system and method will become apparent to those skilled in the art upon reading the detailed description of the preferred embodiment.
Summary of the invention
The present invention provides a decoder for decoding a plurality of convolutionally encoded signals according to claim 1, and a method of decoding according to claim 16. Further preferred aspects are provided according to the dependent claims.
Accordingly, an object of the present invention is to provide an efficient multi-rate convolutional decoder for multi-channel applications.
The further object of the invention is to provide a lower complexity and better performance multichannel convolutional decoder architecture.
Other objects and advantages of the system and method will become apparent to those skilled in the art upon reading the detailed description of the preferred embodiment.
Brief description of the drawings
Figure 1 is a block diagram of a typical prior art CDMA communication system.
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.
IS 2 172 486 T3
Figure 4 is an overall block diagram of the preferred embodiment.
Figure 5 is a block diagram of the interface between a central digital signal processor and the preferred embodiment.
Figure 6 is a diagram of the manipulation constellation for phase-quadrature shift (hereinafter QPSK).
Figure 7 is a detailed block diagram of a "sum-compare-select" channel.
Figure 8a is the first section of a "sum-compare-select" sequencer flow chart.
Figure 8b is the second section of a "sum-compare-select" sequencer flow chart.
Figure 9 is a detailed block diagram of the "sum-compare-select" sequencer.
FIG. 10 is a flow chart of the back-location procedure.
Fig. 11 is a flow chart of the bit error transmission rate process.
Figure 12 is a graphical representation of the behavior of the bit error transmission rate (hereinafter BER) as a function of the signal-to-noise ratio.
Detailed description of the preferred embodiment
The present invention is described with reference to the figures of the drawings, in which like numerals represent like elements in their entirety.
The multi-rate multi-channel Viterbi decoder constructed in accordance with the present invention has been made within the context of a CDMA 17 cell phone system. Such decoders are used in multi-channel wireless communication stations with the reception of communication signals. The system (17) as shown in Figure 2 includes a transmitter (19) and a receiver (21), which can be installed in either a base station receiver or a mobile user receiver.
The transmitter (19) includes a signal processor (23) that encodes voice and non-voice data (25) into frames of various data rates, for example, frames of rates of 8 kb / s, 16 kb / s , 32 kb / s or 64 kb / s. Signal processor 23 selects a transmission rate that depends on the amount of voice activity, whether the data is voice, 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) that can be considered as a biphasic modulated signal is encoded using "direct error correction" (FEC) encoding (27). Since a convolution code R = 1/2 is used, the single modulated biphasic data signal is converted to two modulated biphasic signals. A signal is designated as the in-phase signal channel I. The other signal is designated as the Q quadrature signal channel. The set of the two modulated biphasic signals I and Q is usually referred to as "keying for shift from phase signal to quadrature signal" (QPSK). In the preferred embodiment, the tap generator polynomials (29, 31) for a restricted length of K = 7 and a convolutional code rate of R = 1/2 are:
G1 = 1718 and G2 = 1338
In the second stage, the two modulated biphasic data or symbols (33a, 33b) are extended with the QPSK pseudo-random sequences in phase (35a) (I) and quadrature (Q) (35b). The resulting expanded signals I (37a) and Q (37b) are mixed with a carrier frequency (43), combined at (45) with other expanded signals (channels) having different expansion codes, and transmitted at (47 ). Transmission 47 may contain a plurality of individual channels having different data rates.
The receiver (21) includes a demodulator (49a, 49b) that mixes the broadband transmitted signal (47) into an intermediate carrier frequency (51a, 51b). The QPSK signals are then filtered (53) and mixed (55a, 55b) with the locally generated pseudo-random code (35a, 35b), which is adapted to the transmitted code. Only the original waveforms that were expanded by the same code at the transmitter (19) will be effectively reduced. The other signals will appear as noise to 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-channel Viterbi decoder (61) of various transmission rates, as shown in Figures (3a) and (3b). The decoder (61) comprises a digital signal processor (hereinafter DSP) that enters the Viterbi decoder interface (63), a common Euclidean distance calculator (65), a plurality of channels (67a, 67b, 67c) and (67d) (ACS) sum-compareselect, a pool (69) of state metric memories, an ACS 71 sequencer, a pool
ES 2 172 486 T3 (73) of backhaul memories, a backhaul processor (75) and a decoder to the system interface (77). The system as shown in Figures (3a) and (3b) can be assembled discretely, or realized as an efficient application-specific integrated circuit (hereinafter ASIC) (79).
In the preferred embodiment, any one of the four channels (0,1,2 and 3) of the decoder (61) can process a plurality of data transmission rates: 8 kb / s, 16 kb / s, 32 kb / s or 64 kb / s. In alternative embodiments other data rates may be used. Lower value data rates are achieved by enabling a multiplying factor diversities combiner function that works on redundantly received symbols. This effectively increases the SNR of the received multiplying factor diversity signals. For those symbols in frames corresponding to data rates less than the maximum expected data rate, the symbol data is repeated to maintain a constant symbol rate for the frame.
For the 64 kb / s data rate, a QPSK symbol is sent every 15.625 μδ. For the data rate of 32 kb / s, the corresponding QPSK symbol is sent twice over one channel. The symbols are still sent at the data rate of 64 kb / s, but with double redundancy, thereby effectively reducing the information transmission rate to 32 kb / s. For a data rate of 16 kb / s, the corresponding QPSK symbols are sent through the channel with diversity of a multiplication factor equal to 4. For an 8 kb / s data channel, a diversity with a multiplication factor equal to 8.
Referring to Figures (3a) and (3b), the multi-channel decoder (61) shares common resources to minimize silicon area. As shown in the figures, the state metric memory (69) and the back-location memory (73) are static random access (hereinafter SRAM) and are commonly used for each channel. Performance is further increased with the common Euclidean distance geometry calculator (65), which calculates the square of the Euclidean distance between the received QPSK symbol and the four possible constellation points in the QPSK space for the four channels.
The system architecture as shown in the figures implements the Viterbi algorithm and decodes the convolutionally encoded data. The shunt generator polynomials that correspond for a restricted length of K = 7 and a code rate of R = 1/2 are G1 = 1718 (29) and G2 = 1338 (31). It should be understood that other shunt generator polynomials may be used in alternative embodiments, depending on different restricted lengths and baud rate codes. For example, for a constrained length of K = 9 and a code rate of R = 1/2, the shunt generator polynomials are G1 = 7538 and G2 = 5618. The use of bypass generators is well known to telecommunications experts, and they are employed in the FEC 27 encoder.
A global architecture of the system is shown in Figure 4. A central microcontroller (81) programs a control and timing module (83) (hereinafter TCM) located in the ASIC (79) by means of microcontroller data lines (85), access lines (87) and dial 89 of writing. The microcontroller (81) determines, from the transmitted frame, the multiplying factor diversity factor for a given channel. Diversity pooling is controlled by selectively asserting and denying the pooling pool signals 91a, 91b, 91c, and 91d for channels 0 through 3 respectively. A data output (93) exits a central DSP (95) and carries the I and Q signals for the four channels to the Viterbi decoder interface (63). The central DSP (95) that drives the signal (97) and the access lines (99) is also coupled to the Viterbi decoder interface (63). The central microcontroller (81) controls each signal 91a, (91b), (91c) and (91d) of combination of diversities. The central DSP (95) controls the individual channel data (93) entering the decoder interface (63).
The TCM (83) accepts an externally derived high frequency reference signal (103) for overall system timing. TCM 83 uses reference signal 103 and derives high frequency dump signals 105 and Viterbi clock 107. The TCM (83) also produces a global reset (109) of the decoder.
The data transmission speed of a particular channel is decreased by the microcontroller (81) which activates the respective diversities combiner signal (91a), (91b), (91c) and (91d). For a data rate of (32) kb / s, two adjacent symbols are combined; for a data rate of 16 kb / s, four symbols are combined, and for one of 8 kb / s, eight symbols are combined.
The preferred embodiment uses the diversity of multiplication factors to process the multi-rate data. At a data rate of 64 kb / s each individual bit transmitted is used. However, at the minimum data rate, 8 kb / s, each bit is doubled by a factor of 8. When processed at the lowest data rate, the redundant symbols are simply added together. As stated in the background of the invention, each time a symbol is sent through a respective channel a certain gain and noise figure are received. Therefore, if the same signal is sent through the channel twice, the signal-to-noise ratio (SNR) has effectively doubled. The reason is that redundant symbols add coherently, while the random noise introduced does not add coherently. From the maximum data rate of 64 kb / s to the minimum of 8 kb / s the signal gain is effectively multiplied by a factor of 8.
IS 2 172 486 T3
By lowering the data bit rate and using the diversity of multiplication factors, the signal transmission power can be lowered commensurately, since the gain will be recovered when the various symbols are assembled. With the use of the combination of diversities, lower data transmission speeds are achieved without suffering detrimental effects for lower signal-to-noise ratios.
For the maximum data output of 64 kb / s, the diversity combination function must be deactivated, which is done by keeping the diversity combining signals (91a), (91b), (91c) and (91d) high for that particular channel. When the multichannel decoder (61) operates at low data rates, the diversity combiner signals (91a), (91b), (91c) and (91d) control which adjacent symbols are combined, when the decoder is activated, and when the interface is released for a new set of symbols.
As shown in Figure 5, the decoder interface (63) accepts two 8-bit I and Q compliance samples on the data bus (93) of the central DSP (95). The data from the central DSP (95) is fed into the data bus 93 to a gate decoder. The data bus (93) is a parallel input bus, but data arrives sequentially between the four channels. The data is then separated into the individual in-phase signal and quadrature signal components for each channel, and output to each drain and saturation integration circuit (113I), (113Q), (115I), (115Q) , (117I), (117Q), (119I) and (119Q) on lines (121I), (121Q), (123I), (123Q), (125I), (125Q), (127I), and (127Q ), for channels 0 to 3 respectively. Interface 63 includes 8-bit accumulators that have saturation logic. The maximum positive saturation value is 0x7f16, and the maximum negative saturation value is 0x8016.
In the Viterbi decoder interface (63), the combination of multiplying factor diversities is performed using two fulfillment binary operations. All redundant I and Q samples add up when operating at the lowest data rates. Similarly, saturation adders are used to eliminate sign change if overcapacity occurs. Instead of the diversities combining function residing in a separate integrated circuit from the DSP, the "to customer specification" feature has been included in the ASIC. Once the diversities combining function has been performed, the results are entered as outputs on lines (129I), (129Q), (131I), (131Q), (133I), (133Q), (135I), and ( 135Q) for channels 0 to 3 respectively. The dump and saturation integration circuits also control the trigger lines 137a, 137b, 137c and 137d of the Euclidean distance calculator 65 for channels 0 to 3 respectively.
Referring again to Figures 3a and 3b, all internal processors of the multi-channel decoder (61) are synchronized with the Viterbi clock (107). The central DSP (95) is synchronized by its own asynchronous clock (not shown). The DSP clock and the dump signal (105) are resynchronized with respect to the Viterbi clock (107). The decoder (61) requires that the Viterbi clock (107) should be marginally faster than the flush signal (105).
All channels are coupled from the decoder interface (63) to the Euclidean distance calculator (65) on individual I and Q lines and individual trigger lines, as shown in Figure 4. Referring to Figure 3a, the Euclidean Distance Calculator (65) calculates the four squares of the Euclidean distances between each received symbol I and Q and the four possible QPSK constellation points. A common calculator calculates the distances for each channel only when activated by their respective channels.
As shown in Figure 6, the Euclidean distance calculator (65) compares all the received symbols p per channel representing their correspondences in a constellation x00, x01, x10 and x11. 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 geometric calculator 65 calculates the four distances d00, d01, d10 and d11 from the received symbol p and chooses the minimum distance d00.
The trigger mechanism used is based on the transmission speed of the data transmitted for a particular channel. A gain is obtained in the total performance of the process, since the calculations are carried out in the Euclidean distance calculator (65) only if a new I and Q symbol has been given and the aforementioned calculator (65) has been properly activated. Performance is increased as no computation is thrown away when processing data at the lower transmission rates.
Referring again to Figures 3a and 3b, once the Euclidean distances have been calculated, the 12-bit discrete outputs (139a), (139b), (139c) and (139d) for each channel along with the associated trigger signals (141a) , (141b), (141c) and (141d) are coupled in series to four discrete ACS circuits (67a), (67b), (67c) and (67d), where the correspondences of the Euclidean distances are represented in a Trellis diagram based on the encoder. The use of a Trellis scheme to decode convolutionally encoded FEC data is well known to those of ordinary skill in the art.
The present invention normalizes each symbol and calculates the minimum trellis distance using saturation logic. For each recently received transmitted symbol the previous status metric data is appended. Each individual data point per channel develops and updates the trellis diagram. The status metric data is read from the status metric memory 69. The ACS circuits 67a, 67b, 67c and 67d implement the Viterbi algorithm. The maximum probability decoder is based on the trellis diagram, which
ES 2 172 486 T3 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. An ACS operation is involved in each state and at each level of the trellis. The implementation of a decoder based on the Viterbi algorithm requires the storage of two different data sets. The first storage is for trail status memory 69 or updated metric memory for each successive level of the trellis. The second set of data is the selections of each node or state in the trellis diagram, called memory (73) path.
In the prior art, each respective decoder or ACS circuit would require individual storage for the two data sets. In the present invention, both the metric memory pool (69) and the path memory pool (73) are consolidated into a common memory for each channel in an original way, in order to significantly reduce the size of the memory area. silicon. Also, the common transmission of accesses and data is further combined, increasing performance. The state metric data is written to (143a), (143b), (143c) and (143d), and read from the state metric value memory (69) at (145a), (145b), ( 145c) and (145d).
There are two possible Trellis paths that end in each state. In the ACS circuits 67a, 67b, 67c and 67d a debugging operation is performed, where the best metric value ends up in a given state. The best metric value is determined by choosing the minimum cumulative trellis distance. The chosen path, upper or lower, is represented by 0 or 1, respectively. This information is written to the backhaul memory (73) on lines (149a), (149b), (149c) and (149d).
The trellis diagram is assembled over many received symbols. The preferred embodiment requires 35 symbols in discrete time, and is updated upon receipt of each synchronized symbol. After 35 symbols have been accumulated, a determination finds the Trellis path that has the least error. This decoding method determines which QPSK symbol has been transmitted. The Trellis structure introduces redundancy and accumulates the previous history.
An ACS circuit (67a) for channel 0 is shown in Figure 7. Each new symbol representing a QPSK constellation point is the input (139a). Since each node in the trellis has two paths that enter and exit, the values are split and selected based on the current state in the trellis and what has been coded. Each constellation value is input into separate 4-input multiplexers (189u, 1891). The output (191u, 1911) of each multiplexer (189u, 1891) is based on the present state on the trellis diagram and on the encoder. This decision (153a) originates from the ACS sequencer (71) described later herein. The state metric value 145a is read from memory 69, similarly split for the upper and lower paths, and input to the 8-bit specular flip-flops (193u and 1931). The outputs of the flip-flops (193u and 1931) go into the saturation subtractors (197u and 1971) with the old best metric value (201), and are combined with the new symbol value (191u and 1911) with the subtractors saturation (199u and 1991). Both the upper and lower paths of each trellis node are compared with an 8-bit magnitude comparator 203. Each ACS channel processes 64 trellis states for each particular symbol. Each path is examined to determine which distance or path is the shortest. Both upper and lower paths (205u) and (2051) are entered as inputs in a 2-input multiplexer (207), in which the minimum distance or state metric value (145a) is chosen and stored in memory (209 ). This value is used for normalization with the next symbol entry. In the present invention, all inputs are post-normalized for each operation.
In the prior art, normalization was typically performed on a block basis or after many information symbols had been processed. However, by ex post normalization after each state metric value is chosen, performance is markedly improved. This post-normalization requires saturation logic, since the normalization process can lead to excess capacity. If such logic is not used, the number could overflow at the end and the binary number could vary drastically from the desired value. The system cannot determine if the value is realistic. Using saturation logic, the value last corresponds to a flattening point.
Because each node in the trellis has two paths that end at it and two paths that originate from it, the process is constantly debugging. The trellis diagram represents the metric values for two paths, in which a decision chooses a path that is based on the shorter distance. The best path or the best metric value is stored in the status metric value memory (69), and the path or decision bit is stored in the backhaul memory (149a, 149b, 149c) and (149d).
At the start of a symbol, each ACS channel (67a, 67b, 67c) and (67d) will receive a decoder start signal (141a, 141b, 141c) and (141d) to initialize the channel. As described above, the winning value from the purge operation that was stored in memory is matched against the first; if the second winning value is less than the first, then that particular value is chosen as the best metric value. This operation is similar for the remaining 63 outputs of the trellis diagram.
The historical dependence of symbols as they enter a Viterbi decoder accumulates energy from the many symbols resulting in a very high gain. The energy gain is based on the integration of the energy of more than 35 symbols, which in effect narrows the bandwidth.
IS 2 172 486 T3
The sequencing of the operation of the ACS circuits (67a, 67b, 67c) and (67d) is controlled by the ACS sequencer (71) on lines (151a, 151b, 151c) and (151d). A single ACS sequencer (71) is used to control individual ACS circuits (67a, 67b, 67c) and (67d) for each channel that is decoded. When a particular channel has not been activated (141a, 141b, 141c) and (141d), either due to a lower data rate or if the channel is vacant, the write operations to the metric memories 69 and on path 73 for that particular channel are inhibited via lines (153a, 153b, 153c) and (153d).
The ACS sequencer (71) controls the entire operation of the present invention. Its function is similar to that of a state team. However, instead of using a programmable device and download executable code normally seen in the prior art, the ACS (71) sequencer runs strictly on hardware, resulting in unexpected performance.
The operation of the ACS sequencer (71) is similar to that of a counter driven by a meter, and controls the four independent ACS circuits (67a), (67b, 67c) and (67d) in parallel with a common memory (69). The ACS sequencer (71) also functions as a bit slice cluster processor. A flow chart for the ACS sequencer (71) is shown in Figures (8a) and (8b). After initialization (step 401), the ACS sequencer (71) establishes a base count that is equal to zero (step 403). Since a sequencer is essentially a counter, a return path is required to count (step 415). A decision (step 405) determines if the process has been completed depending on the increment from 0 to 127, contrasting the 64 read operations and the 64 write operations of the trellis diagrams. The sequencer is synchronized at the Viterbi speed that drives the access (steps 411, 419, 425 and 429) and sequencing of the accesses, and the sequencing of the read (steps 413 and 421) and write (steps 427 and 431) operations. . The ACS sequencer (71) processes each ACS channel (67a, 67b, 67c) and (67d) in parallel with a common memory (69).
The status metric memory pool (69) is 64 bits wide and arranged in a "ping" segment and a "pong" segment. The first 32 bits of the 64-bit word are the “ping” segment and the second 32 bits are the “pong” segment. Each of the 8-bit segments of the 32-bit segment represents a different channel (0,1,2 and 3). When the ACS sequencer (71) is reading from the “pong” segment, it is writing in sequence to the “ping” segment. The sequencer reads from "ping" and writes to "pong", and, with the next symbol, reads from "pong" and writes to "ping". This method of shared memory access is known to those of skill in the art.
The ACS sequencer (71) manipulates four channels that may be processing data at different data transmission rates, in such a way that said sequencer 71 may be reading from "ping" for channel 0, reading from "pong" for channel 1, without doing any reading or writing for channel 2, and reading from the “ping” for channel 3. This memory access method is extremely flexible, which is achieved because each channel has an assigned start signal (141a, 141b, 141c) and (141d).
The ACS sequencer (71) accesses the state metric memory pool (69) and each ACS circuit (67a, 67b, 67c) and (67d) examining the base count (step 405) and observing the two least significant bits (hereinafter LSB) of the base count (step 407). The first two states of the sequence are always read operations (steps 413 and 421), and the last two states of the sequence are write operations (steps 427 and 431). The write operations send the results to the memory (69) of state metric values.
As shown in Figure 9, the implementation of the ACS sequencer (71) is done with minimal hardware. The counter (211) provides the base count with the flip-flops (213a, 213b, 213c, 213d, 215a, 215b, 215c) and (215d) that provide the change operations and the writing and reading for the four data channels. transmission speed variables. A 4-input multiplexer (217) activates the status metric accesses for all channels.
The state metric memory pool (69) has sufficient storage capacity for 64 state metric values per channel. To facilitate the reading of (145a, 145b, 145c) and (145d) and writing in (143a, 143b, 143c) and (143d) in the grouping (69) of memories of state metric values, the structure "pingpong" for the memory it facilitates both operations during the individual ACS operations coordinated by the ACS sequencer (71) on the "ping-pong" line (155) and access bus (157). The total capacity of the SRAM pool (69) of state metric memory is 4,096 bits.
The backhaul memory pool (73) is used to record which path has survived in each state for each decoded symbol. Since a trellis diagram is in theory an infinite replica of a state diagram, it would take an infinite amount of memory to record all the information for each transmitted symbol. However, the back-location history is kept for only 35 consecutive symbols and is overwritten from ACS circuits (67a, 67b, 67c) and (67d) on lines (149a, 149b, 149c) and (149d). The traceback memory (73) requires 8,960 bits of SRAM arranged in a 32 x 280 array. The backspace is 35 symbols deep; thus, before a decoded symbol is output, an accumulation of 35 symbols of information has taken place. The input symbol that produces a given output has occurred 35 symbols earlier in time.
The backhaul memory (73) is arranged as a circular buffer circuit. Every time it is written
ES 2 172 486 T3 a new symbol to the backhaul memory (73), all previously stored symbols are shifted, discarding the oldest symbol value. The memory required is based on the rule of 5 times the restricted length, so 35 memory symbols are needed for a restricted length K = 7.
Figure 10 shows how the trackback memory works. The backhaul processor (75) is a recurring operation similar to that of the ACS processor (71), in the sense that a counter is initialized (step 501) and configured (step 503) by assigning a value of (34) as described above (5 times the restricted length). The best local metric value is then assigned to the best metric value (step 505). A decision must be made if the backtracking count equals 0 (step 507). If so, the process is finished (step 531) and the path that was most likely is known, and the decoder outputs one bit (step 529). If the trackback count is not equal to 0, the operation starts over until the best metric value is reached.
Since four different data transmission rates can be processed, the backhaul memory (73) is consumed accordingly, that is, if channel 0 is working at 64 kb / s, after (35) symbols in the channel 0 the backhaul memory will be full for that particular channel; however, if channel 2 is working at half speed, that is, 32 kb / s, channel 2 would only fill half of the backhaul memory (73).
The backhaul memory (73) is allocated in sequence, since one channel may be far behind another channel. The back-location process (75) is unique for each channel, since the data that has been encoded at the transmitter is unique. Consequently, the backhaul operation for each of the four channels will be unique. In addition, the data transmission rates may be different between the four channels.
The back-location process is carried out in series, and the processor (75) works sequentially for channel 0, then for channel 1, then for channel 2 and finally for channel 3, since the accesses are not common. The storage of the retrolocation information depends on the accesses, requiring each process to be segregated for each channel in time. If all four channels were transmitted at full speed, the memory would still need segregation, since the data that was encoded at the transmitter created a different trellis or backtracking path between each of the four channels. The process would be even more complicated if they were processed at different data transmission speeds.
Referring to the flowchart of Figure 10, if the back-location count is not equal to 0 (step 507) the process must back-locate in time to the path that is most likely. The processor reads the 9-bit access that includes a field, a one-byte access, and a 1-bit access. This is done by shifting the access right 4 bits (step 509), then shifting right by 1 bit (step 511), and hiding the 3 least significant bits (step 513). The best local metric value is a 7-bit number. The 4 most significant bits will become the 1-byte access, the next 3 bits will become the number of bits, and the 4 least significant bits are ignored. The trail bit is examined (step 515) to see if it is a 1 or a 0. If the trail bit is a 0, the previous best local metric value is shifted to the right by 1, effectively dividing it by 2 . If the trail bit equals 0, the best local metric value is shifted to the right by 1 (step 517). If the path bit is not equal to 0, 64 are added to the best local metric value, thereby placing the result between a value of 32 and 63. Processor 75 keeps track (steps 521,523,525 and 527) of all paths and its operation is repeated until the coded bit is found.
The processor finds the path that ends in the 64 states with the least energy indicating the least error. The backhaul memory stores the 35 paths associated with the 64 states with a bit that indicates whether the path is coming from the top or the bottom, since there are only two paths in a given state. Therefore, a 0 or a 1 indicates the way. The associated bit path for the best local metric value is stored along with the 1-byte access and the bit access. As all the information is stored in bytes, a decomposition is carried out since there are 64 states, with 8 bytes, with 8 bits per byte. Since there are 8 bits within the first byte, the 8 bits would indicate states 0 through 7, which indicates what better local metric value is pointing to these states. The next byte would be for states 8 through 15, and so on up to the 63rd state.
The process always discards the least significant bit of the 7-bit number. The 3 most significant bits, as discussed above, point to a particular byte access. The 3 bits that follow the most significant 3 point to a particular bit in the byte access. This is the "trail bit", which is used to modify the best local metric value.
The backhaul process runs 512 times faster than the maximum output speed. The access bus control is coordinated between the ACS sequencer (71) and the backhaul processor (75). During the ACS phase of decoder operation, the ACS sequencer controls through lines 151a, 151b, 151c and 151d the access bus 159 of the two memories of metric values of status and of back-location. Upon completion of the ACS operation, control of the backhaul memory access bus is handed over to the backhaul processor (75).
The back-location memory (73) is used in a procedure called "re-linking" or back-location that begins at the last node of the trellis, following the decision path from the last decision to the first in reverse order. This process determines the decoded symbol to be released as an output (161a, 161b, 161c) and (161d). The retrolocation process for all four channels cannot be carried out
ES 2 172 486 T3 in parallel within a common SRAM block (69, 75), since the access characteristics of the back-location process for the separate data channels are assumed to be independent. This process needs to be sequenced for each individual channel. If a particular channel has not been enabled for a particular symbol interval, the backhaul process for that channel is bypassed. The process requires a minimum of 35 clock cycles to perform the backhaul process for a given channel.
The present invention also has a behavioral diagnostic feature that calculates the bit error transmission rate (hereinafter BER). The Euclidean distance calculator (65) outputs a difficult decision 163 which goes into the back-location processor (75). This difficult decision is separated into a 35 symbol “first in-first out” memory (hereinafter FIFO), and then compared to the reconvolutionally encoded symbol output (161a, 161b, 161c) and (161d) which was released by the backhaul processor (75). The bit differences between the two accumulate. After 256 symbols, the backhaul processor accumulator (75) is flushed (165) to a BER output circuit (77) shown in Figure 7. When a new accumulated 8-bit BER value is ready for the host microprocessor to read, the BER ready signal 167 is activated for that particular channel.
As shown in the flow chart in Figure 11, the BER diagnostic process is described. For the BER calculation, the process requires a transmitter part and a receiver part. The data is input (step 601) to the transmitter and will support direct error correction coding, QSPK modulation, and quadrature signal amplification. The signal is not transmitted, but is directly input as input to the receiver part, where the signal is reduced. The output of the downsampling process bypasses the Viterbi decoder (step 603) and is delayed for 35 symbols (steps 607, 609, and 611) to allow the Viterbi decoder to decode the information (step 605). The data that has supported the hard decision (not decoded) is compared to the output of the Viterbi decoder, which provides an indication of the performance of the signal-to-noise ratio (SNR) and the processor.
The behavior of the present invention is shown in Figure 12. Said Figure 12 shows a graphical representation of the BER probability as a function of the signal-to-noise ratio comparing non-convolutionally encoded data and encoded data. Two embodiments of the invention are presented. In the first embodiment a restricted length of K = 7 is used. An alternative embodiment uses a restricted 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 has a bit error probability of 0.05%. However, for the same signal-to-noise ratio, the convolutionally coded data exhibits a dramatic increase in upward behavior from one bit error in one million. The graph also shows an improvement over the constrained length of 7 when an alternative embodiment employing a constrained length of 9 is used.
Instead of assembling a quadrature Viterbi decoder that has four input channels, each with two pairs of I and Q signals, a distance calculator is used to input four channels and output 16 distances. The 16 distances are then coupled to ACS blocks. The outputs of the Euclidean distance calculator block are then prorated per ACS individual block on a per channel basis.
In an alternative embodiment, instead of having four discrete ACS blocks for each individual channel, a drastic reduction could be achieved with a linear increase in clock speed. The ACS characteristic incorporating trellis operation can be reduced to two or even one ACS circuit by multiplexing the data input, along with an increase in clock speed.
Although specific embodiments of the present invention have been shown and described, many modifications and variations could be made by those skilled in the art.
Contents6
14 sheets
Sheet 1 Sheet 2 Sheet 3 Sheet 4 Sheet 5 Sheet 6 Sheet 7 Sheet 8 Sheet 9 Sheet 10 Sheet 11 Sheet 12 Sheet 13 Sheet 14
97 members in 10 offices
Priority claims4
| Document | Office | Kind | Date |
|---|---|---|---|
| 19970040477P | United States of America | – | |
| 4047797 | United States of America | P | |
| 19970871008 | United States of America | – | |
| 87100897 | United States of America | A |
Members97
| Document | Office | Kind | |
|---|---|---|---|
| WO9840971A1 | World Intellectual Property Organization (WIPO) | A1 | |
| US6005898A | United States of America | A | |
| EP0966796A1 | European Patent Office (EPO) | A1 | |
| CN1250558A | China | A | |
| ES2146560T1 | Spain | T1 | |
| DE966796T1 | Germany | T1 | |
| HK1024357A1 | Hong Kong, China | A1 | |
| US6256339B1 | United States of America | B1 | |
| JP2001514829A | Japan | A | |
| EP1161017A2 | European Patent Office (EPO) | A2 | |
| EP1161018A2 | European Patent Office (EPO) | A2 | |
| EP1161019A2 | European Patent Office (EPO) | A2 | |
| US2001050965A1 | United States of America | A1 | |
| US6404828B2 | United States of America | B2 | |
| HK1041385A1 | Hong Kong, China | A1 | |
| HK1041386A1 | Hong Kong, China | A1 | |
| HK1041387A1 | Hong Kong, China | A1 | |
| US2002110183A1 | United States of America | A1 | |
| EP0966796B1 | European Patent Office (EPO) | B1 | |
| AT224118T | Austria | T | |
| ATE224118T1 | Austria | T1 | |
| ES2172486T1 | Spain | T1 | |
| ES2172487T1 | Spain | T1 | |
| ES2172488T1 | Spain | T1 | |
| US2002141488A1 | United States of America | A1 | |
| DE69807850D1 | Germany | D1 | |
| EP1161017A3 | European Patent Office (EPO) | A3 | |
| EP1161018A3 | European Patent Office (EPO) | A3 | |
| EP1161019A3 | European Patent Office (EPO) | A3 | |
| ES2146560T3 | Spain | T3 | |
| CN1109414C | China | C | |
| DE69807850T2 | Germany | T2 | |
| US6577672B2 | United States of America | B2 | |
| US6577673B2 | United States of America | B2 | |
| CN1442957A | China | A | |
| US2004071233A1 | United States of America | A1 | |
| EP1161019B1 | European Patent Office (EPO) | B1 | |
| EP1161017B1 | European Patent Office (EPO) | B1 | |
| AT267483T | Austria | T | |
| AT268074T | Austria | T | |
| ATE267483T1 | Austria | T1 | |
| ATE268074T1 | Austria | T1 | |
| DE69824051D1 | Germany | D1 | |
| DE69824208D1 | Germany | D1 | |
| EP1439640A2 | European Patent Office (EPO) | A2 | |
| EP1161018B1 | European Patent Office (EPO) | B1 | |
| AT272271T | Austria | T | |
| ATE272271T1 | Austria | T1 | |
| DK1161017T3 | Denmark | T3 | |
| DK1161019T3 | Denmark | T3 | |
| DE69825328D1 | Germany | D1 | |
| HK1041385B | Hong Kong, China | B | |
| DE69824051T2 | Germany | T2 | |
| DK1161018T3 | Denmark | T3 | |
| ES2172488T3 | Spain | T3 | |
| HK1041387B | Hong Kong, China | B | |
| ES2172486T3This record | Spain | T3 | |
| ES2172487T3 | Spain | T3 | |
| HK1041386B | Hong Kong, China | B | |
| US6865217B2 | United States of America | B2 | |
| HK1067253A1 | Hong Kong, China | A1 | |
| EP1439640A3 | European Patent Office (EPO) | A3 | |
| DE69824208T2 | Germany | T2 | |
| US2005163195A1 | United States of America | A1 | |
| DE69825328T2 | Germany | T2 | |
| EP1439640B1 | European Patent Office (EPO) | B1 | |
| AT332592T | Austria | T | |
| ATE332592T1 | Austria | T1 | |
| US7088764B2 | United States of America | B2 | |
| DE69835177D1 | Germany | D1 | |
| EP1696584A1 | European Patent Office (EPO) | A1 | |
| CN1278498C | China | C | |
| DK1439640T3 | Denmark | T3 | |
| US2006262832A1 | United States of America | A1 | |
| ES2268532T3 | Spain | T3 | |
| HK1094840A1 | Hong Kong, China | A1 | |
| DE69835177T2 | Germany | T2 | |
| JP3988956B2 | Japan | B2 | |
| EP1696584B1 | European Patent Office (EPO) | B1 | |
| AT382208T | Austria | T | |
| ATE382208T1 | Austria | T1 | |
| DE69838922D1 | Germany | D1 | |
| EP1895671A2 | European Patent Office (EPO) | A2 | |
| DK1696584T3 | Denmark | T3 | |
| EP1895671A3 | European Patent Office (EPO) | A3 | |
| ES2300083T3 | Spain | T3 | |
| HK1114509A1 | Hong Kong, China | A1 | |
| DE69838922T2 | Germany | T2 | |
| EP2259440A1 | European Patent Office (EPO) | A1 | |
| US2012063490A1 | United States of America | A1 | |
| EP1895671B1 | European Patent Office (EPO) | B1 | |
| AT555552T | Austria | T | |
| ATE555552T1 | Austria | T1 | |
| EP2259440B1 | European Patent Office (EPO) | B1 | |
| ES2386278T3 | Spain | T3 | |
| DK2259440T3 | Denmark | T3 | |
| ES2387708T3 | Spain | T3 |
Numbers
- Publication
- 2172486
- Application
- 1120761
Titles2
- Spanish
- DESCODIFICADOR DE VITERBI MULTICANAL.
- English
- MULTICHANNEL VITERBI DECODER.
Classification
- CPC, 20
- H04L1/006
- H03M13/256
- H03M13/4107
- H03M13/4169
- H03M13/6502
- H03M13/6505
- H03M13/6569
- H04B1/707
- H04B2201/70703
- H04L1/0009
- H04L1/0046
- H04L1/0052
- H04L1/0053
- H04L1/0054
- H04L1/0059
- H04L1/0072
- H04L1/0075
- H04L1/08
- H04L25/0262
- H04L2025/03675
- IPC, 5
- H03M13 00
- H03M13 41
- H04B1 707
- H04L1 00
- H04L1 08