Soft decision viterbi decoder for M-ary convolutional codes

The embodiments of the invention in which an exclusive property or privilege is claimed are defined as follows:

1. A method for decoding an encoded signal that represents information bearing data comprising a plurality of bits, said information bearing data having been encoded with an orthogonal convolutional M-ary error correction code, each bit of the information bearing data being represented by one of M different symbols, where M is greater than two, said method comprising the steps of:

(a) for each bit of the information bearing data that was encoded:

(i) determining a correlation value for each of the M symbols;

(ii) determining a maximum correlation value of the M correlation values of step (a) (i);

(iii) determining M branch metrics, each branch metric comprising a difference between the maximum correlation value and one of the M correlation values;

(iv) for each of N current states, determining a most likely path to that state as a function of the branch metrics, said branch metrics being used in connection with a state metric for a prior state to determine a new state metric for each current state; and

(v) storing a value indicative of the most likely path from a prior state to each of the N current states, to produce a path history;

(b) reiterating steps (a)(i) through (a)(v) for each bit of the information bearing data that was encoded; and

(c) as a function of the path history, determining decoded data corresponding to the information bearing data that was encoded, said decoded data comprising a plurality of bits, each of which is determined by tracing back through the path history to identify a state metric value that most likely corresponds to a bit of the information bearing data.

2. A method for decoding a received signal that represents information bearing data comprising a plurality of bits, said information bearing data having been encoded with an orthogonal convolutional M-ary error correction code prior to transmission, each bit of the information bearing data being represented by one of M possible symbols, where each of the M symbols is different from the others and M is greater than two, said method comprising the steps of:

(a) correlating the received signal to determine M correlation values, each correlation value corresponding to one of the M possible symbols;

(b) determining a plurality of branch metrics, including a branch metric for each of the M possible symbols, the branch metric for a symbol being equal to a difference between a maximum one of the M correlation values and the correlation value corresponding to that symbol;

(c) determining path metrics for paths entering each of N different states, by adding the branch metric corresponding to a path from a previous state to a state metric of said previous state, for each of the N different states;

(d) comparing the path metrics entering each of the N states and selecting a minimum path metric for each state as a new state metric for that state;

(e) identifying a data bit corresponding to the path metric selected in step (d);

(f) updating a path history as a function of the path metric selected in step (d);

(g) reiterating steps (a) through (f), storing the data bit for each of the N states, during each of a predetermined number of iterations, to develop a path history;

(h) identifying a minimum state metric of the state metrics for a current iteration, to determine a most likely path through all of said iterations; and

(i) determining a decoded output bit as a function of an earlier state by following the most likely path back through the path history for the predetermined number of iterations, said output bit corresponding to a bit of the information bearing data that was most likely encoded.

3. The method of claim 2, further comprising the step of repeating steps (a) through (i), for each successive bit of the information bearing data that were encoded, until all bits of the information bearing data that were encoded are decoded.

4. The method of claim 2, further comprising the step of identifying a symbol likely representing a bit of the information bearing data that was encoded, said symbol having the maximum correlation value of the M possible symbols.

5. The method of claim 2, wherein M has a value of eight, and wherein there are 64 possible correlation values.

6. The method of claim 2, wherein the step of selecting a minimum path metric further comprises the step of normalizing the state metrics to reduce their magnitude.

7. Apparatus for decoding an input signal encoded to represent information bearing data comprising a plurality of bits, said plurality of bits having been encoded with an orthogonal convolutional M-ary error correction code, each bit of the information bearing data being represented by one of M possible symbols, where each of the M symbols is different from the others and M is greater than two, said apparatus comprising:

(a) branch metric means for determining a branch metric for each of the M possible symbols as a function of correlation values determined from the input signal, the branch metric for a symbol being equal to a difference between a maximum one of the M correlation values and the correlation value for that symbol;

(b) adding means, coupled to the branch metric means, for determining path metrics for all paths entering a state, by adding the branch metric to a previous state metric of each path to a state, for each of N possible states;

(c) comparing means, coupled to the adding means, for comparing path metrics entering each state and including means for selecting a minimum path metric as a new state metric;

(d) updating means, coupled to the comparing means, for updating a state metric as a function of the path metric selected in (c);

(e) memory means, coupled to the updating means, for storing a path history for a predefined number of iterations of determining the branch metrics, state metrics, and path metrics, said path history identifying the path metric selected in (c) for each iteration; and

(f) control means, coupled to the memory means, for identifying a minimum state metric for each iteration, to determine a most likely path through the path history and for decoding an output bit as a function of an earlier state reached by following the most likely path, said output bit most likely corresponding to a bit of the information bearing data that was encoded.

8. The apparatus of claim 7, wherein the branch metric means, adding means, comparing means, updating means, memory means, and control means comprise a single, monolithic integrated circuit.

9. The apparatus of claim 7, wherein the control means include a microcontroller.

10. The apparatus of claim 7, wherein the adding means comprise a plurality of buffers for temporarily storing a plurality of sums produced by adding state metric and selected branch metric values.

11. The apparatus of claim 7, wherein the branch metric means comprise a plurality of registers and a memory for temporarily storing the correlation values and differences between a maximum one of the M correlation values and other of the M correlation values, for each of the possible symbols.

12. The apparatus of claim 7, wherein the memory means comprise a path memory module, said path memory module including:

(a) a path memory controller;

(b) an output decode module coupled to and controlled by the path memory controller; and

(c) counter means for determining when at least the predetermined number of iterations has been completed, said counter means then producing a data ready signal to indicate when the most likely path can be determined to decode a first output bit, followed by successive output bits.

13. The apparatus of claim 7, wherein the control means determine an appropriate branch metric to add to a previous state metric to reach a current state.

14. The apparatus of claim 7, further comprising means for determining an error rate of the input signal by comparing a teencoded symbol from the decoder data to a symbol determined as a function of the maximum of the correlation values derived from the input signal.

15. The apparatus of claim 7, wherein the adding means comprise normalization means for normalizing the state metrics.

16. In a communication system that encodes binary data to be transmitted using an orthogonal convolutional M-ary error correction code to represent the binary data with M different symbols, M being greater than two, a method for decoding a received signal to recover the binary data that was transmitted, even when the received signal has been affected by noise, said method comprising the steps of:

(a) for each bit of the binary data that was encoded:

(i) processing the received signal to determine one of N possible correlation values for each of the M different symbols;

(ii) determining a maximum of the correlation values determined for each of the M different symbols;

(iii) subtracting the correlation values for each of the M different symbols from the maximum of the correlation values to determine M branch metrics;

(iv) for each of two different paths leading to one of N possible current states from previous states, adding a selected one of the branch metrics to a state metric of one of the previous states to determine a path metric for each such path leading to the current state;

(v) comparing the path metrics for each of the N possible current states to determine a minimum path metric of the two paths leading to each of said current states;

(vi) assigning the minimum path metric for each of the N possible current states as a new state metric for that state; and

(vii) identifying a bit value corresponding to the minimum path metric of step (a) (vi);

(b) reiterating steps (a) (i) through (a) (vii) for each bit of the binary data that was encoded for transmission;

(c) for each iteration of step (b), storing the bit value for all of the possible states, to develop a path history;

(d) identifying a minimum state metric for each iteration, to determine a most likely path through the path history;

(e) by tracing back along the most likely path, identifying an output bit associated with an earlier state metric occurring a predetermined number of iterations ago, said most likely representing a bit of the binary data that was encoded and transmitted; and

(f) repeating steps (a) through (e) for each successive bit of the binary data that was encoded to decode each remaining bit thereof.

17. The method of claim 16, wherein M has a value of eight, and wherein there are 64 possible states for each iteration and 64 possible different correlation values.

18. The method of claim 16, further comprising the step of normalizing the state metric for each possible state to reduce a magnitude of the state metric.

19. The method of claim 16, wherein the step of identifying the output bit comprises the step of backing through the path history, following paths connected to the minimum state metric of the current states, to reach the earlier state metric that occurred the predetermined number of iterations ago.

20. The method of claim 16, wherein the maximum of the correlation values corresponds to one of the eight possible symbols that was likely transmitted if the received signal was not adversely affected by noise.

21. The method of claim 16, further comprising the step of determining an error rate for the received signal.

Description Submit all comments and votes

FIELD OF THE INVENTION

The present invention is generally directed to an error correction system used in a communication system employing convolutional codes, and more specifically, relates to an error correction decoder in a receiver of such a communication system.

BACKGROUND OF THE INVENTION

Radio transmissions in communication systems are often subject to noise or jamming that can cause significant errors in the received signal. One of the techniques commonly used to prevent loss of data from a signal transmitted over a noisy or fading channel uses a convolutional encoder to encode the signal input to the transmitter, producing an encoded binary signal. The encoded binary signal provides redundant information that enables correction of erroneous data caused by noise or other sources of signal degradation.

The method used for decoding a received signal has been shown to have a significant impact on the performance of the error correction codes employed in a communication system. It has been determined, for example, that soft decision decoding offers substantially improved performance over hard decision decoding, by reducing the amount of energy required to correctly transmit information. Techniques that implement maximum likelihood decoding provide further improved performance over other decoding techniques, increasing the efficiency of the error correction process.

A soft decision Viterbi decoder algorithm thus represents a preferred approach for decoding a convolutional encoded binary signal. The transmitted data are recovered with this type of decoder by applying a maximum likelihood sequence probability analysis to select the bit most likely transmitted. An example of a soft decision Viterbi decoder is disclosed in U.S. Pat. No. 4,536,878, issued on Aug. 20, 1985 to Rattlingourd et al. The decoder in this patent is implemented on a monolithic very large scale integrated (VLSD circuit that includes a branch metric calculator, a metric update circuit, a path update, a majority vote circuit, and a control circuit. The encoded binary data transmitted comprise symbol pairs, each symbol of the pair comprising three bits, including a sign bit, a most significant bit (MSB), and a least significant bit (LSB). The branch metric calculator determines a difference between the symbol pairs and each of the four possible symbol pair combinations (00, 01, 10, and 11), producing metrics H.sub.00 through H.sub.11, respectively. The metrics are supplied to the metric update circuit, which determines errors for each metric and accumulates these errors as measured, at each of 64 nodes. The metric update circuit determines the minimum error for the metric value of the measurement, which establishes a maximum probability path through a state trellis. This path is updated for each symbol pair received and processed, yielding an indication of the transmitted encoded binary signal and thus, an indication of each binary bit that was input for transmission.

Convolutional encoding of a transmitted signal is usable with many types of communication systems and is particularly applicable to a spread spectrum system. A spread spectrum communication system is sometimes used to insure a low probability of interception of transmitted signals by a third party. In this type of system, a transmitted signal is spread over a frequency band that is much wider than the bandwidth of the information being transmitted. This approach reduces the amount of energy required to communicate information to the lowest level possible, thereby increasing the difficulty of intercepting the signal. Because the transmission has insufficient signal energy for a receiver to acquire a phase lock, the communication system must inherently be non-coherent.

Since a spread spectrum communication system uses excess bandwidth to reduce the signal energy density, making interception difficult, some of the excess bandwidth is available for encoding the signal transmitted, thereby further reducing the signal energy per bit. In order to minimize the intercept of the transmission, it is necessary to use an energy efficient modulation and coding scheme. Thus, one of the first steps for processing the signal to be transmitted in such a system is to encode it using an error correction code. However, instead of using a simple binary convolutional encoding scheme, it is preferable to use an M-ary orthogonal convolutional code that encodes each bit of the input data at the transmitter using M different symbols (M>2) to represent the binary input data. The use of more than two redundant symbols in the encoding scheme increases the resilience of the transmitted signal to fading, jamming, and other noise problems.

An appropriate M-ary orthogonal convolutional error correction code is described by Bruce D. Trumpis in his Doctoral dissertation entitled, "Convolutional Coding for M-ary Channels," University of California at Los Angeles, 1975. However, the thesis only suggests that a standard Viterbi decoding technique could be used to decode the M-ary encoded signal. The prior art technique mentioned in this reference cannot accommodate without modification an 8-ary convolutional error correcting code, for example, which is the preferred format for encoding the spread spectrum signal in a low probability of intercept communication system that is being developed by the assignee of the present invention. In fact, a substantially different branch metric algorithm that is not disclosed in this thesis or in other prior art must be applied to decode an M-ary code, for M>2.

Accordingly, the present invention is directed to a decoder that implements a soft decision algorithm using maximum likelihood decoding, yielding excellent performance not only in a Gaussian noise environment, but also in a partial band-noise jammed channel.

SUMMARY OF THE INVENTION

In accordance with the present invention, a method for decoding a received signal that represents information bearing data comprising a plurality of bits is defined. The information bearing data are encoded with an orthogonal convolutional M-ary error correction code so that each bit of the information bearing data is represented by one of M possible symbols. Each of the M symbols is different from the others and M is greater than two. This method starts with the step of correlating the received signal to determine M correlation values, each correlation value corresponding to one of the M possible symbols. A plurality of branch metrics are then determined, where the branch metric for a symbol is equal to a difference between a maximum one of the M correlation values and the correlation value corresponding to that symbol.

Path metrics for all paths entering each of N different states are determined by adding the branch metric corresponding to a path from a previous state to a state metric of the previous state, for each of the N different states. By comparing the path metrics entering each of the N states, a minimum path metric for each state is selected and used as a new state metric for that state. Preferably, the step of selecting a minimum path metric comprises the step of normalizing the state metrics to reduce their magnitude. A data bit corresponding to the path metric selected in the preceding step is identified, and a path history is updated as a function of the path metric selected above. These steps are repeated until a predetermined number of iterations are completed, and the path metric determined in each iteration is stored in the path history. A minimum state metric of the state metrics is identified as a path metric, for each of the predefined number of iterations, to determine a most likely path through the path history. An output bit is then produced, as a function of an oldest state, by following the most likely path through the path history. This output bit represents the most likely value of a corresponding bit of the information signal that was encoded.

The steps outlined above are repeated for each successive bit encoded, until all bits of the information bearing data that were encoded are decoded. In one preferred form of the invention, M has a value of 8 and there are 64 possible states for the eight possible symbols.

A further aspect of the present invention is directed to apparatus for decoding an input signal encoded with an orthogonal convolutional M-ary error correction code, where each bit of information bearing data conveyed by the input signal is represented by one of M possible symbols, each of the M symbols is different from the others, and M is greater than two. The apparatus generally includes means for implementing each of the steps of the method discussed above.

BRIEF DESCRIPTION OF THE DRAWINGS

The foregoing aspects and many of the attendant advantages of this invention will become more readily appreciated as the same becomes better understood by reference to the following detailed description, when taken in conjunction with the accompanying drawings, wherein:

FIG. 1 is a block diagram of a communication system in which an error control decoder in accordance with the present invention is used to decode an M-ary orthogonal convolutional encoded signal;

FIG. 2A is a more detailed block diagram that more clearly identifies the convolution encoder and an orthogonal encoder used in the communication system of FIG. 1;

FIG. 2B is a schematic block diagram of the convolutional encoder;

FIG. 2C is a more detailed block diagram of the error control decoder of FIG. 1;

FIG. 3 is an overview of the error control decoder in block diagram form;

FIG. 4 is a schematic block diagram of a branch metric module of the error control decoder;

FIG. 5 is a schematic block diagram of one of the two identical state metric modules used in the error control decoder and its associated add-compare-select module;

FIG. 6 is a detailed schematic diagram of one of the select minimum state metric/minimum address modules indicated in FIG. 5;

FIG. 7 is a detailed schematic diagram of a select minimum state metric module indicated in FIG. 5;

FIG. 8 is a block diagram of a path history memory module in the error control decoder;

FIG. 9 is a schematic diagram of one of the two modules "to modify selected bit," as indicated by one of the blocks in FIG. 8;

FIG. 10 is a schematic diagram of an output decode module from FIG. 8;

FIG. 11 is a schematic diagram of a data ready module from FIG. 8;

FIG. 12 is a timing signal chart for signals used by the data ready module of FIG. 11;

FIG. 13A is a schematic block diagram of a path memory controller that comprises one of the blocks shown in FIG. 8; and

FIG. 13B is a timing signal chart for signals in the error control decoder.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

Overview of the Communication System

As illustrated in FIG. 1, a communication link in a spread spectrum communication system 20 in which the present invention is used comprises a transmitter 22 that is transmitting radio signals to a receiver 24. Transmitter 22 is supplied with binary input data, comprising information to be conveyed from transmitter 22 to receiver 24. Spread spectrum communication system 20 is used to convey this information bearing data in an encoded form to ensure a low probability of intercept of the transmitted signal by some unauthorized receiver. The present invention has utility in spread spectrum communication system 20 because it facilitates decoding of the encoded data. It should be recognized, however, that the present invention is not limited to use in such a system.

The binary input data supplied to transmitter 22 is encoded by an error control encoder 26 using an 8-ary code. The symbols are determined by the following generator polynomials:

g1=1+X.sup.1 +X.sup.2 +X.sup.3 +X.sup.4 +X.sup.5

g2=1+X.sup.1 +X.sup.3 +X.sup.4 +X.sup.6

g3=1+X.sup.2 +X.sup.4 +X.sup.5 +X.sup.6 (1)

The encoded symbols produced by error control encoder 26 are input to an orthogonal waveform encoder 28, which produces a set of N orthogonal signals, each of which is represented by a sequence of N bits.

Using the polynomial expressions of equations (1), error control encoder 26 encodes the binary input data to form three bit symbols for each bit of the binary input data. The binary input data are applied to a seven bit shift register 26a (shown in FIG. 2B). The shift register is initialized to zero; successive bits of the binary input data are shifted to the right in the shift register, yielding a different symbol for the data with each successive clock cycle as parity adders 27a, 27b, and 27c combine the bits in selected registers of the shift register to produce different three bit symbols. In the preferred embodiment, the convolutional encoding scheme has a constraint length of seven and employs an alphabet of eight symbols, i.e., (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), and (1,1,1). The orthogonal waveform encoder encodes each of these symbol into one of eight possible orthogonal words. Since orthogonal encoders are well known in the art and because it is not directly relevant to the present invention, details of the orthogonal encoder need not be disclosed.

In the spread spectrum communication system, the sequence of N binary bits output from the orthogonal waveform encoder are combined with a pseudorandom number (PN) binary sequence provided by a PN sequence encoder 30, and the resulting signal is modulated by a modulator and transmitter circuit (32) to produce a radio frequency (RF) signal that is transmitted from an antenna 34. The binary sequence provided by the PN sequence encoder has the characteristics of random noise, but it is deterministic and is reproducible in the intended receiver(s) of the signal. This spread spectrum signal comprises a plurality of "chips." Because the chip rate is higher than the data rate of the binary input data, the signal transmitted from antenna 34 produced by modulating the chips has a broader frequency spectrum than the binary input data and is not readily detected or intercepted.

The transmitted signal is received at receiver 24 by a corresponding antenna 36. From this antenna, the signal is input to a receiver and demodulator circuit 38, which down-converts the received signal and demodulates it. The same PN sequence used by transmitter 22 is also generated in receiver 24 by a PN sequence correlator circuit 40 and used to correlate the demodulated signal. Thus, the output of PN sequence correlator circuit 40 generally corresponds to the orthogonal waveform encoded signal that was input to PN sequence encoder circuit 30 in transmitter 22.

An orthogonal decoder circuit 42 then decodes the signal output from PN sequence correlator circuit 40, producing a signal that is applied to an error control decoder circuit 44, which is constructed and operates in accordance with the present invention. Orthogonal decoder circuit 42 correlates the signal supplied from PN sequence correlator circuit 40 with the eight different orthogonal words in the preferred embodiment, producing correlation values for each of the eight possible symbols.

As shown in FIG. 2C, a block 42a applies a soft decision modified Viterbi decoder algorithm. The soft decision Viterbi decoder uses a convolutional decoding approach, employing a branch metric that is unique to the present invention. This decoding scheme traces a sequential probability path history that is developed by processing branch metric values, enabling the soft decision Viterbi decoder to produce a decoded binary bit stream output, which, with a relatively high probability, represents the information originally transmitted.

Error control decoder circuit 44 (FIG. 1) processes the signal input to it, producing a decoded binary bit stream corresponding to the binary input data supplied to transmitter 22. Noise, fading, jamming and other effects that tend to produce errors in the received signal are more readily compensated because the binary input data were encoded as symbols. The soft decision Viterbi decoder technique employed by error control decoder circuit 44 decodes the signal from the orthogonal decoder, recovering data that would otherwise likely have been lost due to the errors introduced in the signal during its propagation from transmitter 22 to receiver 24. Although conventional Viterbi decoders are well known in the art, such devices are typically used for decoding only a binary convolutional code. In contrast, the present invention employs a novel branch metric technique to accommodate an M-ary code (where M is greater than 2 in the general case and equals 8 in the preferred embodiment).

Overview of the Error Control Decoder Circuit

An overall schematic block diagram of error control decoder circuit 44 is shown in FIG. 3. Error control decoder circuit 44 includes a branch metrics module 46, which is controlled by a microcontroller 48 to carry out the soft decision Viterbi decoder technique. Also included in the error control decoder circuit are an add-compare-select module 50 that determines state metrics and path metrics to determine a path history. The add-compare-select module comprises an A module 52 and a corresponding parallel B module 54. A path history memory module 62 stores path history data that are used in decoding the encoded data. Error control decoder 44 also includes state metrics A and state metrics B modules 58 and 60, and symbol error detection module 64.

Microcontroller 48 accepts external control commands, including STARTMC (start microcontroller) and SYSRSTn (system reset-low) commands and responds to these commands to produce other internal commands and control signals necessary to carry out the decoding operation. The SYSRSTn command is generated, for example, after power is reapplied to the receiver, to reset the error control decoder. Although these components are not separately shown, the microcontroller includes a system clock counter and a read only memory (ROM) that produces a plurality of different control signals used by error control circuit 44. STARTMC starts the counter, causing it to count system clock cycles. The count accumulated by the counter is used to select sequential addresses in the ROM, causing a control signal corresponding to the addresses thus selected to be output. After cycling through all of the instructions stored in the ROM, the RESETn line is set low and the counter is reset until the next STARTMC command is applied, starting the operation over again. Control signals supplied through the microcontroller include SYSCLK (system clock), and SYMCLK (symbol clock).

During normal operation of error control decoder 44, a logic level 0 SYSRSTn signal is produced after power up to place the decoder in a known state. (Note that the "n" on the end of "SYSRSTn" and similarly, as used in the identification acronyms for other signals shown in the Figures, indicates that a "NOT" or inverted logic signal initiates the indicated control action.) On application of the SYSRSTn, a RESETn control signal from the microcontroller goes low (logic level 0), which resets most of the registers and other components in the error control decoder. A MRSTn (ram reset) signal is held low during one complete cycle through the ROM, allowing registers and other elements in the decoder to initialize to zero before the error control decoder begins to decode an input signal.

Several different signal lines convey data/addresses into branch metrics module 46. DIDATA lines 66 convey 6-bit correlation values for each of the eight possible orthogonal words that were determined by orthogonal decoder 42. BMADD lines 68 convey a 3-bit branch metric address identifying the specific orthogonal word of the eight possible corresponding to the correlation value that is then being supplied to branch metrics module 46. BMWRn line 70 conveys a branch metric write signal to enable the correlation value currently being supplied to be written into memory in branch metrics module 46. A BMWRAn line 72 conveys a second branch metric write enable signal, but one that is supplied by microcontroller 48.

Microcontroller 48 is also connected to branch metrics module 46 by other signal lines. BMADDA lines 74 convey a branch metric 3-bit address to select a specific orthogonal symbol to be processed by branch metrics module 46. Each such symbol is processed by the error control decoder during an interval of time referred to herein as a "symbol period."

A NORSELn line 76 provides a NOR gate select signal used in branch metrics module 46. BMADDB lines 78 convey a second branch metric address used in the module. An ADDTOG line 80 provides an address toggle signal comprising an MSB of an address and is used to enable a double buffering scheme that permits addressing of different portions of the module with the same LSBs of the address. A RAMRSTn line 82 conveys a RAM reset signal from microcontroller 48 to branch metrics module 46. Similarly, a RESETn line 84 conveys the reset signal to the branch metrics module, add-compare-select module 50, and path history memory module 62. A RECSYM line 86 conveys a "received symbol" signal from branch metrics module 46 to symbol error detection module 64. This signal indicates the symbol having the greatest correlation value.

BMA lines 88 and BMB lines 90 convey a 6-bit branch metric that is output from branch metrics module 46 to add-compare-select A module 52 and add-compare-select B module 54, respectively. EN1n line 92 and EN2n line 94 convey enable signals from microcontroller 48 to each of the add-compare-select modules A and B. Similarly, WR2n and WR1n lines 96 and 98 convey write signals from the microcontroller to the add-compare-select modules to control timing.

Corresponding lines SMADDA and SMADDB are coupled to both state metrics A and B modules 58 and 60, and to add-compare-select A and B modules 52 and 54, conveying state metric addresses to select the specific state metric currently being processed. SMWR1n line 102 and SMWR2n line 104 connect microcontroller 48 to state metrics A and B modules 58 and 60, conveying state metric write signals from the microcontroller. SMA lines 108 and SMB lines 110 interconnect the state metrics A and B modules, and the add-compare-select A and B modules. A DxA line 116 and a DxB line 112 convey binary data from add-compare-select A module 52 and add-compare-select B module 54, to path history memory module 62 to indicate the path followed from one state to a successive state. This signal is used in defining a path history.

DECDATA lines 120 couple path history memory module 62 and symbol error detection module 64, conveying the decoded symbol from path history memory module 62 for comparison to the symbol that had the largest correlation value. A SYMERR line 124 conveys a signal that indicates whether the bit of the decoded data differs from the bit corresponding to the received symbol that had the largest correlation value. Data decoding does not begin until a signal carried by a DATARDY line 126, which is connected to path history memory module 62, indicates that at least a predetermined number of received symbols have been processed to produce a path history sufficiently long to accurately decode the encoded data.

Description of the Branch Metrics Module

Details of branch metrics module 46 are shown in FIG. 4. The branch metrics module includes a tri-port random access memory (RAM) 130, which stores sixteen 6-bit words that are written through ports A and C and read through ports A and B. ADDTOG line 80 is connected to the MSB of an address terminal of port C on tri-port RAM 130 and to an inverter 132, which inverts the address toggle signal and conveys the inverted signal on a line 148 to the MSB of an address terminal of ports A and B. The branch metrics module also includes a 6-bit register 134, a digital subtraction module 136, a 6-bit register 138, a NOR gate 140, a NAND gate 142, and a 3-bit register 144.

A SYSRSTn line 146 conveys the system reset signal to 3-bit register 144. SYSCLK lines 150 are coupled to each of 6-bit registers 134 and 138, and to 3-bit register 144, providing a 20 megahertz system clock (in the preferred embodiment), which toggles the input signals of the registers from their D inputs to their Q outputs (if the registers are enabled by the signal applied to their enable terminals). Output data from port A of tri-port RAM 130 are conveyed on lines 152 to a B input of digital subtraction module 136 and to the D terminals of 6-bit register 134. The enable terminal of 6-bit register 134 is controlled by the signal from the output of NAND gate 142, which is also coupled through a line 154 to the enable terminal of 3-bit register 144. The output terminals of 6-bit register 134 are coupled through lines 156 into the A inputs of digital subtraction module 136. A line 158 conveys a carry out signal from the digital subtraction module to one of the two inverting inputs of NAND gate 142, the non-inverting input being connected to RESETn line 84. This carry out signal is high if the value of the data applied to the B inputs of the digital subtraction module is greater than the value of the data applied to the A inputs. The actual difference between the data supplied to the A and B inputs (A-B) is conveyed on lines 160 to the D inputs of 6-bit register 138. A reset signal is applied through a line 162 to a reset terminal of this 6-bit register from the output of NOR gate 140. The difference between the data applied to the A and B inputs of digital subtraction module 136 is clocked out of the 6-bit register with each system clock 150 on lines 164; these lines are connected to the inputs of port A on tri-port RAM 130.

The operation of branch metrics module 46 is as follows. Each bit of information that is transmitted is represented by one of eight orthogonal words or symbols in the preferred embodiment. Orthogonal decoder 42 determines a correlation value for each of the eight possible symbols; these correlation values can range between 0 and 63, inclusive. BMADD lines 68 identify the specific one of the eight possible orthogonal words or symbols that is currently being input to port C of tri-port RAM 130, and the corresponding correlation value of that symbol is supplied over DIDATA lines 66 from the orthogonal decoder. The correlation value corresponding to the symbol determined by the orthogonal decoder are written into port C of the tri-port RAM in response to the branch metric write signal on BMWRn line 70. The signal on ADDTOG line 80 determines whether the correlation data a