Abstract:
The present disclosure provides simple methods and systems for generating modified branch metrics for the Viterbi decoder so that the decoder can decode the uncorrelated incoming signals without the influence of either the signal power level or the noise variance. The proposed branch metrics noticeably improve the performance of the Viterbi algorithm in such cases. The present disclosure also provides methods and systems for reducing the length of the demodulated symbols for efficient computation. In an exemplary method, it is shown that the only requirement of the proposed modified branch metric, in addition to the traditional branch metric requirements, is the computation of the noise energy. In another exemplary system, an arrangement of circuit modules offers an implementation of one of the embodiments of the proposed method.

Description:
REFERENCE TO RELATED APPLICATIONS  
       [0001]     The present application claims the benefit of U.S. Provisional Application No. 60/533,193, filed 30 Dec. 2003 and entitled “Viterbi Decoder for Uncorrelated Signals,” the entirety of which is incorporated herein by reference. 
     
    
     TECHNICAL FIELD  
       [0002]     The present invention relates to a communication system and, more particularly, to a Viterbi decoder and its branch metrics.  
       BACKGROUND  
       [0003]     Typically a communication link includes three major elements: a transmitter, a communication channel, and a receiver. The transmitter and the receiver elements can be further subdivided into sub-systems, which include a data source, an encoder, a modulator, a demodulator, a decoder, and an original signal regenerator.  
         [0004]     The data source generates the appropriate information signal that is intended to be sent to the destination. This signal may be digital or analog. Even for analog signals, it is often desirable to digitally encode the signal prior to its transmission. To provide error correction capacity at the receiver, the encoder transforms the information sequence into encoded sequence by adding redundancy to a digital data stream, in the form of additional data bits. The process of adding redundant information is known as “channel coding,” and the encoder is also known as “channel encoder.” 
         [0005]     Coding is an effective method for trading bandwidth and implementation complexity against transmitter power. In general, higher transmitter power results in higher signal to noise ratio (SNR), which means the signal is less susceptible to noise and consequently to error at the receiving end. On the other hand, a low transmission power, and the resulting low SNR, can even make a signal unrecognizable and inseparable from the noise at the receiving end. Under such circumstances, where the probability of error is high, coding helps reduce the error probability and retrieve the original signal.  
         [0006]     Different coding schemes are in use today, including Convolutional coding and Block coding. The Convolutional coding results in a serial data stream, whereas the Block coding results in large message blocks with a fixed number of elements within each block. The encoded signals in both methods include redundant information, as mentioned above. After encoding, the modulator converts the encoded information into physically transmittable signals. Modulation techniques depend on the type of information signal and the particular transmission medium.  
         [0007]     A channel is the medium for transmission of the modulated information. It can be a copper wire, a coaxial cable, or the space. To various degrees, all channels introduce some form of distortion to the transmitted signal. The distortions introduced by different channels differ in their noise distribution. Some can be modeled as Additive White Gaussian Noise (AWGN), by which a noise with uniform power spectral density is assumed to be added to the information signal. Others introduce noise in bursts, include fading channels and multipath channels.  
         [0008]     At the receiving end, the demodulator extracts the encoded information from the modulated signal. To retrieve the original digital signal, the extracted encoded data, which is also distorted to some degree by traveling through the channel, is subsequently decoded by the decoder. The decoding process is usually more complicated than the encoding process—it can also be computationally more intensive. Efficient decoding schemes have been developed over the years such as the Viterbi decoding algorithm for recovery of binary data. These schemes discover the distorted parts of the demodulated information and correct them. Finally, decoded data will be used to produce an estimate of the original signal.  
         [0009]     The Viterbi algorithm is a self-correcting decoder that employs a maximum likelihood decoding rule. It computes some kind of probability measure for different “possible replacements” of the received data, based on the “actual” data received. Each possible string of data (up to the last received data symbol) is called a “data path,” and the probability measure associated with each data path is called a “cumulative metric.” Upon the arrival of a new data symbol, the algorithm adjusts each cumulative metric. This incremental adjustment is called a “branch metric.” In practice this is a series of add-compare-select operations. Ultimately, the Viterbi algorithm utilizes the cumulative metrics to calculate the maximum likelihood of a path being the best path. In other words, it finds the string of data most accurately representing the original encoded symbols.  
         [0010]     Most of the existing codes perform relatively well under uniform channel error conditions, such as those of a Gaussian channel mentioned above, while the received data is correlated. However, to maximize the performance of the coding process, there is a need for improving the Viterbi algorithm for those channels in which the error tends to occur in bursts, such as fading channels, or when the received data is uncorrelated. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0011]     The foregoing aspects and many of the attendant advantages of the invention will become more readily appreciated as the same become better understood by reference to the following detailed description, when taken in conjunction with the accompanying drawings, wherein:  
         [0012]      FIG. 1  is a functional block diagram of the transmitting part of a typical communication system, which transmits “data blocks.” 
         [0013]      FIG. 2  is a schematic diagram of the performance of a fading channel, carrying bursts of data with a relatively short time lapse between them.  
         [0014]      FIG. 3  is a schematic diagram of the performance of a fading channel, carrying bursts of data with a relatively long time lapse between them.  
         [0015]      FIG. 4  is a functional block diagram of the receiving part of a typical communication system, which transmits “data blocks.” 
         [0016]      FIG. 5  is a functional block diagram of an embodiment of the branch metric modification system, in accordance with the present invention.  
         [0017]      FIG. 6  is the schematic representation of a bit fetching process in different bursts.  
         [0018]      FIG. 7  is the flow diagram of the modified method of branch metric generation for the Viterbi algorithm according to one embodiment of this invention. 
     
    
     DETAILED DESCRIPTION  
       [0019]     The present invention relates to the modifications of the branch metrics of the Viterbi decoder so that the decoder can decode the uncorrelated incoming signals without the influence of either the signal power level or the noise variance. The proposed modifications noticeably improve the performance of the Viterbi algorithm in such cases. In the following description, several specific details are presented to provide a thorough understanding of the embodiments of the invention. One skilled in the relevant art will recognize, however, that the invention can be practiced without one or more of the specific details, or in combination with or with other components, etc. In other instances, well-known implementations or operations are not shown or described in detail to avoid obscuring aspects of various embodiments of the invention.  
         [0020]     Reference throughout the specification to “one embodiment” or “an embodiment” means that a particular feature, structure, implementation, or characteristic described in connection with the embodiment is included in at least one embodiment of the present invention. Thus, the appearances of the phrases “in one embodiment” or “in an embodiment” in various places throughout the specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures, implementation, or characteristics may be combined in any suitable manner in one or more embodiments.  
         [0021]      FIG. 1  is a functional block diagram of the transmitting part of a typical communication system, which transmits data blocks. A data block  101  represents data arriving in batches of specific size to be transmitted to some destination. Although a higher transmission power helps the signal to be more distinguished from the noise at the destination, or a higher bandwidth allows multiple copies of the same data to be transmitted in case some are distorted, both solutions are costly and can be avoided to a great extent by appropriate encoding of the data. Manipulation, alternative representation, and reordering of the data, along with the addition of redundancy, are some of the ways of protecting the data while optimizing the system. Accordingly, the data within the data blocks enter a channel encoder  102  to be coded and prepared for their transmission through the physical channel such that they would be recoverable at the destination, despite distortions due to noise and cochannel interference (interference).  
         [0022]     An encoded data  103  enters an interleaver  104  for rearrangement of its content. This shuffling of the encoded data  103  helps avoid the loss of a sizable portion of the data in case of error bursts, which by definition are concentrated in time and are not distributed over the data. Once the damaged interleaved data is deinterleaved, the locally corrupted data is broken up and distributed over the entire deinterleaved data, creating independent errors and easier data correction.  
         [0023]     It is important to note that the fading channels fit the model of a bursty error channel. The term fading is used when the amplitude of the received signal drastically varies as a result of the phase difference between a signal and its reflections. Such signals, at times, can weaken or practically cancel each other, or can combine to form a stronger signal. Although fading primarily is a result of the time variation of phases, the fading channel is an accurate model for channels susceptible to error bursts.  
         [0024]     Interleaved data  105  is segmented to several “bursts” and mapped into physical channel bursts,  107 , by a data segmentation and physical channel mapping module  106 . But while data is being transmitted, the characteristics of the channel can change because of the physical changes in the structure of its medium. Channel characteristics influence the traveling signals and can uncorrelate two otherwise correlated data bursts. Changing weather conditions or other factors, for example, can change the “channel response,” which is defined as the response of a channel to an impulse-like signal, and which is an accurate representation of the channel characteristics.  
         [0025]     In a typical communication system, the lengths of the bursts are chosen so that the channel response remains relatively constant during the transmission of each burst. If the time between two bursts is short enough, this assumption will stay valid even for two consecutive bursts, and preserves the correlation of the signals, of the noise, and of the interferences. However, if the time lapse between the two consecutive bursts is long enough, the signals, the noise, and the interference will be each uncorrelated and will adversely affect the performance of the traditional Viterbi channel decoder.  
         [0026]      FIG. 2  is a schematic diagram of the performance of the traditional Viterbi algorithm if the time delay between transmitted bursts is short and the signals, the noise, and the interferences of the neighboring bursts are each correlated. In contrast,  FIG. 3  schematically represents the performance of the traditional Viterbi algorithm when the time delay between transmitted bursts is long and consequently the signals, the noise, and the interferences affecting the signals of the neighboring bursts are each uncorrelated.  
         [0027]      FIG. 4  is a functional block diagram of the receiving part of a typical communication system, which transmits data blocks. Received data bursts  401 , in addition to the transmitted information signal, include noise and possibly interference. A physical channel demapping and data combination module  402  combines the received data bursts  401  into data blocks  403 , which are still interleaved. Subsequently, a deinterleaver  404  rearranges the data block to its original encoded order.  
         [0028]     If the time between transmitted physical channel bursts  107  has been long enough, the deinterleaver  404  will further distribute the data extracted from an already uncorrelated signal, noise, and interference. Such data,  405 , entering a channel decoder  406 , will affect the branch metrics of the Viterbi algorithm and will lower its performance. The modifications proposed in the present invention, among other advantages, will drastically improve the performance of the channel decoder  406  in such situations. A decoded block data  407  is finally checked by a Cyclic Redundancy Check (CRC) module  408  to identify most of the possible remaining errors.  
         [0029]     In one embodiment the equations for the branch metric modifications are derived as follows. The aim of the Viterbi algorithm, as briefly mentioned above, is to find a set of {{circumflex over (α)} n } that maximizes the likelihood function P({y n }|{α n }), where {α n } is the original signal before coding and {y n } is the quantized received signal, which consists of the coded signal and the noise. In other words, given our observations {y n }, the algorithm tries to find a set of data that maximizes the possibility of such observations. Ideally, the result of such a search should be the original data set {α n }, but, practically, {{circumflex over (α)} n } will be the best result, considering the nondeterministic and random nature of the noise and the interferences. Here P({y n }|{α n }) represents the “cumulative metric” previously described, and if it can be written in the following form: 
 
 J   n   =J   n−1   +y   n   ·s (α n )  Eq. 1 
 
 then y n ·s(α n ) will represent the “branch metric,” since it incrementally adjusts the cumulative metric for each received symbol. The above likelihood function can be written as:  
               P   ⁡     (       {     y   n     }     |     {     α   n     }       )       =       ∏     i   =   1     n     ⁢       1       2   ⁢           ⁢   π   ⁢           ⁢     σ   2           ·     exp   (     -         (       y   i     -     s   ⁡     (     α   i     )         )     2       2   ⁢           ⁢     σ   2           )                 Eq   .           ⁢   2             
 
 where {S(α n )} is the matched filter reconstruction of {α n } based on the received signals {y n }, and σ 2  is the variance of the assumed normally distributed (Gaussian) noise. As a result, {y n } and {S(α n )} have the same power density. After taking natural-log of both sides of Eq. 2, the following manipulations are possible:  
                       log   e     ⁡     (     P   ⁡     (       {     y   n     }     |     {     α   n     }       )       )       =       ⁢         -     1   2       ⁢       ∑     i   =   1     n     ⁢       log   e     ⁡     (     2   ⁢           ⁢   π   ⁢           ⁢     σ   2       )           -       ∑     i   =   1     n     ⁢         (       y   i     -     s   ⁡     (     α   i     )         )     2       2   ⁢           ⁢     σ   2                         =       ⁢         -     1   2       ⁢       ∑     i   =   1     n     ⁢       log   e     ⁡     (     2   ⁢           ⁢   π   ⁢           ⁢     σ   2       )           -                     ⁢         ∑     i   =   1     n     ⁢                y   i          2     +            s   ⁡     (     α   i     )            2         2   ⁢           ⁢     σ   2           +       ∑     i   =   1     n     ⁢         y   i     ·     s   ⁡     (     α   i     )           σ   2                       =       ⁢         log   e     ⁡     (     P   ⁡     (       {     y     n   -   1       }     |     {     α     n   -   1       }       )       )       -       1   2     ⁢       log   e     ⁡     (     2   ⁢           ⁢   π   ⁢           ⁢     σ   2       )         -                     ⁢                  y   n          2     +            s   ⁡     (     α   n     )            2         2   ⁢           ⁢     σ   2         +         y   n     ·     s   ⁡     (     α   n     )           σ   2                       Eq   .           ⁢   3             
 
         [0030]     If {y n } is stationary and correlated and noise has Gaussian distribution, the metric in Eq. 3 can be written in the form of Eq. 1, and, as mentioned above, y n ·s(α n ) will represent its branch metric. Note that in such a case the branch metric has no dependency on the noise variance. But, if {y n } is the concatenation of uncorrelated segments, such as in the case of data bursts with long delays between consecutive bursts, only the signal within each segment is stationary. Or there is a case in which the interference is stationary within each segment but uncorrelated between segments. Or yet another case in which both {y n } and interference are stationary within each segment but uncorrelated between segments. In such cases, Eq. 3 can be rewritten in the following form, while σ n   2  represents noise variance at the n-th symbol:  
                       log   e     ⁡     (     P   ⁡     (       {     y   n     }     |     {     α   n     }       )       )       =       ⁢         -     1   2       ⁢       ∑     i   =   1     n     ⁢       log   e     ⁡     (     2   ⁢           ⁢   π   ⁢           ⁢     σ   i   2       )           -       ∑     i   =   1     n     ⁢         (       y   i     -     s   ⁡     (     α   i     )         )     2       2   ⁢           ⁢     σ   i   2                         =       ⁢         log   e     ⁡     (     P   ⁡     (       {     y     n   -   1       }     |     {     α     n   -   1       }       )       )       -                     ⁢         1   2     ⁢       log   e     ⁡     (     2   ⁢           ⁢   π   ⁢           ⁢     σ   n   2       )         -                y   n          2     +            s   ⁡     (     α   n     )            2         2   ⁢           ⁢     σ   n   2         +                     ⁢         y   n     ·     s   ⁡     (     α   n     )           σ   n   2                     Eq   .           ⁢   4             
 
 Since the value of  
           -     1   2       ⁢       log   e     ⁡     (     2   ⁢           ⁢   π   ⁢           ⁢     σ   n   2       )         -                y   n          2     +            s   ⁡     (     α   n     )            2         2   ⁢           ⁢     σ   n   2             
 
 remains the same for all symbols and will merely add the same constant to the cumulative metrics of all paths, it can be dropped and Eq. 4 can be written in the following form:  
               J   n     =       J     n   -   1       +         y   n     ·     s   ⁡     (     α   n     )           σ   n   2                 Eq   .           ⁢   5             
 
         [0031]     Note that in this case, unlike the case in which {y n }was stationary and correlated, the branch metric part of Eq. 5 is a function of the Signal to Interference and Noise Ratio (SINR n ). This is clearer when we write Eq. 5 in the following form: 
 
 J   n   =J   n−1 +sign( y   n   ·s (α n ))· SINR   n   Eq. 6 
 
 where sign(x)=1 for x&gt;0 and −1 for x&lt;0. As a matter of fact, in any situation in which the received signals are not uncorrelated symbol by symbol, Eq. 5 is a good approximation of the likelihood function. 
 
         [0032]     To implement the latter set of equations, the present invention modifies Eq. 5 to the following equation: (Note that s(α n ) will always be either +1 or −1, while {y n } is the soft output of the equalizer.)  
               J   n     =       J     n   -   1       +       w   n     ·     y   n     ·     s   ⁡     (     α   n     )                   Eq   .           ⁢   7             where                           w   n     =         E     s   ,   n           σ   n   2               Eq   .           ⁢   8             
 
 and where E s,n  is the total energy of the n-th received symbol. 
 
         [0033]      FIG. 5  is a functional block diagram of an embodiment of the branch metric modification system, in accordance with the present invention. This system, among other functions, generates the necessary values for the computation of the modified branch metrics of Eq. 7. Received signal bursts  501  first enter a channel estimator  502 , which estimates the channel characteristics (channel response). The estimated channel parameters  503  help a matched filter  504  and a noise and interference measurement module  509  to more accurately perform their functions by having more information about what happened to the traveling signal as a result of the channel behavior. {S(α n )} is the sign of the correct encoded signals which have passed the channel and the processing at the receiving end before the channel decoder.  
         [0034]     The output of the noise and interference measurement module  509  is utilized by a Soft Output Bit Fetch Decision module  511  to simplify required branch metric computations, as elaborated below. The noise and interference measurement module  509  also produces the estimated value of the energy of the noise per symbol, E n , which will be proved to be the only required value for computing w n , or the only additional computation compared to the computation of a traditional branch metric. If the energy per symbol of information signal is E s , the energy per symbol of information signal at the output of the matched filter  504  will be E s   2 . Now assuming that a demodulator  506  does not change the power ratio of the signal to the noise, w n  can be written as:  
               w   n     =           E   s   2           E   s     ·     E   n         =     1     E   n                 Eq   .           ⁢   9             
 
 where E n , as mentioned above, is produced by the noise and interference measurement module  509 . Therefore, to compute w n , there is no need to estimate the energy of the signal. Also since E n  is estimated for each burst, w n  is only updated once for each burst. 
 
         [0035]     In yet another implementation, to simplify the process, w n  is not multiplied by every y n  output of a demodulator  506 ; rather, a procedure is introduced to select a limited number of its output bits. This procedure is called fetching. It should be noted that fetching is not required for the generation of modified branch metrics. It is merely an additional scheme to make decoder computations more efficient while using modified branch metrics.  
         [0036]     In this procedure, if the soft output y n  of the demodulator  506  has K bits, (b K−1 , b K−2 , . . . , b K , . . . , b 0 ), only L bits of it will be fetched to form y′ n , (b i+L−1 , b i+L−2 , . . . , b i+1 , b i ). Here i is calculated by the Soft Output Bit Fetch Decision module  511 , using the following equation: 
 
 i= round(log 2 ( w   n ))+ c , 0 ≦i≦K−L  
 
 where c is a constant, computed based on the value range of y n  and the bit margin. In fix point implementation, c is determined by the number of fix point bits of soft equalizer output (B 1 ), the input number of fix point bits of Viterbi decoder (B 2 ), and the range of round(log 2 (w n )). c should satisfy 
 
 c +max( abs (round(log 2 ( w   n ))))+ B   2 ≧ B   1  
 
         [0037]      FIG. 6  is the schematic representation of a bit fetching process for the first and the rest of the bursts. The actual process of bit fetching is performed in a Soft Output Bit Fetching module  508 . All the necessary components of Eq. 7, which include the components of the modified branch metric, are subsequently passed to the channel decoder, which in turn employs the Viterbi algorithm. y′ n  is the simplified implementation of y n , which means not to divide w n , but to divide 2 round(log     2     (w     n     )) . In the fix point implementation, it only needs to fetch the soft output of the equalizer from a certain bit i.  
         [0038]      FIG. 7  is the flow diagram of the modified method of branch metric generation for the Viterbi algorithm according to an embodiments of this invention. At step  701  the transmitted signal, which carries the modulated and encoded data, is received. At step  702 , using the received signal, the characteristics of the channel are estimated. The knowledge of channel characteristics will help to more accurately estimate and measure the signal and the noise during subsequent steps.  
         [0039]     At step  703 , the transmitted signal is demodulated and at step  704  the demodulated symbols are quantized to soft outputs. At step  705  the 0, or 1 binary values of the received signal is estimated and, subsequently at step  706 , −1 or +1 is assigned to each binary value, respectively. At step  707  the noise is measured and the energy of the noise per data symbol is computed. At step  708  a branch metric is formed by multiplying the quantized value of a symbol by the assigned −1 or +1, and deviding by the noise energy of the same symbol. In step  709  this branch metric is used to update the cumulative metric.  
         [0040]     The preferred and several alternate embodiments have thus been described. One of ordinary skill after reading the foregoing specification will be able to effect various changes, alterations, combinations, and substitutions of equivalents without departing from the broad concepts disclosed. It is therefore intended that the scope of the letters patent granted hereon be limited only by the definitions contained in the appended claims and equivalents thereof, and not by limitations of the embodiments described herein.