Description

Field of the invention

This invention relates to a Viterbi decoding device and a method for decoding a signal produced by a convolutional encoder. Background of the invention

Convolutional encoding is a method commonly used in telecommunications to make a transmitted signal more robust against perturbations and noise. A convolutional encoder transforms a data stream to be transmitted into a coded data stream having a higher bit rate than the original data stream. An individual bit in the coded data stream may be correlated to two or more bits of the original data stream. Such correlations can be exploited on the receiver side to enable forward error correction.

The Viterbi algorithm is an example of a method of decoding a convolutionally encoded signal and is well-known in the art. Summary of the invention

The present invention provides a Viterbi decoding device and a method for decoding a signal produced by a convolutional encoder as described in the accompanying claims.

Specific embodiments of the invention are set forth in the dependent claims.

These and other aspects of the invention will be apparent from and elucidated with reference to the embodiments described hereinafter.

Brief description of the drawings

Further details, aspects and embodiments of the invention will be described, by way of example only, with reference to the drawings. In the drawings, like reference numbers are used to identify like or functionally similar elements. Elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale.

Figure 1 schematically shows an example of an embodiment of a communication system.

Figure 2 shows an example of a trellis diagram.

Figure 3 schematically shows a first example of a first set of transitions in the trellis diagram of Figure 2.

Figure 4 schematically shows a second set of transitions in the trellis diagram of Figure 2 in accordance with the example of Figure 3.

Figure 5 schematically shows a second example of a first set of transitions in the trellis diagram of Figure 3. Figure 6 shows a second set of transitions in the trellis diagram in accordance with this second example.

Figure 7 schematically shows an example of a sequence of soft symbols.

Figure 8 shows an example of a table specifying a set of branch metric values corresponding to a first set of transitions.

Figure 9 shows an example of a table specifying a set of branch metric values corresponding to a second set of transitions.

Figure 10 shows an example of a table specifying a first set of branch metric values corresponding to a first set of transitions in an example of a convolutional encoder having a total of 64 states.

Figure 1 1 shows a table which is a continuation of the table shown in Figure 10.

Figure 12 shows an example of table specifying a second set of branch metric values corresponding to a second set of transitions in the example mentioned above in reference to Figure 10.

Figure 13 shows a table which is a continuation of the table shown in Figure 12.

Figure 14 schematically illustrates an example of a convolutional encoder.

Figure 15 schematically shows an example of a Viterbi decoder.

Detailed description of the preferred embodiments

Because the illustrated embodiments of the present invention may for the most part, be implemented using electronic components and circuits known to those skilled in the art, details will not be explained in any greater extent than that considered necessary as illustrated above, for the understanding and appreciation of the underlying concepts of the present invention and in order not to obfuscate or distract from the teachings of the present invention.

Figure 1 schematically shows an example of a communication system 10. The communication system 10 may notably comprise an encoder unit 12, a transmitter unit 14, a receiver unit 16, and a decoding unit 18. The transmitter unit 14 may be connected to the coding unit 12. The decoding unit 18 may be connected to the receiver unit 16. The communication system 10 may operate as follows. An input data stream 20 may be fed to the coding unit 12. The data stream 20 fed to the coding unit 12 may also be referred to as the input bit stream. The input bit stream may be a binary sequence, i.e., a succession of bits wherein each bit may have a value of either zero or one. The coding unit 12 may apply a convolutional coding algorithm to the input data stream 20 and thus generate an output data stream 22. The output data stream 22 may also be referred to as the coded data stream or the coded bit stream.

The coded bit stream 22 may have a higher bit rate than the input bit stream 20. The bit rate may be defined as the number of transmitted bits per time unit. The time unit may, for instance, be one second or, if the encoder unit 12 is clocked by a clock cycle, one clock cycle of that clock signal. The bit rate of the coded data stream 22 may notably be an entire multiple of the bit rate of the original data stream 20. More specifically, the coding unit 12 may transform each received bit of the input data stream 20 into a symbol consisting of several, e.g., two, bits. The symbol length, i.e., the number of bits representing one symbol, may be fixed, i.e., every symbol in the output data stream may have the same length. The symbol length may notably be two bits. The bit rate of the output data stream 22 divided by the bit rate of the input data stream 20 may thus coincide with the symbol length. The inverse of this quantity, i.e., the inverse of the symbol length, is known as the code rate.

More generally, the coding unit 12 may be arranged to transform each M-bit input string into an N-bit symbol, where M/N is the code rate and N may be greater than M. This transformation may be a function of the last K-1 input strings. The number K is known as the constraint length of the transformation. The coded data stream 22 may be fed to the transmitter unit 14. The transmitter unit 14 may further transmit the coded data stream 22 to the receiver unit 16, for instance, in the form of a modulated electromagnetic wave 24. The receiver unit 16 may be arranged to recover the coded data stream 22 by demodulating the received signal 24. The receiver unit 16 may, for instance, demodulate the received signal 24 to generate a receiver output signal 26. The receiver output signal 26 may, for instance, be an analog wave form, wherein a high level, e.g., +1 volt, may represent a one bit and a low level, e.g., -1 volt, may represent a zero bit.

The receiver output signal 26 may be fed to the decoder unit 18. The decoder unit 18 may be arranged to decode the receiver output signal 26 to generate a decoder output signal 28. In the absence of transmission or decoding errors, the decoder output signal 28 may be identical to the input data stream 20. Furthermore, a transmission error, e.g., a loss of isolated bits, may not necessarily generate an error in the decoder output signal 28 due to a certain redundancy of the information carried by the coded data stream 22. The decoder unit 18 may, for instance, employ a Viterbi algorithm for decoding the coded data stream 22 represented by, e.g., the receiver output signal 26.

An example of the coding unit 12 is further described in reference to Figure 2. Figure 2 shows a trellis diagram for the coding unit 12, considering the coding unit 12 a state machine. In this example, the state machine may have four possible states: 00, 01 , 10, 1 1. The arrow t in the figure may represent the flow of time. At each instant, e.g., at each instant tO, t1 , t2, or t3, the state of the coding unit 12 may be either 00, 01 , 10, or 1 1 . The current state of the encoder unit 12 may, for instance, be the current state of a shift register (not shown) of the coder unit 12. The state of the shift register may represent the values of the two last received bits of the input data stream 20. For instance, a first bit of value zero followed by a second bit of value one may set the shift register (and thus the coding unit 12) to the state 01 at time tO. Reception of a third bit may trigger a state transition resulting in a new state at instant t1 . For instance, still assuming that the coder unit 12 is in its state 01 at time tO, a zero bit may trigger the transition 01 to 00, whereas a one bit may trigger the transition 01 to 1 1. In the present trellis diagram, transitions triggered by a one bit are represented by continuous arrows, while transitions triggered by a one bit are represented by dashed arrows. The input data stream 20 may thus be identified with a particular path through the trellis diagram. For instance, assuming that the decoder state is 00 at time tO, the bit sequence 1 10 results in the path 00-10-1 1-01. Each of the eight transitions associated with the set of four states may have associated with it a code word which may be output as the next symbol of the output data stream 22.

For instance, now additionally considering Figure 3, the code words associated with the transitions 00-10, 01-10, 10-01 , and 1 1-1 1 may be 00, 00, 10, and 10, respectively. In the figure, these code words are represented as tags to the arrows of the respective transitions. Furthermore, now turning to Figure 4, the transitions 00-10, 01-00, 10-1 1 , and 1 1-01 may have the code words 1 1 , 1 1 , 01 , and 01 , respectively. In this example, each code word is a bit string consisting of a first bit and a second bit. In other words, the code word length may be two. Indeed, the present specification focuses on an implementation in which the code word length may be two. However, the teaching of the present disclosure can perhaps also be used in a scheme in which code word consists of more than two bits and notably in a scheme in which code word consists of a pair number of bits.

Turning back to Figures 3 and 4, it is noted that the mapping from transitions to code words is not necessarily unique. For instance, the symbol 1 1 may result from either the transition 00 to 10 or the transition 01 to 00. To reconstruct the most likely path through the trellis diagram and thus the original data stream 20, the Viterbi decoding algorithm therefore involves a comparison between a variety of paths, e.g., all paths, of the trellis diagram and selecting a winning path, i.e., a path which corresponds best to the received sequence of symbols in, e.g., the receiver output signal 26. To this end, a distance between the last received symbol and each of the eight transitions shown in Figures 3 and 4 may be computed, resulting in a set of eight branch metric values associated with the eight transitions (branches). The actual computation may involve computing less than eight values due to algebraic symmetries. The details of these computations may depend on the definition of the distance between the received symbol and the various transitions.

The sum of branch metric values associated with a given path through the trellis diagram

(see Figure 2) is known as the path metric value. The original bit stream 20 may be recovered by selecting the path having the smallest path metric value. The path metric value for a given state at a given instant, e.g., the path metric value for the state 00 at time t3 in Figure 2, may be obtained from the path metric values of the two predecessor states (states 00 and 01 in this example) by adding the corresponding branch metric value, thus obtaining two new path metric values and by further selecting the smaller one of these two path metric values. For example, the path metric value of state 00 at time t2 (see again Figure 2) plus the branch metric value for the transition 00 to 00 may result in a first candidate path metric value of the state 00 at time t3. Similarly, the path metric value of the state 01 at time t2 plus the branch metric value for the transition 01 to 00 may give a second candidate path metric value associated with the state 00 at time t3. The smaller one among these two candidate path metric values may be selected as the path metric value of the state 00 at time t3. Furthermore, the transition associated with the selected candidate path metric value, i.e., the winning path metric value, may be represented by a decision matrix. Thus, each state at a chosen instant, e.g., time t3 may have a winning path leading to that state, said winning path having associated with it a path metric value. In the present example of a set of four states, there may thus be four winning paths for the chosen instant (e.g., time t3). More specifically, each state may have a winning path leading to that particular state. Selecting among these winning paths the one with the smallest path metric value may be expected to provide the original data stream 20 up to that instant or up to at least some earlier instant (e.g., time tO).

Figures 5 and 6 are analogous to Figures 3 and 4 and illustrate a second example of an assignment of code words to the eight transitions described above.

Referring now to Figure 7, an example of a sequence of sample values taken from, e.g., the receiver output signal 26 (see Figure 1 ) is illustrated. Each circle in the plot may indicate an instantaneous level y of, e.g., the receiver output signal 26 at time t. The samples may be grouped in successive pairs, each pair representing a received symbol of two bits. For example, the four samples taken at times 1 , 2, 3, and 4, respectively, may in this example have a value y = 0.74, 0.95, 0.85, and -1.2, respectively. These values may be rounded to yield the sequence 1 , 1 , 1 , - 1 which may be interpreted as the bit sequence 1 1 10, assuming that the bit values 0 and 1 correspond to the analog levels of -1 and +1 , respectively. Rounding the sample values may thus yield a bit sequence known as a sequence of hard bits. In other words, each sample value may be converted into a hard bit. A pair of sample values may thus yield a hard symbol. The branch metric values mentioned above may be computed on the basis of the thus obtained hard symbols. The branch metric values may, for instance, be defined as Hamming distances between the hard symbols and the code words.

Alternatively, the successive pairs of sample values may be treated as soft symbols, each soft symbol comprising a first sample value SO and a second sample value S1. The branch metric values may, in this case, be computed directly from the soft symbols rather than from hard symbols derived from the soft symbols. Processing a soft symbol may involve a larger computational effort compared to working with hard symbols because a soft symbol may take more than only two different values. On the other hand, working with soft symbols rather than with hard symbols can make the decoding algorithm more reliable. In the example of Figure 7, the first two soft symbols are S=(0.74; 0.95) and S=(0.85; -1.2).

The distance between a code word CW and soft symbol S may, for instance, be chosen Euclidean. For instance, expressing the code word CW as the pair (B0, B1 ) and the soft symbol S as(S0, S1 ), the distance between them may be defined as

D(CW,S) = (B0 - S0) ^** 2 + (B1 - S1 ) ^** 2 wherein B0, SO, B1 , and S1 are the analog levels of the first and second bits of the code word CW and of the soft symbol S, respectively. The double asterisk means "to the power of". The analog levels of the code word bits may be -1 and +1 , for example. The values of the soft bits SO and S1 may typically be approximately -1 or +1 , but deviations from these expected values are possible due to, e.g., noise, interference, and other kinds of transmission deficiencies. The distances for the four different code words 00, 01 , 10, and 1 1 can thus be expressed explicitly as D(00,S) = (-1 - S0) ^** 2 + (-1 - S1) ^** 2

D(01 ,S) = (-1 - S0) ^** 2 + (1 - S1 ) ^** 2

D(10,S) = (1 -S0) ^** 2 + (0-S1) ^** 2

D(11 ,S) = (1 - S0) ^** 2 + (1 - S1 ) ^** 2

Expanding the above expressions and omitting the terms SO to the power of 2 and S1 to the power of two in each of the terms, the distance D(CW,S) may be redefined as follows:

D(00,S) = SO + S1

D(01,S) = S0-S1

D(10,S) = -S0 + S1 =-D(01,S)

D(11,S) = -S0-S1 =-D(00,S)

Considering the pair S = (SO, S2) as a complex number S = SO + J ^* S1 and multiplying S or conj(S) with (1-J) yields:

S ^* (1-J) = D(00, S) + J ^* D(10,S)

-S ^* (1-J) = D(11,S) + J ^* D(01,S)

conj(S) ^* (1-J) = D(01, S) + J ^* D(11 ,S)

-conj(S) ^* (1-J) = D(10, S) + J ^* D(00,S)

This may rearranged as:

D(0, S) + J ^* D(2, S) = S ^* (1-J)

D(2, S) + J ^* D(0, S) = conj(S) ^* (-1 +J)

D(1 , S) + J ^* D(3, S) = conj(S) ^* (1-J)

D(3, S) + J ^* D(1,S) = S ^* (-1+J) wherein the code words (0,0), (0,1), (1,0), and (1,1) are denoted 0, 1, 2, and 3, respectively, and "conj" denotes complex conjugation.

These expressions shows that a pair of distance values may be obtained from a single complex multiplication of the complex soft symbol S or its conjugate and the complex number (1-J) or (-1+J). This can be exploited to compute the branch metric values in a particularly fast manner using a complex algebra unit capable of processing the real and imaginary parts of a complex number in parallel.

The table in Figure 8 relates to the states, transitions and associated code words shown in Figure 3. The four possible final states 00, 01, 10, and 11 are listed in column 1 as 0, 1, 2, and 3, respectively. The letter K represents the corresponding index (not to be confused with the constraint length). Column 2 indicates the code word associated with a transition to a respective state for the set of transitions shown in Figure 3. Column 3 shows the code words using decimal notation. Column 4 shows the corresponding branch metric values, i.e., the distances between the respective code word CW and the received soft symbols. Column 5 indicates the equivalent complex expressions. The complex expressions can be conveniently used to evaluate a pair of branch metric values. For instance, the complex number S ^* (1-J) may be computed using complex algebra to obtain simultaneously the branch metric values for the two transitions 00-00 (K=0) and 10-01 (K=1 ) shown in Figure 3. The branch metric values for K=2 and K=3 can likewise be obtained from the same complex number S ^* (1 -J).

The table in Figure 9 is analogous to the one of Figure 8 but refers to the second set of transitions leading to the state 00, 01 , 10, and 1 1 , respectively, as shown in Figure 4. It is noted that their branch metric values differ from the ones associated with the first set of transitions (see Figures 3 and 8) only in a minus sign. Therefore, they do not need to be explicitly computed. Instead, the second candidate path metric values associated with them may be computed from the path metric values of the respective predecessor state by subtracting (instead of adding) the branch metric values specified in Figure 8.

It is further noted that Figures 8 and 9 may equally apply to the two sets of transitions and the associated code words shown in the example of Figures 5 and 6.

The tables in Figures 10 and 1 1 are analogous to the table of Figure 8 but relate to an example in which the encoder unit 12 has a total of 64 states. The branch metric values for the states K=32 to K=63 may be related to those indicated in the table by the identity BM_0(K)=- BM_0(K-32).

The tables in Figures 12 and 13 are analogous to those of Figures 10 and 1 1 and refer to the mentioned second set of path metric values. As in the example of Figures 3 and 4, the branch metric values BM_0 and BM_1 of the first and second set of transitions may differ from each other only in a minus sign.

Figure 14 schematically represents an example of the encoder 12. The encoder 12 may comprise a set of, e.g., six shift registers connected in series for buffering the latest K-1 received bits of the input data stream 20. In the shown example, K=7, K being the constraint length including the latest bit. The encoder unit 12 may be based on octal generator polynomials [133 171 ].

An example of the decoder unit 18 is further described in reference to Figure 15. The decoder unit 18 may comprise an analog to digital converter (ADC) unit 30, a complex algebra unit 32, and an add compare select (ACS) unit 34. The complex algebra unit 32 may be connected to the ADC unit 30. The complex algebra unit 32 may, for instance, be integrated in an arithmetic logic unit of a processor core. The decoder unit 18 may operate as follows. The ADC unit 30 may receive the receiver output signal 26 described above in reference to Figure 1 and generate from this analog signal 26 a stream of soft symbols S, each soft symbol S being a pair of a first sample value SO (first soft bit) and a second sample value S1 (second soft bit). Each soft symbol S may be provided as a pair of two digital numbers or as a digital complex number. The stream of soft symbols S may be further fed to the complex algebra unit 32. The complex algebra unit 32 may compute from each received soft symbol S a set of branch metric values. The complex algebra unit 32 may, for example, compute a branch metric value BM_0(K) for each state of the encoder unit 12. The computed branch metric values may be further fed to the ACS unit 34. The ACS unit 34 may compute a first candidate path metric value and a second candidate path metric value for each state of the encoder unit 12 and select a winning path metric value. To this end, the ACS unit 34 may comprise a first path metric buffer 36 and a second path metric buffer 38. The ACS unit 34 may further generate a set of decision values D for each state of the coder unit 12, the decision values indicating which path metric value among the first and second candidate path metric values was selected as the winning one for each state. The decision values thus generated may be used to update a decision matrix reflecting the decoded data stream. Add compare select units for processing branch metric values are known in the art, and a variety of different architectures are known.

The complex algebra unit 32 may be designed to take full advantage of the complex number representation of the soft symbols S and the corresponding complex expression for pairs of branch metric values described herein. The complex algebra unit 32 may thus compute a pair of branch metric values from a single complex soft symbol S=S0+J ^* SI in parallel. The complex algebra unit 32 may, for instance, comprise or be integrated in a digital signal processor which may comprise dedicated complex number processing circuitry. The complex computations may thus be performed with the same speed as real computations. An advantage of computing pairs of branch metric values using complex algebra is that these computations can be performed about twice as fast as equivalent real computations using, for instance, a general purpose processor with complex algebra capabilities.

The invention may also be implemented in a computer program for running on a computer system, at least including code portions for performing steps of a method according to the invention when run on a programmable apparatus, such as a computer system or enabling a programmable apparatus to perform functions of a device or system according to the invention.

A computer program is a list of instructions such as a particular application program and/or an operating system. The computer program may for instance include one or more of: a subroutine, a function, a procedure, an object method, an object implementation, an executable application, an applet, a servlet, a source code, an object code, a shared library/dynamic load library and/or other sequence of instructions designed for execution on a computer system.

The computer program may be stored internally on computer readable storage medium or transmitted to the computer system via a computer readable transmission medium. All or some of the computer program may be provided on transitory or non-transitory computer readable media permanently, removably or remotely coupled to an information processing system. The computer readable media may include, for example and without limitation, any number of the following: magnetic storage media including disk and tape storage media; optical storage media such as compact disk media (e.g., CD-ROM, CD-R, etc.) and digital video disk storage media; nonvolatile memory storage media including semiconductor-based memory units such as FLASH memory, EEPROM, EPROM, ROM; ferromagnetic digital memories; MRAM; volatile storage media including registers, buffers or caches, main memory, RAM, etc.; and data transmission media including computer networks, point-to-point telecommunication equipment, and carrier wave transmission media, just to name a few.

A computer process typically includes an executing (running) program or portion of a program, current program values and state information, and the resources used by the operating system to manage the execution of the process. An operating system (OS) is the software that manages the sharing of the resources of a computer and provides programmers with an interface used to access those resources. An operating system processes system data and user input, and responds by allocating and managing tasks and internal system resources as a service to users and programs of the system.

The computer system may for instance include at least one processing unit, associated memory and a number of input/output (I/O) devices. When executing the computer program, the computer system processes information according to the computer program and produces resultant output information via I/O devices.

In the foregoing specification, the invention has been described with reference to specific examples of embodiments of the invention. It will, however, be evident that various modifications and changes may be made therein without departing from the broader spirit and scope of the invention as set forth in the appended claims.

The connections as discussed herein may be any type of connection suitable to transfer signals from or to the respective nodes, units or devices, for example via intermediate devices. Accordingly, unless implied or stated otherwise, the connections may for example be direct connections or indirect connections. The connections may be illustrated or described in reference to being a single connection, a plurality of connections, unidirectional connections, or bidirectional connections. However, different embodiments may vary the implementation of the connections. For example, separate unidirectional connections may be used rather than bidirectional connections and vice versa. Also, plurality of connections may be replaced with a single connection that transfers multiple signals serially or in a time multiplexed manner. Likewise, single connections carrying multiple signals may be separated out into various different connections carrying subsets of these signals. Therefore, many options exist for transferring signals.

Although specific conductivity types or polarity of potentials have been described in the examples, it will be appreciated that conductivity types and polarities of potentials may be reversed.

Each signal described herein may be designed as positive or negative logic. In the case of a negative logic signal, the signal is active low where the logically true state corresponds to a logic level zero. In the case of a positive logic signal, the signal is active high where the logically true state corresponds to a logic level one. Note that any of the signals described herein can be designed as either negative or positive logic signals. Therefore, in alternate embodiments, those signals described as positive logic signals may be implemented as negative logic signals, and those signals described as negative logic signals may be implemented as positive logic signals.

Furthermore, the terms "assert" or "set" and "negate" (or "deassert" or "clear") are used herein when referring to the rendering of a signal, status bit, or similar apparatus into its logically true or logically false state, respectively. If the logically true state is a logic level one, the logically false state is a logic level zero. And if the logically true state is a logic level zero, the logically false state is a logic level one.

Also for example, in one embodiment, the illustrated examples may be implemented as circuitry located on a single integrated circuit or within a same device. For example, units 16 and 18 may be located on a single integrated circuit. Alternatively, the examples may be implemented as any number of separate integrated circuits or separate devices interconnected with each other in a suitable manner. For example, units 16 and 18 may be separate devices connected to each other.

Also for example, the examples, or portions thereof, may implemented as soft or code representations of physical circuitry or of logical representations convertible into physical circuitry, such as in a hardware description language of any appropriate type.

Also, the invention is not limited to physical devices or units implemented in nonprogrammable hardware but can also be applied in programmable devices or units able to perform the desired device functions by operating in accordance with suitable program code, such as mainframes, minicomputers, servers, workstations, personal computers, notepads, personal digital assistants, electronic games, automotive and other embedded systems, cell phones and various other wireless devices, commonly denoted in this application as 'computer systems'.

However, other modifications, variations and alternatives are also possible. The specifications and drawings are, accordingly, to be regarded in an illustrative rather than in a restrictive sense.

In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. The word 'comprising' does not exclude the presence of other elements or steps then those listed in a claim. Furthermore, the terms "a" or "an," as used herein, are defined as one or more than one. Also, the use of introductory phrases such as "at least one" and "one or more" in the claims should not be construed to imply that the introduction of another claim element by the indefinite articles "a" or "an" limits any particular claim containing such introduced claim element to inventions containing only one such element, even when the same claim includes the introductory phrases "one or more" or "at least one" and indefinite articles such as "a" or "an." The same holds true for the use of definite articles. Unless stated otherwise, terms such as "first" and "second" are used to arbitrarily distinguish between the elements such terms describe. Thus, these terms are not necessarily intended to indicate temporal or other prioritization of such elements. The mere fact that certain measures are recited in mutually different claims does not indicate that a combination of these measures cannot be used to advantage.