Viterbi decoder and method using sequential two-way add-compare-select operations

#The present invention pertains to electronic communications, and in particular, to decoding convolutionally encoded data.

#Digital communication systems have many ways of transmitting data through noisy communication channels that help facilitate recovery of the data at the receiver. One conventional method involves convolutionally encoding the data prior to transmission. In such a system, convolutional encoding may be performed after the addition of error correction codes and compression of the data. The convolutional encoding process embeds bits in the data stream resulting in a greater number of bits for transmission depending on the rate of the coder.

#In a digital wireless system, for example, in-phase (I) signals and qudrature-phase (Q) signals may be generated from the convolutionally encoded data and modulated onto a carrier frequency for transmission to a receiver. In this way, a wireless communication device can transmit digital information, including voice and data, over a noisy channel to another wireless communication device via a base station, for example.

#The appended claims point out different embodiments of the invention with particularity. However, the detailed description presents a more complete understanding of the present invention when considered in connection with the figures, wherein like reference numbers refer to similar items throughout the figures and:

#FIG. 1 is a functional block diagram of a receiver in accordance with an embodiment of the present invention;

#FIG. 2 is an illustration of a four-way trellis butterfly diagram which illustrates the performance of four-way add-compare-select (ACS) operations;

#The following description and the drawings illustrate specific embodiments of the invention sufficiently to enable those skilled in the art to practice it. Other embodiments may incorporate structural, logical, electrical, process, and other changes. Examples merely typify possible variations. Individual components and functions are optional unless explicitly required, and the sequence of operations may vary. Portions and features of some embodiments may be included in or substituted for those of others. The scope of the invention encompasses the full ambit of the claims and all available equivalents.

#FIG. 1 is a functional block diagram of a receiver in accordance with an embodiment of the present invention. Receiver 120 is configured to receive convolutionally encoded data which may be decoded by Viterbi decoder 100 and may be especially suitable for receiving data over noisy communication channels. Although the present invention is applicable to almost any communication device, the advantages of the present invention are particularly applicable to wireless, handheld and portable communication devices. By way of example, wireless, handheld and portable communication devices may include wireless and cellular telephones, smart phones, personal digital assistants (PDAs), web-tablets and any device that may provide wireless access to a network such as an intranet or the internet.

#An input signal having convolutionally encoded data is received by input device 122 which may, for example, be an antenna, a cable, an optical detector, or the like. Converter 124 may process the received signal to generate in-phase (I) and quadrature-phase (Q) signals which may be down-converted from a modulated carrier frequency to baseband frequency and converted to serial bit streams with an analog to digital converter. The I and Q serial bit streams are provided to Viterbi decoder 100. Using the encoded data streams, the decoder 100 calculates branch metrics and path metrics for the data and determines the path of the data that has the greatest likelihood of occurrence. Decoder 100 generates an output decoded data signal indicative of the data that is most likely to have been transmitted, even when the data is received over a very noisy communication channel. Although this embodiment of the present invention is described as using I and Q signal inputs, other embodiments of the present invention are not limited to the use of I and Q modulated signals. For example, the present invention is equally suitable for use with any modulation scheme, and is also suitable for use with baseband signals having no modulation.